《第二章对偶理论及灵敏度分析精选文档.ppt》由会员分享，可在线阅读，更多相关《第二章对偶理论及灵敏度分析精选文档.ppt（100页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章第二章 对偶理论及对偶理论及灵敏度分析灵敏度分析本讲稿第一页，共一百页第第第第1 1 1 1节节节节 线性规划的对偶问题线性规划的对偶问题线性规划的对偶问题线性规划的对偶问题一、对偶问题的提出一、对偶问题的提出二、原问题与对偶问题的数学模型二、原问题与对偶问题的数学模型三、原问题与对偶问题的对应关系三、原问题与对偶问题的对应关系本讲稿第二页，共一百页实例：某家电厂家利用现有资源生产实例：某家电厂家利用现有资源生产两种产品，两种产品，有关数据如下表：有关数据如下表：设备设备A 设备设备B调试工序调试工序利润（元）利润（元）0612521115时时24时时 5时时产品产品产品产品D一、对偶问
2、题的提出一、对偶问题的提出本讲稿第三页，共一百页如何安排生产，如何安排生产，使获利最多使获利最多？厂厂家家设设 产量产量 产量产量一、对偶问题的提出一、对偶问题的提出本讲稿第四页，共一百页 设：设备设：设备A A 元时元时 设备设备B B 元时元时 调试工序调试工序 元时元时收收购购 付出的代价最小，付出的代价最小，且对方能接受。且对方能接受。出让代价应不低于用同等数量的资源自己生产的利润。一、对偶问题的提出一、对偶问题的提出本讲稿第五页，共一百页 设备设备A 设备设备B调试工序调试工序利润（元）利润（元）0612521115时时24时时 5时时D厂家能接受的条件：厂家能接受的条件：收购方的意
3、愿：收购方的意愿：单位产品单位产品出租出租收入不低于收入不低于2 2元元单位产品单位产品出租出租收入不低于收入不低于1 1元元出让代价应不低于用同等数量的资源自己生产的利润。本讲稿第六页，共一百页厂厂家家对对偶偶问问题题原原问问题题收收购购厂厂家家一对对偶问题一对对偶问题本讲稿第七页，共一百页3 3个约束个约束2 2个变量个变量2 2个约束个约束 3 3个变量个变量原问题原问题对偶问题对偶问题一一般般规规律律本讲稿第八页，共一百页 特点：特点：1 2限定向量限定向量b 价值向量价值向量C （资源向量）资源向量）3一个约束一个约束 一个变量。一个变量。4 的的LP约束约束“”的的 LP是是“”的
4、约束。的约束。5变量都是非负限制。变量都是非负限制。其它形式其它形式的对偶的对偶?本讲稿第九页，共一百页二、原问题与对偶问题的数学模型二、原问题与对偶问题的数学模型1、对称形式的对偶、对称形式的对偶 当原问题对偶问题只含有不等式约束时，当原问题对偶问题只含有不等式约束时，称为对称形式的对偶。称为对称形式的对偶。原问题原问题对偶问题对偶问题情形一：情形一：本讲稿第十页，共一百页原问题原问题对偶问题对偶问题化为标准对称型情形二：情形二：证明证明对偶对偶本讲稿第十一页，共一百页2、非对称形式的对偶非对称形式的对偶 若原问题的约束条件是等式，则若原问题的约束条件是等式，则原问题原问题对偶问题对偶问题本
5、讲稿第十二页，共一百页推导推导:原问题原问题本讲稿第十三页，共一百页 根据对称形式的对偶模型根据对称形式的对偶模型,可直接写出可直接写出上述问题的对偶问题上述问题的对偶问题:本讲稿第十四页，共一百页令令 ，得对偶问题为：得对偶问题为：证毕。证毕。本讲稿第十五页，共一百页三、原问题与对偶问题的对应关系三、原问题与对偶问题的对应关系 原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）本讲稿第十六页，共一百页例例:本讲稿第十七页，共一百页对偶问题为：对偶问题为：本讲稿第十八页，共一百页第第第第1 1 1 1节节节节 线性规划的对偶问题线性规划的对偶问题线性规划的对偶问题
6、线性规划的对偶问题本讲稿第十九页，共一百页一、单纯形法计算的矩阵描述一、单纯形法计算的矩阵描述二、引例二、引例三、对偶问题的基本性质三、对偶问题的基本性质 1、对称定理、对称定理 2、弱对偶性定理、弱对偶性定理 3、最优性定理、最优性定理 4、对偶定理（强对偶性）、对偶定理（强对偶性）5、互补松弛定理、互补松弛定理第第第第2 2 2 2节节节节 对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质本讲稿第二十页，共一百页对称形式线性规划问题加上对称形式线性规划问题加上松弛变量松弛变量 后为：后为：一、单纯形法计算的矩阵描述一、单纯形法计算的矩阵描述项目项目非基变量非基变量基
7、变量基变量 0 bB NI0初始单纯形表为：初始单纯形表为：本讲稿第二十一页，共一百页当迭代若干步，基变量为当迭代若干步，基变量为 时，则该步的单纯形时，则该步的单纯形 表表中由中由 系数矩阵组成的矩阵为系数矩阵组成的矩阵为I。故当基变量为。故当基变量为 时，新的单纯形表如下：时，新的单纯形表如下：一、单纯形法计算的矩阵描述一、单纯形法计算的矩阵描述项目项目基变量基变量非基变量非基变量 I0本讲稿第二十二页，共一百页对对偶偶问问题题原原问问题题收收购购厂厂家家二、引例二、引例本讲稿第二十三页，共一百页（）原问题原问题的变量的变量原问题松弛变量原问题松弛变量对偶问题对偶问题剩余变量剩余变量对偶问
8、题的变量对偶问题的变量化为极小问题原问题化为极小问题，最终单纯形表：原问题化为极小问题，最终单纯形表：本讲稿第二十四页，共一百页原问题的变量原问题的变量原问题松弛变量原问题松弛变量对偶问题剩余变量对偶问题剩余变量对偶问题的变量对偶问题的变量对偶问题用两阶段法求解的最终的单纯形表对偶问题用两阶段法求解的最终的单纯形表本讲稿第二十五页，共一百页（）原问题原问题的变量的变量原问题松弛变量原问题松弛变量对偶问题对偶问题剩余变量剩余变量对偶问题的变量对偶问题的变量化为极小问题原问题最优解对偶问题最优解原问题化为极小问题，最终单纯形表：原问题化为极小问题，最终单纯形表：本讲稿第二十六页，共一百页两个问题比
9、较两个问题比较:1、两者的最优值相同2、变量的解在两个单纯形表中互相包含原问题最优解原问题最优解（决策变量）对偶问题最优解对偶问题最优解（决策变量）对偶问题的松弛变量对偶问题的松弛变量原问题的松弛变量原问题的松弛变量本讲稿第二十七页，共一百页从引例中可见：从引例中可见：原问题与对偶问题在某种意义上来原问题与对偶问题在某种意义上来说，实质上是一样的，因为第二个问题说，实质上是一样的，因为第二个问题仅仅在第一个问题的另一种表达而已。仅仅在第一个问题的另一种表达而已。本讲稿第二十八页，共一百页一、对称定理：一、对称定理：定理：对偶问题的对偶是原问题。定理：对偶问题的对偶是原问题。设原问题（设原问题（
10、1 1）对偶问题（对偶问题（2 2）三、对偶问题的基本性质三、对偶问题的基本性质本讲稿第二十九页，共一百页二、弱对偶性定理：二、弱对偶性定理：若若 和和 分别是原问题（分别是原问题（1 1）及）及对偶问题（对偶问题（2 2）的可行解，）的可行解，则有 证明：证明：三、对偶问题的基本性质三、对偶问题的基本性质本讲稿第三十页，共一百页（1 1）极大化问题（）极大化问题（原问题原问题）的任一）的任一可行解可行解所所对应对应的的目标函数值目标函数值是对偶问题是对偶问题最优目标函数值最优目标函数值的的下下界界。（2 2）极小化问题（）极小化问题（对偶问题对偶问题）的任一）的任一可行解可行解所所对对应应的
11、的目标函数值目标函数值是原问题是原问题最优目标函数值最优目标函数值的的上上界界。（3 3）若）若原问题可行原问题可行，但其，但其目标函数值无界目标函数值无界，则，则对对偶问题无可行解偶问题无可行解。由弱对偶性可得以下结论：由弱对偶性可得以下结论：三、对偶问题的基本性质三、对偶问题的基本性质本讲稿第三十一页，共一百页（4 4）若对偶问题可行，但其目标函数值无界，则原问题无）若对偶问题可行，但其目标函数值无界，则原问题无可行解。可行解。（5 5）若原问题有可行解而其对偶问题无可行解，则原问题目标）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界。函数值无界。（6 6）对偶问题有可行解而
12、其原问题无可行解，则对偶问题）对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界的目标函数值无界。原问题对偶问题三、对偶问题的基本性质三、对偶问题的基本性质本讲稿第三十二页，共一百页三、最优性定理：三、最优性定理：若若 和和 分别是（分别是（1 1）和（）和（2 2）的可行解，且有的可行解，且有 则则 分分别是（别是（1 1）和（）和（2 2）的最优解）的最优解 。三、对偶问题的基本性质三、对偶问题的基本性质本讲稿第三十三页，共一百页证明：证明：原问题与对偶问题的解一般有三种情况原问题与对偶问题的解一般有三种情况：一个有有限最优解一个有有限最优解 另一个有有限最优解。另一个有有限最
13、优解。一个有无界解一个有无界解 另一个无可行解。另一个无可行解。两个均无可行解。两个均无可行解。四、强对偶性（对偶定理）：四、强对偶性（对偶定理）：若原问题及其对偶问题均具有可行解，若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函则两者均具有最优解，且它们最优解的目标函数值相等。数值相等。三、对偶问题的基本性质三、对偶问题的基本性质本讲稿第三十四页，共一百页五、互补松弛性：五、互补松弛性：若若 分别是原问题（分别是原问题（1 1）与对）与对偶问题（偶问题（2 2）的可行解，）的可行解，分别为分别为（1 1）、（）、（2 2）的松弛变量，则：）的松弛变量，则：为最优解为
14、最优解三、对偶问题的基本性质三、对偶问题的基本性质 说明：说明：在线性规划问题的最优解中，如果对应某一约在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。偶变量一定为零。本讲稿第三十五页，共一百页（1）从已知的最优对偶解，求原问题最）从已知的最优对偶解，求原问题最优解，反之亦然。优解，反之亦然。（2）证实原问题可行解是否为最优解。）证实原问题可行解是否为最优解。（3）从不同假设来进行试算，从而研究）从不同假
15、设来进行试算，从而研究原始、对偶问题最优解的一般性质。原始、对偶问题最优解的一般性质。（4）非线性的方面的应用。）非线性的方面的应用。以上性质同样适用于非对称形式。以上性质同样适用于非对称形式。互补松弛定理应用互补松弛定理应用本讲稿第三十六页，共一百页第第第第2 2 2 2节节节节 对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质对偶问题的基本性质本讲稿第三十七页，共一百页在单纯形法的每步迭代中，在单纯形法的每步迭代中，目标函数取值目标函数取值 ，和检和检验数验数 中都有乘子中都有乘子 ，那么那么Y Y的经济意义是什么？的经济意义是什么？第第第第3 3 3 3节节节节 影子价格影子价格影
16、子价格影子价格本讲稿第三十八页，共一百页 当线性规划原问题求得最优解当线性规划原问题求得最优解时，其对偶问题也得到最优解时，其对偶问题也得到最优解 ，且代入各自的目标函数后有：，且代入各自的目标函数后有：是线性规划原问题约束条件的是线性规划原问题约束条件的右端项，它代表第右端项，它代表第 种资源的拥有量；种资源的拥有量；（1）影子价格的经济意义影子价格的经济意义本讲稿第三十九页，共一百页 对偶变量对偶变量 的意义的意义代表在资源最优代表在资源最优利用条件下对利用条件下对单位单位第第 种资源的种资源的估价估价，这种估价不是资源的市场价格，而是根这种估价不是资源的市场价格，而是根据资源在生产中作出
17、的贡献而作的估价，据资源在生产中作出的贡献而作的估价，为区别起见，称为为区别起见，称为影子价格影子价格（shadow price)。影子价格的经济意义影子价格的经济意义本讲稿第四十页，共一百页1、资源的市场价格是已知数，相对比较稳、资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利定，而它的影子价格则有赖于资源的利用情况，是未知数。由于企业生产任务、用情况，是未知数。由于企业生产任务、产品结构等情况发生变化，资源的影子产品结构等情况发生变化，资源的影子价格也随之改变。价格也随之改变。市场价格影子价格市场企业影子价格的经济意义影子价格的经济意义本讲稿第四十一页，共一百页2、影子
18、价格是一种边际价格。、影子价格是一种边际价格。在（在（1）式中，）式中，。说明说明 的值相当于在资源得到最的值相当于在资源得到最优利用的生产条件下，优利用的生产条件下，每增加每增加一个一个单位单位时时目标函数目标函数 的的增量增量。影子价格的经济意义影子价格的经济意义本讲稿第四十二页，共一百页几何解释：引例图解法分析几何解释：引例图解法分析（3，3）（15/4，5/4）,z=8.75（7/2，3/2），z=8.5本讲稿第四十三页，共一百页3、资源的影子价格实际上又是一种机会成本、资源的影子价格实际上又是一种机会成本.在纯市场经济条件下在纯市场经济条件下,当第当第2种资源的市场价格种资源的市场价
19、格低于低于1/4时，可以买进这种资源；相反当市场价格时，可以买进这种资源；相反当市场价格高于影子价格时，就会卖出这种资源。随着资源高于影子价格时，就会卖出这种资源。随着资源的买进卖出，它的影子价格也将随之发生变化，的买进卖出，它的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才一直到影子价格与市场价格保持同等水平时，才处于平衡状态。处于平衡状态。影子价格的经济意义影子价格的经济意义本讲稿第四十四页，共一百页4、在对偶问题的互补松弛性质中有、在对偶问题的互补松弛性质中有 这表明生产过程中如果某种资源这表明生产过程中如果某种资源 未得到充分未得到充分利用时，该种资源的影子价格为
20、零；又当资源的影利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完子价格不为零时，表明该种资源在生产中已耗费完毕。毕。影子价格的经济意义影子价格的经济意义本讲稿第四十五页，共一百页5、从影子价格的含义上考察单纯形表的、从影子价格的含义上考察单纯形表的 检验数的经济意义。检验数的经济意义。（2）第j种产品的产值生产第j中产品所消耗各项资源的影子价格的总和。（即隐含成本）可见，产品产值可见，产品产值隐含成本隐含成本 可生产该产品；可生产该产品；否则，不安排生产。否则，不安排生产。检验数的经济意义检验数的经济意义影子价格的经济意义影子价格的经济意义本讲稿第四十六
21、页，共一百页 6、一般说对、一般说对线性规划问题线性规划问题的求解是的求解是确定资源的确定资源的最优分配方案最优分配方案，而对于，而对于对对偶问题偶问题的求解则是确定的求解则是确定对资源的恰当对资源的恰当估价估价，这种估价直接涉及到资源的最，这种估价直接涉及到资源的最有效利用。有效利用。经济学研究如何管理自己的稀缺资源影子价格的经济意义影子价格的经济意义本讲稿第四十七页，共一百页第第第第3 3 3 3节节节节 影子价格影子价格影子价格影子价格本讲稿第四十八页，共一百页对偶单纯形法的基本思路对偶单纯形法的基本思路对偶单纯形法的计算步骤对偶单纯形法的计算步骤第第第第4 4 4 4节节节节 对偶单纯
22、形法对偶单纯形法对偶单纯形法对偶单纯形法本讲稿第四十九页，共一百页一、什么是对偶单纯形法？一、什么是对偶单纯形法？对对偶偶单单纯纯形形法法是是应应用用对对偶偶原原理理求求解解原原始始线线性性规规划划的的一一种种方方法法在在原原始始问问题题的的单单纯形表格上进行纯形表格上进行对偶处理对偶处理。注意：注意：不是解对偶问题的单纯形法！不是解对偶问题的单纯形法！本讲稿第五十页，共一百页 二、对偶单纯形法的基本思想二、对偶单纯形法的基本思想1、对对“单单纯纯形形法法”求求解解过过程程认认识识的的提提升升从更高的角度理解单纯形法从更高的角度理解单纯形法初始可行基初始可行基初始可行基初始可行基（对应一个初始
23、基可行解）（对应一个初始基可行解）迭迭代代另另一一个个可可行行基基（对对应应另另一一个个基基可可行行解），直至解），直至所有检验数所有检验数0为止为止。本讲稿第五十一页，共一百页 所有检验数所有检验数意味着意味着说说明明原原始始问问题题的的最最优优基基也也是是对对偶偶问问题题的的可可行行基基。换换言言之之，当当原原始始问问题题的的基基B既既是是原原始始可可行行基基又又是是对偶可行基时，对偶可行基时，B成为最优基。成为最优基。定定理理B是是线线性性规规划划的的最最优优基基的的的的充充要要条条件件是是，B B是是可行基，同时也是对偶可行基。可行基，同时也是对偶可行基。本讲稿第五十二页，共一百页（对
24、偶）单纯形法的基本思路：（对偶）单纯形法的基本思路：原问题基可行解原问题基可行解 最优解判断最优解判断对偶问题的可行解对偶问题最优解判断对偶单纯形法对偶单纯形法基本思路基本思路本讲稿第五十三页，共一百页单纯形法的求解过程就是：单纯形法的求解过程就是：在保持在保持在保持在保持原始可行原始可行的前提下的前提下（b列保持列保持0）通过逐步迭代通过逐步迭代通过逐步迭代通过逐步迭代实现对偶可行实现对偶可行（检验数行（检验数行0）。2、对偶单纯形法思想：对偶单纯形法思想：换换个个角角度度考考虑虑LPLP求求求求解解解解过过过过程程程程：保保持持对对偶偶可可行行的的前前提提下下（检检检检验验验验数数数数行行
25、行行保保保保持持持持00），通通过过逐逐步步迭迭代代实实现现原原始可行始可行（b列列0，从非可行解变成可行解）。，从非可行解变成可行解）。本讲稿第五十四页，共一百页三、对偶单纯形法的实施三、对偶单纯形法的实施1、使用条件：、使用条件：检验数全部检验数全部检验数全部检验数全部00；b列至少一个元素列至少一个元素列至少一个元素列至少一个元素00；2 2、实施对偶单纯形法的基本原则：、实施对偶单纯形法的基本原则：、实施对偶单纯形法的基本原则：、实施对偶单纯形法的基本原则：在保持对偶可行的前提下进行基变换在保持对偶可行的前提下进行基变换在保持对偶可行的前提下进行基变换在保持对偶可行的前提下进行基变换每
26、一每一次迭代过程中取出次迭代过程中取出基变量中的一个负分量基变量中的一个负分量作为作为换换换换出变量出变量出变量出变量去去替换替换替换替换某个某个非基变量非基变量非基变量非基变量（作为（作为换入变量换入变量换入变量换入变量），使），使原始问题的非可行解向可行解靠近。原始问题的非可行解向可行解靠近。本讲稿第五十五页，共一百页3、计算步骤、计算步骤：建立初始单纯形表，计算检验数行。建立初始单纯形表，计算检验数行。b b列列列列00已得最优解；已得最优解；已得最优解；已得最优解；至少一个元素至少一个元素至少一个元素至少一个元素0,0,转下步转下步转下步转下步;b b列列列列00原始单纯形法；原始单纯
27、形法；原始单纯形法；原始单纯形法；至少一个元素至少一个元素至少一个元素至少一个元素0,0,另外处理；另外处理；另外处理；另外处理；检验数全部检验数全部检验数全部检验数全部0 0 非基变量检验数非基变量检验数非基变量检验数非基变量检验数000本讲稿第五十六页，共一百页 基变换基变换确定换出基变量 对应变量 为换出基的变量确定换入基变量 为主元素，为换入基变量原原原原则则则则：确确确确定定定定换换换换入入入入变变变变量量量量原原原原则则则则是是：在在保保保保持持持持对对对对偶偶偶偶可可可可行行行行的的的的前前前前提提提提下下，减减减减少少少少原原原原始问题的不可行性始问题的不可行性始问题的不可行性
28、始问题的不可行性。本讲稿第五十七页，共一百页初始可行基例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：对偶问题的初始可行基本讲稿第五十八页，共一百页例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：使对偶问题基变量可行,换出 换出换出换出本讲稿第五十九页，共一百页例：例：用对偶单纯形法求解线性规划问题：用对偶单纯形法求解线性规划问题：本讲稿第六十页，共一百页最优解例：例：用对偶单纯形法求解线性规划问题：用对偶单纯形法求解线性规划问题：本讲稿第六十一页，共一百页对偶单纯形法的优点：对偶单纯形法的优点：当约束条件为当约束条件为“”时，不必引进人工变量，
29、使时，不必引进人工变量，使计算简化；计算简化；在灵敏度分析中，有时需要用对偶单纯形法处在灵敏度分析中，有时需要用对偶单纯形法处理简化。理简化。对偶单纯形法缺点：对偶单纯形法缺点：对偶单纯形法缺点：对偶单纯形法缺点：在初始单纯形表中对偶问题是基可行解，在初始单纯形表中对偶问题是基可行解，这点对多数线性规划问题很难做到。这点对多数线性规划问题很难做到。因此，对偶单纯形法一般不单独使用。因此，对偶单纯形法一般不单独使用。本讲稿第六十二页，共一百页练习：练习：P76,2.9（1）用对偶单纯形法求解线性规划问题：用对偶单纯形法求解线性规划问题：本讲稿第六十三页，共一百页第第第第4 4 4 4节节节节 对
30、偶单纯形法对偶单纯形法对偶单纯形法对偶单纯形法本讲稿第六十四页，共一百页5.1灵敏度问题及其图解法灵敏度问题及其图解法灵敏度问题灵敏度问题灵敏度分析灵敏度分析图解法图解法第第第第5 5 5 5节节节节 灵敏度分析灵敏度分析灵敏度分析灵敏度分析本讲稿第六十五页，共一百页背景：背景：线性规划问题中，线性规划问题中，都是常数，都是常数，但这些系数是估计值和预测值。但这些系数是估计值和预测值。市场的变化市场的变化 值变化；值变化；工艺的变化工艺的变化 值变化；值变化；资源的变化资源的变化 值变化。值变化。第第第第5.15.15.15.1节节节节 灵敏度问题灵敏度问题灵敏度问题灵敏度问题本讲稿第六十六页
31、，共一百页问题：问题：当这些系数系数中的一个或多个个或多个发生变化变化时，原最优最优解解会怎样变化？当这些系数在什么范围内变化什么范围内变化时，原最优解最优解仍保持不变不变？若最优解最优解发生变化变化，如何如何用最简单的方法找找到现行的最优解最优解？本讲稿第六十七页，共一百页研究内容：研究内容：研究线性规划中，研究线性规划中，的变化对的变化对最优解的影响最优解的影响。研究方法：图解法图解法对偶理论分析对偶理论分析仅适用于含2个变量的线性规划问题在单纯形表中进行分析本讲稿第六十八页，共一百页 MaxZ=34x1+40 x24x1+6x2 482x1+2x2 182x1+x2 16x1、x2 0
32、0线性规划模型线性规划模型灵敏度分析图解法 本讲稿第六十九页，共一百页x2181614121086420|24681012141618x14x1+6x2 482x1+2x2 182x1+x2 16ABCDE(8,0)(0,6.8)最优解最优解(3,6)4x1+6x2=48 2x1+2x2=18灵敏度分析图解法 本讲稿第七十页，共一百页灵敏度分析图解法 181614121086420|24681012141618x14x1+6x2 482x1+2x2 182x1+x2 16ABCDE目标函数的系数目标函数的系数34x1+40 x2=Z40 x2=-34x1+Zx2=-+34x1Z4040本讲稿第
33、七十一页，共一百页灵敏度分析图解法 181614121086420|24681012141618x14x1+6x2 482x1+2x2 182x1+x2 16ABCDE目标函数的系数目标函数的系数34x1+40 x2=Z40 x2=-34x1+Zx2=-+c1x1Zc2c2若若若若 c c1 1增加增加增加增加（c c2 2 不变）不变）不变）不变）新的最优解新的最优解新的最优解新的最优解本讲稿第七十二页，共一百页灵敏度分析图解法 181614121086420|24681012141618x14x1+6x2 482x1+2x2 182x1+x2 16ABCDE目标函数的系数目标函数的系数34
34、x1+40 x2=Z40 x2=-34x1+Zx2=-+c1x1Zc2c2若若若若 c c1 1减少减少减少减少新的最优解新的最优解新的最优解新的最优解本讲稿第七十三页，共一百页181614121086420|24681012141618x14x1+6x2 482x1+2x2 182x1+x2 16ABCDE(斜率斜率=-1)=-1)(斜率斜率=-2/3)=-2/3)灵敏度分析图解法 最优解不变的范围最优解不变的范围（设（设c1固定固定c2可变）可变）本讲稿第七十四页，共一百页 一、分析一、分析 的变化的变化 二、分析二、分析 的变化的变化 三、增加一个变量三、增加一个变量 的分析的分析 四、
35、分析四、分析 的变化的变化 五、增加一个约束条件的分析五、增加一个约束条件的分析第第第第5.25.25.25.2节节节节 灵敏度分析灵敏度分析灵敏度分析灵敏度分析本讲稿第七十五页，共一百页研究内容：研究内容：研究线性规划中，研究线性规划中，的变的变化对最优解的影响。化对最优解的影响。常用公式：常用公式：本讲稿第七十六页，共一百页实例：实例：某家电厂家利用现有资源生产两种产某家电厂家利用现有资源生产两种产品，有关数据如下表：品，有关数据如下表：设备设备A 设备设备B调试工序调试工序利润（元）利润（元）0612521115时时24时时 5时时D本讲稿第七十七页，共一百页如何安排生产，如何安排生产，
36、使获利最多？使获利最多？厂家设设 产量产量 产量产量本讲稿第七十八页，共一百页原问题最优解对偶问题最优解（相差负号）本讲稿第七十九页，共一百页一、分析一、分析 的变化的变化 的变化仅影响 的变化。设备设备A 设备设备B调试工序调试工序利润（元）利润（元）0612521115时时24时时 5时时D1.52问题1：当 该公司最优生 产计划有何变化？本讲稿第八十页，共一百页最终单纯形表最终单纯形表05/41.5 1/4+2（-1/4）-1/80-（-1/8）=本讲稿第八十一页，共一百页最终单纯形表最终单纯形表本讲稿第八十二页，共一百页最优解换基后单纯形表为换基后单纯形表为本讲稿第八十三页，共一百页
37、问题问题2：设产品：设产品II利润为利润为 ，求原最优解不变时求原最优解不变时 的范围。的范围。的变化仅影响的变化仅影响的变化；的变化；在最后一张单纯形表中求出变化的在最后一张单纯形表中求出变化的；原最优解不变，即原最优解不变，即；由上述不等式可求出由上述不等式可求出的范围。的范围。方法：方法：本讲稿第八十四页，共一百页即即产品产品II利润为利润为时的最终单纯形表时的最终单纯形表本讲稿第八十五页，共一百页二、分析二、分析 的变化的变化 的变化仅影响的变化仅影响 ，即原最优解的，即原最优解的可行性可能会变化：可行性可能会变化：可行性不变，则原最优解不变。可行性不变，则原最优解不变。可行性改变，则
38、原最优解改变，可行性改变，则原最优解改变，用对偶单纯形法，找出最优解用对偶单纯形法，找出最优解。本讲稿第八十六页，共一百页问题问题3：设备：设备B B的能力增加到的能力增加到32小时，小时，原最优计划有何变化？原最优计划有何变化？本讲稿第八十七页，共一百页代入单纯形表中代入单纯形表中可行性改变，用对偶单纯形法换基求解。主元本讲稿第八十八页，共一百页新的最优解换基迭代得：换基迭代得：本讲稿第八十九页，共一百页问题问题4：设调试工序可用时间为：设调试工序可用时间为 小时，求小时，求 ，原最优解保持不变。，原最优解保持不变。原最优解保持不变，则原最优解保持不变，则本讲稿第九十页，共一百页三、增加一个
39、变量三、增加一个变量 的分析的分析 增加一个变量相当于增加一种产品。增加一个变量相当于增加一种产品。分析步骤：分析步骤：1、计算、计算2、计算、计算3、若、若 原最优解不变；原最优解不变；若若 ，则按单纯形表继续迭代，则按单纯形表继续迭代;本讲稿第九十一页，共一百页问题问题5：设生产第三种产品，产量为：设生产第三种产品，产量为 件，件，对应的对应的 求最优生产计划。求最优生产计划。解：解：本讲稿第九十二页，共一百页代入最终原单纯形表中代入最终原单纯形表中主元本讲稿第九十三页，共一百页换基后有：换基后有：本讲稿第九十四页，共一百页四、分析四、分析 的变化的变化若若对应的对应的变量变量为基变量，为
40、基变量，B将改变。需引入人工变量求出将改变。需引入人工变量求出可行解，再用单纯形法求解。可行解，再用单纯形法求解。若若对应的变量对应的变量为非基变量，参见三的分析为非基变量，参见三的分析。本讲稿第九十五页，共一百页五、增加一个约束条件的分析五、增加一个约束条件的分析 增加一个约束条件相当于增添一道工序。增加一个约束条件相当于增添一道工序。分析方法：分析方法：将最优解代入新的约束中将最优解代入新的约束中（1）若满足要求，则原最优解不变；）若满足要求，则原最优解不变；（2）若不满足要求，则原最优解改变，）若不满足要求，则原最优解改变，将新增的约束条件添入最终的将新增的约束条件添入最终的单纯形表中继
41、续分析。单纯形表中继续分析。本讲稿第九十六页，共一百页灵敏度分析的步骤归纳如下：灵敏度分析的步骤归纳如下：（1）将参数的改变计算反映到最终）将参数的改变计算反映到最终 单纯形表上；单纯形表上；（2）检查原问题是否仍为可行解；）检查原问题是否仍为可行解；（3）检查对偶问题是否仍为可行解；）检查对偶问题是否仍为可行解；（4）按下表所列情况得出结论和决）按下表所列情况得出结论和决 定继续计算的步骤。定继续计算的步骤。本讲稿第九十七页，共一百页原问题原问题对偶问题对偶问题结论或继续计算的步骤结论或继续计算的步骤可行解可行解可行解可行解问题的最优解或最优基不变问题的最优解或最优基不变可行解可行解非可行解非可行解用单纯形法继续迭代用单纯形法继续迭代非可行解非可行解可行解可行解用对偶单纯形法继续迭代用对偶单纯形法继续迭代非可行解非可行解非可行解非可行解编制新的单纯形表重新计算编制新的单纯形表重新计算总之本讲稿第九十八页，共一百页作业：教材作业：教材P77，2.12题的题的（1）、（）、（2）、（）、（3）小题）小题本讲稿第九十九页，共一百页第第第第5 5 5 5节节节节 灵敏度分析灵敏度分析灵敏度分析灵敏度分析本讲稿第一百页，共一百页