第八章对偶线性规划问题 §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
下面我们讨论标准形线性规划的对偶问题 设线性规划问题为 min s=cX AX=b (8.3) X≥0 等价于minS=CX AX≥b X≥ st-AX≥-b即stl-A bb (8.4) X≥0 X≥0
下面我们讨论标准形线性规划的对偶问题. 设线性规划问题为 s t s t min s t min − − − − = = = 0 0 0 X b b X A A X A X b A X b S C X X A X b S C X 即 等价于 (8.3) (8.4)
引进向量Y≥0,Y2≌0,则(84)的对偶问题可表为 maxz=(Y,Y2) C S·t H1≥0,Y2≥0 max=(-n,)b ∫G1-Y2)4≤C H1≥0,Y2≥0
− = − − − = 0 0 ( ) ( ) 0 0 1 2 1 2 1 2 1 2 , max , ( ) s t max ( ) 1 , 2 1 2 Y Y Y Y A C z Y Y b Y Y C A A Y Y b b z Y , Y 即 引进向量 Y1≥0, Y2≥0, 则（8.4）的对偶问题可表为
令 Y=Y 25 得线性规划问题(8.3)的对偶问题为 maxz=Y6 YA<C S·t (8.5) Y无非负限制 由于 min s= cX maxz=Y6 AX=b YA<C S·t 与s·t Ⅹ≥0 Y无非负限制
s t s t min max s t max = = = = = − 无非负限制 与 由于 无非负限制 令 Y YA C X A X b S C X z Yb Y YA C z Yb Y Y Y 0 , 1 2 得线性规划问题（8.3）的对偶问题为 (8.5)
在形式上不对称,故称这类对偶问题为非对称型对偶 问题 可以证明:(8.5)的对偶问题就是(8.3)也就是说(83) 与(8.5)互为对偶问题在这类非对称的对偶问题中, 个问题的约束条件为等式,则另一问题对应的决策变量 就无非负限制,反之亦然 综合对称型与非对称型对偶问题可得各类型对 偶问题的形式的对偶规则如下
在形式上不对称, 故称这类对偶问题为非对称型对偶 问题. 可以证明: (8.5)的对偶问题就是(8.3).也就是说(8.3) 与(8.5)互为对偶问题.在这类非对称的对偶问题中,一 个问题的约束条件为等式,则另一问题对应的决策变量 就无非负限制, 反之亦然. 综合对称型与非对称型对偶问题,可得各类型对 偶问题的形式的对偶规则如下:
原始问题(对偶问题 对偶问题(原始问题) 1目标函数求maxz 目标函数求minS 2目标函数中系数为c; 约束条件中常数为c 3约束条件中常数为b目标函数系数为b 4约束条件的系数矩阵为A约束条件的系数矩阵为Ar 5约束条件为m个 对偶变量为m个 6决策变量为n个 约束条件为n个 7有第个约束条件为“≤”对偶变量y≥0 8有第k个约束为“=” 对偶变量ν无非负限制 9决策变量无非负限制第个约束条件为“= 10决策变量x≥0 第个约束条件为“≥
原始问题(对偶问题) 对偶问题(原始问题) 1.目标函数求maxz 目标函数求minS 2.目标函数中系数为ci 约束条件中常数为ci 3.约束条件中常数为bi 目标函数系数为bi 4.约束条件的系数矩阵为A 约束条件的系数矩阵为AT 5.约束条件为m个 对偶变量为m个 6.决策变量为n个 约束条件为n个 7.有第i个约束条件为“≤ ” 对偶变量yi ≥ 0 8.有第k个约束为“=” 对偶变量yk无非负限制 9.决策变量xj无非负限制 第j个约束条件为“=” 10.决策变量xj≥0 第j个约束条件为“≥
