第二章线性规划的对偶理论及灵敏度分析

1、线性规划的对偶问题对偶问题的基本性质影子价格对偶单纯形法灵敏度分析参数线性规划l对偶问题概念：l任何一个线性规划问题都有一个伴生的线性规划问题，称为其“对偶”问题。l对偶问题是对原问题从另一角度进行的描述，其最优解与原问题的最优解有着密切的联系，在求得一个线性规划最优解的同时也就得到对偶线性规划的最优解，反之亦然。l对偶理论就是研究线性规划及其对偶问题的理论，是线性规划理论的重要内容之一。 项目每天可用能力设备A（h）0515设备B（h）6224调试工序（h）115利润（元）21我们引用第一章中美佳公司的例子，如表1其线性规划问题为：122121212max25156224. .5,0zxxx

2、xxstxxx x假定有某个公司想把美佳公司的资源收买过来，它至少应付出多大代价，才能使美佳公司愿意放弃生产活动，出让自己的资源？（LP1）2312362521yyyyy 条件：出让代价应不低于用同等数量资源由自己组织生产活动时获取的赢利。y1,y2,y3分别代表单位时间（h）设备A、设备B和调试工序的出让代价。 y1,y2,y3的取值应满足：美佳公司用6h设备B和1h调试可生产一件家电I,赢利2元用5h设备A,2h设备B及1h调试可生产一件家电，赢利1元该公司希望用最小代价把美佳公司的全部资源收买过来，即：123min1524zyyy123minw1524yyy综上所述，2312312362

3、. . 521,0yystyyyy yy（LP2）LP1和LP2两个线性规划问题，通常称LP1为原问题，LP2为前者的对偶问题。nnxcxcxcZ2211max0,. .212121212222111211nmnmnmmnnxxxbbbxxxaaaaaaaaatsmmybybybW2211min0,. .212121212221212111mnmmnnnmmyyycccyyyaaaaaaaaats对称形式的对偶问题对称形式的对偶问题CXZ maxTTYbW min0. .TTTTYCYAts0. .XbAXts对偶问题的特点若原问题目标是求极大化，则对偶问题的目标是极小化，反之亦然原问题的约束

