第二章 对偶问题与灵敏度分析PPT讲稿.ppt

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

1、第二章 对偶问题与灵敏度分析第1页，共114页，编辑于2022年，星期二2.1 线性规划的对偶问题一、问题的提出回顾例题1例1 某工厂在计划期内要安排生产A、B两种产品（假定产品畅销）。已知生产单位产品的利润与所需的劳动力、设备台时及原材料的消耗，如表1.1所示问该厂应如何安排生产使获利最大？表1-1产品A产品B资源限量劳动力设 备原材料9434510360200300利润元/kg70120第2页，共114页，编辑于2022年，星期二其对应的数学模型为：现从另一个角度提出问题。假定有某个公司想把该工厂的资源收买过来，它至少应付出多大代价，才能使这个工厂放弃生产活动，出让自己的资源。显然该工厂愿

2、出让自己资源的条件是，出让价格应不低于用同等数量资源由自己组织生产活动时获取的盈利。价格底线第3页，共114页，编辑于2022年，星期二表1-1产品A产品B资源限量劳动力设 备原材料9434510360200300利润元/kg70120设单位劳动力出让价格y1元，单位设备台时出让价格y2元，单位原材料出让价格y3元。出让收入应不低于自己生产收入：该公司希望用最小代价把这个工厂的全部资源收买过来：第4页，共114页，编辑于2022年，星期二综上所述，我们得到如下数学模型：原问题对偶问题第5页，共114页，编辑于2022年，星期二二、对称形式下对偶问题的一般形式定义：满足下列条件的线性规划问题称为

3、具有对称形式：其变量均具有非负约束，其约束条件当目标函数求极大时取“”号，当目标函数求极小时均取“”号。下面是对称形式下线性规划原问题的一般形式：第6页，共114页，编辑于2022年，星期二用yi(i=1,.,m)代表第i种资源的估价，则其对偶问题的一般形式为：第7页，共114页，编辑于2022年，星期二若用矩阵表示：对称形式下的原问题对称形式下的对偶问题第8页，共114页，编辑于2022年，星期二项目原问题对偶问题A约束系数矩阵其约束系数矩阵的转置b约束条件的右端项向量目标函数中的价格系数向量C目标函数中的价格系数向量约束条件的右端项向量目标函数Max Z=CXMin W=Yb约束条件Ax

4、bAY C决策变量X 0Y 0将上述对称形式下线性规划的原问题与对偶问题进行比较，可列出下表所示的对应关系第9页，共114页，编辑于2022年，星期二写出下面线性规划的对偶规划模型课堂练习第10页，共114页，编辑于2022年，星期二解：按照对称形式的对偶关系，其对偶模型为第11页，共114页，编辑于2022年，星期二原问题有m个约束条件，对偶问题有m个变量原问题有n个变量，对偶问题有n个约束条件原问题的价值系数对应对偶问题的右端项原问题的右端项对应对偶问题的价值系数原问题的系数矩阵转置后为对偶问题系数矩阵原问题的约束条件与对偶问题方向相反原问题与对偶问题优化方向相反小结小结第12页，共114

5、页，编辑于2022年，星期二相关证明：对偶问题的对偶即原问题令=对偶问题对偶问题令Z=Z 第13页，共114页，编辑于2022年，星期二三、非对称形式下原对偶问题关系原问题和对偶问题有很多内在联系，它们之间存在着严格的对应关系：目标函数类型之间的对应关系目标函数系数与右边项的对应关系约束系数矩阵之间的对应关系约束类型与变量类型之间的对应关系并非所有线性规划问题具有对称形式，故下面讨论一般情况下线性规划问题如何写出其对偶问题：第14页，共114页，编辑于2022年，星期二由于前面三个对应关系与对称形式下的对应关系一致，故我们只需讨论约束类型与变量类型之间的对应关系:原问题(对偶问题)对偶问题（原

6、问题）目标函数 max min 目标函数约束条件 =0 变量 0无约束 0变量 0 无约束 约束条件=LableSensibleOddBizarreSensibleOddBizarre第15页，共114页，编辑于2022年，星期二综上所述，其变换形式归纳如下：综上所述，其变换形式归纳如下：原问题（或对偶问题）对偶问题（或原问题）目标函数 max目标函数 min约束条件m个m个变量00=无约束变量n个n个约束条件00无约束=约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项第16页，共114页，编辑于2022年，星期二例 写出下列线性规划问题的对偶问题解：SSSSSSOOBBSSO

