运筹学课件对偶理论及灵敏度分析

1、1p对偶的定义p对偶问题的性质p原始对偶关系n目标函数值之间的关系n最优解之间的互补松弛关系p对偶单纯形法p对偶的经济解释p灵敏度分析dual 2一、对偶问题的提出 现有甲乙两种原材料生产a1，a2两种产品，所需的原料，甲乙两种原料的可供量，以及生产a1,a2两种产品可得的单位利润见表。问如何安排生产资源使得总利润最大？a1a2原料甲3224乙4540利润4.553a1a2原料甲3224乙4540利润4.55解:设生产a1为x1单位，生产a2为x2单位,则线性规划问题为：maxz=4.5x1+5x2 s.t. 3x1+2x224 4x1+5x240 x1,x20解：设甲资源的出让单价为y1,乙

2、资源的出让单价为y2minw=24y1+40y2 s.t. 3y1+4y24.5 2y1+5y25 y1,y20 另一方面，假设另一公司想把资源买过来，它至少应付出多大代价才能使原来公司放弃生产，出让资源？4a1a2原料甲3224乙4540利润4.55解：设生产a1为x1件，生产a2为x2件，则线性规划问题为：maxz=4.5x1+5x2 s.t. 3x1+2x224 4x1+5x240 x1,x20解：设甲资源的出让价格为y1,乙资源的出让价格为y2minw=24y1+40y2 s.t. 3y1+4y24.5 2y1+5y25 y1,y20 另一方面，假设另一公司想把资源买过来，它至少应付出

3、多大代价才能使原来公司放弃生产，出让资源？5a1a2原料甲3224乙4540利润4.55解：设生产a1为x1件，生产a2为x2件，则线性规划问题为：maxz=4.5x1+5x2 s.t. 3x1+2x224 4x1+5x240 x1,x20解：设甲资源的出让价格为y1,乙资源的出让价格为y2minw=24y1+40y2 s.t. 3y1+4y24.5 2y1+5y25 y1,y20 另一方面，假设另一公司想把资源买过来，它至少应付出多大代价才能使原来公司放弃生产，出让资源？3 24 53 42 5定义：变量均为非负约束的情况下，约束条件在目标函数取极大值时均取“”号；当目标函数求极小值时均取“

4、”号，称此线性规划问题具有对称形式max z=c1x1+c2x2+cnxns.t. a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1, x2, , xn 0min w=b1y1+b2y2+bmyms.t. a11y1+a21y2+am1ym c1 a12y1+a22y2+am2ym c2 a1ny1+a2ny2+amnym cn y1, y2, , ym 0max z=cx s.t. axb x0min w=bty s.t. atyct y0原始问题max z=cxs.t. axb x 0对偶问题min w=bt

5、ys.t. atycty 0maxbacctatbtminmnmnmaxz=3x1+2x2 s.t. -x1+2x24 3x1+2x214 x1-x2 3 x1,x20minw=4y1+14y2+3y3 s.t. -y1+3y2+y33 2y1+2x2-y32 y1,y2,y30y1y2y3第一种资源第二种资源第三种资源第一种产品 第二种产品x1x2举例举例原问题：maxz=x1+4x2+2x3 s.t. 5x1-x2+2x38 x1+3x2-3x35 x1,x2,x30对偶问题：minw=8y1+5y2 s.t. 5y1+y21 -y1+3y24 2y1-3y2 2 y1,y20练习原始问题

6、max z=cxs.t. axb x 0对偶问题min w=ytbs.t. atycty 0令w=-wmax w=-ytbs.t. -aty-cty 0对偶min z=-cxs.t. -ax-bx 0令令z=-z对偶问题的对偶就是原始问题。两个问题中的任一个对偶问题的对偶就是原始问题。两个问题中的任一个都可以作为原始问题，另一个就是它的对偶问题。都可以作为原始问题，另一个就是它的对偶问题。11对偶问题的对偶max z=6x1+9x2s.t. x1+2x22 2x1- 3x23 x1+2x2-1 x1, x20minw=2y1+3y2-y3s.t. y1+2y2+y36 2y1-3y2+2y39

7、 y1, y2, y30根据定义写出对偶问题根据定义写出对偶问题max u=6w1+9w2s.t. w1+2w22 2w1- 3w23 w1+2w2-1 w1, w20minz=2x1+3x2-5x3+x4 s.t. x1+x2-3x3+x45 2x1 +2x3-x44 x2+x3+x4=6 x10,x2,x30 x2+x3+x46x2+x3+x46-x1=x1,x10;x4-x4”=x4,x4 0,x4” 0minz=-2x1+3x2-5x3+(x4-x4”) s.t.-x1+x2-3x3+(x4-x4”)5 2x1 -2x3+(x4-x4”)-4 x2+x3 +(x4-x4”) 6 -x2

