第二章对偶理论与灵敏度分析ppt课件

1、第二章第二章 对偶实际与灵敏度分析对偶实际与灵敏度分析1线性规划的对偶问题2对偶问题的根本性质3影子价钱4对偶单纯形法5灵敏度分析第二章1线性规划的对偶问题线性规划的对偶问题1.1 对偶问题的提出1.2 对称方式下对偶问题的普通方式1.3 非对称方式的原对偶问题关系1.4 对偶问题的定义1.5 对偶关系对应表第二章例1：美佳公司利用该公司资源消费两种家电产品。项目项目I IIIII每天可用能力每天可用能力设备设备A A（h h）设备设备B B（h h）调试工序（调试工序（h h）0 06 61 15 52 21 1151524245 5利润（元）利润（元）2 21 1212max1xxzLP0

2、,52426155.2121212xxxxxxxst1.1 1.1 对偶问题的提出对偶问题的提出1线性规划的对偶问题线性规划的对偶问题第二章现从另一角度提出问题。假定有另一公司想把美佳公司的资源收买过来，它至少应付出多大代价，才干使美佳公司情愿放弃消费活动，出让本人的资源？显然美佳公司愿出让本人资源的条件是，出让代价应不低于用同等数量资源由本人组织消费活动时获取的盈利。设分别用yl，y2和y3代表单位时间h设备A、设备B和调试工序的出让代价。因美佳公司用6小时设备A和l小时调试可消费一件家电I，盈利2元；用5小时设备A，2小时设备B及1小时调试可消费一件家电II，盈利1元。1线性规划的对偶问题