7、OBB第17页，共114页，编辑于2022年，星期二例 写出下列线性规划问题的对偶问题课堂练习第18页，共114页，编辑于2022年，星期二答案：答案：第19页，共114页，编辑于2022年，星期二课堂练习第20页，共114页，编辑于2022年，星期二第21页，共114页，编辑于2022年，星期二对偶理论与灵敏度分析v线性规划的对偶问题v对偶问题的基本性质v影子价格v对偶单纯形法v灵敏度分析第22页，共114页，编辑于2022年，星期二2.2 对偶问题的基本性质一、单纯形法计算的矩阵描述对称形式线性规划问题的矩阵表达式加上松驰变量X后为：单纯行法计算时，总选取为初始基，对应基变量Xs举例：第2

8、3页，共114页，编辑于2022年，星期二设迭代若干步后，基变量为XB,XB在初始 单纯行表中的系数矩阵为B。将B在初始单纯行表中单独列出，而A中去掉B的若干列后剩下的列组成N。于是其初始单纯行表可表示成如下形式项目非基变量基变量XB XN XS0 XS b B N Cj-ZjCB CN 0表2.4第24页，共114页，编辑于2022年，星期二当迭代若干步后，基变量为XB时，该步的单纯行表中由XB系数组成的矩阵为 (单位矩阵)。又因单纯行法的迭代是对增广矩阵进行的初等变换，对应Xs的系数矩阵在新表中应为B-1;对应XN的系数矩阵在新表中应为B-1N于是迭代后的单纯行表可表示成如下形式：表2.5

9、项目基变量非基变量XB XN XSCB XB B-1 b B-1 N B-1 Cj-Zj 0CNCB B-1 N-CB B-1 第25页，共114页，编辑于2022年，星期二项目基变量非基变量XB XN XSCB XB B-1 b B-1 N B-1 Cj-Zj CBCN0 项目非基变量基变量XB XN XS0 XS b B N Cj-ZjCB CN 0初始单纯行表:B-1第26页，共114页，编辑于2022年，星期二项目基变量非基变量XB XN XSCB XB B-1 b B-1 N B-1 Cj-Zj 0CNCB B-1 N-CB B-1 表2.5项目基变量非基变量XB XN XSCB X

10、B B-1 b B-1 N B-1 Cj-Zj CBCN0 CB第27页，共114页，编辑于2022年，星期二课堂练习CjCBXBb检验数jx1x2x3x4x5x62-1100060311100101-120102011-1001x4x5x6000 2-110 0 0CBXBb检验数jx1x2x3x4x5x61-1-201/21/20-1/21/2x4x1x202-1第28页，共114页，编辑于2022年，星期二由可知：第29页，共114页，编辑于2022年，星期二检验数的求解：第30页，共114页，编辑于2022年，星期二CBXBb检验数jx1x2x3x4x5x6100011-1-21510

11、1/201/21/2501-3/20-1/21/2x4x1x202-1Cj2-11000第31页，共114页，编辑于2022年，星期二当B为最优基时，其所有检验数应小于零（j 0)于是对应于表2.5有：而对于XB的检验数可写为：由此，（1）（2）（3）式可重新表示为：第32页，共114页，编辑于2022年，星期二若令Y=CB B-1,则上式可表达为：这时可以看出检验数行,若取其相反数恰好是其对偶问题的可行解。为什么？由于对偶问题的限制条件是的形式，则标准形式是在左边减去一个剩余变量的基础上得到的，这个剩余变量为第33页，共114页，编辑于2022年，星期二可以看出，当原问题为最优解时，其对偶问

