管理运筹学单纯形法的灵敏度分析与对偶精选文档.ppt

《管理运筹学单纯形法的灵敏度分析与对偶精选文档.ppt》由会员分享，可在线阅读，更多相关《管理运筹学单纯形法的灵敏度分析与对偶精选文档.ppt（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、管理运筹学单纯形法的灵敏度分析与对偶1本讲稿第一页，共五十页11单纯形表的灵敏度分析单纯形表的灵敏度分析一、目标函数中变量一、目标函数中变量Ck系数灵敏度分析系数灵敏度分析1.在最终的单纯形表里，在最终的单纯形表里，X k是非基变量是非基变量 由于约束方程系数增广矩阵在迭代中只是其本身的行的初等变换与由于约束方程系数增广矩阵在迭代中只是其本身的行的初等变换与Ck没有任何关系，没有任何关系，所以当所以当Ck变成变成Ck+Ck时，在最终单纯形表中其系数的增广矩阵不变，又因为时，在最终单纯形表中其系数的增广矩阵不变，又因为Xk是非是非基变量，所以基变量的目标函数的系数不变，即基变量，所以基变量的目标

2、函数的系数不变，即CB不变，可知不变，可知Zk也不变，只是也不变，只是Ck变变成了成了Ck+Ck。这时。这时 K=Ck-Zk就变成了就变成了Ck+Ck-Zk=K+Ck。要使原来的最优解。要使原来的最优解仍为最优解，只要仍为最优解，只要 K+Ck0即可，也就是即可，也就是Ck的增量的增量 Ck-K。2.在最终的单纯形表中，在最终的单纯形表中，X k是基变量是基变量 当当Ck变成变成Ck+Ck时，最终单纯形表中约束方程的增广矩阵不变，但是基变量的目时，最终单纯形表中约束方程的增广矩阵不变，但是基变量的目标函数的系数标函数的系数CB变了，则变了，则ZJ(J=1,2,.,N)一般也变了，不妨设一般也变

3、了，不妨设CB=(CB1,CB2。,Ck,，CBm),当当CB变成变成=(CB1,CB2。,Ck+Ck,CBm),则：则：ZJ=(CB1,CB2。,Ck,，CBm)(a1j,a2j,aKj ,amj)ZJ=(CB1,CB2。,Ck+Ck,，CBm)(a1j,a2j,aKj ,amj)=ZJ+Ck aKj 2本讲稿第二页，共五十页11单纯形表的灵敏度分析单纯形表的灵敏度分析根据上式可知根据上式可知 检验数检验数 J(J=1,2,.,M)变成了变成了 J,有有 J=CJ-ZJ=J+CK aKj。要使最优解不变，只要当。要使最优解不变，只要当J K时，时，J 5000,250=500+7500500

4、0,所以原题的最优解不是本题的最优解。所以原题的最优解不是本题的最优解。在用电量的约束条件中加入松驰变量在用电量的约束条件中加入松驰变量S S4 4后得：后得：把这个约束条件加入到原最终单纯形表上，其中把这个约束条件加入到原最终单纯形表上，其中S S4 4为基变量，得表如下为基变量，得表如下：迭代次数基变量b比值501000000501010-1050000-2110501000100102500103000015000501005005002750000-500-5008本讲稿第八页，共五十页11单纯形表的灵敏度分析单纯形表的灵敏度分析 在上表中的在上表中的X X1 1，X X2 2不是单位

5、向量，故进行行的线性变换，得不是单位向量，故进行行的线性变换，得迭代次数基变量CBx1x2s1s2s3s4b比值501000000 x1501010-1050s2000-211050 x2100010010250s4000-100-201-3000zj501005005002750000-500-500把上表中的把上表中的S S4 4行的约束可以写为：行的约束可以写为：上式两边乘以（上式两边乘以（-1-1），再加上人工变量），再加上人工变量a a1 1得：得：用上式替换上表中的用上式替换上表中的S S4 4行，得下表：行，得下表：9本讲稿第九页，共五十页11单纯形表的灵敏度分析单纯形表的灵敏度

