CPOSIS AND 邮电大生 管理与人文学院忻展红 1999,4 第二章 线性规划的对偶理论及其应用 窗含西岭千秋雪,门泊东吴万里船 对偶是一种普遍现象
©管理与人文学院 忻展红 1999，4 第二章 线性规划的对偶理论及其应用 窗含西岭千秋雪，门泊东吴万里船 对偶是一种普遍现象
2线性规划的对偶理论 211线性规划原问题与对偶问题的表达形式 ·任何线性规划问题都有其对偶问题 对偶问题有其明显的经济含义 maxf(x)=x,+2x2-3x3+4x4 x1+2x2+2x2-3x4≤25A资源 st.{2x+x2-3x3+2x1≤15B资源 x1,x2,x2,xA≥0 假设有商人要向厂方购买资源A和B,问他们谈判原料 价格的模型是怎样的?
2 2.1 线性规划的对偶理论 2.1.1 线性规划原问题与对偶问题的表达形式 • 任何线性规划问题都有其对偶问题 • 对偶问题有其明显的经济含义 假设有商人要向厂方购买资源A和B，问他们谈判原料 价格的模型是怎样的？ + − + + + − = + − + , , , 0 2 3 2 15 B 2 2 3 25 A . . max ( ) 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 x x x x x x x x x x x x s t f x x x x x 资源 资源
例211 maxf(x)=x+2x2-3x3+4x2 x1+2x2+2x3-3x4≤25A资源 st.{2x1+x2-3x3+2x4≤15B资源 x1,x2,x32x4≥0 目标函数ming()=25y1+15y2 y+2y2≥1产品1的所得 2j1+y2≥2产品2的所得 st.{2yn-32≥-3产品3的所得 3+2y2≥4产品4的所得 n12y2≥0
3 例2.1.1 – 设A、B资源的出售价格分别为 y1 和 y2 – 显然商人希望总的收购价越小越好 – 工厂希望出售资源后所得不应比生产产品所得少 − + − − + + , 0 3 2 4 4 2 3 3 3 2 2 2 2 1 1 . . 1 2 1 2 1 2 1 2 1 2 y y y y y y y y y y s t 产品 的所得 产品 的所得 产品 的所得 产品 的所得 目标函数 min g(y)=25y1+15y2 + − + + + − = + − + , , , 0 2 3 2 15 B 2 2 3 25 A . . max ( ) 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 x x x x x x x x x x x x s t f x x x x x 资源 资源
211线性规划原问题与对偶问题的表达形式 原问题:maxf(x)=CX对偶问题:ming(y)=Ybb AX< b YA≥C s t st X≥0 Y≥0 上两式中 X=(x1,x2,…,xn Y=(y12y2…,ym 21 n n m2 b=(b,b2,…,bn)y
4 2.1.1 线性规划原问题与对偶问题的表达形式 = X 0 AX b s t f x CX . . 原问题 : max ( ) = Y 0 Y A C s t g y Y b . . 对偶问题 : min ( ) T m n m T n b b b b C c c c Y y y y X x x x ( , , , ) ( , , , ) ( , , , ) ( , , , ) 1 2 1 2 1 2 1 2 = = = = 上两式中 = m m mn n n a a a a a a a a a A 1 2 21 22 2 11 12 1
211线性规划原问题与对偶问题的表达形式 把对偶问题展开 对偶问题习惯写为 ming(y)=b,y,+b2y2+.+bmy min g(r=bY y1+a21y2+…+amy AY>C st 2n1+a2y2+…+am2ymC2 Y≥0 s t any1+a2ny2+…+amym≥Cn y2y2…ynm≥0
5 2.1.1 线性规划原问题与对偶问题的表达形式 + + + + + + + + + = + + + , , , 0 . . min ( ) 1 2 1 1 2 2 1 2 1 2 2 2 2 2 1 1 1 2 1 2 1 1 1 1 2 2 m n n mn m n m m m m m m y y y a y a y a y c a y a y a y c a y a y a y c s t g y b y b y b y 把对偶问题展开 = Y 0 A Y C s t g Y b Y T T T T T . . min ( ) 对偶问题习惯写为:
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 行约束条件为 = 型
22线性规划的对偶定理 为了便于讨论,下面不妨总是假设 原问题:maxf(x)=CX对偶问题:ming(y)=Yb AX< b YA≥C s t X≥0 Y≥0 221弱对偶定理 定理对偶问题min)的任何可行解Y,其目标函数值总是 不小于原问题(max)任何可行解γ的目标函数值 证:由于X0,Y0分别为原问题和对偶问题的可行解故有 AX<b YA≥C X≥0 0 0 容易看出有Yb≥Y0AX0≥CX0.#
9 2.2 线性规划的对偶定理 2.2.1 弱对偶定理 定理 对偶问题(min)的任何可行解Y 0 ，其目标函数值总是 不小于原问题(max)任何可行解X0的目标函数值 • 为了便于讨论，下面不妨总是假设 = X 0 AX b s t f x CX . . 原问题 : max ( ) = Y 0 Y A C s t g y Y b . . 对偶问题 : min ( ) Y b Y AX CX # Y 0 Y A C X 0 AX b X Y . : , , 0 0 0 0 0 0 0 0 0 0 容易看出有 证 由于 分别为原问题和对偶问题的可行解 故有
弱对偶定理推论 max问题的任何可行解目标函数值是其对偶min问题 目标函数值的下限;min问题的任何可行解目标函数 值是其对偶max问题目标函数值的上限 如果原max(min问题为无界解,则其对偶min(max) 问题无可行解 如果原max(min问题有可行解,其对偶min(max)问 题无可行解,则原问题为无界解 注:有可能存在原问题和对偶问题同时无可行解的情 况
10 弱对偶定理推论 • max问题的任何可行解目标函数值是其对偶min问题 目标函数值的下限； min问题的任何可行解目标函数 值是其对偶max问题目标函数值的上限 • 如果原max(min)问题为无界解，则其对偶 min (max) 问题无可行解 • 如果原max(min)问题有可行解，其对偶 min (max)问 题无可行解，则原问题为无界解 • 注：有可能存在原问题和对偶问题同时无可行解的情 况