[第二章 线性规划的对偶理论.ppt

最优化方法 Optimizing Methods §1 对偶问题的提出 一、对偶问题的实例 第二章 线性规划的对偶理论 §1 对偶问题的提出 2、非对称型对偶问题 第二章 线性规划的对偶理论 3、混合型对偶问题 §1 对偶问题的提出 原问题与对偶问题的关系 §2 对偶问题的基本性质 讨论对称形式： §2 对偶问题的基本性质 Theorem 1 (对称性定理) §2 对偶问题的基本性质 Theorem 2 (弱对偶定理) 第二章 线性规划的对偶理论 §2 对偶问题的基本性质 Theorem 3 (对偶定理) §2 对偶问题的基本性质 即 §2 对偶问题的基本性质 Corollary 5 对于对称形式（P）问题，如果有最优解， 则在其最优单纯形表中，松弛变量x n+1 , x n+2 ,…, x n+m 的检验数（ ）的 负值即为（D）问题的 一个最优解。 第二章 线性规划的对偶理论 §2 对偶问题的基本性质 Theorem 4 (互补松弛定理) §2 对偶问题的基本性质 第二章 线性规划的对偶理论 §2 对偶问题的基本性质 如果 （P）问题为： 第二章 线性规划的对偶理论 2、利用互补松弛定理求对偶最优解 §2 对偶问题的基本性质 可用图解法求解（P）问题，得：x*=(4/5，3/5)T z*=5 第二章 线性规划的对偶理论 §3 对偶问题的经济解释——影子价格 一、影子价格的概念 第二章 线性规划的对偶理论 §3 对偶问题的经济解释——影子价格 第二章 线性规划的对偶理论 3、影子价格在新产品开发决策中的应用 §3 对偶问题的经济解释——影子价格 5、利用影子价格分析工艺改变后对资源影响 §4 对偶单纯形法 一、对偶单纯形法的基本思路 第二章 线性规划的对偶理论 原始单纯形法的基本思路是： §4 对偶单纯形法 对偶单纯形法的基本思路是： 第二章 线性规划的对偶理论 对偶单纯形法的计算步骤： §4 对偶单纯形法 第二章 线性规划的对偶理论 e.g. 5 用对偶单纯形法求解 §4 对偶单纯形法 对偶单纯形法与原始单纯形法内在的对应关系 §5 灵敏度分析 一、目标函数中价值系数cj 的变化分析 第二章 线性规划的对偶理论 1、若cj 是非基变量的系数 §5 灵敏度分析 2、若cr 是基变量xr 的系数 第二章 线性规划的对偶理论 e.g. 6 §5 灵敏度分析 解： 第二章 线性规划的对偶理论 §5 灵敏度分析 这时 第二章 线性规划的对偶理论 e.g. 7 在上述佳美公司的例子中：（1）若设备 A 和 调试工序的每天能力不变，而设备 B 每天的能力增加 到32小时，分析公司最优计划的变化；（2）若设备A 和 B 每天可用能力不变，则调试工序能力在什么范围 内变化时，问题的最优基不变。 §5 灵敏度分析 第二章 线性规划的对偶理论 三、增加一个变量 xj 的分析 §5 灵敏度分析 e.g. 8 在佳美公司例子中，设该公司又计划推出新产品 Ⅲ，生产一单位产品Ⅲ，所需设备A、B、C调试工序的 时间分别为3小时、4小时、2小时，该产品的预期盈利 为3百元/单位，试分析该新产品是否值得投产；如投产 对该公司的最优生产计划有何变化。 第二章 线性规划的对偶理论 四、约束条件中技术系数 aij 的变化分析 §5 灵敏度分析 2、基变量 xj 的系数列向量 pj 的变化分析 第二章 线性规划的对偶理论 将其加入原最终单纯形表: §5 灵敏度分析 五、增加新约束条件的分析 第二章 线性规划的对偶理论 e.g. 10 仍以佳美公司为例，设产品Ⅰ、Ⅱ经调试后， 还需经过一道环境试验工序，产品Ⅰ每单位须环境试 验3小时，产品Ⅱ每单位须2小时，又环境试验工序每 天生产能力为12小时，试分析增加该工序后的佳美公 司最优生产计划。 Step 2 若 b’=B-1b ≥0 ，则停止计算，当前的正则解 x =B-1b 即为原问题的最优解，否则转入下一步； Step 3 确定换出基变量： 则取 xr 为换出基变量； Step 4 若 则停止计算，原问题无 可行解，否则转入下一步； Step 5 确定换入基变量：若 则取 xk为换入基变量 转 Step 2 Step 6 以 为主元进行换基运算，得新的正则解 令 Evaluation only. Cre