数学软件MATLAB课件第二章_对偶理论及灵敏度分析

1、2022-7-51DUAL 2022-7-522.1 线性规划的对偶问题一、对偶问题的提出 现有甲乙两种原材料生产A1，A2两种产品，所需的原料，甲乙两种原料的可供量，以及生产A1,A2两种产品可得的单位利润见表。问如何安排生产资源使得总利润最大？A1A2原料甲3224乙4540利润4.552022-7-53A1A2原料甲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.

2、 3y1+4y24.5 2y1+5y25 y1,y20 另一方面，假设另一公司想把资源买过来，它至少应付出多大代价才能使原来公司放弃生产，出让资源？2022-7-54A1A2原料甲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、2022-7-55A1A2原料甲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 另一方面，假设另一公司想把资源买过来，它至少应付出多大代价才能使原来公司放弃生产，出让资源？ 2 5 42 5第第6页页二、对称形式下对偶问题的一般形式 定义：变量均为非负约束的情况下，约束条件在目标函数取极大值时均取“”号；当目标函数求极

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第第7页页原始问题max z=CXs.t. AXb X 0对

5、偶问题min w=bTYs.t. ATYCTY 0maxbACCTATbTminmnmn第第8页页maxZ=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举例举例第第9页页原问题：maxZ=x1+4x2+2x3 s.t. 5x1-x2+2x38 x1+3x2-3x35 x1,x2,x30对偶问题：minw=8y1+5y2 s.t. 5y1+y21 -y1+3y24 2

6、y1-3y2 2 y1,y20练习第第10页页结论：对偶问题的对偶为原问题结论：对偶问题的对偶为原问题原始问题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对偶问题的对偶就是原始问题。两个问题中的任一个对偶问题的对偶就是原始问题。两个问题中的任一个都可以作为原始问题，另一个就是它的对偶问题。都可以作为原始问题，另一个就是它的对偶问题。2022-7-511对偶问题的对偶max z=6x1+9x2s.t. x1+2x22 2x1- 3

7、x23 x1+2x2-1 x1, x20minw=2y1+3y2-y3s.t. y1+2y2+y36 2y1-3y2+2y39 y1, y2, y30根据定义写出对偶问题根据定义写出对偶问题max u=6w1+9w2s.t. w1+2w22 2w1- 3w23 w1+2w2-1 w1, w20第第12页页minz=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

8、”) s.t.-x1+x2-3x3+(x4-x4”)5 2x1 -2x3+(x4-x4”)-4 x2+x3 +(x4-x4”) 6 -x2-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对偶问题三、非对称形式的原对偶问题引例引例2022-7-513maxw=5y1-4y2+6(y3-y3”) s.t

9、.-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设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无约束2022-7-514maxw=5y1+4y2+6y3 s.t. y1+2y2 2 y1 +y3 3 -3y1+2y2+y3 -5 y1 -y2 +y3 = 1 y

10、10 ,y20,y3无约束minz=2x1+3x2-5x3+x4 s.t. x1+x2-3x3+x45 2x1 +2x3-x4 4 x2+x3+x4 = 6 x10,x2,x30m i nm i nFree 原原问问题题变变量量m axm ax = = 对对偶偶问问题题约约束束原问题原问题对偶问题对偶问题 = = 约约束束Free 变变量量比较后得出什么结论比较后得出什么结论？第第15页页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.

11、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: Freep原始问题变量的个数(3)等于对偶问题约束条件的个数(3)；p原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。p原始问题变量的性质影响对偶问题约束条件的性质。p原始问题约束条件的性质影响对偶问题变量的性质。写对偶问题的练习（1）第第16页页原始问题max z=2x1-x2+3x3-2x4s.t. x1 +3x2 - 2x3 + x412 -2x1 + x2 -3x48 3x1 - 4x2 +5x

