1、最優(yōu)化方法 Optimization第七講,第四章 對偶理論,窗含西嶺千秋雪， 門泊東吳萬里船。 -(唐)杜甫,對偶是一種普遍現(xiàn)象,主要內(nèi)容,對偶問題的形式普遍存在 L P 對偶形式及定理 對偶問題經(jīng)濟(jì)解釋 對偶單純形法 原-對偶算法,對偶及鞍點(diǎn)問題,Lagrange 對偶問題,(1),定義(1)的對偶問題:,(2),集約束,Lagrange函數(shù),例：考慮線性規(guī)劃問題,若取集合約束D=x|x0，則該 線性規(guī)劃問題的Lagrange函數(shù)為,線性規(guī)劃的對偶問題為：,求下列非線性規(guī)劃問題的對偶問題:,對偶問題為:,對偶定理,定理1(弱對偶定理),推論1:,推論2:,推論3:,推論4:,對偶間隙：,問

2、題：,LP 對偶問題的表達(dá),（1）對稱LP問題的定義,（2）對稱LP問題的對偶問題,(P),(D),例：寫出下列LP問題的對偶問題,對偶,例：寫出對偶問題(D)的對偶,變形,(D),對偶,變形,結(jié)論：對偶問題(D)的對偶 為原問題(P) 。,(DD),min變成max 價值系數(shù)與右端向量互換 系數(shù)矩陣轉(zhuǎn)置 變 原問題中約束條件的個數(shù)=對偶問題中變量的個數(shù) 原問題中變量的個數(shù)=對偶問題中約束條件的個數(shù),寫出對稱形式的對偶規(guī)劃的要點(diǎn),非對稱形式的對偶,對稱形式,對偶,(P),(D),例 min 5x1+4x2+3x3 s.t. x1+x2+x3=4 3x1+2x2+x3 =5 x1 0, x2 0

3、, x3 0 對偶問題為 max 4w1+5w2 s.t. w1+3w25 w1+2w2 4 w1+w2 3,一般情形LP問題的對偶問題,標(biāo)準(zhǔn)形,對偶,變量,約束,約束,變量,練習(xí)題,LP對偶問題的基本性質(zhì),原問題(P),對偶問題(D),定理1(弱對偶定理),例：,1）原問題(P1)一可行解 x=(1, 1)T,(P1),目標(biāo)值 =40,40是(D1)最優(yōu)目標(biāo)值的上界.,2）對偶問題(D1)一可行解 w=（1 1 1 1） 目標(biāo)值 =10 10是(P1)最優(yōu)目標(biāo)值的下界.,推論1,推論2,極大化問題的任何一個可行解所對應(yīng)的目標(biāo) 函數(shù)值都是其對偶問題的目標(biāo)函數(shù)值的下界。,極小化問題的任何一個可行

4、解所對應(yīng)的目標(biāo) 函數(shù)值都是其對偶問題的目標(biāo)函數(shù)值的上界。,推論3,若問題(P)或(D)有無界解，則其對偶問題(D)或(P)無可行解； 若問題(P)或(D)無可行解，則其對偶問題(D)或(P)或者無可行解,或者目標(biāo)函數(shù)值趨于無窮。,定理2(最優(yōu)性準(zhǔn)則),證明：,例,定理3(強(qiáng)對偶定理),若(P),(D)均有可行解,則(P),(D)均有最優(yōu)解,且(P),(D)的最優(yōu)目標(biāo)函數(shù)值相等.,證明：因?yàn)?P),(D)均有可行解,由推論2,推論3知,(P)的目標(biāo)函數(shù)值在其可行域內(nèi)有下界, (D)的目標(biāo)函數(shù)值在其可行域內(nèi)有上界, 故則(P),(D)均有最優(yōu)解.,引入剩余變量，把(P)化為標(biāo)準(zhǔn)形:,推論,在用單純

