第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< b a21 X1+ a22 X2+----+ a2n xn< b aml xi t am2 X2 n 对偶问题 min w= bi y1 b2 y2 +---- bm ym S t all y1 a21 y2 +-- aml ym> 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 原问题 对偶问题