[理学]第三章 线性规划的对偶问题.pptVIP

1 第三章 线性规划的对偶问题 对偶线性规划 对偶定理 对偶单纯形法 第一节 对偶问题 对偶问题概念： 　　任何一个线性规划问题都有一个与之相对应 的线性规划问题，如果前者称为原始问题，后者 就称为“对偶”问题。 　　对偶问题是对原问题从另一角度进行的描述 其最优解与原问题的最优解有着密切的联系，在 求得一个线性规划最优解的同时也就得到对偶线 性规划的最优解，反之亦然。 　　对偶理论就是研究线性规划及其对偶问题的 理论，是线性规划理论的重要内容之一。 3 对偶问题的提出 例1、某工厂生产甲,乙两种产品，这两种产品需要在A,B,C三种不同设备上加工。每种甲、乙产品在不同设备上加工所需的台时，它们销售后所能获得的利润，以及这三种设备在计划期内能提供的有限台时数均列于表。试问如何安排生产计划，即甲,乙两种产品各生产多少吨，可使该厂所获得利润达到最大。 对偶线性规划 设备 每吨产品的加工台时 可供台时数 甲 乙 A B C 3 5 9 4 4 8 36 40 76 利润（元/吨） 32 30 4 设备 每吨产品的加工台时 可供台时数 甲 乙 A B C 3 5 9 4 4 8 36 40 76 利润（元/吨） 32 30 5 现在从另一个角度来考虑该工厂的生产问题: 假设该厂的决策者打算不再自己生产甲,乙产品，而是把各种设备的有限台时数租让给其他工厂使用，这时工厂的决策者应该如何确定各种设备的租价。 6 设备 每吨产品的加工台时 可供台时数 甲 乙 A B C 3 5 9 4 4 8 36 40 76 利润（元/吨） 32 30 7 8 可以得到另一个线性规划：　 称之为原线性规划问题的对偶问题， 对偶线性规划 考虑如下具有不等式约束的线性规划问题 9 10 11 12 　　　　　　　　　　　　　　　　若令　　　　　线性规划标准型 　　　　　　　　　　　　　　　的对偶规划为： 　线性规划问题标准型的对偶问题 考虑一个标准形式的线性规划问题 由于任何一个等式约束都可以用两个不等式约束等价地表示，所以标准形线性规划问题可等价表示为： 它的对偶规划为： 对偶问题的特点 （1）目标函数在一个问题中是求最大值在另一问题中则为求最小值 （2）一个问题中目标函数的系数是另一个问题中约束条件的右端项 （3）一个问题中的约束条件个数等于另一个问题中的变量数 （4）原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵 其他形式问题的对偶 15 　　本节讨论几条重要的对偶定理，这些定理揭示了原始问题的解和对偶问题的解之间的基本关系。 定理1：（对称性）对偶问题的对偶是原问题。 证明：设原问题为　　　　　　　　对偶问题为 　　改写对偶问题为　　　对偶问题的对偶为 第二节 对偶定理 16 对偶线性规划的求法 　　从任何一个线性规划出发，都可以求出相应的对偶规划，在实际求解过程中，通常不通过求标准型，而是利用如下反映原始问题与对偶问题对应关系的原始─对偶表： 目标函数变量系数 约束条件右端项 约束条件右端项 目标函数变量系数 约束条件个数：n个 变量个数：n个 变量个数：m个 约束条件个数：m个 目标函数minW 目标函数maxZ 对偶问题（或原问题） 原问题（或对偶问题） 17 解：对偶规划： 例2 写出下列线性规划的对偶问题 18 例3 写出下列线性规划的对偶问题 解：上述问题的对偶规划： 19 定理2：弱对偶定理 若　　是原（极小化）问题的可行解，　　是对偶（极大化）问题的可行解，那么 　注：原（极小化）问题的最优目标函数值以对偶问题任一可行解的目标函数值为下界。 　 对偶（极大化）问题的最优目标函数值以原问题任一可行解的目标函数值为上界。 　推论1：如果原问题没有下界（即minZ→－∞），则对偶问题不可行。 如果对偶问题没有上界（即maxW→＋∞），则原问题不可行。 若原问题与对偶问题之一无界，则另一个无可行解。 20 证明：由弱对偶定理，对于原始问题的所有可行解　　，都有　　　　　　　 因此　是原问题的最优解。 　同理，对于对偶问题的所有可行解 ，都有 所以 是对偶问题的最优解。 21 证明：设　　是原问题(min)的最优解，则对应的基Ｂ必有 　　　　　　　　　。