第二章对偶理论及灵敏度分析精选PPT.ppt

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

1、第二章第二章 对偶理论及对偶理论及灵敏度分析灵敏度分析第1页，本讲稿共100页第第第第1 1 1 1节节节节 线性规划的对偶问题线性规划的对偶问题线性规划的对偶问题线性规划的对偶问题一、对偶问题的提出一、对偶问题的提出二、原问题与对偶问题的数学模型二、原问题与对偶问题的数学模型三、原问题与对偶问题的对应关系三、原问题与对偶问题的对应关系第2页，本讲稿共100页实例：某家电厂家利用现有资源生产实例：某家电厂家利用现有资源生产两种产品，两种产品，有关数据如下表：有关数据如下表：设备A 设备B调试工序利润（元）0612521115时24时 5时产品产品产品产品D一、对偶问题的提出一、对偶问题的提出第

2、3页，本讲稿共100页如何安排生产，如何安排生产，使获利最多使获利最多？厂家设设 产量产量 产量产量一、对偶问题的提出一、对偶问题的提出第4页，本讲稿共100页 设：设备设：设备A A 元时元时 设备设备B B 元时元时 调试工序调试工序 元时元时收购 付出的代价最小，付出的代价最小，且对方能接受。且对方能接受。出让代价应不低于用同等数量的资源自己生产的利润。一、对偶问题的提出一、对偶问题的提出第5页，本讲稿共100页 设备A 设备B调试工序利润（元）0612521115时24时 5时D厂家能接受的条件：厂家能接受的条件：收购方的意愿：收购方的意愿：单位产品单位产品出租出租收入不低于收入不低于

3、2 2元元单位产品单位产品出租出租收入不低于收入不低于1 1元元出让代价应不低于用同等数量的资源自己生产的利润。第6页，本讲稿共100页厂家对对偶偶问问题题原原问问题题收购厂家一对对偶问题第7页，本讲稿共100页3 3个约束个约束2 2个变量个变量2 2个约束个约束 3 3个变量个变量原问题对偶问题对偶问题一一般般规规律律第8页，本讲稿共100页 特点：特点：1 2限定向量限定向量b 价值向量价值向量C （资源向量）资源向量）3一个约束一个约束 一个变量。一个变量。4 的的LP约束约束“”的的 LP是是“”的约束。的约束。5变量都是非负限制。变量都是非负限制。其它形式其它形式的对偶的对偶?第9

4、页，本讲稿共100页二、原问题与对偶问题的数学模型二、原问题与对偶问题的数学模型1、对称形式的对偶、对称形式的对偶 当原问题对偶问题只含有不等式约束时，当原问题对偶问题只含有不等式约束时，称为对称形式的对偶。称为对称形式的对偶。原问题对偶问题对偶问题情形一：情形一：第10页，本讲稿共100页原问题对偶问题对偶问题化为标准对称型情形二：情形二：证明证明对偶第11页，本讲稿共100页2、非对称形式的对偶非对称形式的对偶 若原问题的约束条件是等式，则若原问题的约束条件是等式，则原问题对偶问题第12页，本讲稿共100页推导:原问题第13页，本讲稿共100页 根据对称形式的对偶模型,可直接写出上述问题的

5、对偶问题:第14页，本讲稿共100页令 ，得对偶问题为：证毕。证毕。第15页，本讲稿共100页三、原问题与对偶问题的对应关系三、原问题与对偶问题的对应关系 原问题（或对偶问题）对偶问题（或原问题）第16页，本讲稿共100页例例:第17页，本讲稿共100页对偶问题为：对偶问题为：第18页，本讲稿共100页第第第第1 1 1 1节节节节 线性规划的对偶问题线性规划的对偶问题线性规划的对偶问题线性规划的对偶问题第19页，本讲稿共100页一、单纯形法计算的矩阵描述一、单纯形法计算的矩阵描述二、引例二、引例三、对偶问题的基本性质三、对偶问题的基本性质 1、对称定理、对称定理 2、弱对偶性定理、弱对偶性定

