第二章对偶理念及灵敏度分析优秀PPT.ppt

《第二章对偶理念及灵敏度分析优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第二章对偶理念及灵敏度分析优秀PPT.ppt（86页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章对偶理念及灵敏度分析第一页，本课件共有86页一、问 题 的 提 出例一、资源的合理利用问题 已知资料如表所示，问应如何安排生产计划使得既能充分利用现有资源有使总利润最大？第二页，本课件共有86页一、问 题 的 提 出1810单件利润单件利润150（设备）（设备）51C100（煤炭）（煤炭）32B170（钢材）（钢材）25A资源限制资源限制乙乙甲甲单件单件产产消耗消耗品品资源资源第三页，本课件共有86页下面从另一个角度来讨论这个问题：下面从另一个角度来讨论这个问题：假定：该厂的决策者不是考虑自己生产甲、乙两种产假定：该厂的决策者不是考虑自己生产甲、乙两种产品，而是将厂里的现有资源用于接受外

2、来加工任务，只品，而是将厂里的现有资源用于接受外来加工任务，只收取加工费。试问该决策者应制定怎样的收费标准（收收取加工费。试问该决策者应制定怎样的收费标准（收费的最底线）？费的最底线）？第四页，本课件共有86页第五页，本课件共有86页一、问 题 的 提 出该问题的数学模型为：该问题的数学模型为：第六页，本课件共有86页模型对比请总结规律第七页，本课件共有86页1 1、对称型对偶问题：已知、对称型对偶问题：已知P，写出写出 D。（一）、对偶问题的形式（一）、对偶问题的形式二、线性规划的对偶理论第八页，本课件共有86页原问题：max z=2x1+3x2 s.t 2x1+2x212 x1+2x28

3、4x1 16 4x212 x10 x20对偶问题：min w=12y1+8y2+16 y2+12y4 s.t 2y1+1y2+4 y3+0y4 2 2y1+2y2+0 y3+4y4 3 y1,y2,y3,y40 非对称型对偶问题如何求解？非对称型对偶问题如何求解？第九页，本课件共有86页对偶问题的其变换形式归纳如下对偶问题的其变换形式归纳如下原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数 max目标函数目标函数 min约约束束条条件件m个个m个个变变量量0000=无约束无约束变变量量n个个n个个约约束束条条件件0000无约束无约束=约束条件右端

4、项约束条件右端项目标函数变量的系数目标函数变量的系数目标函数变量的系数目标函数变量的系数约束条件右端项约束条件右端项变向变向变向变向大约束，小变量大约束，小变量第十页，本课件共有86页例一、写出线性规划问题的对偶问题例一、写出线性规划问题的对偶问题第十一页，本课件共有86页例二、原问题例二、原问题第十二页，本课件共有86页例三：第十三页，本课件共有86页例四、例四、原问题原问题第十四页，本课件共有86页对偶问题对偶问题第十五页，本课件共有86页例五、线性规划问题如下：例五、线性规划问题如下：第十六页，本课件共有86页第十七页，本课件共有86页练习：练习：第十八页，本课件共有86页第十九页，本课

5、件共有86页（二）、对偶问题的性质1 1、对称性定理：对偶问题的对偶是原问题。、对称性定理：对偶问题的对偶是原问题。以下讨论仅就以下讨论仅就“对称形式对称形式”讨论。讨论。因其他形式都可以转化成因其他形式都可以转化成“对称形式对称形式”，故所有结论适用于所有形式。，故所有结论适用于所有形式。第二十页，本课件共有86页2 2、弱对偶原理（弱对偶性）：设、弱对偶原理（弱对偶性）：设 和和 分别是问题（分别是问题（P）和（和（D）的可行解，则必有的可行解，则必有 推论推论.若若 和和 分别是问题（分别是问题（P P）和（和（D D）的可行解，的可行解，则则 是（是（D D）的目标函数最小值的一个下界

6、；的目标函数最小值的一个下界；是是（P P）的目标函数最大值的一个上界。的目标函数最大值的一个上界。第二十一页，本课件共有86页推论推论.在一对对偶问题（在一对对偶问题（P）和（和（D）中，若其中，若其中一个问题可行但目标函数无界，则另一个问题不中一个问题可行但目标函数无界，则另一个问题不可行；反之不成立。这也是对偶问题的无界性。可行；反之不成立。这也是对偶问题的无界性。关于无界性有如下结论：关于无界性有如下结论：问题无界问题无界无可无可行解行解无可无可行解行解问题无界问题无界对偶问题对偶问题原问题原问题第二十二页，本课件共有86页 3 3、最优性判别定理：、最优性判别定理：若若 X*和和Y*

