第06章 单纯形法的灵敏度分析与对偶

1、管理运筹学第06章 单纯形法的灵敏度分析与对偶第六章 单纯形法的灵敏度分析与对偶1单纯形表的灵敏度分析单纯形表的灵敏度分析2线性规划的对偶问题线性规划的对偶问题3对偶规划的基本性质对偶规划的基本性质4对偶单纯形法对偶单纯形法第六章 单纯形法的灵敏度分析与对偶 1单纯形表的单纯形表的灵敏度分析：灵敏度分析：what- if参数的变化如何影响最优解参数的变化如何影响最优解2022-4-2731单纯形表的灵敏度分析T1单纯形表的灵敏度分析1单纯形表的灵敏度分析例：例： 目标函数：目标函数：Max z=50X1+100X2 约束条件：约束条件：X1+X2300 2X1+X2400 X2250 X1，X

2、20 最优单纯形表如下最优单纯形表如下迭代次数基变量CBX1 X2 S1 S2 S3b50 100 0 0 02X1501 0 1 0 -150 S200 0 -2 1 150 X21000 1 0 0 1250 ZJ50 100 50 0 5027500CJ -ZJ0 0 -50 0 -501单纯形表的灵敏度分析当当-50c150时，也就是时，也就是x1的目标函数的目标函数c1在在0c1100时最优时最优解不变。解不变。1单纯形表的灵敏度分析迭代次数基变量CBX1 X2 S1 S2 S3b50 100 0 0 02X1C11 0 1 0 -150 S200 0 -2 1 150 X21000

3、 1 0 0 1250 ZJC1 100 C1 0 -C1+100CJ -ZJ0 0 - C1 0 C1-100从从30，得到，得到-c10,即即c10，并且从，并且从50，得到，得到c1100。 那么如果那么如果c1取值超出这个范围，必然存在一个检验数大取值超出这个范围，必然存在一个检验数大于于0，我们可以通过迭代来得到新的最优解。，我们可以通过迭代来得到新的最优解。二、约束方程中常数项的灵敏度分析二、约束方程中常数项的灵敏度分析 约束式常数项发生变化，则最优解与最优值肯定要发生变化。 研究常数项的灵敏度分析主要是考虑常数项在什么范围以内对偶价格不变(或者当前的基仍然是最优基)。2022-4

4、-2791单纯形表的灵敏度分析二、约束方程中常数项的灵敏度分析二、约束方程中常数项的灵敏度分析 从上表我们可以发现各个松弛变量的值，正好等于相应变量的对偶价格。在最优从上表我们可以发现各个松弛变量的值，正好等于相应变量的对偶价格。在最优解中解中S2 =50是基变量，即为，原料是基变量，即为，原料A有有50千克没用完，再增加千克没用完，再增加A原料是不会增加利原料是不会增加利润的，润的， A的对偶价格为的对偶价格为0。对于任何为基变量的松弛变量所对应的约束条件的对偶。对于任何为基变量的松弛变量所对应的约束条件的对偶价格为价格为0。迭代次数迭代次数基变量基变量CBX1 X2 S1 S2 S3b50

5、 100 0 0 02X1501 0 1 0 -150 S200 0 -2 1 150 X21000 1 0 0 1250 ZJ50 100 50 0 5027500CJ -ZJ0 0 -50 0 -501单纯形表的灵敏度分析1单纯形表的灵敏度分析 约束条件约束条件求解求解max问题中对偶价格和影子价格的取值问题中对偶价格和影子价格的取值 等于这个约束条件对应的松弛变量的等于这个约束条件对应的松弛变量的Zj值值, ,即为即为 j的相反数的相反数 等于这个约束条件对应的剩余变量的等于这个约束条件对应的剩余变量的- -Zj值值, ,即为即为 j =等于这个约束条件对应的人工变量的等于这个约束条件对

6、应的人工变量的Zj值值, ,即为即为 j的相反数的相反数 1单纯形表的灵敏度分析 当当bj中的第中的第k项项bK 变成变成bK +bK时，也就是原来的初始单时，也就是原来的初始单纯形表中的纯形表中的b向量变成了向量变成了b向量向量bbbbk0.00b则有令1单纯形表的灵敏度分析 这样在最终单纯形表中基变量这样在最终单纯形表中基变量XB的解就变成了的解就变成了如要使如要使XB成为可行解，只要使上述等式的右边成为可行解，只要使上述等式的右边0，就可求出，就可求出bK的取值范围，也就是使得第的取值范围，也就是使得第K个约束条件的对偶价格不变个约束条件的对偶价格不变的的bk的变化范围。的变化范围。-1