6、理 3、最优性定理、最优性定理 4、对偶定理（强对偶性）、对偶定理（强对偶性）5、互补松弛定理、互补松弛定理第第第第2 2 2 2节节节节 对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质第20页，本讲稿共100页对称形式线性规划问题加上松弛变量 后为：一、单纯形法计算的矩阵描述一、单纯形法计算的矩阵描述项目项目非基变量非基变量基变量基变量 0 bB NI0初始单纯形表为：第21页，本讲稿共100页当迭代若干步，基变量为 时，则该步的单纯形 表中由 系数矩阵组成的矩阵为I。故当基变量为 时，新的单纯形表如下：一、单纯形法计算的矩阵描述一、单纯形法计算的矩阵描述项目项目基

7、变量基变量非基变量非基变量 I0第22页，本讲稿共100页对对偶偶问问题题原问题收购厂家二、引例二、引例第23页，本讲稿共100页（）原问题的变量原问题松弛变量对偶问题剩余变量对偶问题的变量化为极小问题原问题化为极小问题，最终单纯形表：原问题化为极小问题，最终单纯形表：第24页，本讲稿共100页原问题的变量原问题松弛变量对偶问题剩余变量对偶问题的变量对偶问题用两阶段法求解的最终的单纯形表对偶问题用两阶段法求解的最终的单纯形表第25页，本讲稿共100页（）原问题的变量原问题松弛变量对偶问题剩余变量对偶问题的变量化为极小问题原问题最优解对偶问题最优解原问题化为极小问题，最终单纯形表：原问题化为极小

8、问题，最终单纯形表：第26页，本讲稿共100页两个问题比较两个问题比较:1、两者的最优值相同2、变量的解在两个单纯形表中互相包含原问题最优解原问题最优解（决策变量）对偶问题最优解对偶问题最优解（决策变量）对偶问题的松弛变量原问题的松弛变量第27页，本讲稿共100页从引例中可见：从引例中可见：原问题与对偶问题在某种意义上来说，原问题与对偶问题在某种意义上来说，实质上是一样的，因为第二个问题仅仅在第实质上是一样的，因为第二个问题仅仅在第一个问题的另一种表达而已。一个问题的另一种表达而已。第28页，本讲稿共100页一、对称定理：一、对称定理：定理：对偶问题的对偶是原问题。定理：对偶问题的对偶是原问题

9、。设原问题（1）对偶问题（2）三、对偶问题的基本性质三、对偶问题的基本性质第29页，本讲稿共100页二、弱对偶性定理：二、弱对偶性定理：若若 和和 分别是原问题（分别是原问题（1 1）及）及对偶问题（对偶问题（2 2）的可行解，）的可行解，则有 证明：证明：三、对偶问题的基本性质三、对偶问题的基本性质第30页，本讲稿共100页（1 1）极大化问题（）极大化问题（原问题原问题）的任一）的任一可行解可行解所所对应对应的的目标函数值目标函数值是对偶问题是对偶问题最优目标函数值最优目标函数值的的下界下界。（2 2）极小化问题（）极小化问题（对偶问题对偶问题）的任一）的任一可行解可行解所所对应对应的的目

10、标函数值目标函数值是原问题是原问题最优目标函数值最优目标函数值的的上界上界。（3 3）若）若原问题可行原问题可行，但其，但其目标函数值无界目标函数值无界，则，则对对偶问题无可行解偶问题无可行解。由弱对偶性可得以下结论：由弱对偶性可得以下结论：三、对偶问题的基本性质三、对偶问题的基本性质第31页，本讲稿共100页（4 4）若对偶问题可行，但其目标函数值无界，则原问题无可）若对偶问题可行，但其目标函数值无界，则原问题无可行解。行解。（5 5）若原问题有可行解而其对偶问题无可行解，则原问题）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界。目标函数值无界。（6 6）对偶问题有可行解而其原

11、问题无可行解，则对偶问题的目）对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界标函数值无界。原问题对偶问题三、对偶问题的基本性质三、对偶问题的基本性质第32页，本讲稿共100页三、最优性定理：三、最优性定理：若若 和和 分别是（分别是（1 1）和（）和（2 2）的可行解，且有的可行解，且有 则则 分分别是（别是（1 1）和（）和（2 2）的最优解）的最优解 。三、对偶问题的基本性质三、对偶问题的基本性质第33页，本讲稿共100页证明：原问题与对偶问题的解一般有三种情况：一个有有限最优解 另一个有有限最优解。一个有无界解 另一个无可行解。两个均无可行解。四、强对偶性（对偶定理）：四

