对偶理论和灵敏度分析(新).ppt

《对偶理论和灵敏度分析(新).ppt》由会员分享，可在线阅读，更多相关《对偶理论和灵敏度分析(新).ppt（128页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、对偶理论和灵敏度分对偶理论和灵敏度分析析(新新)第3节 线性规划对偶问题的提出 现有甲乙两种原材料生产A1，A2两种产品，所需的原料，甲乙两种原料的可供量，以及生产A1,A2两种产品可得的单位利润见表。问如何安排生产资源使得总利润为最大？A1A2可供量甲3224已4540利润 4.552解：设生产A1为x1件，生产A2为x2件，则线性规划问题为：maxZ=4.5x1+5x2 s.t.3x1+2x224 4x1+5x240 x1,x20假设现在不考虑生产产品，而是把甲乙两种原材料卖掉，则问题变成对于甲乙两种原材料企业以多少最低价愿意出让？解：设甲资源的出让价格为y1,乙资源的出让价格为y2min

2、w=24y1+40y2 s.t.3y1+4y24.5 2y1+5y25 y1,y203245342 53第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+am2

3、ym c2 a1ny1+a2ny2+amnym cn y1,y2,ym 0Max Z=CX s.t.AXb X0Minw=Yb s.t.AYC Y04原始问题max z=CXs.t.AXb X 0对偶问题min w=Ybs.t.AYCY 0maxbACCATbminmnmn4.1原问题与对偶问题的关系5举例：maxZ=3x1+2x2 s.t.-x1+2x24 3x1+2x214 x1-x2 3 x1,x20minw=4y1+14y2+y3 s.t.-y1+3y2+y33 2y1+2x2-y32 y1,y2,y30y1y2y3第一种资源第二种资源第三种资源第一种产品 第二种产品x1x26原始问题

4、为min z=2x1+3x2-x3s.t.x1+2x2+x36 2x1-3x2+2x39 x1,x2,x30根据定义，对偶问题为max y=6y1+9y2s.t.y1+2y22 2y1-3y23 y1+2y2-1 y1,y20原始问题是极小化问题原始问题的约束全为原始问题有3个变量，2个约束原始问题的变量全部为非负对偶问题是极大化问题对偶问题的约束全为对偶问题有2个变量，3个约束原始问题的变量全部为非负原始问题变量的个数(3)等于对偶问题约束条件的个数(3)原始问题约束条件的个数(2)等于对偶问题变量的个数(2)7非对称形式的原对偶问题minz=2x1+3x2-5x3+x4 s.t.x1+x2

5、-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-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 y

6、1+y2+(y3-y3”)1 -y1-y2-(y3-y3”)-1 y1,y2,y3,y3”0写出对偶问题8maxw=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设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无约束minz=2x1+3x2

7、-5x3+x4 s.t.x1+x2-3x3+x45 2x1 +2x3-x4 4 x2+x3+x4 =6 x10,x2,x30比较原问题和对偶问题9原 始 对 偶 表 10对偶关系1、极大与极小的对偶2、价值系数与资源系数的对偶3、约束条件系数矩阵的对偶是矩阵的转置4、反向不等式与非正的决策变量的对偶5、等式与非负限制的决策变量的对偶6、最优解与检验数的对偶11min z=2x1+4x2-x3s.t.3x1-x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15max y=6w1+12w2+8w3+15w4s.t.3w1-w2+2w3+w4 2 -w1

8、+2w2+w3+3w4 4 2w1-3w2+2w3-w4 -1 w1 0,w2 ,w3 0,w4 0=Free=x10 x20 x3:Freep原始问题变量的个数(3)等于对偶问题约束条件的个数(3)；p原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。p原始问题变量的性质影响对偶问题约束条件的性质。p原始问题约束条件的性质影响对偶问题变量的性质。写对偶问题的练习（1）12写对偶问题的练习（2）原始问题max z=2x1-x2+3x3-2x4s.t.x1+3x2-2x3+x412 -2x1+x2 -3x48 3x1-4x2+5x3-x4=15 x10,x2:Free,x30,x40mi

9、n y=12w1+8w2+15w3s.t.w1-2w2+3w32 3w1+w2-4w3=-1 -2w1 +5w33 w1-3w2-w3-2 w10,w20,w3:Free对偶问题13maxZ=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+4x32 2x1+x2+3x33 x1+4x2+3x3=5 x1