12、题为可行解，且两者具有相同的目标函数值。后面我们将看到，这时对偶问题的解也为最优解将这个解代入对偶问题的目标函数，有:第34页，共114页，编辑于2022年，星期二项目 系数x1 x2 xn xn+1 xn+2 xn+m Zj -Cj y1 y2 ym 由上面的推导知，我们可以从线性规划问题的最终单纯中直接读出其对偶问题的最优解。注：Cj Zj为检验数，需对其取反z1-c1 z2-c2 zn-cnym+1 ym+2 ym+n松弛变量Xs第35页，共114页，编辑于2022年，星期二更一般的结论：用单纯形法求解线性规划问题时，迭代的每一步在得到原问题一个基可行解的同时，其检验行（行0）中的 yi

13、和zjcj值是其对偶问题的一个基解第36页，共114页，编辑于2022年，星期二举例：下面是两个互为对偶的线性规划问题：原问题对偶问题第37页，共114页，编辑于2022年，星期二将上面两个线性规划问题加入松弛和剩余变量后，得到如下形式：y1y2y3对偶变量对偶变量对偶变量对偶变量x1x2第38页，共114页，编辑于2022年，星期二用单纯形法和对偶单纯型法求得两个问题的最终单纯形表如下：项目jy4y5y1 y2 y3x1x2x3x4x5原问题变量原问题松弛变量x3x1x215/20015/4-15/27/21001/4-1/23/2010-1/43/20001/41/2对偶问题的剩余变量对偶

14、问题变量原问题最终单纯形表第39页，共114页，编辑于2022年，星期二项目jx3x4x5 x1 x2对偶问题最终单纯形表y1y2y3y4y5对偶问题变量对偶问题剩余变量y2y31/4-5/410-1/41/41/215/2011/2-3/215/2007/23/2原问题松弛变量原问题变量从上面两个表可以清楚的看出两个问题变量之间的对应关系。同时看出只需求解其中一个问题，从最优的单纯形表中同时得到另一个问题的最优解第40页，共114页，编辑于2022年，星期二二、对偶问题的基本性质第41页，共114页，编辑于2022年，星期二【定义2.1】（弱对偶性）如果xj (j=1,.n)是原问题的可行解

15、，yi (i=1,m)是其对偶问题的可行解，则恒有证明：第42页，共114页，编辑于2022年，星期二由弱对偶性，可得出以下结论：1、原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界2、如原问题有可行解且目标函数值无界（具有无界解），则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解。注意：本点性质的逆不成立，即当对偶问题无可行解时，其原问题或具有无界解或无可行解；反之亦然第43页，共114页，编辑于2022年，星期二3、若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有

16、可行解而其原问题无可行解，则对偶问题的目标函数值无界。第44页，共114页，编辑于2022年，星期二【定理2.2】（最优性）如果xj(j=1,n)是原问题的可行解，yi (i=1,m)是其对偶问题的可行解，且有 则xj (j=1,n)是原问题的最优解，yi (i=1,m)是其对偶问题的最优解第45页，共114页，编辑于2022年，星期二证明：设xj*(j=1,n)是原问题的最优解，yi*(i=1,.,m)是对偶问题的最优解。由弱对偶性质有：又知：第46页，共114页，编辑于2022年，星期二【定理2.3】（强对偶性）若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值

17、相等证明：由于两者均有可行解，根据弱对偶性，对原问题的目标函数具有上界，对偶问题的目标函数具有下界，因此两者具有最优解。由矩阵描述一节可知，当原问题为最优解时，其对偶问 题的解为可行解，且有Z=,由定理2.2可知，这时两者均为最优解第47页，共114页，编辑于2022年，星期二Primal problemDual problemOptimal Z*Optimal W*第48页，共114页，编辑于2022年，星期二【定理2.4】（互补松弛性）在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为零，也即：

18、第49页，共114页，编辑于2022年，星期二以前面例子说明互补松弛定理：y1y2y3对偶变量对偶变量y1y2y3第50页，共114页，编辑于2022年，星期二互补松弛定理（说明续）：项目jy4y5y1 y2 y3x1x2x3x4x5原问题变量原问题松弛变量x3x1x215/20015/4-15/27/21001/4-1/23/2010-1/43/20001/41/2对偶问题的剩余变量对偶问题变量原问题最终单纯形表第51页，共114页，编辑于2022年，星期二已知线性规划问题 min=2x1+3x2+5x3+2x4+3x5 x1+x2+2x3+x4+3x5 4 2x1 x2+3x3+x4+x5