12、、强对偶性（对偶定理）：若原问题及其对偶问题均具有可行若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解，则两者均具有最优解，且它们最优解的目标函数值相等。解的目标函数值相等。三、对偶问题的基本性质三、对偶问题的基本性质第34页，本讲稿共100页五、互补松弛性：五、互补松弛性：若若 分别是原问题（分别是原问题（1 1）与对偶问题（与对偶问题（2 2）的可行解，）的可行解，分别为（分别为（1 1）、（）、（2 2）的松弛变量，则：）的松弛变量，则：为最优解三、对偶问题的基本性质三、对偶问题的基本性质 说明：说明：在线性规划问题的最优解中，如果对应某一约束在线性规划问题的最优解中，

13、如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。一定为零。第35页，本讲稿共100页（1）从已知的最优对偶解，求原问题最）从已知的最优对偶解，求原问题最优解，反之亦然。优解，反之亦然。（2）证实原问题可行解是否为最优解。）证实原问题可行解是否为最优解。（3）从不同假设来进行试算，从而研究）从不同假设来进行试算，从而研究原始、对偶问题最优解的一般性质。原始、对偶问题最优解的一般性质。（4）非线性的方面的应用。）非线性的方面的应用

14、。以上性质同样适用于非对称形式。以上性质同样适用于非对称形式。互补松弛定理应用互补松弛定理应用第36页，本讲稿共100页第第第第2 2 2 2节节节节 对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质第37页，本讲稿共100页在单纯形法的每步迭代中，在单纯形法的每步迭代中，目标函数取值目标函数取值 ，和检和检验数验数 中都有乘子中都有乘子 ，那么那么Y Y的经济意义是什么？的经济意义是什么？第第第第3 3 3 3节节节节 影子价格影子价格影子价格影子价格第38页，本讲稿共100页 当线性规划原问题求得最优解当线性规划原问题求得最优解时，其对偶问题也得到最优解时，其对偶问

15、题也得到最优解 ，且代入各自的目标函数后有：，且代入各自的目标函数后有：是线性规划原问题约束条件的是线性规划原问题约束条件的右端项，它代表第右端项，它代表第 种资源的拥有量；种资源的拥有量；（1）影子价格的经济意义影子价格的经济意义第39页，本讲稿共100页 对偶变量对偶变量 的意义的意义代表在资源最优代表在资源最优利用条件下对利用条件下对单位单位第第 种资源的种资源的估价估价，这种估价不是资源的市场价格，而是根这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，据资源在生产中作出的贡献而作的估价，为区别起见，称为为区别起见，称为影子价格影子价格（shadow price)。

16、影子价格的经济意义影子价格的经济意义第40页，本讲稿共100页1、资源的市场价格是已知数，相对比较稳定，、资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，而它的影子价格则有赖于资源的利用情况，是未知数。由于企业生产任务、产品结构等是未知数。由于企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。情况发生变化，资源的影子价格也随之改变。市场价格影子价格市场企业影子价格的经济意义影子价格的经济意义第41页，本讲稿共100页2、影子价格是一种边际价格。、影子价格是一种边际价格。在（在（1）式中，）式中，。说明说明 的值相当于在资源得到最的值相当于在资源得到最优

17、利用的生产条件下，优利用的生产条件下，每增加每增加一个一个单位单位时时目标函数目标函数 的的增量增量。影子价格的经济意义影子价格的经济意义第42页，本讲稿共100页几何解释：引例图解法分析几何解释：引例图解法分析（3，3）（15/4，5/4）,z=8.75（7/2，3/2），z=8.5第43页，本讲稿共100页3、资源的影子价格实际上又是一种机会成本、资源的影子价格实际上又是一种机会成本.在纯市场经济条件下在纯市场经济条件下,当第当第2种资源的市场价格低种资源的市场价格低于于1/4时，可以买进这种资源；相反当市场价格高于时，可以买进这种资源；相反当市场价格高于影子价格时，就会卖出这种资源。随着

18、资源的买进影子价格时，就会卖出这种资源。随着资源的买进卖出，它的影子价格也将随之发生变化，一直到影卖出，它的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状子价格与市场价格保持同等水平时，才处于平衡状态。态。影子价格的经济意义影子价格的经济意义第44页，本讲稿共100页4、在对偶问题的互补松弛性质中有、在对偶问题的互补松弛性质中有 这表明生产过程中如果某种资源这表明生产过程中如果某种资源 未得到充未得到充分利用时，该种资源的影子价格为零；又当资源分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已的影子价格不为零时，表明该种资源在生