8、-x3-(x4-x4”) -6 x1,x2,x3 ,x4,x4” 0变为对称形式y1y2y3y3”maxw=5y1-4y2+6(y3-y3”) s.t.-y1+2y2 -2 y1 +(y3-y3”) 3 -3y1-2y2 +(y3-y3”) -5 y1+y2+(y3-y3”) 1 -y1-y2-(y3-y3”) -1 y1,y2 ,y3,y3”0对偶问题三、非对称形式的原对偶问题引例引例13maxw=5y1-4y2+6(y3-y3”) s.t.-y1+2y2 -2 y1 +(y3-y3”) 3 -3y1-2y2 +(y3-y3”) -5 y1+y2+(y3-y3”) 1 -y1-y2-(y3-

9、y3”) -1 y1,y2 ,y3,y3”0设y2=-y2,y3=y3-y3”,则y20,y3无约束此时对偶问题变为maxw=5y1+4y2+6y3 s.t. y1+2y2 2 y1 +y3 3 -3y1+2y2+y3 -5 y1 -y2 +y3 = 1 y10 ,y20,y3无约束14maxw=5y1+4y2+6y3 s.t. y1+2y2 2 y1 +y3 3 -3y1+2y2+y3 -5 y1 -y2 +y3 = 1 y10 ,y20,y3无约束minz=2x1+3x2-5x3+x4 s.t. x1+x2-3x3+x45 2x1 +2x3-x4 4 x2+x3+x4 = 6 x10,x2

10、,x30m i nm i nfree 原原问问题题变变量量m axm ax = = 对对偶偶问问题题约约束束原问题原问题对偶问题对偶问题 = = 约约束束free 变变量量比较后得出什么结论比较后得出什么结论？min z= 2x1+4x2-x3s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15max w=6y1+12y2+8y3+15y4s.t. 3y1- y2+2y3+ y4 2 -y1+2y2+ y3+3y4 4 2y1- 3y2+2y3- y4 -1 y1 0,y2 ,y3 0,y4 0=free=x10 x20 x3:

11、 freep原始问题变量的个数(3)等于对偶问题约束条件的个数(3)；p原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。p原始问题变量的性质影响对偶问题约束条件的性质。p原始问题约束条件的性质影响对偶问题变量的性质。写对偶问题的练习（1）原始问题max z=2x1-x2+3x3-2x4s.t. x1 +3x2 - 2x3 + x412 -2x1 + x2 -3x48 3x1 - 4x2 +5x3 - x4 = 15 x10, x2:free, x30, x40min w=12y1+8y2+15y3s.t. y1 2y2 + 3y32 3y1 + y2 4y3=-1 -2y1 +5y3

12、3 y1 3y2 - y3-2 y10,y20, y3:free对偶问题写对偶问题的练习（2）17m axm axfree 原原问问题题变变量量m i nm i n = = 对对偶偶问问题题约约束束 = = 约约束束free 变变量量maxz=x1-2x2+3x3 s.t. 2x1+4x2+3x3100 3x1-2x2+6x3200 5x1+3x2+4x3=150 x1, x30练习minw=100y1+200y2+150y3 s.t. 2y1+3y2+5y31 4y1-2y2+3y3= -2 3y1+6y2+4y33 y10,y20minz=2x1+2x2+4x3 s.t. x1+3x2+4

13、x32 2x1+ x2+3x33 x1+4x2+3x3=5 x1 0, x20maxw=2y1+3y2+5y3 s.t. y1+2y2+ y32 3y1+ y2+4y3 2 4y1+3y2+3y3=4 y10,y20对偶问题对偶问题 原问题 max z=cx axb x0其中x(x1,x2xn)tmax z=cx+0xs ax+ixs=b x, xs0其中xs(xn+1,xn+2xn+m)ti 为mm的单位矩阵 2.2 对偶问题的基本性质一、单纯性法计算的矩阵描述其初始单纯性表及经过若干次迭代后的单纯性其初始单纯性表及经过若干次迭代后的单纯性表如下：表如下：20非基变量基变量xbxnxs0xs

14、bbnicj-zjcbcn0 基变量非基变量xbxnxscbxbb-1 bib-1nb-1cj-zj0cn-cbb-1n-cbb-1(1)初始单纯形表中的单位矩阵i，迭代后的单纯形表中为b-1；(2)初始单纯形表中基变量xs=b，迭代后的表中为xb=b-1b；(3)约束矩阵（a，i）（b，n，i），迭代后为 （b-1b，b-1n，b-1i）（i，b-1n，b-1)；(4)初始单纯形表中xj的系数向量为pj，迭代后为pj，且pj=b-1pj。21非基变量基变量xbxnxs0xsbbnicj-zjcbcn0 基变量非基变量xbxnxscbxbb-1 bib-1nb-1cj-zj0cn-cbb-1n