12、3 - x4 = 15 x10, x2:Free, x30, x40min w=12y1+8y2+15y3s.t. y1 2y2 + 3y32 3y1 + y2 4y3=-1 -2y1 +5y33 y1 3y2 - y3-2 y10,y20, y3:Free对偶问题写对偶问题的练习（2）2022-7-517m axm axFree 原原问问题题变变量量m i nm i n = = 对对偶偶问问题题约约束束 = = 约约束束Free 变变量量第第18页页maxZ=x1-2x2+3x3 s.t. 2x1+4x2+3x3100 3x1-2x2+6x3200 5x1+3x2+4x3=150 x1, x

13、30练习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+4x32 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对偶问题对偶问题第第19页页 原问题 Max Z=CX AXb X0其中X(x1,x2xn)TMax Z=CX+0Xs AX+IXs=b X, Xs0其中Xs(x

14、n+1,xn+2xn+m)TI 为mm的单位矩阵 2.2 对偶问题的基本性质一、单纯性法计算的矩阵描述其初始单纯性表及经过若干次迭代后的单纯性其初始单纯性表及经过若干次迭代后的单纯性表如下：表如下：2022-7-520非基变量基变量XBXNXs0XsbBNIcj-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

15、-1N，B-1)；(4)初始单纯形表中xj的系数向量为Pj，迭代后为Pj，且Pj=B-1Pj。2022-7-521非基变量基变量XBXNXs0XsbBNIcj-zjCBCN0 基变量非基变量XBXNXsCBXBB-1 bIB-1NB-1cj-zj0CN-CBB-1N-CBB-11 11 11 11 11 11 1( () )BNSBNSBBNNBNBNBSBXNXIXbXBbBNXBXZC XC XZC BbCC BN XC BX- - - - - - -+ + += = =- - -= = =+ +- - -由由得得: :, ,代代入入目目标标函函数数+ +得得: :(5)第第22页页当B为

16、最优基，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为对偶问题为可行解且具有相同的目标函数值。第第23页页maxZ=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+x

17、3=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例题2022-7-524cj4.5500CBXBbx1x2x3x44.5x140/7105/7-2/75x224/701-4/73/7cj-zj00-5/14-6/7cj244000CBYBby1y2y3y424y15/1410-5/74/740y26/7012/7-3/7cj-zj0040/724/7(x3,x4)=(0,0)(y3,y4)=(0,0)-y1-y2-y4-y3x1x2x4x32022-7-525

18、maxZ=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.5 2y1+5x2-y4=5 y1,y2,y3,y40y1y2x1x2例题第第26页页原始问题max Z=CXs.t. AXb X 0对偶问题min W=YTbs.t. ATYCTY 0二、对偶问题的基本性质第第

