《022对偶原理.ppt》由会员分享，可在线阅读，更多相关《022对偶原理.ppt（33页珍藏版）》请在三一文库上搜索。
1、2.2 对偶原理,对偶原理给出了原问题和对偶问题之间的重要关系.,为了讨论问题方便我们以“对称型对偶问题”来进行研究和证明，当然所有这些结论对于其它形式的对偶问题也同样成立。,定理1（对称性定理）对偶问题的对偶是原问题.,定理2（弱对偶定理）,分别是问题(P)和(D)的可行解，,设,和,则必有,注：推论2不存在逆.,推论1：若 X0 和Y0 分别是问题(P)和(D)的可行解，则 （1） CX0是问题(D)的目标函数的一个下界； （2） Y0 b是问题(P)的目标函数的一个上界。,推论2(无界性)：在一对对偶问题(P)和(D)中，若其中一个问题有可行解，但目标函数无界，则另一个问题无可行解.,推
2、论3：在一对对偶问题(P)和(D)中，若其中一个问题有可行解，而另一个无可行解，则该问题无界.,定理4（对偶定理） 若一对对偶问题（P）和（D）一个有最优解，则另一个也有最优解，且目标函数的最优值必相等.,定理5,设 X* 和Y* 分别是问题（P）和（D）的可行解，则它们分别是最优解的充要条件是 同时成立：,（互补松弛定理）,定理3(最优性判别定理) 若X*和Y*分别是问题(P)和(D)的可行解，且 CX*=Y*b， 则X*，Y*分别是问题(P)和(D)的最优解.,定理1（对称性定理）对偶问题的对偶是原问题.,根据这一定理，在一对对偶问题中，我们可以把其中任何一个称为原问题，则另一个就是其对偶
3、问题.,证明：,将问题(D)改写对称形式(D) ：,对于问题（D）,记对偶变量为XT， 则(D)的对偶规划为,这就是原问题(P),证毕.,定理2（弱对偶定理）,分别是问题(P)和(D)的可行解，,设,和,则必有,证明：,是问题(P)的可行解，故必有,是问题(D) 的可行解，故必有,左乘不等式（1）两边得,右乘不等式（2）两边得,由（3）和（4）式可知,证毕.,因,同理,由于,用,用,由弱对偶性，有下面推论：,注：推论2不存在逆.,推论1：若 X0 和Y0 分别是问题(P)和(D)的可行解，则 （1） CX0是问题(D)的目标函数的一个下界； （2） Y0 b是问题(P)的目标函数的一个上界。,
4、推论2：在一对对偶问题(P)和(D)中，若其中一个问题有可行解，但目标函数无界，则另一个问题无可行解.,推论3：在一对对偶问题(P)和(D)中，若其中一个问题有可行解，而另一个无可行解，则该问题无界.,例,已知原问题(LP)，,试估计它的目标函数值的界,并验证弱对偶定理.,解：,问题(LP)的对偶问题(DP)为,(DP),解：,由观察可知,分别是原问题和对偶问题的可行解。,，弱对偶定理成立。,且由推论1知，对偶问题目标函数W的下界为10，原问题目标函数Z的上界为40。,且原问题的目标函数值为,对偶问题的目标函数值为,故,例：利用对偶性质判断下面问题有无最优解,解：此问题的对偶问题为,定理3,(
5、最优性判别定理) 若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）的最优解。,例,在前面的例中，我们可以找到 X*=(0,0,4,4)T 是原问题的一个可行解，且 Z*= CX*=28， Y*=(1.2,0.2) 是对偶问题的一个可行解，且 W*= Y*b=28. 由于 CX*=Y*b， 故由定理3知X*,Y*分别是原问题和对偶问题的
6、最优解。,定理4,（对偶定理） 若一对对偶问题（P）和（D）一个有最 优解，则另一个也有最优解，且目标函 数的最优值必相等。,证明：,设线性规划问题(P)有最优解.,引入松弛变量 XS 将 (P) 化为标准形为,记,设 是线性规划问题(P)的一个最优解， 对应的基矩阵为B， 对应的基变量为xi1 , xi2 , , xit , xs1, xs2 , , xsr 对应的目标分量为 令 , 现证明其就是问题(D)的最优解. 非基变量x j 的检验数成立,一对对偶问题的关系，只能有下面三种情况之一： 1. 都有最优解； 2.一个问题无界，则另一个问题无可行解； 3. 两个都无可行解.,一对对偶问题解
7、的情况：,推论,问题(P)的最优解的单纯形表中检验数行对 应问题(D)的最优解。 更一般地，问题(P)基可行解的单纯形表中 检验数行对应问题(D)的一个基解.,注：,0,CN-CBB-1 N,-CBB-1,-Y,YS1,-YS2,例,定理5,设 X* 和Y* 分别是问题（P）和（D）的可行解，则它们分别是最优解的充要条件是 同时成立：,互补松弛定理,式（1）和（2）可以写成下面的等价形式,其中,证明：,在问题（P）和（D）中，分别引入松弛变量Xs=(xn+1, xn+2, xn+m)T和剩余变量Ys=(ym+1, ym+2, ym+n)T， 因为X*,Y*是可行解，则有 AX*+Xs*=b，X
8、*0，Xs*0; (3) Y*AYs*=C，Y*0，Ys*0; (4) 其中Xs*, Ys*表示对应于可行解X*和Y*的松弛变量和剩余变量Xs, Ys的值,用Y*左乘式（3）, 得Y*A X*+Y*Xs*= Y*b (5) 用X*右乘式（4）, 得Y*A X*Ys*X*= CX* (6) 又由于 CX*=Y*b ， 将上两式相减，得 Y*Xs*+Ys*X*=0,AX*+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)
9、 Y*A X*Ys*X*= CX* (6) 即得式（1）和（2）.,再证充分性， 若式（1）和（2）成立，,知，CX*=Y*b 。,再由定理3知， X*和Y*必分别是问题（P）和（D）的最优解。,互补松弛关系,在问题（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 . 这种关系称为互补松弛关系.,如果该约束在所有最优解上的值使左右取等号的一个约束称为紧约束。 即我们把严格
10、等式约束称为紧约束（或起作用约束）.,不是紧约束的约束称为松约束。 即把某一最优解处取严格不等式的约束称为松约束（或不起作用约束）。,对于最优解X*和Y*而言，松约束的对偶约束是紧约束.,以上关系称为对偶问题的互补松弛关系或松紧关系。在计算上，若已知一个问题的最优解，则可利用互补松弛条件求另一个问题的最优解.,紧约束与松约束,松紧关系,非常重要,例,试用对偶原理求解线性规划问题,已知其对偶规划的最优解为,掌握,解：,该问题的对偶规划为,利用松紧关系，,代入对偶规划的约束条件得下列约 束是松约束，,将最优解,松约束,紧约束,其对偶约束是紧约束,设原问题的最优解为,紧约束,对偶规划可以用线性规划的单纯形法求解。 由对偶原理可见，原问题与对偶问题之间有紧密联系，因此我们能够通过求解原问题来找出对偶问题的解，反之依然。 互补松弛条件就可以解决由原问题的最优解直接求出对偶问题的最优解。,注：对偶问题解的求法,判断下列说法是否正确？,如线性规划的原问题存在可行解，则其对偶问题也一定存在可行解； 如线性规划的对偶问题无可行解，则原问题也一定无可行解； 如线性规划的原问题和对偶问题都具有可行解，则该线性规划问题一定具有有限最优解。,作业：,已知线性规划问题,对偶变量 y1 y2,其对偶问题的最优解为y1*=4,y2*=1,试应用对偶问题的性质，求原问题的最优解。,