1、整數規劃及其數學模型整數規劃及其數學模型分枝定界法分枝定界法割平面法割平面法0-1整數規劃整數規劃指派問題指派問題WinQSB軟件應用軟件應用第五章第五章 整數規劃整數規劃 (Integer Programming) 第一節第一節 整數規劃及其數學模型整數規劃及其數學模型在很多實際問題中，有些變量的取值必須是整數在很多實際問題中，有些變量的取值必須是整數在一個規劃問題中，如果它的在一個規劃問題中，如果它的某些變量（或全部某些變量（或全部變量）要求取整數變量）要求取整數，這個規劃問題就稱為，這個規劃問題就稱為整數規整數規劃問題劃問題，其中，其中v如果所有變量都取整數，就稱為如果所有變量都取整數，

2、就稱為純整數規劃或全整純整數規劃或全整數規劃數規劃v如果僅有一部分變量取整數，則稱為如果僅有一部分變量取整數，則稱為混合整數規劃混合整數規劃v 若變量值僅限于若變量值僅限于0 0或或1 1，則稱為，則稱為0-10-1規劃規劃一、問題的提出一、問題的提出在整數規劃問題中，不考慮整數要求，由其他在整數規劃問題中，不考慮整數要求，由其他約束條件和目標函數構成的規劃問題稱為該整約束條件和目標函數構成的規劃問題稱為該整數規劃問題的數規劃問題的松弛問題松弛問題。若松弛問題是一個線性規劃問題，則其對應的若松弛問題是一個線性規劃問題，則其對應的整數規劃問題稱為整數規劃問題稱為整數線性規劃（整數線性規劃（ILP

3、）。本章所討論的整數規劃都是指整數線性規劃。本章所討論的整數規劃都是指整數線性規劃。 （一）下料問題（一）下料問題【例【例5-1】某工地需要長度不同、直徑相同的成套】某工地需要長度不同、直徑相同的成套鋼筋，每套鋼筋由兩根鋼筋，每套鋼筋由兩根7米長和七根米長和七根2米長的鋼筋米長的鋼筋組成。現有組成。現有15米的圓鋼毛坯米的圓鋼毛坯150根，應如何下料根，應如何下料使廢料最少？使廢料最少？ 下料方式下料方式7 7米長的鋼筋（根）米長的鋼筋（根）2 2米長的鋼筋（根）米長的鋼筋（根）廢料廢料1 12 20 01 12 21 14 40 03 30 07 71 1 (二二)工廠選址問題工廠選址問題【

4、例【例5-35-3】工廠】工廠A1和和A2生產某種物資，由于該種物資供不應求，生產某種物資，由于該種物資供不應求，故需要再建一家工廠，相應的建廠方案有故需要再建一家工廠，相應的建廠方案有A3和和A4兩個。這種物兩個。這種物資的需求地有資的需求地有B1、B2、B3、B4四個。各工廠年生產能力、各地四個。各工廠年生產能力、各地年需求量、各廠至各需求地的單位物資運費年需求量、各廠至各需求地的單位物資運費cij（j=1,2,3,4）如如下表所示下表所示B1B2B3B4生產能力生產能力（千噸（千噸/年）年）A12934400A28357600A37612200A44525200需求量需求量（千噸（千噸/

5、年）年）350400300150工廠工廠A3或或A4開工后，每年的生產費用估計分別為開工后，每年的生產費用估計分別為12001200萬元或萬元或15001500萬元?，F要決定應該建設萬元。現要決定應該建設A3還是還是A4，才能使今后每年的總，才能使今后每年的總費用最少。費用最少。( (三三) )投資問題投資問題【5-2】某投資公司可用于投資的資金是】某投資公司可用于投資的資金是B，可供，可供投資的項目有投資的項目有n個，項目個，項目j所需投資額和預期收益所需投資額和預期收益分別分別aj和和cj。同時，由于種種原因，有三個附加。同時，由于種種原因，有三個附加條件：條件：第一，若選擇項目第一，若選