15、-cbb-1111111111111()()bnsbnsbbnnbnbnbsbxnxixbxbbbnxbxzc xc xzc bbcc bn xc bx-+=+=-=-= =+-=+-由由得得: :, ,代代入入目目标标函函数数+ +得得: :(5)当b为最优基，xb为最优解时，则有：cn-cbb-1n0 -cbb-10cb-cbi=0ccbb-1 a0 -cbb-10令ytcbb-1，称 cbb-1为单纯形乘子则：cyt a0 -yt0 atyct y 0y为对偶问题的可行解且wytb=cbb-1b=z结论：结论：当原问题为最优解时，y为对偶问题为可行解且具有相同的目标函数值。maxz=4.

16、5x1+5x2 s.t. 3x1+2x224 4x1+5x240 x1,x20minw=24y1+40y2 s.t. 3y1+4y24.5 2y1+5x25 y1,y20y1y2x1x2maxz=4.5x1+5x2 s.t. 3x1+2x2+x3=24 4x1+5x2+x4=40 x1,x2,x3,x4,0minw=24y1+40y2 s.t. 3y1+4y2-y3=4.5 2y1+5x2-y4=5 y1,y2,y3,y40例题24cj4.5500cbxbbx1x2x3x44.5x140/7105/7-2/75x224/701-4/73/7cj-zj00-5/14-6/7cj244000cby

17、bby1y2y3y424y15/1410-5/74/740y26/7012/7-3/7cj-zj0040/724/7(x3,x4)=(0,0)(y3,y4)=(0,0)-y1-y2-y4-y3x1x2x4x325maxz=4.5x1+5x2 s.t. 3x1+2x224 4x1+5x240 x1,x20minw=24y1+40y2 s.t. 3y1+4y24.5 2y1+5x25 y1,y20y1y2x1x2maxz=4.5x1+5x2 s.t. 3x1+2x2+x3=24 4x1+5x2+x4=40 x1,x2,x3,x4,0minw=24y1+40y2 s.t. 3y1+4y2-y3=4.

