§2-原问题与对偶问题.pptVIP

§2 原问题与对偶问题 从弱对偶性可得到以下重要结论： * 1．对称形式的对偶 当原问题对偶问题只含有不等式约束时，称为对称形式的对偶。 原问题 对偶问题 情形一： 原问题 对偶问题 情形二： 证明 对偶 化为标准对称型 2、 非对称形式的对偶 若原问题的约束条件是等式，则 原问题 对偶问题 推导: 原问题 根据对称形式的对偶模型,可直接写出上述问题的对偶问题: 令 ，得对偶问题为： 证毕。 对偶问题(原问题) 原问题(对偶问题) 目标函数max 目标函数min 目标函数中变量的系数 约束条件右端项 约束条件右端项 目标函数中变量的系数 例: 对偶问题为 例: § 3 对偶问题的基本性质 弱对偶性； 强对偶性； 最优性; 无界性; 互补松弛性 掌握原问题和其对偶问题解之间的关系 对偶问题的对偶是原问题。 对 偶 问 题 原 问 题 租借 方 厂 家 引例 （ ） 原问题 的变量 原问题松弛变量 对偶问题 剩余变量 对偶问题的变量 化为极小问题 原问题化为极小问题，最终单纯形表： （ ） 原问题 的变量 原问题松弛变量 对偶问题 剩余变量 对偶问题的变量 化为极小问题 原问题化为极小问题，最终单纯形表： 原问题的变量 原问题松弛变量 对偶问题剩余变量 对偶问题的变量 对偶问题用两阶段法求解的最终的单纯形表 （ ） 原问题 的变量 原问题松弛变量 对偶问题 剩余变量 对偶问题的变量 化为极小问题 原问题 最优解 对偶问题 最优解 原问题化为极小问题，最终单纯形表： 两个问题作一比较: 1.两者的最优值相同 2.变量的解在两个单纯形表中互相包含 原问题最优解（决策变量） 对偶问题最优解（决策变量） 对偶问题的松弛变量 原问题的松弛变量 从引例中可见： 原问题与对偶问题在某种意义上来说，实质上是一样的，因为第二个问题仅仅在第一个问题的另一种表达而已。 理论证明： 原问题与对偶问题解的关系 在下面的讨论中, 假定线性规划原问题和对偶问题分别如下 原问题 对偶问题 1. 弱对偶性 是其对偶问题的可行解，则恒有 若 是原问题的可行解， 证明： （1）极大化问题（原问题）的任一可行解所对应的目标函数值是对偶问题最优目标函数值的下界。 （2）极小化问题（对偶问题）的任一可行解所对应的目标函数值是原问题最优目标函数值的上界。 （3）若原问题可行，但其目标函数值无界，则对偶问题无可行解。 （4）若对偶问题可行，但其目标函数值无界，则原问题无可行解。 （5）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界。 （6）对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。 原问题 对偶问题 2.最优性 若 是原问题的可行解， 提示 ,则 是原问题的最优解， 是其对偶问题的最优解。 设 是原问题的最优解， 是其对偶问题的最优解。 是其对偶问题的可行解,且有 3.无界性 若原问题(对偶问题)具有无界解, 则其对偶问题(原问题)无可行解. 说明 逆命题不成立。 即原问题(对偶问题)无可行解，则其对偶问题(原问题)或无可行解或具有无界解, 反证法结合弱对偶性 4. 强对偶性(对偶定理) 若原问题有最优解, 则其对偶问题也一定有最优解, 且有 证明： 将原问题化成标准形式 用单纯形法求得最优解，则有 即 即 故 是对偶问题的可行解, 又因 由性质2即可证得。