《对偶原理》PPT课件

《《对偶原理》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§2.2对偶原理对偶原理给出了原问题和对偶问题之间的重要关系.为了讨论问题方便我们以“对称型对偶问题”来进行研究和证明，当然所有这些结论对于其它形式的对偶问题也同样成立。定理1（对称性定理）对偶问题的对偶是原问题.定理2（弱对偶定理）分别是问题(P)和(D)的可行解，设和则必有注：推论2不存在逆.推论1：若X0和Y0分别是问题(P)和(D)的可行解，则（1）CX0是问题(D)的目标函数的一个下界；（2）Y0b是问题(P)的目标函数的一个上界。推论2(无界性)：在一对对偶问题(P)和(D)中，若其中一个问题有可行解，但目标函数无界，则另一个问题无可行解.推论3：在一对对偶问题(P)

2、和(D)中，若其中一个问题有可行解，而另一个无可行解，则该问题无界.定理4（对偶定理）若一对对偶问题（P）和（D）一个有最优解，则另一个也有最优解，且目标函数的最优值必相等.定理5设X*和Y*分别是问题（P）和（D）的可行解，则它们分别是最优解的充要条件是同时成立：（互补松弛定理）定理3(最优性判别定理)若X*和Y*分别是问题(P)和(D)的可行解，且CX*=Y*b，则X*，Y*分别是问题(P)和(D)的最优解.定理1（对称性定理）对偶问题的对偶是原问题.根据这一定理，在一对对偶问题中，我们可以把其中任何一个称为原问题，则另一个就是其对偶问题.证明：将问题(D)改写对称形式(D)’：

3、对于问题（D）记对偶变量为XT，则(D)’的对偶规划为这就是原问题(P),证毕.定理2（弱对偶定理）分别是问题(P)和(D)的可行解，设和则必有证明：是问题(P)的可行解，故必有是问题(D)的可行解，故必有左乘不等式（1）两边得右乘不等式（2）两边得由（3）和（4）式可知证毕.因同理,由于用用由弱对偶性，有下面推论：注：推论2不存在逆.推论1：若X0和Y0分别是问题(P)和(D)的可行解，则（1）CX0是问题(D)的目标函数的一个下界；（2）Y0b是问题(P)的目标函数的一个上界。推论2：在一对对偶问题(P)和(D)中，若其中一个问题有可行解，但目标函数无界，则另一个问题无可行解

4、.推论3：在一对对偶问题(P)和(D)中，若其中一个问题有可行解，而另一个无可行解，则该问题无界.例已知原问题(LP)，试估计它的目标函数值的界,并验证弱对偶定理.解：问题(LP)的对偶问题(DP)为(DP)解：由观察可知分别是原问题和对偶问题的可行解。，弱对偶定理成立。且由推论1知，对偶问题目标函数W的下界为10，原问题目标函数Z的上界为40。且原问题的目标函数值为对偶问题的目标函数值为故例：利用对偶性质判断下面问题有无最优解解：此问题的对偶问题为而其对偶问题的第一个约束条件不能成立，因此对偶问题不可行。故由推论3知原问题无界。因是原问题的一个可行解。由观察可知定理3(最优性判别定

5、理)若X*和Y*分别是问题(P)和(D)的可行解，且CX*=Y*b，则X*，Y*分别是问题(P)和(D)的最优解.证明：对于问题（P）的任意一个可行解X，必有CX≤Y*b但CX*=Y*b，故对原问题（P）的所有可行解X，有CX≤CX*所以，X*为原问题（P）的最优解。同理可证Y*是对偶问题（D）的最优解。例在前面的例中，我们可以找到X*=(0,0,4,4)T是原问题的一个可行解，且Z*=CX*=28，Y*=(1.2,0.2)是对偶问题的一个可行解，且W*=Y*b=28.由于CX*=Y*b，故由定理3知X*,Y*分别是原问题和对偶问题的最优解。定理4（对偶定理）若一对对偶问题（P）和（

6、D）一个有最优解，则另一个也有最优解，且目标函数的最优值必相等。证明：设线性规划问题(P)有最优解.引入松弛变量XS将(P)化为标准形为记设是线性规划问题(P’)的一个最优解，对应的基矩阵为B，对应的基变量为xi1,xi2,…,xit,xs1,xs2,…,xsr对应的目标分量为令,现证明其就是问题(D)的最优解.非基变量xj的检验数成立一对对偶问题的关系，只能有下面三种情况之一：1.都有最优解；2.一个问题无界，则另一个问题无可行解；3.两个都无可行解.一对对偶问题解的情况：推论问题(P)的最优解的单纯形表中检验数行对应问题(D)的最优解。更一般地，问题(P)基可行解的单纯形表中检验

7、数行对应问题(D)的一个基解.XBXNXS注：0CN-CBB-1N-CBB-1-YYS1-YS2Cj45000θiCBXBb’x1x2x3x4x54x145/2103/20-1/20x425/200-5/211/25x245/201-1/201/2λj00-7/20-1/2例Cj-45-80-9000θiCBYBb’y1y2y3y4y5-45y17/215/20-3/21/2-90y31/20-1/211/2-1/2λj0-25/20-45/2-45/2C