18、5 2y1+5x2-y4=5 y1,y2,y3,y40y1y2x1x2例题原始问题max z=cxs.t. axb x 0对偶问题min w=ytbs.t. atycty 0二、对偶问题的基本性质ybxcyxt题的可行解，则分别是原问题和对偶问和设二、对偶问题的基本性质1.1.弱对偶性弱对偶性ybbyxayxayxccyabxayxtttttt)()(,故所以题的可行解分别是原问题和对偶问和证：因为l原问题任一可行解的目标函数是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数是其原问题目标函数的上界。l如原问题有可行解且目标函数值无界，则其对偶问题无可行解；反之对偶问题有可行解且目

19、标函数无界，则原问题无可行解。（对偶问题无可行解时，其原问题无界解或无可行解。l若原问题有可行解而其对偶问题无可行解时，原问题目标函数无界。l若对偶问题有可行解而其原问题无可行解时，对偶问题目标函数无界。推论：tcxb y q q2.最优性 *, ,ttttttttttxycxcxb yb ycxb ycxb ycxb yb ycxb ycxcxb ycxcxb yb y常常=吵=吵=证证：设设, ,分分别别为为原原问问题题和和对对偶偶问问题题的的最最优优解解，则则又又 ，所所以以 故故 题的最优解。分别是原问题和对偶问和则题的可行解，且分别是原问题和对偶问和若yxybxcyxt, 若原问题和

20、对偶问题均具有可行解，则二者均具若原问题和对偶问题均具有可行解，则二者均具有最优解，且它们的最优解的目标值相等。有最优解，且它们的最优解的目标值相等。3.强对偶性（对偶性定理）证：由于二者均有可行解，所以原问题的目标证：由于二者均有可行解，所以原问题的目标函数值具有上界，对偶问题的目标函数值具有函数值具有上界，对偶问题的目标函数值具有下界，因此二者均具有最优解。下界，因此二者均具有最优解。 当原问题有最优解时当原问题有最优解时, ,对偶问题的解对偶问题的解y=cbb-1为可行解为可行解, ,且且 z=cbb-1b=w, ,由最优性知由最优性知, ,二者的二者的解均为最优解。解均为最优解。 在线

21、性规划问题的最优解中，如果对应某一约束条件的在线性规划问题的最优解中，如果对应某一约束条件的对偶对偶变量变量值为非值为非0，则该，则该约束条件约束条件取严格等式；反之如果取严格等式；反之如果约束条件约束条件取严格不等式取严格不等式，则，则 对应的对应的对偶变量对偶变量值为值为0。若yi 0,则aijxj，=bi，即xsi=0若aijxj，bi ，即xsi0 则 yi 0同理若xj 0, 则aijyi，=cj若aijyi ， cj，则 xj 0.4.互补松弛定理maxz=4.5x1+5x2 s.t. 3x1+2x2+x3=24 4x1+5x2+x4=40 x1,x2,x3,x4,0 y1=14/

22、50 y2=6/70minw=24y1+40y2 s.t. 3y1+4y2-y3=4.5 2y1+5x2-y4=5 y1,y2,y3,y40 x1=40/70 x2=24/70 3x1+2x2=24， x3=0 4x1+5x2=40， x4=03y1+4y2=4.5， y3=0, 2y1+5y2=5 ， y4=0, 最优解x=(40/7，24/7，0，0)t ，y=(14/5，6/7，0，0)t利用互补松弛关系求解线性规划min z=6x1+8x2+3x3s.t. x1+ x2 1 x1+2x2+x3 -1 x1, x2, x3 0max w=y1-y2s.t. y1+ y2 6 y1+2y2

23、 8 y2 3 y1,y20原始问题对偶问题0 1 2 3 4 5 6 7 8654321w1w2y=-1 y=1y=3y=6最优解为(y1, y2)=(6, 0)max y=6先用图解法求解对偶问题。34min z=6x1+8x2+3x3s.t. x1+ x2 1 x1+2x2+x3 -1 x1, x2, x3 0max w=y1-y2s.t. y1+ y2 6 y1+2y2 8 y2 3 y1, y20max w=y1-y2s.t. y1+y2+y3 =6 y1+2y2 +y4 =8 y2 +y5=3 y1, y2, y3, y4, y50(y1, y2)=(6,0)(y1,y2,y3,y

24、4,y5)=(6, 0, 0, 2, 3)min z=6x1+8x2+3x3s.t. x1+ x2 -x4 =1 x1+2x2+x3 -x5 =-1 x1, x2, x3 ,x4, x50(x1, x2, x3 | x4, x5)(y1, y2 | y3, y4, y5)x2=x3=x4=0 x1=1, x5=2引进剩余变量 求对偶引进松弛变量图解法求解代入约束求出松弛变量互补松弛关系代入约束求解(x1, x2, x3, x4, x5)=(1, 0, 0, 0, 2)2.3 资源的影子价格(shadow price) yi=w/bi=最大利润的增量/第i种资源的增量=第i种资源的边际利润w=b

25、1y1+b2y2+biyi+bmymw+w=b1y1+b2y2+(bi+bi)yi+bmymw=biyiyi代表在资源最有利条件下对单位第代表在资源最有利条件下对单位第i种资源的估价，称种资源的估价，称为为影子价格影子价格。360 1 2 3 4 5 6 7 8654321x1x2z*=8.5x=(7/2,3/2)z*=8.75x=(15/4,5/4)z=9x=(3,3)maxz=2x1+x2 s.t. 2x215 6x1+2x224 x1+x25 x1,x20256思考:如果第一种资源增加1，也就是把15变为16,目标函数值将怎么变化?为什么?最优解x=(7/2, 3/2)t对偶问题最优解y

26、=(0，1/4，1/2)tp由对偶问题的互补松弛性质当由对偶问题的互补松弛性质当 时，时， 当当 时，时， .表明生产过程中某资源表明生产过程中某资源bi未得到充分利用时，未得到充分利用时，该资源的影子价格为该资源的影子价格为0；当该；当该资源的影子价格不为资源的影子价格不为0时，时，表 明 该 资 源 在 生 产 过 程 中 以 耗 费 完 毕 。表 明 该 资 源 在 生 产 过 程 中 以 耗 费 完 毕 。ijnjijbxa10 iyijnjijbxa10 iyp影子价格是一种机会成本，在完全市场经济条件下，当影子价格是一种机会成本，在完全市场经济条件下，当市场价格高于影子价格时，则会

27、卖出该资源；市场价格高于影子价格时，则会卖出该资源；当市场价当市场价格低于影子价格时，则会买入该资源。即影子价格越大，格低于影子价格时，则会买入该资源。即影子价格越大，说明这种资源越是相对紧缺；影子价格越小，说明这种说明这种资源越是相对紧缺；影子价格越小，说明这种资源越充裕。资源越充裕。p资源的影子价格有赖于资源的利用情况，因企业的生产资源的影子价格有赖于资源的利用情况，因企业的生产任务、产品结构等情况而变化。任务、产品结构等情况而变化。maxz=4x1+10 x2 s.t. 3x1+6x25 x1+3x22 2x1+5x24 x1,x20已知原问题为：y1y2y3则对偶问题为：minw=5y

28、1+2y2+4y3 s.t. 3y1+ y2+2y34 6y1+3y2+5y310 y1,y2,y30maxz=4x1+10 x2 s.t. 3x1+6x2+x3=5 x1+3x2 +x4=2 2x1+5x2 +x5=4 xj0(j=1,2,5)minw=5y1+2y2+4y3 s.t. 3y1+ y2+2y3-y4=4 6y1+3y2+5y3-y5=10 yi0(i=1,2,5)39cj410000cbxbbx1x2x3x4x50 x35361000 x42130100 x5425001cj-zj410000初始单纯形表为：此时对偶问题的基解为y(0，0，0，4，10)t不是对偶问题的可行解

29、40cj410000cbxbbx1x2x3x4x50 x35361005/60 x42130102/30 x54250014/5cj-zj410000初始单纯形表为：此时对偶问题的基解为y(0，0，0，4，10)t不是对偶问题的可行解41迭代得：cj410000cbxbbx1x2x3x4x50 x31101-2010 x22/31/3101/300 x52/31/300-5/31cj-zj2/300-10/30此时对偶问题的基解为y(0，10/3，0，-2/3，0)t不是对偶问题的可行解42迭代得：cj410000cbxbbx1x2x3x4x50 x31101-20110 x22/31/310

30、1/3020 x52/31/300-5/312cj-zj2/300-10/30此时对偶问题的基解为y (0，10/3，0，-2/3，0 )t不是对偶问题的可行解43迭代得：cj410000cbxbbx1x2x3x4x54x11101-2010 x21/301-1/3100 x51/300-1/3-11cj-zj00-2/3-20此时对偶问题的基解为y(2/3，2，0，0，0)t是对偶问题的可行解44 单纯形法求解的过程，从对偶的观点来看，单纯形法求解的过程，从对偶的观点来看，是在始终保持原始可行解的条件下，不断改进对是在始终保持原始可行解的条件下，不断改进对偶可行性的过程。一个从对偶不可行的解

31、，经过偶可行性的过程。一个从对偶不可行的解，经过几次叠代，逐步向对偶可行解靠拢，一旦得到的几次叠代，逐步向对偶可行解靠拢，一旦得到的解既是原问题可行的，又是对偶可行的，这个解解既是原问题可行的，又是对偶可行的，这个解就分别是原问题和对偶问题的最优解。就分别是原问题和对偶问题的最优解。 根据对偶问题的对称性，若保持对偶问题的根据对偶问题的对称性，若保持对偶问题的解是可行的，即检验数解是可行的，即检验数0，而原问题在非可行解，而原问题在非可行解的基础上，不断改进其可行性，逐步达到基可行的基础上，不断改进其可行性，逐步达到基可行解，此时就达到原问题和对偶问题的最优解。解，此时就达到原问题和对偶问题的

32、最优解。 设有问题 max z=cx ， ax b ， x 0 又设b是其一个基，当非基变量都为0时，可以得到xb=b-1b。若在b-1b中至少有一个负分量，并且在单纯形表的检验数行中的检验数都为非正，这种情况就可以用对偶单纯形法来进行求解。对偶单纯形法适用的情况：对偶单纯形法适用的情况：46step1.确定初始解 求初时基可行解,列出初始单纯性表(一般取松弛变量为基变量)；若所有检验数 0，且所有的基变量值均0，则此解为线性规划问题的最优解；若存在基变量的值0，则问题还没有达到最优解，则进行如下计算；step 2.改进 选择换出变量：min b-1bi | b-1 bi0,假设选取xr为换出

33、变量； 选择换入变量：min(cj-zj)/arj|arj0,假设xl为换入变量；step 4.迭代 使得alk1，其余aik为0。对偶单纯形法的计算步骤：minw=5y1+2y2+4y3 s.t. 3y1+ y2+2y34 6y1+3y2+5y310 y1,y2,y30例1maxw=-5y1-2y2-4y3 s.t. -3y1- y2-2y3-4 -6y1-3y2-5y3-10 y1,y2,y30maxw=-5y1-2y2-4y3 s.t. -3y1- y2-2y3+y4=4 -6y1-3y2-5y3+y5=10 yi0(i=1,2,5)48cj-5-2-400cbxbby1y2y3y4y5

34、0y4-4-3-1-2100y5-10-6-3-501cj-zj-5-2-400maxw=-5y1-2y2-4y3 s.t. -3y1- y2-2y3+y4=4 -6y1-3y2-5y3+y5=10 yi0(i=1,2,5)49cj-5-2-400cbxbby1y2y3y4y50y4-4-3-1-2100y5-10-6-3-501cj-zj-5-2-40050cj-5-2-400cbxbby1y2y3y4y50y4-4-3-1-2100y5-10-6-3-5015/62/34/5cj-zj-5-2-40051cj-5-2-400cbxbby1y2y3y4y50y4-4-3-1-2100y5-1

35、0-6-3-5015/62/34/5cj-zj-5-2-400-2y210/3215/30-1/352cj-5-2-400cbxbby1y2y3y4y50y4-4-3-1-2100y5-10-6-3-5015/62/34/5cj-zj-5-2-4000y4-2/3-10-1/31-1/3-2y210/3215/30-1/353cj-5-2-400cbxbby1y2y3y4y50y4-4-3-1-2100y5-10-6-3-5015/62/34/5cj-zj-5-2-4000y4-2/3-10-1/31-1/3-2y210/3215/30-1/3cj-zj-10-2/30-2/354cj-5-2

36、-400cbxbby1y2y3y4y50y4-4-3-1-2100y5-10-6-3-5015/62/34/5cj-zj-5-2-4000y4-2/3-10-1/31-1/3122-2y210/3215/30-1/3cj-zj-10-2/30-2/355cj-5-2-400cbxbby1y2y3y4y50y4-4-3-1-2100y5-10-6-3-5015/62/34/5cj-zj-5-2-4000y4-2/3-10-1/31-1/3122-2y210/3215/30-1/3cj-zj-10-2/30-2/3-5y12/3101/311/356cj-5-2-400cbxbby1y2y3y4y

37、50y4-4-3-1-2100y5-10-6-3-5015/62/34/5cj-zj-5-2-4000y4-2/3-10-1/31-1/3122-2y210/3215/30-1/3cj-zj-10-2/30-2/3-5y12/3101/311/3-2y220112-157cj-5-2-400cbxbby1y2y3y4y50y4-4-3-1-2100y5-10-6-3-5015/62/34/5cj-zj-5-2-4000y4-2/3-10-1/31-1/3122-2y210/3215/30-1/3cj-zj-10-2/30-2/3-5y12/3101/311/3-2y220112-1cj-zj0

38、0-1/3-1-1/3此时对偶问题和原问题都达到可行，所以均达到了最优解y（2/3.2,0,0,0) ，w=-22/3， w=22/3minw=2x1+3x2+4x3 s.t. x1+2x2+ x33 2x1- x2+3x34 x1,x2,x30例2:用对偶单纯形法求对偶问题的最优解maxw=-2x1-3x2-4x3 s.t. -x1- 2x2-x3-3 -2x1 +x2-3x3-4 x1,x2,x30maxw=-2x1-3x2-4x3 s.t. -x1-2x2-x3+x4=4 -2x1 +x2-3x3 +x5=10 xi0(i=1,2,5)maxz=3y1+2y2 s.t. y1+2y22

