第四章 对偶规划、灵敏读分析运筹学讲义

1、1第四章第四章 对偶规划、灵敏度分析与应用对偶规划、灵敏度分析与应用 Dual Problem and Sensitivity analysisn1 1单纯型法的矩阵表示单纯型法的矩阵表示n2 2线性规划的对偶问题线性规划的对偶问题n3 3对偶规划的基本性质对偶规划的基本性质n4 4影子价格（对偶价格）影子价格（对偶价格）n5 5对偶单纯形法对偶单纯形法n6 6单纯形表的灵敏度分析单纯形表的灵敏度分析21 1 单纯型法的矩阵表示Max z= CX Max z = CX+0Xs s.t. AXb s.t. AX+IXs =b X0 X0C=(c1, c2,cn ) A= ( p1, p2 , p

2、n )mnmmnnaaaaaaaaa212222111211AmxxxX21mbbb21bmnnnxxx21sx5 , 2 , 102105340010418026.2231max52142132121jxxxxxxxxxxtsxxzj5310426A21xxX210400180b543xxxXs3N B1005301010400126IA 54321),(ppppp5031014206241),(pppB若取基为10000153),(ppN则241xxxXB53xxXN5 , 2 , 102105340010418026.2231max52142132121jxxxxxxxxxxtsxxzj

3、22031C B00CN210400180100001503101420653241xxxxx532410022031xxxxxZ4B-1bB-1B-1b B-1B-1B-1bB-1B-1b - B-1 B-1bB-1B-1b国内书籍国外书籍P385 非基变量基变量右端项系数系数基变量XBXNXsCs=0XsBNIbCBCN00基变量非基变量右端项系数系数基变量XBXNXsCBXBIB-1NB-1B-1b0CN CBB-1NCsCBB-1B-1bjjjzc 迭迭 代代jjjzc 1110jjmiijijjBjjmiiizcaccpBCcbcZ,jjpBp10jjjJzzxbb1Bj =1,n8

4、6bXXZs0IA00C-11 -1 -1B-1B1 -1BB AB0BCABC1IA00C-1B0BC1Basic variable系数右端项 Z原来变量 X松弛变量XSZ1-C00CBXB0AIbanyZ1C CBB-1A CBB-1 ( )B-1bXB0B-1AB-1( S*)B-1bXB= B-1b Z= B-1b21*TY*TY7cj3122000biCBXBx1x2x3x4x50 x3621001800 x44100104000 x535001210-Z31220000最终单纯型表31x1105/2401/12200 x4005/12113/62022x201 1/801/4303

5、1x10089/24035/12128041081613112512102451B22031BC1235024894108161311251210245220311BCB206024110305B8最终表的矩阵计算（矩阵表示） P26表1-6jjpBp125040030041081613112512102453020201bBb41081613112512102451B10051024108161311251210245212pBp2489811252452203103133pBCcB2801302020220311BbBCZ*59以第二章例一为例Max z = 50 x1 + 100 x2

6、Max z = 50 x1 + 100 x2 s.t. x1 + x2 300 s.t. x1 + x2 + s1 300 2 x1 + x2 400 2 x1 + x2 + s2 400 x2 250 x2 + s3 250 x1 , x2 0 x1 , x2 ，s1 ，s2 ， s3 0100100101200111),(54321pppppA12xXx250400300b1s23sXss100112101241),(pppB1B22xXsx如果3N5sXs100050B,C10单纯型法迭代过程表迭代次数基变量 CB x1 x2 s3 s4 s5 b比值ibi/ai2 50 100 0 0

7、 00 s1 s2 s3 0 0 0 1 1 1 0 0 2 1 0 1 0 0 1 0 0 1300400250300/1400/1250/1 zj 0 0 0 0 0 50 100 0 0 0z=0迭代次数基变量 cB x1 x2 s3 s4 s5 b 比值 bi/aij 50 100 0 0 02 x1 s2 x2 50 0 100 1 0 1 0 -1 0 0 -2 1 1 0 1 0 0 1 50 50 250 zj 50 100 50 0 50 0 0 -50 0 -5027500jjjzc jjjzc 55最终单纯形表最终单纯形表初始单纯形表初始单纯形表11最终表的矩阵计算（矩阵

8、表示）jjpBp125040030010011210125050501bbB1001121011B021001100112101313pBp5002110005003133pBCcB2750025050501000501Bb*BCZ122 2 Dual Problem 线性规划的对偶问题线性规划的对偶问题 例例1. 某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位、产品才能使工厂获利最多？线性规划模型：线性规划模型： 目标函数：Max z = 50 x1 + 100 x2 约束条件：s.t. x1

9、+ x2 300 2 x1 + x2 400 x2 250 x1 , x2 0 最优解x1 = 50 ， x2 =250， z =27500 产品产品设备使用成本和单价资源限制设备1110元 / 时300台时原料A2112元 / kg400kg原料B0118元 / kg250kg销售单价(元)84140单位产品利润(元)501005413 现在我们从另一个角度来考虑这个问题。假如有另外一家公司要求租用该厂的设备和购买原料A、B用于生产其他商品，那么该公司和该厂的厂长应该如何来确定合理的租金和原材料A、B的价格呢？ 设y1表示设备每台时的租金。y2和y3 分别为原材料A、B的出卖的价格，公司将3

10、00台时的设备和400kg原材料A和250kg 原材料B全部租购过来所化的成本为：300 y1 400 y2 250 y3 。显然，公司希望租购的成本最低，故目标函数为 ： Min 300 y1 400 y2 250 y3 下面考虑什么情况下，工厂才愿意租售设备和原材料，而不进行生产。对于工厂来说，租金和出卖价格定义为扣除成本后所能产生的利润。作为工厂来说，把生产单位产品所需的1小时设备的台时和2 kg原材料A租售所得收益应不低于生产一件产品所获的利润50元，即 y12 y2 50；把生产单位产品所需的1小时设备台时、1 kg原材料和1kg原材料B租售所得收益应不低于生产一件产品 所获的利润1

11、00元，即 y1 y2 y3 100，这样我们得到了该问题的数学模型 目标函数：Min f = 300 y1 400 y2 250 y3 约束条件：s.t. y12 y2 50 y1 y2 y3 100 y1 , y2 014这样从两个不同的角度来考虑同一个工厂的最大利润的生产计划和租售设备和原材料的销售计划（最小租金）问题，所建立起来的两个线性模型就是一对对偶问题，其中一个叫做原问题原问题，而另外一个叫对偶问题对偶问题 Primal Problem原问题原问题 Dual Problem 对偶问题对偶问题 Max z = 50 x1 + 100 x2 Min f = 300 y1400 y22

12、50 y3 s.t. x1 + x2 300 s.t. y12 y2 50 2 x1 + x2 400 y1 y2 y3 100 x2 250 y1 , y2 , y3 0 x1 , x2 027500 50050321*,fyyy最优解27500 2505021*,zxx16232115如果我们用矩阵形式来表示，则有原问题和对偶问题： （） （） 其中A是 矩阵mn，该问题有m个约束条件n个变量，X(x1, x2, , xn) T, b= (b1, b2, , bm) T , C = (c1, c2, , cn) 其中AT是A的转置， bT是b的转置, CT是C的转置, Y= (y1, y2

13、, , ym) T 。现在我们用单纯形法求对偶问题的解。有时为了证明需要，也写成YTA C, f =YT b0,maxXbAXCXz0Y minYCYAfTTTb19161212121231235 01 0 0113 0 0 214 0 0 012 5 00 03 0 04 0 02 5 01205 0 1111 0 0 m a x. .m in. .xzxxs txxxyfyyys tyyy及T123000yy1417原规划与对偶规划的线性关系原（对偶）规划原（对偶）规划对偶（原）规划对偶（原）规划Objective: 目标目标max zmin fObjectiveVariables变量变量

14、n个个 0 0自由自由n个个 =Constraint约束约束Constraint types: 约束类型约束类型m个个 =m个个 0 0自由自由变量类型变量类型Variables types:资源限制向量资源限制向量 b价值向量价值向量价值向量价值向量 C资源限制向量资源限制向量18nP41 例12 自由变量321321321321, 0,532443.51020minxxxxxxxxxtsxxxf自由变量4141414141,0510342023.54maxyyyyyyyytsyyz令令 Z1 = -f ，x3 = x4 - x5 ，得，得令令Z = -f1 ，y4 = y2 - y3，得，

15、得5 , 4 , 2 , 10532532443.551020max54215421542154211jxxxxxxxxxxxxxtsxxxxzj3 , 2 , 10551033420223.554min3213213213213211iyyyyyyyyyyyyytsyyyfi对应的对偶规划有对应的对偶规划有192 2对偶规划的基本性质对偶规划的基本性质对偶规划的基本性质对偶规划的基本性质n1对称性对称性。即对偶问题的对偶是原问题。n2弱对偶性弱对偶性。即对于原问题()和对偶问题()的可行解 都有 C bT 。 由弱对偶性，可得出以下推论：（1）原问题任一可行解的目标函数值是其对偶问题目标函数

16、值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。（2）如原问题有可行解且目标函数值无界（或具有无解），则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解（注意：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然）。（3）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。YX,XYnjmiiijjbyxcbYXC11 即,其实CX YTA X YTb bTY15YX,X203. 互补解性质互补解性质：每次单纯型迭代过程中，可以得到原问

17、题的一个基可行解和对偶问题的一个互补的解 见 PPT234.最优性最优性。如果 X* 是原问题()的可行解，Y*是对偶问题()的可行解，并且 CX* =bTY* ，则X*和Y*分别为原问题()和对偶问题()的最优解。对偶问题最优解 Y* T=CBB1 (B为最优基),可丛单纯型表中读出或用公式算出。最终单纯型表中Xs对应的检验数去掉负号(Cs=0) 见PPT 7和P50例15证明 由于CX* =bTY* ，而根据弱对偶性，对任意可行解 有问题无界问题无界无可无可行解行解无可无可行解行解问题无界问题无界对偶问题对偶问题原问题原问题关于无界性有关于无界性有如下结论：如下结论：72336YX,*b

18、YTCXCX*b Yb YTTCX215. 强对偶性强对偶性。即若原问题()及其对偶问题()都有可行解，则两者都有最优解；且它们的最优解的目标函数都相等。证明证明 设设X* 是原问题()的最有解，则对于最优基B，有令令 Y* =CBB1 有 ，且 Y*0, Y*满足约束条件 ()最 优值根据最优性得Y*是对偶问题()的最优解610CCBA*CY A1zCXCBY*bbMax z = 50 x1 + 100 x2 Min f = 300 y1400 y2250 y3 s.t. x1 + x2 + x3 300 s.t. y12 y2 y450 2 x1 + x2 + x4 400 y1 y2 y

19、3 y5 100 x2 + x5 250 y1 , y2 , y3 , y4 , y5 01234550050 00 27500*,yyyyyf1243550250500 27500*,xxxxxz226互补松弛性互补松弛性。在线性规划问题的最优解最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为零也即 若yi*0,则有 若 ， 则有yi*=0njijijbxa1*njijijbxa1* xn+i =0 xn+i 0()00() 00 .TTsTTsssYbAXYXYAC XY XXY或或 原问题与对偶问题变量之间

20、的对应关系(互补松弛)原变量对应的对偶变量基变量 (决策)xj非基变量 (剩余) yn+j非基变量(松弛) 基变量(决策)14bTTCXYAXY证明证明 由弱对偶性由强对偶性bTCXY为松弛变量和剩余变量23互补松弛性的应用互补松弛性的应用例题 设线性规划问题为Min f = 2 x13 x2 5x3 2x4 3x5 s.t. x1 + x2 + 2 x3 + x4 + 3 x5 4 2 x1 x2 + 3x3 x4 + x5 3已知其对偶规划的最优解为Y*=(y*1, y*2 )=(4/5, 3/5),试用对偶理论找出原问题的最优解解 对偶问题为Max z = 4y13y2 将Y*=(4/5

21、, 3/5)代入约束条件，得(2),(3),(4)为s.t. y12y2 2 （1） 严格不等式 x*2 x*3 x*4 0 y1y2 3 （2） 因y*10, y*2 0,，故这两个变量对应原问题的 2 y13y2 5 （3） 约束为等式，得 y1y2 2 （4） x*1 + x *2 + 2 x *3 + x *4 + 3 x *5 = 4 3y1y2 3 （5） 2x*1 x *2 + 3x *3 + x *4 + x *5 = 3 y1 ，y2 0 联立得 x*1 + 3 x *5 = 4 2x*1 + x *5 = 3 最优解x*1 = x *5 = 124迭代次数基变量 CB x1

22、 x2 x3 x4 x5 b比值ibi / ai2 50 100 0 0 00 x3 x4 x5 0 0 0 1 1 1 0 0 2 1 0 1 0 0 1 0 0 1300400250300/1400/1250/1 zj 0 0 0 0 0 50 100 0 0 0z = 01 x3 x4 x2 0 0 100 1 0 1 0 -1 2 0 0 1 -1 0 1 0 0 1 50 150 250 50/1150/2 zj 0 100 0 0 100 50 0 0 0 -100250002 x1 x4 x2 50 0 100 1 0 1 0 -1 0 0 -2 1 1 0 1 0 0 1 50

23、 50 250Y* zj 50 100 50 0 50 0 0 -50 0 -5027500S*(B-1)y4 y5 y1 y2 y3 142520253 3 影子价格（对偶价格）影子价格（对偶价格）ly*表示在其它条件不变情况下，z*对第i种资源的变化率，称为第i种资源的影子价格或边际价格影子价格或边际价格，说明在资源最优利用条件下，每增加(减少)一个单位第i种资源，目标函数z*的增加(减少)量。l资源的市场价格是已知的，而影子价格有赖于资源的利用情况，是未知数，是一种边际价格，它随着系统内资源数量bj、技术系数aij和价值系数ci的变化而变化，是动态的l影子价格反映了资源在系统内的稀缺程度

24、。当系统达到最优时，如果某种资源的影子价格yi*0，则资源已完成耗尽，是稀缺资源，原问题对应的约束取等式。如果资源供大于求，原问题对应的约束为严格不等式，则影子价格为0，对偶问题的变量为0。设备和原材料B为稀缺资源，A为非稀缺资源 ;z2211*iiimmTbzyybybybYbCXnjijijbxa1*njijijbxa1*yi*=0yi*026l影子价格实际是一种机会成本，是增加一个单位资源时，系统所能支付的最大成本量，是高于正常成本的量，当市场上设备1小时的租金高于50元时，应该出租设备，否则应该租进设备进行生产，当市场上资源B的价格高于 18(采购价)+50=68元/kg时，应该出售原

25、料B。l一般说，线性规划问题的求解是确定资源的最优分配方案；而对偶问题的求解则是对资源的恰当估价，这种估价直接涉及资源的最有效利用。如在一个大公司内部，可以借助影子价格来确定资源的内部结算价格。对社会上一些最紧缺的资源，通过影子价格确定资源使用需上缴利润23274 4 The dual simplex method对偶单纯形法对偶单纯形法n对偶单纯型法的思路 单纯型法的迭代过程：在始终保持原问题解可行的条件下(bj0) ，将对偶问题的解由不可行(0)向可行解转化，一旦其对偶问题解可行时 (0)，原问题解为最优解。 对偶单纯行法的思路：在始终保持对偶问题解可行的条件下(0 ) ，将原问题的解由不

26、可行(bj 0)向可行解转化，一旦原问题解可行时 (bj 0 )，则其解达到最优解。n正则解：检验数均非正(0 ) 所对应的基解X称为正则解n对偶单纯形法的计算步骤如下： 1. 设有初始正则解X(0) = (XB (0), XN (0) )T = (b1, , bm ,0, ,0)T 2. 若XB (0),0，则X(0) = X*最优，否则，转Step 3。 3. 由 确定r行上的基变量x Br为出基变量。0maxiiirbbb28nStep 4. 若ar j 0 (j = 1, 2, , n)，则无最优解；否则，由 确定x k为入基变量。nStep 5. 作旋转运算，以x k取代x Br ，

27、得新正则解，转Step 2。简化计算是对偶单纯形法的优点，对于一些形式为的约束不等式，可以化成不等式在加松弛变量。但是它在使用上有很大的局限，这主要是大多数线性规划问题很难找到初始解为正则解。但是在灵敏度分析中，有时需要对偶单纯形法，这样可以简化处理rkkrjrjjjaaa0min29例14 Max z = x13 x2 Max z = x13 x2 s.t. 2x1 x2 3 s.t. 2x1 x2 x3 3 3x12x2 4 3x1 2x2 x4 4 x1 2x2 1 x1 2x2 x5 1 x1 , x2 , 0 x1 , , x5 013000bCBXB x1x2x3x4x50 x32

28、110030 x43201040 x5120011z130000 X (0)(0, 0, 3, 4, 1)T为正则解, x4为出基变量3 ,2, 10322 132 .43max321321321jyyyyyyytsyyyzj0 ,0 12 423 32 .3min2121212121xxxxxxxxtsxxf对偶问题30 x1为入基变量, 3为主元211312331a,min13000bCBXB x1 x2x3x4x50 x32110030 x43201040 x5120011z1300000 x3 01/31 2/301/31x1 12/30 1/304/30 x5 04/30 1/311

29、/3z 07/30 1/304/30 x4 01/23/2101/21x1 11/21/2003/20 x5 03/21/2011/2z 05/21/2003/2最优解最优解 X *(3/2, 0, 0, 1/2, 1/2,) Z * = 3/2 f * = 3/2,31例：Max z = 50 x1 + 100 x2 = 30000 5 0 x3 5 0 x5 s.t. x1 +x3 x5 100 2x3 + x4 + x5 50 x2 + x5 250 x1 , x2 , x3, x4 , x5 01.写出单纯型表，确定出基变量，在常数列中找一个最小的负常量，把这个常量所在行对应放的基变量

30、作为出基变量迭代次数基变量CBx1 x2 x3 x4 x5b 50 100 0 0 02 x150 1 0 1 0 - 1100 x4 0 0 0 -2 1 1-50 x2100 0 1 0 0 1250 zj 50 100 50 0 5030000cj - zj0 0 -50 0 -5051322. 确定出基变量：b2= 50，故x4为出基变量。3. 确定入基变量：第二行只有a23=2, 故x3为入基变量，迭代得：迭代次数基变量CBx1 x2 x3 x4 x5b 50 100 0 0 02 x150 1 0 1 0 - 1100 x4 0 0 0 -2 1 1-50 x2100 0 1 0

31、0 1250 zj 50 100 50 0 5030000cj - zj0 0 -50 0 -503 x150 1 0 0 1/2 - 1/2 75 x3 0 0 0 1 -1/2 -1/2 25 x2100 0 1 0 0 1250 zj 50 100 0 25 7528750cj - zj0 0 0 -25 -75最优解为：x1=75, x2=250, x3=25, x4=0, x5=0，优值：z*=28750335 5 单纯形表的灵敏度分析单纯形表的灵敏度分析l线性规划的灵敏度分析；在线性规划求出最优解后，研究线性规划的系数ci，aij, bj变化对最优解产生什么影响。它包括两个方面 （

32、1）模型中这些数据在什么范围内变化时，最优解不变？ （2）当最优解发生变化时，最优解和最优值如何变化，如何求出新的最优解？l灵敏度分析是非常重要的：线性规划的参数ci，aij, bj都是估计值和预测值，不一定非常精确；其次这些参数会随着市场的变化而变化，有了灵敏度分析，不必随着参数的变化而不断求解，也可以判断参数变化是否会影响到最有解。34每次迭代为单纯形表的恰当形式：每次迭代为单纯形表的恰当形式：基变量非基变量右端项系数系数基变量XBXNXsCBXBIB-1NB-1 (S*)B-1b0CN CBB-1N(Cs)CBB-1 (Y *T)B-1b设问题为：Max z = CX s.t. AX=b

33、 X 0111*1 , z*bbmkkBkkBkkiikiBBcC BpcC pcc aXBC BY *T CB B 1 CB S*jjpBp1对于最优解时：对于最优解时：1*10, Y0*bTBBXBC BCN CBB1N035当系数ci，aij, bj (C, A, b)发生变化时，导致单纯形表发生改变的情况c1c2cncn+1cn+mbCBXBx1x2xnxn+1xn+mcB1xB1A*= B-1 A(B-1p1,B-1p2, ,B-1pn )(p*1, p*2, , p*n )B-1 NB-1 bcB2xB2cBmxBmz CBB-1 ( Y * T)CBB-1 b111*1 , z*

34、bbmkkBkkBkkiikiBBcC B pcC pcc aXBC BABCCBn11),(36一.非基变量系数的变化 1. cj 变化， xj 为非基变量只有只有xj 的检验数发生变化，其他数都不变化计算得：，如果jjjBjjjjjcpccc*Cz0jjc则原最优解不变，否则，将xj 作为入基变量用单纯形法求新的最优解。P 50例例15 已知线性规划已知线性规划jjjjcccc6311cc，试作灵敏度分析）将（，试作灵敏度分析即设12221 2112 (1)44444ccccc,6210 1 2921232346542143215432,.maxjxxxxxxxxxxtsxxxxzj的初始

35、单纯形表与最终单纯形表（表1-22见PPT35）。注意 c3 =3042452037解（1） 最优解不变 （2） 用单纯型法继续求解 表表1-22cj04-3-210bCBXBx1x2x3x4x5x6-3x33/21/211009/20 x6-110-1111初始-z9/211/2011027/20 x1101/23/4-1/4-1/424x2011/2-1/43/43/43最终-z00-5-1-2-3-12新检验数新检验数-z00-52-2-3-121x44/302/31-1/3-1/38/34x21/312/302/32/311/3-z-8/30-19/30-4/3-7/3-52/3021

36、21144*4c023144*4c得新最优解与新最优值为X* = (0, 11/3, 0, 8/3, 0, 0)T，z* = 52/3。434938n2. xj 对应整个一列系数 cj , a1j, a2j, , amj的变化.mjjjmjjjaapaap111jB-z-Y*Tjjjjjcc C Bpcpjjjjcccc用公式求出新的检验系数jjpBp1*代入最终单纯型表, 判断最优解是否变化, 如果最优解变化，用单纯型法求新的最优解例16 设线性规划为 Max z = 3 x1 + 5 x2 s.t. x1 4 2 x2 24 3x1 + 2 x2 18 x1 , x2 0最终单纯型表为35

37、000bCBXBx1x2x3x4x50 x31010045x23/21001/290 x4 3001 16 Z 9/2000 5/2 4512132412535 =4 2 2432 1801 25max., ,jzxxxxxxs txxxxj4039n(1)如果20130111pp4311cc试进行灵敏度分析解11111111001zY4050001 2001121540001022*TBccC B pcp 原最优解 (x1, x2, x3, x4, x5,)T = (0, 9, 4, 6, 0)T 不变(2)如果6311cc20130111pp1115zY60001022*Tjjccp 21

38、120111021000012011*Sp则代入单纯型表用单纯型法求最优解4065000CBXBx1x2x3x4x5b0 x31010045x211001/290 x42001 -16 Z1000 5/2 456x11010045x201101/250 x40021 -114 Z00 10 5/2 49得新最优解与新最优值为X* = (4, 5, 0, 14, 0)T，z* = 49。413. 引进一个新变量引进一个新变量处理方法与非基变量的系数变化相同，非基变量对应系数发生变化处理方法与非基变量的系数变化相同，非基变量对应系数发生变化,0假定在线性规划问题中增加一个变量xk, 相应的价值系数

39、为ck , 12kkkmkaapa列向量为同样利用公式：1kBzY*TkkkkkccC Bpcp1*kkpBp计算变量xk对应的检验数 和列向量kzkkc1*kkpBp在最终单纯形增加变量xk所对应一列，然后判断最优解是否发生变化。当 时，原最优解加上xk 0为新最优解，当 时，以xk为入基变量，用单纯形法求新的最优解。例17 在例16中，增加一个新变量x6，(1)如果c6 2, 0k0k6121p 试进行灵敏度分析,(2)如果c6 3， p6不变，试进行灵敏度分析。3742解 (1) c6 2 666615z2Y200221512022*Tcp 6121p 计算 新最优值为X* = (0,

40、9, 4, 6, 0, 0)T，z* = 45。(2) 当c6 3 时66651z3022c350003bCBXBx1x2x3x4x5x60 x310100145x23/21001/21/290 x4 3001 116 Z 9/2000 5/21/2 45x61010014x211 1/201/207x440 11 10250 1/20 5/20 47610011001 221 201111*p 新最优值为X* = (0, 7, 0, 0, 0, 0, 4)T，z* = 47。43二. 基变量系数的变化 1. cj 变化， xj 为基变量用公式计算所有非基变量的检验数我们可以采用以下方法求解，

41、先求出： 代入最终单纯型得到修订的单纯型表，然后将修订的单纯型表转化成适当的(proper form)形式，再判断最优解的变化情况。例例17 在例在例15中中 P51(1) ，作灵敏度分析； (2) 问：c1在何范围内变化，原最优解不变，最优值又如何？jjjjcccc1BBz*kkkkkkkccC B pcC pBBCC 若所有非基变量的检验数 0，则最优解不变，否则需要继续用单纯形法求新的最优解k*1*B*TjjjjjjcC B pcYpc9011cc3544解 求出非基变量新的检验数cj94 3 21CBXBx1x2x3x4x5x6b9x1101/23/4-1/4-1/424x2011/2

42、-1/43/43/43zj9413/223/43/43/430cj zj0019/231/41/4 1 309x111/32/32/30031x504/32/31/3114cj zj01/329/323/30 131CBXBx1x2x3x4x5x6b9x1101/23/4-1/4-1/424x2011/2-1/43/43/43修订 z90-5-1-2-3-12恰当 z0019/231/41/4 1309123329123432141-21)40(911B11*pBCc讲解P52韩伯棠书3645(2) c1 的取值范围CBXBx1x2x3x4x5x6bx1101/23/4-1/4-1/424x2

43、011/2-1/43/43/43z0-5-1-2-3- 1200-5-1/2c1-1-3/4c1-2+1/4c1-3+1/4c1-12-2c11c1c5 1/2c10； 13/4c1 0；2+1/4c1 0；3+1/4c1 0 4/3 c1 8当4/3 c1 8时，最优解不变，最优值 28/3122c1 28最优值为X* = (3, 0, 0, 0, 4, 0)T，z* = 3146n2. 当基变量xj 对应整个一列系数 cj , a1j, a2j, , amj的变化.mjjjmjjjaapaap111jB-z-Y*Tjjjjjcc C B pcpjjjjcccc用公式求出新的系数代入最终单纯

44、型表后,将修订表转化成恰当恰当的形式，然后判断最优性和可行性，如果不满足，可以用单纯型法和对偶单纯型法求解。如果原问题和对偶问题均不可行，则可以引入人工变量将原问题的解转化成可行解后继续求解例18在例在例15中中 假定假定 (1)jjpBp1*1011cc214112311pp进行灵敏度分析; (2) 当2011cc进行灵敏度分析1011cc214112311pp1011cc214112311pp3547解代入单纯型表转化成恰当的形式为：41412141432141-21*1p1011cc214112311pp221413212141432141-21)40(111B1*111*pBCczcC

45、BXBx1x2x3x4x5x6b1x11/401/23/41/41/424x21/411/21/43/43/43 z20512312转化成恰当的形式1x110231184x20111/21/21/25 z009701 28 得新最优解为X* = (8, 5, 0, 0, 0,0)T，z* = 28。多最有解48(2) 当1102cc214112311pp321413212141432141-21) 40(2*111*zcCBXBx1x2x3x4x5x6b2x11/401/23/41/41/424x21/411/21/43/43/43 z 30512312转化成恰当的形式2x110231184x

46、20111/21/21/25 z0011101036x112440018x502211110 z0213110146得新最优解为X* = (18, 0, 0, 0, 10,0)T，z* = 46。多最有解49三、约束方程中常数项bj的灵敏度分析当bk 变成 bkbk时， b变为 bb时，时， XB=B-1b 变为 X*B=B-1 ，检验向量(所有检验数)不变，X*B为正则解。要使X*B为最优解，只需要使X *B=B-1 0即可：由此可以确定bk的取值范围。列系数第为kSaaaxbaaxk ik ik iBiikk ik iBi*i ,0Min0Max0011.b.bkmkmkbbbbbbb00

47、011mkkkkkkkBkmkabababXbSbbbSS.bb*bb通常通过直接计算X *B来判断最有解是否发生变化kbb5350例19 (书中P53的例17) 在例15中(1) 当b19/2变为 1时，作灵敏度分析；(2) 当b19/2变为 1/4时，作灵敏度分析；(3) 问：b1在何范围内变化，原最优解中基变量的组成不变？4/32/14/12/11B11 21 411 41 23 415 4B /b/【解】 由最终单纯形表得(1) 故最优解中基变量的组成不变，得X* = (1/4, 5/4, 0, 0, 0, 0)T，z* = 511 21 41 41 81 23 417 8/b/B 因

48、b1* = -1/8 0，故须用对偶单纯形法继续求解：(2)1b1b3651CBXBx1x2x3x4x5x6b0 x1101/23/4-1/4-1/4-1/84x2011/2-1/43/43/47/8z00-5-1-2-3-7/21x5-40-2-3111/24x23122001/2 z-80-9-70-1-5/2得新最优解与新最优值为X* = (0, 1/2, 0, 0, 1/2, 0) T，z* = 5/2。 1111229 21 21 41 23 4132/b/bbBb 02/302/211bb(3) 给b1以增量b1 ，即 = 9/2 +b1 ， 故当b11/2时，原最优解中基变量的组

49、成不变。得 b1 -4 1b52例，第二章例1中b1300 350时，进行灵敏度分析解： b1 5025050100250400350100112101bX*241B*Sxxx有用对偶单纯型法进行求解，见PPT301b100112101*S见 PPT103053下面我们仍以第二章例1在最终单纯形表上对bj 进行灵敏度分析。最终单纯形表如下所示：迭代次数基变量CBx1 x2 x3 x4 x5b50 100 0 0 02x150 1 0 1 0 -150 x40 0 0 -2 1 150 x2100 0 1 0 0 1250 zj 50 100 50 0 50 27500cj zj 0 0 -50

50、 0 -50为使最优基不变，求b1 的取值范围2505050X ,0211100112101BB1 -列为第，根据单纯型表得54，最优基不变。即故有当而因为32525300bb5030025025b50250Min500Max5050, 02011111111212111,|,iiBiiiBiaaxaaxsxaa即第一约束条件对偶价格不变。实际意义可以描述为：当设备台时数在250与325之间变化，则设备台时数的对偶价格不变，都为每台设备台时50元。通常我们可以直接计算 X*BB-1bbkPk，令其大于0来确定bk的取值范围。025025050250400300100112101X111B*bb

51、bS b*解得：325250255011bb4855四、增加一个约束条件的灵敏度分析 在原线性规划中增加一个约束条件时,先将原问题的最优解的变量值代入新增的约束条件，如满足则说明新增的条件没有起到限制作用，故原最优解不变，否则将新增的约束添入原最终单纯形表上进一步求解。这时增加一个新的(松弛、剩余或人工)变量xn+1，将单纯型表化为恰当形式，即原基向量列化为单位列向量，基变量的检验数化为0。 下面仍以第三章例1为例来加以说明。 例：假如该工厂除了在设备台时，原材料A、B上对该厂的生产有限制外，还有电力供应上的限制。最高供应电量为5000度，而生产一个产品需要用电10度，而生产一个产品需要用电3

52、0度。试分析此时该厂获得最大利润的生产计划？1256新的用电量约束为： 10 x1 + 30 x2 5000将原最优解x1=50，x2=250代入，不满足约束在用电量约束条件中加入松弛变量s4得： 10 x1 + 30 x2 + x6 =5000代入单纯型表，化为恰当形式后为正则解，用对偶单纯型法求解迭代次数基变量CBx1 x2 x3 x4 x5 x6b50 100 0 0 0 0 x150 1 0 1 0 -1 050 x40 0 0 -2 1 1 0 50 x2100 0 1 0 0 1 0250 x6010 30 0 0 0 1 5000cj zj0 0 -50 0 -50 0恰当形式x

53、150 1 0 1 0 -1 050 x40 0 0 -2 1 1 0 50 x2100 0 1 0 0 1 0250 x60 0 0 -10 0 -20 1-3000zj50 100 50 0 50 027500cj zj0 0 -50 0 -50 01057迭代次数基变量CBx1 x2 x3 x4 x5 x6b50 100 0 0 0 0 x150 1 0 3/2 0 0 -1/20 200 x40 0 0 -5/2 1 0 1/20-100 x2100 0 1 -1/2 0 0 1/20100 x50 0 0 1/2 0 1 -1/20 150zj50 100 25 0 0 5/2200

54、00cj zj0 0 -25 0 0 -5/2x150 1 0 0 3/5 0 1/50140 x30 0 0 1 -2/5 0 -1/50 40 x2100 0 1 0 -1/5 0 2/50120 x50 0 0 0 1/5 1 -3/50130zj50 100 0 10 0 319000cj zj0 0 0 -10 0 -3最优解： x1=140, x2= 120, x3=40, x5=130, x4=x6=0， 最优值：z*=19000元 58灵敏度分析总结n一.非基变量xj系数的变化mjjjmjjjaapaap11jjjjjpcpBCcc*Y-z-1Bjjjjjcccc用公式求出新的

55、系数jjpBp1*代入最终单纯型表, 判断最优解是否变化, 如果最优解变化，用单纯型法求新的最优解如果只是cj 变化 ， 为上述情况的特例，只需计算n二. 基变量xj系数的变化jjjjccccjjjBjjjjjcpccc*Cz0jjc判断是否有59n二二. . 基变量基变量xj系数的变化系数的变化mjjjmjjjaapaap11jjjjjpcpBCcc*Y-z-1Bjjjjjcccc用公式求出新的检验数和列向量用公式求出新的检验数和列向量代入最终单纯型表后代入最终单纯型表后,将修订的表转化成将修订的表转化成恰当恰当的形式，然后的形式，然后 判断最优性和判断最优性和可行性，如果不满足，可以用单纯

56、型法和对偶单纯型法求解。可行性，如果不满足，可以用单纯型法和对偶单纯型法求解。jjpBp1*n三三. .常数项bj的灵敏度分析601. 下表为用单纯形计算时某一步的表格，已知该线性规划的目标函数为Max z =5 x13 x2 ， 约束形式为， x3、 x4为松弛变量，表中解代入目标函数后得 z =10。XBx1x2x3x4b右端项x3c011/52x1de01acjzjb1fg(1) 求a g的值；(2) 判断表中给出的解是否为最优解？补充练习61cj2-11000bCBXBx1x2x3x4x5x60 x4311100600 x51-12010100 x611-100120cj zj2-11

57、0000最终单纯型表0 x41-1-22x101/21/2-1x20- 1/21/2cj zj2. 已知线性规划问题用单纯形法计算时得到的初始单纯形表及最终单纯形表如下，请将表中空格数字填上623. 已知线性规划问题 max z = 2x1 3 x2 x3 ； s.t . 1/3x1 1/3x2 1/3x3 1， 1/3 x14/3x2 7/3x3 3， x1, x2 , x3 0 cj23100bCBXBx1x2x3x4x52x11014 113x2012 1 12cj zj00 3 5 1试对下列变化进行灵敏度分析(1)目标函数变为 max z = 2x1 3 x2 6x3 ；（2）求c1

58、的变化范围，使原最优解不变(3) 约束条件右端项由(4 ) 增加一个新的变量x6，其系数为c6 = 7，(5) 增加一个新的约束 x1 2 x2 3x3 414bb32 用单纯形法求解得最终单纯形表为611p 63Wyndor Case Study 伟恩德公司案例研究伟恩德公司案例研究what-if 分析之前，最初伟恩德公司问题电子表格模分析之前，最初伟恩德公司问题电子表格模型及最优解型及最优解实际举例实际举例64修正的伟恩德例子，门的单位利润修正的伟恩德例子，门的单位利润P PD D=$300=$300降到降到P PD D=$200=$200和和增加到增加到PD=$500=$500，最优解不

59、变最优解不变 伟恩德公司案例研究，单位利润变化的灵敏读分伟恩德公司案例研究，单位利润变化的灵敏读分析析65修正的伟恩德例子，门的单位利润从修正的伟恩德例子，门的单位利润从PD=$300增加增加到到PD=$1000，最优解改变，最优解改变 实际举例实际举例Wyndor Case Study 伟恩德公司案例研究伟恩德公司案例研究66用解的表格进行灵敏读分析用解的表格进行灵敏读分析 Using Solver Table to do Sensitivity Analysis345678910111213141516171819202122232425262728BCDEFGDoorsWindowsUn

60、it Profit$300$500HoursHoursUsedAvailablePlant 1102=4Plant 20212=12Plant 33218=18DoorsWindowsTotal ProfitUnits Produced26$3,600Unit ProfitTotalfor DoorsDoorsWindowsProfit26$3,600$100$200$300$400$500$600$700$800$900$1,000Hours Used Per Unit ProducedOptimal Units ProducedSelect these cells (B18:E28), b