系統(tǒng)工程---第四章整數(shù)規(guī)劃-展示頁
2024-10-27 18:55本頁面
【正文】 njjj,2,1,0,2,1,),()(m a x ( m i n )11??且為整數(shù) ????????????????njxmibxaxcxfjnjijijnjjj,2,1,0,2,1,),()(m a x ( m i n )11??整數(shù)規(guī)劃問題 A 其松弛問題 B 二、整數(shù)規(guī)劃的解法 分枝定界法 是一種計算與分析判斷相結(jié)合的求解整數(shù)規(guī)劃問題的重要方法。這種方法有很強的適應(yīng)能力，是目前較為成功的求解整數(shù)規(guī)劃問題的一種方法。它是先求解松弛問題，如果其最優(yōu)解不符合整數(shù)條件，則求出整數(shù)規(guī)劃的上下界，用增加約束條件的方法把相應(yīng)的線性規(guī)劃的可行域分成子區(qū)域（稱為分枝），再求解這些子區(qū)域上的線性規(guī)劃問題，不斷縮小整數(shù)規(guī)劃的上下界距離，最后取得整數(shù)規(guī)劃的最優(yōu)解。 若 B有最優(yōu)解 ， 且符合問題 A的整數(shù)條件 ， 則 B的最優(yōu)解也是 A的最優(yōu)解 ， 則停止 。 Step2 確定 A的最優(yōu)目標(biāo)函數(shù)值 f*的上下界 ， 其上界為 f1， 即 再用觀察法找到 A的一個整數(shù)可行解 ， 求其目標(biāo)函數(shù)值作為f*的下界 ， 記為 f， 這時有 Step3 判斷 是否等于 。 否則 ， 進行 Step4。構(gòu)造兩個約束條件： xj≤ [bj] 和 xj ≥ [bj]+1 將這兩個約束條件分別加入問題 B， 得到 B的兩個分枝 B1和 B2。 修改 A的最優(yōu)目標(biāo)函數(shù)值的上下界 。從已符合整數(shù)條件的各分枝中，找出目標(biāo)函數(shù)值最大者作為新的下界，這就是定界過程。 各分枝的最優(yōu)目標(biāo)函數(shù)中若有小于 者，則剪掉這枝，即以后不再考慮了。 ffff ?*各分枝問題的解可能出現(xiàn)的情況 序號 問題 B 1 問題 B 2 說 明 1 無可行解 無可行解 整數(shù)規(guī)劃無可行解 2 無可行解 整數(shù)解 此整數(shù)解即最優(yōu)解 3 無可行解 非整數(shù)解 對問題 B 2 繼續(xù)分枝 4 整數(shù)解 整數(shù)解 較優(yōu)的一個為最優(yōu)解 5 整數(shù)解，目標(biāo)函數(shù)優(yōu)于問題 B 2 非整數(shù)解 問題 B 1 的解即最優(yōu)解 6 整數(shù)解 非整數(shù)解，目標(biāo)函數(shù)優(yōu)于問題 B 1 問題 B 1 停止分枝 ( 剪枝 ) ，其整數(shù)解為界，對問題 B 2 繼續(xù)分枝 ? 情況 2, 4, 5 找到最優(yōu)解 ? 情況 3 在縮減的域上繼續(xù)分枝定界法 ? 情況 6 問題 1 的整數(shù)解作為界被保留，用于以后與問題 2 的后續(xù)分枝所得到的解進行比較，結(jié)論如情況 4或 5 例 1 ????????????且為整數(shù) 0,7 2134246m a x21212121xxxxxxxxf解：松弛問題 B的最優(yōu)解為 x1= , x2=2 , f =23 ??????????????? 0,2 7 2134246m a x2112121121xxxxxxxBxxf問題??????????????? 0,3 7 2134246m a x2112121221xxxxxxxBxxf問題分枝定界法舉例 問題 A ???????????? 0,7 2134246m a x21212121xxxxxxxxf松弛問題 B 由 x1= 得到兩個分枝如下： 顯然 x1=1 , x2=1是問題 A的可行解，其目標(biāo)函數(shù)值為 10 于是有 10≤f *≤23 求解兩個分枝問題 問題 B 1 問題 B 2 x 1 =2 x 1 =3 x 2 = 2 . 2 5 x 2 =1 f 1 = 2 1 f 2 = 2 2 問題 B2的解即為原整數(shù)規(guī)劃問題 A的最優(yōu)解 ? 可能存在兩個分枝都是非整數(shù)解的情況，則需要兩邊同時繼續(xù)分枝，直到有整數(shù)解出現(xiàn)，就可以進行定界過程 ? 當(dāng)有很多變量有整數(shù)約束時，分枝既廣又深，在最壞情況下相當(dāng)于組合所有可能的整數(shù)解 松弛問題 B x1= x2=2 f=23 問題 B1 x1=2 x2= f1=21 問題 B2 x1=3 x2=1 f2=22 x1≤2 x1≥3 10≤f *≤23 22≤f *≤23 例 2 ????????????且為整數(shù) 0,16 2 329544050m a x21212121xxxxxxxxf解：松弛問題 B的最優(yōu)解為 x1= , x2= , f = ??????????????? 0,3 16 2 329544050m a x2122121121xxxxxxxBxxf問題??????????????? 0,4 16 2 329544050m a x2122121221xxxxxxxBxxf問題分枝定界法舉例 問題 A * ?? f由 x2= 得到兩個分枝如下： x1=1 , x2=1 顯然是問題 A的一個可行解 , 其目標(biāo)函數(shù)值為 90 , 這時有
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1