【正文】 ) 2 4 1 4 ∨ － 2 ( 1. 0. 0 ) 1 1 1 0 ∨ 3 ( 0. 1. 1 ) 1 5 ( 1. 0. 1 ) 0 2 1 1 ∨ 8 ( 1. 1. 0 ) 3 ( 1. 1. 1 ) 2 6 由上表可知，問題的最優(yōu)解為 X*=( x1 =1 x2=0 x3=1 ) 由上表可知： x1 =0 x2=0 x3=1 是一個可行解，為盡快找到最優(yōu)解，可將 3 x1－ 2 x2＋ 5 x3 ≥5 作為一個約束，凡是目標(biāo)函數(shù)值小于 5 的組合不必討論，如下表。但此法太繁瑣，工作量相當(dāng)大。這樣根據(jù)消防車 15分鐘趕到現(xiàn)場的限制，可得到如下模型 : 1 2 3 4 5 6121 2 6343454562m i n 1 1 1. . 1 1 Z x x x x x xxxx x xxxs t x x xx x xx? ? ? ? ? ?????????≥≥≥≥≥56 1 0 1 1 , , 6ixxxi??????????????≥取 或 ， 0－ 1 整數(shù)規(guī)劃是一種特殊形式的整數(shù)規(guī)劃，這時的決策變量 xi 只取兩個值 0或 1，一般的解法為隱枚舉法。 ? 請確定設(shè)站方案。條件： – 必須保證在城區(qū)任何地方發(fā)生火警時，消防車能在15分鐘之內(nèi)趕到現(xiàn)場。 – 學(xué)校、醫(yī)院、商業(yè)區(qū)、消防隊等公共設(shè)施的布點問題。 LP3 CB XB b x1 x2 x3 x4 x5 x8 3 x1 7/2 1 0 1/2 0 1/2 0 2 x2 2 0 1 0 0 1 0 0 x4 1 0 0 1 1 2 0 0 x8 4 1 0 0 0 0 1 Z 29/2 0 0 3/2 0 1/2 0 3 x1 7/2 1 0 1/2 0 1/2 0 2 x2 2 0 1 0 0 1 0 0 x4 1 0 0 1 1 2 0 0 x8 1/2 0 0 1/2 0 1/2 1 Z 29/2 0 0 3/2 0 1/2 0 3 x1 4 1 0 0 0 0 1 2 x2 1 0 1 1 0 0 2 0 x4 3 0 0 3 1 0 4 0 x5 1 0 0 1 0 1 2 Z 14 0 0 2 0 0 1 x1=4, x2=1 Z(4) =14 找到整數(shù)解，問題已探明，停止計算。即 x2+ x5= 2 , － x2+x6=－ 3 得下表 : 3 2 0 0 0 CB XB b x1 x2 x3 x4 x5 3 x1 13/4 1 0 3/4 1/4 0 2 x2 5/2 0 1 1/2 1/2 0 0 x5 2 0 1 0 0 1 Z 59/4 0 0 5/4 1/4 0 3 x1 13/4 1 0 3/4 1/4 0 2 x2 5/2 0 1 1/2 1/2 0 0 x5 1/2 0 0 1/2 1/2 1 Z 59/4 0 0 5/4 1/4 0 3 x1 7/2 1 0 1/2 0 1/2 2 x2 2 0 1 0 0 1 0 x4 1 0 0 1 1 2 Z 29/2 0 0 3/2 0 1/2 x1=7/2, x2=2 Z(1) =29/2= 繼續(xù)分枝，加入約束 3≥ x1 ≥4 LP1 3 2 0 0 0 CB XB b x1 x2 x3 x4 x6 3 x1 13/4 1 0 3/4 1/4 0 2 x2 5/2 0 1 1/2 1/2 0 0 x6 3 0 1 0 0 1 Z 59/4 0 0 5/4 1/4 0 3 x1 13/4 1 0 3/4 1/4 0 2 x2 5/2 0 1 1/2 1/2 0 0 x6 1/2 0 0 1/2 1/2 1 Z 59/4 0 0 5/4 1/4 0 3 x1 5/2 1 0 0 1/2 3/2 2 x2 3 0 1 0 0 1 0 x3 1 0 0 1 1 2 Z 27/2 0 0 0 3/2 5/2 LP2 x1=5/2, x2=3 Z(2) =27/2= ∵ Z(2) Z(1) ∴ 先不考慮分枝 接 (LP1)繼續(xù)分枝，加入約束 4 ≤ x1≤ 3， 有下式： ????????????????且為整數(shù)0,3 2 14329 2)3(23m a x2112212121xxxxxxxxIPxxZ????????????????且為整數(shù)0,4 2 14329 2)4(23m a x2112212121xxxxxxxxIPxxZ分別引入松弛變量 x7 和 x8 ，然后進行計算。 至此，原問題（ IP）的最優(yōu)解為： x1=2， x2 =3, Z* = Z(5) ＝－ 17 以上的求解過程可以用一個樹形圖表示如右： LP1 x1=1, x2=3 Z(1) ＝－ 16 LP x1=18/11, x2=40/11 Z(0) ＝－ LP2 x1=2, x2=10/3 Z(2) ＝－ LP3 x1=12/5, x2=3 Z(3) ＝－ LP4 無可 行解 LP5 x1=2, x2=3 Z(5) ＝－ 17 LP6 x1=3, x2=5/2 Z(6) ＝－ x1≤1 x1≥2 x2≤3 x2≥4 x1≤2 x1≥3 ＃ ＃ ＃ ＃ ?????????????且全為整數(shù)0,13651914m a x21212121xxxxxxxxZ練習(xí)：用分枝定界法求解整數(shù)規(guī)劃問題 （圖解法） JIXU LP1 x1=1, x2=7/3 Z(1) ＝ 10/3 LP x1=3/2, x2=10/3 Z(0) ＝ 29/6 LP2 x1=2, x2=23/9 Z(2) ＝ 41/9 x1≤1 x1≥2 LP5 x1=1, x2=2 Z(5) ＝ 3 LP6 無可 行解 ＃ ＃ x2≤2 x2≥3 LP3 x1=33/14, x2=2 Z(3) ＝ 61/14 LP4 無可 行解 x2≤2 x2≥3 ＃ LP7 x1=2, x2=2 Z(7) ＝ 4 LP8 x1=3, x2=1 Z(8) ＝ 4 x1≤2 x1≥3 ＃ ＃ LP1 x1=1, x2=7/3 Z(1) ＝ 10/3 LP x1=2/3, x2=10/3 Z(0) ＝ 29/6 LP2 x1=2, x2=23/9 Z(2) ＝ 41/9 LP3 x1=33/14, x2=2 Z(3) ＝ 61/14 LP4 無可 行解 LP7 x1=2, x2=2 Z(7) ＝ 4 LP8 x1=3, x2=1 Z(8) ＝ 4 x1≤1 x1≥2 x2≤2 x2≥3 x1≤2 x1≥3 ＃ ＃ ＃ ＃ ????????????且為整數(shù)0,143292)(23m a x21212121xxxxxxIPxxZ3 2 0 0 CB XB b x1 x2 x3 x4 0 x3 9 2 1 1 0 9/2 0 x4 14 2 3 0 1 14/2 Z 0 3 2 0 0 3 2 0 0 CB XB b x1 x2 x3 x4 3 x1 13/4 1 0 3/4 1/4 2 x2 5/2 0 1 1/2 1/2 Z 59/4 0 0 5/4 1/4 解 :用單純形法解對應(yīng)的 (LP)問題 ,如表所示 ,獲得最優(yōu)解。此時在 F點取得最優(yōu)解。 即 x1＝ 2, x2 =3, Z(5)＝－ 17 找到整數(shù)解，問題已探明，此枝停止計算。 x1 x2 ⑴ ⑵ 3 3 (18/11,40/11) ⑶ 1 1 B A C D 先求 （ LP5） ,如圖所示。 在 （ LP3）的基礎(chǔ)上繼續(xù)分枝。 D 求 （ LP4）， 如圖所示。 即 x1＝ 12/5≈, x2 =3, Z(3)＝ 87/5≈Z≈ 但 x1＝ 12/5不是整數(shù)，可繼續(xù)分枝。 x1 x2 ⑴ ⑵ 3 3 (18/11,40/11) ⑶ 1 1 B A C 先求 （ LP3） ,如圖所示。 即 x1＝ 2, x2 =10/3, Z(2) ＝－ 56/3≈－ ∵ Z2 Z1＝－ 16 ∴ 原問題有比（ － 16）更小的最優(yōu)解，但 x2 不是整數(shù)，故利用 3 ≥ 10/3≥4 加入條件。 1 1 同理求 （