6、分析迭代次数基变量x1x2s1s2s3s4a1b比值501000000-Mx1501010-10050s2000-21(1)0050 x21000100100250a4-M00-100-20113000zj5010050-10M050-20M0-M0010M-50020M-5000 x15010-11000100s3000-2110050 x2100012-1000200a4-M0050-200-112000zj50100150-50M20M-500M-M050M-15050-20M0-M0 x1501003/50-1/501/50140s300001/51-2/502/50130 x2100

7、010-1/502/50-2/50120s40001-2/50-1/501/5040zj5010001003-300-100-3-M+310本讲稿第十页，共五十页11单纯形表的灵敏度分析单纯形表的灵敏度分析 由上表可知，最优解为：由上表可知，最优解为：即该工厂在添加了用电限量以后的最优生产计划为即该工厂在添加了用电限量以后的最优生产计划为产产品生产品生产140140件，件，产品生产产品生产120120件。件。11本讲稿第十一页，共五十页11单纯形表的灵敏度分析单纯形表的灵敏度分析三、约束方程中常数项的灵敏度分析三、约束方程中常数项的灵敏度分析 从上表我们可以发现各个松弛变量的值，正好等于相应变

8、量的对偶价格。在最从上表我们可以发现各个松弛变量的值，正好等于相应变量的对偶价格。在最优解中优解中S2=50是基变量，即为，原料是基变量，即为，原料A有有50千克没用完，再增加千克没用完，再增加A原料是不会增原料是不会增加利润的，加利润的，A的对偶价格为的对偶价格为0。对于任何为基变量的松弛变量所对应的约束条件的。对于任何为基变量的松弛变量所对应的约束条件的对偶价格为对偶价格为0。迭代次数基变量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 502750

9、0CJ-ZJ0 0 -50 0 -5012本讲稿第十二页，共五十页11单纯形表的灵敏度分析单纯形表的灵敏度分析 可以看出，上题中对于设备台时数约束来说，当其松弛变量在目标函数可以看出，上题中对于设备台时数约束来说，当其松弛变量在目标函数中从中从0变到变到Z3=50时，也就是只要当前余下一台时数设备从不能获利变成获利时，也就是只要当前余下一台时数设备从不能获利变成获利50元时，譬如有人愿意出元时，譬如有人愿意出50元买一个设备时，我们就不必为生产元买一个设备时，我们就不必为生产、产产品品而使用完所有的而使用完所有的设备设备台台时时了，了，这说这说明了明了设备设备台台时时数的数的对对偶价格就是偶价

10、格就是Z3=50元。元。对对于含有大于等于号的于含有大于等于号的约约束条件，添加剩余束条件，添加剩余变变量化量化为标为标准型。准型。这时这时这这个个约约束条件的束条件的对对偶价格就和偶价格就和这这个剩余个剩余变变量的量的 有关了。有关了。这这将使得最将使得最优优目目标值标值特特别别“恶恶化化”而不是改而不是改进进，故，故这时约这时约束条件的束条件的对对偶价格偶价格应应取取 值值的相反的相反数数-。对对于含有等于号的于含有等于号的约约束条件，其束条件，其约约束条件的束条件的对对偶价格就和偶价格就和该约该约束方束方程的人工程的人工变变量有关了。其量有关了。其约约束条件的束条件的对对偶价格就等于此偶

11、价格就等于此约约束方程的人工束方程的人工变变量的量的 值值。13本讲稿第十三页，共五十页下表下表给给出了一个由最出了一个由最终单纯终单纯形表形表对对于不同于不同约约束束类类型的型的对对偶价格的取偶价格的取值值。从从对对偶价格的定偶价格的定义义,可以知道当可以知道当对对偶价格偶价格为为正正时时它将改它将改进进目目标标函数的函数的值值，当，当对对偶价格偶价格为负时为负时它将使得目它将使得目标标函数朝着与最函数朝着与最优优化相反的方向前化相反的方向前进进。下面我下面我们们研究当右端研究当右端项项bj发发生生变变化化时时，在什么范，在什么范围围内其内其对对偶价格不偶价格不变变。由于由于bj的的变变化并