10、 0,x20maxw=2y1+3y2+5y3 s.t.y1+2y2+y32 3y1+y2+4y3 2 4y1+3y2+3y34 y10,y2014原始和对偶问题可行解目标函数值比较min z=2x1+3x2s.t.x1+3x23 2x1+x2 4 x1,x2 0max w=3y1+4y2s.t.y1+2y22 3y1+y2 3 y1,y2 00 1 2 34321A(3,0)B(1.8,0.4)C(0,4)D(2,2)可行解z最优解A6B4.8是C12D103210 1 2A(1,0)B(0.8,0.6)C(0,1)O(0,0)可行解w最优解O0A3B4.8是C415单纯形法计算的矩阵描述Ma

11、x Z=CX AXb X0其中X(x1,x2xn)TMax Z=CX+0Xs AX+IXs=b X,Xs0其中Xs(xn+1,xn+2xn+m)TI 为mm的单位矩阵16非基变量基变量XBXNXs0XsbBNIcj-zjCBCN0基变量非基变量XBXNXsCBXBB-1 bIB-1NB-1cj-zj0CN-CBB-1N-CBB-1对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1；初始单纯形表中基变量Xs=b，迭代后的表中为XB=B-1b；约束矩阵（A，I）（B，N，I），迭代后为（B-1B，B-1N，B-1I）（I，B-1N，B-1)；初始单纯形表中xj的系数向量为Pj，迭代后为Pj

12、，且Pj=B-1Pj。17当B为最优基时，XB为最优解时，则有：CN-CBB-1N0 -CBB-10CB-CBI=0代入得：CNCBB-1N+CB-CBI0CCBB-1(B+N)0整理得：CCBB-1 A0 -CBB-10令CBB-1为单纯形乘子，YCBB-1则：CY A0 -Y0Y AC Y 0WYb=CBB-1b=Z所以当原问题为最优解时，对偶问题为可行解且具有相同的目标函数值。18maxZ=4.5x1+5x2 s.t.3x1+2x224 4x1+5x240 x1,x20minw=24y1+40y2 s.t.3y1+4y24.5 2y1+5y25 y1,y20y1y2x1x2maxZ=4.

13、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+5Y2-y4=5 y1,y2,y3,y40y1y2x1x219cj4.5500CBXBbx1x2x3x40 x3243210120 x44045018cj-zj4.5500解原问题：20cj4.5500CBXBbx1x2x3x40 x3243210120 x44045018cj-zj4.55000 x387/501-2/55x284/5101/5cj-zj1/200-121cj4.5500CBXBbx1x2x3x4

14、0 x3243210120 x44045018cj-zj4.55000 x387/501-2/540/75x284/5101/510cj-zj1/200-122cj4.5500CBXBbx1x2x3x40 x3243210120 x44045018cj-zj4.55000 x387/501-2/540/75x284/5101/510cj-zj1/200-14.5x140/7105/7-2/75x224/701-4/73/7cj-zj00-5/14-6/7Z=4.540/7524/7=300/723解对偶问题：w=245/14406/7=300/7cj244000CBYBby1y2y3y424y

15、15/1410-5/74/740y26/7012/7-3/7cj-zj0040/724/724cj4.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-y3x1x2x4x325（1）对称性：对偶问题的对偶max z=6x1+9x2s.t.x1+2x22 2x1-3x23 x1+2x2-1 x1,x20mi

16、nw=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,w204.2对偶问题的基本性质26maxZ=x1+4x2+2x3 s.t.5x1-x2+2x38 x1+3x2-3x35 x1,x2,x30minw=8y1+5y2 s.t.5y1+y21 -y1+3y24 2y1-3y2 2 y1,y20274.2 对偶问题的基本性质原始问题

17、max z=CXs.t.AXb X 0对偶问题min w=Ybs.t.AYCY 0（2）弱对偶性若X为原问题的可行解，Y为对偶问题的可行解，则恒有CXYb28推论：原问题任一可行解的目标函数是其对偶问题目标函数值的下界，反之对偶问题任一可行解的目标函数是其原问题目标函数的上界。（3）无界性 如原问题有可行解且目标函数值无界，则其对偶问题无可行解；反之对偶问题有可行解且目标函数无界，则原问题无可行解。（对偶问题无可行解时，其原问题无界解或无可行解。推论：若原问题有可行解而其对偶问题无可行解时，原问题目标函数无界 若对偶问题有可行解而其原问题无可行解时，对偶问题目标函数无界。29maxZ=x1+x