4、系数矩阵与对偶问题的约束系数矩阵互为转置矩阵极大化问题的每个约束对应于极小化问题的一个变量，其每个变量对应于对偶问题的一个约束。 一般线性规划问题的对偶问题nnxcxcxcZ2211maxmmybybybW2211minnjjmnmnmmnnnnxbxaxaxabxaxaxabxaxaxa1), 0(0),(),(),(22112222212111212111或符号不限mijnmmnnnmmmmycyayayacyayayacyayaya1),0(0),(),(),(22112222211211221111或符号不限对偶问题对应表原问题（对偶问题） 对偶问题（原问题）目标函数maxZ目标函数m

5、inZ约束条件： m个第i个约束类型为“”第i个约束类型为“”第i个约束类型为“” 变量数： m个第i个变量0第i个变量0第i个变量是自由变量 变量数：n个第j个变量0第j个变量0第j个变量是自由变量 约束条件：n个第j个约束类型为“”第j个约束类型为“”第j个约束类型为“” 例22 标准型对偶问题 nnxcxcxcZ2211max0,. .2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxat s符号不限mnmmnnnmmmmyyycyayayacyayayacyayaya,2122112222211211221111mmybyb

6、ybW2211min例23321324minxxxZ 0,32121321321, 01413121110987654xxxxxxxxxxx符号不限32114117maxyyyW0y0,y,3212132132131062139541284符号不限yyyyyyyyy例2-4 写出下列问题的对偶问题1 1223311112133221 122223331ax. .00zc xc xc xa xa xa xba xa xa xbsta xa xa xbxxx， 无约束（2.4a）（2.4b）（2.4c）（2.4d）11223333max zc xc xc xc x1111

7、2213313321122223323321122223323331132233333312331223. .0000a xa xa xa xba xa xa xa xbsta xa xa xa xba xa xa xa xbxxxx ，对偶变量y1 y2 y2 y3先转换成对称形式，如下：例2-4令各约束对应的对偶变量分别为y1、y2、y2、 -y311222233min wb yb yb yb y11121221231312122222232313123223233313123223233312331223. .0000a ya ya ya yca ya ya ya ycsta ya ya

8、 ya yca ya ya ya ycyyyy ，令y2= y2-y2， y3=-y3，原问题的对偶问题为112233minwb yb yb y112131122232132333123112321233123. .0y0a ya ya yca ya ya ycsta ya ya ycyy， 无约束，项目原问题（对偶问题）对偶问题（原问题）A约束系数矩阵其约束系数矩阵的转置b约束条件的右端项向量目标函数中的价格系数向量C目标函数中的价格系数向量约束条件的右端项向量目标函数max z=CjXjmin w= biyi(1,., )00jjjjxjnxxx变量无约束ijijijijijijnja y

9、ca yca ycmi=1mi=1mi=1有 个（ =1，.,n）约束条件nijijnijijnijijmjma xba xba xbi=1i=1i=1有个（ =1，.,）约束条件y(1,.,)00jjjjjmyyy变量无约束线性规划的对偶问题对偶问题的基本性质影子价格对偶单纯形法灵敏度分析参数线性规划单纯形法计算的矩阵描述对称形式线性规划矩阵表达式加上松弛变量Xs后为：max0. .0,0zCXXsAXIXsbstXXs其中松弛变量Xs=（xn+1,xn+2,.,xn+m）,I为mm单位矩阵项目基变量基变量XB XNXs0 Xs bB NIcj-zjCB CN0选取I为初始基，对应基变量为X

10、s。设迭代若干步后，基变量为XB，XB在初始单纯形表中的系数矩阵为B。A中去掉B的若干列后剩下的列组成矩阵N。进一步迭代,新的单纯形表如下：项目基变量非基变量XBXN XsCB XB B-1bIB-1N B-1cj-zj0CN-CBB-1N CBB-1 对应初始单纯形表中的单位矩阵I，迭代后的单纯形 表中为B-1初始单纯形表中基变量Xs=b，迭代后的表中XB=B-1b初始单纯形表中约束系数矩阵为 A,I=B,N,I， 迭代后的表中约束系数矩阵为 B-1A,B-1I=B-1B,B-1N,B-1I=I,B-1N,B-1若初始矩阵中变量xj的系数向量为Pj，迭代后为 Pj，则有Pj=B-1Pj当B为

11、最优基时，表中应有 CN-CBB-1N0,-CBB-10例2-5参看例2-1中的原问题和对偶问题，并分别加上松弛变量和剩余变量，如下：12345max2000zxxxxx231241255156224. .50(1,.,5)jxxxxxstxxxxj12345min1524500wyyyyy234123562. . 5210(1,.,5)iyyystyyyyyi对偶变量y1y2y3对偶变量x1x2两个问题的最终单纯形表如下：项目原问题变量原问题松弛变量x1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1/43/2zj-cj0001/41/2变

12、量对偶问题的剩余变量对偶问题变量y4y5y1y2y3项目对偶问题变量对偶问题剩余变量y1y2y3y4y5y21/4-5/410-1/41/4y31/215/2011/2-3/2cj-zj15/2007/23/2变量原问题松弛变量原问题变量x3x4x5x1x21.弱对偶性 如果xj（j=1，.，n）是原问题的可行解，yi（i=1，.，m）是其对偶问题的可行解，则恒有11jjnmiijic xb y弱对偶性的推论：(1) 原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。(2) 如原问题有可行解且目标函数值无界(具有无界解)，则

13、其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解。注意：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然。(3) 若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。最优性如果 (j=1,.,n)是原问题的可行解，(i=1,.,m)是其对偶问题的可行解，且有j xi ynmjji ij=1i=1cx =by则 (j=1,.,n)是原问题的最优解， (i=1,.,m)是其对偶问题的最优解。j xi y 强对偶性(或称对偶定理) 若原问题及其对偶问题均具有可行

14、解，则两者均具有最优解，且它们最优解的目标函数值相等。互补松弛性 在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。也即i y若 0，则有 ，即1nij jija xb0six 若 ，即 ，则有1nij jija xb0six 0iy 因此一定有 ， six0iy 线性规划的对偶问题对偶问题的基本性质影子价格对偶单纯形法灵敏度分析参数线性规划对偶最优解的经济含义影子价格 *22*11*mmybybybZ 代表着当第i个右端常数增加一个单位时，最优目标函数值的相应增量。 其含义是在目前已给定的情况下

15、，最优目标值随资源数量变化的变化率； 其经济含义是为约束条件所付出的代价。 当B是原问题的最优基时，Y=CBB-1就是影子价格向量。资源的市场价格是其价值的客观体现，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。因企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。影子价格是一种边际价格。资源的影子价格实际上又是一种机会成本。随着资源的买进卖出，其影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。生产过程中如果某种资源未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。影子价格反映单纯

16、形表中各个检验数的经济意义。一般说对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及资源的最有效利用。ABC拥有量工 时1113材 料1479单件利润23321)9 , 3(minyyW0332714111. .2121yyyyts y1=5/3, y2=1/3 即工时的影子价格为5/3，材料的影子价格为1/3。如果目前市场上材料的价格低于1/3，则企业可以购进材料来扩大生产，反之可以卖掉部分材料。 如果有客户以高于5/3的价格购买工时，则可以出售一些工时，反之则反线性规划的对偶问题对偶问题的基本性质影子价格对偶单纯形法灵敏度分析参数线

17、性规划对偶单纯形法并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。求解单纯形法的基本思路： 对原问题的一个基可行解，判别是否所有检验数cj-zj0 (j=1,n)。若是，又基变量中无非零人工变量，即找到了问题最优解；若为否，再找出相邻的目标函数值更大的基可行解，并继续判别，只要最优解存在，就一直循环进行到找出最优解为止。对于标准线性规划问题：可行基可行基B B 若B对应的基本解是可行解最优基最优基B B 若B对应的基本解是最优解对偶可行基对偶可行基B B 若CBB-1是对偶问题可行解 即 C-CBB-1A0 或 检验数0 CXZ maxCYAts. .0. .XbAXtsYb

18、W min对于标准线性规划问题：CXZ maxCYAts. .0. .XbAXtsYbW min最优基B可行基B 对偶可行基B单纯形法可行基B 保持可行性 对偶可行基B对偶单纯形法可行基B 保持对偶可行性 对偶可行基B对于标准线性规划问题：CXZ max0. .XbAXts对偶单纯形法可行基B 保持对偶可行性 对偶可行基B 找一个基，建立初始对偶单纯形表，检验数全部非正； 若b列元素非负，则已经是最优基。反之，则取相应行的基变量为出基变量； 为保证能对基的可行性有所改进，则将来的主元应该为负数；为保证下一个基还能是对偶可行基，应使检验数仍为非正的。 主元变换12323123123min1524

19、562. . 521,0wyyyyystyyyy yy例26 用对偶单纯形法求解： 123452341235max152450062. .5210(1,.,5)iwyyyyyyyystyyyyyicj-15-24-500CB基by1y2y3y4y50y4-20-6-1100y5-1-5-2-101cj-zj-15-24-500-24y21/3011/6-1/600y3-1/3-50-2/3-1/31cj-zj-150-1-40-24y21/4-5/410-1/41/4-5y31/215/2011/2-3/2cj-zj-15/200-7/2-3/2练习：用对偶单纯形法求解 12312312312

20、3min524324. . 63510,0zxxxxxxstxxxx x x线性规划的对偶问题对偶问题的基本性质影子价格对偶单纯形法灵敏度分析参数线性规划 在生产计划问题的一般形式中，A代表企业的技术状况，b代表企业的资源状况，而C代表企业产品的市场状况，在这些因素不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值决定。 在实际生产过程中，上述三类因素均是在不断变化的，如果按照初始的状况制订了最佳的生产计划，而在计划实施前或实施中上述状况发生了改变，则决策者所关心的是目前所执行的计划还是不是最优，如果不是应该如何修订原来的最优计划。更进一步，为了防止在各类状况发生时，来不及随时

21、对其变化作出反应，即所谓“计划不如变化快”，企业应当预先了解，当各项因素变化时，应当作出什么样的反应。 灵敏度分析的步骤可归纳如下：1.将参数的改变通过计算反映到最终单纯形表上来。2.检查原问题是否仍为可行解。3.检查对偶问题是否仍为可行解。4.按下表所列情况得出结论或决定继续计算的步骤。原问题对偶问题结论或继续计算的步骤可行解可行解问题的最优解或最优基不变可行解非可行解用单纯形法继续迭代求最优解非可行解可行解用对偶单纯形法继续迭代求最优解非可行解非可行解引进人工变量，编制新的单纯形表重新计算 CB XB cjCBCN xj b XBTXNTCBTXBB-1b B-1BB-1N- CB B-1

22、b CB- CB B-1BCN- CB B-1N若B是最优基，则最优表形式如下灵敏度分析总是在最优表上进行 当系数A，b，C发生改变时，目前最优基是否还最优？ 为保持目前最优基还是最优，系数A，b，C的允许变化范围是什么？假设每次只有一种系数变化目标系数C变化 基变量系数发生变化； 非基变量系数发生变化；右端常数b变化增加一个变量增加一个约束技术系数A发生变化分析cj的变化例2-7 在第一章例1的美佳公司例子中：（1）若家电的利润降至1.5元/件，而家电的利润增至2元/件时，美佳公司最优生产计划有何变化?cj1.52000CB基bx1x2x3x4x50 x315/20015/4-15/21.5

23、x17/21001/4-1/22x23/2010-1/43/2cj-zj0001/8-9/40 x46004/51-61.5x1210-1/5012x23011/500cj-zj00-1/100-3/2即美佳公司随家电，的利润变化应调整为生产2件，生产3件。项目21+000CB基bx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21+x23/2010-1/43/2cj-zj000-1/4+1/4-1/2-3/2（2）若家电的利润不变，则家电的利润在什么范围内变化时，该公司的最优生产计划将不发生变化？ 设家电的利润为（1+）元，如下为保证最优解， -1/4

24、+1/40， -1/2-3/2 0解得-1/3 1即家电的利润c2的变化范围应满足2/3 c2 2分析bi的变化例2-8 在美佳公司的例子中：（1）若设备A和调试工序的每天能力不变，而设备B每天的能力增加到32h，分析公司最优计划的变化；cj21000CB基bx1x2x3x4x50 x335/20015/4-15/22x111/21001/4-1/21x2-1/2010-1/43/2cj-zj000-1/4-1/20 x315051002x15110010 x420-401-6cj-zj0-100-2080b 115/415/201001/41/28201/43/202bBb 例2-8 （2）

25、设设备A和设备B每天可用能力不变，则调试工序能力在什么范围内变化时，问题的最优基不变。 设调试工序每天可用能力为（5+）h，因有115215/415/20101/41/20201/43/232bBb 最终单纯形表中b列数字为15/2 15/27/2 1/23/23/2b因b0时最优基不变，故-11。调试工序的能力应在4h6h之间。增加一个变量xj的分析 若企业在计划期内，有新的产品可以生产，则在知道新产品的单位利润，单件资源消耗量时，可以在最优表中补充一列，其中的前m行可以由基矩阵的逆矩阵得到，而检验数行也可以由与其它列相同的方法计算得到。若检验数非正，则原最优解仍为最优，原生产计划不变，不生

26、产这种新产品；否则，当检验数为正时，则应以该变量进基，作单纯形迭代，从而找出新的最优解。 增加一个变量xj的分析增加一个变量在实际问题中反映为增加一种新的产品。其分析步骤为：3. 若 j0，原最优解不变，只需将计算得到的Pj和j直接写入最终单纯形表中；若j0，则按单纯形法继续迭代计算找出最优。例2-9 设美佳公司又计划推出新型号的家电，生产一件所需设备A、B及调试工序的时间分别为3h、4h、2h，该产品的预期盈利为3元/件，试分析该产品是否值得投产；如投产，对该公司的最优生产计划有何影响。 设生产x6件家电，有c6=3，P6=（3，4，2）T33(1 30,1/4,1/2) 42615/415

27、/23701/41/24001/43/222P cj210003CB基bx1x2x3x4x5x60 x315/20015/4-15/2-72x17/21001/4-1/201x23/2010-1/43/22cj-zj000-1/4-1/210 x351/407/213/8-9/402x17/21001/4-1/203x63/401/20-1/83/41cj-zj0-1/20-1/8-5/40最优生产计划应为每天生产7/2件家电，51/4件家电。分析参数aij的变化23(3/2 80,1/4,1/2) 41例2-10 在美佳公司的例子中，若家电每件需设备A,B和调试工时变为8h、4h、1h，该产

28、品的利润变为3元/件，试重新确定该公司最优生产计划。设生产工时变化后的新家电的生产量为x2，其中：215/415/2811/201/41/241/201/43/211/2P cj23000CB基bx1x2x3x4x50 x315/2011/215/4-15/22x17/211/201/4-1/21x23/201/20-1/43/2cj-zj03/20-1/4-1/20 x3-90014-242x121001/2-23x23010-1/23cj-zj0001/2-5原问题和对偶问题均为非可行解上表中第二阶段第一行的约束为：x3+4x4-24x5=-9 -x3-x4+24x5+x6=9替换后重新得

29、表：cj23000-MCB基bx1x2x3x4x5x6-Mx6900-1-42412x121001/2-203x23010-1/230cj-zj00-M1/2-4M-5+24M00 x53/800-1/24-1/611/242x111/410-1/121/601/123x215/8011/800-1/8cj-zj00-5/24-1/30-M+5/24最优生产计划为每天生产11/4台家电，15/8台家电|增加一个约束条件 在企业的生产过程中，经常有一些突发事件产生，造成原本不紧缺的某种资源变成为紧缺资源，对生产计划造成影响。 若把目前的最优解代入新增加的约束，能满足约束条件，则说明该增加的约束对

30、最优解不构成影响，即不影响最优生产计划的实施。 若当前最优解不满足新增加的约束，则应把新的约束添到原问题的最优表内新的一行中去，用对偶单纯形方法来进行迭代，求出新的最优解。 增加一个约束条件例2-11 设家电，经调试后，还需经过一道环境试验工序。家电每件需环境试验3h，家电每件需2h，又环境试验工序每天生产能力为12h。试分析增加该工序后的美佳公司最优生产计划。（1）检验原问题的最优解是否仍适用。将x1=7/2，x2=3/2代入3x1+2x212，27/212，所以不适用。（2）加入松弛变量x6，得3x1+2x2+x6=12（3）单纯形表求解。cj210000CB基bx1x2x3x4x5x60

31、 x315/20015/4-15/202x17/21001/4-1/201x23/2010-1/43/200 x612320001cj-zj000-1/4-1/200 x315/20015/4-15/202x17/21001/4-1/201x23/2010-1/43/200 x6-3/2000-1/4-3/21cj-zj000-1/4-1/200 x3150015/20-52x141001/30-1/31x20010-1/2010 x510001/61-2/3cj-zj000-1/60-1/3注：表中同，=-3-2。线性规划的对偶问题对偶问题的基本性质影子价格对偶单纯形法灵敏度分析参数线性规划当目标函数中cj值连续变化时，其参数线性规划的形式为：0. .)(max *XbbAXtsCXz当约束条件右端项连续变