chapter3对偶理论dualtheory

chapter3对偶理论dualtheory内容摘要：

,03354751086m in321321321iyyyyyyyyyywi 线性规划的对偶模型 Dual model of LP Chapter3 对偶理论 Dual Theory 线性规划问题的 规范形式 (Canonical Form 或叫 对称形式 ) ： 定义： 目标函数求 极大值 时，所有约束条件 为 ≤号 ， 变量非负 ； 目标函数求 极小值 时，所有约束条件 为 ≥号，变量非负。 线性规划的对偶模型 Dual model of LP 0)(m a xXbAXCXZ0)(m i nXbAXCXZ注： (1)线性规划规范形式与标准型是两种不同形式，但可以 相互转换。 (2)规范形式的线性规划问题的对偶仍然是规范形式． Chapter3 对偶理论 Dual Theory 原问题 (或对偶问题 ) 对偶问题 (或原问题 ) 目标函数 max 目标函数系数 (资源限量 ) 约束条件系数矩阵 A(AT) 目标函数 min 资源限量 (目标函数系数 ) 约束条件系数矩阵 AT(A) 变 量 n个变量 第 j个变量 ≥0 第 j 个变量 ≤0 第 j个变量无约束 约 束 n个约束 第 j个约束为 ≥ 第 j个约束为 ≤ 第 j个约束为 = 约 束 m个约束 第 i个约束 ≤ 第 i个约束 ≥ 第 i个约束为 = 变 量 m个变量 第 i个变量 ≥0 第 i个变量 ≤0 第 i个变量无约束 线性规划的对偶模型 Dual model of LP 问题 ：讨论一般形式的线性规划问题的对偶问题。 方法： 先将其转化为规范形式的线性规划问题，然后写出其对偶问题，适当将其进行化简。 (具体过程见书本 P40) 对偶性质 Dual property Chapter3 对偶理论 Dual Theory 0m a xXbAXCXZ对偶问题是 (记为 DP)： 0m inYCYAYbw这里 A是 m n矩阵 , X是 n 1列向量 , Y是 1 m行向量。 【 性质 1】 对称性 : 对偶问题的对偶是原问题。 设原问题是 (记为 LP)： 对偶性质 Dual property 对偶性质 【 性质 2】 弱对偶性 : 设 X*、 Y*分别为 LP(max)与 DP(min)的可行解，则 bYCX ** Chapter3 对偶理论 Dual Theory 对偶性质 Dual property 由这个性质可得到下面几个 结论 ： (1) (LP) 的任一可行解的目标值是 (DP) 的最优值下 界； (DP)的任一可行解的目标是 (LP)的最优值的上界； (2) 在互为对偶的两个问题中 ， 若一个问题可行且具有无界解 ， 则另一个问题无可行解； (3) 若原问题可行且另一个问题不可行，则原问题具 有无界解。 注意 : 上述结论 (2)及 (3)的条件不能少。 一个问题无可行解时 ， 另一个问题可能有可行解 (此时具有无界解 )也可能无可行解。 **( ( m a x ) ) ( ( m i n ) )L P D PC X Y bChapter3 对偶理论 Dual Theory 例如： 0,22212m in21212121xxxxxxxxz无可行解 ， 而对偶问题 0,221122m a x21212121yyyyyyyyw有可行解 ， 由结论 (3)知必有无界解。 对偶性质 Dual property Chapter3 对偶理论 Dual Theory 【 性质 3】 最优准则定理 : 设 X*与 Y*分别是 (LP)与 (DP)的可行解 ， 则 X*、 Y*是 (LP)与 (DP)的最优解当且仅当 C X*= Y*b . 对偶性质 Dual property 【 性质 4】 对偶性： 若互为对偶的两个问题其中一个有最优解 ， 则另一个也有最优解 ， 且最优值相同。 另一结论 ：若 (LP)与 (DP)都有可行解 ， 则两者都有最优解 ， 若一个问题无最优解 ， 则另一问题也无最优解。 【 性质 5】 互补松弛定理 : 设 X*、 Y*分别为。