18、2 s.t.-x1+x2+x3 2 -2x1+x2+x3 1 x1,x2,x3,0minw=2y1+y2 s.t.-y1-2y2 1 y1+y2 1 y1-y2 0 y1,y20试用对偶理论证明上述线性规划问题无最优解例。已知线性规划问题例。已知线性规划问题证：首先该问题存在可行解。可知对偶问题无可行解，因原问题有可行解，故无最优解。30（4）最优性若X为原问题的可行解，Y为对偶问题的可行解，且CXYb则X，Y分别为原问题和对偶问题的最优解。（5）强对偶性若原问题和对偶问题均具有可行解，则两者均具有最优解，且他们的最优解的目标值相等。31（6）互补松弛定理在线性规划问题的最优解中，如果对应某一

19、约束条件的对偶变量值为0，则该约束条件取严格等式，既松弛变量或剩余变量为0；反之如果对应某一约束条件的对偶变量值不为0，则该约束条件取严格不等式，既松弛变量或剩余变量不为0.若yi 0,则aijxj=bi，即xsi=0若yi 0,则aijxjbi，即xsi0即xsiyi=0同理若xj 0,则aijyi=cj，即ysj=0若xj 0,则aijyicj，即ysj0即ysjxj=032maxZ=4.5x1+5x2 s.t.3x1+2x2+x3=24 4x1+5x2+x4=40 x1,x2,x3,x4,0y1y2minw=24y1+40y2 s.t.3y1+4y2-y3=4.5 2y1+5x2-y4=

20、5 y1,y2,y3,y40 x1x2X3=0,3x1+2x2=24,y1=14/5X4=0,4x1+5x2=40,y2=6/7y3=0,3y1+4y2=5,x1=40/7y4=0,2y1+5y2=5,x2=24/733利用互补松弛关系求解线性规划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=3y=6最优解为(y1,y2)=(6,0)max y=6先用图解法求解对偶

21、问题。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,y4,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

22、,y5)x2=x3=x4=0 x1=1,x5=2引进剩余变量 求对偶引进松弛变量图解法求解代入约束求出松弛变量互补松弛关系代入约束求解(x1,x2,x3,x4,x5)=(1,0,0,0,2)35第5节 对偶问题的经济解释资源的影子价格(Shadow Price)p影子价格越大，说明这种资源越是相对紧缺p影子价格越小，说明这种资源相对不紧缺p如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0 yi=w/bi=最大利润的增量/第i种资源的增量=第i种资源的边际利润w=b1y1+b2y2+biyi+bmymw+w=b1y1+b2y2+(bi+bi)yi+bmymw=biyi360 1 2

23、 3 4 5 6 7 8654321y1y2Z*=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,目标函数值将怎么变化?为什么?37资源的影子价格是一种机会成本根据互补松弛定理若yi 0,则aijxj=bi，若yi 0,则aijxjbi，某种资源bi未得到充分利用时，该种资源的影子价格为0；当资源的影子价格不为0，表示该种资源在生产中已消耗完毕。j=cj-zj=cj-CBB-1Pjcj表示第i种产品的产值，aij

24、yi表示生产该种产品所消耗各项资源的影子价格的总和，即产品的隐含成本。38Maxz=4x1+10 x2 s.t.3x1+6x25 x1+3x22 2x1+5x24 x1,x20已知原问题为：y1y2y3则对偶问题为：Minw=5y1+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,

25、5)39cj410000CBXBbx1x2x3x4x50 x35361000 x42130100 x5425001cj-zj410000初始单纯形表为：此时对偶问题的解为Y（0，0，0，4，10）代入Minw=5y1+2y2+4y3 s.t.3y1+y2+2y3-y4=4 6y1+3y2+5y3-y5=10 yi0(i=1,2,5)不是对偶问题的可行解40cj410000CBXBbx1x2x3x4x50 x35361005/60 x42130102/30 x54250014/5cj-zj410000初始单纯形表为：此时对偶问题的解为Y（0，0，0，4，10）代入Minw=5y1+2y2+4y3

26、 s.t.3y1+y2+2y3-y4=4 6y1+3y2+5y3-y5=10 yi0(i=1,2,5)不是对偶问题的可行解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）代入Minw=5y1+2y2+4y3 s.t.3y1+y2+2y3-y4=4 6y1+3y2+5y3-y5=10 yi0(i=1,2,5)不是对偶问题的可行解42对原问题进行迭代得：cj410000CBXBbx1x2x3x4x50