19、 3 xj 0(j=1,2,5)对偶问题的最优解为y1*=4/5,y2*=3/5,Z=5,试找出原问题的最优解。课堂举例st.第52页，共114页，编辑于2022年，星期二分析：先写出其对偶问题 max Z=4y1+3y2 y1+2 y2 2 y1-y2 3 2y1+3y2 5 y1+y2 2 3y1+y2 3x1x2x3x4x5将y1*、y2*的值带入约束条件，得到24个约束条件为严格不等式；由互补松弛性得x2*=x3*=x4*=0.因y1*、y2*0;原问题的两个约束条件应取等式：x1*+3x5*=4 2x1*+x5*=3求解后得到x1*=1,x5*=1,故原问题最优解x*=(1,0,0,

20、0,0,1)T;*=5第53页，共114页，编辑于2022年，星期二课堂练习已知原问题的最优解为X*=(0,0,4)T,最优值为Z*=12.试用对偶理论求对偶问题的最优解第54页，共114页，编辑于2022年，星期二将X*=(0,0,4)T,代入原问题的三个约束条件可知：由松弛互补定理可知，必有y1*=y2*=0，代入对偶问题得y3*=3y1y2y3对偶变量对偶变量解：原问题的对偶问题为：Y*=(0,0,3),最优值为最优值为W*=12第55页，共114页，编辑于2022年，星期二对偶理论与灵敏度分析v线性规划的对偶问题v对偶问题的基本性质v影子价格v对偶单纯形法v灵敏度分析第56页，共114

21、页，编辑于2022年，星期二当线性规划原问题求得最优解xj*(j=1,2n)时，其对偶问题也得到最优解yi*(i=1,.,m),代入各自的目标函数后有：3.3.1其中，bi代表第i种资源的拥有量，对偶变量yi*的意义代表在资源最优利用条件下对单位资源i的估价。这种估计不是资源的市场价格，而是根据在生产中做出的贡献而作的估价，为区别一般意义的价格，我们将其（yi*）称为影子价格（shadow price）2.3 影子价格（对偶最优解的经济解释）第57页，共114页，编辑于2022年，星期二影子价格的几点说明1 资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。

22、因企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。2 影子价格是一种边际价格，在3.31式中对Z求bi的偏导数得这说明yi*的值相当于在资源得到最优利用的生产条件下，bi每增加一个单位时目标函数Z的增量第58页，共114页，编辑于2022年，星期二关于第2点的说明检验数jx3x2x10532100-1/31/360101/2020011/3-1/3-36000-3/2-1最终单纯形表y1y2y3对偶变量对偶变量y1 y2 y3第59页，共114页，编辑于2022年，星期二关于第2点的说明(2,6)(5/3,13/2)Z1=3(2)+5(6)=362x2=122x2=13Z2=3

23、(5/3)+5(13/2)=37.5Z=Z2 Z1=3/2=y*2第60页，共114页，编辑于2022年，星期二3 资源的影子价格实际上又是一种机会成本。在纯市场经济条件下，当某一资源的市场价格低于该影子价格时，可以买进这种资源；相反，当市场价格高于影子价格时，就会卖出这种资源。随着资源的买进卖出，它的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。4、在上一节对偶问题的互补松弛性质中有第61页，共114页，编辑于2022年，星期二这表明生产过程中如果某资源bi未得到充分利用，则该种资源的影子价格为零；又当某资源的影子价格不为零时，表明该种资源已消耗完毕。(互

24、补松弛定理的经济解释)5 对单纯形表的检验数Cj代表第j种产品的单位产值，aijyi是生产单位该种产品所消耗各项资源的影子价格的总和。当产品单位产值大于隐含成本时，表明生产该项产品有利，可在计划中安排生产，否则用这些资源来生产别的产品更为有利，就不安排生产。（检验数的经济解释）第62页，共114页，编辑于2022年，星期二6 一般说来，对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估计直接涉及资源的最有效利用。例如，在一个大公司内部，可借助资源的影子价格确定一些内部结算价格，以便控制有限资源的使用和考核下属企业经营的好坏。又如，在社会上可对一些

