第八章对偶线性规划问题 §8对偶线性规划问题的概念及性质 对偶线性规划问题的数学模型 设有线性规划问题 (I max==C11+ C2x2+.+Cntm C1x1+a12xX2+…+a1xn≤ b 21x1+a2x2+…+a2n2xn≤ m1x1+amn2x2+…+ mann b ≥0(j=1,2,…,n)
第八章 对偶线性规划问题 §8.1 对偶线性规划问题的概念及性质 一、 对偶线性规划问题的数学模型 设有线性规划问题 = + + + + + + + + + = + + + 0 ( 1,2, , ) s t max 1 1 2 2 2 1 1 2 2 2 2 2 1 1 1 1 2 2 1 1 1 1 2 2 x j n a x a x a x b a x a x a x b a x a x a x b z c x c x c x j m m m n n m n n n n n n (Ⅰ)
和线性规划问题 (Ⅱ)mS=by+b2y2+…+ bm y mm a111+a21y2+.tamm>Cl 2y1+a2y2+…+m2ym>C2 S·t c1n2y1+a2ny2+…+m.ym≥Cn y1≥0(i=1,2,…,m) 我们称问题(Ⅱ)为问题(I)的对偶线性规划问题, 简称对偶问题,而将问题(Ⅰ)称为原始线性规划问题, 简称为原始问题
和线性规划问题 我们称问题(Ⅱ)为问题(Ⅰ)的对偶线性规划问题, 简称对偶问题,而将问题(Ⅰ) 称为原始线性规划问题, 简称为原始问题. = + + + + + + + + + = + + + 0 ( 1,2, , ) s t min 1 1 2 2 1 2 1 2 2 2 2 2 1 1 1 2 1 2 1 1 1 1 2 2 y i m a y a y a y c a y a y a y c a y a y a y c S b y b y b y i n n mn m n m m m m m m ≥ ≥ ≥ ≥ (Ⅱ)
变量y(i=1,2,…,m)称为对偶(决策)变量. 问题(I)和问题(Ⅱ)的矩阵形式分别为 maxz=CX (I) AX<b 8.1) X≥0 minS=巧b (Ⅱ)′ YA≥C (82) y≥0
变量 yi (i =1,2, ···, m) 称为对偶(决策)变量. 问题(Ⅰ)和问题(Ⅱ) 的矩阵形式分别为 (Ⅰ) ′ (8.1) (Ⅱ) ′ (8.2) = X 0 AX b z CX s t max = Y 0 YA C S Yb s t min
其中C=(c;C2,…,cn)Y=(y,y,…,yn) 12 n n h2 12 mn 容易验证:若以问题(Ⅱ)为原始问题,按上述定义 则其对偶问题正好是原始问题(Ⅰ).这也就是说,原始 问题与对偶问题,实际上是互为对偶问题
其中C = ( c1 ,c2 , ···, cn ) Y = ( y1 , y2 , ···, ym ) 容易验证: 若以问题(Ⅱ)为原始问题, 按上述定义 则其对偶问题正好是原始问题(Ⅰ). 这也就是说, 原始 问题与对偶问题,实际上是互为对偶问题. = = = m m m n m n n n x x x b b b a a a a a a a a a 2 1 2 1 1 2 2 1 2 2 2 1 1 1 2 1 A b X
(I)和(Ⅱ)这种对称形式的对偶问题,其对称关系 可用下表表示 决策变量x1x2 n yI In S 2 maxz n
(Ⅰ)和(Ⅱ) 这种对称形式的对偶问题, 其对称关系 可用下表表示 决策变量 x1 x2 xn c1 c2 cn m m m m n m n n y a a a b y a a a b y a a a b 1 2 2 2 1 2 2 2 2 1 1 1 1 2 1 1 ≥ ≤ minS maxz