对偶单纯形法灵敏度分析

对偶单纯形法灵敏度分析第一页，共六十六页，2022年，8月28日第四节对偶单纯形法

对偶单纯形法并不是求对偶问题解的方法，而是利用单纯形法求解规划问题时运用了对偶理论。也就是说：对偶单纯形法与单纯形法一样都是是求解线性规划的一种基本方法。它是根据对偶原理和单纯形法原理设计出来的，因此称为对偶单纯形法。

在了解对偶单纯形法的实质之前，我们回顾一下单纯形法。单纯形法开始于初始基可行解。如果不满足最优性条件，则要换基迭代转到能使目标函数值得到改善的邻近顶点上。在这个转换过程中，存在两个原则:一是首先保持原问题的解仍是可行的，另一个是要求目标函数值有改善。

如何保证可行？第二页，共六十六页，2022年，8月28日项目非基变量基变量XBXNXS0XSbBNICj-ZjCBCN0项目基变量非基变量XBXNXSCBXBB-1bIB-1NB-1

Cj-Zj0CN-CBB-1N-CBB-1

初始单纯形表CBCN0单纯形法是在保持所有约束条件常数项总是保持大于等于零的情况（保证可行），通过迭代，使所有检验数小于等于零（求最大值），求得最优解。第三页，共六十六页，2022年，8月28日1、当原问题达到最优时，松弛变量经过上述转换后构成的检验数的相反数为其对偶问题的一个可行解，反之亦成立原问题表中的检验数满足最优性条件CN-CBB-1N≤0

-CBB-1≤0;ATY≥CT;

Y≥0YT=CBB-1从上面可以看出：也就是说，当原问题达到最优时，对偶问题的解可行。并且根据对偶的性质，我们可以确定此时对偶问题也达到最优CB:1×mB-1：m×mCBB-1：1×mY：m×1第四页，共六十六页，2022年，8月28日项目非基变量基变量XBXNXS0XSbBNICj-ZjCBCN0项目基变量非基变量XBXNXSCBXBB-1bIB-1NB-1

Cj-Zj0CN-CBB-1N-CBB-1

初始单纯形表也就是：单纯形法计算时只要原问题可行（B-1b≥0），对偶问题可行（即检验数小于0），解就是最优解。单纯形法的基本过程就是保证原问题解可行的情况下，不停迭代，直至对偶问题也达到可行，此时原问题达到最优，对偶问题也达到最优第五页，共六十六页，2022年，8月28日根据刚才所说，单纯形法只要单纯形法计算时只要原问题可行（B-1b≥0），对偶问题可行（即检验数小于0），解就是最优解。所以，我们利用单纯形法对原问题求解时，如果首先保持对偶问题的可行性（即原问题检验数≤0），然后再看原问题是否可行，如果此时原问题的解不可行，则换基迭代，换基过程中保证对偶可行（检验数≤0），直至原问题由不可行解变为可行解，此时就得到它的最优解，——这就是对偶单纯形法的基本思想。第四节对偶单纯形法

也就是说：对偶单纯形法是在保持原问题所有检验数都小于等于零的基础上，通过迭代，使原问题的解（即右边常数项）都大于等于零，从而求得最优解。第六页，共六十六页，2022年，8月28日第四节对偶单纯形法（2）初始解不可行，即右端常数项有负分量（如果原问题可行，则直接用单纯形法）使用对偶单纯形法必须满足两个条件：（1）单纯形表中的所有检验数必须符合对偶可行，即小于等于0第七页，共六十六页，2022年，8月28日①先找一个基，建立初始对偶单纯形表，使检验数全部非正，即C全部为非正；②若b列元素非负，则已经是最优基。反之，则换基迭代，直至原问题可行。第四节对偶单纯形法怎么做呢？第八页，共六十六页，2022年，8月28日例用对偶单纯形法求解该问题用单纯形法求解时，需要先化标准型，此时约束方程两边左边需要减去剩余变量，同时为了构造单位阵，需要添加人工变量，采用大M法求解。第四节对偶单纯形法思考：上面约束方程化为标准型后，两边乘以-1，就可得到单位阵。此时能否用单纯形法？原因?答：不能。因为此时右边常数项为负数，解不可行。为了保证初始解可行第九页，共六十六页，2022年，8月28日例用对偶单纯形法求解第四节对偶单纯形法能否用对偶单纯形法呢？对偶单纯形法初始对偶单纯形表只要保证对偶可行，即检验数全部非正即可。并不要求初始解可行，所以右边常数项可以非负，此题目价值系数均为负，意味着初始单纯形表格的检验数为负，而右端常数项又有负数，正好满足对偶单纯形法的要求。第十页，共六十六页，2022年，8月28日例用对偶单纯形法求解将约束方程化为标准型，再用（-1）乘不等式两边第四节对偶单纯形法第十一页，共六十六页，2022年，8月28日cj

-1-40-300CBXBbx1

x2x3x4x5x600x5x6-3-2-1-21-11021-4-1010-1-40-300此时，初始单纯形表检验数均小于等于0，对偶可行，但原问题初始解不可行第四节对偶单纯形法初始对偶单纯形表第十二页，共六十六页，2022年，8月28日cj

-1-40-300CBXBbx1

x2x3x4x5x600x5x6-3-2-1-21-11021-4-1010-1-40-300先选出基变量后选进基变量原问题不可行，应该换基迭代。但按对偶单纯形法的思想，每次均应保证检验数均非正cj

-1-40-300CBXBbx1

x2x3x4x5x6-10x1x63-812-11-100-3-2-32130-2-1-2-10第十三页，共六十六页，2022年，8月28日cj

-1-40-300CBXBbx1

x2x3x4x5x6-10x1x63-812-11-100-3-2-32130-2-1-2-10-10x1x37417/205/2-2-1/203/213/2-1-1/270-1/20-1/2-2-1/2最优解X*=（7，0，4，0）TZ*=-7第十四页，共六十六页，2022年，8月28日例6用对偶单纯形法求解（P）第十五页，共六十六页，2022年，8月28日1-4/3---10-5/21/21-1/221-1/23/20-1/20-4-10-1-8/5--22/501-1/5-2/51/511/5107/5-1/5-2/500-3/5-8/5-1/5[][]单纯形表第十六页，共六十六页，2022年，8月28日第四节对偶单纯形法

使用对偶单纯形法求初始解时右边常数项可以为负，所以对于一些大于等于号的约束表达式不需要添加人工变量，只要两边同时乘上-1，就可用对偶单纯形法求解，简化计算，这是该方法的优点。缺点是很难找到一个初始解使得所有检验数都小于等于零，因而很少单独使用。第十七页，共六十六页，2022年，8月28日1、什么是灵敏度分析？

灵敏度分析是指系统或事物因为周围条件变化而显示出来的敏感程度分析。一、含义和研究对象第五节灵敏度分析第十八页，共六十六页，2022年，8月28日

在生产计划问题的一般形式中，A代表企业的技术状况，b代表企业的资源状况，而C代表企业产品的市场状况，在这些因素不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值决定。在实际生产过程中，上述三类因素均是在不断变化的，如果按照初始的状况制订了最佳的生产计划，而在计划实施前或实施中上述状况发生了改变，则决策者所关心的是目前所执行的计划还是不是最优，如果不是应该如何修订原来的最优计划。更进一步，为了防止在各类状况发生时，来不及随时对其变化作出反应，即所谓“计划不如变化快”，企业应当预先了解，当各项因素变化时，应当作出什么样的反应。第五节灵敏度分析第十九页，共六十六页，2022年，8月28日1、什么是灵敏度分析？

