整數(shù)規(guī)劃問題的求解

1、整數(shù)規(guī)劃問題的求解,整數(shù)規(guī)劃問題的求解方法：,分支定界法和割平面法 匈牙利法（指派問題）,分支定界法,1）求整數(shù)規(guī)劃的松弛問題最優(yōu)解；若松弛問題的最優(yōu)解滿足整數(shù)要求，得到整數(shù)規(guī)劃的最優(yōu)解,否則轉(zhuǎn)下一步；2）分支與定界：任意選一個非整數(shù)解的變量xi，在松弛問題中加上約束：xi≤[xi] 和 xi≥[xi]+1組成兩個新的松弛問題，稱為分枝。新的松弛問題具有特征：當(dāng)原問題是求最大值時，目標(biāo)值是分枝問題的上界；當(dāng)原問題

2、是求最小值時，目標(biāo)值是分枝問題的下界。檢查所有分枝的解及目標(biāo)函數(shù)值，若某分枝的解是整數(shù)并且目標(biāo)函數(shù)值大于（max）等于其它分枝的目標(biāo)值，則將其它分枝剪去不再計算，若還存在非整數(shù)解并且目標(biāo)值大于(max)整數(shù)解的目標(biāo)值，需要繼續(xù)分枝，再檢查，直到得到最優(yōu)解。,分支定界法的解題步驟：,分支定界法,例4.4 用分枝定界法求解整數(shù)規(guī)劃問題,解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問題(原整數(shù)規(guī)劃問題的松馳問題),LP,IP,分支定界法,用圖

3、解法求松弛問題的最優(yōu)解，如圖所示。,,,,,,,,,,,x1,x2,,⑴,⑵,,3,(18/11,40/11),,,,,,,,,,,,,,,,,,,,,,,,,,,⑶,2,1,1,2,3,x1＝18/11, x2 =40/11Z=－218/11≈(－19.8)即Z 也是IP最小值的下限。,對于x1＝18/11≈1.64，取值x1 ≤1， x1 ≥2對于x2 =40/11 ≈3.64，取值x2 ≤3 ，x2 ≥4先將（LP）劃分

4、為（LP1）和（LP2）,取x1 ≤1, x1 ≥2,分支定界法,分支：,分別求出（LP1）和（LP2）的最優(yōu)解。,分支定界法,先求LP1,如圖所示。此時在B點取得最優(yōu)解。x1＝1, x2 =3, Z(1)＝－16找到整數(shù)解，問題已探明，此枝停止計算。,,,,,,,,,,,,,,,,x1,x2,,⑴,⑵,,3,3,(18/11,40/11),,,,,,,,,,,,,,,,,,,,,,,,,⑶,1,1,,,,B,A,C,,,,,,,,

5、,,同理求LP2,如圖所示。在C 點取得最優(yōu)解。即:x1＝2, x2 =10/3, Z(2)＝－56/3≈－18.7 ∵Z(2)< Z(1)＝－16 ∴原問題有比－16更小的最優(yōu)解，但 x2 不是整數(shù)，故繼續(xù)分支。,分支定界法,在IP2中分別再加入條件： x2≤3, x2≥4 得下式兩支：,分別求出LP21和LP22的最優(yōu)解,分支定界法,,,,,,,,,,,,,x1,x2,,⑴,⑵,,3,3,(18/11,4

6、0/11),,,,,,,,,,,,,,,,,,,,,,,,,,,⑶,1,1,,,B,A,C,,,D,,,,先求LP21,如圖所示。此時D 在點取得最優(yōu)解。即 x1＝12/5≈2.4, x2 =3, Z(21)＝-87/5≈-17.4 < Z(1)=-16但x1＝12/5不是整數(shù)，可繼續(xù)分枝。即 3≤x1≤2。,求LP22，如圖所示。無可行解，故不再分枝。,分支定界法,在（LP21）的基礎(chǔ)上繼續(xù)分枝。加入條件3≤x1≤2有下式

7、：,分別求出（LP211）和（LP212）的最優(yōu)解,分支定界法,,,,,,,,,,,,,x1,x2,,⑴,⑵,,3,3,(18/11,40/11),,,,,,,,,,,,,,,,,,,,,,,,,,,⑶,1,1,,,B,A,C,,,D,,E,F,,,,先求（LP211）,如圖所示。此時 在E點取得最優(yōu)解。即 x1＝2, x2 =3, Z(211)＝－17找到整數(shù)解，問題已探明，此枝停止計算。,求（LP212），如圖所示。此時 F在點

8、取得最優(yōu)解。即x1＝3, x2 =2.5, Z(212)＝－31/2≈－15.5 > Z(211) 如對LP212繼續(xù)分解，其最小值也不會低于－15.5 ，問題探明,剪枝。,分支定界法,原整數(shù)規(guī)劃問題的最優(yōu)解為: x1=2, x2 =3, Z* =－17以上的求解過程可以用一個樹形圖表示如右：,LP1x1=1, x2=3Z(1) ＝－16,,LPx1=18/11, x2=40/11Z(0) ＝－19.8,,LP2

9、x1=2, x2=10/3Z(2) ＝－18.5,,LP21x1=12/5, x2=3Z(21) ＝－17.4,,LP22無可行解,,LP211x1=2, x2=3Z(211) ＝－17,,LP212x1=3, x2=5/2Z(212) ＝－15.5,,,,x1≤1,x1≥2,,,x2≤3,x2≥4,,,x1≤2,x1≥3,＃,＃,＃,＃,分支定界法,例4.5 用分枝定界法求解,解: 先求對應(yīng)的松弛問題（記為LP0

10、）,用圖解法得到最優(yōu)解X＝(3.57,7.14),Z0=35.7,如下圖所示。,分支定界法,,,,10,10,,,,,,松弛問題LP0的最優(yōu)解X=(3.57,7.14),Z0=35.7,,,,x1,x2,o,A,B,C,分支定界法,,,10,,,,,x2,o,A,B,C,,,LP1,LP2,3,4,LP1:X=(3,7.6),Z1=34.8,①,②,LP2:X=(4,6.5),Z2=35.5,分支定界法,,,,10,,,,x1,x2,o

11、,A,B,C,,LP1,LP21,3,4,LP21:X=(4.33,6),Z21=35.33,,6,,,,分支定界法,,,10,,,,x1,x2,o,A,C,,LP1,3,4,,6,,,,,LP211:X=(4,6),Z211=34,,,LP212:X=(5,5),Z212=35,5,LP212,分支定界法,上述分枝過程可用下圖表示：,LP0:X=(3.57,7.14),Z0=35.7,LP1:X=(3,7.6) Z

12、1=34.8,LP2:X=(4,6.5) Z2=35.5,,,x1≤3,x1≥4,LP21:X=(4.33,6) Z21=35.33,,x2≤6,,LP211:X=(4,6) Z211=34,LP212:X=(5,5) Z212=35,,x1≤4,x1≥5,LP22無可行解,x2≥7,,小結(jié),學(xué)習(xí)要點： 掌握一般整數(shù)規(guī)劃問題概念及模型結(jié)構(gòu) 掌握分支定界法原理