第三讲+线性规划的对偶问题.pptx

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 对偶线性规划的求法 　　从任何一个线性规划出发，都可以求出相应的对偶规划，在实际求解过程中，通常不通过求标准型，而是利用如下反映原始问题与对偶问题对应关系的原始─对偶表： 目标函数变量系数 约束条件右端项 约束条件右端项 目标函数变量系数 约束条件个数：n个 变量个数：n个 变量个数：m个 约束条件个数：m个 目标函数minW 目标函数maxZ 对偶问题（或原问题） 原问题（或对偶问题） 16 解：对偶规划： 例2 写出下列线性规划的对偶问题 17 例3 写出下列线性规划的对偶问题 解：上述问题的对偶规划： 18 　　本节讨论几条重要的对偶定理，这些定理揭示了原始问题的解和对偶问题的解之间的基本关系。 定理1：（对称性）对偶问题的对偶是原问题。 证明：设原问题为　　　　　　　　对偶问题为 　　改写对偶问题为　　　对偶问题的对偶为 第二节 对偶定理 19 定理2：弱对偶定理 若　　是原（极小化）问题的可行解，　　是对偶（极大化）问题的可行解，那么 　注：原（极小化）问题的最优目标函数值以对偶问题任一可行解的目标函数值为下界。 　 对偶（极大化）问题的最优目标函数值以原问题任一可行解的目标函数值为上界。 　推论1：如果原问题没有下界（即minZ→－∞），则对偶问题不可行。 如果对偶问题没有上界（即maxW→＋∞），则原问题不可行。 若原问题与对偶问题之一无界，则另一个无可行解。 20 证明：由弱对偶定理，对于原始问题的所有可行解　　，都有　　　　　　　 因此　是原问题的最优解。 　同理，对于对偶问题的所有可行解 ，都有 所以 是对偶问题的最优解。 21 证明：设　　是原问题(min)的最优解，则对应的基Ｂ必有 　　　　　　　　　。