管理运筹学 02-线性规划课件.ppt

《管理运筹学 02-线性规划课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、,3)则有y1y2y3y4二、原问题与对偶问题的关系一般表示式：原问题：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·························a1ny1+a2ny2+┈+amnymcnyi0，(i=1,2,···

3、,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0则有minw=Ybs.t-YA-CY0对偶问题典式：用矩阵形式表示：（1）maxz=CXminw=Ybs.tA

4、X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:约束方程i:xj0xj无约束=xj0约束方程:变量yi:yi0=yi无约束yi0例2-10写出下述线性规划问题的对偶问题。例子则由表中原问题和对偶问题的对

5、应关系，可以直接写出上述问题的对偶问题对偶问题解法--第2章对偶问题----13--(1)对称性对偶问题的对偶是原问题;(2)弱对偶性若X是原问题的可行解，Y是对偶问题的可行解。则存在CX≤Yb;(3)无界性若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解;(4)可行解是最优解时的性质;(5)对偶定理若原问题有最优解，那么对偶问题也有最优解；且目标函数值相等;(6)兼容性;(7)互补松弛性.三、对偶问题的性质1.对称性对偶问题的对偶是原问题。三、对偶问题的性质证设原问题是maxz=CX;AX≤b；X≥0根据对偶问题的对称变换关系，可以找到它的对偶问题是minω=Yb;YA≥C；

6、Y≥0若将上式两边取负号，又因minω=max(-ω)可得到max(-ω)=-Yb;-YA≤-C；Y≥0根据对称变换关系，得到上式的对偶问题是min(-ω′)=-CX；-AX≥-b;X≥0又因min(-ω′)=maxω′可得maxω′=maxz=CX；AX≤b;X≥0这就是原问题。证毕。2.弱对偶性若是原问题的可行解，是对偶问题的可行解。则存在;二、对偶问题的性质3.无界性若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解。由弱对偶性可知，，不可能成立，因此可证。4.可行解是最优解时的性质设是原问题的可行解，是对偶问题的可行解，当时，分别是原问题与对偶问题的最优解。5.对偶定理若

7、原问题有最优解，那么对偶问题也有最优解；且目标函数值相等。6.兼容性该性质设原问题是它的对偶问题是原问题与对偶问题标准化后，具有相同的分量个数。这些分量相互之间存在着对应的关系。原问题的松弛变量对应着对偶问题的决策变量，对偶问题的剩余变量对应着原问题的决策变量。则原问题单纯形表的检验数行的相反数对应其对偶问题的一个基解，且二者目标函数值相等。我们把这样一对基本解称为互补基本解。主要讨论原问题检验数与对偶问题解的关系。例子