7、分别是分别是 P和和D 的可行解且的可行解且 CX*=Y*b，则则X*.Y*分别是问题分别是问题 P和和D 的最优解。的最优解。下面来求原问题和对偶问题的最优解：下面来求原问题和对偶问题的最优解：第二十三页，本课件共有86页CjCBCN0系数系数基基XBXNXSCBXBB-1bIB-1NB-1Z=CBB-1b0CN-CBB-1N-CBB-1C-CBB-1A0最优解的判定条件是：最优解的判定条件是：-CBB-10CBB-10令令Y=CBB-1-CBB-10由由C-CBB-1A0则则CBB-1AC即即YAC即即AYCW=Yb=CBB-1b=CBX=Z则则Y0则则Y0第二十四页，本课件共有86页4

8、4、对偶定理（强对偶性）：、对偶定理（强对偶性）：若一对对偶问题若一对对偶问题 P和和D 都有可行解，则它们都有都有可行解，则它们都有最优解，且目标函数的最优值必相等。最优解，且目标函数的最优值必相等。推论（推论（3 3）.若若 P和和D的任意一个有最优解，则的任意一个有最优解，则另一个也有最优解，且目标函数的最优值相等。另一个也有最优解，且目标函数的最优值相等。推论（推论（4）.在一对对偶问题（在一对对偶问题（P）和（和（D）中，中，若一个可行若一个可行，而另一个不可行而另一个不可行，则该可行的问题无则该可行的问题无界。界。原问题有最优解，则对偶问题只少有一个可行解原问题有最优解，则对偶问题

9、只少有一个可行解。并且这一解即为对偶问题的最优解。并且这一解即为对偶问题的最优解。第二十五页，本课件共有86页综上所述，一对对偶问题的关系，只能有下综上所述，一对对偶问题的关系，只能有下面三种情况之一出现：面三种情况之一出现：.都有可行解，都有最优解，分别设为都有可行解，都有最优解，分别设为X*和和Y*，则必有则必有CX*=Y*b；.一个问题无界，则另一个问题无可行解；一个问题无界，则另一个问题无可行解；.两个都无可行解。两个都无可行解。第二十六页，本课件共有86页 5 5、互补松弛定理：、互补松弛定理：在线性规划问题的最优解中，在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零

10、，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；则该约束条件取严格等式；如果约束条件取严格不等式，则其对应的对如果约束条件取严格不等式，则其对应的对偶变量一定为零。偶变量一定为零。严格不等式约束称为松约束，严格不等式约束称为松约束，而把严格等式约束称为紧约束。而把严格等式约束称为紧约束。第二十七页，本课件共有86页例例4、已知、已知试通过求对偶问题的最优解来求解原问题的最优解。试通过求对偶问题的最优解来求解原问题的最优解。解：对偶问题为解：对偶问题为第二十八页，本课件共有86页用图解法求出：用图解法求出：Y*=（1.3），），W=11。将将y*1=1，y*2=3代入对偶约束条

11、件，代入对偶约束条件，（1）（）（2）（）（5）式为紧约束，（）式为紧约束，（3）（）（4）为松约束。）为松约束。令原问题的最优解为令原问题的最优解为X*=（x1.x2.x3.x4.x5），），则根据互补则根据互补松弛条件，必有松弛条件，必有x3=x4=0(1.3)（1）（2）（3）（4）（5）第二十九页，本课件共有86页又由于又由于y*10，y*20，原问题的约束必为等式，即原问题的约束必为等式，即化简为化简为此方程组为无穷多解此方程组为无穷多解 令令x5=0,得到得到x1=1，x2=2即即X*1=（1.2.0.0.0）为原问题的为原问题的一个最优解，一个最优解，Z=11。再令再令x5=2/

12、3，得到得到x1=5/3，x2=0即即X*2（5/3.0.0.0.2/3）也是原问题的一个最优解，也是原问题的一个最优解，Z=11。第三十页，本课件共有86页例例5、已知原问题的最、已知原问题的最优解为优解为X*=（0.0.4）试试求对偶问题的最优解。求对偶问题的最优解。（最优解与最优值的区别）最优解与最优值的区别）解：解：（1）（2）（3）第三十一页，本课件共有86页将将X*=（0.0.4）代入原问题中，有下式：代入原问题中，有下式：所以，根据互补松弛条件，必有所以，根据互补松弛条件，必有y*1=y*2=0，代入对偶问题代入对偶问题（3 3）式，）式，y3=3。因此，对偶问题的最优解为因此，

