整數(shù)規(guī)劃的難度遠(yuǎn)大于一般線性規(guī)劃-免費(fèi)閱讀
【正文】 打破僵局 。整數(shù)規(guī)劃 整數(shù)規(guī)劃的難度遠(yuǎn)大于一般線性規(guī)劃 1 整數(shù)規(guī)劃簡介 ? 要求所有 xj 的解為整數(shù)，稱為純整數(shù)規(guī)劃 ? 要求部分 xj 的解為整數(shù)，稱為混合整數(shù)規(guī)劃 ? 對應(yīng)沒有整數(shù)解要求的線性規(guī)劃稱之為松弛問題 ? 整數(shù)規(guī)劃的解是可數(shù)個(gè)的，最優(yōu)解不一定發(fā)生在極點(diǎn) ? 整數(shù)規(guī)劃的最優(yōu)解不會(huì)優(yōu)于其松弛問題的最優(yōu)解 ????????????????njxmibxatsxcxfjnjijijnjjj,2,1,0,2,1,),(..)(max(m in)11??且為整數(shù)2 整數(shù)規(guī)劃的分枝定解法 思路與解題步驟 ? 只解松弛問題 在全部可行性域上解松弛問題 – 若松弛問題最優(yōu)解為整數(shù)解，則其也是整數(shù)規(guī)劃的最優(yōu)解 分枝過程 – 若松弛問題最優(yōu)解中某個(gè) xk=bk 不是整數(shù)，令 ? bk ? 為 bk 的整數(shù)部分 – 構(gòu)造兩個(gè)新的約束條件 xk? ? bk ? 和 xk? ? bk ?+1，分別加于原松弛問題，形成兩個(gè)新的整數(shù)規(guī)劃 求解分枝的松弛問題 — 定界過程 – 設(shè)兩個(gè)分枝的松弛問題分別為問題 1 和問題 2 ，它們的最優(yōu)解有如下情況 3 表 分枝問題解可能出現(xiàn)的情況 序號 問題 1 問題 2 說 明1 無可行解 無可行解 整數(shù)規(guī)劃無可行解2 無可行解 整數(shù)解 此整數(shù)解即最優(yōu)解3 無可行解 非整數(shù)解 對問題 2 繼續(xù)分枝4 整數(shù)解 整數(shù)解 較優(yōu)的一個(gè)為最優(yōu)解5 整數(shù)解，目標(biāo)函數(shù)優(yōu)于問題 2非整數(shù)解 問題 1 的解即最優(yōu)解6 整數(shù)解 非整數(shù)解，目標(biāo)函數(shù)優(yōu)于問題 1問題 1 停止分枝 ( 剪枝 ) ，其整數(shù)解為界，對問題 2 繼續(xù)分枝情況 2, 4, 5 找到最優(yōu)解 情況 3 在縮減的域上繼續(xù)分枝定界法 情況 6 問題 1 的整數(shù)解作為 界 被保留，用于以后與問題 2 的后續(xù)分枝所得到的整數(shù)解進(jìn)行比較，結(jié)論如情況 4 4 分枝定界法舉例 例 ????????????且為整數(shù) 0,7 2134246)(max21212121xxxxxxxxxf解 ：松弛問題的最優(yōu)解為 x1=, x2=2, OBJ=23 由 x1= 得到兩個(gè)分枝如下： ???????????????且為整數(shù)問題 0,2 7 21342I46)(max211212121xxxxxxxxxxf?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1