哈尔滨工程大学：《运筹学基础》课程教学资源（PPT课件讲稿）第二章 线性规划的对偶理论

第2章对偶问题- 第2章线性规划的对偶理论 Dliy对偶 Dual problem对偶问题 Dual Linear programming 对偶线性规划 Dll7 heory对偶理论 2006/3

2006/3 --第2章 对偶问题-- --2-- 第 2 章 线性规划的对偶理论 Duality 对偶 Dual Problem 对偶问题 Dual Linear Programming 对偶线性规划 Dual Theory 对偶理论

第2章对偶问题- 2.1问题的提出 例:某企业计划生产甲、乙两种产品,该两种产品均需要A、B、C、 D四种不同的材料,按工艺资料规定,生产一单位甲乙产品需要各 种材料数量及单位产品利润如表中所示。问:如何安排产品的生产计 划,才能使企业获利最大? 设备 产品 A B D单位利润 甲产品2 C40 04 2 乙产品2 现有材料 28 数量 12 16 12 2006/3

2006/3 --第2章 对偶问题-- --3-- 2.1 问题的提出 例：某企业计划生产甲、乙两种产品，该两种产品均需要A、B、C、 D 四种不同的材料，按工艺资料规定，生产一单位甲乙产品需要各 种材料数量及单位产品利润如表中所示。问:如何安排产品的生产计 划,才能使企业获利最大? 设 备 产品 A B C D 单位利润 甲产品 乙产品 2 2 1 2 4 0 0 4 2 3 现 有材 料 数量 12 8 16 12

第2章对偶问题- 1最大生产利润模型 2资源最低售价模型 设企业生产甲产品为x1件, 设第评种资源价格为y,(i1,2,3,4,) 乙产品为x2件,则 则有 max z=2 X1 +3 X2 minw=12y1+8y2+16y3+12y4 St,2X1+2X2≤12y str2y1+y2+4y+0y4≥2 X1+2X2≤8 2y1+2y2+0y3+4y4≥3 4X1 16y 4X2≤12y X2≥0 (原问题) (对偶问题) 2006/3

2006/3 --第2章 对偶问题-- --4-- 1.最大生产利润模型 设 企业生产甲产品为X1件， 乙产品为X2件，则 max z= 2 X1 +3 X2 s.t 2 X1 +2 X2  12 X1 +2 X2  8 4 X1  16 4 X2  12 X1  0 , X2  0 2.资源最低售价模型 (原问题) ( 对偶问题) 设第i种资源价格为yi,（ i=1, 2, 3, 4,） 则有 min w= 12y1 + 8y2 + 16y3 +12 y4 s.t 2y1 + y2 + 4y3 +0 y4  2 2y1 +2y2 + 0y3 +4 y4  3 yi  0, (i=1, 2, 3, 4 ) y1 y2 y3 y4

第2章对偶问题- 22原问题与对偶问题的关系 般表示式 原问题: max Z= C1 X1 C2 2+ n Ar S t a11 X1 a12 X2+----+ ain xn C1 a12y1+a22y2 am2 ym 2 aln y1 t a2n y amn yr y 2006/3

2006/3 --第2章 对偶问题-- --5-- 2.2 原问题与对偶问题的关系 一般表示式： 原问题： max z = c1 X1 + c2 X2 + ┈ + cn Xn s.t a11 X1 + a12 X2 + ┈ + a1n Xn  b1 a21 X1 + a22 X2 + ┈ + a2n Xn  b2 ······················· am1 X1 + am2 X2 + ┈ + amn Xn  bm xj  0，j=1,2,┈,n 对偶问题： min w = b1 y1 + b2 y2 + ┈ + bm ym s.t a11 y1 + a21 y2 + ┈ + am1 ym  c1 a12 y1 + a22 y2 + ┈ + am2 ym  c2 ························· a1n y1 + a2n y2 + ┈ + amn ym  cn yi  0，(i=1,2,···,m )

第2章对偶问题- 典式模型对应对偶结构矩阵表示 原问题 对偶问题 (1) max Z=C X min w=yb stAX≤b S t YA≥C X≥0 Y≥0 2006/3