39、2y1 -y23 y1+3y24 y1,y20对偶问题为59cj-2-3-400cbxbbx1x2x3x4x50 x4-3-1-2-1100 x5-4-21-30114/3cj-zj-2-3-4000 x4-10-5/21/21-1/28/52-2x121-1/23/20-1/2cj-zj0-4-10-1-3x22/501-1/5-2/51/5-2x111/5107/5-1/5-2/5cj-zj00-9/5-8/5-1/5此时对偶问题和原问题都达到可行，所以均达到了最优解 原问题最优解为:x=(11/5,2/5,0,0,0)t, w =-28/5, w=28/5对偶问题最优解为：y=(8/5,

40、1/5,0,0,9/5)tl(1)初始解可以是非可行解，当检验数都初始解可以是非可行解，当检验数都时，时，就可以进行基的变换，这时不需要加入人工变就可以进行基的变换，这时不需要加入人工变量，因此可以直接计算。量，因此可以直接计算。l(2)当变量多于约束条件，对这样的当变量多于约束条件，对这样的lp问题，问题，用对偶单纯形法计算可以减少计算工作量。因用对偶单纯形法计算可以减少计算工作量。因此，对变量较少，而约束条件很多的此，对变量较少，而约束条件很多的lp问题，问题，可以先将它变换成对偶问题，然后用对偶单纯可以先将它变换成对偶问题，然后用对偶单纯形法求解。形法求解。l(3)在灵敏度分析中，有时需