19、27页页YbXCYXT题的可行解，则分别是原问题和对偶问和设二、对偶问题的基本性质1.1.弱对偶性弱对偶性YbbYXAYXAYXCCYAbXAYXTTTTTT)()(,故所以题的可行解分别是原问题和对偶问和证：因为第第28页页|原问题任一可行解的目标函数是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数是其原问题目标函数的上界。|如原问题有可行解且目标函数值无界，则其对偶问题无可行解；反之对偶问题有可行解且目标函数无界，则原问题无可行解。（对偶问题无可行解时，其原问题无界解或无可行解。|若原问题有可行解而其对偶问题无可行解时，原问题目标函数无界。|若对偶问题有可行解而其原问题无可行

20、解时，对偶问题目标函数无界。推论：TCXb Y Q Q第第29页页2.最优性 *, ,TTTTTTTTTTXYCXCXb Yb YCXb YCXb YCXb Yb YCXb YCXCXb YCXCXb Yb Y常常=吵=吵=证证：设设, ,分分别别为为原原问问题题和和对对偶偶问问题题的的最最优优解解，则则又又 ，所所以以 故故 题的最优解。分别是原问题和对偶问和则题的可行解，且分别是原问题和对偶问和若YXYbXCYXT,第第30页页 若原问题和对偶问题均具有可行解，则二者均具若原问题和对偶问题均具有可行解，则二者均具有最优解，且它们的最优解的目标值相等。有最优解，且它们的最优解的目标值相等。3

21、.强对偶性（对偶性定理）证：由于二者均有可行解，所以原问题的目标证：由于二者均有可行解，所以原问题的目标函数值具有上界，对偶问题的目标函数值具有函数值具有上界，对偶问题的目标函数值具有下界，因此二者均具有最优解。下界，因此二者均具有最优解。 当原问题有最优解时当原问题有最优解时, ,对偶问题的解对偶问题的解Y=CBB-1为可行解为可行解, ,且且 Z=CBB-1b=W, ,由最优性知由最优性知, ,二者的二者的解均为最优解。解均为最优解。第第31页页 在线性规划问题的最优解中，如果对应某一约束条件的在线性规划问题的最优解中，如果对应某一约束条件的对偶对偶变量变量值为值为非非0，则该，则该约束条

22、件约束条件取严格等式；反之如果取严格等式；反之如果约束条件约束条件取严格不等式取严格不等式，则，则 对应的对应的对偶变量对偶变量值为值为0。若yi 0,则aijxj，=bi，即xsi=0若aijxj，bi ，即xsi0 则 yi 0同理若xj 0, 则aijyi，=cj若aijyi ， cj，则 xj 0.4.互补松弛定理第第32页页maxZ=4.5x1+5x2 s.t. 3x1+2x2+x3=24 4x1+5x2+x4=40 x1,x2,x3,x4,0 Y1=14/50 y2=6/70minw=24y1+40y2 s.t. 3y1+4y2-y3=4.5 2y1+5x2-y4=5 y1,y2,

23、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第第33页页利用互补松弛关系求解线性规划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 8 y2 3 y1,y20原始问题对偶问题0 1 2 3 4 5 6 7 8654321w1w2y=-1 y=1y

24、=3y=6最优解为(y1, y2)=(6, 0)max y=6先用图解法求解对偶问题。2022-7-534min 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,y4,y5)=(6, 0, 0, 2, 3)min z=6x1+8x2+3x3s.t. x1+ x2

25、-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)第第35页页2.3 资源的影子价格(Shadow Price) yi=w/bi=最大利润的增量/第i种资源的增量=第i种资源的边际利润w=b1y1+b2y2+biyi+bmymw+w=b1y1+b2y2+(bi+bi)yi+bm

26、ymw=biyiYi代表在资源最有利条件下对单位第代表在资源最有利条件下对单位第i种资源的估价，称种资源的估价，称为为影子价格影子价格。2022-7-5360 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=(0，1/4，1/2)T第第37页页p由对偶问题的互补松弛性质当由对偶

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

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

29、y34 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)2.4 对偶单纯形法2022-7-539cj410000CBXBbx1x2x3x4x50 x35361000 x42130100 x5425001cj-zj410000初始单纯形表为：此时对偶问题的基解为Y(0，0，0，4，10)T不是对偶问题的可行解2022-7

30、-540cj410000CBXBbx1x2x3x4x50 x35361005/60 x42130102/30 x54250014/5cj-zj410000初始单纯形表为：此时对偶问题的基解为Y(0，0，0，4，10)T不是对偶问题的可行解2022-7-541迭代得：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不是对偶问题的可行解2022-7-542迭代得：cj410000CBXBbx1x2x3x4x50 x3110

31、1-20110 x22/31/3101/3020 x52/31/300-5/312cj-zj2/300-10/30此时对偶问题的基解为Y (0，10/3，0，-2/3，0 )T不是对偶问题的可行解2022-7-543迭代得：cj410000CBXBbx1x2x3x4x54x11101-2010 x21/301-1/3100 x51/300-1/3-11cj-zj00-2/3-20此时对偶问题的基解为Y(2/3，2，0，0，0)T是对偶问题的可行解2022-7-544 单纯形法求解的过程，从对偶的观点来看，单纯形法求解的过程，从对偶的观点来看，是在始终保持原始可行解的条件下，不断改进对是在始终保

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

