三章节对偶理论及灵敏度分析.ppt

《三章节对偶理论及灵敏度分析.ppt》由会员分享，可在线阅读，更多相关《三章节对偶理论及灵敏度分析.ppt（117页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题三章节对偶理论及灵敏度分析 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望返回返回返回返回继续继续继续继续3.1.1 3.1.1 3.1.1 3.1.1 线性规划的对偶问题线性规划的对偶问题线性规划的对偶问题线性规划的对偶问题n一、对偶问题的提出一、对偶问题的提出n二、原问题与对偶问题的数学模型二、原问题与对偶问题的数学模型n三、原问题与对偶问题的对应关系三、原问题与对偶问题的对应关系

2、返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题实例：某家电厂家利用现有资源生产两种实例：某家电厂家利用现有资源生产两种 产品，产品，有关数据如下表：有关数据如下表：设备设备A 设备设备B调试工序调试工序利润（元）利润（元）0612521115时时24时时 5时时产品产品产品产品D一、对偶问题的提出一、对偶问题的提出返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题如何安排生产，如何安排生产，使获利最多使获利最多？厂厂家家设设 产量产量 产量产量返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题 设：设

3、备设：设备A A 元时元时 设备设备B B 元时元时 调试工序调试工序 元时元时收收购购 付出的代价最小，付出的代价最小，且对方能接受。且对方能接受。出让代价应不低于出让代价应不低于用同等数量的资源用同等数量的资源自己生产的利润。自己生产的利润。返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题 设备设备A 设备设备B调试工序调试工序利润（元）利润（元）0612521115时时24时时 5时时Dn厂家能接受的条件：厂家能接受的条件：n收购方的意愿：收购方的意愿：单位产品单位产品出租出租收入不低于收入不低于2 2元元单位产品单位产品出租出租收入不低于收入不低于1 1

4、元元出让代价应不低于出让代价应不低于用同等数量的资源用同等数量的资源自己生产的利润。自己生产的利润。返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题厂厂家家对对偶偶问问题题原原问问题题收收购购厂厂家家一对对偶问题一对对偶问题返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题3 3个约束个约束2 2个变量个变量2 2个约束个约束 3 3个变量个变量原问题原问题对偶问题对偶问题一般规律返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题 特点：特点：1 2限定向量限定向量b 价值向量价值向量C （资源向量）资

5、源向量）3一个约束一个约束 一个变量。一个变量。4 的的LP约束约束“”的的 LP是是“”的约束。的约束。5变量都是非负限制。变量都是非负限制。其它形式其它形式的对偶的对偶?返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题二、原问题与对偶问题的数学模型二、原问题与对偶问题的数学模型n1对称形式的对偶对称形式的对偶 当原问题对偶问题只含有不等式约束时，当原问题对偶问题只含有不等式约束时，称为对称形式的对偶。称为对称形式的对偶。原问题原问题对偶问题对偶问题情形一：情形一：返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题原问题原问题对偶

6、问题对偶问题化为标准对称型化为标准对称型情形二：情形二：证明证明对偶对偶返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题n2、非对称形式的对偶非对称形式的对偶 若原问题的约束条件是等式，则若原问题的约束条件是等式，则原问题原问题对偶问题对偶问题返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题推导推导:原问题原问题返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题 根据对称形式的对偶模型根据对称形式的对偶模型,可直接可直接写出上述问题的对偶问题写出上述问题的对偶问题:返回返回返回返回上页上页上页上页下页

7、下页下页下页对对对对偶偶偶偶问问问问题题题题令令 ，得对偶问题为：，得对偶问题为：证毕。证毕。返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题三、原问题与对偶问题的对应关系三、原问题与对偶问题的对应关系 原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题n例例:返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题对偶问题为对偶问题为返回返回返回返回线性规划的对偶问题线性规划的对偶问题线性规划的对偶问题线性规划的对偶问题返回返回

8、返回返回继续继续继续继续3.1.2 3.1.2 对偶问题的基本性质对偶问题的基本性质n引例引例n对称性对称性n弱对偶性弱对偶性n最优性最优性n对偶性（强对偶性）对偶性（强对偶性）n互补松弛性互补松弛性返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题对对偶偶问问题题原原问问题题收收购购厂厂家家n引例引例返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题（）原问题原问题的变量的变量原问题松弛变量原问题松弛变量对偶问题对偶问题剩余变量剩余变量对偶问题的变量对偶问题的变量化为极小问题原问题化为极小问题，最终单纯形表：原问题化为极小问题，最终

