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