第四章整數規劃4.1整數規劃數學模型和解的特點

4.2分配問題4.3分枝定界法4.4割平面法4.5應用舉例1第四章整數規劃4.1整數規劃數學模型和解的特點14.3分支定界法分支定界法24.3分支定界法2原理：首先，不考慮變量的整數約束，求解松弛問題線性規劃的最優解。如果線性規劃的最優解恰好是整數解，則這個解就是整數規劃的最優解。如果線性規劃的最優解中至少有一個變量不是整數，把線性規劃的可行域切割成兩部分，分別求解兩個線性規劃的最優解。如果這兩個線性規劃的最優解還不是整數解，分別把每一個可行域再進行分割。這個過程，叫做“分支”。分支過程得到的整數解中，目標函數值最優的一個叫做整數規劃目標函數值的“界”。分支過程中非整數的線性規劃的最優解，如果目標函數值劣于或等于這個“界”，就停止繼續分支。這個過程，叫做“定界”。3原理：3步驟：解整數規劃問題（ILP）的松弛問題，結果可能有三種：松弛問題沒有可行解，ILP也沒有可行解，停止計算。松弛問題有最優解，并符合ILP的整數條件，則此最優解即為ILP的最優解，停止計算。松弛問題有最優解，但不符合ILP的整數條件，記它的目標函數值為；用觀察法找問題ILP的一個整數可行解，求得其目標函數值，并記作，以Z*表示ILP的最優目標函數值，則分支，如松弛問題有一個最優解xj為非整數值bj，則可以構造兩個分支。xj≤[bj]xj≥[bj]+1定界，以每個后繼問題為一分支表明求解的結果。4步驟：4【例1】用分枝定界法求解【解】先求對應的松弛問題（記為LP0）：

用圖解法得到最優解X＝（3.57,7.14）,Z0=35.7,如下圖所示。5【例1】用分枝定界法求解【解】先求對應的松弛問題（記為LP08.3310松弛問題LP0的最優解X=(3.57,7.14),Z0=35.7x1x2oABC1068.3310松弛問題LP0的最優解X=(3.57,7.14)1010x1x2oABCLP1LP234LP1:X=(3,7.6),Z1=34.8LP2:X=(4,6.5),Z2=35.5①②71010x1x2oABCLP1LP234LP1:X=(3,71010x1x2oABCLP1LP334LP3:X=(4.33,6),Z3=35.336①②LP1:X=(3,7.6),Z1=34.881010x1x2oABCLP1LP334LP3:X=(4.31010x1x2oACLP1346①②LP4:X=(4,6),Z4=34LP5:X=(5,5),Z5=355LP1:X=(3,7.6),Z1=34.8LP3LP591010x1x2oACLP1346①②LP4:X=(4,6)盡管LP1的解中x1不為整數，但Z5>Z因此LP5的最優解就是原整數規劃的最優解。上述分枝過程可用下圖表示LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6)Z1=34.8LP2:X=(4,6.5)Z2=35.5x1≤3x1≥4LP3:X=(4.33,6)Z3=35.33x2≤6LP4:X=(4,6)Z4=34LP5:X=(5,5)Z5=35x1≤4x1≥5無可行解x2≥710盡管LP1的解中x1不為整數，但Z5>Z因此(11/4,9/4),Z=31/4(3,3/2),Z=15/2(2,2),Z=6無解無解例2：(11/4,9/4)x1≤2x1≥3(2,2)(3,3/2)x2≤1x2≥2(19/6,1),Z=22/3(3,1),Z=7(19/6,1)x1≤3x1≥411(11/4,9/4),Z=31/4(3,3/2),Z=15/分支定界法的基本思想以求相應的線性規劃問題的最優解為出發點，如果得到的解不符合整數條件，就將原規劃問題分成幾支，每支增加了約束條件，即縮小了可行解區域，可行解范圍也隨之縮小了，因而整數規劃的最優值不會優于相應的線性規劃最優值。“定界”是指為目標函數定上下界，以便自動舍去那些最優值較差的子問題，提高計算效率。當整數規劃問題的最優目標函數值的上下界相等時，該整數規劃最優解已求出。12分支定界法的基本思想12分枝定界法的步驟：1.求整數規劃的松弛問題最優解；2.

若松弛問題的最優解滿足整數要求，得到整數規劃的最優解，否則轉下一步；3.任意選一個非整數解的變量xi，在松弛問題中加上約束xi≤[xi]及xi≥[xi]+1組成兩個新的松弛問題，稱為分枝。新的松弛問題具有特征：當原問題是求最大值時，目標值是分枝問題的上界；當原問題是求最小值時，目標值是分枝問題的下界；4.

檢查所有分枝的解及目標函數值，若某分枝的解是整數并且目標函數值大于（max）等于其它分枝的目