212标准(max,≤)型的对偶变换 目标函数由max型变为min型 对应原问题每个约束行有一个对偶变量y,i=1,2,…,mn 对偶问题约束为≥型,有n行 原问题的价值系数C变换为对偶问题的右端项 原问题的右端项b变换为对偶问题的价值系数 原问题的技术系数矩阵A转置后成为对偶问题的技术 系数矩阵 原问题与对偶问题互为对偶 对偶问题可能比原问题容易求解 对偶问题还有很多理论和实际应用的意义
6 2.1.2 标准(max,)型的对偶变换 • 目标函数由 max 型变为 min 型 • 对应原问题每个约束行有一个对偶变量 yi，i=1,2,…,m • 对偶问题约束为 型，有 n 行 • 原问题的价值系数 C 变换为对偶问题的右端项 • 原问题的右端项 b 变换为对偶问题的价值系数 • 原问题的技术系数矩阵 A 转置后成为对偶问题的技术 系数矩阵 • 原问题与对偶问题互为对偶 – 对偶问题可能比原问题容易求解 – 对偶问题还有很多理论和实际应用的意义
2.13非标准型的对偶变换化为mx≤型标准问题 例2.1.2原线性规划问题 max f(x)=4x,+5x,-5 max f(x)=4x+5x2 3x1+2x2-2x≤20 3x1+2x,≤20 4x1+3x2-3x≤-10 4x1-3x2≥10 st x1+x2-x2≤5 st x1+ 不限,x1≥0 ≥0 y1=,y2=-2,y3=3-2应用标准型对偶变换规则 经整理得 mink(w)=20形1-10形2+5形3-54 mig(y)=201+10y2+5y 3形-4形2+2-w1≥4 3y1+4y2+y3≥4 2+3形+形2-w1≥5 st y-3y2+y3 2w1-3形,-3+形1≥ 0 y≥0,y20,y ±不限 w12w2,w3,w4≥0
2.1.3 非标准型的对偶变换 + = − + = + , 0 5 4 3 10 3 2 20 . . max ( ) 4 5 2.1.2 2 1 1 2 1 2 1 2 1 2 x x x x x x x x s t f x x x 不限 例 原线性规划问题 − − + − + − − + − − + − = + − , , 0 5 5 4 3 3 10 3 2 2 20 . . max ( ) 4 5 5 (max, ) 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 x x x x x x x x x x x x x x x s t f x x x x 化为 型标准问题 − − − + − + + − − + − = − + − , , , 0 2 3 5 2 3 5 3 4 4 . . min ( ) 20 10 5 5 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 w w w w w w w w w w w w w w w w s t h w w w w w 应用标准型对偶变换规则 − + = + + = + + = = − = − 不限 经整理得 令 1 2 3 1 2 3 1 2 3 1 2 3 1 1 2 2 3 3 4 0, 0, 2 3 5 3 4 4 . . min ( ) 20 10 5 : , , y y y y y y y y y s t g y y y y y w y w y w w
表211对偶变换的规则 原问题(max) 对偶问题(min) 技术系数矩阵A 技术系数矩阵A 价值系数C 右端项b 右端项b 价值系数C 第i行约束条件为≤型 对偶变量y≥0 第i行约束条件为≥型 对偶变量y≤0 第讠行约束条件为=型 对偶变量y±不限 决策变量x≥0 第j行约束条件为≥型 决策变量x≤0 第j行约束条件为≤型 决策变量x土不限 第j行约束条件为=型 约束条件的类型与非负条件对偶 非标准的约束条件类型对应非正常的非负条件 对偶变换是一一对应的
8 表2.1.1 对偶变换的规则 • 约束条件的类型与非负条件对偶 • 非标准的约束条件类型对应非正常的非负条件 • 对偶变换是一一对应的 原问题 (max) 对偶问题 (min) 技术系数矩阵 A 技术系数矩阵 A T 价值系数 C 右端项 b 右端项 b 价值系数 C 第 i 行约束条件为 型 对偶变量 yi 0 第 i 行约束条件为 型 对偶变量 yi 0 第 i 行约束条件为 = 型 对偶变量 yi 不 限 决策变量 xj 0 第 j 行约束条件为 型 决策变量 xj 0 第 j 行约束条件为 型 决策变量 xj 不 限 第 j 行约束条件为 = 型