9、单纯形表：返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题原问题的变量原问题的变量原问题松弛变量原问题松弛变量对偶问题剩余变量对偶问题剩余变量对偶问题的变量对偶问题的变量对偶问题用两阶段法求解的最终的单纯形表对偶问题用两阶段法求解的最终的单纯形表返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题（）原问题原问题的变量的变量原问题松弛变量原问题松弛变量对偶问题对偶问题剩余变量剩余变量对偶问题的变量对偶问题的变量化为极小问题化为极小问题原问题原问题最优解最优解对偶问题对偶问题最优解最优解原问题化为极小问题，最终单纯形表：原问题化为极小问

10、题，最终单纯形表：返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题n两个问题作一比较两个问题作一比较:1.两者的最优值相同两者的最优值相同2.变量的解在两个单纯形表中互相包含变量的解在两个单纯形表中互相包含原问题最优解原问题最优解（决策变量）（决策变量）对偶问题最优解对偶问题最优解（决策变量）（决策变量）对偶问题的松弛变量对偶问题的松弛变量原问题的松弛变量原问题的松弛变量返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题从引例中可见：从引例中可见：原问题与对偶问题在某种意义上来说，原问题与对偶问题在某种意义上来说，实质上是一样的，因

11、为第二个问题仅仅在第实质上是一样的，因为第二个问题仅仅在第一个问题的另一种表达而已。一个问题的另一种表达而已。理论证明：理论证明：原问题与对偶问题解的关系原问题与对偶问题解的关系返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题对偶问题的基本性质对偶问题的基本性质一、对称定理：一、对称定理：定理：定理：对偶问题的对偶是原问题对偶问题的对偶是原问题。设原问题（设原问题（1 1）对偶问题（对偶问题（2 2）返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题二、弱对偶性定理：二、弱对偶性定理：若若 和和 分别是原问题（分别是原问题（1 1）

12、及对偶问题（及对偶问题（2 2）的可行解，则有）的可行解，则有 证明：证明：对偶问题的基本性质对偶问题的基本性质返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题n（1 1）极大化问题（原问题）的任一可行解所）极大化问题（原问题）的任一可行解所对应的目标函数值是对偶问题最优目标函数值对应的目标函数值是对偶问题最优目标函数值的下界。的下界。n（2 2）极小化问题（对偶问题）的任一可行解）极小化问题（对偶问题）的任一可行解所对应的目标函数值是原问题最优目标函数值所对应的目标函数值是原问题最优目标函数值的上界。的上界。n（3 3）若原问题可行，但其目标函数值无界，）若原

13、问题可行，但其目标函数值无界，则对偶问题无可行解。则对偶问题无可行解。返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题n（4 4）若对偶问题可行，但其目标函数值无界，）若对偶问题可行，但其目标函数值无界，则原问题无可行解。则原问题无可行解。n（5 5）若原问题有可行解而其对偶问题无可行）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界。解，则原问题目标函数值无界。n（6 6）对偶问题有可行解而其原问题无可行解，）对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。则对偶问题的目标函数值无界。原问题原问题对偶问题对偶问题返回返回返回返回上页

14、上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题三、最优性定理：三、最优性定理：若若 和和 分别是（分别是（1 1）和（）和（2 2）的）的 可行解，且有可行解，且有 则则 分别是分别是（1 1）和（）和（2 2）的最优解）的最优解 。则则 为（为（1 1）的最优解，）的最优解，反过来可知：反过来可知：也是（也是（2 2）的最优解。）的最优解。证明：因为（证明：因为（1）的任一可行解）的任一可行解 均满足均满足对偶问题的基本性质对偶问题的基本性质返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题证明：证明：原问题与对偶问题的解一般有三种情况原问题与对偶

15、问题的解一般有三种情况：n一个有有限最优解一个有有限最优解 另一个有有限最优解。另一个有有限最优解。n一个有无界解一个有无界解 另一个无可行解。另一个无可行解。n两个均无可行解。两个均无可行解。四、对偶定理（强对偶性）：四、对偶定理（强对偶性）：若原问题及其对偶问题均具有可行解，若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函则两者均具有最优解，且它们最优解的目标函数值相等数值相等。对偶问题的基本性质对偶问题的基本性质返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题五、互补松弛性：五、互补松弛性：若若 分别是原问题（分别是原问题（1 1