12、不影响系数矩化并不影响系数矩阵阵的迭代，故其最的迭代，故其最终单纯终单纯形表中的系数矩形表中的系数矩阵阵没有没有变变化。由化。由此可此可见见当当bj变变化化时时，要使原来的基不，要使原来的基不变变得到的基本可行解仍然是可行解，也就是所得到的基本可行解仍然是可行解，也就是所求的基求的基变变量的量的值值一定要大于一定要大于0。所。所谓谓使其使其对对偶价格不偶价格不变变的的bj的的变变化范化范围围，也就是使，也就是使其最其最优优解的所有基解的所有基变变量不量不变变，且所得的最，且所得的最优优解仍然是可行的解仍然是可行的bj的的变变化范化范围围。约束条件影子价格的取值 等于这个约束条件对应的松弛变量的

13、 值,即为 的相反数 等于这个约束条件对应的剩余变量的 值,即为 的相反数 =等于这个约束条件对应的人工变量的 值,即为 的相反数 11单纯形表的灵敏度分析单纯形表的灵敏度分析14本讲稿第十四页，共五十页11单纯形表的灵敏度分析单纯形表的灵敏度分析 当bj中的第k项bK 变成 时，也就是原来的初始单纯形表中的b向量变成了b向量15本讲稿第十五页，共五十页11单纯形表的灵敏度分析单纯形表的灵敏度分析 这样在最终单纯形表中基变量这样在最终单纯形表中基变量XB的解就变成了的解就变成了 如要使如要使XB成为可行解，只要使上述等式的右边成为可行解，只要使上述等式的右边0，就可求出，就可求出 的取值范围，

14、也就是使得第的取值范围，也就是使得第K个约束条件的对偶价格不变的个约束条件的对偶价格不变的bk的变化范围。的变化范围。，16本讲稿第十六页，共五十页11单纯形表的灵敏度分析单纯形表的灵敏度分析下面我们仍以第二章例1在最终单纯形表上对bj 进行灵敏度分析。最终单纯形表如下所示：迭代次数基变量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 -5017本讲稿第十七页，共五十页11单纯形表的灵敏度分析单纯形表的灵敏度分

15、析 我们对b1进行灵敏度分析，因为在第一个约束方程中含有松弛变量S1,实际意义可以描述为：当设备台时数的对偶价格不变，都为每设备台时数在250与325之间变化，则设备台时数的对偶价格不变，都为每台设备台时50元。18本讲稿第十八页，共五十页11单纯形表的灵敏度分析单纯形表的灵敏度分析三、约束方程系数矩阵A灵敏度分析下面分两种情况讨论 1.在初始单纯形表上的变量Xk的系数列Pk改变为Pk经过迭代后，在最终单纯形表上Xk是非基变量。由于单纯形表的迭代是约束方程的增广矩阵的行变换，Pk变成Pk仅仅影响最终单纯形表上第k列数据，包括Xk的系数列、Zk以及 k，这时最终单纯形表上的Xk的系数列就变成了B

16、-1Pj,而Zk就变成CBB-1Pk，新的检验数 k=Ck-CBB-1Pk。若 k0，则原最优解仍然为最优解。若 k 0，则继续进行迭代以求出最优。例例 以第二章例1为基础，设该厂除了生产，种产品外，现在试制成一个新产品，已知生产产品,每件需要设备2台时，并消耗A原料0.5公斤。B原料1.5公斤，获利150元，问该厂应该生产该产品多少？解：这是一个增加新变量的问题。我们可以把它认为是一个改变变量X3在初始表上的系数列的问题，19本讲稿第十九页，共五十页11单纯形表的灵敏度分析单纯形表的灵敏度分析接上页迭代次数基变量CBX1 X2 S1 S2 S3 X3 b50 100 0 0 0 150X15

