运筹学对偶理论与灵敏度分析.ppt

《运筹学对偶理论与灵敏度分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1第2章线性规划的对偶理论与灵敏度分析第一节线性规划的对偶理论2一、对偶问题的提出在同一企业的资源状况和生产条件下产生的，且是同一个问题从不同角度考虑所产生的，因此两者密切相关-----两个LP问题是互为对偶3即任何一个求maxZ的LP都有一个求minW的LP。“原问题”----“LP”，“对偶问题”------“DP”。41、原问题与对偶问题--对称形式(1)原问题中的约束条件个数等于它的对偶问题中的变量数；(2)原问题中目标函数的系数是其对偶问题中约束条件的右端项；(3)约束条件在原问题中为“≤”，则在其对偶问题

2、中为“≥”；(4)目标函数在原问题中为求最大值，在其对偶问题中则为求最小值。二、对偶理论5例2.2写出下述线性规划问题的对偶问题解：按照上述规则，该问题的对偶线性规划为:6非对称形式---例如：当原问题约束条件为等式对偶问题:特点：对偶变量符号不限7对于一般情况下线性规划问题如何写出对偶问题。对于等式约束可以把它写成两个不等式约束，对于“≥”的不等式，可以两边同乘“－1”，再根据对称形式的对偶关系写出对偶问题，然后进行适当的整理，使式中出现的所有系数与原问题中的系数相对应。归纳-----表2.28MaxMin约束条件

3、数=m变量个数=m第i个约束条件“≤”“≥”“=”第i个变量≥0≤0无限制变量数=n约束条件数=n第i个变量≥0≤0无限制第i个约束条件为“≥”为“≤”为“=”第i个约束条件的右端项目标函第i个变量的系数目标函数第i个变量的系数第i个约束条件的右端项表2.29例2.3写出下述线性规划问题的对偶问题10例2.4写出下述线性规划问题的对偶问题112、对偶问题的基本定理（1）（对称性）对偶问题的对偶是原问题。（2）（弱对偶定理）若X(0)是原问题的可行解，Y(0)是对偶问题的可行解，则有CX(0)≤Y(0)b。(3）（无

4、界性）若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。（4）（最优性定理），若X(0)、Y(0)分别是互为对偶问题的可行解，且CX(0)=Y(0)b，则X(0)、Y(0)分别是它们的最优解。（5）（强对偶定理）若互为对偶问题之一有最优解，则另一问题必有最优解，且它们的目标函数值相等。（6）（互补松驰性）若X*、Y*分别是原问题和对偶问题的可行解，则X*、Y*是最优解的充要条件是：Y*XS=0,YSX*=0(其中XS，YS分别是原问题和对偶问题的松驰变量向量)。12证：设原问题是maxZ=CX；AX

5、≤b；X≥0其对偶问题为minW=Yb；YA≥C；Y≥0又因为可得对称变换，上式的对偶问题是max（-W）=-Yb；-YA≤-C，Y≥0两边取负号，因minW＝max（-W），得到（1）（对称性）对偶问题的对偶是原问题。13证：设原问题是若X(0)是原问题的可行解，Y(0)是对偶问题的可行解，则有CX(0)≤Y(0)b。将右乘上式，得到因为是LD的可行解，所以满足对偶问题是是LD的可行解，将左乘上式，得到是LP可行解，满足约束,即（2）（弱对偶定理）14注意：不存在逆。当原问题（对偶问题）无可行解时，其对偶问题（原问

6、题）或具有无界解或无可行解。若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。证：由弱对偶性CX(0)≤Y(0)b，显然得。（3）（无界性）15证：若所以是最优解。同样证明：对于LP所有可行解X，存在可见使目标函数取值最小的可行解，既最优解。因为，所以根据性质2，LD的所有可行解Y都存在若X(0)、Y(0)分别是互为对偶问题的可行解，且CX(0)=Y(0)b，则X(0)、Y(0)分别是它们的最优解。（4）（最优性定理），16若互为对偶问题之一有最优解，则另一问题必有最优解，且它们的目标函数值相等。是原问题

7、的最优解，对应基阵B必存在即得到，其中若是对偶问题的可行解，它使因原问题的最优解是，使目标函数取值由此，得到是对偶问题的最优解。（5）（强对偶定理）17从上述性质中，可看到原问题与对偶问题的解必然是下列三种情况之一：①原问题与对偶问题都有最优解，且CX=Yb；②一个问题具有无界解，则它的对偶问题无可行解；③两个问题均无可行解。18若X*、Y*分别是原问题和对偶问题的可行解，则X*、Y*是最优解的充要条件是：Y*XS=0,YSX*=0(其中XS，YS分别是原问题和对偶问题的松驰变量向量)。证明：设原问题和对偶问题的标准

8、型是原问题对偶问题（6）（互补松驰性）19将原问题目标函数中的系数向量C用代替后，得到必有又若分别是原问题和对偶问题的最优解，则若；则故是最优解。将对偶问题的目标函数中的系数向量，用代替后，得到20松约束:某一可行点（如X*和Y*）处的严格不等式约束（包括对变量的非负约束）紧约束:严格等式约束已知试通过求LD的最优解来求解LP的最优解。例2.5