对偶理论讲义.pptVIP

3、最优性判别定理：若X*和Y*分别是P和D的可行解且CX*=Y*b，则X*.Y*分别是问题P和D的最优解。例如，在例1中，可找到X*=（0.0.4.4），Y*=（1.2，0.2）,则Z=28，W=28.故X*.Y*分别是P和D的最优解。第30页，共69页，星期日，2025年，2月5日4、对偶定理（强对偶性）：若一对对偶问题P和D都有可行解，则它们都有最优解，且目标函数的最优值必相等。推论⑷.若P和D的任意一个有最优解，则另一个也有最优解，且目标函数的最优值相等。综上所述，一对对偶问题的关系，只能有下面三种情况之一出现：①.都有最优解，分别设为X*和Y*，则必有CX*=Y*b；②.一个问题无界，则另一个问题无可行解；③.两个都无可行解。第31页，共69页，星期日，2025年，2月5日5、互补松弛定理：设X*和Y*分别是问题P和D的可行解，则它们分别是最优解的充要条件是同时成立一般而言，我们把某一可行点（如X*和Y*）处的严格不等式约束（包括对变量的非负约束）称为松约束，而把严格等式约束称为紧约束。所以有如下推论：设一对对偶问题都有可行解，若原问题的某一约束是某个最优解的松约束，则它的对偶约束一定是其对偶问题最优解的紧约束。第32页，共69页，星期日，2025年，2月5日例4、已知试通过求对偶问题的最优解来求解原问题的最优解。解：对偶问题为第33页，共69页，星期日，2025年，2月5日用图解法求出：Y*=（1.3），W=11。将y*1=1，y*2=3代入对偶约束条件，（1）（2）（5）式为紧约束，（3）（4）为松约束。令原问题的最优解为X*=（x1.x2.x3.x4.x5），则根据互补松弛条件，必有x3=x4=0(1.3)（1）（2）（3）（4）（5）第34页，共69页，星期日，2025年，2月5日又由于y*1＞0，y*2＞0，原问题的约束必为等式，即化简为此方程组为无穷多解令x5=0,得到x1=1，x2=2即X*1=（1.2.0.0.0）为原问题的一个最优解，Z=11。再令x5=2/3，得到x1=5/3，x2=0即X*2（5/3.0.0.0.2/3）也是原问题的一个最优解，Z=11。第35页，共69页，星期日，2025年，2月5日例5、已知原问题的最优解为X*=（0.0.4），Z=12试求对偶问题的最优解。解：（1）（2）（3）第36页，共69页，星期日，2025年，2月5日将X*=（0.0.4）代入原问题中，有下式：所以，根据互补松弛条件，必有y*1=y*2=0，代入对偶问题（3）式，y3=3。因此，对偶问题的最优解为Y*=（0.0.3），W=12。第37页，共69页，星期日，2025年，2月5日6、对偶问题的解利用原问题的最优单纯形表和改进单纯形表求解对偶问题的最优解。⑴.设原问题为：maxZ=CXAX≤bX≥0引入xs，构建初始基变量，然后，用单纯形法求解。当检验数满足σj≤0，则求得最优解。此时，xs对应的σjs为-Y*，故求对偶Y*，只要将最优单纯形表上xs对应的检验数反号即可。CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1Z－CBB-1b0CN－CBB-1N－CBB-1第38页，共69页，星期日，2025年，2月5日例一、第39页，共69页，星期日，2025年，2月5日cj1018000cBxBbx1x2x3x4x50x317052100170/20x410023010100/30x515015001150/5-Z01018000cj1018000cBxBbx1x2x3x4x50x3540/7001-23/711/710x150/71005/7-3/718x2200/7010-1/72/7-Z-4100/7000-32/7-6/7初始表最终表第40页，共69页，星期日，2025年，2月