16、）与对偶）与对偶问题（问题（2 2）的可行解，）的可行解，分别为（分别为（1 1）、）、（2 2）的松弛变量，则：）的松弛变量，则：即：即：为最优解为最优解原问题第原问题第i条约束条约束 A的第的第i行行返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题 说明：说明：在线性规划问题的最优解中，如果对在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该应某一约束条件的对偶变量值为非零，则该约束条件去严格等式；反之如果约束条件取约束条件去严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。严格不等式，则其对应的对偶变量一定为零。另一方

17、面：另一方面：对偶问题的第对偶问题的第j条约束条约束返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题n n互补松弛定理应用：互补松弛定理应用：n（1）从已知的最优对偶解，求原问题最）从已知的最优对偶解，求原问题最优解，反之亦然。优解，反之亦然。n（2）证实原问题可行解是否为最优解。）证实原问题可行解是否为最优解。n（3）从不同假设来进行试算，从而研究）从不同假设来进行试算，从而研究原始、对偶问题最优解的一般性质。原始、对偶问题最优解的一般性质。n（4）非线性的方面的应用。）非线性的方面的应用。以上性质同样适用于非对称形式。以上性质同样适用于非对称形式。返回返回返

18、回返回对偶问题的基本性质对偶问题的基本性质返回返回返回返回继续继续继续继续3.1.3 3.1.3 影子价格影子价格在单纯形法的每步迭代中，目标函数取值 ，和检验数 中都有乘子 ，那么Y的经济意义是什么？返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题n 当线性规划原问题求得最优解时，其对偶问题也得到最优解 ，且代入各自的目标函数后有：是线性规划原问题约束条件的右端项，它代表第 种资源的拥有量；（3）返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题 对偶变量 的意义代表在资源最优利用条件下对单位第 种资源的估价，这种估价不是资源的市

19、场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格（shadow price)。影子价格的定义影子价格的定义返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题n1资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。由于企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。影子价格的经济意义影子价格的经济意义市场价格影子价格市场企业返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题影子价格的经济意义影子价格的经济意义n2影子价格是一种边际价格。在（3）式中，。说明 的值

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

21、变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题n4在对偶问题的互补松弛性质中有 这表明生产过程中如果某种资源 未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题n5从影子价格的含义上考察单纯形表的 检验数的经济意义。（4）第j种产品的产值生产第j中产品所消耗各项资源的影子价格的总和。（即隐含成本）可见，产品产值可见，产品产值隐含成本隐含成本 可生产该产品；可生产该产品；

22、否则，不安排生产。否则，不安排生产。检验数的经济意义检验数的经济意义返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题影子价格的经济意义影子价格的经济意义n6一般说对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及到资源的最有效利用。经济学研究如何管理自己的稀缺资源返回返回返回返回影子价格影子价格3.1.4 3.1.4 对偶单纯形法对偶单纯形法n 对偶单纯形法的基本思路对偶单纯形法的基本思路n 对偶单纯形法的计算步骤对偶单纯形法的计算步骤返回返回返回返回继续继续继续继续返回返回返回返回上页上页上页上页下页下

23、页下页下页对对对对偶偶偶偶问问问问题题题题对偶单纯形法的基本思路对偶单纯形法的基本思路对偶单纯形法的基本思路对偶单纯形法的基本思路单纯形法的基本思路：单纯形法的基本思路：原问题基可行解原问题基可行解 最优解判断最优解判断对偶问题的可行解对偶问题的可行解对偶问题对偶问题最优解判断最优解判断对偶单纯形法对偶单纯形法对偶单纯形法对偶单纯形法基本思路基本思路基本思路基本思路返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题对偶单纯形法的计算步骤对偶单纯形法的计算步骤n线性规划问题 不妨设 为对偶问题的初始可行基，则 。若 ，即表中原问题和对偶问题均为最优解，否则换基。返回

24、返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题确定换出基变量 对应变量 为换出基的变量确定换入基变量 为主元素，为换入基变量返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题初始可行基例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：对偶问题的初始可行基返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：例、

25、用对偶单纯形法求解线性规划问题：使对偶问题基变量可行,换出 换出换出换出返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题最优解最优解例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问

26、问问题题题题n n对偶单纯形法的优点：对偶单纯形法的优点：n不需要人工变量；不需要人工变量；n当变量多于约束时，用对偶单纯形法可减少当变量多于约束时，用对偶单纯形法可减少迭代次数；迭代次数；n在灵敏度分析中，有时需要用对偶单纯形法在灵敏度分析中，有时需要用对偶单纯形法处理简化。处理简化。n n对偶单纯形法缺点：对偶单纯形法缺点：n在初始单纯形表中对偶问题是基可行解，这在初始单纯形表中对偶问题是基可行解，这点对多数线性规划问题很难做到。点对多数线性规划问题很难做到。因此，对偶单纯形法一般不单独使用。因此，对偶单纯形法一般不单独使用。返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶

27、问问问问题题题题练习n用对偶单纯形法求解线性规划问题：用对偶单纯形法求解线性规划问题：返回返回返回返回 对偶单纯形法对偶单纯形法3.2.1 灵敏度问题及其图解法灵敏度问题及其图解法灵敏度问题灵敏度问题灵敏度分析灵敏度分析图解法图解法返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题 灵敏度问题n背景：线性规划问题中，都是常数，但这些系数是估计值和预测值。市场的变化 值变化；工艺的变化 值变化；资源的变化 值变化。返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题n问题：n当这些系数中的一个或多个发生变化时，原最优解会怎样变化？n当这些

28、系数在什么范围内变化时，原最优解仍保持不变？n若最优解发生变化，如何用最简单的方法找到现行的最优解？返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题n研究内容：研究线性规划中，的变化对最优解的影响。l研究方法研究方法：图解法图解法对偶理论分析对偶理论分析仅适用于含仅适用于含2个变量个变量的线性规划问题的线性规划问题在单纯形表中在单纯形表中进行分析进行分析返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题 Max Z=34 x1+40 x24 x1+6 x2 48 2 x1+2 x2 182 x1+x2 16x1、x2 0 0线性规划

29、模型线性规划模型灵敏度分析图解法 返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题x218 16 14 12 10 8 6 4 2 0|24681012141618x14x1+6x2 482x1+2x2 182x1+x2 16ABCDE(8,0)(0,6.8)最优解最优解(3,6)4x1+6x2=48 2x1+2x2=18灵敏度分析图解法 返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题灵敏度分析图解法 18 16 14 12 10 8 6 4 2 0|24681012141618x14x1+6x2 482x1+2x2 182x1

30、+x2 16ABCDE目标函数的系数目标函数的系数34x1+40 x2=Z40 x2=-34x1+Zx2=-+34x1Z4040返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题灵敏度分析图解法 18 16 14 12 10 8 6 4 2 0|24681012141618x14x1+6x2 482x1+2x2 182x1+x2 16ABCDE目标函数的系数目标函数的系数34x1+40 x2=Z40 x2=-34x1+Zx2=-+c1x1Zc2c2若若若若 c c1 1增加增加增加增加（c c2 2 不变）不变）不变）不变）新的最优解新的最优解新的最优解新的最优解

31、返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题灵敏度分析图解法 18 16 14 12 10 8 6 4 2 0|24681012141618x14x1+6x2 482x1+2x2 182x1+x2 16ABCDE目标函数的系数目标函数的系数34x1+40 x2=Z40 x2=-34x1+Zx2=-+c1x1Zc2c2若若若若 c c1 1减少减少减少减少新的最优解新的最优解新的最优解新的最优解返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题18 16 14 12 10 8 6 4 2 0|24681012141618x14x1

32、+6x2 482x1+2x2 182x1+x2 16ABCDE(斜率斜率=-1)=-1)(斜率斜率=-2/3)=-2/3)灵敏度分析图解法 最优解不变的范围最优解不变的范围（设（设c1固定固定c2可变）可变）返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题3.2.1 灵敏度问题及其图解法灵敏度问题及其图解法 3.2.2 灵敏度分析 一、分析一、分析 的变化的变化 二、分析二、分析 的变化的变化 三、增加一个变量三、增加一个变量 的分析的分析 四、增加一个约束条件的分析四、增加一个约束条件的分析 五、分析五、分析 的变化的变化返回返回返回返回上页上页上页上页下页下