41、要用对偶单纯形法，在灵敏度分析中，有时需要用对偶单纯形法，这样可使问题的处理简化。这样可使问题的处理简化。maxz=3x1-4x2 s.t. x1+2x22 3x1+ x24 x1- x21 x1+ x23 x1,x20maxz=3x1-4x2 s.t. -x1-2x2-2 -3x1- x2-4 x1- x21 x1+ x23 x1,x20maxz=3x1-4x2 s.t. -x1-2x2+x3=-2 -3x1- x2+x4=-4 x1- x2+x5=1 x1+ x2+x6=3 xj0例362cj3-40000cbxbbx1x2x3x4x5x60 x3-2-1-210000 x4-4-3-10

42、1000 x511-100100 x63110001cj-zj3-40000可以看出，这时候原问题和对偶问题都不可行列出初始单纯形表：63cj3-40000cbxbbx1x2x3x4x5x60 x3-2-1-210000 x4-4-3-101000 x511-100100 x63110001cj-zj3-4000064cj3-40000cbxbbx1x2x3x4x5x60 x3-2-1-210000 x4-4-3-1010040 x511-100100 x63110001cj-zj3-4000065cj3-40000cbxbbx1x2x3x4x5x60 x3-2-1-210000 x4-4-3

43、-1010040 x511-100100 x63110001cj-zj3-40000-4x24310-10066cj3-40000cbxbbx1x2x3x4x5x60 x3-2-1-210000 x4-4-3-1010040 x511-100100 x63110001cj-zj3-400000 x36501-200-4x24310-10067cj3-40000cbxbbx1x2x3x4x5x60 x3-2-1-210000 x4-4-3-1010040 x511-100100 x63110001cj-zj3-400000 x36501-200-4x24310-1000 x55400-11068

44、cj3-40000cbxbbx1x2x3x4x5x60 x3-2-1-210000 x4-4-3-1010040 x511-100100 x63110001cj-zj3-400000 x36501-200-4x24310-1000 x55400-1100 x6-1-20010169cj3-40000cbxbbx1x2x3x4x5x60 x3-2-1-210000 x4-4-3-1010040 x511-100100 x63110001cj-zj3-400000 x36501-200-4x24310-1000 x55400-1100 x6-1-200101cj-zj1500-40070cj3-4

