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 ( ) 对偶问题习惯写为: