運(yùn)籌學(xué)課件第二章線性規(guī)劃的對偶理論與靈敏度分析(完整版)
【正文】 標(biāo)函數(shù)類型 max min 目標(biāo)函數(shù)系數(shù)與右邊項(xiàng)的對應(yīng)關(guān)系 目標(biāo)函數(shù)各變量系數(shù)對應(yīng)約束條件右邊項(xiàng)的系數(shù) 右邊項(xiàng)的系數(shù)對應(yīng)目標(biāo)函數(shù)系數(shù) 變量個數(shù)與約束條件個數(shù)的對應(yīng)關(guān)系 變量個數(shù) n 約束條件個數(shù) m 約束條件個數(shù) n 變量個數(shù) m 原問題變量類型與對偶問題約束條件類型的對應(yīng)關(guān)系 ≥0 (對稱 ) 變量類型 ≤0 (非對稱 ) 自由 ≥(對稱 ) 約束條件類型 ≤ (非對稱 ) = 原問題約束條件類型與對偶問題變量類型的對應(yīng)關(guān)系 ≥ (非對稱 ) 約束條件類型 ≤ (對稱 ) = ≤ (非對稱 ) 變量類型 ≥ (對稱 ) 自由 運(yùn)籌學(xué)教程 例題：寫出下面線性規(guī)劃的對偶規(guī)劃： ????????????????????0,01413121110987654..32432121321321321xxxxxxxxxxxtsxxxM i n Z符號不限運(yùn)籌學(xué)教程 ?????????????????????0,0,31062139541284..1411732121321321321yyyyyyyyyyytsyyyM a x W符號不限 ?????????????????????0,0,31062139541284..1411732121321321321yyyyyyyyyyytsyyyM a x W符號不限（ 原問題是極小化問題 ， 因此 應(yīng)從原 對偶表的 右邊 往 左邊 查 ！ ） √ ????????????????????0,01413121110987654..32432121321321321xxxxxxxxxxxtsxxxM i n Z符號不限項(xiàng)目 原問題 （對偶問題） 對偶問題 （原問題） 目標(biāo)函數(shù)類型 max min 原問題變量類型與對偶問題約束條件類型的對應(yīng)關(guān)系 ≥0 (對稱 ) 變量類型 ≤0 (非對稱 ) 自由 ≥(對稱 ) 約束條件類型 ≤ (非對稱 ) = 原問題約束條件類型與對偶問題變量類型的對應(yīng)關(guān)系 ≥ (非對稱 ) 約束條件類型 ≤ (對稱 ) = ≤ (非對稱 ) 變量類型 ≥ (對稱 ) 自由 運(yùn)籌學(xué)教程 第二節(jié) 對偶問題的基本性質(zhì) 原問題對偶問題為對稱形式的線性規(guī)劃問題 ??????????????njxmibxatsxcM a x Zjnjijijnjjj,2,10,2,1..11????????????????miynjcyatsybM i n Wimijiijmiii,2,10,2,1..11??，運(yùn)籌學(xué)教程 一、 單純形法的矩陣描述 進(jìn)一步討論修正單純形法 便于理論推導(dǎo) （ 如對偶定理的證明 ） 二 、 矩陣描述 關(guān)鍵 —— 寫出兩個基本的表達(dá)式 。 189。 運(yùn)籌學(xué)教程 推論 3 原問題可行 ， 且目標(biāo)函數(shù)值無界 ==對偶問題不可行 對偶問題可行 ， 且目標(biāo)函數(shù)值無界==原問題不可行 若對偶問題不可行，其原問題 或 沒有可行解 或 無界解。約束條件為 = x2=20。約束條件為 ???????????????014223221212121yyyyyyy求解結(jié)果為 Y=(1,1)T Min W=26 運(yùn)籌學(xué)教程 ? 思考題 ? 如何理解對偶問題的基本性質(zhì)？ ? 討論題 ? 用例子說明互補(bǔ)松弛性的實(shí)際應(yīng)用。 X~X~X~Y~Y~Y~運(yùn)籌學(xué)教程 CX’=Y’ b CX*≤ Y*b 弱對偶 定 理 已 知 結(jié)論 Y*b≤Y ’ b 因?yàn)閄’Y’可行解 CX’ ≤ CX* 證明思路 設(shè) X*,Y*分別為原問題和對偶問題的最優(yōu)解 。 j=1,2,…,n) 在一對變量中，其中一個大于 0，另一個一定等于 0 運(yùn)籌學(xué)教程 二 、 對偶問題的基本性質(zhì) 對偶基本性質(zhì)揭示 原問題的解與對
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1