1、數學建模培訓數學建模培訓 整數規劃整數規劃專題專題吳穎丹吳穎丹整數規劃的模型整數規劃的模型分支定界法分支定界法割平面法割平面法0 01 1 整數規劃整數規劃指派問題指派問題例一、合理下料問題例一、合理下料問題設用某型號的圓鋼下零件設用某型號的圓鋼下零件A A1 1, , A A2 2, ,A,Am m 的毛坯。在一根的毛坯。在一根圓鋼上下料的方式有圓鋼上下料的方式有B B1 1,B,B2 2, , B Bn n 種，每種下料方式可以得種，每種下料方式可以得到各種零件的毛坯數以及每種零件的需要量，如表所示。怎到各種零件的毛坯數以及每種零件的需要量，如表所示。怎樣安排下料方式，使得即滿足需要，所用

2、的原材料又最少？樣安排下料方式，使得即滿足需要，所用的原材料又最少？零件 方 個數 式零件零 件毛坯數nBB 1mAA 1mbb 1mnmnaaaa 1111 設：設：xj 表示用表示用Bj (j=1.2n) 種方式下料根數種方式下料根數 模型：模型：且為整數n)1.2(j 0)2 . 1( min11jnjijijnjjxmibxaxZ例三、機床分配問題例三、機床分配問題設有設有m臺同類機床，要加工臺同類機床，要加工n種種零件。已知各種零件的加工時間分零件。已知各種零件的加工時間分別為別為a1,a2,an ，問如何分配，使各，問如何分配，使各機床的總加工任務相等，或者說盡機床的總加工任務相等

3、，或者說盡可能平衡。可能平衡。設：設： 1 分配第分配第i臺機床加工第臺機床加工第j種零件；種零件； xij （i=1,2,m;j=1,2,n） 0 相反。相反。于是，第于是，第i臺機床加工各種零件的總時間為：臺機床加工各種零件的總時間為：njijjmixa1)2 . 1( 因此，求因此，求xij ，使得，使得n)1.2jm,1.2(i 1 0n)1.2(j 1),max(min111121或ijmiijnjnjnjmjjjjjjxxxaxaxaZ又由于一個零件只能在一臺機床上加工，所以有又由于一個零件只能在一臺機床上加工，所以有miijmix1)2 . 1( 1整數規劃一般形式整數規劃一般形

4、式依照決策變量取整要求的不同，整數規劃可分為依照決策變量取整要求的不同，整數規劃可分為純整數規劃、全整數規劃、混合整數規劃、純整數規劃、全整數規劃、混合整數規劃、01整數整數規劃。規劃。 n)1.2(j 0)2 . 1( )min(max11jnjijijnjjjxmibxaxcZZ 或部分或者全部為整數部分或者全部為整數純整數規劃：所有決策變量要求取非負整數純整數規劃：所有決策變量要求取非負整數（這時引進的松弛變量和剩余變量可以不要求（這時引進的松弛變量和剩余變量可以不要求取整數）。取整數）。全整數規劃：除所有決策變量要求取非負整數全整數規劃：除所有決策變量要求取非負整數外，系數外，系數ai

5、j和常數和常數bi也要求取整數（這時引進也要求取整數（這時引進的松弛變量和剩余變量也必須是整數）。的松弛變量和剩余變量也必須是整數）。混合整數規劃：只有一部分的決策變量要求取混合整數規劃：只有一部分的決策變量要求取非負整數，另一部分可以取非負實數。非負整數，另一部分可以取非負實數。 01整數規劃：所有決策變量只能取整數規劃：所有決策變量只能取 0 或或 1 兩兩個整數。個整數。從數學模型上看整數規劃似乎是線性規劃從數學模型上看整數規劃似乎是線性規劃的一種特殊形式，求解只需在線性規劃的基礎的一種特殊形式，求解只需在線性規劃的基礎上，通過舍入取整，尋求滿足整數要求的解即上，通過舍入取整，尋求滿足整

6、數要求的解即可。但實際上兩者卻有很大的不同，通過舍入可。但實際上兩者卻有很大的不同，通過舍入得到的解（整數）也不一定就是最優解，有時得到的解（整數）也不一定就是最優解，有時甚至不能保證所得倒的解是整數可行解。甚至不能保證所得倒的解是整數可行解。例：設整數規劃問題如下例：設整數規劃問題如下 首先不考慮整數約束，得到線性規劃問題（一般首先不考慮整數約束，得到線性規劃問題（一般稱為松弛問題）。稱為松弛問題）。0,13651914max21212121xxxxxxxxZ0,13651914max21212121xxxxxxxxZ且為整數 用圖解法求出最優解用圖解法求出最優解x x1 13/2, 3/2

7、, x x2 2 = 10/3 = 10/3且有且有Z = 29/6Z = 29/6x1x233(3/2,10/3)現 求 整 數 解 （ 最 優現 求 整 數 解 （ 最 優解）：如用解）：如用“舍入取整法舍入取整法”可得到可得到4個點即個點即(1，3), (2，3),(1，4),(2，4)。顯然，。顯然，它們都不可能是整數規劃它們都不可能是整數規劃的最優解。的最優解。按整數規劃約束條件，其可行解肯定在線性規劃問題的可按整數規劃約束條件，其可行解肯定在線性規劃問題的可行域內且為整數點。故整數規劃問題的可行解集是一個有限集，行域內且為整數點。故整數規劃問題的可行解集是一個有限集，如圖所示。如圖

8、所示。因此，可將集合內的整數點一一找出，其最因此，可將集合內的整數點一一找出，其最大目標函數的值為最優解，此法為大目標函數的值為最優解，此法為完全枚舉法完全枚舉法。如上例：其中（如上例：其中（2 2，2 2）（）（3 3，1 1）點為最大值，）點為最大值，Z=4Z=4。目前，常用的求解整數規劃的方法有：目前，常用的求解整數規劃的方法有：分支定界法和割平面法；分支定界法和割平面法；對于特別的對于特別的0 01 1規劃問題采用隱枚舉法和匈規劃問題采用隱枚舉法和匈牙利法。牙利法。且為整數且為整數)2 . 1( , 0)2 . 1( )(max11mjxmibxaIPxcZjnjijijnjjj考慮純

9、整數問題：考慮純整數問題：)2 . 1( , 0)2 . 1( )(max11mjxmibxaLPxcZjnjijijnjjj整數問題的松弛問題：整數問題的松弛問題：1、先不考慮整數約束，解、先不考慮整數約束，解( IP )的松弛問題的松弛問題( LP )，可，可能得到以下情況之一：能得到以下情況之一： .若若( LP )沒有可行解，則沒有可行解，則( IP )也沒有可行解，停也沒有可行解，停止計算。止計算。 .若若( LP )有最優解，并符合有最優解，并符合( IP )的整數條件，則的整數條件，則( LP )的最優解即為的最優解即為( IP )的最優解，停止計算。的最優解，停止計算。 .若若

10、( LP )有最優解，但不符合有最優解，但不符合( IP )的整數條件，的整數條件，轉入下一步。為討論方便，設轉入下一步。為討論方便，設( LP )的最優解為：的最優解為： 不不全全為為整整數數其其中中目目標標函函數數最最優優值值為為), 2 , 1(.Z)0 , 0 ,( (0)21)0(mibbbbbXiTmr 2、定界：、定界： 記記( IP )的目標函數最優值為的目標函數最優值為Z* ,以以Z(0) 作為作為Z* 的上的上界，記為界，記為 Z(0) 。再用觀察法找的一個整數可行解。再用觀察法找的一個整數可行解 X，并以其相應的目標函數值，并以其相應的目標函數值 Z作為作為Z* 的下界，

11、記的下界，記為為Z Z，也可以令，也可以令Z，則有，則有: Z Z* ZZ 3、分枝：、分枝： 在在( LP )的最優解的最優解 X(0)中，任選一個不符合整數條中，任選一個不符合整數條件的變量，例如件的變量，例如xr=br （不為整數），以（不為整數），以br 表示不表示不超過超過br 的最大整數。構造兩個約束條件的最大整數。構造兩個約束條件 xr br 和和xr br 1 將這兩個約束條件分別加入問題將這兩個約束條件分別加入問題( IP ) ，形成兩個，形成兩個子問題子問題( IP1)和和( IP2 ) ，再解這兩個問題的松弛問題，再解這兩個問題的松弛問題( LP1)和和( LP2) 。4

12、、修改上、下界：按照以下兩點規則進行。、修改上、下界：按照以下兩點規則進行。.在各分枝問題中，找出目標函數值最大者作為在各分枝問題中，找出目標函數值最大者作為新的上界；新的上界；.從已符合整數條件的分枝中，找出目標函數值從已符合整數條件的分枝中，找出目標函數值最大者作為新的下界。最大者作為新的下界。5、比較與剪枝、比較與剪枝 ：各分枝的目標函數值中，若有小于各分枝的目標函數值中，若有小于Z 者，則剪掉此者，則剪掉此枝，表明此子問題已經探清，不必再分枝了枝，表明此子問題已經探清，不必再分枝了;否則繼續否則繼續分枝。分枝。如此反復進行，直到得到如此反復進行，直到得到ZZ* 為止，即得最優解為止，即

13、得最優解 X* 。Z 為了更好地說明用分枝定界法求整數規劃最優解的過程，為了更好地說明用分枝定界法求整數規劃最優解的過程，我們選擇只有兩個變量的引例我們選擇只有兩個變量的引例3.2.1 進行求解。進行求解。 例例3.3.1 用分枝定界法求解整數規劃問題用分枝定界法求解整數規劃問題 (P)：max Z = 15x1 20 x2 s.t. 6x1 4x2 25 x1 3x2 10 xi 0, 1, 2, 解：解：1. 求解如下的松弛問題求解如下的松弛問題 (P0)： (P0)：max Z = 15x1 20 x2 s.t. 6x1 4x2 25 x1 3x2 10 xi 0，i = 1, 2得最優

14、解得最優解 x1 = 2.5，x2 = 2.5，最優值，最優值 z = 87.5。由于原。由于原問題問題 (P) 目標函數的系數為整數，目標函數的系數為整數，xi 0, 1, 2, ，故，故 z* 87，即最優值的上界，即最優值的上界 = 87。令最優值的下界。令最優值的下界 z = 0，則有，則有 z = 0 z* 87 = 。我們將這些結果記錄。我們將這些結果記錄在樹形圖圖在樹形圖圖 3.3.3 中。中。 zz 2. 因為此時兩個變量都不是整數，我們從中選擇一個變量因為此時兩個變量都不是整數，我們從中選擇一個變量進行分枝。假定選擇進行分枝。假定選擇 x1，在，在 (P0) 的約束之外，增加

15、兩個互相排的約束之外，增加兩個互相排斥的約束條件：斥的約束條件：x1 2 與與 x1 3，形成兩個子模型，形成兩個子模型 (P1) 和和 (P2)： (P1)：max Z = 15x1 20 x2 (P2)：max Z = 15x1 20 x2 s.t. 6x1 4x2 25 s.t. 6x1 4x2 25 x1 3x2 10 x1 3x2 10 x1 2 x1 3 xi 0，i = 1, 2 xi 0，i = 1, 2此時，模型此時，模型 (P0) 的可行域被分成兩個相應的子域的可行域被分成兩個相應的子域 R1 和和 R2，如圖，如圖 3.3.2 所示。所示。顯然，被拋去的非陰影區域內（顯然

16、，被拋去的非陰影區域內（2 x1 z =75，所以，在所以，在 (P2) 的約束之外，增加兩個互相排斥的約束的約束之外，增加兩個互相排斥的約束條件：條件：x2 1 與與 x2 2，形成兩個子模型，形成兩個子模型 (P5) 和和 (P6)： (P5)：max Z = 15x1 20 x2 (P6)：max Z = 15x1 20 x2 s.t. 6x1 4x2 25 s.t. 6x1 4x2 25 x1 3x2 10 x1 3x2 10 x1 3 x1 3 x2 1 x2 2 xi 0，i = 1, 2 xi 0，i = 1, 2 7. 對子模型對子模型 (P5) 進行求解，得最優解為進行求解，

17、得最優解為 x1 = 3.5，x2 = 1，最優值最優值 z = 72.5。由于最優值。由于最優值 z = 72.5 75 = z，故不再分枝。因，故不再分枝。因為分枝后，新模型的最優值不可能超過當前新的下界。為分枝后，新模型的最優值不可能超過當前新的下界。 8. 對子模型對子模型 (P6) 進行求解，因為無可行解，故不再分枝。進行求解，因為無可行解，故不再分枝。 至此，已將所有分枝的子模型求解完畢，當前新的下界值至此，已將所有分枝的子模型求解完畢，當前新的下界值相應的解，是現行最好的整數可行解，也就是原整數規劃問題相應的解，是現行最好的整數可行解，也就是原整數規劃問題的最優解：的最優解：x1

18、* = 1，x2* = 3。最優目標函數值。最優目標函數值 z = 75。 z z 注：圖注：圖 3.3.3 中的子模型中的子模型 (P3)、(P4)、(P5) 不再不再分枝，并不是說它們分枝后不可以找到新的整數可分枝，并不是說它們分枝后不可以找到新的整數可行解，而是表明：即使找出新的整數可行解也不會行解，而是表明：即使找出新的整數可行解也不會優于目前最好的整數可行解，其目標函數值不會大優于目前最好的整數可行解，其目標函數值不會大于目前的下界值，這些可行解已被全部隱含枚舉了。于目前的下界值，這些可行解已被全部隱含枚舉了。實質上，分枝定界法是一種隱枚舉法（實質上，分枝定界法是一種隱枚舉法（Imp

19、licit Enumeration）。）。 提示：用分枝定界法求解整數規劃問題，其計提示：用分枝定界法求解整數規劃問題，其計算量一般比較大，所以此法只能求解規模不太大的算量一般比較大，所以此法只能求解規模不太大的整數規劃問題。對于規模較大的整數規劃問題，可整數規劃問題。對于規模較大的整數規劃問題，可以采取以采取啟發式算法，例如遺傳算法來求解啟發式算法，例如遺傳算法來求解。 例二：用分枝定界法求解整數規劃問題例二：用分枝定界法求解整數規劃問題且全為整數0,4 30 652 5min211212121xxxxxxxxxZ記為（記為（IP）解：首先去掉整數約束，變成一般線性規劃問題解：首先去掉整數約

20、束，變成一般線性規劃問題0,4 30 652 5min211212121xxxxxxxxxZ記為（記為（LP）用圖解法求（用圖解法求（LP）的最）的最優解，如圖所示。優解，如圖所示。x1x233(18/11,40/11)對于對于x118/111.64， 取值取值x1 1， x1 2對于對于x2 =40/11 3.64，取值取值x2 3 ，x2 4先將（先將（LP）劃分為（）劃分為（LP1）和（）和（LP2）,取取x1 1, x1 2 x118/11, x2 =40/11 Z(0) =218/11(19.8)即即Z 是（是（IP）最小值的下限。）最小值的下限。有下式：有下式：且且為為整整數數0,

21、1 4 30 652 )1(5min2111212121xxxxxxxxIPxxZ且且為為整整數數0,2 4 30 652 )2(5min2111212121xxxxxxxxIPxxZ 現在只要求出（現在只要求出（LP1）和（）和（LP2）的最優解即可。）的最優解即可。x1x233(18/11,40/11) 先求（先求（LP1）,如圖所示。如圖所示。此時此時B 在點取得最優解。在點取得最優解。x11, x2 =3, Z(1)16找到整數解，問題已探明，找到整數解，問題已探明，此枝停止計算。此枝停止計算。11同理求（同理求（LP2） ,如圖所示。如圖所示。在在C 點取得最優解。點取得最優解。即即

22、x12, x2 =10/3, Z(2) 56/318.7 Z2 Z116 原問題有比（原問題有比（16）更小的最優解，但更小的最優解，但 x2 不是整數，利用不是整數，利用 3 10/34 加入條件。加入條件。BAC加入條件：加入條件： x23, x24 有下式：有下式：且且為為整整數數0,3 2 4 30 652 )3(5min21211212121xxxxxxxxxIPxxZ且且為為整整數數0,4 2 4 30 652 )4(5min21211212121xxxxxxxxxIPxxZ只要求出（只要求出（LP3）和（）和（LP4）的最優解即可。）的最優解即可。x1x233(18/11,40/

23、11)11BAC先求（先求（LP3）,如圖所示。此如圖所示。此時時D 在點取得最優解。在點取得最優解。即即 x112/52.4, x2 =3, Z(3)-87/5-17.4 Z(5) F如對如對 Z(6) 繼續分解，其最小值也不會低于繼續分解，其最小值也不會低于15.5 ，問題探明問題探明,剪枝。剪枝。 至此，原問題至此，原問題（IP）的最優解）的最優解為：為： x1=2， x2 =3, Z* = Z(5) 17以上的求解過程以上的求解過程可以用一個樹形可以用一個樹形圖表示如右：圖表示如右：LP1x1=1, x2=3Z(1) 16LPx1=18/11, x2=40/11Z(0) 19.8LP2

24、x1=2, x2=10/3Z(2) 18.5LP3x1=12/5, x2=3Z(3) 17.4LP4無可無可行解行解LP5x1=2, x2=3Z(5) 17LP6x1=3, x2=5/2Z(6) 15.5x11x12x23x24x12x13（一）、計算步驟：（一）、計算步驟：1、用單純形法求解、用單純形法求解( IP )對應的松弛問題對應的松弛問題( LP )： .若若( LP )沒有可行解，則沒有可行解，則( IP )也沒有可行解，也沒有可行解，停止計算。停止計算。 .若若( LP )有最優解，并符合有最優解，并符合( IP )的整數條件，的整數條件，則則( LP )的最優解即為的最優解即為

25、( IP )的最優解，停止計算。的最優解，停止計算。 .若若( LP )有最優解，但不符合有最優解，但不符合( IP )的整數條件，的整數條件，轉入下一步。轉入下一步。 2、從、從(LP)的最優解中，任選一個不為整數的分量的最優解中，任選一個不為整數的分量xr,將最將最優單純形表中該行的系數優單純形表中該行的系數 和和 分解為整數部分和小數部分分解為整數部分和小數部分之和，并以該行為源行，按下式作割平面方程：之和，并以該行為源行，按下式作割平面方程：rjarbnmjjrjrxff10 3、將所得的割平面方程作為一個新的約束條件置于最優單純、將所得的割平面方程作為一個新的約束條件置于最優單純形表

26、中（同時增加一個單位列向量），用對偶單純形法求出新形表中（同時增加一個單位列向量），用對偶單純形法求出新的最優解，返回的最優解，返回1。的小數部分的小數部分的小數部分的小數部分rjarb例一：用割平面法求解整數規劃問題例一：用割平面法求解整數規劃問題且為整數0,023623 max2121212xxxxxxxZ解：增加松弛變量解：增加松弛變量x3和和x4 ，得到，得到( (LP)的初始單純形表的初始單純形表和最優單純形表：和最優單純形表：Cj0100CBXBbx1x2x3x40 x3632100 x40-3201Z00100Cj0100CBXBbx1x2x3x40 x11101/6-1/61x

27、23/2011/41/4Z-3/2 00 -1/4 -1/4 此題的最優解為：此題的最優解為：X*= (1 , 3/2) Z = 3/2 但不是整數最但不是整數最優解，引入割平面。以優解，引入割平面。以x2 為源行生成割平面，由于為源行生成割平面，由于 1/4=0+1/4, 3/2=1+1/2, 我們已將所需要的數分解為整數和分我們已將所需要的數分解為整數和分數，所以，生成割平面的條件為數，所以，生成割平面的條件為: 21414143xx也即：也即：)4141(2112114141234141432432432xxxxxxxxx0)4141(21 43xx將將 x3=6-3x1-2x2 , x

28、4=3x1-2x2 ,帶入帶入21414143xxx1x233第一個割平面第一個割平面得到等價的割平面條件：得到等價的割平面條件： x2 1,見下圖。見下圖。Cj01000CBXBbx1x2x3x4s10 x11101/6-1/601x23/2011/41/400s1-1/200-1/4-1/41Z-3/200-1/4-1/40現將生成的割平面條件加入松弛變量，然后加到表中：現將生成的割平面條件加入松弛變量，然后加到表中：214141143 sxxCBXBbx1x2X3X4s10 x12/3100-1/32/31x21010010 x320011-4Z-10000-1 此時，此時，X1 (2/

29、3, 1), Z=1,仍不是整數解。繼續以仍不是整數解。繼續以x1為源行為源行生成割平面，其條件為：生成割平面，其條件為：32323214sx 用上表的約束解出用上表的約束解出x4 和和s1 ，將它們帶入上式得到等價的，將它們帶入上式得到等價的割平面條件：割平面條件：x1 x2 ，見圖：，見圖：x1x233第一個割平面第一個割平面第二個割平面第二個割平面將生成的割平面條件加入松弛變量，然后加到表中：將生成的割平面條件加入松弛變量，然后加到表中：323232214 ssxCBXBbx1x2x3x4s1s20 x12/3100-1/32/301x210100100 x320011-400s2-2/

30、3000-2/3-2/31Z-10000-10CBXBbx1x2x3x4s1s20 x10100-1011x20010-103/20 x3600150-60s1100011-3/2Z000010-3/2CBXBbx1x2x3x4s1s20 x1110001-1/21x210100100 x310010-53/20 x4100011-3/2Z-10000-10 至此得到最優表，其最優解為至此得到最優表，其最優解為 X= (1 , 1) , Z = 1, 這也這也是原問題的最優解。是原問題的最優解。 有以上解題過程可見，表中含有分數元素且算法過程有以上解題過程可見，表中含有分數元素且算法過程中始終

31、保持對偶可行性，因此，這個算法也稱為分數對中始終保持對偶可行性，因此，這個算法也稱為分數對偶割平面算法。偶割平面算法。0-1變量及其應用：0-1變量可表示邏輯關系：x=1: 采取方案。x=0:不采取方案。若需要從p個約束條件中，恰好選擇q個，則可引入p個0-1變量：njijijpibxa1),.,2 , 1(yi=0:選擇i個約束條件。yi=1:不選擇i個約束條件那么，約束條件組為：Mi是充分大的數njiiijijpiMybxa1),.,2 , 1(piiqpy1n個變量有2n種組合，采用隱枚舉法。列出2n種組合，先求出一個可行解，計算目標函數值，作為當前的最優解。對于其它組合，先計算目標函數

32、值，若不如當前的最優解，就不必檢驗它的可行性。否則，如果是可行解，則把更新為當前的最優解。采用分支定界法，搜索更快。 01 整數規劃是一種特殊形式的整數規劃，這整數規劃是一種特殊形式的整數規劃，這時的決策變量時的決策變量xi 只取兩個值只取兩個值0或或1，一般的解法為，一般的解法為隱枚舉法。隱枚舉法。例一、求解下列例一、求解下列01 規劃問題規劃問題10,(4) 64 (3) 3 (2) 44(1) 22523max3213221321321321或xxxxxxxxxxxxxxxxZ 解：對于解：對于0 01 1 規劃問題，由于每個變量只取規劃問題，由于每個變量只取0 0，1 1兩個值，一般會

33、用兩個值，一般會用窮舉法來解，即將所有的窮舉法來解，即將所有的0 0，1 1 組合找出，使目標函數達到極值要求就組合找出，使目標函數達到極值要求就可求得最優解。但此法太繁瑣，工作量相當大。而隱枚舉法就是在此基可求得最優解。但此法太繁瑣，工作量相當大。而隱枚舉法就是在此基礎上，通過加入一定的條件，就能較快的求得最優解。礎上，通過加入一定的條件，就能較快的求得最優解。x1 . x2. x3約束條件約束條件滿足條件滿足條件Z 值值 (1) (2) (3) (4)是是 否否( 0. 0. 0 ) 0 0 0 00( 0. 0. 1 ) 1 1 0 15( 0. 1. 0 ) 2 4 1 42( 1.

34、0. 0 ) 1 1 1 03( 0. 1. 1 ) 1 5( 1. 0. 1 ) 0 2 1 18( 1. 1. 0 ) 3( 1. 1. 1 ) 2 6由上表可知，問題的最優解為由上表可知，問題的最優解為 X*=( x1 =1 x2=0 x3=1 )由上表可知：由上表可知： x1 =0 x2=0 x3=1 是一個可行解，為盡快找到最優解，可是一個可行解，為盡快找到最優解，可將將3 x12 x25 x3 5 作為一個約束，凡是目標函數值小于作為一個約束，凡是目標函數值小于5 的組合不必的組合不必討論，如下表。討論，如下表。x1 . x2. x3約束條件約束條件滿足條件滿足條件Z 值值(0)

35、(1) (2) (3) (4)是是 否否( 0. 0. 0 ) 0 0 0 0 00( 0. 0. 1 ) 5 1 1 0 15( 0. 1. 0 )-2( 0. 1. 1 ) 3( 1. 0. 0 ) 3( 1. 0. 1 ) 8 0 2 1 18( 1. 1. 0 ) 1( 1. 1. 1 ) 4 指派問題的數學模型指派問題的數學模型設設n 個人被分配去做個人被分配去做n 件工作，已知第件工作，已知第i 個人去做第個人去做第j 件件工作的的效率為工作的的效率為Cij(i=1.2n;j=1.2n)并假設并假設Cij 0。問應如。問應如何分配才能使總效率（何分配才能使總效率（ 時間或費用）最高

36、？時間或費用）最高？設決策變量設決策變量 1 分配第分配第i 個人去做第個人去做第j 件工作件工作 xij = 0 相反相反 ( I,j=1.2. n ) ).2.1,1(0).2.1( 1).2.1( 1min1111njixnjxnixxcZijniijnjijninjijij或解題步驟：解題步驟：第一步：變換指派問題的系數矩陣（第一步：變換指派問題的系數矩陣（cij）為）為(bij)，使在，使在(bij)的各行各列中都出現的各行各列中都出現0元素，即元素，即(1) 從（從（cij）的每行元素都減去該行的最小元素；）的每行元素都減去該行的最小元素；(2)再從所得新系數矩陣的每列元素中減去該

37、列的再從所得新系數矩陣的每列元素中減去該列的最小元素。最小元素。第二步：進行試指派，以尋求最優解。第二步：進行試指派，以尋求最優解。 在在(bij)中找盡可能多的獨立中找盡可能多的獨立0元素，若能找出元素，若能找出n個個獨立獨立0元素，就以這元素，就以這n個獨立個獨立0元素對應解矩陣元素對應解矩陣(xij)中的中的元素為元素為1，其余為，其余為0，這就得到最優解。找獨立，這就得到最優解。找獨立0元素，元素，常用的步驟為：常用的步驟為： (1)從只有一個從只有一個0元素的行元素的行(列列)開始，給這個開始，給這個0元素加圈，記作元素加圈，記作 。然后劃去然后劃去 所在列所在列(行行)的其它的其它

38、0元素，記作元素，記作 ；這表示這列所代表的任；這表示這列所代表的任務已指派完，不必再考慮別人了。務已指派完，不必再考慮別人了。(2)給只有一個給只有一個0元素的列元素的列(行行)中的中的0元素加圈，記作；然后劃去元素加圈，記作；然后劃去 所在行的所在行的0元素，記作元素，記作 (3)反復進行反復進行(1)，(2)兩步，直到盡可能多的兩步，直到盡可能多的0元素都被圈出和劃掉元素都被圈出和劃掉為止。為止。(4)若仍有沒有劃圈的若仍有沒有劃圈的0元素，且同行元素，且同行(列列)的的0元素至少有兩個，則從元素至少有兩個，則從剩有剩有0元素最少的行元素最少的行(列列)開始，比較這行各開始，比較這行各0

39、元素所在列中元素所在列中0元素的數目，元素的數目，選擇選擇0元素少的那列的這個元素少的那列的這個0元素加圈元素加圈(表示選擇性多的要表示選擇性多的要“禮讓禮讓”選擇選擇性少的性少的)。然后劃掉同行同列的其它。然后劃掉同行同列的其它0元素。可反復進行，直到所有元素。可反復進行，直到所有0元元素都已圈出和劃掉為止。素都已圈出和劃掉為止。 （5）若）若 元素的數目元素的數目m 等于矩陣的階數等于矩陣的階數n，那么這指派問題的最，那么這指派問題的最優解已得到。若優解已得到。若m n, 則轉入下一步。則轉入下一步。第三步：作最少的直線覆蓋所有第三步：作最少的直線覆蓋所有0元素。元素。(1)對沒有的行打對

40、沒有的行打號；號；(2)對已打對已打號的行中所有含號的行中所有含元素的列打元素的列打號；號；(3)再對打有再對打有號的列中含號的列中含 元素的行打元素的行打號；號；(4)重復重復(2)，(3)直到得不出新的打直到得不出新的打號的行、列為止；號的行、列為止；(5)對沒有打對沒有打號的行畫橫線，有打號的行畫橫線，有打號的列畫縱線，這就號的列畫縱線，這就得到覆蓋所有得到覆蓋所有0元素的最少直線數元素的最少直線數 l 。l 應等于應等于m，若不，若不相等，說明試指派過程有誤，回到第二步相等，說明試指派過程有誤，回到第二步(4)，另行試，另行試指派；若指派；若 lm n，須再變換當前的系數矩陣，以找，須

41、再變換當前的系數矩陣，以找到到n個獨立的個獨立的0元素，為此轉第四步。元素，為此轉第四步。第四步：變換矩陣第四步：變換矩陣( (b bijij) )以增加以增加0 0元素。元素。在沒有被直線覆蓋的所有元素中找出最小元素，然后打在沒有被直線覆蓋的所有元素中找出最小元素，然后打各行都減去這最小元素；打各行都減去這最小元素；打各列都加上這最小元素各列都加上這最小元素（以保證系數矩陣中不出現負元素）。新系數矩陣的最（以保證系數矩陣中不出現負元素）。新系數矩陣的最優解和原問題仍相同。轉回第二步。優解和原問題仍相同。轉回第二步。 任務任務人員人員ABCD甲甲215134乙乙1041415丙丙9141613

42、丁丁78119 9118713161491514410413152 241047501110062111302497 00102350960607130 2410475011100621113042 00102350960607130 0100000100101000有一份中文說明書，需譯成英、日、德、俄四種文有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作字，分別記作A A、B B、C C、D D。現有甲、乙、丙、丁四人，他。現有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時間如下表所們將中文說明書譯成不同語種的說明書所需時間如下表所示，問如何分派任務，可使總時間最少

43、？示，問如何分派任務，可使總時間最少？ 任務任務人員人員ABCD甲甲67112乙乙4598丙丙31104丁丁5982求解過程如下：求解過程如下：第一步，變換系數矩陣：第一步，變換系數矩陣：2142 289541013895421176)( ijc 0673390245100954 01733402401004545第二步，試指派：第二步，試指派：找到找到 3 個獨立零元素個獨立零元素 但但 m = 3 n = 4 第三步，作最少的直線覆蓋所有第三步，作最少的直線覆蓋所有0元素：元素：立零元素的個數獨立零元素的個數m等于最少直線數等于最少直線數

44、l，即，即lm=3=12; x3+x4+x5+x6+x7=15; x1+x4+x5+x6+x7=12; x1+x2+x5+x6+x7=14; x1+x2+x3+x6+x7=16; x1+x2+x3+x4+x7=18; x1+x2+x3+x4+x5=19;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);gin(x7);End返回返回Global optimal solution found at iteration: 9 Objective value: 4400.000 Variable Value Reduced Cost X1 5.00000

45、0 0.000000 X2 2.000000 0.000000 X3 8.000000 0.000000 X4 0.000000 0.000000 X5 4.000000 0.000000 X6 0.000000 66.66667 X7 3.000000 0.000000該問題本質上是個整數規劃問題，放松的線性規劃的最優解是個整數解，所以兩規劃等價。定義整數變量用函數gin(x1) gin(x7); 0-1整數變量為bin(x1) 某城市要在市區設置k個應急服務中心,經過初步篩選確定了m個備選地，現已知共有n個居民小區，各小區到個備選地的距離為 為了使得各小區能及時得到應急服務，要求各小區到最

46、近的服務中心的距離盡可能的短，試給出中心選址方案。,.,2 , 1,.,2 , 1,mjnidij 該問題與傳統的選址問題的主要區別在于其目標不再是要求費用最小，而是要求最長距離最短。也就是離服務中心距離最遠的小區離最近的服務中心距離最小。 變量變量：當中心的位置確定下來后，各小區對應的最近中心也就確定，所以真正的變量也就是小區的位置。設 ,.,2,1,1 ,0mjxj 為了便于說明問題引入間接變量，第i小區是否由第j個中心服務 以及最遠的距離 約束條件約束條件 小區服務約束小區服務約束,.,2 , 1,.,2 , 1, 1 , 0mjniyij, z,.,2 , 1,.,2 , 1,mjni

47、xyjij,.,2 , 1, 11niymjij 最遠距離約束最遠距離約束 中心個數約束中心個數約束目標函數：最遠距離目標函數：最遠距離 最小最小 mjnizydijij,.,2 , 1,.,2 , 1,z,1kxmjj0,.,2 , 1,.,2 , 1, 1 , 0,.,2 , 1,.,2 , 1,.,2 , 1, 1,.,2 , 1,.,2 , 1,. .min11zmjniyxkxmjnizydniymjnixytszijjmjjijijmjijjij3.4 求解整數規劃的蒙特卡洛方法求解整數規劃的蒙特卡洛方法 在在3.4 中介紹的分枝定界方法，算法的每一個計中介紹的分枝定界方法，算法的

48、每一個計算步驟都是固定的，而且可以保證求得最優解。但是，算步驟都是固定的，而且可以保證求得最優解。但是，當整數線性規劃的決策變量數目很大時，分枝定界法當整數線性規劃的決策變量數目很大時，分枝定界法的代價可能是巨大的；特別是當整數規劃本身是非線的代價可能是巨大的；特別是當整數規劃本身是非線性的時候，尚未有一種成熟而有效的求解方法，因為性的時候，尚未有一種成熟而有效的求解方法，因為非線性規劃本身的通用有效解法尚未找到。非線性規劃本身的通用有效解法尚未找到。 然而，由于整數規劃解的數目是有限的，于是為枚舉然而，由于整數規劃解的數目是有限的，于是為枚舉法提供了方便。當然，當決策變量數目很大、取值范圍法

49、提供了方便。當然，當決策變量數目很大、取值范圍很寬情況下，企圖用完全搜索（即窮舉法）計算出最優很寬情況下，企圖用完全搜索（即窮舉法）計算出最優值是不現實的，但是應用蒙特卡洛算法，在一定的計算值是不現實的，但是應用蒙特卡洛算法，在一定的計算量下，完全可以得出一個滿意解。量下，完全可以得出一個滿意解。 例例3.4.1 已知非線性整數規劃為：已知非線性整數規劃為：max s.t.Z = x12 x22 3x32 4x42 2x52 8x1 2x2 3x3 x4 2x5x1 x2 x3 x4 x5 400 x1 2x2 2x3 x4 6x5 800 2x1 x2 6x3 200 x3 x4 5x5 2

50、005x1 9x2 45 0 xi 99，i = 1, 2, 3, 4, 5 對該問題，目前尚無有效方法求出準確的最優解。對該問題，目前尚無有效方法求出準確的最優解。如果用窮舉法（完全搜索）試探，共需計算如果用窮舉法（完全搜索）試探，共需計算1005 = 1010 個點，計算量非常大。然而概率理論能夠保證，應用蒙個點，計算量非常大。然而概率理論能夠保證，應用蒙特卡洛方法隨機計算特卡洛方法隨機計算106個點，便可找到問題的滿意解。個點，便可找到問題的滿意解。 解：用蒙特卡洛方法求解這個問題必須借助計算機解：用蒙特卡洛方法求解這個問題必須借助計算機來實現來實現。 運行程序運行程序 5 次，可得如下

51、表次，可得如下表 所示的結果：所示的結果： 運行程序最優解最優值第一次運行x = (2, 93, 13, 99, 10)T48024第二次運行x = (9, 98, 4, 99, 17)T48558第三次運行x = (34, 95, 5, 98, 9)T48097第四次運行x = (50, 91, 1, 98, 15)T48517第五次運行x = (38, 99, 3, 99, 3)T49866 注：蒙特卡洛（注：蒙特卡洛（Monte Carlo）算法是一種）算法是一種隨機搜索算法隨機搜索算法，它允許算法在執行的過程中隨機選擇下一個計算步驟。許多情況它允許算法在執行的過程中隨機選擇下一個計算步

52、驟。許多情況下，當算法在執行過程中面臨一個選擇時，隨機性選擇常比最優下，當算法在執行過程中面臨一個選擇時，隨機性選擇常比最優選擇省時，因此蒙特卡洛算法可在很大程度上降低算法的復雜度。選擇省時，因此蒙特卡洛算法可在很大程度上降低算法的復雜度。但另一方面，同一實例用蒙特卡洛算法求解兩次可能得到完全不但另一方面，同一實例用蒙特卡洛算法求解兩次可能得到完全不同的結果，也就是說，用蒙特卡洛算法能夠求得問題的一個解，同的結果，也就是說，用蒙特卡洛算法能夠求得問題的一個解，但無法判斷這個解是否正確，求得正確解的概率依賴于算法所用但無法判斷這個解是否正確，求得正確解的概率依賴于算法所用的時間，算法所用的時間越

53、多，得到正確解的概率就越高。的時間，算法所用的時間越多，得到正確解的概率就越高。 3.5 范例范例招聘計劃招聘計劃 招聘計劃：一家保姆服務公司專門向顧主提供保姆服務。招聘計劃：一家保姆服務公司專門向顧主提供保姆服務。根據估計，下一年的需求是：春季根據估計，下一年的需求是：春季 6000 人日，夏季人日，夏季 7500 人日，人日，秋季秋季 5500 人日，冬季人日，冬季 9000 人日。公司新招聘的保姆必須經過人日。公司新招聘的保姆必須經過 5 天的培訓才能上崗，每個保姆每季度工作（新保姆包括培訓）天的培訓才能上崗，每個保姆每季度工作（新保姆包括培訓）65 天。保姆從該公司而不是從顧主那里得到報酬，每人每月工天。保姆從該公司而不是從顧主那里得到報酬，每人每月工資資 800 元。春季開始時公司擁有元。春季開始時公司擁有 120 名保姆，在每個季度結束名保姆，在每個季度結束后，將有后，將有 15% 的保姆自動離職。的保姆自動離職。 (1) 如果公司不允許解雇保姆，請你為公司制定下一年的招如果公司不允許解雇保姆，請你為公司制定下一年的招聘計劃；哪些季度需求的增加不影響招聘計劃？可以增加多少？聘計劃；哪些季度需求的增加不影響招聘計劃？可以增加多少？ (2) 如果公司在每個季度結束后允許解雇保姆，請為公司制如果公司在每個季度結束后允許解雇保姆，請為公司制定下一年的招聘計劃。定下