對偶理論ppt課件-文庫吧資料
2025-05-05 00:32本頁面
【正文】 數(shù) wPjcj ≤0， 即保持對偶問題的可行性。45所以， x(0)為對偶可行的基本解。 x3 4 3 1 0 120? max z=56 x1 +30 x2 x4 2 1 0 1 50? . 4 x1 +3 x2≤120 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 2 24 1440對偶問題的解為 :w*=(2, 24)43 （ 2）告訴管理者花多大代價購買進(jìn)資源或賣出資源是合適的 影子價格的作用（ 1）告訴管理者增加何種資源對企業(yè)更有利 （ 3） 為新產(chǎn)品定價提供依據(jù)44對偶單純形法?定義：設(shè) x(0)是 (L)的一個基本解（不一定是可行解），它對應(yīng)的矩陣為 B， 記w=cBB1，若 w是 (L)的對偶問題的可行解，即對任意的 j, wPjcj ≤0， 則稱 x(0)為原問題的 對偶可行的基本解 。 x*=(4,2), MaxZ=14。極小化問題的任何一個可行解所對應(yīng)的目標(biāo)函數(shù)值都是其對偶問題的目標(biāo)函數(shù)值的上界。(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
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1