022对偶原理课件

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

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

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

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

5、最优解第10页，共33页。解：此问题的对偶问题为而其对偶问题的第一个约束条件不能成立，因此对偶问题不可行。故由推论3知原问题无界。因是原问题的一个可行解。由观察可知第11页，共33页。定理3(最优性判别定理) 若X*和Y*分别是问题(P)和(D)的可行解，且CX*=Y*b，则X*，Y*分别是问题(P)和(D)的最优解. 证明：对于问题（P）的任意一个可行解X ，必有CXY*b但 CX*=Y*b ，故对原问题（P）的所有可行解X，有CXCX*所以，X*为原问题（P）的最优解。同理可证Y*是对偶问题（D）的最优解。第12页，共33页。例在前面的例中，我们可以找到 X*=(0,0,4,4)T是原问题

6、的一个可行解，且 Z*= CX*=28， Y*=(1.2,0.2)是对偶问题的一个可行解，且 W*= Y*b=28.由于 CX*=Y*b，故由定理3知X*,Y*分别是原问题和对偶问题的最优解。第13页，共33页。定理4（对偶定理）若一对对偶问题（P）和（D）一个有最优解，则另一个也有最优解，且目标函数的最优值必相等。证明：设线性规划问题(P)有最优解.引入松弛变量 XS 将 (P) 化为标准形为第14页，共33页。记设 是线性规划问题(P)的一个最优解，对应的基矩阵为B，对应的基变量为xi1 , xi2 , , xit , xs1, xs2 , , xsr对应的目标分量为令 , 现证明其就是问

7、题(D)的最优解.非基变量x j 的检验数成立第15页，共33页。一对对偶问题的关系，只能有下面三种情况之一： 1. 都有最优解； 2.一个问题无界，则另一个问题无可行解； 3. 两个都无可行解.一对对偶问题解的情况：第16页，共33页。推论问题(P)的最优解的单纯形表中检验数行对应问题(D)的最优解。更一般地，问题(P)基可行解的单纯形表中检验数行对应问题(D)的一个基解.XBXNXS注：0CN-CBB-1 N-CBB-1-YYS1-YS2第17页，共33页。Cj45000iCBXBbx1x2x3x4x54x145/2103/20-1/20 x425/200-5/211/25x245/201

8、-1/201/2j00-7/20-1/2例第18页，共33页。Cj-45-80-9000iCBYBby1y2y3y4y5-45y17/215/20-3/21/2-90y31/20-1/211/2-1/2j0-25/20-45/2-45/2第19页，共33页。Cj-45-80-9000iCBYBby1y2y3y4y5-45y17/215/20-3/21/2-90y31/20-1/211/2-1/2j0-25/20-45/2-45/2Cj45000iCBXBbx1x2x3x4x54x145/2103/20-1/20 x425/200-5/211/25x245/201-1/201/2j00-7/20

9、-1/2第20页，共33页。定理5设 X* 和Y* 分别是问题（P）和（D）的可行解，则它们分别是最优解的充要条件是 同时成立：互补松弛定理式（1）和（2）可以写成下面的等价形式 其中第21页，共33页。证明：在问题（P）和（D）中，分别引入松弛变量Xs=(xn+1, xn+2, xn+m)T和剩余变量Ys=(ym+1, ym+2, ym+n)T，因为X*,Y*是可行解，则有AX*+Xs*=b，X*0，Xs*0; (3)Y*AYs*=C，Y*0，Ys*0; (4)其中Xs*, Ys*表示对应于可行解X*和Y*的松弛变量和剩余变量Xs, Ys的值 第22页，共33页。用Y*左乘式（3）, 得Y*

10、A X*+Y*Xs*= Y*b (5)用X*右乘式（4）, 得Y*A X*Ys*X*= CX* (6)又由于 CX*=Y*b ，将上两式相减，得 Y*Xs*+Ys*X*=0AX*+Xs*=b，X*0，Xs*0; (3)Y*AYs*=C，Y*0，Ys*0; (4)又由变量的非负性可知，必有Y*Xs*=0 (7)Ys*X*=0 (8) 代入式（5）和（6），Y*A X*+Y*Xs*= Y*b (5)Y*A X*Ys*X*= CX* (6)即得式（1）和（2）.第23页，共33页。 再证充分性，若式（1）和（2）成立，知，CX*=Y*b 。再由定理3知，X*和Y*必分别是问题（P）和（D）的最优解。

11、第24页，共33页。互补松弛关系在问题（P）和（D）的最优解 X* 和Y* 处（1） 若有某个 x*j 0，则必有 Y*Pj=cj ；（2） 若有某个 Y*Pj cj ，则必有 x*j =0 ；（3） 若有某个 y*j 0 ，则必有 aiX*=bi ；（4） 若有某个 aiX*bi ，则必有 yi*=0 .这种关系称为互补松弛关系.第25页，共33页。如果该约束在所有最优解上的值使左右取等号的一个约束称为紧约束。 即我们把严格等式约束称为紧约束（或起作用约束）. 不是紧约束的约束称为松约束。 即把某一最优解处取严格不等式的约束称为松约束（或不起作用约束）。对于最优解X*和Y*而言，松约束的对偶

12、约束是紧约束.以上关系称为对偶问题的互补松弛关系或松紧关系。在计算上，若已知一个问题的最优解，则可利用互补松弛条件求另一个问题的最优解.紧约束与松约束松紧关系非常重要第26页，共33页。例试用对偶原理求解线性规划问题已知其对偶规划的最优解为掌握第27页，共33页。解：该问题的对偶规划为第28页，共33页。利用松紧关系，代入对偶规划的约束条件得下列约束是松约束，将最优解松约束紧约束其对偶约束是紧约束第29页，共33页。设原问题的最优解为紧约束第30页，共33页。 对偶规划可以用线性规划的单纯形法求解。由对偶原理可见，原问题与对偶问题之间有紧密联系，因此我们能够通过求解原问题来找出对偶问题的解，反之依然。互补松弛条件就可以解决由原问题的最优解直接求出对偶问题的最优解。注：对偶问题解的求法第31页，共3