第二章对偶线性规优秀课件.ppt

第二章对偶线性规第二章对偶线性规2022/10/26浙江科技学院经济管理学院管工系1第1页，本讲稿共49页本章学习要求n n掌握对偶理论及其性质掌握对偶理论及其性质掌握对偶理论及其性质掌握对偶理论及其性质n n掌握影子价格的应用掌握影子价格的应用掌握影子价格的应用掌握影子价格的应用n n掌握对偶单纯形法掌握对偶单纯形法掌握对偶单纯形法掌握对偶单纯形法n n熟悉灵敏度分析的概念和内容熟悉灵敏度分析的概念和内容熟悉灵敏度分析的概念和内容熟悉灵敏度分析的概念和内容n n掌握右侧常数，价值系数，工艺系数的变换对原最优解的影掌握右侧常数，价值系数，工艺系数的变换对原最优解的影掌握右侧常数，价值系数，工艺系数的变换对原最优解的影掌握右侧常数，价值系数，工艺系数的变换对原最优解的影响响响响n n掌握增加新变量和增加新约束条件对原最优解的影响，并求出掌握增加新变量和增加新约束条件对原最优解的影响，并求出掌握增加新变量和增加新约束条件对原最优解的影响，并求出掌握增加新变量和增加新约束条件对原最优解的影响，并求出相应因素的灵敏度范围相应因素的灵敏度范围相应因素的灵敏度范围相应因素的灵敏度范围第2页，本讲稿共49页2.1线性规划的对偶问题n问题的提出问题的提出n对称形式下对偶问题的一般形式对称形式下对偶问题的一般形式n非对称形式下的原问题与对偶问题的关系非对称形式下的原问题与对偶问题的关系第3页，本讲稿共49页一、对偶问题的提出每一个每一个每一个每一个LPLP问题，都伴随着另一个问题，都伴随着另一个问题，都伴随着另一个问题，都伴随着另一个LPLP，而且二者有密切关系，互为对偶，而且二者有密切关系，互为对偶，而且二者有密切关系，互为对偶，而且二者有密切关系，互为对偶，另其中一个问题为原问题，另一个问题为对偶问题，只要得到了其中一另其中一个问题为原问题，另一个问题为对偶问题，只要得到了其中一另其中一个问题为原问题，另一个问题为对偶问题，只要得到了其中一另其中一个问题为原问题，另一个问题为对偶问题，只要得到了其中一个问题的解（目标值），也得到另一问题的解，因此通常只求解一个问个问题的解（目标值），也得到另一问题的解，因此通常只求解一个问个问题的解（目标值），也得到另一问题的解，因此通常只求解一个问个问题的解（目标值），也得到另一问题的解，因此通常只求解一个问题就可以了。题就可以了。题就可以了。题就可以了。例例例例1 1：（美佳公司）：（美佳公司）：（美佳公司）：（美佳公司）美佳公司应如何生产安排，使已有美佳公司应如何生产安排，使已有美佳公司应如何生产安排，使已有美佳公司应如何生产安排，使已有资源利润最大化。资源利润最大化。资源利润最大化。资源利润最大化。某公司至少该出多大代价，某公司至少该出多大代价，某公司至少该出多大代价，某公司至少该出多大代价，使美佳公司愿意放弃自己的使美佳公司愿意放弃自己的使美佳公司愿意放弃自己的使美佳公司愿意放弃自己的资源，资源，资源，资源，产品资源资源约束A0515B6224调试工序115单位产品利润21产品资源AB调试工序单位资源利润06125211资源量15245第4页，本讲稿共49页数学模型Cj21000CBXBbx1x2x3x4x50 x3 15/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2j000-1/4-1/2cj-15-24-500-MCBYBby1y2y3y4y5y6-My62061-1011/3-15y11/512/51/50-1/505/2j06M-18 M-2-M-30-24y21/3011/6-1/601/62-15y11/5102/151/15-1/5-1/151/2j001-3-3-M+8-24y21/4-5/410-1/41/41/2-5y31/215/2011/2-3/2-3j-15/200-7/2-3/2-M-3Z*=8.5W*=8.5第5页，本讲稿共49页二、对偶问题的一般形式 一般认为变量均为非负约束的情况下，约束条件在目标函数取Max时均取“”号；当目标函数求Min值时均取“号。则称这些线性规划问题具有对称性。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 X0Minw=Yb s.t.AYC Y0第6页，本讲稿共49页原问题max z=CXs.t.AXb X 0对偶问题min w=Ybs.t.AYCY 0maxbC CC CATbminmnmnA第7页，本讲稿共49页举例：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第一种资源第二种资源第三种资源第一种产品 第二种产品x1x2第8页，本讲稿共49页原始问题为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个约束原始问题的变量全部为非负第9页，本讲稿共49页对偶问题的对偶max z=6x1+9x2s.t.x1+2x22 2x1-3x23 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第10页，本讲稿共49页对偶问题的性质总结对偶的对偶就是原始问题max z=CXmax z=CXs.t.AXs.t.AX b b X 0 X 0min w=Ybs.t.ATY CY0对偶的定义max u=CWs.t.AWCW 0第11页，本讲稿共49页maxZ=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,y20第12页，本讲稿共49页三、非对称形式的原对偶问题minz=2x1+3x2-5x3+x4 s.t.x1+x2-3x3+x45 2x1 +2x3-x44 x2+x3+x4=6 x10,x2,x30minz=-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 y1+y2+(y3-y3”)1 -y1-y2-(y3-y3”)-1 y1,y2,y3,y3”0写出对偶问题maxw=5y1+4y2+6y3 s.t.y1+2y2 2 y1 +y3 3 -3y1+2y2+y3 -5 y1 -y2 +y3 =1 y10,y20,y3无约束第13页，本讲稿共49页结论结论LP(LD)MaxMaxX0X0X0X0X X无约束无约束无约束无约束St St st st St=St=LD(LP)MinMinst st St St St=St=Y0Y0Y0Y0Y Y无约束无约束无约束无约束第14页，本讲稿共49页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:Freep原始问题变量的个数(3)等于对偶问题约束条件的个数(3)；p原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。p原始问题变量的性质影响对偶问题约束条件的性质。p原始问题约束条件的性质影响对偶问题变量的性质。写对偶问题的练习（1）第15页，本讲稿共49页写对偶问题的练习（2）原始问题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 +5y33 y1 3y2-y3-2 y10,y20,y3:Free对偶问题第16页，本讲稿共49页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+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+3y34 y10,y20第17页，本讲稿共49页课后作业P74 2.1(4)第18页，本讲稿共49页2.2 对偶问题的基本性质n单纯形法的矩阵描述单纯形法的矩阵描述n对偶问题的基本性质对偶问题的基本性质第19页，本讲稿共49页一、单纯形法计算的矩阵描述Max Z=CX AXb X0Max Z=CX AX+Xs=b X 0,Xs0引入松弛变量令X=(XB,XN)T C=(CB,CN)A=(B,N)BXBXB B+NX+NXNN+X+XS S=b=bB B-1-1BXBXB B+B+B-1-1NXNXNN+B+B-1-1X XS S=B=B-1-1b bX XB B=B=B-1-1b-Bb-B-1-1NXNXNN-B-B-1-1X XS S MaxZ=CB B(B B-1-1b-Bb-B-1-1NXNXNN-B-B-1-1X XS S)+C)+CNNX XNN =CB BB B-1-1b b（C CNN-CB BB B-1-1N)XN)XNN-CB BB B-1-1X XS S第20页，本讲稿共49页某一决策变量某一决策变量某一决策变量某一决策变量x x x xk k k k系数列向量迭代前为系数列向量迭代前为系数列向量迭代前为系数列向量迭代前为P P P Pk k k k，迭代后为，迭代后为，迭代后为，迭代后为B B B B-1-1-1-1P P P Pk k k k。当当当当B B B B为最优基时为最优基时为最优基时为最优基时MaxZ=CB BB B-1-1b b（C CNN-CB BB B-1-1N)XN)XNN-CB BB B-1-1X XS S令令令令Y=CY=CY=CY=CB BB B B B-1-1由此可以看出，当由此可以看出，当由此可以看出，当由此可以看出，当X X X X为最优解时，为最优解时，为最优解时，为最优解时，Y Y Y Y为对偶问题的可行解。为对偶问题的可行解。为对偶问题的可行解。为对偶问题的可行解。且该可行解对应的目标函数值且该可行解对应的目标函数值且该可行解对应的目标函数值且该可行解对应的目标函数值W=Yb=CX*W=Yb=CX*第21页，本讲稿共49页非基变量基变量XBXNXs0XsbBNIcj-zjCBCN0基变量非基变量XBXNXsCBXBB-1bIB-1NB-1cj-zj0CN-CBB-1N-CBB-1 对应初始单纯形表中的单位矩阵对应初始单纯形表中的单位矩阵对应初始单纯形表中的单位矩阵对应初始单纯形表中的单位矩阵I I I I，迭代后的单纯形表中为，迭代后的单纯形表中为，迭代后的单纯形表中为，迭代后的单纯形表中为B B B B-1-1-1-1；初始单纯形表中基变量初始单纯形表中基变量初始单纯形表中基变量初始单纯形表中基变量Xs=bXs=bXs=bXs=b，迭代后的表中为，迭代后的表中为，迭代后的表中为，迭代后的表中为X X X XB B B B=B=B=B=B-1-1-1-1b b b b；约束矩阵（约束矩阵（约束矩阵（约束矩阵（A A A A，I I I I）（）（）（）（B B B B，N N N N，I I I I），迭代后为），迭代后为），迭代后为），迭代后为（B B B B-1-1-1-1B B B B，B B B B-1-1-1-1N N N N，B B B B-1-1-1-1I I I I）（）（）（）（I I I I，B B B B-1-1-1-1N N N N，B B B B-1-1-1-1)；初始单纯形表中初始单纯形表中初始单纯形表中初始单纯形表中x x x xj j j j的系数向量为的系数向量为的系数向量为的系数向量为P P P Pj j j j，迭代后为，迭代后为，迭代后为，迭代后为P P P Pj j j j，且，且，且，且P P P Pj j j j=B=B=B=B-1-1-1-1P P P Pj j j j。第22页，本讲稿共49页二、对偶问题的基本性质原始问题max z=CXs.t.AXb X 0对偶问题min w=Ybs.t.AY CY 01.1.弱对偶性弱对偶性弱对偶性弱对偶性若若若若X X0 0为原问题的可行解，为原问题的可行解，为原问题的可行解，为原问题的可行解，Y Y0 0为对偶问题的可行解，则恒有为对偶问题的可行解，则恒有为对偶问题的可行解，则恒有为对偶问题的可行解，则恒有CXCX0 0YY0 0bb证明：证明：证明：证明：X X0 0 0 0为为为为LPLP的可行解，的可行解，的可行解，的可行解，Y Y0 0 0 0为为为为LDLD的可行解，则有：的可行解，则有：的可行解，则有：的可行解，则有：AX AX0 0 b A b A Y Y0 0 C C Y Y0 0AXAX0 0 Y Y0 0b (Ab (A Y Y0 0)X)X0 0 (C)X (C)X0 0 Y Y0 0b Yb Y0 0AXAX0 0 CX CX0 0第23页，本讲稿共49页推论推论推论推论:(LP-Max LD-Min):(LP-Max LD-Min)1.LP1.LP任一可行解的目标函数是其任一可行解的目标函数是其任一可行解的目标函数是其任一可行解的目标函数是其LDLD目标函数值的下界，目标函数值的下界，目标函数值的下界，目标函数值的下界，反之反之反之反之LDLD任一可行解的目标函数是其任一可行解的目标函数是其任一可行解的目标函数是其任一可行解的目标函数是其LPLP目标函数的上界。目标函数的上界。目标函数的上界。目标函数的上界。Z=CXMaxZ=MinW YbZ=CXMaxZ=MinW Yb2.2.如如如如LPLP有可行解且目标函数值有可行解且目标函数值有可行解且目标函数值有可行解且目标函数值无界无界无界无界，则其，则其，则其，则其LDLD无可行解无可行解无可行解无可行解；反之反之反之反之LDLD有可行解且目标函数有可行解且目标函数有可行解且目标函数有可行解且目标函数无界无界无界无界，则，则，则，则LPLP无可行解无可行解无可行解无可行解。(对偶问题无可行解时，其原问题无界解或无可行解。对偶问题无可行解时，其原问题无界解或无可行解。对偶问题无可行解时，其原问题无界解或无可行解。对偶问题无可行解时，其原问题无界解或无可行解。)Z=CXZ=CX+Yb W=Yb+Yb W=Yb-CX-CX3.3.若若若若LPLP有可行解而其有可行解而其有可行解而其有可行解而其LDLD无可行解时，无可行解时，无可行解时，无可行解时，LPLP目标函数目标函数目标函数目标函数无界无界无界无界反之，若反之，若反之，若反之，若LDLD有可行解而其有可行解而其有可行解而其有可行解而其LPLP无可行解时，无可行解时，无可行解时，无可行解时，LDLD目标函数目标函数目标函数目标函数无界无界无界无界。第24页，本讲稿共49页2.2.最优性最优性最优性最优性若若若若X X0 0为为为为LPLP的可行解，的可行解，的可行解，的可行解，Y Y0 0为为为为LDLD的可行解，且的可行解，且的可行解，且的可行解，且CXCX0 0Y Y0 0b,b,则则则则X X0 0，Y Y0 0分别为分别为分别为分别为LPLP和和和和LDLD的最优解。的最优解。的最优解。的最优解。证明：设证明：设证明：设证明：设LPLP的最优解为的最优解为的最优解为的最优解为X*,LDX*,LD的最优解为的最优解为的最优解为的最优解为Y*Y*又因为：又因为：又因为：又因为：CX*CXCX*CX0 0=Y=Y0 0b Y*bb Y*b又由弱对偶性定理：又由弱对偶性定理：又由弱对偶性定理：又由弱对偶性定理：CX YbCX Yb则则则则X X0 0必为必为必为必为X*,YX*,Y0 0必为必为必为必为Y*Y*3.3.强对偶性强对偶性强对偶性强对偶性若原问题和对偶问题均具有可行解，则两者均具有最优解，若原问题和对偶问题均具有可行解，则两者均具有最优解，若原问题和对偶问题均具有可行解，则两者均具有最优解，若原问题和对偶问题均具有可行解，则两者均具有最优解，且他们的最优解的目标值相等。且他们的最优解的目标值相等。且他们的最优解的目标值相等。且他们的最优解的目标值相等。第25页，本讲稿共49页4.4.互补松弛定理互补松弛定理互补松弛定理互补松弛定理如果如果如果如果X*,Y*X*,Y*分别为分别为分别为分别为LP,LDLP,LD问题的可行解，则问题的可行解，则问题的可行解，则问题的可行解，则X*,Y*X*,Y*为最优解的充为最优解的充为最优解的充为最优解的充要条件为：要条件为：要条件为：要条件为：Y*XY*XS S*=0*=0Y YS S*X*=0*X*=0 当当当当LPLP中第中第中第中第i i个约束是严格不等式，则个约束是严格不等式，则个约束是严格不等式，则个约束是严格不等式，则Y Y中的中的中的中的YiYi必为必为必为必为0 0，如果，如果，如果，如果YiYi不为不为不为不为0,0,则则则则LPLP中第中第中第中第i i个约束为严格等式。个约束为严格等式。个约束为严格等式。个约束为严格等式。当当当当LDLD中第中第中第中第j j个约束是严格不等式，则个约束是严格不等式，则个约束是严格不等式，则个约束是严格不等式，则X X中的中的中的中的xjxj必为必为必为必为0 0，如果，如果，如果，如果xjxj不为不为不为不为0,0,则则则则LDLD中第中第中第中第j j个约束为严格等式。个约束为严格等式。个约束为严格等式。个约束为严格等式。第26页，本讲稿共49页课堂作业P74 2.3课后作业(P75-P76)2.4 2.5 2.6 2.7第27页，本讲稿共49页2.3 影子价格阐述对偶变量的经济意义，即对偶变量的经济解释阐述对偶变量的经济意义，即对偶变量的经济解释引例：美佳公司引例：美佳公司如果已知如果已知LP的的X*=(7/2,3/2,15/2,0,0)Z*=8.5求解求解Y*,W*？由对偶问题的基本性质知：由对偶问题的基本性质知：W*=Z*=8.5 15Y1+24y2+5y3=8.5又因为又因为Y*XS*=0 X*代入代入LP的的约束条件中，知约束条件中，知为严格不等式，为严格不等式，则则xS10，则，则y1=0由互补松弛定理：由互补松弛定理：因为因为YS*X*=0 X10,X20则则yS1*=0,yS2*=0，即，即LD的的，为严格等式为严格等式6y2+y3=25y1+2y2+y3=1 Y Y1=0=0 Y Y2=1/4=1/4 y y3=1/2=1/2第28页，本讲稿共49页1.1.定理：根据对偶问题的基本性质定理：根据对偶问题的基本性质定理：根据对偶问题的基本性质定理：根据对偶问题的基本性质对对对对LPLP为生产问题而言：为生产问题而言：为生产问题而言：为生产问题而言：bi bi表示表示表示表示LPLP中第中第中第中第i i种资源的拥有量；种资源的拥有量；种资源的拥有量；种资源的拥有量；Cj Cj表示第表示第表示第表示第j j种产品的利润或产值种产品的利润或产值种产品的利润或产值种产品的利润或产值其中其中其中其中Yi*Yi*可用下面数学式求得：可用下面数学式求得：可用下面数学式求得：可用下面数学式求得：1 1）yi*yi*可解释为第可解释为第可解释为第可解释为第i i种资源的边际价格，即在其他条件不变的情况下，只增加单位第种资源的边际价格，即在其他条件不变的情况下，只增加单位第种资源的边际价格，即在其他条件不变的情况下，只增加单位第种资源的边际价格，即在其他条件不变的情况下，只增加单位第i i种种种种资源所引起的目标函数最优值的变化，资源所引起的目标函数最优值的变化，资源所引起的目标函数最优值的变化，资源所引起的目标函数最优值的变化，bibibi+1,bi+1,bi=1bi=1，Z*Z*的值为的值为的值为的值为yi*yi*。2 2）yi*yi*也可解释为出让单位第也可解释为出让单位第也可解释为出让单位第也可解释为出让单位第i i种资源的收益；种资源的收益；种资源的收益；种资源的收益；3 3）yi*yi*的取值随的取值随的取值随的取值随cj,xj,Aijcj,xj,Aij的变化而变化，因此企业不同，产业不同，资源拥有量的变化而变化，因此企业不同，产业不同，资源拥有量的变化而变化，因此企业不同，产业不同，资源拥有量的变化而变化，因此企业不同，产业不同，资源拥有量不同，不同，不同，不同，yi*yi*的值不同，是具体企业，具体产品和具体资源拥有量的特定价格。的值不同，是具体企业，具体产品和具体资源拥有量的特定价格。的值不同，是具体企业，具体产品和具体资源拥有量的特定价格。的值不同，是具体企业，具体产品和具体资源拥有量的特定价格。第29页，本讲稿共49页例：美佳公司例：美佳公司X*=(7/2,3/2,15/2,0,0)Z*=8.5由由1）可知：）可知：y1*为为变为变为5x216时时Z*的增量，的增量，y1*Z*0Y2*为为变为变为6x12x225时时Z*的增量的增量所以当所以当A的资源增加时，的资源增加时，Z*无变化，无变化，Y1*0LP中中约束为严格的不等式，表明约束为严格的不等式，表明A没有被充分利用。没有被充分利用。第30页，本讲稿共49页2.2.影子价格的应用（对偶问题的应用）影子价格的应用（对偶问题的应用）影子价格的应用（对偶问题的应用）影子价格的应用（对偶问题的应用）1 1）yi*yi*实际上是一种机会成本，当实际上是一种机会成本，当实际上是一种机会成本，当实际上是一种机会成本，当A A的单位市场价格无论多低时，还应卖出的单位市场价格无论多低时，还应卖出的单位市场价格无论多低时，还应卖出的单位市场价格无论多低时，还应卖出A A资源，直到资源，直到资源，直到资源，直到15/215/2；当；当；当；当B B的单位市场价格的单位市场价格的单位市场价格的单位市场价格1/40Yi*0表明该资源已充分利用，因此该资源的增加或减少均会引表明该资源已充分利用，因此该资源的增加或减少均会引表明该资源已充分利用，因此该资源的增加或减少均会引表明该资源已充分利用，因此该资源的增加或减少均会引起起起起Z*Z*的变动，的变动，的变动，的变动，Yi*Yi*越大，变动越大。越大，变动越大。越大，变动越大。越大，变动越大。由美佳可得：由美佳可得：由美佳可得：由美佳可得：Y1=0Y1=0表明表明表明表明A A没有充分利用，没有充分利用，没有充分利用，没有充分利用，y2=1/4,y3=1/2y2=1/4,y3=1/2表明表明表明表明y3y3的变动对美佳公司利的变动对美佳公司利的变动对美佳公司利的变动对美佳公司利益的影响要大。益的影响要大。益的影响要大。益的影响要大。3 3）新产品是否投产以及合理定价的问题）新产品是否投产以及合理定价的问题）新产品是否投产以及合理定价的问题）新产品是否投产以及合理定价的问题例：美佳考虑生产例：美佳考虑生产例：美佳考虑生产例：美佳考虑生产电器电器电器电器，要耗，要耗，要耗，要耗A 3 A 3，B 2B 2，调试，调试，调试，调试1 1个单位，市场价格个单位，市场价格个单位，市场价格个单位，市场价格2 2元，问是否值得元，问是否值得元，问是否值得元，问是否值得生产。又如果美佳决定生产该种产品，则要定价多少该公司才不会亏本。生产。又如果美佳决定生产该种产品，则要定价多少该公司才不会亏本。生产。又如果美佳决定生产该种产品，则要定价多少该公司才不会亏本。生产。又如果美佳决定生产该种产品，则要定价多少该公司才不会亏本。第31页，本讲稿共49页4 4）合理调配资源）合理调配资源）合理调配资源）合理调配资源因为影子价格是资源在特点环境下的价值，随环境的变化而变化，同一资源在有因为影子价格是资源在特点环境下的价值，随环境的变化而变化，同一资源在有因为影子价格是资源在特点环境下的价值，随环境的变化而变化，同一资源在有因为影子价格是资源在特点环境下的价值，随环境的变化而变化，同一资源在有些使用中价值低，有些使用中价值高。些使用中价值低，有些使用中价值高。些使用中价值低，有些使用中价值高。些使用中价值低，有些使用中价值高。例：美佳公司有两个子公司例：美佳公司有两个子公司例：美佳公司有两个子公司例：美佳公司有两个子公司（1 1）A A0 0 B B 1/41/4 C C 1/21/2(2)A(2)A2 2 B B 0 0 C C 1 1因此：因此：因此：因此：（1 1）（2 2）A A A A B B B B C C C C第32页，本讲稿共49页课后作业P76 2.8第33页，本讲稿共49页2.4 对偶单纯形法一、基本思路一、基本思路从从LP的一个基解出发，转换到另一个基解；在转换过程中，的一个基解出发，转换到另一个基解；在转换过程中，保持对应的保持对应的LD的解的解Y的可行性（相当于的可行性（相当于LP的的j0），逐），逐步消除该基解的不可行性，直到基解变成可行解，就获步消除该基解的不可行性，直到基解变成可行解，就获得了最优解。得了最优解。注：该方法不是求解注：该方法不是求解注：该方法不是求解注：该方法不是求解LDLD的单纯形法，而是利用对偶关系求解的单纯形法，而是利用对偶关系求解的单纯形法，而是利用对偶关系求解的单纯形法，而是利用对偶关系求解LPLP的另一种方法。的另一种方法。的另一种方法。的另一种方法。第34页，本讲稿共49页二、计算步骤：二、计算步骤：二、计算步骤：二、计算步骤：1.1.假定已给一对偶可行基单位阵假定已给一对偶可行基单位阵假定已给一对偶可行基单位阵假定已给一对偶可行基单位阵B B（对应（对应（对应（对应LDLD问题的解可行），相应的基问题的解可行），相应的基问题的解可行），相应的基问题的解可行），相应的基解解解解X XB Bb b。2.2.若若若若b b的各个分量均非负，则这个解就是最优解，停止迭代。的各个分量均非负，则这个解就是最优解，停止迭代。的各个分量均非负，则这个解就是最优解，停止迭代。的各个分量均非负，则这个解就是最优解，停止迭代。3.3.如果如果如果如果X XB B有分量有分量有分量有分量x xl l00，且，且，且，且x xl l所在行的所有系数所在行的所有系数所在行的所有系数所在行的所有系数a alj lj00，则，则，则，则LPLP无可行解，停止迭无可行解，停止迭无可行解，停止迭无可行解，停止迭代代代代。如果如果如果如果X XB B有分量有分量有分量有分量x xl l00，且该分量所在行的系数，且该分量所在行的系数，且该分量所在行的系数，且该分量所在行的系数a alj lj有负分量，则该解不是有负分量，则该解不是有负分量，则该解不是有负分量，则该解不是LPLP的最优解，继续。的最优解，继续。的最优解，继续。的最优解，继续。4.4.如果如果如果如果min bmin bi i/b/bi i00b bl l，则，则，则，则x xl l为换出变量为换出变量为换出变量为换出变量 minmin j j/a alj lj|al|alj j0=0=k k/a alklk,则则则则x xk k为换入变量为换入变量为换入变量为换入变量5.5.以以以以a alklk为主元，进行系数行变换，得一新的对偶可行基解为主元，进行系数行变换，得一新的对偶可行基解为主元，进行系数行变换，得一新的对偶可行基解为主元，进行系数行变换，得一新的对偶可行基解(也称正则解），转第也称正则解），转第也称正则解），转第也称正则解），转第2 2步。步。步。步。第35页，本讲稿共49页比较比较比较比较单纯形法单纯形法单纯形法单纯形法和和和和对偶单纯形法对偶单纯形法对偶单纯形法对偶单纯形法单纯形法：单纯形法：单纯形法：单纯形法：先从基解、可行解出发，通过若干次迭代使满足先从基解、可行解出发，通过若干次迭代使满足j0对偶单纯形法对偶单纯形法对偶单纯形法对偶单纯形法:先从基解，先从基解，对偶可行解（等价于对偶可行解（等价于j0）出发，再通）出发，再通过若干次迭代使之可行。过若干次迭代使之可行。对偶单纯形法的优缺点：对偶单纯形法的优缺点：对偶单纯形法的优缺点：对偶单纯形法的优缺点：优点优点优点优点:初始基解可为负，减少人工变量数量，使计算简单；灵敏初始基解可为负，减少人工变量数量，使计算简单；灵敏度分析时使用方便。度分析时使用方便。缺点：缺点：缺点：缺点：不能保证所有的不能保证所有的Lp问题的初始单纯形表中的问题的初始单纯形表中的j0。第36页，本讲稿共49页例:cj-2-3-400CBXBbx1x2x3x4x50X4-3-1-2-1100 x5-4-21-301j-2-3-400 1 14/34/3 0 x4-2x11 12 2-1/2 3/20-1/2-10-5/2 1/21-1/2j0-2-10-1 4/54/52 2-3 x2-2x1 1 12/50-1/5-2/5 1/511/5107/5-1/5-2/5j00-9/5-8/5-1/5所以：所以：所以：所以：X*=(xX*=(xX*=(xX*=(x1 1 1 1,x,x,x,x2 2 2 2)T T T T=(11/5,2/5)=(11/5,2/5)=(11/5,2/5)=(11/5,2/5)T T T T Z*=28/5 Z*=28/5 Z*=28/5 Z*=28/5第37页，本讲稿共49页课后作业2.9（1）第38页，本讲稿共49页2.5 灵敏度分析nCj变化时变化时nbi变化时变化时n增加一个变量增加一个变量xj时时n增加一个约束条件时增加一个约束条件时n技术系数技术系数Pj发生变化时发生变化时第39页，本讲稿共49页LP变化导致的变化可分为：变化导致的变化可分为：X*不变，不变，Z*改变改变X*中基变量不变，取值改变，中基变量不变，取值改变，Z*改变。改变。X*中基变量改变，中基变量改变，Z*改变改变X XB BX XNNX XS SX XS SB BNNI Ib bX XB BI IB B-1-1NNB B-1-1B B-1-1b b 0 0C CNN-C-CB BB B-1-1NN-C-CB BB B-1-1第40页，本讲稿共49页一、分析一、分析cj变化变化1.当当CNj发生变化时，发生变化时，对应的对应的 Nj变化变化变化变化 Nj0 X*,Z*不变不变 Nj0 用单纯形法进行基变换用单纯形法进行基变换X XB BX XNNX XS SX XS SB BNNI Ib bX XB BI IB B-1-1NNB B-1-1B B-1-1b b 0 0C CNN-C-CB BB B-1-1NN-C-CB BB B-1-12.当当CBi发生变化时，发生变化时，所有所有 Nj变化变化变化变化 Nj0 X*不变不变,Z*变化变化 Nj0 用单纯形法进行基变换用单纯形法进行基变换第41页，本讲稿共49页例5：美佳公司1.当当C1由由2变为变为1.5时，时，当当C2由由1变为变为2时，最优解有什么变化？时，最优解有什么变化？2.当当C1不变，不变，C2在什么范围内变换时，最优解不变？在什么范围内变换时，最优解不变？Cj21000CBXBbx1x2x3x4x50 x3 15/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2j000-1/4-1/2解：解：1CjCj1.51.52 20 00 00 0CBCBXBXBb bx1x1x2x2x3x3x4x4x5x50 0 x4x46 60 00 04/54/51 1-6-61.51.5x1x12 21 10 0-1/5-1/50 01 12 2x2x23 30 01 11/51/50 00 0 j j0 00 0-1/10-1/100 0-3/2-3/21.51.51/8-9/4 22解：解：2Cj21000CBXBbx1x2x3x4x50 x3 15/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2j000-1/4-1/2c2c2454 4=（c c2 2-2-2）/40/405 5=（2 23c3c2 2）/2/2 02/32/32/32/3c c2 2 2 22222第42页，本讲稿共49页二、分析二、分析bi变化变化该变化只会引起右侧常数的变化：该变化只会引起右侧常数的变化：该变化只会引起右侧常数的变化：该变化只会引起右侧常数的变化：B B-1-1b0 b0 则基变量不变，则基变量不变，则基变量不变，则基变量不变，X*X*的取值变化，的取值变化，的取值变化，的取值变化，Z*Z*变化变化变化变化B B-1-1b b 0 0 用对偶单纯形法进行基变换用对偶单纯形法进行基变换用对偶单纯形法进行基变换用对偶单纯形法进行基变换X XB BX XNNX XS SX XS SB BNNI Ib bX XB BI IB B-1-1NNB B-1-1B B-1-1b b 0 0C CNN-C-CB BB B-1-1NN-C-CB BB B-1-1第43页，本讲稿共49页例6：美佳公司1.当其他能力不变，当其他能力不变，B设备由设备由24变为变为32时，最优解有什么变化？时，最优解有什么变化？2.当当A,B不变，调试工序能力在什么范围内变换时，基变量不变？不变，调试工序能力在什么范围内变换时，基变量不变？Cj21000CBXBbx1x2x3x4x50 x3 35/235/20015/4-15/22x1 11/211/21001/4-1/21x2-1/2-1/2010-1/43/2j000-1/4-1/2解：解：1：CjCj2 21 10 00 00 0CBCBXBXBb bx1x1x2x2x3x3x4x4x5x50 0 x3x315150 05 51 10 00 02 2x1x15 51 11 10 00 01 10 0 x4x42 20 0-4-40 01 1-6-6 j j0 0-1-10 00 0-2-2 解：解：24444b b3 3 3 36666第44页，本讲稿共49页三、增加一个变量三、增加一个变