25、最紧缺的资源，借助影子价格规定使用这种单位资源时必须上交的利润额，以控制一些经济效益低的企业自觉地节约使用紧缺资源，使有限资源发挥更大的经济效益。第63页，共114页，编辑于2022年，星期二对偶理论与灵敏度分析v线性规划的对偶问题v对偶问题的基本性质v影子价格v对偶单纯形法v灵敏度分析第64页，共114页，编辑于2022年，星期二2.4 对偶单纯形法一、对偶单纯形法的基本思路对原问题的一个基可行解，判别是否所有检验数，若是，又基变量中无非零人工变量，即找到了问题的最优解；若为否，再找出相邻的目标函数值更大的基可行解，并继续判别，只要最优解存在，就一直循环进行到找出最优解为止。求解线性规划的单

26、纯形法的思路是：第65页，共114页，编辑于2022年，星期二对偶单纯形法的基本思路是：从原问题的一个基本解出发，此基本解不一定可行（即b中有负数），但它对应着一个对偶可行解（检验数非正），所以此时也可以说是从一个对偶可行解出发；然后检验原问题的基本解是否可行，即b是否有为负的分量,若是，则进行迭代，求解另一个基本解，此基本解对应着另一个对偶可行解（保持检验数非正）。如果得到的基本解的分量皆非负，则该基本解为最优解。根据对偶问题的性质，因为Cj Zj=Cj CBB-1Pj,当Cj Zj 0(j=1,2,n),即有YPj Cj 或aijyi Cj(j=1,2,n)也即其对偶问题的解为可行解。i=

27、1m第66页，共114页，编辑于2022年，星期二也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原问题的基本解由不可行逐步变为可行。当同时得到对偶问题与原问题的可行解时，便得到了原问题的最优解。第67页，共114页，编辑于2022年，星期二单纯形法与对偶单纯形法之间的比较单纯形法对偶单纯形法前提条件所有bi 0所有j 0最优解检验所有j 0所有bi 0换入、换出变量的确定先确定换入变量后确定换出变量先确定换出变量后确定换入变量基解的变化可行最优非可行可行（最优）第68页，共114页，编辑于2022年，星期二二、对偶单纯形法的计算步骤1 根据线性规划问题，列出初始单

28、纯形表，检查b列的数字，若都为非负，检验数都为非正，则已得到最优解，停止计算。若检查b列的数字时，至少有一个负分量，所有检验数保持非正，那么进行以下计算2 确定换出基的变量 按 对应的基变量xr为换出基的变量第69页，共114页，编辑于2022年，星期二3确定换入变量4 在单纯形表中检查xr所在行的各系数arj(j=1,2,n)5 若所有arj 0，则原问题无可行解xr+ar,m+1xm+1+arn xn=br因为arj 0(j=m+1,.,n),又br0,故不可能存在xj 0 (j=1,2.n)，故原问题无可行解。若存在arj 0(j=1,2n),则按最小比值原则计算称ars为主元素（枢轴元

29、素），xs为换入基的变量第70页，共114页，编辑于2022年，星期二4 以ars为主元素，进行高斯消元，得到新的计算表 重复14的步骤第71页，共114页，编辑于2022年，星期二解：将模型转化为三、对偶单纯形法举例第72页，共114页，编辑于2022年，星期二cj-9-12-15000cBxBbx1x2x3x4x5x60 x4-10-2-2-11000 x5-12-2-3-10100 x6-14-1-1-5001Cj Zj0-9-12-15000(-9/-1,-12/-1,-15/-5)cj-9-12-15000cBxBbx1x2x3x4x5x60 x4-36/5-9/5-9/5010-1

30、/50 x5-46/5-9/5-14/5001-1/5-15x314/51/51/5100-1/5Cj Zj42-6-9000-3(-30/-9,-45/-14,-15/-1)第73页，共114页，编辑于2022年，星期二cj-9-12-15000cBxBbx1x2x3x4x5x60 x4-9/7-9/14001-9/14-1/14-12x223/79/14100-5/141/14-15x315/71/140101/14-3/14Cj Zj501/7-3/14000-45/14-33/14(-3/-9,-45/-9,-33/-1)cj-9-12-15000cBxBbx1x2x3x4x5x6-9