是指研究线性规划模型的某些参数(bi,cj,aij）或限制量（xj,约束条件）的变化对最优解的影响及其程度的分析过程<也称为优化后分析>。一、含义和研究对象s.t.第五节灵敏度分析第二十页，共六十六页，2022年，8月28日回答两个问题：

①这些系数在什么范围内发生变化时，最优解不变？②系数变化超出上述范围，如何用最简便的方法求出新的最优解？2、灵敏度分析的研究对象：

目标函数的系数cj变化对最优解的影响；约束方程右端系数bi变化对最优解的影响；约束方程组系数矩阵A变化对最优解的影响；

一、含义和研究对象第二十一页，共六十六页，2022年，8月28日

1、在最终单纯形表的基础上进行；2、尽量减少附加的计算工作量；

二、进行灵敏度分析的基本原则第二十二页，共六十六页，2022年，8月28日三、灵敏度分析的步骤原问题对偶问题结论或继续计算的步骤可行解可行解非可行解非可行解可行解非可行解可行解非可行解问题的最优解或最优基不变用单纯形法继续迭代求最优解用对偶单纯形法继续迭代求最优解引进人工变量，编制新的单纯形表重新计算先求问题的最优解.将参数的改变通过计算反映到最终单纯形表上来.检查原问题的可行解和检验数是否满足最优.4.依据不同情况决定继续计算或得到结论.第二十三页，共六十六页，2022年，8月28日4.分析增加一个约束条件的变化四、灵敏度分析的主要内容1.分析

cj

的变化2.分析

bi

的变化3.分析系数

aij的变化5.分析增加一个变量

xj的变化

系数矩阵As.t.第二十四页，共六十六页，2022年，8月28日

对偶问题决策变量的最优解<影子价格>：初始单纯形表最优单纯形表X*=B-1bCN－CBB-1N≤0－CBB-1≤0

原问题基变量的最优解：Z*=CBB-1b最优值：Y*T=CBB-1第二十五页，共六十六页，2022年，8月28日Y*T=CBB-1

XB

I

0基变量非基变量XB基变量基变量基可系数行解

CN－CBB-1NB-1NB-1XNXsB-1bCBB-1b－CBB-1Z*=CBB-1b分析cj

的变化原问题对偶问题结论或继续计算的步骤可行解可行解非可行解非可行解可行解非可行解可行解非可行解问题的最优解或最优基不变用单纯形法继续迭代求最优解用对偶单纯形法继续迭代求最优解引进人工变量，编制新的单纯形表重新计算最优值可能已变第二十六页，共六十六页，2022年，8月28日

x1,x2≥0maxs.t.2x1+2x2≤12z=2x1+3x2

4x1≤165x2≤

15变化

x1,x2≥0maxs.t.2x1+2x2≤12z=(2+λ1)x1+(3+λ2)x2

4x1≤165x2≤

15qi当λ2=0时，将λ1反映在最终单纯形表中，可得从而，表中解仍为最优解的条件是即当

时问题的最优解不变。例1-1分析λ1和λ2分别在什么范围变化时，最优解不变？第二十七页，共六十六页，2022年，8月28日

x1,x2≥0maxs.t.2x1+2x2≤12z=2x1+3x2

4x1≤165x2≤

15变化

x1,x2≥0maxs.t.2x1+2x2≤12z=(2+λ1)x1+(3+λ2)x2

4x1≤165x2≤

15qi当λ1=0时，将λ2

反映在最终单纯形表中，可得从而，表中解仍为最优解的条件是即当时问题的最优解不变。例1-1分析λ1和λ2分别在什么范围变化时，最优解不变？第二十八页，共六十六页，2022年，8月28日美佳公司计划生产I、II两种产品，每天生产条件如表，问(1)该公司应如何安排生产计划才能使总利润最多?(2)若产品Ⅰ的利润不变，则产品Ⅱ的利润在什么范围内变化时，该公司的最优生产计划将不发生变化？(3)若产品Ⅰ的利润降至1.5百元/单位，而产品Ⅱ的利润增至2百元/单位，最优生产计划有何变化

？例2-1设备A(h)设备B(h)调试工序(h)利润(百元)ⅠⅡ每天可用能力资源产品0562112115245第二十九页，共六十六页，2022年，8月28日例2-1如何安排生产计划才能使总利润最多？解：(1)设x1,x2分别表示Ⅰ、Ⅱ两种产品的生产数量，得LP模型maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5x1,x2≥0用单纯形法求解得最终单纯形表设备A(h)设备B(h)调试工序(h)利润(百元)ⅠⅡ每天可用能力资源产品0562112115245第三十页，共六十六页，2022年，8月28日例2-1如何安排生产计划才能使总利润最多？解：(1)设x1,x2分别表示Ⅰ、Ⅱ两种产品的生产数量，得LP模型maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5x1,x2≥0用单纯形法求解得最终单纯形表得最优解为：X*=(7/2,3/2,15/2,0,0)Tzmax=8.5(百元)。即每天生产3.5单位产品Ⅰ，1.5单位产品Ⅱ时总利润最多，且第三十一页，共六十六页，2022年，8月28日maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5x1,x2≥0例2-1解：(2)将产品Ⅱ的利润变化反映在最终单纯形表中，可得maxz=2x1+(1+△c2)x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5x1,x2≥0表中解仍为最优解的条件是产品Ⅱ的利润在什么范围内变化时，最优生产计划不会发生变化？即故当产品Ⅱ的利润在范围变化时，最优生产计划不变。1→1+△c2第三十二页，共六十六页，2022年，8月28日maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5x1,x2≥0例2-1产品Ⅰ利润降至1.5百元/单位，产品Ⅱ的利润增至2百元/单位，生产计划如何变化？解：(3)将产品Ⅰ、Ⅱ的利润变化反映在最终单纯形表中，可得maxz=1.5x1+2x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5x1,x2≥0因有非基变量的检验数大于零需继续用单纯形法迭代计算第三十三页，共六十六页，2022年，8月28日例2-1产品Ⅰ利润降至1.5百元/单位，产品Ⅱ的利润增至2百元/单位，生产计划如何变化？需继续用单纯形法迭代计算θ614-得最优解为：X*=(2,3,0,6,0)T说明随产品利润的改变，为获得最高利润，应将生产计划调整为每天生产2单位产品Ⅰ，3单位产品Ⅱ，且zmax=9(百元)。第三十四页，共六十六页，2022年，8月28日Y*T=CBB-1

XB

I

0基变量非基变量XB基变量基变量基可系数行解

CN－CBB-1NB-1NB-1XNXsB-1bCBB-1b－CBB-1Z*=CBB-1b分析cj

的变化原问题对偶问题结论或继续计算的步骤可行解可行解非可行解非可行解可行解非可行解可行解非可行解问题的最优解或最优基不变用单纯形法继续迭代求最优解用对偶单纯形法继续迭代求最优解引进人工变量，编制新的单纯形表重新计算第三十五页，共六十六页，2022年，8月28日B-1NB-1Y*T=CBB-1

XB

I

0基变量非基变量XB基变量基变量基可系数行解

CN－CBB-1NXNXsB-1bCBB-1b－CBB-1Z*=CBB-1b原问题对偶问题结论或继续计算的步骤可行解可行解非可行解非可行解可行解非可行解可行解非可行解问题的最优解或最优基不变用单纯形法继续迭代求最优解用对偶单纯形法继续迭代求最优解引进人工变量，编制新的单纯形表重新计算分析bi的变化最优解或最优值可能已变第三十六页，共六十六页，2022年，8月28日

x1,x2≥0maxs.t.2x1+2x2≤12z=2x1+3x2

4x1≤165x2≤

15变化

x1,x2≥0maxs.t.2x1+2x2≤12+λ1z=2x1+3x2

4x1≤16+λ25x2≤

15+λ3分析λi分别在什么范围变化时，最优基不变？例1-2qi第三十七页，共六十六页，2022年，8月28日

x1,x2≥0maxs.t.2x1+2x2≤12z=2x1+3x2

4x1≤165x2≤

15变化

x1,x2≥0maxs.t.2x1+2x2≤12+λ1z=2x1+3x2

4x1≤16+λ25x2≤

15+λ3例1-2解：先分析λ1的变化范围:为使最优基不变，则需,即从而得到同理可得λ2与λ3的取值范围分析λi分别在什么范围变化时，最优基不变？第三十八页，共六十六页，2022年，8月28日

美佳公司计划生产I、II两种产品，每天生产条件如表，问(4)若设备A和B的能力不变，调试工序能力在什么范围内变化时，问题的最优基不变？(5)设备A和调试工序每天能力不变，而设备B能力增加到32，问最优生产计划如何变化？例2-2设备A(h)设备B(h)调试工序(h)利润(百元)ⅠⅡ每天可用能力资源产品0562112115245maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5x1,x2≥0得最优解为：X*=(7/2,3/2,15/2,0,0)T第三十九页，共六十六页，2022年，8月28日例2-2解：调试工序能力在什么范围变化，最优基不变？maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5x1,x2≥0maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5+△b3x1,x2≥0(4)由最终单纯形表，可得第四十页，共六十六页，2022年，8月28日例2-2解：maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5x1,x2≥0maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5+△b3x1,x2≥0(4)由最终单纯形表，可得由，计算得调试工序能力在什么范围变化，最优基不变？第四十一页，共六十六页，2022年，8月28日例2-2因此当调试工序能力在范围变化时，问题的最优基不变。调试工序能力在什么范围变化，最优基不变？为使最优基不变，则需,即从而得到5→5+△b3第四十二页，共六十六页，2022年，8月28日maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5x1,x2≥0例2-2解：(5)由最终单纯形表，可得maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24+8x1+x2≤5x1,x2≥0设备B可用能力增加到32，生产计划如何变化？第四十三页，共六十六页，2022年，8月28日maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5x1,x2≥0例2-2解：(5)由最终单纯形表，可得maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24+8x1+x2≤5x1,x2≥0设备B可用能力增加到32，生产计划如何变化？反映到最终单纯形表可得第四十四页，共六十六页，2022年，8月28日maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5x1,x2≥0例2-2解：(5)由最终单纯形表，可得maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24+8x1+x2≤5x1,x2≥0设备B可用能力增加到32，生产计划如何变化？反映到最终单纯形表可得第四十五页，共六十六页，2022年，8月28日例2-2解：(5)由最终单纯形表，可得maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24+8x1+x2≤5x1,x2≥0设备B可用能力增加到32，生产计划如何变化？表中原问题为非可行解，用对偶单纯形法继续计算得最优解为：X*=(5,0,15,2,0)Tzmax=10(百元)。第四十六页，共六十六页，2022年，8月28日B-1NB-1Y*T=CBB-1

XB

I

0基变量非基变量XB基变量基变量基可系数行解

CN－CBB-1NXNXsB-1bCBB-1b－CBB-1Z*=CBB-1b原问题对偶问题结论或继续计算的步骤可行解可行解非可行解非可行解可行解非可行解可行解非可行解问题的最优解或最优基不变用单纯形法继续迭代求最优解用对偶单纯形法继续迭代求最优解引进人工变量，编制新的单纯形表重新计算分析bi的变化第四十七页，共六十六页，2022年，8月28日4.分析增加一个约束条件的变化四、灵敏度分析的主要内容1.分析

cj

的变化2.分析

bi

的变化3.分析系数

aij的变化5.分析增加一个变量

xj的变化系数矩阵As.t.第四十八页，共六十六页，2022年，8月28日增加一个新变量xj的分析若企业在计划期内，有新的产品可以生产，则在知道新产品的单位利润，单件资源消耗量时，可以在最优表中补充一列，其中的前m行可以由基矩阵的逆矩阵得到，而检验数行也可以由与其它列相同的方法计算得到。若检验数非正，则原最优解仍为最优，原生产计划不变，不生产这种新产品；否则，当检验数为正时，则应以该变量进基，作单纯形迭代，从而找出新的最优解。第四十九页，共六十六页，2022年，8月28日增加一个新变量xj的分析项目基变量非基变量CB

XBB–1

b

XBXN

XsIB–1

N

B–1

检验数0(CN-

CBB–1

N

)-CBB–1

项目0Xs

b非基变量基变量XBXNXsB

N

I检验数CB

CN0XjPjCjXjB-1PjCj–CBB-1Pj第五十页，共六十六页，2022年，8月28日增加一个新变量xj的分析项目基变量非基变量CB

XBB–1

b

XBXN

XsIB–1

N

B–1

检验数0(CN-

CBB–1

N

)-CBB–1

XjB-1PjCj–CBB-1Pj此时如果检验数小于0，原最优解仍为最优，原生产计划不变，不生产这种新产品；否则，当检验数为正时，则应以该变量进基，作单纯形迭代，从而找出新的最优解。第五十一页，共六十六页，2022年，8月28日增加一个新变量xj的分析计算步骤：项目基变量非基变量CB

XBB–1

b

XBXN

XsIB–1

N

B–1

检验数0XjB-1PjCj–CBB-1Pj(CN-

CBB–1

N

)-CBB–1

第五十二页，共六十六页，2022年，8月28日例

美嘉公司例子maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5x1,x2≥0maxz=2x1+x2s.t.5x2≤15

6x1+2x2≤24x1+x2≤5x1,x2≥0设备A(h)设备B(h)调试工序(h)利润(百元)ⅠⅡ每天可用能力资源产品0562112115245如果该厂计划推出新产品3，生产一件所需要设备A,B以及调试工序的时间分别是3h,4h,2h，该产品的预期利润3元/件，分析该种产品是否值得投产？如投产，对该公司的最优生产计划有何改变？第五十三页，共六十六页，2022年，8月28日是否值得生产，看检验数，大于0，值得生产（影子价格特点）解：设该厂生产新产品3为x6件，C６=3,P6=(3,4,2)T检验数大于0，值得生产分析该种产品是否值得投产？第五十四页，共六十六页，2022年，8月28日解：设该厂生产新产品3为x6件，C６=3,P6=(3,4,2)T如投产，对该公司的最优生产计划有何改变？因为检验数大于0，值得生产。也说明要投产的话，最优计划会改变，如何变，要通过计算，将结果反映到最终单纯形表上。第五十五页，共六十六页，2022年，8月28日Cj210003CB

基bX1x2x3x4x5x60x315/22x17/21x23/20015/4-15/2-7100¼-1/20010-1/43/22Cj-Zj000-1/4-1/21Cj210003CB

基bX1x2x3x4x5x60x351/42x17/23x63/407/213/8-9/40100¼-1/2001/20-1/83/41Cj-Zj0-1/20-1/8-5/40第五十六页，共六十六页，2022年，8月28日Cj210003CB

基bX1x2x3x4x5x60x351/42x17/23x63/407/213/8-9/40100¼-1/2001/20-1/83/41Cj-Zj0-1/20-1/8-5/40新的最优生产计划为每天生产1产品：7/2件生产2产品：0件；生产3产品：3/4件。第五十七页，共六十六页，2022年，8月28日参数aij的变化导致系数阵A的元素发生变化。相当于增加1个新变量（系数阵A增加1列），如果xj在最终单纯形表中为基变量，则aij的变化会使相应的B,B-1发生变化，有可能出现原问题与对偶问题无可行解的情况。引进人工变量，使用单纯形法计算。如果该厂生产的产品2，生产一件所需要设备A,B以及调试工序的时间分别变为8h,4h,1h，该产品的利润变为3元/件，对该公司的最优生产计划有何改变？分析参数aij的变化第五十八页，共六十六页，2022年，8月28日解：将改变的产品看作是一件新的产品，生产量X2’将其反映到单纯形表分析参数aij的变化第五十九页，共六十六页，2022年，8月28日Cj213000CB基bX1x2X2’x3x4x50x315/22x17/21x23/20011/215/4-15/210½0¼-1/201½0-1/43/2Cj-Zj003/20-1/4-1/2Cj213000CB

基bX1

x2x2’x3x4x50x3-92x123x2’300014-2410001/2-20110-1/23Cj-Zj00001/2-5删除X2所在列第六十页，共六十六页，2022年，8月28日原问题与对偶问题均为非可行解，先使原问题转化为可行解第一行的约束：x3+4x4-24x5=-9,乘以（-1），加上人工变量-x3-4x4+24x5

+x6