45、0000cbxbbx1x2x3x4x5x60 x3-2-1-210000 x4-4-3-1010040 x511-100100 x63110001cj-zj3-400000 x36501-2006/5-4x24310-1004/30 x55400-1105/40 x6-1-200101-cj-zj1500-40071cj3-40000cbxbbx1x2x3x4x5x60 x36501-2006/5-4x24310-1004/30 x55400-1105/40 x6-1-200101-cj-zj1500-4003x16/5101/5-2/50072cj3-40000cbxbbx1x2x3x4x5

46、x60 x36501-2006/5-4x24310-1004/30 x55400-1105/40 x6-1-200101-cj-zj1500-4003x16/5101/5-2/500-4x22/501-3/51/50073cj3-40000cbxbbx1x2x3x4x5x60 x36501-2006/5-4x24310-1004/30 x55400-1105/40 x6-1-200101-cj-zj1500-4003x16/5101/5-2/500-4x22/501-3/51/5000 x51/500-4/53/51074cj3-40000cbxbbx1x2x3x4x5x60 x36501-2

47、006/5-4x24310-1004/30 x55400-1105/40 x6-1-200101-cj-zj1500-4003x16/5101/5-2/500-4x22/501-3/51/5000 x51/500-4/53/5100 x67/500-2/51/50175cj3-40000cbxbbx1x2x3x4x5x60 x36501-2006/5-4x24310-1004/30 x55400-1105/40 x6-1-200101-cj-zj1500-4003x16/5101/5-2/500-4x22/501-3/51/5000 x51/500-4/53/5100 x67/500-2/51

48、/501cj-zj00-320076cj3-40000cbxbbx1x2x3x4x5x60 x36501-2006/5-4x24310-1004/30 x55400-1105/40 x6-1-200101-cj-zj1500-4003x16/5101/5-2/500-4x22/501-3/51/50020 x51/500-4/53/5101/30 x67/500-2/51/5017cj-zj00-320077cj3-40000cbxbbx1x2x3x4x5x63x16/5101/5-2/500-4x22/501-3/51/50020 x51/500-4/53/5101/30 x67/500-2

49、/51/5017cj-zj00-32000 x41/300-4/315/3078cj3-40000cbxbbx1x2x3x4x5x63x16/5101/5-2/500-4x22/501-3/51/50020 x51/500-4/53/5101/30 x67/500-2/51/5017cj-zj00-32003x14/310-1/302/300 x41/300-4/315/3079cj3-40000cbxbbx1x2x3x4x5x63x16/5101/5-2/500-4x22/501-3/51/50020 x51/500-4/53/5101/30 x67/500-2/51/5017cj-zj00

50、-32003x14/310-1/302/30-4x21/30 1-1/30-1/300 x41/300-4/315/3080cj3-40000cbxbbx1x2x3x4x5x63x16/5101/5-2/500-4x22/501-3/51/50020 x51/500-4/53/5101/30 x67/500-2/51/5017cj-zj00-32003x14/310-1/302/30-4x21/30 1-1/30-1/300 x41/300-4/315/300 x64/300-2/151/5-1/3181cj3-40000cbxbbx1x2x3x4x5x63x16/5101/5-2/500-4

51、x22/501-3/51/50020 x51/500-4/53/5101/30 x67/500-2/51/5017cj-zj00-32003x14/310-1/302/30-4x21/30 1-1/30-1/300 x41/300-4/315/300 x64/300-2/150-1/31cj-zj00-1/30-2/30此时对偶问题和原问题都达到可行，所以均达到了最优解 x（4/3.1/3,0,1/3,0,4/3), z=8/3第五节第五节 灵敏度分析灵敏度分析 灵敏度分析的概念灵敏度分析的概念 对系统或事物（线性规划问题）因周围条件的变对系统或事物（线性规划问题）因周围条件的变化（如化（如c

52、j , bi, aij 的变化）显示出来的敏感程度的分的变化）显示出来的敏感程度的分析析b xb xnb-1b i b-1n j 0 cn - cbb-1n 当当cj、bi、ai j变变化时会引起哪些化时会引起哪些数字的变化？数字的变化？(1) 参数参数a，b，c在什么范围内变动，对当前最在什么范围内变动，对当前最优方案无影响？优方案无影响？(2) 参数参数a，b，c中的一个变动，对当前最优方中的一个变动，对当前最优方案影响？案影响？(3) 如果最优方案改变，如何用简便方法求新方如果最优方案改变，如何用简便方法求新方案？案？灵敏度分析所解决的问题灵敏度分析所解决的问题原问题对偶问题结论或继续计

