爱家的 对偶的性质 设原问题(1)对偶问题(2) maxz=CX minw=yb st.AX<bst.YA≥C X≥0 Y≥0 上页 下一、对称定理: 定理:对偶问题的对偶是原问题。 回
返回 上页 下页 对 偶 问 题 对偶问题的基本性质 一、对称定理： 定理： 对偶问题的对偶是原问题。 设原问题（1） 对偶问题（2） 0 . . max = X st AX b z CX 0 . . min = Y st YA C w Yb
12学测学 1二、弱对偶性定理: 若萩分别是原问题(1)及 对偶问题(2)的可行解,则有 上页 CX<Yb 证明:Ax≤b→YAx≤Yb YA≥C→YA4X≥CX 回 CX<YAX<Yb
返回 上页 下页 对 偶 问 题 二、弱对偶性定理： ——若 和 分别是原问题（1）及 对偶问题（2）的可行解，则有 CX YAX Yb YA C YAX CX AX b YAX Yb 证明： X Y CX Yb 对偶问题的基本性质
从弱对偶性可得到以下重要结论 周(1)极大化间题(原间题)的任一可行解所 对应的目标函数值是对偶问题最优目标函数值 的下界。 (2)极小化问题(对偶问题)的任一可行解 上页 所对应的目标函数值是原问题最优目标函数值 下页 的上界。 (3)若原问题可行,但其目标函数值无界, 回 则对偶问题无可行解
返回 上页 下页 对 偶 问 题 从弱对偶性可得到以下重要结论： ◼ （1）极大化问题（原问题）的任一可行解所 对应的目标函数值是对偶问题最优目标函数值 的下界。 ◼ （2）极小化问题（对偶问题）的任一可行解 所对应的目标函数值是原问题最优目标函数值 的上界。 ◼ （3）若原问题可行，但其目标函数值无界， 则对偶问题无可行解
(4)若对偶问题可行,但其目标函数值无界, 则原问题无可行解。 (5)若原问题有可行解而其对偶问题无可行 解,则原问题目标函数值无界。 (6)对偶问题有可行解而其原问题无可行解, 则对偶问题的目标函数值无界。 上页 Cx≤b 下页 回 原问题 对偶问题 CX=yb 通观图
返回 上页 下页 对 偶 问 题 ◼ （4）若对偶问题可行，但其目标函数值无界， 则原问题无可行解。 ◼ （5）若原问题有可行解而其对偶问题无可行 解，则原问题目标函数值无界。 ◼ （6）对偶问题有可行解而其原问题无可行解， 则对偶问题的目标函数值无界。 原问题 对偶问题 CX Yb CX Y b =
12学测学 最优性定理 若和分别是(1)和(2)的 可行解,且有CX-则b,分别是(1)和 (2)的最优解。 画证明:因为(1)的任可行解均满足 下页 CX<Yb ∴CX=Yb 回 则X为(1)的最优解 反过来可知:y也是(2)的最优解。 通观图
返回 上页 下页 对 偶 问 题 三、最优性定理： ——若 和 分别是（1）和（2）的 可行解，且有 则 分别是（1）和 （2）的最优解 。 X Y CX = Y b, X ,Y 则 为（1）的最优解， 反过来可知： 也是（2）的最优解。 X Y CX Y b CX Y b = , 证明：因为（1）的任一可行解 X 均满足 对偶问题的基本性质