2006/3 --第2章 对偶问题-- --6-- 典式模型对应对偶结构矩阵表示 （1） max z = C X s.t AX  b X  0 min w = Y b s.t YA  C Y  0 原问题 对偶问题

第2章对偶问题- 对偶模型其他结构关系 (2)若模型为 max z=CX 变形 max z=CX st「AX≥b 对偶问题 st(-AX≤-b Ⅹ≥0 对偶变量Y′ Min w=Y (-b 令Y=Y st.∫Y"(-A)≥C min w=yb Y≥0 StYA≥C Y≤0 2006/3

2006/3 --第2章 对偶问题-- --7-- 对偶模型其他结构关系 （2）若模型为 max z = C X s.t AX  b X  0 max z = C X s.t - AX  -b X  0 变形 min w = Y b s.t YA  C Y  0 Min w=Y ´(-b) st. Y ´(-A)  C Y ´ 0 令 Y=- Y ´ 对偶问题 对偶变量Y

第2章对偶问题- (3)maxz=CⅩ max=-CX stAX≤b 设X=-X st.「-AX≤b Ⅹ≤0 X≥0 变形 min w=yb 则有 min w=yb st-YA≥-C stYA≤C Y≥0 Y≥0 2006/3

2006/3 --第2章 对偶问题-- --8-- （3）max z = C X s.t AX  b X  0 变形 设X= -X´ max = -CX ´ st. -AX´  b X´ 0 min w = Y b s.t YA  C Y  0 min w = Y b 则有 s.t -YA - C Y 0

第2章对偶问题- 对偶问题典式: 用矩阵形式表示: (1)maxz=CⅩ w=Yb st axs b >StYA≥C X≥0 Y≥0 (2) max Z=CX min w=yb stAX≥b >S.tYA≥C X≥0 Y≤0 (3) max Z= CX min w=yb st ax s b stYA≤C Ⅹ≤0 Y≥0 2006/3

2006/3 --第2章 对偶问题-- --9-- 对偶问题典式： 用矩阵形式表示： （1） max z = C X min w = Y b s.t AX  b s.t YA  C X  0 Y  0 （2） max z = C X min w = Y b s.t AX  b s.t YA  C X  0 Y  0 （3）max z = C X min w = Y b s.t AX  b s.t YA  C X  0 Y  0

第2章对偶问题- 原问题与对偶问题关系表 原问题(对偶问题) 对偶问题(原问题) 目标函数系数 约束右端项 约束右端项 目标函数系数 约束条件系数列向量A 约束条件系数行向量AT 变量个数 约束条件个数 max mIn 变量x 约束方程i x1≥0 Xj无约束 Xi≤0 约束方程 变量y;: yi≥0 yi无约束 yi≤0 2006/3

2006/3 --第2章 对偶问题-- --10-- 原问题与对偶问题关系表 原问题(对偶问题) 对偶问题(原问题) 目标函数系数 约束右端项 约束右端项 目标函数系数 约束条件系数列向量 A 约束条件系数行向量 AT 变量个数 约束条件个数 max min 变量 x j : 约束方程 i : x j  0  x j 无约束 = x j  0  约束方程: 变量 y i :  y i  0 = y i 无约束  y i  0

第2章对偶问题- 2.3对偶问题的基本性质 Max z= cX Min w=yb st.AX≤b st.YA≥C X≥0 Y≥0 (1)弱对偶性 若X0—原问题可行解,Y°对偶问题可行解 则CX0≤Y0b 证明:∵Y0≥0,AX0≤b,∴Y0AX0≤Y0b, 而Y0A≥C,∴CX0≤Y0AX0 ∴CX0<Y0AX0<Y0b 2006/3 11

2006/3 --第2章 对偶问题-- --11-- 2.3 对偶问题的基本性质 Max z = CX Min w = Y b s t . AX  b s t . YA  C X  0 Y  0 (1) 弱对偶性： 若 X0——原问题可行解，Y0——对偶问题可行解 则 CX0  Y0 b 证明： ∵ Y0  0， AX0  b，∴ Y0 AX0  Y0 b， 而 Y0 A  C ， ∴ CX0  Y0AX0 ， ∴ CX0  Y0 AX0  Y0 b