33、此时就达到原问题和对偶问题的最优解。解，此时就达到原问题和对偶问题的最优解。第第45页页 设有问题 max Z=CX ， AX b ， X 0 又设B是其一个基，当非基变量都为0时，可以得到XB=B-1b。若在B-1b中至少有一个负分量，并且在单纯形表的检验数行中的检验数都为非正，这种情况就可以用对偶单纯形法来进行求解。对偶单纯形法适用的情况：对偶单纯形法适用的情况：2022-7-546step1.确定初始解 求初时基可行解,列出初始单纯性表(一般取松弛变量为基变量)；若所有检验数 0，且所有的基变量值均0，则此解为线性规划问题的最优解；若存在基变量的值0，则问题还没有达到最优解，则进行如下计

34、算；step 2.改进 选择换出变量：min B-1bi | B-1 bi0,假设选取xr为换出变量； 选择换入变量：min(cj-zj)/arj|arj0,假设xl为换入变量；step 4.迭代 使得alk1，其余aik为0。对偶单纯形法的计算步骤：第第47页页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

35、-3y2-5y3+y5=10 yi0(i=1,2,5)2022-7-548cj-5-2-400CBXBby1y2y3y4y50y4-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)2022-7-549cj-5-2-400CBXBby1y2y3y4y50y4-4-3-1-2100y5-10-6-3-501cj-zj-5-2-4002022-7-550cj-5-2-400CBXBby1y2y3y4y50y4-4-3-1-2100y5

36、-10-6-3-5015/62/34/5cj-zj-5-2-4002022-7-551cj-5-2-400CBXBby1y2y3y4y50y4-4-3-1-2100y5-10-6-3-5015/62/34/5cj-zj-5-2-400-2y210/3215/30-1/32022-7-552cj-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/32022-7-553cj-5-2-400CBXBby1y2y3y4y50y4-4-3-1

37、-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/32022-7-554cj-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/32022-7-555cj-5-2-400CBXBby1y2y3y4y50y4-4-3-1-2100y5-10-6-3-5015/6

38、2/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/32022-7-556cj-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-12022-7-557cj-5-2-400CBXBby1y2y3y4y50y4-4

39、-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-zj00-1/3-1-1/3此时对偶问题和原问题都达到可行，所以均达到了最优解Y（2/3.2,0,0,0) ，W=-22/3， W=22/3第第58页页Minw=2x1+3x2+4x3 s.t. x1+2x2+ x33 2x1- x2+3x34 x1,x2,x30例2:用对偶单纯形法求对偶问题的最优解Maxw=-2x1-3x2-4x3

40、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 2y1 -y23 y1+3y24 y1,y20对偶问题为2022-7-559cj-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-

41、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,1/5,0,0,9/5)T第第60页页|(1)初始解可以是非可行解，当检验数都初始解可以是非可行解，当检验数都时，就时，就可以进行基的变换，这时不需要加入人工变量，可以进行基的变换，这时不需要加入人工变量，因此可以直接计算。因此可以直接计算。|(2)当变量多于约束条件，对这样的当变量多于约束条件，对这样

42、的LP问题，用对问题，用对偶单纯形法计算可以减少计算工作量。因此，对偶单纯形法计算可以减少计算工作量。因此，对变量较少，而约束条件很多的变量较少，而约束条件很多的LP问题，可以先将问题，可以先将它变换成对偶问题，然后用对偶单纯形法求解。它变换成对偶问题，然后用对偶单纯形法求解。|(3)在灵敏度分析中，有时需要用对偶单纯形法，在灵敏度分析中，有时需要用对偶单纯形法，这样可使问题的处理简化。这样可使问题的处理简化。对偶单纯形法的优点第第61页页Maxz=3x1-4x2 s.t. x1+2x22 3x1+ x24 x1- x21 x1+ x23 x1,x20Maxz=3x1-4x2 s.t. -x1

