最優(yōu)化方法之對偶理論講解(參考版)
2025-06-19 18:36本頁面
【正文】 ? 特點：先選擇出基變量，再選擇進(jìn)基變 量?；舅枷耄? 從原問題的一個對偶可行的基解出發(fā)；? 求改進(jìn)的對偶可行的基解：每個對偶可行的基解 x=(xBT,0)T對應(yīng)一個對偶問題的可行解 w=cBB1， 相應(yīng)的對偶問題的目標(biāo)函數(shù)值為 wb=cBB1b， 所謂改進(jìn)的對偶可行的基解，是指對于原問題的這個基解，相應(yīng)的對偶問題的目標(biāo)函數(shù)值wb有改進(jìn)（選擇離基變量和進(jìn)基變量，進(jìn)行 主元消去 ）；? 當(dāng)?shù)玫降膶ε伎尚械幕馐窃瓎栴}的可行解時，就達(dá)到最優(yōu)解。? 結(jié)論：當(dāng)對偶可行的基解是原問題的可行解時，由于判別數(shù) ≤0， 因此，它就是原問題的最優(yōu)解。 x*=(4,2), MaxZ=14。推論 3若問題 (P)或 (D)有無界解，則其對偶問題 (D)或 (P)無可行解； 若問題 (P)或 (D)無可行解，則其對偶問題 (D)或 (P)或者無可行解 ,或者目標(biāo)函數(shù)值趨于無窮。(DD)? min變成 max ? 價值系數(shù)與右端向量互換? 系數(shù)矩陣轉(zhuǎn)置? ≥ 變 ≤? 原問題中約束條件的個數(shù) =對偶問題中變量的個數(shù)? 原問題中變量的個數(shù) =對偶問題中約束條件的個數(shù)寫出對稱形式的對偶規(guī)劃的要點非對稱形式的對偶對稱形式對偶(P)(D)例 min 5x1+4x2+3x3 . x1+x2+x3=4 3x1+2x2+x3 =5 x1 ≥ 0, x2 ≥0, x3 ≥0 對偶問題為 max 4w1+5w2 . w1+3w2≤5 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)值 =4040是 (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ù)值的下界。最優(yōu)化方法 Optimization第七講第四章 對偶理論 窗含西嶺千秋雪，門泊東吳萬里船。 (唐 )杜甫 對偶是一種普遍現(xiàn)象主要內(nèi)容? 對偶問題的形式 — 普遍存在
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1