17、01 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 0 -50 0 -50 -2520本讲稿第二十页，共五十页11单纯形表的灵敏度分析单纯形表的灵敏度分析例 假设上例题中产品的工艺结构有了改进，这时生产1件产品需要使用1.5台设备，消耗原料A为2千克，原料B为1千克，每件产品的利润为160元，问该厂的生产计划是否要修改。解：首先求出X3在最终表上的系数列 迭代次数基变量CBX1 X2 S1 S2 S3 X3 b50 100 0 0 0 1502X1501 0 1 0

18、 -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 3521本讲稿第二十一页，共五十页11单纯形表的灵敏度分析单纯形表的灵敏度分析接下来又可以有新的迭代S3进基，迭代次数基变量CBX1 X2 S1 S2 S3 X3 b50 100 0 0 0 1503X31602 0 2 0 -2 1100-S200 0 -2 1 1 05050/1 X2100-20 1 -2 0 3 0150250/3 ZJ120 100 120 0 -20 160310

19、00CJ-ZJ-70 0 -120 0 20 022本讲稿第二十二页，共五十页11单纯形表的灵敏度分析单纯形表的灵敏度分析接上页接上页 可知此规模的最优解可知此规模的最优解X1=0,X2=0,S1=0,S2=0,S3=50,X3=200,此时，最大目标此时，最大目标函数为函数为32000元。也就是说，该厂的新的生产计划为不生产元。也就是说，该厂的新的生产计划为不生产、产产品，生品，生产产产产品品200件件,可可获获得最大利得最大利润润32000元。元。迭代次数基变量CBX1 X2 S1 S2 S3 X3 b50 100 0 0 0 1504X31602 0 2 0 -2 1200-S300 0

20、 -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 023本讲稿第二十三页，共五十页11单纯形表的灵敏度分析单纯形表的灵敏度分析 2.在初始表上的变量在初始表上的变量XK的系数的系数PK改变为改变为PK，经，经过迭代后，在最终表上过迭代后，在最终表上XK是基变量，在这种情况下是基变量，在这种情况下原最优解的可行性和最优解都可能被破坏，问题十分原最优解的可行性和最优解都可能被破坏，问题十分复杂，一般不去修改原表而是直接计算。复杂，一般不去修改原表而是直接计算。24本讲稿第二

21、十四页，共五十页 每一个线性规划问题，都存在每一个与它密切相关的线性规划的问题，我们称其为原问题，另一个为对偶问题。每一个线性规划问题，都存在每一个与它密切相关的线性规划的问题，我们称其为原问题，另一个为对偶问题。例题例题1 1 某工厂在计划期内安排某工厂在计划期内安排、两种产品，生产单位产品所需设备两种产品，生产单位产品所需设备A A、B B、C C台时如表所示台时如表所示 该工厂每生产一单位产品该工厂每生产一单位产品 可获利可获利5050元，每生产一单位产品元，每生产一单位产品可获利可获利100100元，问工厂应分别生产多少元，问工厂应分别生产多少 产品和产品和产品，才能使工厂获利最多？产

22、品，才能使工厂获利最多？解：设解：设 为产品为产品 的计划产量，的计划产量，为产品为产品的计划产量，则有的计划产量，则有目标函数：目标函数：Max z=50+100 Max z=50+100约束条件：约束条件：，2 2 线性规划的对偶问题线性规划的对偶问题25本讲稿第二十五页，共五十页 现在我们从另一个角度来考虑这个问题。假如有另外一个工厂要求租用该厂的设备现在我们从另一个角度来考虑这个问题。假如有另外一个工厂要求租用该厂的设备A、B、C，那么该厂的厂长应该如何来确定合理的租金呢？，那么该厂的厂长应该如何来确定合理的租金呢？设设 分别为设备分别为设备A、B、C的每台时的租金。为了叙述方便，这里