43、-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例32022-7-562cj3-40000CBXBbx1x2x3x4x5x60 x3-2-1-210000 x4-4-3-101000 x511-100100 x63110001cj-zj3-40000可以看出，这时候原问题和对偶问题都不可行列出初始单纯形表：2022-7-563cj3-40000CBXBbx1x2x3x4x5x60 x3-2-1-210000 x4-4

44、-3-101000 x511-100100 x63110001cj-zj3-400002022-7-564cj3-40000CBXBbx1x2x3x4x5x60 x3-2-1-210000 x4-4-3-1010040 x511-100100 x63110001cj-zj3-400002022-7-565cj3-40000CBXBbx1x2x3x4x5x60 x3-2-1-210000 x4-4-3-1010040 x511-100100 x63110001cj-zj3-40000-4x24310-1002022-7-566cj3-40000CBXBbx1x2x3x4x5x60 x3-2-1-

45、210000 x4-4-3-1010040 x511-100100 x63110001cj-zj3-400000 x36501-200-4x24310-1002022-7-567cj3-40000CBXBbx1x2x3x4x5x60 x3-2-1-210000 x4-4-3-1010040 x511-100100 x63110001cj-zj3-400000 x36501-200-4x24310-1000 x55400-1102022-7-568cj3-40000CBXBbx1x2x3x4x5x60 x3-2-1-210000 x4-4-3-1010040 x511-100100 x63110

46、001cj-zj3-400000 x36501-200-4x24310-1000 x55400-1100 x6-1-2001012022-7-569cj3-40000CBXBbx1x2x3x4x5x60 x3-2-1-210000 x4-4-3-1010040 x511-100100 x63110001cj-zj3-400000 x36501-200-4x24310-1000 x55400-1100 x6-1-200101cj-zj1500-4002022-7-570cj3-40000CBXBbx1x2x3x4x5x60 x3-2-1-210000 x4-4-3-1010040 x511-10

47、0100 x63110001cj-zj3-400000 x36501-2006/5-4x24310-1004/30 x55400-1105/40 x6-1-200101-cj-zj1500-4002022-7-571cj3-40000CBXBbx1x2x3x4x5x60 x36501-2006/5-4x24310-1004/30 x55400-1105/40 x6-1-200101-cj-zj1500-4003x16/5101/5-2/5002022-7-572cj3-40000CBXBbx1x2x3x4x5x60 x36501-2006/5-4x24310-1004/30 x55400-11

48、05/40 x6-1-200101-cj-zj1500-4003x16/5101/5-2/500-4x22/501-3/51/5002022-7-573cj3-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/5102022-7-574cj3-40000CBXBbx1x2x3x4x5x60 x36501-2006/5-4x24310-1004/30 x5540

49、0-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/5012022-7-575cj3-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/501cj-zj00-3200202

50、2-7-576cj3-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-32002022-7-577cj3-40000CBXBbx1x2x3x4x5x63x16/5101/5-2/500-4x22/501-3/51/50020 x51/500-4/53/5101/30 x67/500-2/51

51、/5017cj-zj00-32000 x41/300-4/315/302022-7-578cj3-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/302022-7-579cj3-40000CBXBbx1x2x3x4x5x63x16/5101/5-2/500-4x22/501-3/51/50020 x51/500-4/53/5101/30 x67/500-2/5

52、1/5017cj-zj00-32003x14/310-1/302/30-4x21/30 1-1/30-1/300 x41/300-4/315/302022-7-580cj3-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/312022-7-581cj3-40000CBXBbx1

53、x2x3x4x5x63x16/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/150-1/31cj-zj00-1/30-2/30此时对偶问题和原问题都达到可行，所以均达到了最优解 X（4/3.1/3,0,1/3,0,4/3), Z=8/3第第82页页第五节第五节 灵敏度分析灵敏度分析 灵敏度分析的概念灵敏度分析的概念 对系统或事物（线性规划问题）

