《對偶問題》PPT課件.ppt

《《對偶問題》PPT課件.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、某工廠用三臺設備生產(chǎn)兩種產(chǎn)品，已知的條件如表所示，試制訂總利潤最大的生產(chǎn)計劃設備I產(chǎn)品II產(chǎn)品總有效臺時A2212B128C039單位產(chǎn)品的利潤（千元）23求max引例1生產(chǎn)計劃問題換一角度：將設備賣出，售價定為多少適宜？原問題對偶問題兩個互為對偶規(guī)劃問題之間的關系（對稱形式）1）目標函數(shù)的目標互為相反。(max,min)2）目標函數(shù)的系數(shù)是另一個約束條件右端的向量3）約束系數(shù)矩陣是另一個的約束系數(shù)矩陣的轉置4）約束方程的個數(shù)與另一個的變量的個數(shù)相等max限定向量b價值向量Cm個約束，n個變量約束條件“≤”變

2、量“≥”原問題對偶問題min價值向量限定向量n個約束，m個變量變量“≥”約束條件“≥”對稱式對偶max限定向量b價值向量Cm個約束，n個變量約束條件“=”原問題對偶問題min價值向量限定向量n個約束，m個變量變量自由變量非對稱式對偶目標函數(shù)max原問題（對偶問題）對偶問題（原問題）目標函數(shù)min目標函數(shù)中變量的系數(shù)約束條件右端項約束條件右端項目標函數(shù)中變量的系數(shù)例2：給出下列線性規(guī)劃的對偶問題：minZ=2X1+8X2-4X3X1+3X2–3X3>=30-X1+5X2+4X3=80st.4X1+2X2-4X3<

3、=50X1<=0,X2>=0,X3無約束其對偶問題為：MAXw=30y1+80y2+50y3y1-y2+4y3〉=2st.3y1+5y2+2y3<=8-3y1+4y2-4y3=-4y1>=0,y2無約束，y3<=0一、對稱性定理對偶問題的對偶是原問題。2.3對偶問題基本性質二、弱對偶定理原問題對偶問題如果分別是（1）和（2）的可行解，則有。三、最優(yōu)性定理如果分別是(1)和(2)的可行解，且有，則分別是(1)和(2)的最優(yōu)解.四、強對偶定理原問題對偶問題五、無界性定理對于一對對偶問題，其中一個有有限最優(yōu)解，則另一

4、個也有最優(yōu)解，且兩個目標函數(shù)值相等。對于一對對偶問題，若一個有無界解，則另一個無可行解。例3已知原問題其對偶問題為：試估計它們的目標函數(shù)值的界，并驗證弱對偶定理的正確性。解:由觀察知和分別是原問題和對偶問題的可行解，，且原問題的目標函數(shù)值對偶問題的目標函數(shù)值故，弱對偶定理成立，并且我們知對偶問題的目標函數(shù)值原問題的目標函數(shù)值六、互補松弛性定理利用互補松弛定理,在已知一個問題的最優(yōu)解的情況下,可以不要列單純形表求出另一個的最優(yōu)解.例4：已知線性規(guī)劃問題要求：1）寫出對偶問題；2）已知原問題的最優(yōu)解為x1=-5,x

5、2=0,x3=-1;試根據(jù)對偶理論直接求出對偶問題最優(yōu)解。解：1）對偶問題2）由互補松弛定理，因原問題最優(yōu)解中x1=-5≠0,必使對偶問題第一個約束條件為等式，于是有，例5:已知下列線性規(guī)劃問題的對偶問題的最優(yōu)解為(6/5,1/5),求該線性規(guī)劃問題的最優(yōu)解.其對偶問題為：原問題的松弛變量為:X5,X6,對偶問題的剩余變量為:Y3,Y4,Y5,Y6,將(6/5,1/5)代入1)和2)知:Y3,Y4,均不為0,于是由松弛互補定理知:X1,X2,=0又由Y1>0,Y2>0和松弛互補定理知:X5,X6,=0從而,原問

6、題的約束變?yōu)?2X3+3X4=203X3+2X4=20解此方程得:X3=X4=4于是原問題的最優(yōu)解為:(0,0,4,4)七、單純形表的雙重含義例6：用單純形法，解線性規(guī)劃，（LP1）maxZ=2X1+X25X2<=156X1+2X2<=24st.X1+X2<=5X1>=0,X2>=0對偶問題為:（LP2）minW=15Y1+24Y2+5Y36Y2+Y3>=2ST.5Y1+2Y2+Y3>=1Y1>=0,Y2>=0基變量X1X2X3X4X5解X30015/4-15/215/2X11001/4-1/27/2X2010

7、-1/43/23/2-Z(目標)000-1/4-1/2-17/2檢驗數(shù)全部<0,于是得到最優(yōu)解為X=(7/2,3/2,15/2,0,0),最優(yōu)值為:Z=17/2,把松弛變量的檢驗數(shù)的相反數(shù)(0,1/4,1/2)帶入對偶問題中,看有什么規(guī)律?1、松弛變量與對偶變量的乘積有什么關系？松弛變量與對偶變量的乘積=02、對偶問題的最優(yōu)解與什么對應？對偶問題的最優(yōu)解是原問題松弛變量檢驗數(shù)的相反數(shù).結論：將原始單純形表中松弛變量的檢驗數(shù)反號恰好得對應對偶問題的一個解。事實上，我們把原始問題寫成（1）其對偶問題寫成（2）其中其

8、中決策變量和松弛變量，所對應的檢驗數(shù)分別為：和（不一定滿足“≤0”條件）。設為原始問題（1）的一個基本可行解（不一定為最優(yōu)解），它所對應的基矩陣為,令這時兩組檢驗數(shù)分別為：和再根據(jù)問題（2），這兩組檢驗數(shù)可分別記為上述對應關系如表2.在獲得最優(yōu)解之前，，及的各分量中至少有一大于零，即中至少有一個小于零。這時對應的對偶問題的解為非可行解。和即,重要結論：1.原始問題的單純形表中，原始問題