23、把租金定义为扣除成本后的利润。作为出租者来说，把生产单位的每台时的租金。为了叙述方便，这里把租金定义为扣除成本后的利润。作为出租者来说，把生产单位 产品所产品所需各设备的台时各总租金不应低于原利润需各设备的台时各总租金不应低于原利润50元，即元，即 ，否则就不出租还是用于生产，否则就不出租还是用于生产 产品以获利产品以获利50元；同样把元；同样把 生产一单位生产一单位 产品所需各设备的台时的总租金也不应当低于原利润产品所需各设备的台时的总租金也不应当低于原利润100元，元，即即，否则这些设备台时就不出租，还是用于生产，否则这些设备台时就不出租，还是用于生产 产品以获利产品以获利100元。但对于

24、租用者来说，他要求在满足上述要求的前提下，也就是在出租者愿意出租的元。但对于租用者来说，他要求在满足上述要求的前提下，也就是在出租者愿意出租的前提下尽量要求全部设备台时的总租金越低越好，即前提下尽量要求全部设备台时的总租金越低越好，即min ，这样我们得到了该问题的数学模型：，这样我们得到了该问题的数学模型：目标函数：目标函数：约束条件：约束条件：这样从两个不同的角度来考虑同一个工厂的最大利润（最小租金）的问题，所建立起来的两个线性模型就是一对对偶问题，其中一个叫做原问题，而另外一个叫对偶问题。这样从两个不同的角度来考虑同一个工厂的最大利润（最小租金）的问题，所建立起来的两个线性模型就是一对对

25、偶问题，其中一个叫做原问题，而另外一个叫对偶问题。2 2 线性规划的对偶问题线性规划的对偶问题26本讲稿第二十六页，共五十页 如果我们把求目标函数最大值的线性规划问题看成原问题，则求目标函数最小值的线性规划问题看成对偶问题。下面来研究这两个问题在数学模如果我们把求目标函数最大值的线性规划问题看成原问题，则求目标函数最小值的线性规划问题看成对偶问题。下面来研究这两个问题在数学模型上的关系。型上的关系。1 求目标函数最大值的线性规划问题中有求目标函数最大值的线性规划问题中有n 个变量个变量 m个约束条件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，有个约束条件，它

26、的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，有m个变量个变量n个约束条件，个约束条件，其约束条件都为大于等于不等式。其约束条件都为大于等于不等式。2 原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项，并且原问题的目标函数中的第原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项，并且原问题的目标函数中的第 i个变量的系数就等于对偶问题中的第个变量的系数就等于对偶问题中的第i个约束条件的个约束条件的右边常数项。右边常数项。3 原问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系数。并且原问题的第原问题的约束条件的右边常数项为对偶问题

27、的目标函数中的变量的系数。并且原问题的第i个约束条件的右边常数项就等于零对偶问题的目标函个约束条件的右边常数项就等于零对偶问题的目标函数中的第数中的第i个变量的系数。个变量的系数。4 对偶问题的约束条件的系数矩阵对偶问题的约束条件的系数矩阵A是原问题约束矩阵的转置。是原问题约束矩阵的转置。设设 A=则则 2 2 线性规划的对偶问题线性规划的对偶问题27本讲稿第二十七页，共五十页如果我们用矩阵形式来表示，则有原问题：如果我们用矩阵形式来表示，则有原问题：其中其中A是是 矩阵矩阵m*n，该问题有，该问题有m个约束条件个约束条件n个变量，个变量，x=,b=,c=对偶问题：对偶问题：其中其中 是是A的

28、转置，的转置，是是b的转置的转置,是是c的转置的转置,y=现在我们用单纯形法求对偶问题的解。现在我们用单纯形法求对偶问题的解。2 2 线性规划的对偶问题线性规划的对偶问题28本讲稿第二十八页，共五十页 加上剩余变量加上剩余变量 和人工变量和人工变量 ，把此问题化成标准型如下：，把此问题化成标准型如下：把上述数据填入单纯形表计算。把上述数据填入单纯形表计算。2 2 线性规划的对偶问题线性规划的对偶问题29本讲稿第二十九页，共五十页迭代变量基变量 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

