对偶问题(运筹学).ppt

《对偶问题(运筹学).ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第四节对偶问题大连海事大学交通运输管理学院2.4.1对偶问题的提出2.4.2原问题与对偶问题2.4.3对偶问题的性质2.4.4对偶变量的经济含义2.4.5对偶单纯形法第四节对偶问题一、对偶问题的提出某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表1-1所示。每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问应如何安排计划使该工厂获利最多?1.最大生产利润模型设企业生产甲产品为X1件，乙产品为X2件，则2.资源最低售价模型(原问题)<========>(对偶问题)设第i种资源价格为yi,

2、(i=1,2,3)则有y1y2y3y4第2章对偶问题--二、原问题与对偶问题的关系一般表示式：原问题：maxz=c1X1+c2X2+┈+cnXns.ta11X1+a12X2+┈+a1nXnb1a21X1+a22X2+┈+a2nXnb2·······················am1X1+am2X2+┈+amnXnbmxj0，j=1,2,┈,n对偶问题：minw=b1y1+b2y2+┈+bmyms.ta11y1+a21y2+┈+am1ymc1a12y1+a22y2+┈+am2ymc2·························

3、a1ny1+a2ny2+┈+amnymcnyi0，(i=1,2,···,m)典式模型对应对偶结构矩阵表示（1）maxz=CXs.tAXbX0minw=Ybs.tYACY0对偶问题原问题对偶模型其他结构关系（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（3）maxz=CXs.tAXbX0变形设X=-X´max=-CX´st.-AX´bX´0minw=Ybs.tYACY

4、0则有minw=Ybs.t-YA-CY0对偶问题典式：用矩阵形式表示：（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0原问题与对偶问题关系表原问题(对偶问题)对偶问题(原问题)目标函数系数约束右端项约束右端项目标函数系数约束条件系数列向量A约束条件系数行向量AT变量个数约束条件个数maxmin变量xj:约束方程

5、i:xj0xj无约束=xj0约束方程:变量yi:yi0=yi无约束yi0例2-10写出下述线性规划问题的对偶问题。例子则由表中原问题和对偶问题的对应关系，可以直接写出上述问题的对偶问题对偶问题解法练习maxz=2y1+5y2+1y32y1+3y2+1y331y1-5y2+1y323y1+1y3-1≥=≤y1≥0,y2≤0,y3自由s.t.解minω=3x1+2x2-1x32x1+1x2+3x3≥23x1-5x2≤51x1+1x2+1x3=1x1≤0,x3≥0s.t.三、对偶问题的性质性质1对称性规范原始、对偶问题(P1)与(D1)

6、互相对偶。即对偶问题的对偶是原问题。性质2弱对偶性设X,Y分别为(P1)与(D1)的任意可行解，则CX≤Yb性质3最优性设X,Y分别为(P1)与(D1)的任意可行解，则当CX=Yb时，X,Y分别是(P1)与(D1)的最优解。三、对偶问题的性质性质4无界性互为对偶的两个线性规划问题，若其中一个问题的解无界，则另一个问题无可行解。性质5对偶定理互为对偶的两个线性规划问题，若其中一个问题有最优解，则另一个问题也有最优解，且二者最优值相等。注意：无界性之逆命题不成立。因为一个问题无可行解时，另一个问题可能解无界，也可能无可行解。三、对偶问题的性质兼容性原

7、始问题的检验行的相反数给出对偶问题的一个基本解。X*=(4,6,4,0,0)T,z*=42y1y2y3y4y5Y*=(0,1/2,1,0,0)T,w*=42σ3σ4σ5σ1σ2互补基本解x3x2x1x1x2x3x4x53500005360101/2040011/3-1/34100-2/31/342000-1/2-1cj比值基解:maxz=3x1+5x2x1≤82x2≤123x1+4x2≤36x1，x2≥0s.t.(P1):minw=8y1+12y2+36y3y1+3y3≥32y2+4y3≥5y1,y2,y3≥0s.t.(D1):maxz=3x1+

8、5x2x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥0s.t.(Ps):minw=8y1+12