第一节 线性规划的树偶问题 解：按照规则，可得上述原问题的对偶问题 如下（过程略。可以参考教材第53页上的表格直 接写出对偶问题 ) minw=2y+y2+4y3 2y1+3y2+y3≥1 3y1-y2+y3≤4 -5y1+6y2+y3=3 y1≥0，y2≤0，y3≤0 18
18 解：按照规则，可得上述原问题的对偶问题 如下（过程略。可以参考教材第53页上的表格直 接写出对偶问题）： − + + = − + + + = + + 0, 0, 0 5 6 3 3 4 2 3 1 min 2 4 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 y y y y y y y y y y y y W y y y 第一节 线性规划的对偶问题
第一节 线性规划的对偶问题 四、对偶问题的基本性质 1)弱对偶性。 如x(j1,2,n)是原问题（求最大）的 可行解，y:(i=1,2,m)是对偶问题（求最 小)的可行解，则原问题(2-3)的目标函数值小 于等于对偶问题(2-4)的目标函数值，即 ∑cx,≤∑b,y 19
19 四、 对偶问题的基本性质 1) 弱对偶性。 如xj(j=1，2，.，n)是原问题（求最大）的 可行解，yi（i=1，2，.，m）是对偶问题（求最 小）的可行解，则原问题（2-3）的目标函数值小 于等于对偶问题（2-4）的目标函数值，即 i m i j i n j j c x b y = = 1 1 第一节 线性规划的对偶问题
第一节 线性规划的对偶问题 证明：因为 2c,x≤22a,yx,=立2a,xy I= i=1 i=l i=1 j=1 1 77 n ∑by≥∑（∑a,x,y=∑∑a,y i=l i=1 i=1 i=1 i=1 所以 x,≤∑y 1- i-1 证毕 20
20 证明：因为 = = = = = = m i i n j j i j j n j m i j i j i n j j c x a y x a x y 1 1 1 1 1 ( ) = = = = = = m i i n j i i j j m i n j i j j m i i i b y a x y a x y 1 1 1 1 1 ( ) 所以 = = m i j i i n j j c x b y 1 1 证毕 第一节 线性规划的对偶问题
第一节 线性规划的对偶问题 由弱对偶性，可得出以下推论 (1)原问题任一可行解的目标函数值是其对 偶问题目标函数值的下界；反之对偶问题任一可 行解的目标函数值是其原问题目标函数值的上界。 (2)如原问题有可行解且目标函数值无界（具 有无界解)，则其对偶问题无可行解；反之对偶 问题有可行解且目标函数值无界，则其原问题无 可行解（注意：本结论的逆不成立，举例说明）。 21
21 由弱对偶性，可得出以下推论： (1)原问题任一可行解的目标函数值是其对 偶问题目标函数值的下界；反之对偶问题任一可 行解的目标函数值是其原问题目标函数值的上界。 (2)如原问题有可行解且目标函数值无界(具 有无界解)，则其对偶问题无可行解；反之对偶 问题有可行解且目标函数值无界，则其原问题无 可行解（注意：本结论的逆不成立,举例说明)。 第一节 线性规划的对偶问题
第一节 线性规划的对偶问题 当对偶问题无可行解时，其原问题或具有无 界解或无可行解，反之亦然。 (3)若原问题有可行解而其对偶问题无可行 解，则原问题目标函数值无界；反之对偶问题有 可行解而其原问题无可行解，则对偶问题的目标 函数值无界（这个推论的证明用到了教材第55页 的结论)。 22
22 当对偶问题无可行解时，其原问题或具有无 界解或无可行解，反之亦然。 (3)若原问题有可行解而其对偶问题无可行 解，则原问题目标函数值无界；反之对偶问题有 可行解而其原问题无可行解，则对偶问题的目标 函数值无界（这个推论的证明用到了教材第55页 的结论）。 第一节 线性规划的对偶问题