33、页下页下页对对对对偶偶偶偶问问问问题题题题n研究内容：研究线性规划中，的变化对最优解的影响。l常用公式：常用公式：返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题实例：某家电厂家利用现有资源生产两种产品，有某家电厂家利用现有资源生产两种产品，有关数据如下表：关数据如下表：设备设备A 设备设备B调试工序调试工序利润（元）利润（元）0612521115时时24时时 5时时D返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题如何安排生产，如何安排生产，使获利最多？使获利最多？厂厂家家设设 产量产量 产量产量返回返回返回返回上页上页上页上页

34、下页下页下页下页对对对对偶偶偶偶问问问问题题题题原问题最优解对偶问题最优解（相差负号）返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题一、分析 的变化n 的变化仅影响 的变化。设备设备A 设备设备B调试工序调试工序利润（元）利润（元）0612521115时时24时时 5时时D1.52问题1：当 该公司最优生 产计划有何变化？返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题最终单纯形表05/41.5 1/4+2（-1/4）-1/80-（-1/8）=返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题最终单

35、纯形表返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题换基后单纯形表为最优解返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题 问题2：设产品II利润为 ，求原最优解不变时 的范围。的变化仅影响的变化仅影响 的变化；的变化；在最后一张单纯形表中求出变化的在最后一张单纯形表中求出变化的 ；原最优解不变，即原最优解不变，即 ；由上述不等式可求出由上述不等式可求出 的范围。的范围。方法：方法：返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题即即产品产品II利润为利润为 时的最终单纯形时的最终单纯形表表返回返

36、回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题二、分析 的变化 的变化仅影响 ，即原最优解的可行性可能会变化：可行性不变，则原最优解不变。可行性不变，则原最优解不变。可行性改变，则原最优解改变，可行性改变，则原最优解改变，用对偶单纯形法，找出最优解。用对偶单纯形法，找出最优解。返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题问题3：设备B的能力增加到32小时，原最优计划有何变化？返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题代入单纯形表中代入单纯形表中可行性改变，用对偶可行性改变，用对偶单纯形法换基求

37、解。单纯形法换基求解。主元主元返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题新的最优解新的最优解换基迭代得：换基迭代得：返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题问题4：设调试工序可用时间为 小时，求 ，原最优解保持不变。原最优解保持不变，则原最优解保持不变，则返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题三、增加一个变量 的分析 增加一个变量相当于增加一种产品。分析步骤：1、计算2、计算3、若 ，原最优解不变；若 ，则按单纯形表继续迭代 计算找出最优解。返回返回返回返回上页上页上页上页下

38、页下页下页下页对对对对偶偶偶偶问问问问题题题题问题5：设生产第三种产品，产量为 件，对应的 求最优生产计划。解：解：返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题代入最终原单纯形表中主元主元返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题换基后有：返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题四、增加一个约束条件的分析 增加一个约束条件相当于增添一道工序。分析方法：分析方法：将最优解代入新的约束中将最优解代入新的约束中（1）若满足要求，则原最优解不变；）若满足要求，则原最优解不变；（2）若不满足

39、要求，则原最优解改变，）若不满足要求，则原最优解改变，将新增的约束条件添入最终的将新增的约束条件添入最终的单纯形表中继续分析。单纯形表中继续分析。返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题五、分析 的变化若若 对应的对应的 变量变量 为基变量，为基变量，B将改变。需引入人工变量求出将改变。需引入人工变量求出可行解，再用单纯形法求解。可行解，再用单纯形法求解。若 对应的变量 为非基变量，参见三的分析。返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题灵敏度分析的步骤归纳如下：（1）将参数的改变计算反映到最终 单纯形表上；（2）检

40、查原问题是否仍为可行解；（3）检查对偶问题是否仍为可行解；（4）按下表所列情况得出结论和决 定继续计算的步骤。返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题原问题原问题 对偶问题对偶问题 结论或继续计算的步骤结论或继续计算的步骤可行解可行解 可行解可行解 问题的最优解或最优基不变问题的最优解或最优基不变可行解可行解 非可行解非可行解 用单纯形法继续迭代用单纯形法继续迭代非可行解非可行解 可行解可行解 用对偶单纯形法继续迭代用对偶单纯形法继续迭代非可行解非可行解 非可行解非可行解 编制新的单纯形表重新计算编制新的单纯形表重新计算总之返回返回返回返回上页上页上页上