7、-1-1BXB .(bb)BbBb 。mkk3kk2kk1kk1-21kdb.dbdbdbbB,.D则mkkkdddmkk2kk1kk21BBdb.dbdb.XXBmBBXXX有新的最优解为1单纯形表的灵敏度分析2022-4-27151单纯形表的灵敏度分析下面我们仍以第二章例下面我们仍以第二章例1在最终单纯形表上对在最终单纯形表上对bj 进行灵敏度分析。进行灵敏度分析。最终单纯形表如下所示：最终单纯形表如下所示：迭代次数迭代次数基变量基变量CBX1 X2 S1 S2 S3b50 100 0 0 02X1501 0 1 0 -150 S200 0 -2 1 150 X21000 1 0 0 12

8、50 ZJ50 100 50 0 5027500CJ -ZJ0 0 -50 0 -501单纯形表的灵敏度分析 我们对我们对b1进行灵敏度分析，因为在第一个约束方程中含有松弛变进行灵敏度分析，因为在第一个约束方程中含有松弛变量量S1,实际意义可以描述为：当设备台时数的对偶价格不变，都为每设备实际意义可以描述为：当设备台时数的对偶价格不变，都为每设备台时数在台时数在250与与325之间变化，则设备台时数的对偶价格不变，都为之间变化，则设备台时数的对偶价格不变，都为每台设备台时每台设备台时50元。元。1单纯形表的灵敏度分析1单纯形表的灵敏度分析例例 以第二章例以第二章例1为基础，设该厂除了生产为基础

9、，设该厂除了生产，种产品外，现种产品外，现在试制成一个新产品在试制成一个新产品，已知生产，已知生产产品产品,每件需要设备每件需要设备2台台时，并消耗时，并消耗A原料原料0.5公斤。公斤。B原料原料1.5公斤，获利公斤，获利150元，问元，问该厂应该生产该产品多少？该厂应该生产该产品多少？，1单纯形表的灵敏度分析接上页接上页迭代次数基变量CBX1 X2 S1 S2 S3 X3 b50 100 0 0 0 150X1501 0 1 0 -1 0.550 S200 0 -2 1 1 -250 X21000 1 0 0 1 1.5250 ZJ50 100 50 0 50 17527500CJ -ZJ0

10、 0 -50 0 -50 -251单纯形表的灵敏度分析例例 假设上例题中产品假设上例题中产品的工艺结构有了改进，这时生产的工艺结构有了改进，这时生产1件件产品产品需要使用需要使用1.5台设备台设备 ，消耗原料，消耗原料A为为2千克，原料千克，原料B为为1千克，每件千克，每件产品的利润为产品的利润为160元，问该厂的生产计划是否要修改。元，问该厂的生产计划是否要修改。 解：首先求出解：首先求出X3在最终表上的系数列在最终表上的系数列 61PB填入下表,35,125100.5(50,0,100),105 . 0125 . 1111010021PB66661ZCzj迭代次数基变量CBX1 X2 S1

11、 S2 S3 X3 b50 100 0 0 0 1502X1501 0 1 0 -1 0.55050/0.5 S200 0 -2 1 1 050 X21000 1 0 0 1 1250250/1 ZJ50 100 50 0 50 12527500CJ -ZJ0 0 -50 0 -50 351单纯形表的灵敏度分析接下来又可以有新的迭代接下来又可以有新的迭代S3进基，进基，6310,3,XX由于可知此解不是最优解 我们要进行第 次迭代 选为入基变量，为出基变量迭代迭代次数次数基变量基变量CBX1 X2 S1 S2 S3 X3 b50 100 0 0 0 1503X31602 0 2 0 -2 11

12、00- S200 0 -2 1 1 05050/1 X2100-20 1 -2 0 3 0150250/3 ZJ120 100 120 0 -20 16031000CJ -ZJ-70 0 -120 0 20 01单纯形表的灵敏度分析可知此规模的最优解可知此规模的最优解X1=0, X2=0, S1=0, S2=0, S3=50, X3=200,此时，最大目标函数为此时，最大目标函数为32000元。也就是说，该厂的新的生元。也就是说，该厂的新的生产计划为不生产产计划为不生产、产品，生产产品，生产产品产品200件件, 可获得最大可获得最大利润利润32000元。元。迭代迭代次数次数基变量基变量CBX1

13、 X2 S1 S2 S3 X3 b50 100 0 0 0 1504X31602 0 2 0 -2 1200- S300 0 -2 1 1 05050/1 X2100-2 1 4 -3 0 00250/3 ZJ120 100 80 20 0 16032000CJ -ZJ-70 0 -80 -20 0 01单纯形表的灵敏度分析四、增加一个约束条件的灵敏度分析四、增加一个约束条件的灵敏度分析在最终单纯形中增加一行，初始变换后再重新计算。在最终单纯形中增加一行，初始变换后再重新计算。 下面仍以第三章例下面仍以第三章例1为例来加以说明。为例来加以说明。 例：假如该工厂除了在设备台时，原材料例：假如该工