13、对偶问题的最优解为 Y*=（0.0.3），），W=12。第三十二页，本课件共有86页6 6、对偶问题的解、对偶问题的解利用原问题的最优单纯利用原问题的最优单纯形表和改进单纯形表求形表和改进单纯形表求解对偶问题的最优解。解对偶问题的最优解。设原问题为：设原问题为：maxZ=CXAXbX0引入引入xs，构建初始基变量，然后，用单纯形法求解。当检验数构建初始基变量，然后，用单纯形法求解。当检验数满足满足j0，则求得最优解。此时，则求得最优解。此时，xs对应的对应的js为为-Y*，故求故求对偶对偶Y*，只要将最优单纯形表上只要将最优单纯形表上xs对应的检验数反号即可。对应的检验数反号即可。CCBCN0

14、CBXBbXBXNXSCBXBB-1bIB-1NB-1ZCBB-1b0CNCBB-1NCBB-1第三十三页，本课件共有86页例一、例一、第三十四页，本课件共有86页cj1018000cBxBbx1x2x3x4x50 x3170521000 x4100230100 x515015001-Z01018000cj1018000cBxBbx1x2x3x4x50 x3540/7001-23/711/710 x150/71005/7-3/718x2200/7010-1/72/7-Z-4100/7000-32/7-6/7初初始始表表最最终终表表第三十五页，本课件共有86页由上表可知：由上表可知：X*=（50

15、/7.200/7），），Z=4100/7对偶问题的最优解：对偶问题的最优解：Y*=（0.32/7.6/7），），W=4100/7第三十六页，本课件共有86页例二、例二、第三十七页，本课件共有86页cj3-1-100-M-McBxBbx1x2x3x4x5x6x73x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3-Z-2000-1/3-1/31/3-M2/3-Mcj3-1-100-M-McBxBbx1x2x3x4x5x6x70 x4111-211000-Mx63-4120-110-Mx71-2010001-Z3-6M-1+M-1+3M

16、0-M00第三十八页，本课件共有86页所以，所以，X*=（4.1.9），），Z=2y*1=(04)=1/3y*2=(M6)=M(1/3M)=1/3y*3=(M7)=M(2/3M)=2/3Y*=（1/3.1/3.2/3）W=2初始基变量的检验数初始基变量的检验数4=1/3，6=1/3M,7=2/3M第三十九页，本课件共有86页定义：在一对定义：在一对P和和D中，若中，若P的某个约束条件的右端的某个约束条件的右端项常数项常数bi增加一个单位时，所引起的目标函数最优值增加一个单位时，所引起的目标函数最优值Z*的改的改变量变量y*i称为第称为第i个约束条件的影子价格，又称为边际价格。个约束条件的影子价

17、格，又称为边际价格。三、对偶问题的经济解释三、对偶问题的经济解释影子价格影子价格第四十页，本课件共有86页设：设：B是问题是问题P的最优基，由前式可知，的最优基，由前式可知，Z*=CBB-1b=Y*b=y*1b1+y*2b2+y*Ibi+y*mbmCCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1ZCBB-1b0CNCBB-1NCBB-1即即y*i表示表示Z*对对bi的变化率。的变化率。第四十一页，本课件共有86页其经济意义是：在其它条件不变的情况下，其经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变单位资源变化所引起的目标函数的最优值的变化。即对偶

18、变量化。即对偶变量yi就是第就是第i个约束条件的影个约束条件的影子价格。子价格。第四十二页，本课件共有86页若第若第i种资源的单位市场价格为种资源的单位市场价格为mi。当当yimi时，企业愿意购进这种资源，单位时，企业愿意购进这种资源，单位纯利为纯利为yimi，则有利可图；则有利可图；如果如果yimi，则企业有偿转让这种资源，则企业有偿转让这种资源，可获单位纯利可获单位纯利miyi，否则，企业无利可图，否则，企业无利可图，甚至亏损。甚至亏损。第四十三页，本课件共有86页01 2 3 4 5 6 7 8 1 2 3 4 5 6 x2 x1(4 2)X*=（4.2.0.0.0.4）Y*=（0.3/

