對偶理論ppt課件(已修改)
2025-05-11 00:32 本頁面
【正文】 第四章 對偶原理窗含西嶺千秋雪，門泊東吳萬里船對偶是一種普遍現(xiàn)象1x1x2x3y1 y2 y3 y4甲 乙 丙 丁材料產(chǎn)品３?。病。薄。保础。薄。场。玻病。病。场。碅BC每臺收益202240003000限額 600 400 200 300假設(shè)工廠考慮不進行生產(chǎn)而把全部可利用的資源都讓給其他企業(yè)，工廠希望給這些資源定出一個合理的價格，即使別的單位愿意購買，又使本工廠能得到生產(chǎn)這些產(chǎn)品所能獲得的最大收益。 2二、對偶問題的表達（ 1）對稱 LP問題的定義（ 2） 對稱 LP問題的對偶問題第一類對稱形式 第二類對稱形式(L)(D)3例 1：寫出下列 LP問題的對偶問題對偶4（ 3）對偶問題的對偶推導(dǎo)過程變形(D)5對偶變形結(jié)論：對偶問題的對偶為原問題。(DD)6寫出下列 LP問題的對偶問題：例 2：7?寫出對稱形式的對偶規(guī)劃的要點：?(1) min變成 max?(2) 價值系數(shù)與右端向量互換?(3) 系數(shù)矩陣轉(zhuǎn)置?(4) ≥ 變 ≤?原問題中約束條件的個數(shù) =對偶問題中變量的個數(shù)?原問題中變量的個數(shù) =對偶問題中約束條件的個數(shù)8非對稱形式的對偶寫成對稱形式對偶問題為：9? 例 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 ≤ 310一般情形 LP問題的對偶問題? min cx? . A1x ≥b1 A1 為 m1n , b1為 m11? A2x =b2 A2 為 m2n , b2為 m21? A3x ≤ b3 A3 為 m3n , b3為 m31? x ≥0? 引入松弛 變 量? min cx? . A1x –xs =b1 xs為 m11? A2x =b2 ? A3x +xt = b3 xt為 m31? x, xs , xt ≥011? min cx? . A1x –xs =b1 xs為 m11? A2x =b2 ? A3x +xt = b3 xt為 m31? x, xs , xt ≥0? 對 偶 問題為? max w1b1+ w2b2 + w3b3? . w1A1+ w2A2 + w3A3 ≤c? – w1Is ≤0? w3It ≤0? ? max w1b1+ w2b2 + w3b3? . w1A1+ w2A2 + w3A3 ≤c? w1 ≥ 0, w3 ≤012? min max? 變 ≥0 ≤ 約? 量 ≤0 ≥ 束? 無限制 = 方? 程? 約 ≥ ≥0 ? 束 ≤ ≤0 變? 方 = 無限制
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1