27、x31101-20110 x22/31/3101/3020 x52/31/300-5/312cj-zj2/300-10/30此时对偶问题的解为Y（0，10/3，0，-2/3，0）代入Minw=5y1+2y2+4y3 s.t.3y1+y2+2y3-y4=4 6y1+3y2+5y3-y5=10 yi0(i=1,2,5)不是对偶问题的可行解43对原问题进行迭代得：cj410000CBXBbx1x2x3x4x54x11101-2010 x21/301-1/3100 x51/300-1/3-11cj-zj00-2/3-20此时对偶问题的解为Y（2/3，2，0，0，0）代入Minw=5y1+2y2+4y3

28、 s.t.3y1+y2+2y3-y4=4 6y1+3y2+5y3-y5=10 yi0(i=1,2,5)是对偶问题的可行解44 单纯形法求解的过程，从对偶的观点来看，是在始终保持原始可行解的条件下，不断改进对偶可行性的过程。一个从对偶不可行的解，经过几次叠代，逐步向对偶可行解靠拢，一旦得到的解既是原始可行的，又是对偶可行的，这个解就分别是原始问题和对偶问题的最优解。45第6节 对偶单纯形法 对于对偶单纯形法刚好和单纯形法的思路相反，就是在始终保持对偶问题可行的条件下，不断改进原问题可行性的过程。一个从原问题不可行的解，经过几次叠代，逐步向原问题可行解靠拢，一旦得到的解既是原始可行的，又是对偶可行

29、的，这个解就分别是原始问题和对偶问题的最优解。46步骤：1.确定初始解一般设松弛变量为初时基可行解2.判断 若所有的基变量值均0，则此解为线性规划问题的最优解，若存在基变量的值0，则问题还没有达到最优解，需要进行改进。3.改进选择换出变量min bi/bi0假设选取xk为换出变量选择换入变量min(cj-zj)arj|arj0,cj-zj0则假设选取xl为换出变量4.迭代。使得alk1，其余aik为047Minw=5y1+2y2+4y3 s.t.3y1+y2+2y34 6y1+3y2+5y310 y1,y2,y30举例：Maxw=-5y1-2y2-4y3 s.t.-3y1-y2-2y3-4 -

30、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-400CBXBby1y2y3y4y50y4-4-3-1-2100y5-10-6-3-501cj-zj-5-2-40049cj-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

31、-40051cj-5-2-400CBXBby1y2y3y4y50y4-4-3-1-2100y5-10-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/

32、31-1/3-2y210/3215/30-1/3cj-zj-10-2/30-2/354cj-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/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

33、/30-2/3-5y12/3101/311/356cj-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-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/3c

34、j-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/3W=22/358Minw=2x1+3x2+4x3 s.t.x1+2x2+x33 2x1-x2+3x34 x1,x2,x30练习:用对偶单纯形法求解并求出对偶变量的最优解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=-3 -2x1 +x2-3x3

35、 +x5=-4 xi0(i=1,2,5)Maxz=3y1+4y2 s.t.y1+2y22 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/2-1/31-1/28/532-2x121-1/22/30-1/2cj-zj0-4-10-1-3x22/510-1/5-2/51/5-2x111/5017/5-1/5-2/5cj-zj00-3/5-8/5-1/5此时对偶问题和原问题都达到可行，所以均达到了最优解Y（11/5.2/5,0,0,

36、0)W=-28/5W=28/560Maxz=3y1+4y2 s.t.y1+2y22 2y1 -y23 y1+3y24 y1,y20Maxz=3y1+2y2 s.t.y1+2y2+y32 2y1 -y2+y43 y1+3y2+y54 yi0cj-2-3-400-3x22/510-1/5-2/51/5-2x111/5017/5-1/5-2/5cj-zj00-3/5-8/5-1/5-y3-y4-y5-y1-y261对偶单纯形法的特点：当约束条件为“”时，不需要引入人工变量，从而使计算更为简便。用对偶单纯形法求解时，目标函数必须是求极大化的。62Maxz=3x1-4x2 s.t.x1+2x22 3x1

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

38、0 x3-2-1-210000 x4-4-3-101000 x511-100100 x63110001cj-zj3-4000065cj3-40000CBXBbx1x2x3x4x5x60 x3-2-1-210000 x4-4-3-1010040 x511-100100 x63110001cj-zj3-4000066cj3-40000CBXBbx1x2x3x4x5x60 x3-2-1-210000 x4-4-3-1010040 x511-100100 x63110001cj-zj3-40000-4x24310-10067cj3-40000CBXBbx1x2x3x4x5x60 x3-2-1-2100