53、算的步骤可行解可行解问题的最优解或最优基不变可行解非可行解用单纯形法继续迭代求最优解非可行解可行解用对偶单纯形法继续迭代求最优解非可行解非可行解引进人工变量，编制新的单纯形表重新计算每天可用能力每天可用能力设备设备a(h)设备设备b(h)调试工序调试工序(h)06152115245利润利润(元元)21例：佳美公司计划制造例：佳美公司计划制造、 两种家电产品。已两种家电产品。已知各制造一件时分别占用的设备知各制造一件时分别占用的设备a、b的台时、调的台时、调整工序时间及每天可用于这两种家电的能力、各整工序时间及每天可用于这两种家电的能力、各出售一件时的获利情况，如下表。问该公司应制出售一件时的获

54、利情况，如下表。问该公司应制造两种家电各生产多少造两种家电各生产多少, 可获最大利润可获最大利润?一、分析一、分析 cj 的变化的变化c j 的变化仅仅影响检验数的变化仅仅影响检验数 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1，x2 0max z= 2x1 +x2解解: :设两种家电设两种家电产量分别为变量产量分别为变量x1 ， x2s.t.最终单纯形表如下：最终单纯形表如下：87cbxbbx1x2x3x4x5210000 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2000-1/4-1/2（1）若家电）若家电的利润降至

55、的利润降至1.5元元/件，而家电件，而家电的的利润增至利润增至2元元/件时，美佳公司最优生产计划有何件时，美佳公司最优生产计划有何变化？变化？88cbxbbx1x2x3x4x51.520000 x315/20015/4-15/261.5x17/21001/4-1/2142x23/2010-1/43/20001/8-9/4cbxbbx1x2x3x4x51.520000 x46004/51-61.5x1210-1/5012x23011/50000-1/100-3/2(2)若家电若家电的利润不变，则家电的利润不变，则家电的利润在什么范围的利润在什么范围内变化时，该公司的最优生产计划将不发生变化？内变

56、化时，该公司的最优生产计划将不发生变化？设家电设家电的的利润为利润为(1+)元，最终单纯形变为：元，最终单纯形变为：cbxbbx1x2x3x4x521+0000x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2000-1/4+ 1/4 -1/2-3/2 -1/4+1/4 0-1/2- 3/2 0- 1/3 12/3 c22二、分析二、分析 bi的变化的变化bi 的变化仅仅影响的变化仅仅影响b列列 的变化的变化 b= = b-1b x xb= = b-1b ， b=b+b x xb， = = b-1b= b-1(b+ b) = b-1b+ b-1

57、b（3）若设备若设备a a和调试工序的每天能力不变，而设和调试工序的每天能力不变，而设备备b b每天的能力增加到每天的能力增加到3232小时，分析公司最优计划小时，分析公司最优计划的变化。的变化。cbxbbx1x2x3x4x5210000 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2000-1/4-1/21 5/4 15/20 1/4 -1/20 -1/4 3/2b-1b=080= =102-2b-1080102-2（3）若设备若设备a a和调试工序的每天能力不变，而设和调试工序的每天能力不变，而设备备b b每天的能力增加到每天的能力增加到

58、3232小时，分析公司最优计划小时，分析公司最优计划的变化。的变化。cbxbbx1x2x3x4x5210000 x335/20015/4-15/22x111/21001/4-1/21x2-1/2010-1/43/2000-1/4-1/2利用对偶单纯形法迭代后得：利用对偶单纯形法迭代后得：0 x315051002x15110010 x420-401-60-100-2最优计划为只生产最优计划为只生产5件家电件家电。（4）若设备）若设备a和和b每天能力不变，而调试工每天能力不变，而调试工序在什么范围内变化，问题的最优基不变。序在什么范围内变化，问题的最优基不变。b-1 b=1 5/4 15/2 0-

59、15/20 1/4 -1/2 0 = -1/20 -1/4 3/2 3/2cbxbbx1x2x3x4x5210000 x315/2 -15/20015/4-15/22x17/2 -1/21001/4-1/21x23/2 +3/2010-1/43/2000-1/4-1/2-1 14 b36增加一个变量增加一个变量xj 相当于增加一种新产品相当于增加一种新产品三、增加一个变量三、增加一个变量x j 的分析的分析（5）公司计划推出新产品）公司计划推出新产品，生产一件所需设备，生产一件所需设备a,b及调试工序的时间分别为及调试工序的时间分别为3小时、小时、4小时、小时、2小时，小时，预期盈利预期盈利3

60、元元/件，试分析该种产品是否值得投产，件，试分析该种产品是否值得投产，如投产，对该公司的最优生产计划有何影响。如投产，对该公司的最优生产计划有何影响。1 5/4 15/20 1/4 -1/20 -1/4 3/2p,6=b-1p6=342-702= =6 = c6 - cbb-1 p6 = c6 - y p6 3 =3-( 0, 1/4 , 1/2) 4 = 1 2设该公司生产设该公司生产x6件家电件家电 ,有有cbxbbx1x2x3x4x5x62100030 x315/20015/4-15/2-72x17/21001/4-1/201x23/2010-1/43/22000-1/4-1/2 1cb