19、产中已耗费完毕。耗费完毕。影子价格的经济意义影子价格的经济意义第45页，本讲稿共100页5、从影子价格的含义上考察单纯形表的、从影子价格的含义上考察单纯形表的 检验数的经济意义。检验数的经济意义。（2）第j种产品的产值生产第j中产品所消耗各项资源的影子价格的总和。（即隐含成本）可见，产品产值可见，产品产值隐含成本隐含成本 可生产该产品；可生产该产品；否则，不安排生产。否则，不安排生产。检验数的经济意义检验数的经济意义影子价格的经济意义影子价格的经济意义第46页，本讲稿共100页 6、一般说对、一般说对线性规划问题线性规划问题的求解是的求解是确定资源的确定资源的最优分配方案最优分配方案，而对于，

20、而对于对对偶问题偶问题的求解则是确定的求解则是确定对资源的恰当对资源的恰当估价估价，这种估价直接涉及到资源的最，这种估价直接涉及到资源的最有效利用。有效利用。经济学研究如何管理自己的稀缺资源影子价格的经济意义影子价格的经济意义第47页，本讲稿共100页第第第第3 3 3 3节节节节 影子价格影子价格影子价格影子价格第48页，本讲稿共100页 对偶单纯形法的基本思路 对偶单纯形法的计算步骤第第第第4 4 4 4节节节节 对偶单纯形法对偶单纯形法对偶单纯形法对偶单纯形法第49页，本讲稿共100页一、什么是对偶单纯形法？一、什么是对偶单纯形法？对对偶偶单单纯纯形形法法是是应应用用对对偶偶原原理理求求

21、解解原原始始线线性性规规划划的的一一种种方方法法在在原原始始问问题的单纯形表格上进行题的单纯形表格上进行对偶处理对偶处理。注意：注意：不是解对偶问题的单纯形法！不是解对偶问题的单纯形法！第50页，本讲稿共100页 二、对偶单纯形法的基本思想二、对偶单纯形法的基本思想1 1、对、对、对、对“单纯形法单纯形法单纯形法单纯形法”求解过程认识的提升求解过程认识的提升求解过程认识的提升求解过程认识的提升从更高的角度理解单纯形法从更高的角度理解单纯形法初始可行基初始可行基初始可行基初始可行基（对应一个初始基可行解）（对应一个初始基可行解）迭迭迭迭代代代代另另另另一一一一个个个个可可可可行行行行基基基基（对

22、对应应另另一一个个基基可可行行解解），直至，直至所有检验数所有检验数所有检验数所有检验数00为止为止。第51页，本讲稿共100页 所有检验数所有检验数意味着意味着说说明明原原原原始始始始问问问问题题题题的的的的最最最最优优优优基基基基也也也也是是是是对对对对偶偶偶偶问问问问题题题题的的的的可可可可行行行行基基基基。换换言言之之，当当原原始始问问题题的的基基B既既是是原原始始可可行行基基又又是是对对偶可行基时，偶可行基时，B成为最优基。成为最优基。定定定定理理理理 B B是是是是线线线线性性性性规规规规划划划划的的的的最最最最优优优优基基基基的的的的充充充充要要要要条条条条件件件件是是是是，B

23、B是是是是可行基，同时也是对偶可行基。可行基，同时也是对偶可行基。可行基，同时也是对偶可行基。可行基，同时也是对偶可行基。第52页，本讲稿共100页（对偶）单纯形法的基本思路：（对偶）单纯形法的基本思路：原问题基可行解原问题基可行解 最优解判断最优解判断对偶问题的可行解对偶问题最优解判断对偶单纯形法对偶单纯形法对偶单纯形法对偶单纯形法基本思路基本思路基本思路基本思路第53页，本讲稿共100页单纯形法的求解过程就是：单纯形法的求解过程就是：在保持在保持在保持在保持原始可行原始可行原始可行原始可行的前提下的前提下的前提下的前提下（b列保持列保持0）通过逐步迭代通过逐步迭代通过逐步迭代通过逐步迭代实