29、-250M250-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+502 2 线性规划的对偶问题线性规划的对偶问题30本讲稿第三十页，共五十页 由上表，最优解：由上表，最优解：=50，-f 的最大值为的最大值为-27500，即目标函数，即目标函数f的最大值为的最大值为f=27500元

30、。元。从上面可知租金：从上面可知租金：A设备为设备为50元，元，B设备为设备为0元，元，C设备为设备为50元。这样把工元。这样把工厂的所有设备出租可共得租金厂的所有设备出租可共得租金27500元。对出租者来说这租金是出租者愿意出元。对出租者来说这租金是出租者愿意出租设备的最小费用，因为这是目租设备的最小费用，因为这是目 标函数的最小值。标函数的最小值。通过比较，我们发现：通过比较，我们发现：对偶问题的最优解即最佳租金恰好等于原问题各种对偶问题的最优解即最佳租金恰好等于原问题各种设备的对偶价格，这在道理上也能讲得通。设备的对偶价格，这在道理上也能讲得通。对于两个有对偶关系的线性规划对于两个有对偶

31、关系的线性规划的问题，我们只要求得了其中一个最优解，就可以从这个问题的对偶价格而的问题，我们只要求得了其中一个最优解，就可以从这个问题的对偶价格而求得其对偶问题的最优解，知道其中一个最优值也就找到了其对偶问题的最求得其对偶问题的最优解，知道其中一个最优值也就找到了其对偶问题的最优值，因为这两个最优值相等。优值，因为这两个最优值相等。2 2 线性规划的对偶问题线性规划的对偶问题31本讲稿第三十一页，共五十页 下面来阐述如何写出一个线性规划问题的对偶问题。为了便于阐述，我们不妨以下面的线性规划为下面来阐述如何写出一个线性规划问题的对偶问题。为了便于阐述，我们不妨以下面的线性规划为例，写出它的对偶问

32、题。例，写出它的对偶问题。S.T.2 2 线性规划的对偶问题线性规划的对偶问题32本讲稿第三十二页，共五十页 这是一个求最大值的线性规划问题，为了写出它的对偶问题，我们不妨把它的约束条件都变换成取小于号的不等式。显然第一个这是一个求最大值的线性规划问题，为了写出它的对偶问题，我们不妨把它的约束条件都变换成取小于号的不等式。显然第一个约束条件已符合要求，不要做任何变动，而第二个约束条件，我们只要两边都乘以（约束条件已符合要求，不要做任何变动，而第二个约束条件，我们只要两边都乘以（-1），使不等号方向改变即可，得），使不等号方向改变即可，得 这样第二个约束条件也就符合要求。对于第三个约束条件，我们

33、可以用小于等于和大于等于两个约束条件来替代它。即这样第二个约束条件也就符合要求。对于第三个约束条件，我们可以用小于等于和大于等于两个约束条件来替代它。即有有 显然，这两个约束条件与原来第三个约束条件是等价的，我们再把其中的显然，这两个约束条件与原来第三个约束条件是等价的，我们再把其中的两边都乘以（两边都乘以（-1），得），得 2 2 线性规划的对偶问题线性规划的对偶问题33本讲稿第三十三页，共五十页 通过上面的一些变换，我们得到了一个和原线性规划等价的线性规划问题：通过上面的一些变换，我们得到了一个和原线性规划等价的线性规划问题：s.t.2 2 线性规划的对偶问题线性规划的对偶问题34本讲稿第

34、三十四页，共五十页 这个求最大值的线性规划问题的约束条件都取小于等于号，我们马这个求最大值的线性规划问题的约束条件都取小于等于号，我们马上可以写出其对偶问题：上可以写出其对偶问题：s.t.2 2 线性规划的对偶问题线性规划的对偶问题35本讲稿第三十五页，共五十页 这里这里 和和 一样都是不同的决策变量，为了表示这两个一样都是不同的决策变量，为了表示这两个决策变量都来源于原问题的第三个约束条件，记为决策变量都来源于原问题的第三个约束条件，记为 。因为在该对偶问题中因为在该对偶问题中 和和 的系数只相差一个符号，我们可以把的系数只相差一个符号，我们可以把上面的对偶问题化为：上面的对偶问题化为：s.

