《运筹学》第二章 对偶问题.ppt

《《运筹学》第二章 对偶问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章线性规划的对偶理论2.1对偶问题的提出2.2原问题与对偶问题的关系2.3对偶问题的性质2.4影子价格2.5对偶单纯形法2.6灵敏度分析2.7参数线性规划1对偶：Duality对偶问题：DualProblem对偶线性规划：DualLinearProgramming对偶理论：DualTheory22.1对偶问题的提出例：某企业计划生产甲、乙两种产品，该两种产品均需要A、B、C、D四种不同的材料，按工艺资料规定，生产一单位甲乙产品需要各种材料数量及单位产品利润如表中所示。问:如何安排产品的生产计划,才能使企业获利最大?3解：设企业生产甲产品为

2、X1件，乙产品为X2件，则maxz=2X1+3X2s.t.2X1+2X212X1+2X284X1164X212X10,X204如果另外一企业想将上述企业拥有的资源收买过来，至少应付出多少代价，才能使第一个企业愿意放弃生产活动，出售资源？我出让资源的代价不应低于我自己组织生产时的产值!我要用最小的代价购买资源!注:关键是确定转让价格5设第i种资源单位增值价（售价＝成本＋增值），为yi,（i=1,2,3,4）,则有minw=12y1+8y2+16y3+12y4s.t.2y1+y2+4y3+0y422y1+2y2+0y3+4y43y

3、i0,(i=1,2,3,4)61.最大生产利润模型设企业生产甲产品为X1件,乙产品为X2件，则maxz=2X1+3X2s.t2X1+2X212X1+2X284X1164X212X10,X202.资源最低售价模型原问题<========>对偶问题设第i种资源价格为yi,（i=1,2,3,4,）则有minw=12y1+8y2+16y3+12y4s.t2y1+y2+4y3+0y422y1+2y2+0y3+4y43yi0,(i=1,2,3,4)y1y2y3y4注：考虑角度不同，模型中的系数有对应关系。7对偶问题：minw=b1y1

4、+b2y2+┈+bmyma11y1+a21y2+┈+am1ymc1a12y1+a22y2+┈+am2ymc2·························a1ny1+a2ny2+┈+amnymcnyi0，(i=1,2,···,m)2.2原问题与对偶问题的关系原问题：maxz=c1x1+c2x2+┈+cnxna11x1+a12x2+┈+a1nxnb1a21x1+a22x2+┈+a2nxnb2·······················am1x1+am2x2+┈+amnxnbmxj0，j=1,2,┈,n一般形式：目标函数系数

5、:C=[c1c2…cn]系数矩阵:A=[aij]m×n约束右端项:b=b1b2:bm目标函数系数:b’系数矩阵:A’约束右端项:C’8（1）maxz=CXs.tAXbX0典式模型的对偶结构的矩阵表示minw=Ybs.tYACY0对偶问题原问题Y=(y1,…,ym)9(2)maxz=CXs.tAXbX0maxz=CXs.t-AX-bX0变形minw=Ybs.tYACY≤0minw=Y´(-b)st.Y´(-A)CY´0令Y=-Y´对偶问题对偶变量Y其它模型的对偶结构的矩阵表示10（3）maxz=CXs.t.AXbX0

6、变形设X=-X´maxz=(-C)X´s.t.(-A)X´bX´0minw=Ybs.t.YACY0minw=Ybs.t.Y(-A)-CY0对偶变量Y11原问题与对偶问题的对应关系用矩阵形式表示：（1）maxz=CXminw=Ybs.tAXb<========>s.tYACX0Y0（2）maxz=CXminw=Ybs.tAXb<========>s.tYACX0Y0（3）maxz=CXminw=Ybs.tAXb<========>s.tYACX0Y012原问题(对偶问题)对偶问题(原问题)目标函数系数约束右端

7、项约束右端项目标函数系数约束条件系数列向量A约束条件系数行向量A’变量个数约束条件个数maxmin变量xj:第j个约束方程:xj0xj无约束=xj0第i各约束方程:变量yi:yi0=yi无约束yi0原问题与对偶问题的对应关系表13例写出下列线性规划问题的对偶问题.解：原问题的对偶问题为对偶问题的对偶还是原问题14练习写出下列线性规划问题的对偶问题.152.3对偶问题的基本性质原问题对偶问题Maxz=CXMinw=Ybs.t.AXbs.t.YACX0Y0(1)弱对偶性(2)最优性(3)强对偶性(或称对偶定理)(4)互补松

8、弛性(5)单纯形表上的对应关系16弱对偶性：若X0是原问题可行解，Y0是对偶问题可行解，则CX0Y0b证明：∵Y00，AX0b，∴Y0AX0Y0b，而Y0A