31、x12100-14/911/9-12x220101-10-15x320011/90-2/9Cj Zj72000-1/3-3-7/3第74页，共114页，编辑于2022年，星期二四、对偶单纯形法的应用时机1 对偶单纯形法的优点是，初始解可以是非可行解，不需要加入人工变量2 对一个线性规划问题，即可以用单纯形法求解，也可以用对偶单纯形法求解。具体采用那种方法，由当前情况（计算表）决定。使用那种方法比较方便，就使用那种方法第75页，共114页，编辑于2022年，星期二3 求目标函数最大化时，在单纯形表中：如果检验数均非正，而b列中有负值，这时使用对偶单 纯形法；如果所有bi 0,检验数有正值，使用单

32、纯形法 如果b列中有负值，且检验数中有正值，这时必须引入 人工变量，建立新的单纯形表，重新计算第76页，共114页，编辑于2022年，星期二用对偶单纯法求解下述线性规划问题：分析：先将问题改写为最大化形式，然后在约束条件两端乘“1”后，加入相应的松弛变量得：课堂练习第77页，共114页，编辑于2022年，星期二列出单纯形表，并用上述对偶单纯形法求解步骤进行计算Cj-15 -24 -5 0 0CB 基 by1 y2 y3 y4 y50 y4 -20 -6 -1 1 0 0 y5 -1-5 -2 -1 0 1 Cj-Zj-15 -24 -5 0 0-24/-6 1.5，而家电II的利润12，美佳公

33、司最优生产计划有何变化(2)若家电I的利润不变，则家电II的利润在什么范围内变化时，则该公司的最优生产计划不发生变化第92页，共114页，编辑于2022年，星期二分析：(1)Cj2 1 0 0 0CB 基 bx1 x2 x3 x4 x50 x3 15/20 0 1 5/4 -15/22 x1 7/21 0 0 1/4 -1/21 x2 3/20 1 0 -1/4 3/2 Cj-Zj0 0 0 -1/4 -1/2最终单纯形表j=Cj -CBB-1pj ,其中B-1pj可从最终单纯形表读得Cj3/2 2 0 0 0CB 基 bx1 x2 x3 x4 x50 x3 15/20 0 1 5/4 -15

34、/23/2 x1 7/21 0 0 1/4 -1/22 x2 3/20 1 0 -1/4 3/2 Cj-Zj0 0 0 1/8 -9/4因变量x4的检验数大于零，故需继续用单纯形法迭代第93页，共114页，编辑于2022年，星期二Cj3/2 2 0 0 0比值CB 基 bx1 x2 x3 x4 x50 x3 15/20 0 1 5/4 -15/23/2 x1 7/21 0 0 1/4 -1/22 x2 3/20 1 0 -1/4 3/2 Cj-Zj0 0 0 1/8 -9/4614Cj3/2 2 0 0 0CB 基 bx1 x2 x3 x4 x50 x4 60 0 4/5 1 -63/2 x1

35、 21 0 -1/5 0 12 x2 30 1 1/5 0 0 Cj-Zj0 0 -1/10 0 -3/2即美佳公司随家电利润的变化应调整为生产I 2件，生产II 3 件第94页，共114页，编辑于2022年，星期二分析：(2)设家电II的利润为(1+)元，反映到最终单纯形表中，得下表：Cj2 1+0 0 0CB 基 bx1 x2 x3 x4 x50 x3 15/20 0 1 5/4 -15/22 x1 7/21 0 0 1/4 -1/21+x2 3/20 1 0 -1/4 3/2 Cj-Zj0 0 0 -1/4+1/4 -1/2-3/2为使上表的解仍为最优解，应有：-1/4+1/4 0 ;-

36、1/2 2/3 0解得：-1/3 1即家电II的利润c2的变化范围应满足：2/3 c2 2第95页，共114页，编辑于2022年，星期二二、分析bi的变化右端项bi的变化在实际问题中反映为可用资源数量的变化。由于bi变化反映到最终单纯形表上仅引起b列数字的变化，故解的最优性不受影响（对偶问题可行），我们只需要判断解的可行性即可。若该解可行，则最优基不变若该解不可行，则使用对偶单纯形法迭代直到找到最优解第96页，共114页，编辑于2022年，星期二在上述美佳公司的例子中：（1）若设备A和调试工序的每天能力不变，而设备B每天的能力增加到32h，分析公司最优计划的变化（2）若设备A和设备B每天可用能

