整數(shù)規(guī)劃的難度遠大于一般線性規(guī)劃-預覽頁
【正文】 束條件 xk? ? bk ? 和 xk? ? bk ?+1，分別加于原松弛問題，形成兩個新的整數(shù)規(guī)劃 求解分枝的松弛問題 — 定界過程 – 設(shè)兩個分枝的松弛問題分別為問題 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)的一個為最優(yōu)解5 整數(shù)解，目標函數(shù)優(yōu)于問題 2非整數(shù)解 問題 1 的解即最優(yōu)解6 整數(shù)解 非整數(shù)解，目標函數(shù)優(yōu)于問題 1問題 1 停止分枝 ( 剪枝 ) ，其整數(shù)解為界，對問題 2 繼續(xù)分枝情況 2, 4, 5 找到最優(yōu)解 情況 3 在縮減的域上繼續(xù)分枝定界法 情況 6 問題 1 的整數(shù)解作為 界 被保留，用于以后與問題 2 的后續(xù)分枝所得到的整數(shù)解進行比較，結(jié)論如情況 4 4 分枝定界法舉例 例 ????????????且為整數(shù) 0,7 2134246)(max21212121xxxxxxxxxf解 ：松弛問題的最優(yōu)解為 x1=, x2=2, OBJ=23 由 x1= 得到兩個分枝如下： ???????????????且為整數(shù)問題 0,2 7 21342I46)(max211212121xxxxxxxxxxf???????????????且為整數(shù)問題 0,3 7 21342II46)(max211212121xxxxxxxxxxf5 表 分枝問題的松弛解 問題 I 問題 IIx 1 2 3x 2 9 / 4 1f ( x ) 21 22問題 II的解即原整數(shù)問題的最優(yōu)解 可能存在兩個分枝都是非整數(shù)解的情況，則需要兩邊同時繼續(xù)分枝，直到有整數(shù)解出現(xiàn)，就可以進行定界過程 當有很多變量有整數(shù)約束時，分枝即廣又深，在最壞情況下相當于組合所有可能的整數(shù)解 一般整數(shù)規(guī)劃問題屬于一類未解決的難題， NPplete，只有少數(shù)特殊問題有好的算法，如 任務(wù)分配問題 、 匹配問題 6 任務(wù)分配問題 例 有四個熟練工人，他們都是多面手，有四項任務(wù)要他們完成。 證明：略 清華算法的 基本思路 ： ? 根據(jù) 定理 1 變換效率矩陣，使矩陣中有足夠多的零。 打破僵
教學課件相關(guān)推薦
鄂ICP備17016276號-1