[管理學]整數(shù)規(guī)劃(2)-在線瀏覽
2024-12-06 01:40本頁面
【正文】 是最優(yōu)解 （３）即使該方法結果可以得到最優(yōu)解，但如果有 n個決策變量，則取舍方案有 ２ n種。 所以，有必要討論整數(shù)規(guī)劃的求解方法。 如前例，增加約束 x1 ≤4，則 LP問題的最優(yōu)解，即為 x1=4,x2=1,Zmax=90， 就是 IP問題的解。 一般思想： ))(m a x()(m in xfxf sxsx ??松弛問題 的提出 考察這樣的問題 其中 S是有限集 設 A,B是兩個有限集，且 )2()(m i n)1()(m i n xfxf BxAx ??BA ?稱問題 (2)是問題 (1)的松弛問題 。那么求解方法呢？ 也許大家會認為，問題 (2)的搜索范圍大，所以 (2)的求 解更難一些，這看法似乎有道理，但實際并非如此 看一個生活中的例子： B — 全國 100m跑運動員全體 A — 全國 18歲的百米運動員全體 米成績表示具體運動員的 100)( Bxxf ?問題 (2) )(m in xfBx?很易解決，只需查一下全國記錄就 )(m in xfAx?知道了。 先假設對某個最優(yōu)化問題（ 1） (min)已找到一個容易解決的松弛問題 (2),設 x0是 (2)的最優(yōu)解，其最優(yōu)解 z0=f(x0). １、如果 則問題 (1)也解決了 ２、否則，至少可知問題 (1)的最優(yōu)值 z1一定 ≥了問題 (1)的一個下界 所以解決問題 (2)總是有好處的。如果最優(yōu)解不符合整數(shù)條件，則把相應線形規(guī)劃的可行域分割為若干子域，求出上、下界，不斷調整上下界，當它們相等時候，就得到相應的整數(shù)線形規(guī)劃最優(yōu)解。 例 在東區(qū)由 A1 ， A2 ， A3 三個點至多選擇兩個； 在西區(qū)由 A4 ， A5 兩個點中至少選一個； 在南區(qū)由 A6 ， A7 兩個點中至少選一個； 在北區(qū)由 A8 ， A9 ， A10 三個點中至少選兩個。但投資總額不能超過 720萬元，問應選擇哪幾個銷售點，可使年利潤為最大 ? A 1 A 2 A 3 A 4 A 5 A 6 A 7 A 8 A 9 A 10 投資額 100 120 150 80 70 90 80 140 160 180 利潤 36 40 50 22 20 30 25 48 58 61 解： 設： 01變量 xi = 1 (Ai 點被選用）或 0 (Ai 點沒被選用）。 資源 小號容器 中號容器 大號容器 金屬板（噸） 2 4 8 勞動力（人月） 2
教學課件相關推薦
鄂ICP備17016276號-1