第二章对偶理念及灵敏度分析精选文档.ppt

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

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

2、来加工任务，只收品，而是将厂里的现有资源用于接受外来加工任务，只收取加工费。试问该决策者应制定怎样的收费标准（收费的取加工费。试问该决策者应制定怎样的收费标准（收费的最底线）？最底线）？本讲稿第四页，共八十六页本讲稿第五页，共八十六页一、问 题 的 提 出该问题的数学模型为：该问题的数学模型为：本讲稿第六页，共八十六页模型对比请总结规律本讲稿第七页，共八十六页1 1、对称型对偶问题：已知、对称型对偶问题：已知P，写出写出 D。（一）、对偶问题的形式（一）、对偶问题的形式二、线性规划的对偶理论本讲稿第八页，共八十六页原问题：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 非对称型对偶问题如何求解？非对称型对偶问题如何求解？本讲稿第九页，共八十六页对偶问题的其变换形式归纳如下对偶问题的其变换形式归纳如下原原问题（或（或对偶偶问题）对偶偶问题（或原（或原问题）目目标标函数函数 max目目标标函数函数 min约束束条条件件m个个m个个变量量0000=无无约束束变量量n个个n个个约束束条条件件0000无无约束束=约束条件右端束条件右端项目目标函数函数变量的系数

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

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

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

7、Y*b，则则X*.Y*分别是问题分别是问题 P和和D 的最优解。的最优解。下面来求原问题和对偶问题的最优解：下面来求原问题和对偶问题的最优解：本讲稿第二十三页，共八十六页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本讲稿第二十四页，共八十六页4 4、对偶定理（强对偶性）：、对偶定理（强对偶性）：若一

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

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

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

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

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

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

14、ZCBB-1b0CNCBB-1NCBB-1本讲稿第三十三页，共八十六页例一、例一、本讲稿第三十四页，共八十六页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初初始始表表最最终终表表本讲稿第三十五页，共八十六页由上表可知：由上表可知：X*=（50/7.200/7），），Z=4100/7对偶问题的最优

15、解：对偶问题的最优解：Y*=（0.32/7.6/7），），W=4100/7本讲稿第三十六页，共八十六页例二、例二、本讲稿第三十七页，共八十六页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+3M0-M00本讲稿第三十八页，共八十六页所以，所以，X*

16、=（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本讲稿第三十九页，共八十六页定义：在一对定义：在一对P和和D中，若中，若P的某个约束条件的右端项常的某个约束条件的右端项常数数bi增加一个单位时，所引起的目标函数最优值增加一个单位时，所引起的目标函数最优值Z*的改变量的改变量y*i称为第称为第i个约束条件的影子价格，又称为边际价格。个约束条件的影子价格，又称为边际价格。三、对偶问题的经济解释三、对偶问题

17、的经济解释影子价格影子价格本讲稿第四十页，共八十六页设：设：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的变化率。的变化率。本讲稿第四十一页，共八十六页其经济意义是：在其它条件不变的情况下，其经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变单位资源变化所引起的目标函数的最优值的变化。即对偶变量化。即对偶变量yi就是第就是第i个约束条件的影子个

18、约束条件的影子价格。价格。本讲稿第四十二页，共八十六页若第若第i种资源的单位市场价格为种资源的单位市场价格为mi。当当yimi时，企业愿意购进这种资源，单位时，企业愿意购进这种资源，单位纯利为纯利为yimi，则有利可图；则有利可图；如果如果yimi，则企业有偿转让这种资源，则企业有偿转让这种资源，可获单位纯利可获单位纯利miyi，否则，企业无利可图，否则，企业无利可图，甚至亏损。甚至亏损。本讲稿第四十三页，共八十六页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/2.1/8.0）最优值为最优值为14最优值没有发生变化

