運(yùn)籌學(xué)課件第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析(參考版)
2025-05-18 22:15本頁面
【正文】 ? 對(duì)偶定理。約束條件為 ???????????????014223221212121yyyyyyy求解結(jié)果為 Y=(1,1)T Min W=26 運(yùn)籌學(xué)教程 ? 思考題 ? 如何理解對(duì)偶問題的基本性質(zhì)？ ? 討論題 ? 用例子說明互補(bǔ)松弛性的實(shí)際應(yīng)用。約束條件為 = x2=20。y20 6+2 2+0=10。 都有可行解 各自有上下界 都有最優(yōu)解 目標(biāo)函數(shù)值相等 證明要點(diǎn)： 1**Bz C B b Y b???運(yùn)籌學(xué)教程 定理 4 互補(bǔ)松弛性 在線性規(guī)劃問題的最優(yōu)解中，如果對(duì)應(yīng)某一約束條件的對(duì)偶變量值為非零，則該約束條件取嚴(yán)格等式；反之，如果約束條件取嚴(yán)格不等式，則其對(duì)應(yīng)的對(duì)偶變量一定為零。 X~X~X~Y~Y~Y~運(yùn)籌學(xué)教程 CX’=Y’ b CX*≤ Y*b 弱對(duì)偶 定 理 已 知 結(jié)論 Y*b≤Y ’ b 因?yàn)閄’Y’可行解 CX’ ≤ CX* 證明思路 設(shè) X*,Y*分別為原問題和對(duì)偶問題的最優(yōu)解 。 運(yùn)籌學(xué)教程 推論 3 原問題可行 ， 且目標(biāo)函數(shù)值無界 ==對(duì)偶問題不可行 對(duì)偶問題可行 ， 且目標(biāo)函數(shù)值無界==原問題不可行 若對(duì)偶問題不可行，其原問題 或 沒有可行解 或 無界解。 運(yùn)籌學(xué)教程 ?極大化問題有上界 —— 推論 1 對(duì)偶問題 (極小化問題 ) 的任意一個(gè)可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值是其原問題目標(biāo)函數(shù)值的一個(gè)上界。 X~ X~Y~ Y~證明思路： 由（ L） bXA ?~ 左乘 ，得 bYXAY ~~~ ?Y~由（ D） CAY ?~ 右乘 ，得 X~ XCXAY ~~~ ?bYXC ~~ ?運(yùn)籌學(xué)教程 該結(jié)論對(duì)非對(duì)稱形式的對(duì)偶問題同樣成立 。 j=1,2,…,n) 在一對(duì)變量中，其中一個(gè)大于 0，另一個(gè)一定等于 0 運(yùn)籌學(xué)教程 二 、 對(duì)偶問題的基本性質(zhì) 對(duì)偶基本性質(zhì)揭示 原問題的解與對(duì)偶問題的解之間關(guān)系 補(bǔ)充 :對(duì)稱性定理 對(duì)偶問題的對(duì)偶是原問題 。 189。 1/2 0 1/4 3/2 Cj+zj 0 0 0 188。 令 YT= CB B1 單純形乘子 ATY ≥ C T。 CB B1 ≤0。2211yyycyayayacyayayacyayayastybybybWyyyycyayayayacyayayayacyayayayacyayayayastybybybybW自由y2=y2’y2’’ y3=y3’ 非對(duì)稱形式的對(duì)偶關(guān)系： （ 1） 原問題 對(duì)偶問題 運(yùn)籌學(xué)教程 （ 2） 怎樣寫出非對(duì)稱形式的對(duì)偶問題 ？ 把一個(gè)等式約束寫成兩個(gè)不等式約束 ，再根據(jù)對(duì)稱形式的對(duì)偶關(guān)系定義寫出； 按照原 對(duì)偶表直接寫出 ； （ 3） 原 對(duì)偶表 運(yùn)籌學(xué)教程 項(xiàng)目 原問題 （對(duì)偶問題） 對(duì)偶問題 （原問題） 目標(biāo)函數(shù)類型 max min 目標(biāo)函數(shù)系數(shù)與右邊項(xiàng)的對(duì)應(yīng)關(guān)系 目標(biāo)函數(shù)各變量系數(shù)對(duì)應(yīng)約束條件右邊項(xiàng)的系數(shù) 右邊項(xiàng)的系數(shù)對(duì)應(yīng)目標(biāo)函數(shù)系數(shù) 變量個(gè)數(shù)與約束條件個(gè)數(shù)的對(duì)應(yīng)關(guān)系 變量個(gè)數(shù) n 約束條件個(gè)數(shù) m 約束條件個(gè)數(shù) n 變量個(gè)數(shù) m 原問題變量類型與對(duì)偶問題約束條件類型的對(duì)應(yīng)關(guān)系 ≥0 (對(duì)稱 ) 變量類型 ≤0 (非對(duì)稱 ) 自由 ≥(對(duì)稱 ) 約束條件類型 ≤ (非對(duì)稱 ) = 原問題約束條件類型與對(duì)偶問題變量類型的對(duì)應(yīng)關(guān)系 ≥ (非對(duì)稱 ) 約束條件類型 ≤ (對(duì)稱 ) = ≤ (非對(duì)稱 ) 變量類型 ≥ (對(duì)稱 ) 自由 運(yùn)籌學(xué)教程 例題：寫出下面線性規(guī)劃的對(duì)偶規(guī)劃： ????????????????????0,01413121110987654..32432121321321321xxxxxxxxxxxtsxxxM i n Z符號(hào)不限運(yùn)籌學(xué)教程 ?????????????????????0,0,31062139541284..1411732121321321321yyyyyyyyyyytsyyyM a x W符號(hào)不限 ?????????????????????0,0,31062139541284..1411732121321321321yyy
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1