14、厂除了在设备台时，原材料A、B上对该厂上对该厂的生产有限制外，还有电力供应上的限制。最高供应电量为的生产有限制外，还有电力供应上的限制。最高供应电量为5000度，而生产一个度，而生产一个产品需要用电产品需要用电10度，而生产一个度，而生产一个产产品需要用电品需要用电30度。试分析此时该厂获得最大利润的生产计划？度。试分析此时该厂获得最大利润的生产计划？1单纯形表的灵敏度分析 1210305000 xx解：先将原问题的最优解解：先将原问题的最优解x1 =50，x2=250代入用电量的约束条件代入用电量的约束条件,得：得：1050+30250=500+75005000,所以原题的最优解不是本题的最

15、所以原题的最优解不是本题的最优解。在用电量的约束条件中加入松驰变量优解。在用电量的约束条件中加入松驰变量S4后得：后得：12410 x +30 x +s =5000把这个约束条件加入到原最终单纯形表上，其中把这个约束条件加入到原最终单纯形表上，其中S4为基变量，得表如下：为基变量，得表如下：BC1x2x1s2s3s4s1x2s2x4sjz迭代次数基变量b比值501000000501010-1050000-2110501000100102500103000015000501005005002750000-500-500jjjcz1单纯形表的灵敏度分析jjjcss 在上表

16、中的在上表中的X1，X2不是单位向量，故进行行的线性变换，得不是单位向量，故进行行的线性变换，得迭代迭代次数次数基变量基变量CBx1x2s1s2s3s4b比值比值501000000 x1501010-1050s2000-211050 x2100010010250s4000-100-201-3000zj501005005002750000-500-500把上表中的把上表中的S4行的约束可以写为：行的约束可以写为：上式两边乘以（上式两边乘以（-1-1），再加上人工变量），再加上人工变量a a1 1得：得：134110203000sssa用上式替换上表中的用上式替换上表中的S4行，得下表：行，得下表

17、：1单纯形表的灵敏度分析jjjcz迭代迭代次数次数基变量基变量x1x2s1s2s3s4a1b比值比值501000000-Mx1501010-10050s2000-21(1)0050 x21000100100250s4-M00-100-20113000zj5010050-10M050-20M0-M0010M-50020M-5000 x15010-11000100 s3000-2110050 x2100012-1000200 s4-M0050-200-112000 zj50100150-50M20M-500M-M 050M-15050-20M0-M0 x1501003/50-1/501/50140

18、 s300001/51-2/502/50130 x2100010-1/502/50-2/50120 s40001-2/50-1/501/5040 zj5010001003-3 00-100-3-M+3 jjjczjjjcz1单纯形表的灵敏度分析 1212311401200 xxsssa由上表可知，最优解为：由上表可知，最优解为： 即该工厂在添加了用电限量以后的最优生产计划即该工厂在添加了用电限量以后的最优生产计划为为产品生产产品生产140件，件，产品生产产品生产120件。件。 2 线性规划的对偶问题 每一个线性规划问题，都存在每一个与它密切相关的线性每一个线性规划问题，都存在每一个与它密切相关

19、的线性规划的问题，我们称其为原问题，另一个为对偶问题。规划的问题，我们称其为原问题，另一个为对偶问题。 例题例题1 某工厂在计划期内安排某工厂在计划期内安排、两种产品，生产单位两种产品，生产单位产品所需设备产品所需设备A、B、C台时如表所示。台时如表所示。 该工厂每生产一该工厂每生产一单位产品单位产品 I可获利可获利50元，每生产一单位产品元，每生产一单位产品可获利可获利100元，元，问工厂应分别生产多少问工厂应分别生产多少 产品产品I和产品和产品 ，才能使工厂获利，才能使工厂获利最多？最多？III资源限量资源限量设备设备A11300台时台时设备设备B21400台时台时设备设备C01250台时

20、台时解：设解：设x1为产品为产品 I 的计划产量，的计划产量，x2为产品为产品II的计划产量，则有的计划产量，则有121212212max50100300s.t.24002500zxxxxxxxxx，2 线性规划的对偶问题123min300400250yyy2 线性规划的对偶问题现在我们从另一个角度来考虑这个问题。假如有另外一现在我们从另一个角度来考虑这个问题。假如有另外一个工厂要求租用该厂的设备个工厂要求租用该厂的设备A、B、C，那么该厂的厂长应，那么该厂的厂长应该如何来确定合理的租金呢？该如何来确定合理的租金呢？买方希望租赁价格越低越好。买方希望租赁价格越低越好。 但卖方则不能让出租的收益

