系統(tǒng)工程---第四章整數(shù)規(guī)劃(已修改)
2024-10-30 18:55 本頁面
【正文】 一、 整數(shù)規(guī)劃簡介 ?整數(shù)規(guī)劃 是數(shù)學(xué)規(guī)劃的一個重要分支，它研究的是一類要求其部分或全部變量取整數(shù)的最優(yōu)化問題。 ?要求所有的解 xj 為整數(shù)，稱為 純整數(shù)規(guī)劃 ?要求部分的 xj 為整數(shù)，稱為 混合整數(shù)規(guī)劃 ?要求 xj 的取值只能是 0和 1 ， 稱為 01型整數(shù)規(guī)劃 ????????????????njxmibxatsxcxfjnjijijnjjj,2,1,0,2,1,),(..)(m a x ( m i n )11??且為整數(shù)整數(shù)規(guī)劃數(shù)學(xué)模型 第四章 整數(shù)規(guī)劃 ?對應(yīng)沒有整數(shù)解要求的線性規(guī)劃稱之為松弛問題 ?整數(shù)規(guī)劃的解是可數(shù)個的，最優(yōu)解不一定發(fā)生在極點 ?整數(shù)規(guī)劃的最優(yōu)解不會優(yōu)于其松弛問題的最優(yōu)解 ????????????????njxmibxaxcxfjnjijijnjjj,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ī)劃問題的重要方法。它既能解決純整數(shù)規(guī)劃問題，又能解決混合整數(shù)規(guī)劃問題。這種方法有很強的適應(yīng)能力，是目前較為成功的求解整數(shù)規(guī)劃問題的一種方法。 基本思想： 分枝定界法是通過有系統(tǒng)的“分枝”和“定界”步驟來尋求最優(yōu)解的。它是先求解松弛問題，如果其最優(yōu)解不符合整數(shù)條件，則求出整數(shù)規(guī)劃的上下界，用增加約束條件的方法把相應(yīng)的線性規(guī)劃的可行域分成子區(qū)域（稱為分枝），再求解這些子區(qū)域上的線性規(guī)劃問題，不斷縮小整數(shù)規(guī)劃的上下界距離，最后取得整數(shù)規(guī)劃的最優(yōu)解。 分枝定界法的解題步驟： Step1 求解松弛問題 B， 若松弛問題 B無解 ， 則整數(shù)規(guī)劃 A也無解 ,則停止 。 若 B有最優(yōu)解 ， 且符合問題 A的整數(shù)條件 ， 則 B的最優(yōu)解也是 A的最優(yōu)解 ， 則停止 。 若 B有最優(yōu)解 ， 但不符合 A的整數(shù)條件 ， 記其目標(biāo)函數(shù)值為 f1。 Step2 確定 A的最優(yōu)目標(biāo)函數(shù)值 f*的上下界 ， 其上界為 f1， 即 再用觀察法找到 A的一個整數(shù)可行解 ， 求其目標(biāo)函數(shù)值作為f*的下界 ， 記為 f， 這時有 Step3 判斷 是否等于 。 如果 ， 則 A的最優(yōu)解即為其目標(biāo)函數(shù)值等于 的那個整數(shù)可行解 。 否則 ， 進(jìn)行 Step4。 1ff ?fff ?? *f f ff ?fStep4 分枝 ， 在 B的最優(yōu)解中任選一個不符合整數(shù)條件的變量xj=bj， 以 [bj]表示小于 bj的最大整數(shù)。構(gòu)造兩個約束條件： xj≤ [bj] 和 xj ≥ [bj]+1 將這兩個約束條件分別加入問題 B， 得到 B的兩個分枝 B1和 B2。 Step5 求解分枝 B1, B2。 修改 A的最優(yōu)目標(biāo)函數(shù)值的上下界 。 在各分枝問題的最優(yōu)解中，找出最優(yōu)目標(biāo)函數(shù)值最大者作為新的上界。從已符合整數(shù)條件的各分枝中，找出目標(biāo)函數(shù)值最大者作為新的下界，這就是定界過程。 Step6 比較與剪枝。 各分枝的最優(yōu)目標(biāo)函數(shù)中若有小于 者，則剪掉這枝，即以后不再考慮了。若大于 ，且不符合整數(shù)條件，則重復(fù) Step4至 Step6,直至 ，求出整數(shù)最優(yōu)解為止。 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ù)分枝所得到的解進(jìn)行比較，結(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 x2121
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1