3、线性规划的对偶问题第二章由此y1，y2，y3的取值应满足:该公司希望用最小代价把美佳公司的全部资源收买过来。因此，线性规划模型为：32152415minyyyz1252632132yyyyy32152415min)2(yyyzLP0,12526.32132132yyyyyyyyts1线性规划的对偶问题线性规划的对偶问题第二章例2 写出以下问题的原问题与对偶问题 1 2 加工才干(小时/天) A 2 2 12 B 1 2 8 C 4 0 16 D 0 4 12 2 3销售收入产品设备1线性规划的对偶问题线性规划的对偶问题第二章原问题：设x1 ， x2 为产品1，2的产量2x1 +2x2 12 x

4、1 +2x2 84x1 16 4x2 12x1 x2 0maxZ= 2X1 +3x2 2 2 12 1 2 x1 84 0 x2 160 4 12(2 3) x1x21线性规划的对偶问题线性规划的对偶问题第二章对偶问题：设 y1 , y2 , y3 , y4分别为A, B, C, D设备的单价2y1 +y2 +4y3 22y1 +2y2 +44 3y1 y4 02 1 4 02 2 0 4y1 y2 y3 y4 23(y1 y2 y3 y4)1281612minW=12y1+8y2 +16y3+12y4y1 y4 “影子价钱1线性规划的对偶问题线性规划的对偶问题第二章对称的含义：满足以下条件的

5、线性规划问题称为具有对称方式：其变量均具有非负约束，其约束条件当目的函数求极大时均取“号，当目的函数求极小时均取“号。对称方式下线性规划原问题的普通方式为：max Z=c1x1+ c2x2+cnxna11x1+ a12x2+ a1nxn b1a21x1+ a22x2+ a2nxn b2 am1x1+ am2x2+ amnxn bmxj 0(j=1,n)s.t.1.2 对称方式下对偶问题的普通方式对称方式下对偶问题的普通方式1线性规划的对偶问题线性规划的对偶问题第二章用yi(i1，m)代表第i种资源的估价，那么其对偶问题的普通方式为：min w=b1y1+ b2y2+bmyma11y1+ a21

6、y2+ am1ym c1a12y1+ a22y2+ am2ym c2 a1ny1+ a2ny2+ amnym cnXj 0(j=1,m)s.t.1线性规划的对偶问题线性规划的对偶问题第二章用矩阵方式表示，原问题为:其对偶问题为：CXz max0.XbAXstbYwmin0.YCYAst1线性规划的对偶问题线性规划的对偶问题第二章原问题与对偶问题的对应关系 原问题 对偶问题A 约束系数矩阵 其系数矩阵转置B 约束条件右端项向量 目的函数价值系数C 目的函数价值系数 约束条件 右端项向量 目的函数 maxz=CX min w =Yb 约束条件 AX b AY C 决策变量 X 0 Y0 1线性规划

7、的对偶问题线性规划的对偶问题第二章1.3 非对称方式的原对偶问题关系非对称方式的原对偶问题关系1线性规划的对偶问题线性规划的对偶问题例例2 写出下述线性规划问题的对偶问题写出下述线性规划问题的对偶问题321321321321321, 0, 041632532. .34maxxxxxxxxxxxxxtsxxxz无约束第二章1.3 非对称方式的原对偶问题关系非对称方式的原对偶问题关系1线性规划的对偶问题线性规划的对偶问题写出其对偶问题为：写出其对偶问题为：可变换成具有如下对称可变换成具有如下对称方式的线性规划问题方式的线性规划问题0,44166325532. .334max 3321 3321 3

8、321 3321 3321 3321xxxxxxxxxxxxxxxxxxxxtsxxxxz0,36536543132. .442min 3321 3321 3321 3321 3321 3321yyyyyyyyyyyyyyyyyyyytsxyyyw第二章1.3 非对称方式的原对偶问题关系非对称方式的原对偶问题关系1线性规划的对偶问题线性规划的对偶问题进展整理为：进展整理为：321321321321321, 0, 036543132. .42minyyyyyyyyyyyytsyyyz无约束第二章例3 写出下述线性规划问题的对偶问题1.3 非对称方式的原对偶问题关系非对称方式的原对偶问题关系max

9、Z= 5X1 +6X2 3X1 -2X2 =74X1 +X2 9X1 , X2 01线性规划的对偶问题线性规划的对偶问题第二章解：原问题可化为maxZ= 5X1 +6X2 3X1 -2X2 7-3X1 +2X2 -74X1 +X2 9X1 , X2 0y1y1 y2那么对偶问题：3y1 -3y1 +4y2 5 -2y1 +2y1 +y2 6y1 , y1 , y2 0minW=7y1 -7y1 +9y21线性规划的对偶问题线性规划的对偶问题第二章令 y1 = y1 -y1 minW=7y1 +9y23y1+4y2 5 -2y1 +y2 6y1自在 , y2 01线性规划的对偶问题线性规划的对偶

10、问题第二章1.4 1.4 对偶的关系对偶的关系原始问题max z=CTXs.t.AX bX 0对偶问题min y=bTWs.t. ATW CW 0CATbTminmnmaxbACTmn1线性规划的对偶问题线性规划的对偶问题第二章 原问题 对偶问题目的函数类型 max min目的函数系数 目的函数系数 右边项系数与右边项的对应关系 右边项系数 目的函数系数变量数与约束数 变量数n 约束数 n的对应关系 约束数m 变量数m原问题变量类型与 0 对偶问题约束类型 变量 0 约束 的对应关系 无限制 原问题约束类型与 0 对偶问题变量类型 约束 变量 0 的对应关系 无限制1.5 1.5 对偶关系对应

11、表对偶关系对应表1线性规划的对偶问题线性规划的对偶问题第二章第二章2对偶问题的根本性质对偶问题的根本性质单纯形法计算的矩阵描画单纯形法计算的矩阵描画一、对称性一、对称性 二、弱对偶性二、弱对偶性三、无界性三、无界性 四、可行解是最优解的性质四、可行解是最优解的性质五、对偶定理五、对偶定理六、松紧定理六、松紧定理 第二章用矩阵方式表示，原问题为:其对偶问题为：min y=bYs.t. AY CY 0max z=CXs.t.AX bX 02对偶问题的根本性质对偶问题的根本性质满足这两个条件的Y是对偶问题的一个可行解。满足这两个条件的X是原问题的一个可行解。第二章单纯形法计算的矩阵描画单纯形法计算的

12、矩阵描画对称方式线性规划问题的矩阵表达式加上松弛变量后为：0, 00maxSSSXXbIXAXXCXZ上式中XS为松弛变量) ,(21mnnnSxxxX I 为mm单位矩阵经过迭代后: X=XB + XN相应地: C=CB + CN系数矩阵 : A= B + N2对偶问题的根本性质对偶问题的根本性质参1-105第二章迭代后新的单纯形表为：初始单纯形表：非基变量基变量XXS0 XS bcj-zj基变量非基变量XB XN XSCB XB B-1bcj-zj2对偶问题的根本性质对偶问题的根本性质第二章迭代后新的单纯形表为：初始单纯形表：非基变量基变量XB XN XS0 XS bB NIcj-zjCB

13、 CN0基变量非基变量XB XN XSCB XB B-1bI B-1N B-1cj-zjCB- CBB-1BCN- CBB-1N -CBB-1C- CBB-1A2对偶问题的根本性质对偶问题的根本性质第二章可以看出：(1)对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1 ；(2)初始单纯形表中基变量Xsb，迭代后的表中 XB=B1b ；(3)初始单纯形表中约束系数矩阵为A，I B，N，I ，迭代后的表中约束系数矩阵为B-1A，B-1IB-1B，B-1N，B-1I I，B-1N，B-1 ；(4)假设初始矩阵中变量Xi的系数向量为Pj，迭代后为Pj，那么有Pj=B-1Pj 。2对偶问题的根

14、本性质对偶问题的根本性质第二章当B为最优基时因xB的检验数可写为 CB- CBI=0CBB-1称为单纯形乘子，假设令Y= CBB-1 ，那么所以0YCAY0YCYACN- CBB-1N 0 -CBB-1 0C- CBB-1A 0 -CBB-1 02对偶问题的根本性质对偶问题的根本性质第二章看出这时检验数行，假设取其相反数恰好是其对偶问题的一个可行解。将这个解代入对偶问题的目的函数值，有：当原问题为最优解时，这时对偶问题为可行解，且两者具有一样的目的函数值，对偶问题的解也为最优解。w=Yb= CBB-1b=z2对偶问题的根本性质对偶问题的根本性质第二章例例4 5x2 +x3 =15 s.t. 6

15、x1 +2x2 +x4 =24 x1 + x2 +x5 =5 x1 , , x5 0 maxZ=2x1+ x2+0 x3 +0 x4+0 x5s.t. 6y2 + y3 -y4 =2 5y1 + 2y2 + y3 -y5 =1 y1 , , y5 0 min w=15y1+ 24y2+ 5y3 +0y4+0y52对偶问题的根本性质对偶问题的根本性质第二章最终单纯形表：最终单纯形表：原问题变量松弛变量XB bx1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1/43/2zj-cj0001/41/2对偶问题的剩余变量对偶问题变量y4y5y1y2y

16、3对偶问题变量对偶问题的剩余变量XB by1y2y3y4y5y21/4-5/410-1/41/4y31/215/2011/2-3/2cj zj15/2007/23/2原问题的松驰变量原问题变量x3x4x5x1x22对偶问题的根本性质对偶问题的根本性质第二章 0maxxbAxLxczT0minYcYADYbw一一 . 对称性对称性 ： 对偶问题的对偶是原问题对偶问题的对偶是原问题2对偶问题的根本性质对偶问题的根本性质第二章 0minYcYADYbw 0)()(maxYcAYDbYw 0minxbAxLxcwT 0maxxbAxLxczT对对偶偶2对偶问题的根本性质对偶问题的根本性质第二章假设x是

17、原问题的可行解，y是对偶问题的可行解。那么有 cxyb byxAyxcoxcAybyxAyybxA又证明：0二二. 弱对偶性弱对偶性2对偶问题的根本性质对偶问题的根本性质第二章推论(2)： 假设原问题对偶问题为无界解，那么其对偶问题原问题无可行解。推论(1)： 原问题任一可行解的目的函数值是其对偶问标题的函数值的下界，反之对偶问题任一可行解的目的函数值是其原问标题的函数值的上界。 注 ： 其逆不成立。推论(3)假设原问题有可行解而其对偶问题无可行解，那么原问标题的函数值无界，反之对偶问题有可行解而其原问题无可行解，那么对偶问题的目的函数值无界。2对偶问题的根本性质对偶问题的根本性质第二章设x是

18、原问题的可行解，y是对偶问题的可行解. 当 cx= yb 时 x, y 是最优解。三三 . 最优性最优性*CXCX证明：bYbY*bYCX又bYCX*CXCXbYbY*CXCXbYbY2对偶问题的根本性质对偶问题的根本性质第二章四四 . 强对偶性对偶定理强对偶性对偶定理 假设原问题及其对偶问题均具有可行解，那么两者均具有最优解且它们最优解的目的函数值相等。证明： 由弱对偶定理推论1，可知两者都有最优解。由前面公式可知，当原问题有最优解时，对偶问题有可行解，且目的函数值相等。由最优性知，两者均为最优解。2对偶问题的根本性质对偶问题的根本性质第二章五五. 互补松弛性松紧定理互补松弛性松紧定理在线性

19、规划问题的最优解中，假设对应某一约束条件的对偶变量值为非零，那么该约束条件取严厉等式；反之假设约束条件取严厉不等式，那么其对应的对偶变量一定为零。y1y2y3212max1xxzLP0,52426155.2121212xxxxxxxst2对偶问题的根本性质对偶问题的根本性质第二章即：0即,则有,0若1sinjijijixbxay0则有, 0即, ,若1isinjiijyxbxa0因此一定有isiyx2对偶问题的根本性质对偶问题的根本性质 miiiminjijijnjjjybyxaxc1111001njijijibxa，y必有时当001injijijy，bxa必有时当证明：011injijijm

20、iybxa01injijijybxa第二章无最优解。：证明：0324min132131321ixxxxxxxxx几个练习几个练习2对偶问题的根本性质对偶问题的根本性质第二章故无最优解。原问题是无界的，对偶问题不可行，因而考虑其对偶问题为其一可行解。证明：0,121134max)0 , 0 , 4(212122121yyyyyyyyyzx2对偶问题的根本性质对偶问题的根本性质第二章025357162954max2321321321ixxxxxxxxxxz：考虑问题1 阐明原问题和对偶问题都有最优解.2 求原问题和对偶问题的最优目的函数值的一个上界和下界.2对偶问题的根本性质对偶问题的根本性质第二

21、章两者都有最优解。对偶性质可知，两问题都有可行解，由有可行解：其对偶问题为：原问题有可行解）解：)0 , 5(0,93255472516min)8 ,0 ,0(12121212121yyyyyyyyyyyx2对偶问题的根本性质对偶问题的根本性质第二章8072.80)0 , 5(;72)8 ,0 ,0(2*zzyzx下界。有上数值由弱对偶性最优目标函有对于对偶问题的可行解有）对于原问题的可行解2对偶问题的根本性质对偶问题的根本性质第二章对偶问题的最优解。用互补松弛定理计算的最优解为问题：已知28)4 , 4 , 0 , 0(02023220322432max3*432143214321zxxxx

22、xxxxxxxxxxzLPi0,42333222122020min212121212121yyyyyyyyyyyy解：对偶问题为：2对偶问题的根本性质对偶问题的根本性质第二章最优值。为对偶问题的最优解和；对应目标函数值为对偶问题的可行解，经检验解得有由有根据互补松弛定理，由285/1, 5/6285/1, 5/65/1, 5/6423043320421*2121214213yyzyyyyyyxyyx2对偶问题的根本性质对偶问题的根本性质第二章最优解。）是可行的，则一定有证明：若问题（）：问题（。得到改为有最优解。现将向量）：问题（：设20min20min14XdAXCXLPdbXbAXCXLP

23、2对偶问题的根本性质对偶问题的根本性质第二章。可知其对偶问题必可行理，）有最优解，由对偶定问题（ 1）的对偶问题亦可行，从而问题（ 2）一定有最优解。由强对偶性，问题（2CYAYbzmax1）的对偶问题为：证明：问题（0YCYAYdzmax2）的对偶问题为：问题（0Y2对偶问题的根本性质对偶问题的根本性质第二章3影子价钱影子价钱式中bi是线性规划原问题约束条件的右端项，它代表第i种资源的拥有量；对偶变量yi*的意义代表在资源最优利用条件下对单位第i仲资源的估价。这种估价不是资源的市场价钱，而是根据资源在消费中作出的奉献而作的估价，为区别起见，称为影子价钱(shadow price)。njmii

24、ijjwybxcz11*第二章关于影子价钱的几点阐明1影子价钱是未知数,有赖于资源的利用情况。2影子价钱是一种边沿价钱。miiiybz1*iiybz求导 这阐明影子价钱的值相当于在资源得到最优利用的消费条件下，b每添加一个单位时目的函数Z的增量。3影子价钱影子价钱第二章原问题变量松弛变量XB bx1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1/43/2zj-cj0001/41/2对偶问题的剩余变量对偶问题变量y4y5y1y2y3例1ABC15/200资源剩余01/41/2影子价钱543210002maxxxxxxz)5,.,1(05242

25、615552142132jxxxxxxxxxj3影子价钱影子价钱第二章15/4，5/4z=8.753，3z=9BAC7/2，3/2z=8.5所以第2种资源的影子价钱为0.25，第3种资源的影子价钱为0.5。3影子价钱影子价钱第二章3资源的影子价钱实践上又是一种时机本钱。在纯市场经济条件下，可以根据影子价钱与市场价钱的关系确定资源的买进或卖出。4消费过程中假设某种资源末得到充分利用时，该种资源的影子价钱为零；又当资源的影子价钱不为零时，阐明该种资源在消费中已耗费终了。3影子价钱影子价钱第二章5单纯形表中各个检验数的经济意义 6对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解那么

26、是确定对资源的恰当估价。当产品产值大于隐含本钱时，阐明消费该项产品有利，可在方案中安排，否那么这些资源来消费别的产品更为有利，就不在方案中安排。这就是单纯形表中各个检验数的经济意义。miiijjjBjjyacPBCc113影子价钱影子价钱第二章4对偶单纯形法对偶单纯形法单纯形法的思绪：找一个基可行解，在坚持解可行的前单纯形法的思绪：找一个基可行解，在坚持解可行的前提下，让检验数全为非正。提下，让检验数全为非正。 原问题变量原问题变量松弛变量松弛变量XB bx1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1/43/2zj-cj0001/41/

27、2对偶问题的剩余变量对偶问题的剩余变量对偶问题变量对偶问题变量y4y5y1y2y3第二章对偶单纯形法的根本思绪：先找出一个对偶问题对偶单纯形法的根本思绪：先找出一个对偶问题的可行基，并坚持对偶问题为可行解条件下，如不存的可行基，并坚持对偶问题为可行解条件下，如不存在在XB o，经过变换到一个相邻的目的函数值较小的，经过变换到一个相邻的目的函数值较小的根本解根本解(因对偶问题是求目的函数极小化因对偶问题是求目的函数极小化)，并循环进，并循环进展，不断到原问题也为可行解展，不断到原问题也为可行解(即即XB o)，这时对偶，这时对偶问题与原问题均为可行解。问题与原问题均为可行解。在迭代过程中坚持原问

28、题的检验数为非正，逐渐在迭代过程中坚持原问题的检验数为非正，逐渐交换负基变量，从而得到最优解。交换负基变量，从而得到最优解。4对偶单纯形法对偶单纯形法第二章对偶单纯形法的计算步骤：对偶单纯形法的计算步骤： 1. 列出初始单纯形表，且检验数非正。 为换出变量。对应的基变量按rriiixbBbBbB1110min.2为换入变量确定按srsssrjrjjjxazcaazc0min.34对偶单纯形法对偶单纯形法第二章4.以ars为主元素，进展迭代变换。可以证明，按照上述方法进展迭代变换以后，检验数仍坚持为非正，即对偶问题仍可行。5 . 返 2，直到B 0为止。原始单纯形法 按列选主元 对偶单纯形法 按

29、行选主元对于对偶问题有可行解，而原问题无可行解的判别。判别准那么是：对 ，而对一切j=1,n，有 。0rja0rb4对偶单纯形法对偶单纯形法第二章例5：用对偶单纯形法求解以下问题02225324. .23min321321321321321xxxxxxxxxxxxtsxxxz02225324. .23min654321632153214321321xxxxxxxxxxxxxxxxxxtsxxxz4对偶单纯形法对偶单纯形法第二章02225324. .23max654321632153214321321xxxxxxxxxxxxxxxxxxtsxxxzCj321000CBXBbx1x2x3x4x5x

30、60 x441111000 x552310100 x62221001 j=cj-zj4对偶单纯形法对偶单纯形法第二章Cj321000CBXBbx1x2x3x4x5X60 x417/31/302/31-1/30-2x25/3-2/31-1/30-1/300X6-16/3-2/30-1/302/31 j=cj-zjCj321000CBXBbx1x2x3x4x5X60 x417/31/302/31-1/30-2X25/3-2/31-1/30-1/300X6-16/3-2/30-1/302/31 j=cj-zj-13/30-5/30-2/304对偶单纯形法对偶单纯形法第二章Cj321000CBXBbx

31、1x2x3x4x5X60 x4-5-10011/32-2X270100-1-1-1X3162010-2-3 j=cj-zj-1000-7/3-5Cj321000CBXBbx1x2x3x4x5X6-3x15100-1-1/3-2-2X270100-1-1-1X360012-21 j=cj-zj000-1-5-74对偶单纯形法对偶单纯形法第二章已获得最优解：x1, x2, x3, x4, x5, x6=5, 7, 6, 0, 0, 0 min z=35对偶问题的最优解为：w1, w2, w3, w4, w5, w6=-1, 5, 7, 0, 0, 0 max y=354对偶单纯形法对偶单纯形法第二

32、章 从以上计算可以看出，用对偶单纯形法求解线性规划问题时，当约束条件为“时，不用引进人工变量，使计算简化。但在初始单纯形表中其对偶问题应是基可行解这点，对多数线性规划问题很难实现。因此对偶单纯形法普通不单独运用，而主要运用于灵敏度分析及整数规划等有关章节中。4对偶单纯形法对偶单纯形法例:(初始解原始、对偶都不可行的问题)0 xxx2xx2x5xx3x24xxx. t . sx2x2x3zmin3213213213213210 xxxxxx2xxx2x5xxx3x24xxxx. t . sx2x2x3zmin65432163215321432132102225324. .223max654321

33、632153214321321xxxxxxxxxxxxxxxxxxtsxxxz解法1：先处理原始可行性Cj322000CBXBbx1x2x3x4x5x60 x441111000 x552310100 x62221001 j=cj-zjCj322000CBXBbx1x2x3x4x5x60 x417/31/302/31-1/30-2x25/3-2/31-1/30-1/300 x6-16/3-2/30-1/302/31 j=cj-zj-13/304/30-2/30Cj322000CBXBbx1x2x3x4x5x60 x43001/2101/2-2x270100-1-1-3x18101/20-1-3/

34、2 j=cj-zj0011/20-5-13/2Cj322000CBXBbx1x2x3x4x5x62x36001201-2x270100-1-1-3x15100-1-1-2 j=cj-zj000-7-5-10在得到原始可行解时同时得到对偶可行解，已获得最优解：x1, x2, x3, x4, x5, x6=5, 7, 6, 0, 0, 0 min z=17对偶问题的最优解为：w1, w2, w3, w4, w5, w6=-7, 5, 10, 0, 0, 0 max y=17第二章Cj322000CBXBbx1x2x3x4x5x60 x441111000 x552310100 x62221001 j

35、=cj-zj322000解法2：先处理对偶可行性已得到对偶可行解，再用对偶单纯形法求解Cj322000CBXBbx1x2x3x4x5x62x341111000 x59120-1100 x62110101 j=cj-zj500-200Cj322000CBXBbx1x2x3x4x5x62x317/21/2013/2-1/20-2x29/2-1/2101/2-1/200 x6-5/2-1/2001/21/21 j=cj-zj500-200Cj322000CBXBbx1x2x3x4x5x62x36001201-2x270100-1-1-3x15100-1-1-2 j=cj-zj000-7-5-10得到

36、原始可行解，已获得最优解：x1, x2, x3, x4, x5, x6=5, 7, 6, 0, 0, 0 min z=17对偶问题的最优解为：w1, w2, w3, w4, w5, w6=-7, 5, 10, 0, 0, 0 max y=17第二章对偶单纯形法的优点：对偶单纯形法的优点： 1 简化计算简化计算 2 减少计算量减少计算量 3 灵敏度分析灵敏度分析缺陷：缺陷： 第一个正那么解很难找到第一个正那么解很难找到4对偶单纯形法对偶单纯形法第二章5灵敏度分析灵敏度分析灵敏度分析是指对系统或事物因周围条件变化显示出来的敏感程度的分析。A，b，C当这些参数中的一个或几个发生变化时，问题的最优解会

37、有什么变化，或者这些参数在一个多大范围内变化时，问题的最优解不变。这就是灵敏度分析所要研讨处理的问题。单纯形法的迭代计算是从一组基向量变换为另一组基向量，表中每步迭代得到的数字只随基向量的不同选择而改动，因此有能够把个别参数的变化直接在计算得到最优解的最终单纯形表上反映出来。第二章 灵敏度分析的步骤灵敏度分析的步骤1将参数的改动计算反映到最终单纯形表上来：将参数的改动计算反映到最终单纯形表上来：5灵敏度分析灵敏度分析bBb1jjPBP1bBXB1jjPBP101ABCCBmiiijjjjyaczc1*)(第二章2检查原问题能否仍为可行解；3检查对偶问题能否仍为可行解；4按下表所列情况得以结论和

38、决议继续计算的步骤。原问题对偶问题结论或继续计算的步骤可行解可行解最优解可行解非可行解用单纯形法求解最优解非可行解可行解用对偶单纯形法求解最优解非可行解非可行解引入人工变量求解最优解5灵敏度分析灵敏度分析第二章灵敏度分析处理的主要问题：(1)、参数A，b，C在什么范围内变动，对当前方案无影响？ (2)、参数A，b，C中的一个(几个)变动，对当前方案影响？ (3)、假设最优方案改动，如何用简便方法求新方案？5灵敏度分析灵敏度分析第二章一、分析一、分析Cj的变化的变化线性规划目的函数中变量系数线性规划目的函数中变量系数Cj的变化仅仅影的变化仅仅影响到检验数响到检验数(Cj-Zj)约变化。所以将约变

39、化。所以将Cj的变化直接反的变化直接反映到最终单纯形表中，只能够出现前两种情况。映到最终单纯形表中，只能够出现前两种情况。5灵敏度分析灵敏度分析原问题对偶问题结论或继续计算的步骤可行解可行解最优解可行解非可行解用单纯形法求解最优解非可行解可行解用对偶单纯形法求解最优解非可行解非可行解引入人工变量求解最优解第二章5灵敏度分析灵敏度分析 例5 在第一章例1的美佳公司例子中:(1)假设家电I的利润降至1. 5元件，而家电的利润增至2元件时，美佳公司最优消费方案有何变化?Cj21000CBXBbx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2010

40、-1/43/2 j=cj-zj000-1/4-1/2第二章5灵敏度分析灵敏度分析解 (1)将家电I，II的利润变化直接反映到最终单纯形表中。Cj1.52000CBXBbX1x2x3x4x50 x315/20015/4-15/21.5x17/21001/4-1/22x23/2010-1/43/2 j=cj-zj0001/8-9/4以x4为换入变量,x3为换出变量，列新单纯形表。Cj1.52000CBXBbx1x2x3x4x50 x46004/51-61.5x1210-1/5012x23011/500 j=cj-zj00-1/10 0-3/2一切检验数为非正，问题得到最优解：X2，3，0，6，0第

41、二章5灵敏度分析灵敏度分析(2)假设家电I的利润不变，那么家电II的利润在什么范围内变化时，那么该公司的最优消费方案将不发生变化？设家电II的利润为(1十)元，反映到最终单纯形表中为：Cj21十000CBXBbx1x2x3x4x50 x460015/4-15/22x121001/4-1/21十x23010-1/43/2 j=cj-zj000-1/4+1/4 -1/2-3/2 为使表中的解仍为最优解，应有即家电II的利润C2的变化范围应满足：第二章例6 A B C 备用资源 甲 1 1 1 12 乙 1 2 2 20 利润 5 8 6 产品原料问：如何安排产品产量，可获最大利润？5灵敏度分析灵敏

42、度分析第二章maxZ=5X1 +8X2 +6X3X1+ X2 + X3+X4 = 12X1+2X2+2X3 +X5 =20X1 X5 0解：Cj58600CBXBbx1x2x3x4x55x14100218x2801111 j=cj-zj00223最优单纯形表为：问: 价值系数变化时对最优解的影响？5灵敏度分析灵敏度分析第二章(1)、非基变量系数Cj Cj 改动，仍有j0 时对最优方案无影响。12=C3 -(5 8) =C3 -80 2 -1-1 1即C3 8 例中C3在什么范围内变化时，对最优方案无影响？ 3 = C3 -CBB-1 P35灵敏度分析灵敏度分析第二章 C3改为10， 最优方案如

43、何变化？CB XB b 5 8 10 0 0 5 X1 4 1 0 0 2 -1 8 X2 8 0 1 (1) -1 1 0 0 (2) -2 -3 5 X1 4 1 0 0 2 -1 X3 8 0 1 1 -1 1 0 -2 0 0 -5 3 =205灵敏度分析灵敏度分析第二章(2)、基变量系数Cj Cj 改动？ 全部 j0，最优方案不变例中C1改动 A = C -CBB-1 A =(0,0,-2,-2C1+8, C1 -8) 0-2C1+8 0C1-8 04 C1 81 0 0 2 -10 1 1 -1 1=(C1 ,8,6,0,0 ) -(C1 8)5灵敏度分析灵敏度分析第二章 C1改动

44、 C1=10？ XB 10 8 6 0 010 X1 4 1 0 0 2 -1 8 X2 8 0 1 1 -1 (1) 0 0 -2 -12 2 10 X1 12 1 1 1 1 0 0 X5 8 0 1 1 -1 1 0 -2 -4 -10 0 5 =20 ,换基5灵敏度分析灵敏度分析第二章二、分析二、分析bi的变化的变化右端项bj的变化在实践问题中反映为可用资源数量的变化。原问题对偶问题结论或继续计算的步骤可行解可行解最优解可行解非可行解用单纯形法求解最优解非可行解可行解用对偶单纯形法求解最优解非可行解非可行解引入人工变量求解最优解5灵敏度分析灵敏度分析第二章 例7：在美佳公司的例子中：(

45、1)假设设备A和调试工序的每天才干不变，而设备B每天的才干添加到32小时，分析公司最优方案的变化?Cj21000CBXBbx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2 j=cj-zj000-1/4-1/2解：由于：080b22100802/ 34/ 102/ 14/ 102/154/ 511bBb5灵敏度分析灵敏度分析第二章以X2为换出变量，X4为换入变量，列新单纯形表得：问题的最优解：X5，0，15，2，0Cj21000CBXBbx1x2x3x4x50 x335/20015/4-15/22x111/21001/4-

46、1/21x2-1/2010-1/43/2 j=cj-zj000-1/4-1/2Cj21000CBXBbx1x2x3x4x50 x315051002x15110011x420-401-6 j=cj-zj0-100-25灵敏度分析灵敏度分析第二章单纯形表中b列数字为：(2)假设设备A和B每天可用才干不变，那么调试工序才干在什么范围内变化时，问题的最优基不变?设调试工序每天可用才干为5+小时，因有2321215002/ 34/ 102/ 14/ 102/154/ 511bBb23232127215215b当b 0时问题的最优基不变，解得：-1 1因此调试工序的才干应在4小时-6小时之间。5灵敏度分析

47、灵敏度分析第二章(1)、bj 改动？改动？ B-1 b仍仍0时，最优方案不变。时，最优方案不变。例中例中b1改动改动2 -1-1 1b120B-1 b= 010 b1 20 2b1 -20 0-b1+20 0Cj58600CBXBbx1x2x3x4x55x14100218x2801111 j=cj-zj00223前面例子：前面例子：第二章CB XB 5 X1 40 1 0 0 2 -1 8 X2 -10 0 1 1 (-1) 1 0 0 -2 -2 -3 5 X1 20 1 2 2 0 1 0 X4 10 0 -1 -1 1 -1 0 -2 -4 0 -5(2)、 b1改动改动, b1=30

48、，2 -1-1 13020B-1 b= 40-10第二章三、添加一个变量三、添加一个变量xj的分析的分析添加一个变量在实践问题中反映为添加一种新的产品。其分析步骤为：miiijjjjjyaczc1*计算. 1jjPBP1计算. 23.假设 ，原最优解不变，只需将计算得到的 和 直接写入最终单纯 形表中；假设 ，那么按单纯形法继续迭代计算找出最优。0jjPj0j5灵敏度分析灵敏度分析第二章 例8 在美佳公司例子中，设该公司又方案推出新型号的家电III，消费一件所需设备A、B及调试工序的时间分别为3小时、4小时、2小时，该产品的预期盈利为3元件。试分析该种产品能否值得投产，如投产，对该公司的最优消

49、费汁划有何变化。1243)21,41, 0(32072432/ 34/ 102/ 14/ 102/154/ 516P解：设该公司消费家电III 件，有TPc)2 , 4 , 3(, 3665灵敏度分析灵敏度分析第二章以x2 为换出变量， x6 为换入变量，列新单纯形表得：Cj210003CBXBbx1x2x3x4x5x60 x315/20015/4-15/2-72x17/21001/4-1/201x23/2010-1/43/22 j=cj-zj000-1/4-1/215灵敏度分析灵敏度分析第二章问题的最优解：X7/2，0，51/4，0，0，3/4T。所以，该公司新的消费方案应为每天消费家电I

50、7/2件，消费家电III 3/4件。Cj210003CBXBbx1x2x3x4x5x60 x351/407/213/8-9/402x17/21001/41/203x63/401/20-1/83/41 j=cj-zj0-1/20-1/8-5/405灵敏度分析灵敏度分析第二章现有新产品现有新产品D D，知消费，知消费1 1个单位个单位D D要耗费：要耗费： 甲：甲：3 3 乙：乙：2 2 ，可以得利润，可以得利润1010。问：投产产品问：投产产品D D能否有利？能否有利？Cj58600CBXBbx1x2x3x4x55x14100218x2801111 j=cj-zj00223 A B C 备用资源

51、备用资源 甲甲 1 1 1 12 乙乙 1 2 2 20 利润利润 5 8 6 产品产品原料原料前面例子：前面例子：第二章结论：无利结论：无利 6 = C6 - CBB-1 P6 = 10 - (5 8) 2 -1 3 -1 1 2 = 10 - 12 = -2 0 得 C6 122 2 C6 =15 C6 =15 时时 ，原问题的最优解为多少？，原问题的最优解为多少？ 6 =3 6 =3 P6 = B-1 P6 = 2 -1 3 = 4 -1 1 2 -1 第二章 5 8 6 0 0 15 5 8 6 0 0 15 XB X1 XB X1 X2 X3 X4 X5 X6X2 X3 X4 X5

52、X6 X1 4 1 0 X1 4 1 0 0 2 -1 (4)0 2 -1 (4) X2 8 0 1 X2 8 0 1 1 -1 1 -11 -1 1 -1 0 0 0 0 -2 -2 -3 3-2 -2 -3 3 X6 1 1/4 0 X6 1 1/4 0 0 -1/2 -1/4 1 0 -1/2 -1/4 1 X2 9 1/4 1 X2 9 1/4 1 1 -1/2 3/4 0 1 -1/2 3/4 0 -3/4 0 - -3/4 0 -2 -7/2 -9/4 02 -7/2 -9/4 0第二章四、分析参数四、分析参数aij的变化的变化 aij的变化使线性规划的约束系数矩阵A发生变化。假设

53、变量xj在最终单纯形表中为非基变量，其约束条件中系数aij的变化分析步骤可参照本节之三；假设变量xi在最终单纯形表中为基变量，那么aij的变化将使相应的B和B-1 发生变化因此有能够出现原问题和对偶问题均为非可行解的情况。出现这种情况时，需引进入工变量将原问题的解转化为可行解，再用单纯形法求解。5灵敏度分析灵敏度分析第二章例9 在美佳公司的例子中，假设家电II每件需设备A，B和调试工时变为8小时、4小时、1小时，该产品的利润变为3元/件，试重新确定该公司最优消费方案。解：将消费工时变化后的新家电II看作是一种新产品，消费量为x2。2/3148)21,41, 0(322/ 12/ 12/1114

54、82/ 34/ 102/ 14/ 102/154/ 512P5灵敏度分析灵敏度分析第二章因x2已变换为x2 ，故用单纯形算法将x2交换出基变量中的x2 ，并在单纯形表中不再保管x2。Cj213000CBXBbx1x2x2x3x4x50 x315/20011/215/4-15/22x17/2101/201/4-1/21x23/2011/20-1/43/2 j=cj-zj003/20-1/4-1/2Cj23000CBXBbx1x2x3x4x50 x3-90014-242x121001/2-23x2 30101/23 j=cj-zj0001/2-55灵敏度分析灵敏度分析第二章添加人工变量。Cj230

55、00CBXBbx1x2x3x4x50 x3-90014-242x121001/2-23x2 30101/23 j=cj-zj0001/2-5Cj23000-MCBXBbx1x2x3x4x5x6-Mx3900-1-42412x121001/2-203x2 30101/230 j=cj-zj00-M1/2-4M-5+24M0X3+ 4X4 - 24X5= -95灵敏度分析灵敏度分析第二章美佳公司的最优消费方案为每天消费家电I 11/4件，新家电II 15/8件。Cj23000-MCBXBbx1x2x3x4x5x60 x53/800-1/24-1/611/242x111/410-1/121/301/

56、123x2 15/8011/800-1/8 j=cj-zj00-5/24-2/30-M-5/245灵敏度分析灵敏度分析第二章前面例子：产品前面例子：产品A工艺改动，对甲、乙需求变为工艺改动，对甲、乙需求变为2，2。 利润为利润为7，问最优方案如何？，问最优方案如何？先计算先计算 p1= 2 -1 2 = 2 -1 1 2 0 1=7-2*5= -3 放入最优表Cj58600CBXBbx1x2x3x4x55x14100218x2801111 j=cj-zj00223第二章 X1 X1 X2 X1 X1 X2 X3 X4 X5X3 X4 X5 5 X1 4 1 2 5 X1 4 1 2 0 0 2

57、 -10 0 2 -1 8 X2 8 0 0 8 X2 8 0 0 1 1 -1 11 1 -1 1 0 -3 0 -3 0 -2 -2 -30 -2 -2 -3 7 X1 2 1 7 X1 2 1 0 0 1 -1/20 0 1 -1/2 8 X2 8 0 8 X2 8 0 1 1 -1 1 1 1 -1 1 0 0 0 -2 1 -3/20 -2 1 -3/2 0 X4 2 1 0 X4 2 1 0 0 1 -1/2 0 0 1 -1/2 8 X2 10 1 8 X2 10 1 1 1 0 1/2 1 1 0 1/2 -1 -1 0 -2 0 -10 -2 0 -1换入？换出？第二章 X1

58、 X1 X2 X1 X1 X2 X3 X4 X5X3 X4 X5 5 X1 4 1 2 5 X1 4 1 2 0 0 2 -10 0 2 -1 8 X2 8 0 0 8 X2 8 0 0 1 1 -1 11 1 -1 1 0 -3 0 -3 0 -2 -2 -30 -2 -2 -3 7 X1 2 1 7 X1 2 1 0 0 1 -1/20 0 1 -1/2 8 X2 8 0 8 X2 8 0 1 1 -1 1 1 1 -1 1 0 0 0 -2 1 -3/20 -2 1 -3/2 0 X4 2 1 0 X4 2 1 0 0 1 -1/2 0 0 1 -1/2 8 X2 10 1 8 X2 1

59、0 1 1 1 0 1/2 1 1 0 1/2 -1 -1 0 -2 0 -10 -2 0 -1第二章五、添加一个约束条件的分析五、添加一个约束条件的分析 添加一个约束条件在实践问题中相当增添一道工序。从图形二维上分析相当于添加了一条直线。分析的方法是先将原问题最优解的变量值代入新增的约束条件。如满足，阐明新增的约束未起到限制造用，原最优解不变。否那么，将新增的约束直接反映到最终单纯形表中再进步分析。5灵敏度分析灵敏度分析第二章例10 仍以美佳公司为例，设家电I，II经调试后，还需经过道环境实验工序。家电I每件须环境实验3小时，家电II每件2小时，又环境实验工序每天消费才干为12小时试分析添加

60、该工序后的美佳公司最优消费方案。解：先将原问题的最优解x1 =7/2, x2 =3/2代入环境实验工序的约束条件： 3x1 +2 x2 12。由于37/2 + 23/2 12，故原问题最优解不是本例的最优解。5灵敏度分析灵敏度分析第二章在实验工序中参与松驰变量得：3X1+ 2X2 +X6= 12Cj210000CBXBbx1x2x3x4x5x60 x315/20015/4-15/202x17/21001/4-1/201x23/2010-1/43/200 x612320001 j=cj-zj000-1/4-1/205灵敏度分析灵敏度分析第二章Cj210000CBXBbx1x2x3x4x5x60