37、力不变，则调试工序能力在什么范围变化时，问题的最优基不变第97页，共114页，编辑于2022年，星期二分析：(1)因为 ，于是有：将计算结果反映到最终单纯形表中去,有：第98页，共114页，编辑于2022年，星期二Cj2 1 0 0 0CB 基 bx1 x2 x3 x4 x50 x3 15/20 0 1 5/4 -15/22 x1 7/21 0 0 1/4 -1/21 x2 3/20 1 0 -1/4 3/2 Cj-Zj0 0 0 -1/4 -1/2原最终单纯形表Cj2 1 0 0 0CB 基 bx1 x2 x3 x4 x50 x3 35/20 0 1 5/4 -15/22 x1 11/21

38、0 0 1/4 -1/21 x2 1/20 1 0 -1/4 3/2 Cj-Zj0 0 0 -1/4 -1/2由于原问题为非可行解，故用对偶单纯形法继续计算得下表第99页，共114页，编辑于2022年，星期二Cj2 1 0 0 0CB 基 bx1 x2 x3 x4 x50 x3 150 5 1 0 02 x1 51 1 0 0 10 x4 20 -4 0 1 -6 Cj-Zj0 -1 0 0 -2 由此，美佳公司的最优计划改变为只生产家电 5件第100页，共114页，编辑于2022年，星期二分析：（2）设调试工序每天可用能力为（5+）h,因此有：当b 0时问题的最优基不变，解得 -1 1由此，

39、此调试工序的能力应在46h之间第101页，共114页，编辑于2022年，星期二三、增加一个变量xj的变化增加一个变量在实际问题中反映为增加一种新的产品，其分析步骤为：1、计算2、计算3、若，则原最优解不变，只需将计算得到的直接写入最终单纯形表中即可；若存在,则按单纯形法继续迭代计算找出最优解。第102页，共114页，编辑于2022年，星期二美佳公司又计划推出新型号的家电III，生产一件所需设备A、B及调试工序的时间分别为3h,4h,2h，该产品的预期盈利为3元/件，试分析该种产品是否值得投产；如投产，对该公司的最优生产计划有何变化。分析：设该公司生产家电III x6件，有C6=3,P6=(3,

40、4,2)T第103页，共114页，编辑于2022年，星期二将其反映到最终单纯形表中得下表：Cj2 1 0 0 0 3CB 基 bx1 x2 x3 x4 x5 x60 x3 15/20 0 1 5/4 -15/2 -7 2 x1 7/21 0 0 1/4 -1/2 01 x2 3/20 1 0 -1/4 3/2 2 Cj-Zj0 0 0 -1/4 -1/2 1Cj2 1 0 0 0 3CB 基 bx1 x2 x3 x4 x5 x60 x3 51/40 7/2 1 3/8 -9/4 02 x1 7/21 0 0 1/4 -1/2 03 x6 3/40 1/2 0 -1/8 3/4 1 Cj-Zj0

41、 -1/2 0 -1/8 -5/4 0由此，美佳公司最优生产计划应为每天生产家电I 7/2件；家电III 3/4件第104页，共114页，编辑于2022年，星期二四、分析参数aij的变化aij的变化使线性规划的约束系数矩阵A发生变化。若变量Xj在最终单纯形表中为非基变量，其约束条件中系数aij的变化分析步骤可以参照前面小节（增加一个变量xj的变化）。若变量xj在最终单纯行表中为基变量，则在计算反映到最终单纯形表后，需要对其作高斯消元，已保证得到恰当的形式（proper form from Gaussian elimination）第105页，共114页，编辑于2022年，星期二注：对第二种情况