54、因周围条件的变对系统或事物（线性规划问题）因周围条件的变化（如化（如cj , bi, aij 的变化）显示出来的敏感程度的分的变化）显示出来的敏感程度的分析析b XB XNB-1b I B-1N j 0 CN - CBB-1N 当当cj、bi、ai j变变化时会引起哪些化时会引起哪些数字的变化？数字的变化？第第83页页(1) 参数参数A，b，C在什么范围内变动，对当前最在什么范围内变动，对当前最优方案无影响？优方案无影响？(2) 参数参数A，b，C中的一个中的一个( (几个几个) )变动，对当前变动，对当前最优方案影响？最优方案影响？(3) 如果最优方案改变，如何用简便方法求新方如果最优方案改

55、变，如何用简便方法求新方案？案？灵敏度分析所解决的问题灵敏度分析所解决的问题第第84页页原问题对偶问题结论或继续计算的步骤可行解可行解问题的最优解或最优基不变可行解非可行解用单纯形法继续迭代求最优解非可行解可行解用对偶单纯形法继续迭代求最优解非可行解非可行解引进人工变量，编制新的单纯形表重新计算第第85页页每天可用能力每天可用能力设备设备A(h)设备设备B(h)调试工序调试工序(h)06152115245利润利润(元元)21例：佳美公司计划制造例：佳美公司计划制造、 两种家电产品。已两种家电产品。已知各制造一件时分别占用的设备知各制造一件时分别占用的设备A、B的台时、调的台时、调整工序时间及每

56、天可用于这两种家电的能力、各整工序时间及每天可用于这两种家电的能力、各出售一件时的获利情况，如下表。问该公司应制出售一件时的获利情况，如下表。问该公司应制造两种家电各生产多少造两种家电各生产多少, 可获最大利润可获最大利润?一、分析一、分析 cj 的变化的变化c j 的变化仅仅影响检验数的变化仅仅影响检验数第第86页页 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1，x2 0max Z= 2x1 +x2解解: :设两种家电设两种家电产量分别为变量产量分别为变量x1 ， x2s.t.最终单纯形表如下：最终单纯形表如下：2022-7-587CBXBbx1x2x3x4X521000

57、0 x315/20015/4-15/22X17/21001/4-1/21X23/2010-1/43/2000-1/4-1/2（1）若家电）若家电的利润降至的利润降至1.5元元/件，而家电件，而家电的的利润增至利润增至2元元/件时，美佳公司最优生产计划有何件时，美佳公司最优生产计划有何变化？变化？2022-7-588CBXBbx1x2x3x4X51.520000 x315/20015/4-15/262X17/21001/4-1/2141X23/2010-1/43/20001/8-9/4CBXBbx1x2x3x4X51.520000 x46004/51-61.5X1210-1/5012X23011

58、/50000-1/100-3/2第第89页页(2)若家电若家电的利润不变，则家电的利润不变，则家电的利润在什么范围的利润在什么范围内变化时，该公司的最优生产计划将不发生变化？内变化时，该公司的最优生产计划将不发生变化？设家电设家电的的利润为利润为(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第第90页页二、分析二、分析 bi的变化的变化bi

59、 的变化仅仅影响的变化仅仅影响b列列 的变化的变化 b= = B-1b X XB= = B-1b ， b=b+b X XB， = = B-1b= B-1(b+ b) = B-1b+ B-1 b第第91页页（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/

60、20 -1/4 3/2B-1b=080= =102-2B-1080102-2第第92页页（3）若设备若设备A A和调试工序的每天能力不变，而设和调试工序的每天能力不变，而设备备B B每天的能力增加到每天的能力增加到3232小时，分析公司最优计划小时，分析公司最优计划的变化。的变化。CBXBbx1x2x3x4x5210000 x335/20015/4-15/22x111/21001/4-1/21x2-1/2010-1/43/2000-1/4-1/2利用对偶单纯形法迭代后得：利用对偶单纯形法迭代后得：第第93页页0 x315051002x15110010 x420-401-60-100-2最优计划