《第二章对偶理念及灵敏度分析精选PPT.ppt》由会员分享，可在线阅读，更多相关《第二章对偶理念及灵敏度分析精选PPT.ppt（86页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章对偶理念及灵敏度分析第1页，本讲稿共86页一、问 题 的 提 出例一、资源的合理利用问题 已知资料如表所示，问应如何安排生产计划使得既能充分利用现有资源有使总利润最大？第2页，本讲稿共86页一、问 题 的 提 出1810单件利润单件利润150（设备）（设备）51C100（煤炭）（煤炭）32B170（钢材）（钢材）25A资源限制资源限制乙乙甲甲单件单件 产产 消耗消耗 品品资源资源第3页，本讲稿共86页下面从另一个角度来讨论这个问题：下面从另一个角度来讨论这个问题：假定：该厂的决策者不是考虑自己生产甲、乙两种假定：该厂的决策者不是考虑自己生产甲、乙两种产品，而是将厂里的现有资源用于接受外来
2、加工任务，产品，而是将厂里的现有资源用于接受外来加工任务，只收取加工费。试问该决策者应制定怎样的收费标准只收取加工费。试问该决策者应制定怎样的收费标准（收费的最底线）？（收费的最底线）？第4页，本讲稿共86页第5页，本讲稿共86页一、问 题 的 提 出该问题的数学模型为：该问题的数学模型为：第6页，本讲稿共86页模型对比请总结规律第7页，本讲稿共86页1 1、对称型对偶问题：已知、对称型对偶问题：已知 P，写出写出 D。（一）、对偶问题的形式（一）、对偶问题的形式二、线性规划的对偶理论第8页，本讲稿共86页原问题：max z=2x1+3x2 s.t 2x1+2x212 x1+2x28 4x1
3、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 非对称型对偶问题如何求解？非对称型对偶问题如何求解？第9页，本讲稿共86页对偶问题的其变换形式归纳如下对偶问题的其变换形式归纳如下原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数 max目标函数目标函数 min约约束束条条件件m个个m个个变变量量0000=无约束无约束变变量量n个个n个个约约束束条条件件0000无约束无约束=约束条件右端项约束条件
4、右端项目标函数变量的系数目标函数变量的系数目标函数变量的系数目标函数变量的系数约束条件右端项约束条件右端项变向变向变向变向大约束，小变量大约束，小变量第10页，本讲稿共86页例一、写出线性规划问题的对偶问题例一、写出线性规划问题的对偶问题第11页，本讲稿共86页例二、原问题例二、原问题第12页，本讲稿共86页例三：第13页，本讲稿共86页例四、例四、原问题原问题第14页，本讲稿共86页对偶问题对偶问题第15页，本讲稿共86页例五、线性规划问题如下：例五、线性规划问题如下：第16页，本讲稿共86页第17页，本讲稿共86页练习：练习：第18页，本讲稿共86页第19页，本讲稿共86页（二）、对偶问题
5、的性质1 1、对称性定理：对偶问题的对偶是原问题。、对称性定理：对偶问题的对偶是原问题。以下讨论仅就以下讨论仅就“对称形式对称形式”讨论。讨论。因其他形式都可以转化成因其他形式都可以转化成“对称形式对称形式”，故所有结论适用于所有形式。，故所有结论适用于所有形式。第20页，本讲稿共86页2 2、弱对偶原理（弱对偶性）：设、弱对偶原理（弱对偶性）：设 和和 分别是问题分别是问题（P）和（和（D）的可行解，则必有的可行解，则必有 推论推论.若若 和和 分别是问题（分别是问题（P P）和（和（D D）的可行解，的可行解，则则 是（是（D D）的目标函数最小值的一个下界；的目标函数最小值的一个下界；是
6、是（P P）的目标函数最大值的一个上界。的目标函数最大值的一个上界。第21页，本讲稿共86页推论推论.在一对对偶问题（在一对对偶问题（P）和（和（D）中，若其中中，若其中一个问题可行但目标函数无界，则另一个问题不可行；一个问题可行但目标函数无界，则另一个问题不可行；反之不成立。这也是对偶问题的无界性。反之不成立。这也是对偶问题的无界性。关于无界性有如下结论：关于无界性有如下结论：问题无界问题无界无可无可行解行解无可无可行解行解问题无界问题无界对偶问题对偶问题原问题原问题第22页，本讲稿共86页 3 3、最优性判别定理：、最优性判别定理：若若 X*和和 Y*分别是分别是 P和和 D 的可行解且的
7、可行解且 CX*=Y*b，则则X*.Y*分别是问题分别是问题 P和和D 的最优解。的最优解。下面来求原问题和对偶问题的最优解：下面来求原问题和对偶问题的最优解：第23页，本讲稿共86页Cj CBCN0系数系数基基 XBXNXSCBXBB-1b IB-1NB-1 Z=CBB-1b 0 CN-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第24页，本讲稿共86页4 4、对偶定理（强对偶性）：、对偶
8、定理（强对偶性）：若一对对偶问题若一对对偶问题 P和和D 都有可行解，则它们都有都有可行解，则它们都有最优解，且目标函数的最优值必相等。最优解，且目标函数的最优值必相等。推论（推论（3 3）.若若 P和和D的任意一个有最优解，则另的任意一个有最优解，则另一个也有最优解，且目标函数的最优值相等。一个也有最优解，且目标函数的最优值相等。推论（推论（4）.在一对对偶问题（在一对对偶问题（P）和（和（D）中，中，若一个可行若一个可行，而另一个不可行而另一个不可行，则该可行的问题无界。则该可行的问题无界。原问题有最优解，则对偶问题只少有一个可行解原问题有最优解，则对偶问题只少有一个可行解。并且这一解即为
9、对偶问题的最优解。并且这一解即为对偶问题的最优解。第25页，本讲稿共86页综上所述，一对对偶问题的关系，只能有下综上所述，一对对偶问题的关系，只能有下面三种情况之一出现：面三种情况之一出现：.都有可行解，都有最优解，分别设为都有可行解，都有最优解，分别设为X*和和Y*，则必有则必有CX*=Y*b；.一个问题无界，则另一个问题无可行解；一个问题无界，则另一个问题无可行解；.两个都无可行解。两个都无可行解。第26页，本讲稿共86页 5 5、互补松弛定理：、互补松弛定理：在线性规划问题的最优解中，在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，如果对应某一约束条件的对偶变量值为非零
10、，则该约束条件取严格等式；则该约束条件取严格等式；如果约束条件取严格不等式，则其对应的对偶如果约束条件取严格不等式，则其对应的对偶变量一定为零。变量一定为零。严格不等式约束称为松约束，严格不等式约束称为松约束，而把严格等式约束称为紧约束。而把严格等式约束称为紧约束。第27页，本讲稿共86页例例4、已知、已知试通过求对偶问题的最优解来求解原问题的最优解。试通过求对偶问题的最优解来求解原问题的最优解。解：对偶问题为解：对偶问题为第28页，本讲稿共86页用图解法求出：用图解法求出：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）第29页，本讲稿共86页 又由于又由于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/
12、3.0.0.0.2/3）也是原问题的一个最优解，也是原问题的一个最优解，Z=11。第30页，本讲稿共86页例例5、已知原问题的最、已知原问题的最优解为优解为X*=（0.0.4）试试求对偶问题的最优解。求对偶问题的最优解。（最优解与最优值的最优解与最优值的区别）区别）解：解：（1）（2）（3）第31页，本讲稿共86页将将X*=（0.0.4）代入原问题中，有下式：代入原问题中，有下式：所以，根据互补松弛条件，必有所以，根据互补松弛条件，必有y*1=y*2=0，代入对偶代入对偶问题问题（3 3）式，）式，y3=3。因此，对偶问题的最优解为因此，对偶问题的最优解为 Y*=（0.0.3），），W=12。
13、第32页，本讲稿共86页6 6、对偶问题的解、对偶问题的解利用原问题的最优单纯形利用原问题的最优单纯形表和改进单纯形表求解对表和改进单纯形表求解对偶问题的最优解。偶问题的最优解。设原问题为：设原问题为：maxZ=CXAXbX0引入引入xs，构建初始基变量，然后，用单纯形法求解。当构建初始基变量，然后，用单纯形法求解。当检验数满足检验数满足j0，则求得最优解。此时，则求得最优解。此时，xs对应的对应的js为为-Y*，故求对偶故求对偶Y*，只要将最优单纯形表上只要将最优单纯形表上xs对应的检验数反号即可。对应的检验数反号即可。CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1ZCB
14、B-1b0CNCBB-1NCBB-1第33页，本讲稿共86页例一、例一、第34页，本讲稿共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初初始始表表最最终终表表第35页，本讲稿共86页由上表可知：由上表可知：X*=（50/7.200/7），），Z=4100/7对偶问题的最优解：对偶问题的最优
15、解：Y*=（0.32/7.6/7），），W=4100/7第36页，本讲稿共86页例二、例二、第37页，本讲稿共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+3M0-M00第38页，本讲稿共86页所以，所以，X*=（4.1.9），），Z=2y
16、*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第39页，本讲稿共86页 定义：在一对定义：在一对 P和和 D中，若中，若 P的某个约束条件的的某个约束条件的右端项常数右端项常数bi增加一个单位时，所引起的目标函数最优增加一个单位时，所引起的目标函数最优值值Z*的改变量的改变量y*i称为第称为第 i个约束条件的影子价格，又个约束条件的影子价格，又称为边际价格。称为边际价格。三、对偶问题的经济解释三、对偶问题的经济解释影子价格影子价
17、格第40页，本讲稿共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的变化率。的变化率。第41页，本讲稿共86页 其经济意义是：在其它条件不变的情况下，其经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的单位资源变化所引起的目标函数的最优值的变化。即对偶变量变化。即对偶变量yi就是第就是第 i个约束条件的个约束条件的影子价格。影子价格
18、。第42页，本讲稿共86页若第若第i种资源的单位市场价格为种资源的单位市场价格为mi。当当yimi时，企业愿意购进这种资源，单位纯时，企业愿意购进这种资源，单位纯利为利为yimi，则有利可图；则有利可图；如果如果yimi，则企业有偿转让这种资源，可则企业有偿转让这种资源，可获单位纯利获单位纯利miyi，否则，企业无利可图，否则，企业无利可图，甚至亏损。甚至亏损。第43页，本讲稿共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/2.1/8.0）最优值为最优值为14最优值没有发生变化即最优值没有发生变化即y1=0第
19、44页，本讲稿共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第45页，本讲稿共86页生产过程中如果某种资源bi未得到充分利用时，该种资源的影子价格为零。当资源的影子价格不为零时，表明该种资源生产过程已耗尽完毕。第46页，本讲稿共86页第47页，本讲稿共86页对偶单纯形法是求解线性规划的另一的基本方法。它对偶单纯形法是求解线性规划的另一的基本方法。它是根据对偶原理和单纯形法
20、的原理而设计出来的，因是根据对偶原理和单纯形法的原理而设计出来的，因此称为对偶单纯形法。此称为对偶单纯形法。对偶单纯形法的基本思想：对偶单纯形法的基本思想：在保持对偶问题为可行解的基础上（这时原问题一般在保持对偶问题为可行解的基础上（这时原问题一般为非可行解），通过迭代，当原问题也达到可行解时，为非可行解），通过迭代，当原问题也达到可行解时，即得到目标函数最优值。即得到目标函数最优值。四、对四、对偶偶单单纯纯形形法法W=Yb=CBB-1b=CX=ZY=CBB-1单位矩阵单位矩阵I行变换，即基变换行变换，即基变换与与第48页，本讲稿共86页3 3、计算步骤、计算步骤：建建立立初初始始单单纯纯形形
21、表表，确确定定原原问问题题或或对对偶偶问问题题的的基基（单单位位矩矩阵阵）。条条件件是是检检验验数数全全部部00。(原原问问题是不是可行解没有关系）题是不是可行解没有关系）基变换：基变换：先先确确定定换换出出变变量量b b b b列列中中的的负负元元素素（一一般般选选最最小小的负元素）对应的基变量出基即的负元素）对应的基变量出基即第49页，本讲稿共86页然然后后确确定定换换入入变变量量原原则则是是：在在保保保保持持持持对对对对偶偶偶偶可可可可行行行行的的的的 前前前前 提提提提下下，减减 少少 原原 始始 问问 题题 的的 不不 可可 行行 性性。如果存在如果存在 （最小比值原则，保证所有的检
22、验数（最小比值原则，保证所有的检验数=0=0）则选则选 为换入变量，相应的列为为换入变量，相应的列为主元列主元列，主元行和主元列交叉处的元素主元行和主元列交叉处的元素 为主元素为主元素。如如如如果果果果不不不不存存存存一一一一个个个个a a a aljlj0,0,则则原原问问题题无无可可行行解解，那那么么对对偶问题就存在无界解。偶问题就存在无界解。第50页，本讲稿共86页按按按按主主主主元元元元素素素素进进进进行行行行换换换换基基基基迭迭迭迭代代代代（旋旋旋旋转转转转运运运运算算算算、枢枢枢枢运运运运算算算算），将将主主元元素素变变成成1 1，主主元元列列变变成成单单位位向向量量，得得到到新新
23、的单纯形表。的单纯形表。继继续续以以上上步步骤骤，直直至至求求出出最最优优解解。即即所所有有的的检检验数小于等于零并且右端项大于等于零。验数小于等于零并且右端项大于等于零。跳出循环地方的有几处？跳出循环地方的有几处？（保证原问题与对偶问题都有可行解，保证原问题与对偶问题都有可行解，这时就得到两问题的最优解，为什么？）这时就得到两问题的最优解，为什么？）第51页，本讲稿共86页例一、用对偶单纯形法求解：例一、用对偶单纯形法求解：解：将模型转化为解：将模型转化为如果用单纯形法如果用单纯形法如何求解？如何求解？第52页，本讲稿共86页cj-9-12-15000cBxBbx1x2x3x4x5x60 x
24、4-10-2-2-11000 x5-12-2-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第53页，本讲稿共86页cj-9-12-15000cBxBbx1x2x3x4x5x60 x4-9/7-9/14001-9/14-1/14-12x223/79/141
25、00-5/141/14(-3/-9.-45/-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第54页，本讲稿共86页所以，所以，X*=（2.2.2.0.0.0），），Z*=72，原问题原问题Z*=72其对偶问题的最优解为：其对偶问题的最优解为：Y*=(1/3.3.7/3)，W*=72第55页，本讲稿共86页练习：练习：第56页，本讲稿
26、共86页cj-2-3-400cBxBbx1x2x3x4x50 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第57页，本讲稿共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第58页，本讲稿共86页灵敏度分析的步骤：灵敏度分析的步骤：1.1
27、.将参数的改变通过矩阵计算反映到最终表中；将参数的改变通过矩阵计算反映到最终表中；2.2.检查原问题是否可行解；检查原问题是否可行解；3.3.检查对偶问题是否可行解；检查对偶问题是否可行解；4.4.按以下原则得出结论或决定继续计算的步骤。按以下原则得出结论或决定继续计算的步骤。五、五、灵敏度分析灵敏度分析第59页，本讲稿共86页j=cjCBB1Pj =B1Pj=B1b关键是求关键是求B B-1-1即找单位矩阵即找单位矩阵I I第60页，本讲稿共86页求下列求下列LP问题问题 第61页，本讲稿共86页Cj0-130-20CBXBbx1x2x3x4x5x60 x1713-10200 x4120-2
28、41000 x6100-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第62页，本讲稿共86页B3=（P2，P3，P6）=B31=第63页，本讲稿共86页求下列求下列LP问题的最优解问题的最优解第64页，本讲稿共86页第65页，本讲稿共86页B41=B3=（P4，P2，P3）=B31=B4=（P1，P2，P3）=第66页，本讲稿共86页例例：某某企企业业利利
29、用用三三种种资资源源生生产产两两种种产产品品的的最最优优计计划划问题归结为下列线性规划问题归结为下列线性规划已知最优表如下。已知最优表如下。（1 1）确定）确定x2的系数的系数c2的的变化范围，使原最优解变化范围，使原最优解保持最优；保持最优；（2 2）若）若c2=6，求新的最求新的最优计划。优计划。一、一、价值系数价值系数c cj j的变化分析的变化分析第67页，本讲稿共86页cj54000CBXBbx1x2x3x4x50 x3250012-55x1351001-14x210010-12000-1-3第68页，本讲稿共86页4=c2505=52c205/2c25cj5c2000CBXBbx1
30、x2x3x4x50 x3250012-55x1351001-1c2x210010-12000c2-55-2c2最优解最优解X*=（35，10，25，0，0）保持不变。保持不变。（1）第69页，本讲稿共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）第70页，本讲稿共86页XB=B1b例：对于
31、上例中的线性规划作下列分析：例：对于上例中的线性规划作下列分析：（1 1）b3在什么范围内变化，原最优基不变？在什么范围内变化，原最优基不变？（2 2）若）若b3=55，求出新的最优解。求出新的最优解。二、右端常数二、右端常数b bi i的变化分析的变化分析第71页，本讲稿共86页cj54000CBXBbx1x2x3x4x50 x3250012-55x1351001-14x210010-12000-1-3最优基：最优基：B=（P3，P1，P2）B1=第72页，本讲稿共86页（1）B1=0解得解得40b350，即当即当b340，50时，最优基时，最优基B 不变不变z*=5（80b3）+4（80+
32、2b3）=80+3b3=也可计算：也可计算：B1B1见书上的见书上的P65P65例例6 6第73页，本讲稿共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第74页，本讲稿共86页三、三、增加一个新变量的分析增加一个新变量的分析例例2.102.10（续例2.8）设企业研制了一种新产品，对三种资源的消耗系数列向量以P6表示P6 =。问它的价值系数c6符合什么条件才必
33、须安排它的生产？设c6=3，新的最优生产计划是什么？第75页，本讲稿共86页6=c6CBB1P6=c6（0，5，4）=c65/2=B1P6=第76页，本讲稿共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第77页，本讲稿共86页四、四、增加新的约束条件的分析增加新的约束条件的分析例例2.112.11 假设在例2.8中，还要考虑一个新的资源约束：4x1+2x215
34、04x1+2x2+x6=150X*=（35，10，25，0，0）T第78页，本讲稿共86页4x1+2x2+x6=150cj540000CBXBbx1x2x3x4x5x60 x3250012-505x1351001-104 x2 10 010-1200 x6150420001000-1-30不管是单纯形法还对偶单纯形法都是不管是单纯形法还对偶单纯形法都是从单位矩阵开始的，因此要先找单位矩阵从单位矩阵开始的，因此要先找单位矩阵第79页，本讲稿共86页Cj540000CBXBbx1x2x3x4x5x60 x3250012-505x1351001-104x210010-1200 x6150420001
35、j000-1-300 x3250012-505x1351001-104x210010-1200 x6-10000-201j000-1-300 x3150010-515x1301000-11/24x21501002-1/20 x4500010-1/2j0000-3-1/2第80页，本讲稿共86页五、五、其它变化情况的分析其它变化情况的分析1.cj和bi同时变化的情况例例2.12 在例2.8中，假定c2由4上升为6，b3增加到55，试问最优解将会发生什么变化？B1=B1 =代替最优表的b列，并把c2改为6第81页，本讲稿共86页cj56000CBXBbx1x2x3x4x50 x3-250012-5
36、5x1251001-16 x2 30 010-12j0001-7原问题与对偶问题均非可行解，表中第一方程是x3+2x45x5=25，两边乘以（-1），得：x32x4+5x5=25，再引入人工变量x6：x32x4+5x5+x6=25以x6为基变量，增添第6列，应用大M法继续求解。第82页，本讲稿共86页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/50-2/5j00-7/5-9
37、/50-M+7/5新的最优计划产量为x1*=30，x2*=20，z*=270。x32x4+5x5+x6=25第83页，本讲稿共86页2.技术系数aij的变化例例2.13 在例2.8中，第一种产品的消耗系数改变为 ，价值系数不变，求新的最优解。B1=第84页，本讲稿共86页Cj54000CBXBbx1x2x3x4x50 x3252012-55x1351001-14 x2 10-1/210-12j 000-1-3第85页，本讲稿共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页，本讲稿共86页