42、，高斯消元后可能出现原问题和对偶问题均无可行解的情况。出现这种情况时，需要引进人工变量先将原问题转化为可行解，再用单纯形法求解。第106页，共114页，编辑于2022年，星期二例 在美佳公司的例子中，若家电II 每件需设备A,B和调试工时变为8h,4h,1h，该产品的利润变为3元/件，试重新确定该公司最优生产计划解：先将生产工时变化后的家电II看作时一种新产品，仿照前面小节的计算步骤，计算出并反映到最终单纯形表中，其中第107页，共114页，编辑于2022年，星期二将其反映到最终单纯形表有：Cj2 3 0 0 0CB 基 bx1 x2 x3 x4 x50 x3 15/20 11/2 1 5/4

43、 -15/22 x1 7/21 1/2 0 1/4 -1/23 x2 3/20 1/2 0 -1/4 3/2 Cj-Zj0 3/2 0 -1/4 -1/2不符合高斯消元形式Cj2 3 0 0 0CB 基 bx1 x2 x3 x4 x50 x3 15/20 11/2 1 5/4 -15/22 x1 7/21 1/2 0 1/4 -1/23 x2 3/20 1/2 0 -1/4 3/2 Cj-Zj0 3/2 0 -1/4 -1/2第108页，共114页，编辑于2022年，星期二Cj2 3 0 0 0CB 基 bx1 x2 x3 x4 x50 x3 15/20 11/2 1 5/4 -15/22 x

44、1 7/21 1/2 0 1/4 -1/23 x2 3/20 1/2 0 -1/4 3/2 Cj-Zj0 3/2 0 -1/4 -1/2Cj2 3 0 0 0CB 基 bx1 x2 x3 x4 x50 x3 -90 0 1 4 -242 x1 21 0 0 1/2 -23 x2 30 1 0 -1/2 3 Cj-Zj0 0 0 1/2 -5既不可行，也不最优，采用特殊方法第109页，共114页，编辑于2022年，星期二在加入人工变量后，求得最优解为：美佳公司的最优计划为每天生产家电I 11/4件，新家电II 15/8 件第110页，共114页，编辑于2022年，星期二五、增加一个约束条件的分析

45、添加一个约束条件在实际问题中相当于添加一道工序。分析的方法是先将原问题最优解的变量值代入新增的约束条件，如满足，说明新增的约束未起到限制作用，原最优解不变。否则，将新增的约束直接反映到最终单纯形表中再进一步分析。仍以美佳公司为例，设家电I，II经调试后，还需经过一道环境试验工序。家电I每件须环境试验3h，家电II每件2h，又环境试验工序每天生产能力为12h。试分析增加该工序后的美佳公司最优生产计划。第111页，共114页，编辑于2022年，星期二分析：先将原问题的最优解x1=7/2，x2=3/2代入环境试验工序的约束条件:因3*(7/2)+2*(3/2)=27/212,，故原问题最优解不是本例

46、的最优解。在实验工序的约束条件中加入松弛变量得：以x6为基变量，上式反映到最终单纯行表中：第112页，共114页，编辑于2022年，星期二Cj2 1 0 0 0 0CB 基 bx1 x2 x3 x4 x5 x60 x3 15/20 0 1 5/4 -15/2 0 2 x1 7/21 0 0 1/4 -1/2 01 x2 3/20 1 0 -1/4 3/2 00 x6 123 2 0 0 0 1 Cj-Zj0 0 0 -1/4 -1/2 0不符合高斯消元形式Cj2 1 0 0 0 0CB 基 bx1 x2 x3 x4 x5 x60 x3 15/20 0 1 5/4 -15/2 0 2 x1 7/

47、21 0 0 1/4 -1/2 01 x2 3/20 1 0 -1/4 3/2 00 x6 -3/20 0 0 -1/4 -3/2 1 Cj-Zj0 0 0 -1/4 -1/2 0第113页，共114页，编辑于2022年，星期二Cj2 1 0 0 0 0CB 基 bx1 x2 x3 x4 x5 x60 x3 150 0 1 5/2 0 -5 2 x1 41 0 0 1/3 0 -1/31 x2 00 1 0 -1/2 0 10 x5 10 0 0 1/6 1 -2/3 Cj-Zj0 0 0 -1/6 0 -1/3由上表可知，添加环境试验工序后，美佳公司得最优生产计划为只生产家电 I 4件第114页，共114页，编辑于2022年，星期二