线性规划的对偶模型 Page 11 原问题（或对偶问题） 对偶问题（或原问题） 约束条件右端项 目标函数变量的系数 目标函数变量的系数 约束条件右端项 目标函数max 目标函数min 约 m个 m个 ≤ ≥0 变 条 ≥ ≤0 = 无约束 n个 n个 变量 ≥0 ≥ ≤0 ≤ 约束条件 无约束
线性规划的对偶模型 Page 11 原问题（或对偶问题） 对偶问题（或原问题） 约束条件右端项 目标函数变量的系数 目标函数变量的系数 约束条件右端项 目标函数 max 目标函数 min 约 束 条 件 m个 m个 变 量 ≤ ≥0 ≥ ≤0 = 无约束 变 量 n个 n个 约 束 条 件 ≥0 ≥ ≤0 ≤ 无约束 =
线性规划的对偶模型 Page 12 例2.2写出下列线性规划问题的对偶问题. max Z=2x+3x2-5x3+x 4x1+x2-3x3+2x4≥5 3x1-2x2+7x4≤4 2x1+3x2+4x3+x4=6 x1≤0，x2,x3≥0，x无约束 解：原问题的对偶问题为 minW=5y +4y2 +6y3 4y1+3y2-2y3≤2 y1-2y2+3y3≥3 一3y+ 4y3≥-5 2y1+7y2+y3=1 y,≤0，y2≥0，y无约束
线性规划的对偶模型 Page 12 例2.2 写出下列线性规划问题的对偶问题. − + + + = − + + − + = + − + 1 2 3 4无约束 1 2 3 4 1 2 4 1 2 3 4 1 2 3 4 0, , 0, 2 3 4 6 3 2 7 4 4 3 2 5 max 2 3 5 x x x x x x x x x x x x x x x Z x x x x 解：原问题的对偶问题为 + + = − + − − + + − = + + 1 2 3 无约束 1 2 3 1 3 1 2 3 1 2 3 1 2 3 0, 0, 2 7 1 3 4 5 2 3 3 4 3 2 2 min 5 4 6 y y y y y y y y y y y y y y W y y y
对偶性质 Page 13 例2.3分别求解下列2个互为对偶关系的线性规划问题 max=2x+ minw=15y,+24y2+5y3 5x2+x3=15 6y2+y3-y4=2 6x1+2x2+x4=24 s.t s.t5y1+2y2+y3-y=1 x1+x2+x=5 y,≥0 x,≥0 分别用单纯形法求解上述2个规划问题，得到最终单纯形表如 下表：
对偶性质 Page 13 例2.3 分别求解下列2个互为对偶关系的线性规划问题 + + = + + = + = = + 0 5 6 2 24 5 15 . max 2 1 2 5 1 2 4 2 3 1 2 x j x x x x x x x x s t z x x + + − = + − = = + + 0 5 2 1 6 2 . min 15 24 5 1 2 3 5 2 3 4 1 2 3 i y y y y y y y y s t w y y y 分别用单纯形法求解上述2个规划问题，得到最终单纯形表如 下表：
对偶性质 Page 14 原问题的变量 原问题的松弛变量 b 原问 XE X1 X2 X3 X4 X5 题最 X3 15/2 0 0 1 5/4 -15/2 优表 XI 7/2 1 0 0 1/4 -1/2 X2 3/2 0 1 0 -1/4 3/2 0 0 0 -1/4 -1/2 对偶问题的变量 对偶问题的剩余变量 XB b 对偶 y1 y2 Y3 y4 5 问题 y2 1/4 -4/5 1 0 -1/4 1/4 最优 y3 1/2 15/2 0 1 1/2 -3/2 表 15/2 0 0 7/2 3/2
对偶性质 Page 14 XB b 原问题的变量 原问题的松弛变量 x1 x2 x3 x4 x5 x3 15/2 0 0 1 5/4 -15/2 x1 7/2 1 0 0 1/4 -1/2 x2 3/2 0 1 0 -1/4 3/2 0 0 0 －1/4 －1/2 j XB b 对偶问题的变量 对偶问题的剩余变量 y1 y2 y3 y4 y5 y2 1/4 -4/5 1 0 -1/4 1/4 y3 1/2 15/2 0 1 1/2 -3/2 15/2 0 0 7/2 3/2 j 原问 题最 优表 对偶 问题 最优 表
对偶性质 Page 15 原问题与其对偶问题的变量与解的对应关系： 在单纯形表中，原问题的松弛变量对应对 偶问题的变量，对偶问题的剩余变量对应原问 题的变量
对偶性质 Page 15 原问题与其对偶问题的变量与解的对应关系： 在单纯形表中，原问题的松弛变量对应对 偶问题的变量，对偶问题的剩余变量对应原问 题的变量