19、2.1/8.0）最优值为最优值为14最优值没有发生变化即最优值没有发生变化即y1=0第四十四页，本课件共有86页01 2 3 4 5 6 7 8 1 2 3 4 5 6 x2 x1(4 5/2)最优值为最优值为15.5，变化了，变化了3/2，即，即y2=3/2即即b2增加一个单位，增加一个单位，y2增加了增加了3/2，即第二，即第二种资源的边际价格为种资源的边际价格为3/2第四十五页，本课件共有86页生产过程中如果某种资源bi未得到充分利用时，该种资源的影子价格为零。当资源的影子价格不为零时，表明该种资源生产过程已耗尽完毕。第四十六页，本课件共有86页第四十七页，本课件共有86页对偶单纯形法是

20、求解线性规划的另一的基本方法。它对偶单纯形法是求解线性规划的另一的基本方法。它是根据对偶原理和单纯形法的原理而设计出来的，因是根据对偶原理和单纯形法的原理而设计出来的，因此称为对偶单纯形法。此称为对偶单纯形法。对偶单纯形法的基本思想：对偶单纯形法的基本思想：在保持对偶问题为可行解的基础上（这时原问题一般在保持对偶问题为可行解的基础上（这时原问题一般为非可行解），通过迭代，当原问题也达到可行解时，为非可行解），通过迭代，当原问题也达到可行解时，即得到目标函数最优值。即得到目标函数最优值。四、对四、对偶偶单单纯纯形形法法W=Yb=CBB-1b=CX=ZY=CBB-1单位矩阵单位矩阵I行变换，即基变

