022對偶原理課件

1、2.2 對偶原理對偶原理給出了原問題和對偶問題之間的重要關(guān)系.為了討論問題方便我們以“對稱型對偶問題”來進行研究和證明，當然所有這些結(jié)論對于其它形式的對偶問題也同樣成立。第1頁，共33頁。定理1（對稱性定理）對偶問題的對偶是原問題.定理2（弱對偶定理）分別是問題(P)和(D)的可行解，設和則必有注：推論2不存在逆.推論1：若 X0 和Y0 分別是問題(P)和(D)的可行解，則 （1） CX0是問題(D)的目標函數(shù)的一個下界；（2） Y0 b是問題(P)的目標函數(shù)的一個上界。推論2(無界性)：在一對對偶問題(P)和(D)中，若其中一個問題有可行解，但目標函數(shù)無界，則另一個問題無可行解.推論3：在

2、一對對偶問題(P)和(D)中，若其中一個問題有可行解，而另一個無可行解，則該問題無界. 第2頁，共33頁。定理4（對偶定理）若一對對偶問題（P）和（D）一個有最優(yōu)解，則另一個也有最優(yōu)解，且目標函數(shù)的最優(yōu)值必相等.定理5設 X* 和Y* 分別是問題（P）和（D）的可行解，則它們分別是最優(yōu)解的充要條件是 同時成立：（互補松弛定理）定理3(最優(yōu)性判別定理) 若X*和Y*分別是問題(P)和(D)的可行解，且CX*=Y*b，則X*，Y*分別是問題(P)和(D)的最優(yōu)解. 第3頁，共33頁。定理1（對稱性定理）對偶問題的對偶是原問題.根據(jù)這一定理，在一對對偶問題中，我們可以把其中任何一個稱為原問題，則另一

3、個就是其對偶問題.證明：將問題(D)改寫對稱形式(D) ：對于問題（D）記對偶變量為XT，則(D)的對偶規(guī)劃為這就是原問題(P),證畢.第4頁，共33頁。定理2（弱對偶定理）分別是問題(P)和(D)的可行解，設和則必有證明：是問題(P)的可行解，故必有是問題(D) 的可行解，故必有左乘不等式（1）兩邊得右乘不等式（2）兩邊得由（3）和（4）式可知證畢.因同理,由于用用第5頁，共33頁。由弱對偶性，有下面推論：注：推論2不存在逆.推論1：若 X0 和Y0 分別是問題(P)和(D)的可行解，則 （1） CX0是問題(D)的目標函數(shù)的一個下界；（2） Y0 b是問題(P)的目標函數(shù)的一個上界。推論2

4、：在一對對偶問題(P)和(D)中，若其中一個問題有可行解，但目標函數(shù)無界，則另一個問題無可行解.推論3：在一對對偶問題(P)和(D)中，若其中一個問題有可行解，而另一個無可行解，則該問題無界. 第6頁，共33頁。例已知原問題(LP)，試估計它的目標函數(shù)值的界,并驗證弱對偶定理.第7頁，共33頁。解：問題(LP)的對偶問題(DP)為 (DP)第8頁，共33頁。解：由觀察可知 分別是原問題和對偶問題的可行解。 ，弱對偶定理成立。且由推論1知，對偶問題目標函數(shù)W的下界為10，原問題目標函數(shù)Z的上界為40。且原問題的目標函數(shù)值為對偶問題的目標函數(shù)值為故第9頁，共33頁。例：利用對偶性質(zhì)判斷下面問題有無

5、最優(yōu)解第10頁，共33頁。解：此問題的對偶問題為而其對偶問題的第一個約束條件不能成立，因此對偶問題不可行。故由推論3知原問題無界。因是原問題的一個可行解。由觀察可知第11頁，共33頁。定理3(最優(yōu)性判別定理) 若X*和Y*分別是問題(P)和(D)的可行解，且CX*=Y*b，則X*，Y*分別是問題(P)和(D)的最優(yōu)解. 證明：對于問題（P）的任意一個可行解X ，必有CXY*b但 CX*=Y*b ，故對原問題（P）的所有可行解X，有CXCX*所以，X*為原問題（P）的最優(yōu)解。同理可證Y*是對偶問題（D）的最優(yōu)解。第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*分別是原問題和對偶問題的最優(yōu)解。第13頁，共33頁。定理4（對偶定理）若一對對偶問題（P）和（D）一個有最優(yōu)解，則另一個也有最優(yōu)解，且目標函數(shù)的最優(yōu)值必相等。證明：設線性規(guī)劃問題(P)有最優(yōu)解.引入松弛變量 XS 將 (P) 化為標準形為第14頁，共33頁。記設 是線性規(guī)劃問題(P)的一個最優(yōu)解，對應的基矩陣為B，對應的基變量為xi1 , xi2 , , xit , xs1, xs2 , , xsr對應的目標分量為令 , 現(xiàn)證明其就是問

7、題(D)的最優(yōu)解.非基變量x j 的檢驗數(shù)成立第15頁，共33頁。一對對偶問題的關(guān)系，只能有下面三種情況之一： 1. 都有最優(yōu)解； 2.一個問題無界，則另一個問題無可行解； 3. 兩個都無可行解.一對對偶問題解的情況：第16頁，共33頁。推論問題(P)的最優(yōu)解的單純形表中檢驗數(shù)行對應問題(D)的最優(yōu)解。更一般地，問題(P)基可行解的單純形表中檢驗數(shù)行對應問題(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）的可行解，則它們分別是最優(yōu)解的充要條件是 同時成立：互補松弛定理式（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）的最優(yōu)解。

11、第24頁，共33頁?；パa松弛關(guān)系在問題（P）和（D）的最優(yōu)解 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 .這種關(guān)系稱為互補松弛關(guān)系.第25頁，共33頁。如果該約束在所有最優(yōu)解上的值使左右取等號的一個約束稱為緊約束。 即我們把嚴格等式約束稱為緊約束（或起作用約束）. 不是緊約束的約束稱為松約束。 即把某一最優(yōu)解處取嚴格不等式的約束稱為松約束（或不起作用約束）。對于最優(yōu)解X*和Y*而言，松約束的對偶

12、約束是緊約束.以上關(guān)系稱為對偶問題的互補松弛關(guān)系或松緊關(guān)系。在計算上，若已知一個問題的最優(yōu)解，則可利用互補松弛條件求另一個問題的最優(yōu)解.緊約束與松約束松緊關(guān)系非常重要第26頁，共33頁。例試用對偶原理求解線性規(guī)劃問題已知其對偶規(guī)劃的最優(yōu)解為掌握第27頁，共33頁。解：該問題的對偶規(guī)劃為第28頁，共33頁。利用松緊關(guān)系，代入對偶規(guī)劃的約束條件得下列約束是松約束，將最優(yōu)解松約束緊約束其對偶約束是緊約束第29頁，共33頁。設原問題的最優(yōu)解為緊約束第30頁，共33頁。 對偶規(guī)劃可以用線性規(guī)劃的單純形法求解。由對偶原理可見，原問題與對偶問題之間有緊密聯(lián)系，因此我們能夠通過求解原問題來找出對偶問題的解，反之依然?；パa松弛條件就可以解決由原問題的最優(yōu)解直接求出對偶問題的最優(yōu)解。注：對偶問題解的求法第31頁，共3