5、形法求解LP問題（P）的最優(yōu)單純 形表中松弛變量的檢驗(yàn)數(shù)的相反數(shù)(單純形 乘子w=(B-1)TcB)就是其對偶問題（D）的最優(yōu)解.,由于(P)化成標(biāo)準(zhǔn)形式時,松弛變量xn+j 對應(yīng)的列為-ej，它在目標(biāo)函數(shù)中的價格系數(shù)，所以，判別數(shù)為 (B-1)TcB(-ej)-0=-wj 則松弛變量對應(yīng)的判別數(shù)均乘以(-1)，便得到單純形乘子w=(w1,wm). 當(dāng)原問題達(dá)最優(yōu)時,單純形乘子即為對偶問題的最優(yōu)解.,解：化為標(biāo)準(zhǔn)形,例: 求下列問題之對偶問題的最優(yōu)解,4,1,2,此時達(dá)到最優(yōu)解。x*=(4,2), MaxZ=14。,(P),(D),小結(jié),原問題(min) 對應(yīng)關(guān)系 對偶問題(max),有最優(yōu)解

6、,有最優(yōu)解,無界解,不可行,不可行,無界解,（無可行解）,（無可行解）,（無界解）,（無可行解）,定理4（互補(bǔ)松馳定理）,證明：（必要性）,證明：（充分性）,定理4：互補(bǔ)松馳定理(非對稱形式）,例: 考慮下面問題,解:,1、定義,對偶問題的經(jīng)濟(jì)學(xué)解釋：影子價格(自學(xué)),2、含義,考慮在最優(yōu)解處,右端項(xiàng)bi的微小變動對目標(biāo)函數(shù)值的影響.,若把原問題的約束條件看成是廣義的資源約束,則右端項(xiàng)的值表示每種資源的可用量. 對偶解的經(jīng)濟(jì)含義:資源的單位改變量引起目標(biāo)函數(shù)值的增加量. 通常稱對偶解為影子價格. 影子價格的大小客觀地反映了資源在系統(tǒng)內(nèi)的稀缺程度.資源的影子價格越高,說明資源在系統(tǒng)內(nèi)越稀缺,而增

7、加該資源的供應(yīng)量對系統(tǒng)目標(biāo)函數(shù)值貢獻(xiàn)越大.,木門 木窗 木工 4小時 3小時 120小時/日 油漆工 2小時 1小時 50小時/日 收入 56 30 解：設(shè)該車間每日安排 x1 x2 x3 x4 生產(chǎn)木門x1扇，木窗x2 x3 4 3 1 0 120 max z=56 x1 +30 x2 x4 2 1 0 1 50 s.t. 4 x1 +3 x2120 -56 -30 0 0 0 2 x1 + x2 50 x3 0 1 1 -2 20 x1 x2 0 x1 1 1/2 0 1/2 25 0 -2 0 28 1400 x2 0 1 1 -2 20 x1 0 0 -1/2 -1/2 15 0 0

8、2 24 1440,對偶問題的解為: w*=(2, 24),（2）告訴管理者花多大代價購買進(jìn)資源或賣出資源是合適的,3、影子價格的作用,（1）告訴管理者增加何種資源對企業(yè)更有利,（3）為新產(chǎn)品定價提供依據(jù),對偶單純形法,定義：設(shè)x(0)是(P)的一個基本解（不一定是可行解），它對應(yīng)的矩陣為B，記w=cBB-1，若w是(P)的對偶問題的可行解，即對任意的j, wPj-cj 0，則稱x(0)為原問題的對偶可行的基解。 結(jié)論：當(dāng)對偶可行的基解是原問題的可行解時，由于判別數(shù)0，因此，它就是原問題的最優(yōu)解。,所以，x(0)為對偶可行的基解。,基本思想： 從原問題的一個對偶可行的基解出發(fā)； 求改進(jìn)的對偶可行的基解：每個對偶可行的基解x=(xBT,0)T對應(yīng)一個對偶問題的可行解w=cBB-1，相應(yīng)的對偶問題的目標(biāo)函數(shù)值為wb=cBB-1b，所謂改進(jìn)的對偶可行的基解，是指對于原問題的這個基解，相應(yīng)的對偶問題的目標(biāo)函數(shù)值wb有改進(jìn)（選擇離基變量和進(jìn)基變量，進(jìn)行主元消去）； 當(dāng)?shù)玫降膶ε伎尚械幕馐窃瓎栴}的可行解時，就達(dá)到最優(yōu)解。,與原單純形法的區(qū)別： 原單純形法保持原問題的可行性，對偶單純形法保持所有檢驗(yàn)數(shù)w