41、页下页下页下页下页对对对对偶偶偶偶问问问问题题题题练习：某厂计划生产甲、乙、丙三种产品，这三种产品单位利润及生产产品所需材料、劳动力如下表：单位产品单位产品 甲甲 乙乙 丙丙 可使用资源量可使用资源量 劳动力劳动力 1/3 1/3 1/3 1 材料材料 1/3 4/3 7/3 3利润（元）利润（元）2 3 1 返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题（1）确定最优的生产方案；（2）当 增大至多少时，丙产品安排生产；（3）增加3个劳动力，最优解是否改变？（4）劳动力在哪个范围内变化，对利润值 的改变有利；（5）增加新的产品丁，需1个劳动力，1个 单位原料，

42、利润3元。确定最优的生产方案。（6）添加新约束：最优解是否改变？返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题解：初始及最终单纯形表为返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题3 3.2.2 .2.2 灵敏度分析灵敏度分析 3.2.3 参数线性规划目标函数的系数含有参数 的线性规划问题约束条件右端的常数项含有约束条件右端的常数项含有参数的线性规划问题参数的线性规划问题返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题参数线性规划概念 当参数当参数 或或 沿某一方沿某一方向连续变动时，目标函数值

43、向连续变动时，目标函数值z将随将随 或或 的变动而呈线性变动，的变动而呈线性变动，z是这个是这个变动参数的线性函数，因而称为参变动参数的线性函数，因而称为参数线性规划。数线性规划。返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题模型目标函数的系数含有参数的线性规划模型约束条件右端的常数项含有参数的约束条件右端的常数项含有参数的LP模型模型：价值向量：变动向量：参数 ：资源向量 ：变动向量 ：参数 返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题参数线性规划问题的分析步骤：（1）令 求解得最终单纯形表；（2）将 或 项反映到最终单纯

44、形表中去；（3）随 值的增大或减小，观察原问题或对偶 问题。（4）重复第（3）步，一直到 值继续增大或减小 时，表中的解（基）不再出现变化时为止。确定现有解（基）允许的确定现有解（基）允许的 的变动范围；的变动范围；当当 的变动超出这个范围时，用单纯的变动超出这个范围时，用单纯形法或对偶单纯形法求新的解。形法或对偶单纯形法求新的解。返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题举例分析目标函数的系数目标函数的系数 含有参数的线性规划问题含有参数的线性规划问题 分析分析 值变化时，下述参数线性规划值变化时，下述参数线性规划问题最优解的变化。问题最优解的变化。返回

45、返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题 先令先令 求得最优求得最优 解，然后解，然后将将 反映在最终单纯形表中，见下表：反映在最终单纯形表中，见下表：最优解保持不变的条件返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题当当 时时检验数检验数非负非负返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题当当 时，换基得：时，换基得：返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题当 时，由原最终单纯形表检验数检验数非负非负返回返回返回返回上页上页上页上页下页下页下页下页

46、对对对对偶偶偶偶问问问问题题题题当 时，最终单纯形表返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题当 时，原最终单纯形表检验数检验数非负非负返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题当 时，最终单纯形表返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题目标函数值 随 值变化的情况-2-1/5-1127.21523返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题举例分析约束条件右端的常数项含约束条件右端的常数项含 有参数的线性规划问题有参数的线性规划问题 分析分析

47、 值变化时，下述参数线性规划值变化时，下述参数线性规划问题最优解的变化。问题最优解的变化。返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题 先令先令 求得最优求得最优 解，然后解，然后将将 反映在最终单纯形表中，见下表：反映在最终单纯形表中，见下表：最优基不变条件是 最优值为 返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题当 时返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题 先令先令 求得最优求得最优 解，然后解，然后将将 反映在最终单纯形表中，见下表：反映在最终单纯形表中，见下表：最优基不变条件是 最优值为 返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题当当 时时 当 时最优值为 返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题当当 时时 当 时最优值 当 时，所在元素均为正，故原问题无可行解 返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题第三节第三节 参数线性规划参数线性规划