24、现对偶可行实现对偶可行实现对偶可行实现对偶可行（检验数行（检验数行0）。2、对偶单纯形法思想：对偶单纯形法思想：换换换换个个个个角角角角度度度度考考考考虑虑虑虑LPLP求求求求解解解解过过过过程程程程：保保持持对对对对偶偶偶偶可可可可行行行行的的前前提提下下（检检检检验验验验数数数数行行行行保保保保持持持持00），通通过过逐逐步步迭迭代代实实实实现现现现原原原原始始始始可可可可行行行行（b b列列列列00，从非可行解变成可行解）。，从非可行解变成可行解）。第54页，本讲稿共100页三、对偶单纯形法的实施三、对偶单纯形法的实施1 1、使用条件：、使用条件：、使用条件：、使用条件：检验数全部检验数

25、全部检验数全部检验数全部00；b b列至少一个元素列至少一个元素列至少一个元素列至少一个元素00；2 2、实施对偶单纯形法的基本原则：、实施对偶单纯形法的基本原则：、实施对偶单纯形法的基本原则：、实施对偶单纯形法的基本原则：在保持对偶可行的前提下进行基变换在保持对偶可行的前提下进行基变换在保持对偶可行的前提下进行基变换在保持对偶可行的前提下进行基变换每一次迭代过程中取出每一次迭代过程中取出基变量中的一个负分量基变量中的一个负分量基变量中的一个负分量基变量中的一个负分量作为作为换出变量换出变量换出变量换出变量去去替换替换替换替换某个某个非基变量非基变量非基变量非基变量（作为（作为换入变量换入变量

26、换入变量换入变量），），使原始问题的非可行解向可行解靠近。使原始问题的非可行解向可行解靠近。第55页，本讲稿共100页3、计算步骤、计算步骤：建立初始单纯形表，计算检验数行。建立初始单纯形表，计算检验数行。建立初始单纯形表，计算检验数行。建立初始单纯形表，计算检验数行。b b列列列列00已得最优解；已得最优解；已得最优解；已得最优解；至少一个元素至少一个元素至少一个元素至少一个元素0,0,转下步转下步转下步转下步;b b列列列列00原始单纯形法；原始单纯形法；原始单纯形法；原始单纯形法；至少一个元素至少一个元素至少一个元素至少一个元素0,0,另外处理；另外处理；另外处理；另外处理；检验数全部检

27、验数全部检验数全部检验数全部0 0 非基变量检验数非基变量检验数非基变量检验数非基变量检验数000第56页，本讲稿共100页 基变换基变换确定换出基变量 对应变量 为换出基的变量确定换入基变量 为主元素，为换入基变量原原原原则则则则：确确确确定定定定换换换换入入入入变变变变量量量量原原原原则则则则是是：在在保保保保持持持持对对对对偶偶偶偶可可可可行行行行的的的的前前前前提提提提下下，减减减减少少少少原始问题的不可行性原始问题的不可行性原始问题的不可行性原始问题的不可行性。第57页，本讲稿共100页初始可行基例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：对偶问题的初始可

28、行基第58页，本讲稿共100页例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：使对偶问题基变量可行,换出 换出换出第59页，本讲稿共100页例：用对偶单纯形法求解线性规划问题：第60页，本讲稿共100页最优解例：例：用对偶单纯形法求解线性规划问题：用对偶单纯形法求解线性规划问题：第61页，本讲稿共100页对偶单纯形法的优点：对偶单纯形法的优点：对偶单纯形法的优点：对偶单纯形法的优点：当约束条件为当约束条件为“”时，不必引进人工变时，不必引进人工变量，使计算简化；量，使计算简化；在灵敏度分析中，有时需要用对偶单纯形在灵敏度分析中，有时需要用对偶单纯形法处理简化。法处理简化

29、。对偶单纯形法缺点：对偶单纯形法缺点：对偶单纯形法缺点：对偶单纯形法缺点：在初始单纯形表中对偶问题是基可行解，在初始单纯形表中对偶问题是基可行解，这点对多数线性规划问题很难做到。这点对多数线性规划问题很难做到。因此，对偶单纯形法一般不单独使用。因此，对偶单纯形法一般不单独使用。第62页，本讲稿共100页练习：练习：P76,2.9（1）用对偶单纯形法求解线性规划问题：用对偶单纯形法求解线性规划问题：第63页，本讲稿共100页第第第第4 4 4 4节节节节 对偶单纯形法对偶单纯形法对偶单纯形法对偶单纯形法第64页，本讲稿共100页5.1 灵敏度问题及其图解法灵敏度问题灵敏度问题灵敏度分析灵敏度分析