39、00 x4-4-3-1010040 x511-100100 x63110001cj-zj3-400000 x36501-200-4x24310-10068cj3-40000CBXBbx1x2x3x4x5x60 x3-2-1-210000 x4-4-3-1010040 x511-100100 x63110001cj-zj3-400000 x36501-200-4x24310-1000 x55400-11069cj3-40000CBXBbx1x2x3x4x5x60 x3-2-1-210000 x4-4-3-1010040 x511-100100 x63110001cj-zj3-400000 x36

40、501-200-4x24310-1000 x55400-1100 x6-1-20010170cj3-40000CBXBbx1x2x3x4x5x60 x3-2-1-210000 x4-4-3-1010040 x511-100100 x63110001cj-zj3-400000 x36501-200-4x24310-1000 x55400-1100 x6-1-200101cj-zj1500-40071cj3-40000CBXBbx1x2x3x4x5x60 x3-2-1-210000 x4-4-3-1010040 x511-100100 x63110001cj-zj3-400000 x36501-2

41、006/5-4x24310-1004/30 x55400-1105/40 x6-1-200101-cj-zj1500-40072cj3-40000CBXBbx1x2x3x4x5x60 x36501-2006/5-4x24310-1004/30 x55400-1105/40 x6-1-200101-cj-zj1500-4003x16/5101/5-2/50073cj3-40000CBXBbx1x2x3x4x5x60 x36501-2006/5-4x24310-1004/30 x55400-1105/40 x6-1-200101-cj-zj1500-4003x16/5101/5-2/500-4x2

42、2/501-3/51/50074cj3-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/51075cj3-40000CBXBbx1x2x3x4x5x60 x36501-2006/5-4x24310-1004/30 x55400-1105/40 x6-1-200101-cj-zj1500-4003x16/5101/5-2/500-4x22/501-3/51/5

43、000 x51/500-4/53/5100 x67/500-2/51/50176cj3-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-320077cj3-40000CBXBbx1x2x3x4x5x60 x36501-2006/5-4x24310-1004/30 x55400-1105/40 x6-1

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

45、51/50020 x51/500-4/53/5101/30 x67/500-2/51/5017cj-zj00-32003x14/310-1/302/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/3081cj3-40000CBXBbx1x2x3x4x5x63x16/51

46、01/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/3182cj3-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

47、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/383第7节 灵敏度分析前提条件:原线性规划问题已取得了最优解；每次只讨论一种参数的变化，而参数之间的变化互不关联。84 某厂准备用甲乙两种原料生产A，B，C，D四种产品，相关参数见表。问如何安排生产总利润为最大。ABCD可供量甲3210418乙21/23利润985019Maxz=9x1+8x2+50 x3+19x4 s.t.3x1+2x2+10 x3+4x418

48、 2x3+1/2x43 xj0(j=1,2,3,4)Maxz=9x1+8x2+50 x3+19x4 s.t.3x1+2x2+10 x3+4x4+x5=18 2x3+1/2x4+x6=3 xj0(j=1,2,6)85用单纯形法对该线性规划进行求解，得初始单纯行表和最优单纯形表cj98501900CBXBbx1x2x3x4x5x60 x51832104100 x630021/201cj-zj98501900。19x4224/3012/3-10/350 x31-1/2-1/310-1/64/3cj-zj-4-2/300-13/3-10/3Z*=88B=(P4,P3)=4 10 2B-1-y1-y2-

49、y3-y4-y5-y6867.1资源系数（右端常数项bi）发生变化的分析X=(XB,0)T其中XB=B-1bZ=CBB-1b当bi 发生变化时：bi=b+(0,bi,0)T=b+b则:XB=B-1b=B-1(b+b)=B-1b+B-1bXB+B-1b如果XB=XB+B-1b0，则原最终单纯形表中的基变量不变，基变量的值将发生变化如果XB=XB+B-1b0，则需采用对偶单纯形表进行重新求解。87假设：甲原材料的供给量从18变为6，则b=(6,3)TXB=B-1b=2/3 -10/3-1/6 4/3(6,3)T=(-6,3)T可以看出甲的供给量发生变化后，x4的值=-40，所以用对偶单纯形表求新解

50、。88cj98501900CBXBbx1x2x3x4x5x60 x5632104100 x630021/201cj-zj98501900。19x4-624/3012/3-10/350 x33-1/2-1/310-1/64/3cj-zj-4-2/300-13/3-10/389cj98501900CBXBbx1x2x3x4x5x60 x5632104100 x630021/201cj-zj98501900。19x4-624/3012/3-10/350 x33-1/2-1/310-1/64/3cj-zj-4-2/300-13/3-10/30 x69/5-3/5-2/50-3/10-1/5190cj9