35、t.2 2 线性规划的对偶问题线性规划的对偶问题36本讲稿第三十六页，共五十页 进一步，我们可以令进一步，我们可以令 ，这时当，这时当 时，时，当，当 时，时，。这也就是说，尽管。这也就是说，尽管 但但 的取值可以为正，可以为的取值可以为正，可以为0，可以为负，即可以为负，即 没有非负限制。没有非负限制。这样我们把原规划的对偶问题化为这样我们把原规划的对偶问题化为 s.t.没有限制。没有限制。对照原线性规划问题，我们可以知道：对照原线性规划问题，我们可以知道：当原线性规划问题的第当原线性规划问题的第i个约束条件取等号时，则其对偶问题的个约束条件取等号时，则其对偶问题的 i个决策变量没有非个决策

36、变量没有非负限制。负限制。如果当原线性规划问题中的第如果当原线性规划问题中的第 i个决策变量个决策变量 没有非负限制时，我们也可以用没有非负限制时，我们也可以用 进行替换，这里进行替换，这里 ，用类似的方法知道其对偶问题中第，用类似的方法知道其对偶问题中第 i个个约束条件取等号。约束条件取等号。2 2 线性规划的对偶问题线性规划的对偶问题37本讲稿第三十七页，共五十页 另外，用大于等于另外，用大于等于0的两个决策变量之差来代替无非负限制的决策变的两个决策变量之差来代替无非负限制的决策变量也是求解含有无非负限制的决策变量的线性规划问题的一种方法。量也是求解含有无非负限制的决策变量的线性规划问题的

37、一种方法。原线性规划问题为：原线性规划问题为：s.t.无非负限制。无非负限制。2 2 线性规划的对偶问题线性规划的对偶问题38本讲稿第三十八页，共五十页39本讲稿第三十九页，共五十页33对偶规划的基本性质对偶规划的基本性质对偶规划的基本性质对偶规划的基本性质1对称性。即对偶问题的对偶是原问题。对称性。即对偶问题的对偶是原问题。2弱对偶性。即对于原问题（弱对偶性。即对于原问题（）和对偶问题（）和对偶问题（）的可行解）的可行解 都都有有C bT 。由弱对偶性，可得出以下推论：由弱对偶性，可得出以下推论：（1）原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之）原问题任一可行解的目标函数

38、值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。（2）如原问题有可行解且目标函数值无界（或具有无界解），则其对偶问题无可行）如原问题有可行解且目标函数值无界（或具有无界解），则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解（注意：本点解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解（注意：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然）。之亦然

39、）。（3）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。40本讲稿第四十页，共五十页3 341本讲稿第四十一页，共五十页33对偶规划的基本性质对偶规划的基本性质3最优性。如果最优性。如果 是原问题是原问题()的可行解，的可行解，是对偶是对偶问题问题()的可行解，并且的可行解，并且 C =bT ，则则 和和 分分别为原问题别为原问题()和对偶问题和对偶问题()的最优解。的最优解。4强

40、对偶性。即若原问题强对偶性。即若原问题()及其对偶问题及其对偶问题()都都有可行解，则两者都有最优解；且它们的最优解的有可行解，则两者都有最优解；且它们的最优解的目标函数都相等。目标函数都相等。42本讲稿第四十二页，共五十页5互补松弛性。在线性规划问题的最优解中，如果互补松弛性。在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，如果约束条件取严格束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为零也即不等式，则其对应的对偶变量一定为零也即 若若yi*0,则有则有 若若 ，则有，则有y

