最優(yōu)化方法之對偶理論講解-文庫吧資料
2025-06-22 18:36本頁面
【正文】 ? L P 對偶形式及定理? 對偶問題經(jīng)濟解釋? 對偶單純形法? 原 對偶算法對偶及鞍點問題Lagrange 對偶問題(1)定義 (1)的對偶問題 :(2)集約束Lagrange函數(shù)例：考慮線性規(guī)劃問題若取集合約束 D={x|x≥0}，則該線性規(guī)劃問題的 Lagrange函數(shù)為線性規(guī)劃的對偶問題為：求下列非線性規(guī)劃問題的對偶問題 :對偶問題為 :對偶定理定理 1(弱對偶定理 )推論 1:推論 2:推論 3:推論 4:對偶間隙：問題 ：LP 對偶問題的表達（ 1）對稱 LP問題的定義（ 2） 對稱 LP問題的對偶問題(P)(D)例：寫出下列 LP問題的對偶問題對偶例：寫出對偶問題 (D)的對偶變形(D)對偶變形結(jié)論 ：對偶問題 (D)的對偶 為原問題 (P) 。極小化問題的任何一個可行解所對應的目標函數(shù)值都是其對偶問題的目標函數(shù)值的上界。定理 2(最優(yōu)性準則 )證明：例定理 3(強對偶 定理 )若 (P),(D)均有可行解 ,則 (P),(D)均有最優(yōu)解 ,且 (P),(D)的最優(yōu)目標函數(shù)值相等 .證明：因為 (P),(D)均有可行解 ,由推論 2,推論 3知 ,(P)的目標函數(shù)值在其可行域內(nèi)有下界 , (D)的目標函數(shù)值在其可行域內(nèi)有上界 , 故則 (P),(D)均有最優(yōu)解 .引入剩余變量，把 (P)化為標準形 :推論 在用單純形法求解 LP問題（ P）的最優(yōu)單純形表中松弛變量的檢驗數(shù)的相反數(shù) (單純形乘子 w=(B1)TcB)就是其對偶問題（ D） 的最優(yōu)解 .由于 (P)化成標準形式時 ,松弛變量 xn+j 對應的列為 ej，它在目標函數(shù)中的價格系數(shù)＝０，所以，判別數(shù)為 (B1)TcB(ej)0=wj則松弛變量對應的判別數(shù)均乘以 (1)，便得到單純形乘子 w=(w1,…, wm). 當原問題達最優(yōu)時 ,單純形乘子即為對偶問題的最優(yōu)解 .解 ：化為標準形例 : 求下列問題之對偶問題的最優(yōu)解x1 x2 x3 x4 x5 1 2 1 0 04 0 0 1 00 4 0 0 12 3 0 0 0x3x4x58161201 0 1 0 1/24 0 0 1 00 1 0
教學教案相關推薦
鄂ICP備17016276號-1