30、图解法图解法第第第第5 5 5 5节节节节 灵敏度分析灵敏度分析灵敏度分析灵敏度分析第65页，本讲稿共100页背景：背景：线性规划问题中，线性规划问题中，都是常数，都是常数，但这些系数是估计值和预测值。但这些系数是估计值和预测值。市场的变化市场的变化 值变化；值变化；工艺的变化工艺的变化 值变化；值变化；资源的变化资源的变化 值变化。值变化。第第第第5.15.15.15.1节节节节 灵敏度问题灵敏度问题灵敏度问题灵敏度问题第66页，本讲稿共100页问题：问题：当这些系数系数中的一个或多个个或多个发生变化变化时，原最最优解优解会怎样变化？当这些系数在什么范围内变化什么范围内变化时，原最优解最优解

31、仍保持不变不变？若最优解最优解发生变化变化，如何如何用最简单的方法找找到现行的最优解最优解？第67页，本讲稿共100页研究内容：研究内容：研究线性规划中，研究线性规划中，的变化对的变化对最优解的影响。最优解的影响。研究方法：图解法图解法对偶理论分析对偶理论分析仅适用于含2个变量的线性规划问题在单纯形表中进行分析第68页，本讲稿共100页 MaxZ=34x1+40 x24x1+6x2 482x1+2x2 182x1+x2 16x1、x2 0 0线性规划模型灵敏度分析图解法 第69页，本讲稿共100页x2181614121086420|24681012141618x14x1+6x2 482x1+2

32、x2 182x1+x2 16ABCDE(8,0)(0,6.8)最优解最优解(3,6)4x1+6x2=48 2x1+2x2=18灵敏度分析图解法 第70页，本讲稿共100页灵敏度分析图解法 181614121086420|24681012141618x14x1+6x2 482x1+2x2 182x1+x2 16ABCDE目标函数的系数34x1+40 x2=Z40 x2=-34x1+Zx2=-+34x1Z4040第71页，本讲稿共100页灵敏度分析图解法 181614121086420|24681012141618x14x1+6x2 482x1+2x2 182x1+x2 16ABCDE目标函数的系

33、数34x1+40 x2=Z40 x2=-34x1+Zx2=-+c1x1Zc2c2若若若若 c c1 1增加增加增加增加（c c2 2 不变）不变）不变）不变）新的最优解新的最优解新的最优解新的最优解第72页，本讲稿共100页灵敏度分析图解法 181614121086420|24681012141618x14x1+6x2 482x1+2x2 182x1+x2 16ABCDE目标函数的系数34x1+40 x2=Z40 x2=-34x1+Zx2=-+c1x1Zc2c2若若若若 c c1 1减少减少减少减少新的最优解新的最优解新的最优解新的最优解第73页，本讲稿共100页181614121086420

34、|24681012141618x14x1+6x2 482x1+2x2 182x1+x2 16ABCDE(斜率=-1)(斜率=-2/3)灵敏度分析图解法 最优解不变的范围（设c1固定c2可变）第74页，本讲稿共100页 一、分析 的变化 二、分析 的变化 三、增加一个变量 的分析 四、分析 的变化 五、增加一个约束条件的分析第第第第5.25.25.25.2节节节节 灵敏度分析灵敏度分析灵敏度分析灵敏度分析第75页，本讲稿共100页研究内容：研究内容：研究线性规划中，研究线性规划中，的变的变化对最优解的影响。化对最优解的影响。常用公式：第76页，本讲稿共100页实例：实例：某家电厂家利用现有资源生

35、产两种产某家电厂家利用现有资源生产两种产品，有关数据如下表：品，有关数据如下表：设备A 设备B调试工序利润（元）0612521115时24时 5时D第77页，本讲稿共100页如何安排生产，使获利最多？厂家设设 产量产量 产量产量第78页，本讲稿共100页原问题最优解对偶问题最优解（相差负号）第79页，本讲稿共100页一、分析一、分析 的变化的变化 的变化仅影响 的变化。设备A 设备B调试工序利润（元）0612521115时24时 5时D1.52问题1：当 该公司最优生 产计划有何变化？第80页，本讲稿共100页最终单纯形表最终单纯形表05/41.5 1/4+2（-1/4）-1/80-（-1/8