19、即最优值没有发生变化即y1=0本讲稿第四十四页，共八十六页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本讲稿第四十五页，共八十六页生产过程中如果某种资源bi未得到充分利用时，该种资源的影子价格为零。当资源的影子价格不为零时，表明该种资源生产过程已耗尽完毕。本讲稿第四十六页，共八十六页本讲稿第四十七页，共八十六页对偶单纯形法是求解线性规划的另一的基本方法。对偶单纯形法是求解线性规

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

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

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

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

24、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本讲稿第五十三页，共八十六页cj-9-12-15000cBxBbx1x2x3x4x5x60 x4-9/7-9/14001-9/14-1/14-12x223/79/14100-5/141/14(-3/-9.-45/-9.-33/-1)-15

25、x315/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本讲稿第五十四页，共八十六页所以，所以，X*=（2.2.2.0.0.0），），Z*=72，原问题原问题Z*=72其对偶问题的最优解为：其对偶问题的最优解为：Y*=(1/3.3.7/3)，W*=72本讲稿第五十五页，共八十六页练习：练习：本讲稿第五十六页，共八十六页cj-2-3-400cBxBbx1x2x3x4x5

26、0 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本讲稿第五十七页，共八十六页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本讲稿第五十八页，共八十六页灵敏度分析的步骤：灵敏度分析的步骤：1.1.将参数的改变通过矩阵计算反映到最终表中；将参数的

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

28、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本讲稿第六十二页，共八十六页B3=（P2，P3，P6）=B31=本讲稿第六十三页，共八十六页求下列求下列LP问题的最优解问题的最优解本讲稿第六十四页，共八十六页本讲稿第六十五页，共八十六页B41=B3=（P4，P2，P3）=B31=B4=（P1，P2，P3）=本讲稿第六十六页，共八十六页例例：某某企企业业利利用用三三种种资资源源生生产产

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

30、x3250012-55x1351001-1c2x210010-12000c2-55-2c2最优解最优解X*=（35，10，25，0，0）保持不变。保持不变。（1）本讲稿第六十九页，共八十六页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）本讲稿第七十页，共八十六页XB=B1b例：对于上例中的线性规

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

32、）=80+3b3=也可计算：也可计算：B1B1见书上的见书上的P65P65例例6 6本讲稿第七十三页，共八十六页（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本讲稿第七十四页，共八十六页三、三、增加一个新变量的分析增加一个新变量的分析例例2.102.10（续例2.8）设企业研制了一种新产品，对三种资源的消耗系数列向量以P6表示P6 =。问它的价值系数c6符合什么条件才

33、必须安排它的生产？设c6=3，新的最优生产计划是什么？本讲稿第七十五页，共八十六页6=c6CBB1P6=c6（0，5，4）=c65/2=B1P6=本讲稿第七十六页，共八十六页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本讲稿第七十七页，共八十六页四、四、增加新的约束条件的分析增加新的约束条件的分析例例2.112.11 假设在例2.8中，还要考虑一个新的资源约束：4x

34、1+2x21504x1+2x2+x6=150X*=（35，10，25，0，0）T本讲稿第七十八页，共八十六页4x1+2x2+x6=150cj540000CBXBbx1x2x3x4x5x60 x3250012-505x1351001-104 x2 10 010-1200 x6150420001000-1-30不管是单纯形法还对偶单纯形法都是不管是单纯形法还对偶单纯形法都是从单位矩阵开始的，因此要先找单位矩阵从单位矩阵开始的，因此要先找单位矩阵本讲稿第七十九页，共八十六页Cj540000CBXBbx1x2x3x4x5x60 x3250012-505x1351001-104x210010-1200

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

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

37、/50-2/5j00-7/5-9/50-M+7/5新的最优计划产量为x1*=30，x2*=20，z*=270。x32x4+5x5+x6=25本讲稿第八十三页，共八十六页2.技术系数aij的变化例例2.13 在例2.8中，第一种产品的消耗系数改变为 ，价值系数不变，求新的最优解。B1=本讲稿第八十四页，共八十六页Cj54000CBXBbx1x2x3x4x50 x3252012-55x1351001-14 x2 10-1/210-12j 000-1-3本讲稿第八十五页，共八十六页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本讲稿第八十六页，共八十六页