41、i*=043本讲稿第四十三页，共五十页44本讲稿第四十四页，共五十页45本讲稿第四十五页，共五十页44对偶单纯形法对偶单纯形法 对偶单纯形法也是解决线性规划问题的一种方法。对偶单纯形法是在保持原对偶单纯形法也是解决线性规划问题的一种方法。对偶单纯形法是在保持原有问题的所有检验数都小于有问题的所有检验数都小于0的情况下，通过迭代使得所有的约束都大于等于的情况下，通过迭代使得所有的约束都大于等于0，最后求得最优解。最后求得最优解。简化计算是对偶单纯形法的优点，但是它在使用上有很大的局限，这主要是简化计算是对偶单纯形法的优点，但是它在使用上有很大的局限，这主要是大多数线性规划问题很难找到初始解使得其

42、所有检验数都小于大多数线性规划问题很难找到初始解使得其所有检验数都小于0。但是在灵敏度。但是在灵敏度分析中，有时需要对偶单纯形法，这样可以简化处理。下面以第二节例一为例。分析中，有时需要对偶单纯形法，这样可以简化处理。下面以第二节例一为例。上节分析中已上节分析中已知当知当250b1325时第一个约束条件的对偶价格不变，现在时第一个约束条件的对偶价格不变，现在b1=300变成变成b1=350，请问这时第一个约束方程的对偶价格应为多少呢？，请问这时第一个约束方程的对偶价格应为多少呢？解：求出在第二次迭代表上的常数列解：求出在第二次迭代表上的常数列 46本讲稿第四十六页，共五十页44对偶单纯形法对偶

43、单纯形法迭代次数基变量CBX1 X2 S1 S2 S3b50 100 0 0 02X1501 0 1 0 -1100 S200 0 -2 1 1-50 X21000 1 0 0 1250 ZJ50 100 0 50 50CJ-ZJ0 0 -50 0 -501.1.确定出基变量，在常数列中找一个最小的负常量，把这个常量所在行作为出基变量确定出基变量，在常数列中找一个最小的负常量，把这个常量所在行作为出基变量47本讲稿第四十七页，共五十页44对偶单纯形法对偶单纯形法 4.检查常数列值，若已经都非负结束迭代，即为最优，如果还有检查常数列值，若已经都非负结束迭代，即为最优，如果还有负数重复负数重复1-

44、4步。步。迭代次数基变量CBX1 X2 S1 S2 S3b50 100 0 0 02X1501 0 1 1/2 -1/275 S200 0 -2 -1/2 -1/225 X21000 1 0 0 1250 ZJ50 100 0 25 7528750CJ-ZJ0 0 0 -25 -7548本讲稿第四十八页，共五十页这说明，若原问题的某一约束条件的右侧常数这说明，若原问题的某一约束条件的右侧常数b b增加一个单位，则由此引起最优目标增加一个单位，则由此引起最优目标函数值的增加量，这就等于该约束相对应的对偶变量的最优值。这样一来，在有限资函数值的增加量，这就等于该约束相对应的对偶变量的最优值。这样一

45、来，在有限资源条件下使收益最大化这一类问题中，即可把对偶变量的最优值，看成是相应资源每源条件下使收益最大化这一类问题中，即可把对偶变量的最优值，看成是相应资源每一单位对于目标函数的贡献，也就是这些资源被充分利用时所能带来的收益，从而，一单位对于目标函数的贡献，也就是这些资源被充分利用时所能带来的收益，从而，的值就相当于对单位的值就相当于对单位i i中资源在实现最大利润时的一种价格估计，这种估计是针对具中资源在实现最大利润时的一种价格估计，这种估计是针对具体企业具体产品而存在的一种特殊价格，称之为影子价格。体企业具体产品而存在的一种特殊价格，称之为影子价格。若仅从经济上考虑，当某种资源的市场价格低于影子价格时，企业就可以买进这种资若仅从经济上考虑，当某种资源的市场价格低于影子价格时，企业就可以买进这种资源，当市场价格高于影子价格时，企业就可以出售这种资源。源，当市场价格高于影子价格时，企业就可以出售这种资源。49本讲稿第四十九页，共五十页50本讲稿第五十页，共五十页