36、）=第81页，本讲稿共100页最终单纯形表第82页，本讲稿共100页最优解换基后单纯形表为第83页，本讲稿共100页 问题问题2：设产品：设产品II利润为利润为 ，求原最优解不变时求原最优解不变时 的范围。的范围。的变化仅影响 的变化；在最后一张单纯形表中求出变化的 ；原最优解不变，即 ；由上述不等式可求出 的范围。方法：第84页，本讲稿共100页即产品II利润为 时的最终单纯形表第85页，本讲稿共100页二、分析二、分析 的变化的变化 的变化仅影响的变化仅影响 ，即原最优解的，即原最优解的可行性可能会变化：可行性可能会变化：可行性不变，则原最优解不变。可行性不变，则原最优解不变。可行性改变，

37、则原最优解改变，可行性改变，则原最优解改变，用对偶单纯形法，找出最优解用对偶单纯形法，找出最优解。第86页，本讲稿共100页问题问题3：设备：设备B B的能力增加到的能力增加到32小时，小时，原最优计划有何变化？原最优计划有何变化？第87页，本讲稿共100页代入单纯形表中可行性改变，用对偶单纯可行性改变，用对偶单纯形法换基求解。形法换基求解。主元第88页，本讲稿共100页新的最优解换基迭代得：第89页，本讲稿共100页问题问题4：设调试工序可用时间为：设调试工序可用时间为 小时，求小时，求 ，原最优解保持不变。，原最优解保持不变。原最优解保持不变，则原最优解保持不变，则第90页，本讲稿共100

38、页三、增加一个变量三、增加一个变量 的分析的分析 增加一个变量相当于增加一种产品。增加一个变量相当于增加一种产品。分析步骤：分析步骤：1、计算、计算2、计算、计算3、若、若 原最优解不变；原最优解不变；若若 ，则按单纯形表继续迭代，则按单纯形表继续迭代;第91页，本讲稿共100页问题问题5：设生产第三种产品，产量为：设生产第三种产品，产量为 件，件，对应的对应的 求最优生产计划。求最优生产计划。解：第92页，本讲稿共100页代入最终原单纯形表中代入最终原单纯形表中主元第93页，本讲稿共100页换基后有：换基后有：第94页，本讲稿共100页四、分析四、分析 的变化的变化若 对应的 变量 为基变量

39、，B将改变。需引入人工变量求出可行解，再用单纯形法求解。若 对应的变量 为非基变量，参见三的分析。第95页，本讲稿共100页五、增加一个约束条件的分析五、增加一个约束条件的分析 增加一个约束条件相当于增添一道工序。增加一个约束条件相当于增添一道工序。分析方法：将最优解代入新的约束中将最优解代入新的约束中（1）若满足要求，则原最优解不变；）若满足要求，则原最优解不变；（2）若不满足要求，则原最优解改变，）若不满足要求，则原最优解改变，将新增的约束条件添入最终的将新增的约束条件添入最终的单纯形表中继续分析。单纯形表中继续分析。第96页，本讲稿共100页灵敏度分析的步骤归纳如下：灵敏度分析的步骤归纳

40、如下：（1）将参数的改变计算反映到最终）将参数的改变计算反映到最终 单纯形表上；单纯形表上；（2）检查原问题是否仍为可行解；）检查原问题是否仍为可行解；（3）检查对偶问题是否仍为可行解；）检查对偶问题是否仍为可行解；（4）按下表所列情况得出结论和决）按下表所列情况得出结论和决 定继续计算的步骤。定继续计算的步骤。第97页，本讲稿共100页原问题 对偶问题 结论或继续计算的步骤可行解 可行解 问题的最优解或最优基不变可行解 非可行解 用单纯形法继续迭代非可行解 可行解 用对偶单纯形法继续迭代非可行解 非可行解 编制新的单纯形表重新计算总之第98页，本讲稿共100页作业：教材作业：教材P77，2.12题的题的（1）、（）、（2）、（）、（3）小题）小题第99页，本讲稿共100页 第第第第5 5 5 5节节节节 灵敏度分析灵敏度分析灵敏度分析灵敏度分析第100页，本讲稿共100页