21、少于自己生产的收益。但卖方则不能让出租的收益少于自己生产的收益。12312123123min300400250250s.t.100,0fyyyyyyyyy yy2 线性规划的对偶问题这样我们得到了该问题的数学模型：这样我们得到了该问题的数学模型： 这样从两个不同的角度来考虑同一个工厂的最大利润这样从两个不同的角度来考虑同一个工厂的最大利润（最小租金）的问题，所建立起来的两个线性模型就是（最小租金）的问题，所建立起来的两个线性模型就是一对对偶问题，其中一个一对对偶问题，其中一个叫做原问题叫做原问题，而另外一个叫，而另外一个叫对对偶问题偶问题。121212212max50100 300s.t.24

22、00 2500zxxxxxxxxx，1112112.=.nmmmnaaaaaaAmnnnmTaaaaaa2112111A2 线性规划的对偶问题4 对偶问题的约束条件的系数矩阵对偶问题的约束条件的系数矩阵A是原问题约束矩阵是原问题约束矩阵的转置。设的转置。设 则则2 线性规划的对偶问题0,maxxbAxcxz如果我们用矩阵形式来表如果我们用矩阵形式来表示，则有原问题：示，则有原问题： 其中其中A是矩阵是矩阵m*n，该问题，该问题有有m个约束条件个约束条件n个变量，个变量，对偶问题：对偶问题：12( ,.,).nc ccc12( ,.,)Tmb bbb12,Tnx xxx0minycyAybTTT

23、f2 线性规划的对偶问题现在我们用单纯形法求对偶问题的解。加上剩余变量现在我们用单纯形法求对偶问题的解。加上剩余变量s1,s2 和人工变量和人工变量a1，把此问题化成标准型如下：，把此问题化成标准型如下：把上述数据填入单纯形表计算。把上述数据填入单纯形表计算。123112111232123121max()300400500250. .100,0fyyyMayysastyyysy yy s s a 2 线性规划的对偶问题迭代变量基变量 b-300-400-25000-M 1-M1 0 -1 0 15050/2-250 1 1 1 0 -1 0 100100/1-M-250-2M-250-250M

24、250-M-50M-25000M-2502M-1500-M-25002-4001/210-1/201/225-2501/2011/2-1-1/275-325-400-25075250-75-287502500-75-250-M+753-300120-10150-2500-111-1-150-300-350-25050250-50-275000-500-50-250-M+50bc1y2y3y2s1s1a1a3yjzjjzc 2y3y2/1752/125jzjjzc 1y3yjzjjzc 2 线性规划的对偶问题123123123123123max346236440,. .64100,53200,0

25、zxxxxxxstxxxxxxx x x 先写出原问题形式：min则约束式=，max则约束=，约束约束式常数项小于0。 再写出对偶问题：把原规划的对偶问题化为把原规划的对偶问题化为123123123123123min4401002002653,. .3434,66,0, is arbitraryfyyyyyystyyyyyyy yy2 线性规划的对偶问题3对偶规划的基本性质对偶规划的基本性质对偶规划的基本性质1对称性。即对偶问题的对偶是原问题。对称性。即对偶问题的对偶是原问题。2弱对偶性。即对于原问题（弱对偶性。即对于原问题（）和对偶问题（）和对偶问题（）的可）的可行解行解 都有都有C bT

26、。由弱对偶性，可得出以下推论：由弱对偶性，可得出以下推论：（1）原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；）原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。（2）如原问题有可行解且目标函数值无界（或具有无界解），则其对）如原问题有可行解且目标函数值无界（或具有无界解），则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解（注意：本点性质的逆不成立，当对偶问题无

27、可行解时，其题无可行解（注意：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然）。原问题或具有无界解或无可行解，反之亦然）。（3）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。函数值无界。YX,XY3对偶规划的基本性质XYXYXY最终单纯形表的矩阵形式3对偶规划的基本性质2022-4-27424对偶单纯形法 对偶单纯形法也是解决线性规划问题的一种方法。对偶单纯形法也是解决线性规划问题的一种方法。对偶单纯形法是在保持原有问题的所有检验数都小于对偶单纯形法是在保持原有问题的所有检验数都小于0的情况下，通过迭代使得所有的约束都大于等于的情况下，通过迭代使得所有的约束都大于等于0，最，最后求得最优解。后求得最优解。 简化计算是对偶单纯形法的优点，但是它在使用上简化计算是对偶单纯形法的优点，但是它在使用上有很大的局限，这主要是大多数线性规划问题很难找到有很大的局限，这主要是大多数线性规划问题很难找到初始解使得其所有检