6、擇項目1，就必須同時選擇項目，就必須同時選擇項目2，反，反之則不一定；之則不一定；第二，項目第二，項目3和項目和項目4中至少選擇一個；中至少選擇一個；第三，項目第三，項目5、項目、項目6和項目和項目7中恰好選擇兩個。中恰好選擇兩個。應當怎樣選擇投資項目，才能使總預期收益最大？應當怎樣選擇投資項目，才能使總預期收益最大？整數規劃數學模型的一般形式整數規劃數學模型的一般形式且部分或全部為整數，或 n)21(j 0)21( )min(max11jnjijijnjjjxmibxaxcZZ 依照決策變量取整要求的不同，整數規劃可分為純依照決策變量取整要求的不同，整數規劃可分為純整數規劃整數規劃/ /全整

7、數規劃、混合整數規劃、全整數規劃、混合整數規劃、0 01 1整數規劃整數規劃二、整數規劃模型的一般形式及解的特點二、整數規劃模型的一般形式及解的特點且且為為整整數數0,143292)(23max21212121xxxxxxIPxxZ求解整數規劃問題求解整數規劃問題分析：考慮對應的線性規劃問題分析：考慮對應的線性規劃問題(LP)0,143292)(23max21212121xxxxxxLPxxZ整數規劃解的性質整數規劃解的性質3200CB XB b x1x2x3x40 x3921109/20 x414230114/2j32003200CB XB b x1x2x3x43x113/4103/4-1/

8、42x25/201-1/21/2j00-5/4-1/4用單純形法解（用單純形法解（如表所示如表所示），獲得最優解），獲得最優解初始表初始表最終表最終表可見，最優解為可見，最優解為x1=3.25 x2=2.5 z(0) =59/4=14.75變量不為整數，顯然（變量不為整數，顯然（LP）的最優解不是（）的最優解不是（IP）的最優解）的最優解 湊整湊整：(4, 3), (4, 2), (3, 3), (3, 2) (4, 3), (4, 2), (3, 3)均不可行均不可行 (3, 2)對應的目標函數值對應的目標函數值 z=13 但但(4, 1)對應的目標函數值對應的目標函數值 z=14可見，直接

9、湊整得到的解不見得是可行解；或者雖是可行可見，直接湊整得到的解不見得是可行解；或者雖是可行解，但不一定是最優解解，但不一定是最優解故需要對整數規劃問題發展新的解法故需要對整數規劃問題發展新的解法 分枝定界法分枝定界法 割平面法割平面法 分配問題的匈牙利法分配問題的匈牙利法 0-1規劃的隱枚舉法規劃的隱枚舉法0 x2 x1(a)(b)(5/3,5/2)第二節第二節 整數規劃的解法整數規劃的解法 分枝定界法分枝定界法且均為整數0,521023max2122121xxxxxxxz【例【例5-75-7】求解整數規劃問題求解整數規劃問題【思考【思考】（IPIP）的最優解是否會優于（）的最優解是否會優于（

10、LPLP）的最優解？）的最優解？（IPIP）的可行域與（）的可行域與（LPLP）可行域的關系如何？）可行域的關系如何？若（若（LPLP）有最優解，且其最優解為整數，則它是否也）有最優解，且其最優解為整數，則它是否也是（是（IPIP）的最優解？）的最優解？若（若（LPLP）有最優解，但其最優解不是整數，怎么辦？）有最優解，但其最優解不是整數，怎么辦？假設已知（假設已知（IPIP）的一個整數可行解，則（）的一個整數可行解，則（IPIP）的最優）的最優解與該解有怎樣的關系？解與該解有怎樣的關系？v 適用范圍適用范圍 全整數規劃問題或混合整數規劃問題全整數規劃問題或混合整數規劃問題v 本世紀本世紀60

11、60年代初由年代初由Land DoigLand Doig和和DakinDakin等人提出等人提出v 基本思路基本思路 設有最大化的整數規劃問題設有最大化的整數規劃問題(IP)，與它相應的線性規，與它相應的線性規劃問題為劃問題為(LP)松弛問題。從解松弛問題。從解(LP)開始，若其開始，若其最優解不符合整數條件，那么最優解不符合整數條件，那么(LP)的最優目標函數的最優目標函數必是必是(IP)最優解最優解z*的一個上界，記作的一個上界，記作z ;而而(IP)的任意的任意可行解的目標函數值將是可行解的目標函數值將是z*的一個下界的一個下界z 。分枝定界。分枝定界法就是將法就是將(LP)的可行域分成

12、子區域（分枝），逐步的可行域分成子區域（分枝），逐步減小減小z 和增大和增大z ，最終求得，最終求得z*的方法。的方法。【例【例5-75-7】且為整數且為整數)2 . 1( , 0)2 . 1( )(max11mjxmibxaIPxcZjnjijijnjjj考慮全整數規劃問題：考慮全整數規劃問題：)2 . 1( , 0)2 . 1( )(max11mjxmibxaLPxcZjnjijijnjjj整數規劃的松弛問題：整數規劃的松弛問題：步驟：步驟： 1、先不考慮整數約束，解、先不考慮整數約束，解( IP )的松弛問題的松弛問題( LP )，可能，可能得到以下情況之一：得到以下情況之一： ( LP

13、 )沒有最優解，則沒有最優解，則( IP )也沒有最優解，停止計算；也沒有最優解，停止計算； 若若( LP )有最優解，并符合有最優解，并符合( IP )的整數條件，則的整數條件，則( LP )的的最優解即為最優解即為( IP )的最優解，停止計算；的最優解，停止計算； 若若( LP )有最優解，但不符合有最優解，但不符合( IP )的整數條件，轉入下的整數條件，轉入下一步。為討論方便，設一步。為討論方便，設( LP )的最優解為：的最優解為： 不不全全為為整整數數其其中中目目標標函函數數最最優優值值為為), 2 , 1(.Z)0 , 0 ,( (0)21)0(mibbbbbXiTmr 2、定

14、界：、定界： 記記( IP )的目標函數最優值為的目標函數最優值為Z* ,以以Z(0) 作為作為Z* 的上界，的上界，記為記為 Z(0) 。再用觀察法找到一個整數可行解。再用觀察法找到一個整數可行解 X，并，并以其相應的目標函數值以其相應的目標函數值 Z作為作為Z* 的下界，記為的下界，記為Z Z（?。ㄈj = 0），則有：），則有： Z Z* 。ZZ將這兩個約束條件分別加入問題將這兩個約束條件分別加入問題(IP) ，形成兩個子問題，形成兩個子問題(IP1)和和(IP2) ，再解這兩個問題的松弛問題，再解這兩個問題的松弛問題(LP1)和和(LP2) 。 3、分枝：分枝： 在在( LP )的最

15、優解的最優解X(0)中，任選一個不符合整數條件的中，任選一個不符合整數條件的變量，例如變量，例如xr= （不為整數），以（不為整數），以 表示不超過表示不超過 的的最大整數。構造兩個約束條件最大整數。構造兩個約束條件 xr 和和xr 1 1rbrbrbrbrb 4、修改上、下界：修改上、下界：( (按照以下兩點規則進行按照以下兩點規則進行) ) 在各分枝問題中，找出目標函數值最大者作為新在各分枝問題中，找出目標函數值最大者作為新的上界；的上界； 從已符合整數條件的分枝中，找出目標函數值最從已符合整數條件的分枝中，找出目標函數值最大者作為新的下界。大者作為新的下界。 5、比較與剪枝比較與剪枝 ：

16、 各分枝的目標函數值中，若有小于各分枝的目標函數值中，若有小于Z 者，則剪掉此枝，者，則剪掉此枝，表明此子問題已經探清，不必再分枝了表明此子問題已經探清，不必再分枝了;否則繼續分枝否則繼續分枝 。 如此反復進行，直到得到如此反復進行，直到得到ZZ* 為止，即得最優解為止，即得最優解 X* Z3200CB XB b x1x2x3x40 x3921109/20 x414230114/232003200CB XB b x1x2x3x43x113/4103/4-1/42x25/201-1/21/200-5/4-1/4解解:用單純形法解對應的用單純形法解對應的(LP)問題問題,如表所示如表所示,獲得最優

17、解獲得最優解初始表初始表最終表最終表可見，最優解為可見，最優解為x1=3.25 x2=2.5 z(0) =59/4=14.75且且為為整整數數0,143292)(23max21212121xxxxxxIPxxZ例例1、用分枝定界法求解整數規劃問題、用分枝定界法求解整數規劃問題選選 x2 進行分枝，即增加兩個約束進行分枝，即增加兩個約束x22 和和x2 3 ，則，則且且為為整整數數0,2 14329 2) 1(23max212212121xxxxxxxIPxxZ且且為為整整數數0,3 14329 2)2(23max212212121xxxxxxxIPxxZ 分別在分別在(LP1)和和(LP2)中

18、引入松弛變量中引入松弛變量x5和和x6 ，將新加，將新加約束條件加入上表計算，即約束條件加入上表計算，即 x2+ x5= 2 , x2+x6=3 得下表得下表:32000CB XB b x1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200 x520100100-5/4-1/403x113/4103/4-1/402x25/201-1/21/200 x5-1/2001/2 -1/2100-5/4-1/403x17/2101/20-1/22x22010010 x4100-11-200-3/20-1/2x1=7/2, x2=2 Z(1) =29/2=14.5繼續分枝

19、，繼續分枝，加入約束加入約束 x1 3, x1 4LP132000CB XB b x1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200 x6-30-1001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200 x6-1/200-1/2 1/21-Z-59/400-5/4-1/403x15/21001/23/22x230100-10 x31001-1-2-Z-27/2000-3/2-5/2LP2x1=5/2, x2=3 Z(2) =27/2=13.5 Z(2) z(3),故故x1=4, x2=1為最優解為最優

20、解 LP4樹形圖如下：樹形圖如下：LP1x1=7/2, x2=2Z(1)29/2=14.5LPx1=13/4, x2=5/2Z(0) 59/4=14.75LP2x1=5/2, x2=3Z(2)27/2=13.5LP3x1=3, x2=2Z(3) 13LP4x1=4, x2=1Z(4) 14x22x23x13x14例例2、用分枝定界法求解整數規劃問題、用分枝定界法求解整數規劃問題（圖解法計算）（圖解法計算）且且全全為為整整數數0,4 30 652 5min211212121xxxxxxxxxZ記為（記為（IP）解：首先去掉整數約束，變成一般線性規劃問題解：首先去掉整數約束，變成一般線性規劃問題0

21、,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,1 4 30 652 )1(5min

22、2111212121xxxxxxxxIPxxZ且且為為整整數數0,2 4 30 652 )2(5min2111212121xxxxxxxxIPxxZ 現在只要求出（現在只要求出（LP1）和（）和（LP2）的最優解即可）的最優解即可同理求同理求（LP2） ,如圖所示如圖所示在在C 點取得最優解點取得最優解即即x12, x2 =10/3, Z(2) 56/318.7 Z(2) Z(0) 原問題目標函數值的下界為原問題目標函數值的下界為-18.7-18.7x2 不是整數，故利用不是整數，故利用3 10/34 加入條件加入條件x1x233(18/11,40/11) 先求先求（LP1）, ,如圖所示。此

23、如圖所示。此時，在時，在B 點取得最優解點取得最優解x11, x2 =3, Z(1)16找到整數解，問題已探明，找到整數解，問題已探明，此枝停止計算。且由此可知此枝停止計算。且由此可知目標函數最優值的上界為目標函數最優值的上界為-1611BAC加入條件：加入條件： x23, x24 有下式：有下式：且且為為整整數數0,3 2 4 30 652 )3(5min21211212121xxxxxxxxxIPxxZ且且為為整整數數0,4 2 4 30 652 )4(5min21211212121xxxxxxxxxIPxxZ只要求出（只要求出（LP3）和（）和（LP4）的最優解即可）的最優解即可x1x2

24、33(18/11,40/11)11BAC先求先求（LP3）, ,如圖所示。此時如圖所示。此時D 在點取得最優解在點取得最優解即即 x112/5=2.4, x2 =3, Z(3)-87/5=-17.4-18.7但但x112/5不是整數，可繼續不是整數，可繼續分枝。即分枝。即 3x12D求求（LP4），），如圖所示如圖所示無可行解，不再分枝無可行解，不再分枝 在在（LP3）的基礎上繼續分枝。加入條件）的基礎上繼續分枝。加入條件3x12有下式：有下式：且且為為整整數數0,2 3 2 4 30 652 )5(5min211211212121xxxxxxxxxxIPxxZ且且為為整整數數0,3 3 2

25、4 30 652 )6(5min211211212121xxxxxxxxxxIPxxZ只要求出（只要求出（LP5）和（）和（LP6）的最優解即可）的最優解即可x1x233(18/11,40/11)11BACD先求先求（LP5）, ,如圖所示。此時如圖所示。此時E 在點取得最優解在點取得最優解即即 x12, x2 =3, Z(5)17找到整數解，問題已探明，此找到整數解，問題已探明，此枝停止計算。枝停止計算。E求求（LP6），），如圖所示。此時如圖所示。此時 F在點取得最優解在點取得最優解x13, x2 =2.5, Z(6)31/2=15.5 Z(5) F 如對如對Z(6) 繼續分解，其最小值也

26、不會低于繼續分解，其最小值也不會低于15.5，問題探明，問題探明, ,剪枝剪枝至此，原問題至此，原問題( (IP) )的最優解為：的最優解為： x1=2， x2 =3, Z* = Z(5) 17以上的求解過程可以上的求解過程可以用一個樹形圖表以用一個樹形圖表示如右：示如右：LP1x1=1, x2=3Z(1) 16LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=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.5x11x12x23

27、x24x12x13 且全為整數且全為整數0,13651914max21212121xxxxxxxxZ練習：用分枝定界法求解整數規劃問題練習：用分枝定界法求解整數規劃問題 LP1x1=1, x2=7/3Z(1) 10/3LPx1=3/2, x2=10/3Z(0) 29/6LP2x1=2, x2=23/9Z(2) 41/9x11x12LP3x1=33/14, x2=2Z(3) 61/14LP4無可無可行解行解x22x23LP5x1=2, x2=2Z(7) 4LP6x1=3, x2=1Z(8) 4x12x13一、計算步驟一、計算步驟 1、用單純形法求解、用單純形法求解( IP )對應的松弛問題對應的

28、松弛問題( LP ) 若若( LP )沒有最優解，則沒有最優解，則( IP )也沒有最優解，也沒有最優解，停止計算；停止計算； 若若( LP )有最優解，并符合有最優解，并符合( IP )的整數條件，的整數條件，則則( LP )的最優解即為的最優解即為( IP )的最優解，停止計算；的最優解，停止計算； 若若( LP )有最優解，但不符合有最優解，但不符合( IP )的整數條件，的整數條件，轉入下一步。轉入下一步。第三節第三節 整數規劃的解法整數規劃的解法 割平面法割平面法 2 2、從、從( (LP) )的最優解中，任選不為整數的分量的最優解中，任選不為整數的分量xi ,將最將最優單純形表中該

29、行的系數優單純形表中該行的系數 和和 分解為整數部分和小分解為整數部分和小數部分之和，并以該行為源行，作割平面方程數部分之和，并以該行為源行，作割平面方程ikaib由最終單純形表可以得到：由最終單純形表可以得到： ikikibxaxikaib將將 和和分成整數部分和非負真分數之和，即分成整數部分和非負真分數之和，即iiifNb10iiifbN的整數部分，為ikikikfNa10ikikikfaN的整數部分，為代入上式得：代入上式得：kkikkiikikixffNxNx 因變量為整數，即上式左邊必須是整數，由右邊看，因為因變量為整數，即上式左邊必須是整數，由右邊看，因為00fi 11，所以不能為

30、正，即，所以不能為正，即 0kkikixff割平面方程割平面方程 3 3、將由割平面方程得到的約束條件作為一個新、將由割平面方程得到的約束條件作為一個新的約束條件置于最優單純形表中，用對偶單純形法的約束條件置于最優單純形表中，用對偶單純形法求出新的最優解，返回求出新的最優解，返回1 1。例例1 、用割平面法求解整數規劃問題、用割平面法求解整數規劃問題且為整數, 0,14329223max21212121xxxxxxxxZ2123maxxxz0,1432924321421321xxxxxxxxxx 解：增加松弛變量解：增加松弛變量x3和和x4 ，得到，得到(LP)的初始單純形表的初始單純形表和最

31、優單純形表和最優單純形表：Cj3200CBXBbx1x2x3x40 x31423100 x492101Z00100Cj3200CBXBbx1x2x3x42x25/2011/2-1/23x113/410-1/41/4Z-3/200-1/4-5/4 此題的最優解為：此題的最優解為：X =(13/4 ,5/2) 。但不是整數最優解，但不是整數最優解，引入割平面。可以使用的割平面的條件有引入割平面?？梢允褂玫母钇矫娴臈l件有: 252121432xxx4134141431xxx41414343xx21212143xx252121432xxx21221214432xxxx43422121212xxxx41

32、34141431xxx41341434331xxxx43314143413xxxx 為加快割平面的速度，一般選擇較大的為加快割平面的速度，一般選擇較大的 fi 作為割平面作為割平面方程進行計算方程進行計算現將生成的割平面條件加入松弛變量，然后加到表中現將生成的割平面條件加入松弛變量，然后加到表中212121543xxx21212143xx21212143xxCj32000CBXBbx1x2x3x4x52x25/2011/2-1/203x113/410-1/43/400 x5-1/200-1/2-1/2100-1/4-5/402x22010-113x17/21001-1/20 x310011-2

33、000-1-1/221215x割平面方程為割平面方程為: :Cj320000CBXBbx1x2x3x4x5x62x22010-1103x17/21001-1/200 x310011-200 x6-1/20000-1/21000-1-1/202x21010-1023x1410010-10 x3300110-40 x5100001-2000-10-1且均為整數0,521023max2122121xxxxxxxz【例【例5-75-7】求解整數規劃問題求解整數規劃問題且為整數0,205462max21212121xxxxxxxxz【練習【練習】求解整數規劃問題求解整數規劃問題 01整數規劃是一種特殊形

34、式的整數規劃，整數規劃是一種特殊形式的整數規劃，這時的決策變量這時的決策變量xi 只取兩個值只取兩個值0或或1，一般的解法為，一般的解法為隱枚舉法隱枚舉法【例【例5-11】求解下列】求解下列01規劃問題規劃問題 10,(4) 64 (3) 3 (2) 44(1) 22523max3213221321321321或或xxxxxxxxxxxxxxxxZ第四節第四節 0-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

35、4 1 42( 1, 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 )解：對于解：對于01規劃問題，由于每個變量只取規劃問題，由于每個變量只取0、1兩個值，一兩個值，一般會用窮舉法來求解，即將所有的般會用窮舉法來求解，即將所有的0、1組合找出，使目標函組合找出，使目標函數達到極值要求就可求得最優解。數達到極值要求就可求得最優解。 由上表可知：由上表可知： x1 =0，x2=0，x3=1是一

36、個可行解，為盡快找是一個可行解，為盡快找到最優解，可將到最優解，可將3x12x25x35作為一個約束，凡是目標函作為一個約束，凡是目標函數值小于數值小于5的組合不必討論，如下表。的組合不必討論，如下表。x1 , x2 , x3約束條件約束條件滿足條件滿足條件Z 值值(0) (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問題的最優解為問題的最優

37、解為 X*=( x1 =1，x2=0，x3=1 )隱枚舉法如果重新排列變量的順序可使問題更快地求得最優解，如：如果重新排列變量的順序可使問題更快地求得最優解，如：令令x2=1-x2(0 x21)，將目標函數中變量前的系數均化為正數，將目標函數中變量前的系數均化為正數，則目標函數變為則目標函數變為22355)1(23213321xxxxxxzmax尋找最優目標函數值尋找最優目標函數值x1 ， x2， x3約束條件約束條件滿足條件滿足條件Z 值值(0) (1) (2) (3) (4)是是 否否( 1, 1, 1 ) 8 0 0 0 08問題的最優解為問題的最優解為 X*=( x1=1，x2=0，x

38、3=1 ) 【例】求解下列【例】求解下列01規劃問題規劃問題4 , 3 , 2 , 1 1 , 05 35646 1 273max421432143214321jxxxxxxxxxxxxxxxxZj 解：令解：令 x11x1, x2=1- x2, x4=1- x4，則目標函數變，則目標函數變為為1173)1 ()1 (7)1 ( 3max43214321xxxxxxxxZ此時，此時，x*=(1, 0, 1, 0)，z*=-2練習：求解下列練習：求解下列01規劃問題規劃問題)5 , 4 , 3 , 2 , 1( 1054 24423 248510min543215432154321jxxxxxx

39、xxxxxxxxxxZj或所以，所以， 原問題的最優解為：原問題的最優解為： X*(0, 0, 1, 0, 0)，Z*=8第五節第五節 指派問題指派問題 在實際中經常會遇到這樣的問題，有在實際中經常會遇到這樣的問題，有n 項不同的任項不同的任務，務，需要需要n 個人分別完成其中的一項個人分別完成其中的一項，但由于任務的，但由于任務的性質和各人的專長不同，因此各人去完成不同的任務性質和各人的專長不同，因此各人去完成不同的任務的效率（或花費的時間或費用）也就不同。于是產生的效率（或花費的時間或費用）也就不同。于是產生了一個問題，指派哪個人去完成哪項任務，可使完成了一個問題，指派哪個人去完成哪項任務

40、，可使完成 n 項任務的總效率最高（或所需時間最少）？這類問項任務的總效率最高（或所需時間最少）？這類問題稱為題稱為指派問題指派問題或或分配問題分配問題。 每一項工作只能分配給一個人；每一項工作只能分配給一個人； 每一個人只能并且必須接受一項工作每一個人只能并且必須接受一項工作 一、指派問題的一般提法一、指派問題的一般提法【5-135-13】某工廠要生產四種產品，該工廠有四個車間都可以生】某工廠要生產四種產品，該工廠有四個車間都可以生產這四種產品。但由于設備情況與技術情況不同，所以生產成產這四種產品。但由于設備情況與技術情況不同，所以生產成本不同，其單位產品的生產成本如表所示。問應當如何分配這

41、本不同，其單位產品的生產成本如表所示。問應當如何分配這四種產品到各車間，才能使總的生產成本最?。吭嚱⒃搯栴}四種產品到各車間，才能使總的生產成本最??？試建立該問題的數學模型。的數學模型。 產品產品車間車間1234145410251453332643446解解 引入引入0-10-1變量變量xij ( (i, j1,2,3,4,5)1,2,3,4,5)，令：令： 時生產產品，當不指派車間時生產產品，當指派車間jijixij01這個問題的約束條件如下：這個問題的約束條件如下：(1)(1)一個車間只生產一種產品，即一個車間只生產一種產品，即1111444342413433323124232221141

42、31211xxxxxxxxxxxxxxxx141jijx簡寫為：簡寫為： （i=1,2,3,4） (2)(2)一種產品只由一個車間生產，即一種產品只由一個車間生產，即 111144342414433323134232221241312111xxxxxxxxxxxxxxxx簡寫為：簡寫為：141iijx（ j =1,2,3,4） (3)(3)變量工變量工xij 必須等于必須等于0 0或或1 1，即，即xij =0=0或或1 1。 目標函數為：目標函數為：Min 443412116454xxxxz設決策變量設決策變量 1 分配第分配第i 個人去做第個人去做第j 件工作件工作 xij = 0 相反相

43、反 ( i , j =1.2. n )其數學模型為： 設設n個人被分配去做個人被分配去做n件工作，規定每個人只做一件工作件工作，規定每個人只做一件工作,每每件工作只有一個人去做。已知第件工作只有一個人去做。已知第i個人去做第個人去做第j件工作的的效件工作的的效率（率（ 時間或費用）為時間或費用）為cij (i =1, 2, , n; j =1, 2, , n)并假設并假設cij 0。問應如何分配才能使總效率（。問應如何分配才能使總效率（ 時間或費用）最高？時間或費用）最高？ninjijijxcz11min), 2 , 1,( 10), 2 , 1( 1), 2 , 1( 111njixnjxn

44、ixijniijnjij或效率矩陣（成本矩陣）效率矩陣（成本矩陣）:(:(cij ) )nn 二、匈牙利法二、匈牙利法 分配問題是分配問題是0-1規劃的特例，也是運輸問題的特例，當然可規劃的特例，也是運輸問題的特例，當然可用整數規劃，用整數規劃，0-1規劃或運輸問題的解法去求解，但這些方法卻規劃或運輸問題的解法去求解，但這些方法卻沒有充分利用指派問題的特點。沒有充分利用指派問題的特點。 庫恩庫恩( (W.W.Kuhn) )于于19551955年提出了指派問題的解法，他引用了年提出了指派問題的解法，他引用了匈牙利數學家康尼格匈牙利數學家康尼格( (D.Konig) )的關于矩陣中獨立零元素的定理

45、：的關于矩陣中獨立零元素的定理：系數矩陣中獨立系數矩陣中獨立0 0元素的最多個數等于能覆蓋所有零元元素的最多個數等于能覆蓋所有零元素的最小直線數，習慣上稱之為匈牙利解法。素的最小直線數，習慣上稱之為匈牙利解法。 分配問題最優解的以下性質：分配問題最優解的以下性質：若從系數矩陣若從系數矩陣(cij )的某行的某行( (或某列或某列) )各元素分別減去該行（列）的最小元素，得各元素分別減去該行（列）的最小元素，得到新矩陣到新矩陣(cij),那么以那么以(cij)為系數矩陣求得的最優解和為系數矩陣求得的最優解和利用原系數矩陣求得的最優解相同。利用原系數矩陣求得的最優解相同。 證明證明), 2 , 1