21、换行变换，即基变换与与第四十八页，本课件共有86页3 3、计算步骤、计算步骤：建建立立初初始始单单纯纯形形表表，确确定定原原问问题题或或对对偶偶问问题题的的基基（单单位位矩矩阵阵）。条条件件是是检检验验数数全全部部00。(原问题是不是可行解没有关系）原问题是不是可行解没有关系）基变换：基变换：先先确确定定换换出出变变量量b b列列中中的的负负元元素素（一一般般选选最最小的负元素）对应的基变量出基即小的负元素）对应的基变量出基即第四十九页，本课件共有86页然然后后确确定定换换入入变变量量原原则则是是：在在保保持持对对偶偶可可行行的的前前提提下下，减减少少原原始始问问题题的的不不可可行行性性。如果

22、存在如果存在 （最小比值原则，保证所有的检验数（最小比值原则，保证所有的检验数=0=0）则则选选 为换入变量，相应的列为为换入变量，相应的列为主元列主元列，主，主元行和主元列交叉处的元素元行和主元列交叉处的元素 为主元素为主元素。如如果果不不存存一一个个a aljlj0,0,则则原原问问题题无无可可行行解解，那那么么对对偶问题就存在无界解。偶问题就存在无界解。第五十页，本课件共有86页按按主主元元素素进进行行换换基基迭迭代代（旋旋转转运运算算、枢枢运运算算），将将主主元元素素变变成成1 1，主主元元列列变变成成单单位位向向量量，得得到到新新的单纯形表。的单纯形表。继继续续以以上上步步骤骤，直直

23、至至求求出出最最优优解解。即即所所有有的的检检验验数小于等于零并且右端项大于等于零。数小于等于零并且右端项大于等于零。跳出循环地方的有几处？跳出循环地方的有几处？（保证原问题与对偶问题都有可行解，保证原问题与对偶问题都有可行解，这时就得到两问题的最优解，为什么？）这时就得到两问题的最优解，为什么？）第五十一页，本课件共有86页例一、用对偶单纯形法求解：例一、用对偶单纯形法求解：解：将模型转化为解：将模型转化为如果用单纯形法如果用单纯形法如何求解？如何求解？第五十二页，本课件共有86页cj-9-12-15000cBxBbx1x2x3x4x5x60 x4-10-2-2-11000 x5-12-2-

24、3-10100 x6-14-1-1-5001(-9/-1.-12/-1.-15/-5)-Z0-9-12-15000cj-9-12-15000cBxBbx1x2x3x4x5x60 x4-36/5-9/5-9/5010-1/50 x5-46/5-9/5-14/5001-1/5(-30/-9.-45/-14.-1/5/-3)-15x314/51/51/5100-1/5-Z42-6-9000-3第五十三页，本课件共有86页cj-9-12-15000cBxBbx1x2x3x4x5x60 x4-9/7-9/14001-9/14-1/14-12x223/79/14100-5/141/14(-3/-9.-45

25、/-9.-33/-1)-15x315/71/140101/14-3/14-Z501/7-3/14000-45/14-33/14cj-9-12-15000cBxBbx1x2x3x4x5x6-9x12100-14/911/9-12x220101-10-15x320011/90-2/9-Z72000-1/3-3-7/3第五十四页，本课件共有86页所以，所以，X*=（2.2.2.0.0.0），），Z*=72，原问题原问题Z*=72其对偶问题的最优解为：其对偶问题的最优解为：Y*=(1/3.3.7/3)，W*=72第五十五页，本课件共有86页练习：练习：第五十六页，本课件共有86页cj-2-3-400c

26、BxBbx1x2x3x4x50 x4-3-1-2-1100 x5-4-21-301-Z-2-3-400cj-2-3-400cBxBbx1x2x3x4x50 x4-10-5/21/21-1/2-2x121-1/23/20-1/2-Z0-4-10-1第五十七页，本课件共有86页cj-2-3-400cBxBbx1x2x3x4x5-3x22/501-1/5-2/51/5-2x111/5107/5-1/5-2/5-Z28/500-3/5-8/5-1/5Y=（8/5.1/5）X=（2/5.11/5.0）Z=28/5第五十八页，本课件共有86页灵敏度分析的步骤：灵敏度分析的步骤：1.1.将参数的改变通过矩阵

27、计算反映到最终表中；将参数的改变通过矩阵计算反映到最终表中；2.2.检查原问题是否可行解；检查原问题是否可行解；3.3.检查对偶问题是否可行解；检查对偶问题是否可行解；4.4.按以下原则得出结论或决定继续计算的步骤。按以下原则得出结论或决定继续计算的步骤。五、五、灵敏度分析灵敏度分析第五十九页，本课件共有86页j=cjCBB1Pj=B1Pj=B1b关键是求关键是求B B-1-1即找单位矩阵即找单位矩阵I I第六十页，本课件共有86页求下列求下列LP问题问题 第六十一页，本课件共有86页Cj0-130-20CBXBbx1x2x3x4x5x60 x1713-10200 x4120-241000 x

28、6100-43081j0-130-200 x11015/201/4203x330-1/211/4000 x610-5/20-3/481j01/20-3/4-20-1x242/5101/104/503x351/5013/102/500 x611100-1/2101j-1/500-4/5-12/50第六十二页，本课件共有86页B3=（P2，P3，P6）=B31=第六十三页，本课件共有86页求下列求下列LP问题的最优解问题的最优解第六十四页，本课件共有86页第六十五页，本课件共有86页B41=B3=（P4，P2，P3）=B31=B4=（P1，P2，P3）=第六十六页，本课件共有86页例例：某某企企业

29、业利利用用三三种种资资源源生生产产两两种种产产品品的的最最优优计计划划问问题归结为下列线性规划题归结为下列线性规划已知最优表如下。已知最优表如下。（1 1）确定）确定x2的系数的系数c2的变的变化范围，使原最优解保持化范围，使原最优解保持最优；最优；（2 2）若）若c2=6，求新的最求新的最优计划。优计划。一、一、价值系数价值系数c cj j的变化分析的变化分析第六十七页，本课件共有86页cj54000CBXBbx1x2x3x4x50 x3250012-55x1351001-14x210010-12000-1-3第六十八页，本课件共有86页4=c2505=52c205/2c25cj5c2000

30、CBXBbx1x2x3x4x50 x3250012-55x1351001-1c2x210010-12000c2-55-2c2最优解最优解X*=（35，10，25，0，0）保持不变。保持不变。（1）第六十九页，本课件共有86页Cj56000CBXBbx1x2x3x4x50 x3250012-55x1351001-16x210010-12j0001-70 x425/2001/21-5/25x145/210-1/203/26x245/2011/20-1/2j00-1/20-9/2x1*=45/2，x2*=45/2，x4*=25/2，x3*=x5*=0，z*=495/2（2）第七十页，本课件共有86页

31、XB=B1b例：对于上例中的线性规划作下列分析：例：对于上例中的线性规划作下列分析：（1 1）b3在什么范围内变化，原最优基不变？在什么范围内变化，原最优基不变？（2 2）若）若b3=55，求出新的最优解。求出新的最优解。二、右端常数二、右端常数b bi i的变化分析的变化分析第七十一页，本课件共有86页cj54000CBXBbx1x2x3x4x50 x3250012-55x1351001-14x210010-12000-1-3最优基：最优基：B=（P3，P1，P2）B1=第七十二页，本课件共有86页（1）B1=0解得解得40b350，即当即当b340，50时，最优基时，最优基B 不变不变z*

32、=5（80b3）+4（80+2b3）=80+3b3=也可计算：也可计算：B1B1见书上的见书上的P65P65例例6 6第七十三页，本课件共有86页（2）当当 b3=55时时=x2x1x50-11/5-3/500j0-1/52/51020403/5-1/5013051-2/5-1/50050-32-1-5x50-1000j-101030 x24100125x152100-25x30 x4x3x2x1bXBCB0045Cj第七十四页，本课件共有86页三、三、增加一个新变量的分析增加一个新变量的分析例例2.102.10（续例2.8）设企业研制了一种新产品，对三种资源的消耗系数列向量以P6表示P6 =

33、。问它的价值系数c6符合什么条件才必须安排它的生产？设c6=3，新的最优生产计划是什么？第七十五页，本课件共有86页6=c6CBB1P6=c6（0，5，4）=c65/2=B1P6=第七十六页，本课件共有86页Cj540003CBXBbx1x2x3x4x5x60 x3250012-515x1351001-11/26 x2 10 010-120j 000-1-31/23x6250012-515x145/210-1/203/204 x2 10 010-120j00-1/2-2-1/20第七十七页，本课件共有86页四、四、增加新的约束条件的分析增加新的约束条件的分析例例2.112.11 假设在例2.8

34、中，还要考虑一个新的资源约束：4x1+2x21504x1+2x2+x6=150X*=（35，10，25，0，0）T第七十八页，本课件共有86页4x1+2x2+x6=150cj540000CBXBbx1x2x3x4x5x60 x3250012-505x1351001-104 x2 10 010-1200 x6150420001000-1-30不管是单纯形法还对偶单纯形法都是不管是单纯形法还对偶单纯形法都是从单位矩阵开始的，因此要先找单位矩阵从单位矩阵开始的，因此要先找单位矩阵第七十九页，本课件共有86页Cj540000CBXBbx1x2x3x4x5x60 x3250012-505x1351001

35、-104x210010-1200 x6150420001j000-1-300 x3250012-505x1351001-104x210010-1200 x6-10000-201j000-1-300 x3150010-515x1301000-11/24x21501002-1/20 x4500010-1/2j0000-3-1/2第八十页，本课件共有86页五、五、其它变化情况的分析其它变化情况的分析1.cj和bi同时变化的情况例例2.12 在例2.8中，假定c2由4上升为6，b3增加到55，试问最优解将会发生什么变化？B1=B1 =代替最优表的b列，并把c2改为6第八十一页，本课件共有86页cj56

36、000CBXBbx1x2x3x4x50 x3-250012-55x1251001-16 x2 30 010-12j0001-7原问题与对偶问题均非可行解，表中第一方程是x3+2x45x5=25，两边乘以（-1），得：x32x4+5x5=25，再引入人工变量x6：x32x4+5x5+x6=25以x6为基变量，增添第6列，应用大M法继续求解。第八十二页，本课件共有86页Cj56000-MCBXBbx1x2x3x4x5x6-Mx62500-1-2515x1251001-106 x2 30 010-120j 00-M-2M+15M-700 x5500-1/5-2/5105x13010-1/53/501

37、/56 x2 20 012/5-1/50-2/5j00-7/5-9/50-M+7/5新的最优计划产量为x1*=30，x2*=20，z*=270。x32x4+5x5+x6=25第八十三页，本课件共有86页2.技术系数aij的变化例例2.13 在例2.8中，第一种产品的消耗系数改变为 ，价值系数不变，求新的最优解。B1=第八十四页，本课件共有86页Cj54000CBXBbx1x2x3x4x50 x3252012-55x1351001-14 x2 10-1/210-12j 000-1-3第八十五页，本课件共有86页Cj54000CBXBbx1x2x3x4x50 x3252012-55x1351001-14 x2 10-1/210-12j 000-1-30 x3-450010-35x1351001-14 x2 27.5 010-1/23/2j000-3-10 x51500-1/3015x15010-1/3104 x2 5 011/2-1/20j 00-1/3-30第八十六页，本课件共有86页