46、;, 3 , 2();, 2 , 1(11njniccnjkccijijjj設成本矩陣第一行各元素均減去同一個數設成本矩陣第一行各元素均減去同一個數k，得到的新矩，得到的新矩陣記為陣記為( (cij ) )kzkxcxcxkxcxcxkcxczninjijijninjijijnjjnjjjninjijijnjjjninjijij1121111112111111)( 第一步：變換成本矩陣，使每行每列中至少出現一第一步：變換成本矩陣，使每行每列中至少出現一個個0元素元素 (1) 令令(cij) nn的每行元素都減去該行的最小元素；的每行元素都減去該行的最小元素； (2) 再從所得新系數矩陣的每列元

47、素中減去該列的再從所得新系數矩陣的每列元素中減去該列的最小元素。最小元素。644362335415104543110401143046010321401101011130430103匈牙利法的步驟（以（以 例例5-135-13為例）為例） 第二步：試求最優解第二步：試求最優解 在新矩陣中找盡可能多的獨立在新矩陣中找盡可能多的獨立0元素，若能找出元素，若能找出n個個獨立獨立0元素，就以這元素，就以這n個獨立個獨立0元素對應解矩陣元素對應解矩陣(xij)中的元中的元素為素為1，其余為，其余為0，這就得到最優解。找獨立，這就得到最優解。找獨立0元素，常元素，常用的步驟為：用的步驟為： (1) 從只有

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