1、1第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃學時安排：學時安排：8學時教學目的：教學目的：掌握若干特殊整數(shù)規(guī)劃的解法教學內(nèi)容：教學內(nèi)容：1.整數(shù)規(guī)劃問題及特點2.分枝定界法與割平面法3.0-1規(guī)劃4.指派問題 教學重點：教學重點：割平面法與指派問題 教學難點：教學難點：分枝定界法與割平面法2第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃教學內(nèi)容第一節(jié)整數(shù)規(guī)劃問題的提出第二節(jié)解純整數(shù)規(guī)劃的割平面法 第三節(jié)分支定界法 第四節(jié) -整數(shù)規(guī)劃 第五節(jié)指派問題3第一節(jié) 整數(shù)規(guī)劃問題的提出1. 整數(shù)規(guī)劃問題基本概念2. 整數(shù)規(guī)劃問題的數(shù)學模型3. 整數(shù)規(guī)劃解的特點第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃41. 基本

2、概念 整數(shù)規(guī)劃：要求部分或全部決策變量取整數(shù)值的規(guī)劃問題。 整數(shù)規(guī)劃問題的松弛問題：不考慮整數(shù)條件的規(guī)劃問題。 整數(shù)線性規(guī)劃：整數(shù)規(guī)劃為線性規(guī)劃 純整數(shù)線性規(guī)劃（pure integer linear programming) 混合整數(shù)線性規(guī)劃（mixed integer linear programming） 0-1整數(shù)線性規(guī)劃(zero-one integer linear programming）注意：注意：后面提到的整數(shù)規(guī)劃，一般指的都是整數(shù)線性規(guī)劃。第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃52. 整數(shù)規(guī)劃數(shù)學模型的一般形式部分或全部取整數(shù)值),2, 1(),2, 1(0),2, 1(),( .

3、max(min) 11njxnjxmibxatsxczjjnjijijnjjj第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃63. 整數(shù)規(guī)劃解的特點問題：能否將松弛問題最優(yōu)解的近似值（取整、四舍五入）作為整數(shù)規(guī)劃問題的最優(yōu)解？例1：求下述整數(shù)規(guī)劃的最優(yōu)解。且取整數(shù)0,5 .45 .0143223max21212121xxxxxxxxZ第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃7第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃 1 2 3 4 5 6 7x115234x2A (3.25,2.5)2x1+3x2=14X1+0.5x2 =4.5Z=3x1+2x2最優(yōu)解為最優(yōu)解為(4,1)且取整數(shù)0,5 .45 .0143223max212121

4、21xxxxxxxxZ8第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃結(jié)論：結(jié)論：不能把松弛問題的最優(yōu)解通過不能把松弛問題的最優(yōu)解通過“四舍五入四舍五入”或或“截尾截尾”（即湊整）處理后作為整數(shù)規(guī)劃的（即湊整）處理后作為整數(shù)規(guī)劃的最優(yōu)解。不過，在變量取值很大時，用上述方最優(yōu)解。不過，在變量取值很大時，用上述方法得到的解與最優(yōu)解差別不大。法得到的解與最優(yōu)解差別不大。點點(4,1)不是可行域的頂點，所以直接用圖解不是可行域的頂點，所以直接用圖解法或單純形法無法求出整數(shù)規(guī)劃問題的最優(yōu)解法或單純形法無法求出整數(shù)規(guī)劃問題的最優(yōu)解9第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃 整數(shù)線性規(guī)劃的解與松弛問題的解既有聯(lián)系，整數(shù)線性規(guī)劃的解與

5、松弛問題的解既有聯(lián)系，又有本質(zhì)的區(qū)別。設又有本質(zhì)的區(qū)別。設 IP的松弛問題的可行域為的松弛問題的可行域為C，IP的可行域為的可行域為C，則有，則有 CC 整數(shù)規(guī)劃的可行解是松弛問題可行解集合的一整數(shù)規(guī)劃的可行解是松弛問題可行解集合的一個子集。所以個子集。所以：IP的可行解一定是它的松弛問題的可行解。的可行解一定是它的松弛問題的可行解。 IP的最優(yōu)值不會優(yōu)于其松弛問題的最優(yōu)值。的最優(yōu)值不會優(yōu)于其松弛問題的最優(yōu)值。10第二節(jié) 割平面法1. 割平面方法的基本思想和步驟2. 構造割平面約束的方法3. 示例第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃21maxxxZ為整數(shù)2,12121210,431xxxxxxxx1

6、x2x112-x1+x2 =13x1+x2 =4maxZAA(3/4,7/4)C(1,1)1. 割平面方法的基本思想和步驟基本思想基本思想：在IP問題的松弛問題中依次引進線性約束（稱Gomory約束或割平面），使問題的可行域逐步縮小，所割去的區(qū)域僅包含問題的部分非整數(shù)解；當規(guī)劃問題的最優(yōu)解恰好位于縮小的可行域的一個頂點時，算法結(jié)束。第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃求解步驟：求解步驟：第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃 求出松弛問題最優(yōu)解，若為整數(shù)，則停止，否則轉(zhuǎn) 構造割平面方程。構造的割平面約束應當具備兩個性質(zhì)：a) 已獲得的非整數(shù)最優(yōu)解不滿足該線性約束，從而保證在以后的解中不可能再出現(xiàn)。b) 所有

7、的整數(shù)解皆滿足該線性約束，從而保證整數(shù)最優(yōu)解始終都保留在以后每次所形成的新的線性規(guī)劃的可行域中。14第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃3-10003-1013/79/731/71000101/7-2/7-3/70012/73/722/700-5/70-3/7jcjjzc X4=31/7不是整數(shù)，該行對應的方程是：不是整數(shù)，該行對應的方程是：731722)73(534xxxCBXBbx1x2x3x4x5x1x2x4第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃X4 - 3/7 x3 + 22/7 x5 = 31/7基變量（整數(shù)）基變量（整數(shù)） 非基變量（整數(shù)）非基變量（整數(shù)） -3/7 = -1+4/7 22/7=

8、 3 + 1/7 31/7= 4 + 3/7 在上述式子中，除第一部分在上述式子中，除第一部分X4 （即整數(shù)部（即整數(shù)部分）外，我們將后面變量的系數(shù)與常數(shù)項皆分）外，我們將后面變量的系數(shù)與常數(shù)項皆化為兩部分：不超過該數(shù)的最大整數(shù)與非負化為兩部分：不超過該數(shù)的最大整數(shù)與非負分數(shù)，即分數(shù)，即16第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃734)713 ()741(534xxx 將整數(shù)部分放在等式的左邊將整數(shù)部分放在等式的左邊,其余部分放在右邊其余部分放在右邊,得：得：5353471747343xxxxx731722)73(534xxx17第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃上式的左邊是一個整數(shù)，右邊是一個小于上式的

9、左邊是一個整數(shù)，右邊是一個小于的數(shù)，因此，右邊是一個小于或等于的數(shù)，因此，右邊是一個小于或等于的整數(shù)，即的整數(shù)，即071747353xx73717453xx通過分析，可以得出上式具有如下兩個性質(zhì)：通過分析，可以得出上式具有如下兩個性質(zhì)：松弛問題的非整數(shù)最優(yōu)解不滿足該式松弛問題的非整數(shù)最優(yōu)解不滿足該式IP的所有整數(shù)可行解都滿足此式的所有整數(shù)可行解都滿足此式18第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃構造割平面約束的一般方法如下：構造割平面約束的一般方法如下： 1、在松弛問題的最優(yōu)表中，設、在松弛問題的最優(yōu)表中，設b列的第列的第k個分量個分量bk為非整為非整數(shù)，可將它分解為整數(shù)和非整數(shù)部分之和，即數(shù)，可將它

10、分解為整數(shù)和非整數(shù)部分之和，即bk =Nk + fk ， Nk bk 且為整數(shù)，且為整數(shù)，0 fk 1。 2、然后，第、然后，第k行中的每一個非基變量行中的每一個非基變量 xj的系數(shù)的系數(shù) akj也分解也分解為整數(shù)與非負數(shù)之和的形式，即為整數(shù)與非負數(shù)之和的形式，即 akj= Nkj + fkj ;Nkj akj ; 0 fk 1,則割平面方程為：則割平面方程為：kjkjfxfxj為非基變量為非基變量通常，從最優(yōu)單純形表中，選擇具有通常，從最優(yōu)單純形表中，選擇具有最大分數(shù)部分的非整最大分數(shù)部分的非整分量分量所在行構造割平面約束，可以提高切割效果，減少切所在行構造割平面約束，可以提高切割效果，減少

11、切割次數(shù)。割次數(shù)。19第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃例例：用用割平面法求解純整數(shù)規(guī)劃。割平面法求解純整數(shù)規(guī)劃。213maxxxZ為整數(shù)。2,1212121210,521045323xxxxxxxxxx解解: 1、用單純形法求得松弛問題的最優(yōu)表如下。、用單純形法求得松弛問題的最優(yōu)表如下。20第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃3-10003-1013/79/731/71000101/7-2/7-3/70012/73/722/700-5/70-3/776727153xx 松弛問題的最優(yōu)解為非整數(shù)松弛問題的最優(yōu)解為非整數(shù),而在而在13/7=1+6/7 ，9/7=1+2/7 ， 31/7=4+3/7的非負分

12、數(shù)中的非負分數(shù)中,6/7最大。最大。所以，將所以，將13/7所在的行中非基變量所對應的系數(shù)進行所在的行中非基變量所對應的系數(shù)進行分解分解: 1/7=0+1/7 2/7=0+2/7。割平面方程為：。割平面方程為：jcjjzc CBXBbx1x2x3x4x5x1x2x421第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃3-100003-10013/79/731/7-6/7100001001/7-2/7-3/7-1/700102/73/722/7-2/7000100-5/70-3/70jcjjzc 將割平面約束變?yōu)榈仁郊s束后，并入松弛問題的將割平面約束變?yōu)榈仁郊s束后，并入松弛問題的最優(yōu)表中，見下表。最優(yōu)表中，見下表

13、。CBXBbx1x2x3x4x5x1x2x4x6x622第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃3-100003-10015/45/27/41000010000100-1/4-1/21/400011-5/4-11/2-3/4000-1/40-17/4利用對偶單純形法求出最優(yōu)解，見下表。利用對偶單純形法求出最優(yōu)解，見下表。CBXBbx1x2x3x4x5x1x2x3x5x6jcjjzc 23第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃由上表第四行產(chǎn)生的割平面約束為：由上表第四行產(chǎn)生的割平面約束為：43414164xx3-10000 03-100015/45/27/41000001000001000-1/4-1/21/4-

14、1/4000101 0-5/4 0-11/2 0-3/4 0-1/4 1000-1/40-17/4 0jcjjzc x1x2x4x6CBXBbx1x2x3x4x5x6x7-3/4x724第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃3-10000 03-1000124110000010000010000001000101 0-1 -1-5 -2-1 11 -400000-4 -1jcjjzc x1x2x4x6CBXBbx1x2x3x4x5x6x4 3x71max, 2, 121zxx25第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃3x1-2x2=35x1+4x2=102x1+x2=5ABCDmax1x2x 1 2 3152

15、34-1/7x3-2/7x5 -6/7x11-1/4x4-1/4x6 -3/4x1 +x2 3x11x1 +x2 3EF3x1-2x2 35x1+4x2 102x1+x2 5maxZ=3x1-x23x1-2x2 + x3= 35x1+4x2 x4 =102x1+x2 + x5 = 5maxZ=3x1-x2F26第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃案例案例32x1+x2 64x1+5x2 20 x1,x2 0且為整數(shù)且為整數(shù)maxZ=x1+x21、求出松弛問題的最優(yōu)解、求出松弛問題的最優(yōu)解2x1+x2 +x3 = 64x1+5x2 +x4 = 20 x1,x2 , x3,x4 0且為整數(shù)且為整數(shù)max

16、Z=x1+x227第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃110015/3105/6-1/618/301-2/31/300-1/6-1/6x1x2CBXBbx1x2x3x4jcjjzc 32656543xx2、構造割平面、構造割平面326565543xxx第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃1100 0 15/3105/6-1/6 018/301-2/31/3 0 0-2/300-5/6-5/6 100-1/6-1/6 0 x1x2CBXBbx1x2x3x4jcjjzc 326565543xxxx5x5第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃1100 0 11100-1 1116/50101 -4/5 04/50011

17、 -6/50000 -1/5x1x2CBXBbx1x2x3x4jcjjzc x3x554545x3、構造割平面、構造割平面545465xx第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃1100 0 0 11100-1 1 0116/50101 -4/5 0 04/50011 -6/5 0 0-4/50000 -4/5 10000 -1/5 0 x1x2CBXBbx1x2x3x4jcjjzc x3x5545465xxx6x6第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃1100 0 0 10100-1 0 5/41 40101 0 -1 0 20011 0 -3/2 010000 1 -5/40000 0 -1/4x1x2CB

18、XBbx1x2x3x4jcjjzc x3x5x5x6第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃2x1+x2 64x1+5x2 20 x1,x2 0且為整數(shù)且為整數(shù)maxZ=x1+x21x2x 1 2 3 4 51523462x1+x2 = 64x1+5x2 = 20maxZA(5/3,8/3)32656543xx52121xxB(1,16/5)C(9/5,12/9)54545x421xxD(0,4)E(2,2)F(1,3)第三節(jié) 分支定界法一、分支定界法步驟二、示例第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃21maxxxz145114921xx31221xx且為整數(shù)0,21xxx x1

19、1x x2 25 54 43 32 21 1x x1 1+9/14x+9/14x2 2=51/14=51/14-2x-2x1 1 +x+x2 2=1/3=1/3maxmaxA(3/2,10/3)A(3/2,10/3)x1=1x1=1x1=2x1=2B BC C第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃LP2(CGE):LP2(CGE):C(2,23/9);Z=41/9C(2,23/9);Z=41/9LP1(BFD):LP1(BFD):B(1,7/3);Z=10/3B(1,7/3);Z=10/3不不可可能能區(qū)區(qū)域域x1x2maxABCx1=1x1=2EDFGMHLP21(HMEG):LP21(HMEG):M

20、(33/14,2);Z=61/14M(33/14,2);Z=61/14x1=3NLLP212(NEL):LP212(NEL):N(3,1);Z=4N(3,1);Z=4LP211(HG):LP211(HG):H(2,2);Z=4H(2,2);Z=436一、分支定界法步驟一、分支定界法步驟第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃1分支分支 假設松弛問題的最優(yōu)解不是整數(shù)解，則選擇一假設松弛問題的最優(yōu)解不是整數(shù)解，則選擇一個非整數(shù)分量構造兩個約束條件：個非整數(shù)分量構造兩個約束條件：iibx 1iibx分別加入松弛問題中，得到兩個子問題分別加入松弛問題中，得到兩個子問題LP1與與LP2, 即后繼問題，并求解之。即

21、后繼問題，并求解之。x1+9/14x2 51/14-2x1+x2 1/3x1 1x1,x2 0,且為整數(shù)且為整數(shù)maxZ=x1+x2LP1LP1x1+9/14x2 51/14-2x1+x2 1/3x1 2x1,x2 0,且為整數(shù)且為整數(shù)maxZ=x1+x2LP2LP237一、分支定界法步驟一、分支定界法步驟第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃2定界（以求極大值為例）定界（以求極大值為例） 以最優(yōu)目標函數(shù)值中最大者（針對沒有分支的以最優(yōu)目標函數(shù)值中最大者（針對沒有分支的線性規(guī)劃問題而言）為上界，以符合整數(shù)條件線性規(guī)劃問題而言）為上界，以符合整數(shù)條件的各子問題中目標函數(shù)值最大者作為下界。若的各子問題中目

22、標函數(shù)值最大者作為下界。若無整數(shù)解，在無整數(shù)解，在Z0的情況下，令的情況下，令Z=03比較與剪枝比較與剪枝若上界等于下界，則停止；否則，剪去小于若上界等于下界，則停止；否則，剪去小于下界的分支。對于大于下界的分支，繼續(xù)重復下界的分支。對于大于下界的分支，繼續(xù)重復（函數(shù)值較大的分支優(yōu)先）。（函數(shù)值較大的分支優(yōu)先）。38第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃X11X120 0z z6 62 29 9z z0 0z z9 94 41 1z zX22X230 0z z1 14 46 61 1z zX12X134 4z z4 4z zLP0S: X1=3/2；X2=10/3；Z0=29/6S2X1=1,X2=7

23、/3,Z =10/3LP1S1X1=2,X2=23/9,Z=41/9LP2S11X1=33/14,X2=2,Z =61/14LP21無可行解無可行解LP22S111X1=3,X2=1,Z =4LP211S112X1=2,X2=2,Z =4LP21239第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃使用范圍使用范圍:純整數(shù)、混合整數(shù)規(guī)劃純整數(shù)、混合整數(shù)規(guī)劃 9x1+7x2 567x1+20 x2 70 x1,x2 0,且為整數(shù)且為整數(shù)maxZ=40 x1+90 x2LPLP例例2:40第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃9x1+7x2 = 561 2 3 4 5 6 7 8 9x1x2123456787x1+20 x

24、2 =70maxZx1=4x1=5B(4,2.1);Z=349x2=2x2=3E(4,2);Z=340D(1.42,3);Z=327C(5,1.57);Z=341x2=1LP2(OGBH):BLP2(OGBH):BLP1(MKC):CLP1(MKC):CHMA(4.81,1.82)GOKF(5.44,1);Z=30841第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃X14X150 0z z3 3z z 560 0z z3 3z z 49X22X2340413 3z z3 3z zX21X2240403 3z z3 3z zLP0S: X1=4.81；X2=1.82；Z0=356S1X1=5,X2=1.57,Z

25、 =341LP1:CS2X1=4,X2=2.1,Z=349LP2 :BX1=4,X2=2,Z =340S21LP21 :EX1=1.42,X2=3,Z =327LP22 :DS11X1=5.44,X2=1,Z =308LP11 :FLP12無可行解無可行解第四節(jié) 0-1 整數(shù)規(guī)劃一、0-1變量及其應用二、0-1規(guī)劃的隱枚舉法第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃43注：決策時，如果要考慮某個特定方案是否被選取（即多個方案不一定全用），可以使用0-1變量。【例1】某公司欲在東、西、南三區(qū)建立門市部，共有7個門市部可供選擇。規(guī)定；在東區(qū)，由A1、A2、A3三個點中至多選兩個；在西區(qū)，由A4、A5兩點中至少

26、選一個；在南區(qū)，由A6、A7兩點中至少選一個。選用Ai點，投資為bi元，每年可獲利潤ci元，但投資總額不能超過B元。問應選擇哪幾個點可使年利潤最大？一、0-1變量及應用第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃44iiixcz71maxBxbiii712321xxx154xx176xx10或ix解：設10ixAi被選用Ai不被選用則問題變?yōu)榈谖逭碌谖逭?整數(shù)規(guī)劃整數(shù)規(guī)劃45【例2】含有相互排斥的約束條件問題120150100250工時限額（h/周）400.40.50.10.7A2250.20.30.20.3A1利潤（元件）B3方式1 方式2B2B1工時/件 工序產(chǎn)品第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃46 要求

27、B3 3只能從加工方式與中選擇一種，那么工廠應如何安排生產(chǎn)，才能使總利潤最大？設生產(chǎn)兩種產(chǎn)品分別為x1與x2件101y當工序B3選用加工方式，即滿足1505 . 03 . 021xx當工序B3不選用加工方式102y當工序B3 3選用加工方式，即滿足1204 . 02 . 021xx當工序B3 3不選用加工方式第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃4710,11204 . 02 . 01505 . 03 . 02121221121或yyyyMyxxMyxx101y1505 . 03 . 021xx當工序B3選用加工方式，即滿足當工序B3不選用加工方式102y1204 . 02 . 021xx當工序B3選

28、用加工方式，即滿足當工序B3不選用加工方式方式與中選擇一種等價于第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃4810,11204 . 02 . 01505 . 03 . 01001 . 02 . 02507 . 03 . 04025max2121221121212121或取yyyyMyxxMyxxxxxxxxz則數(shù)學模型為：第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃49該問題也可以令：10y當工序B3采用加工方式當工序B3采用加工方式則從兩種加工方式中選擇一種等價于：MyxxMyxx)1(1204.02.01505.03.02121第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃50一般情形下，如果有 P個約束條件，q個起作用njjij

29、pibxai1),2, 1(可以令：10iy當?shù)趇個起作用當?shù)趇個不起作用則問題轉(zhuǎn)化為：10111或者yqpyMybxapiinjijiji第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃51【例3】試利用0-1變量將下列各約束條件表示成一般的線性約束條件。221 xx83221xx或解： 設10y選第一個約束 選第二個約束則原命題等價于MyxxMyxx)1 (83222121第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃52x3只能取r1, r2, , rk中的一個。若x24,則x50；否則， x53設01iyx3取ri否則則1012122113或ikkkyyyyyryryrx設10y當x24；當x2 4 第五章第五章 整數(shù)

30、規(guī)劃整數(shù)規(guī)劃53則1 ,0)1(3)1(445522yMyxMyxMyxMyx（4）當變量可以取多個整數(shù)值時，可以用多個 0-1變量來表示， 例如， x9可以表示為 x=20y0+ 21y1 + 22y2 + 23y3 9 其中，y0, y1 , y2 ,y3是0-1變量。第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃54二、0-1規(guī)劃的隱枚舉法 枚舉法是解0-1規(guī)劃的一種算法。具體方法就是檢查每個變量等于0或1的所有組合。滿足所有約束條件，且使目標函數(shù)值達到最優(yōu)的組合就是0-1規(guī)劃的最優(yōu)解。 由于當0-1 變量有n個時，須檢查2n個變量組合，而當 n15時，這幾乎是不可能的。所以有人提出隱枚舉法。第五章第五

31、章 整數(shù)規(guī)劃整數(shù)規(guī)劃55 尋找一種方法，使問題在達到最優(yōu)解之前，僅須依次檢查所有可能變量組合的很少一部分。下面介紹兩種這樣的方法。求解步驟：【例4】求解321523maxxxxz)3 ,2, 1(1 ,064344223221321321ixxxxxxxxxxxi1 .隱枚舉方法的求解思路和方法第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃56、先找一個可行解,如（0,0,0)，并將其目標函數(shù)值z=0 作為下界；、由上步得出過濾條件 3x1- 2x2+ 5x30、對某種變量的組合，檢驗其是否滿足上述過濾條件，若滿足且又是可行解，則修改過濾條件。重復步驟3。第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃57第五章第五章 整數(shù)規(guī)

32、劃整數(shù)規(guī)劃0z5z8z321523maxxxxz(x2,x1,x3)Z值值約束條件約束條件過濾條件過濾條件(0,0,0)0(0,0,1)5(0,1,1)8(1,1,1)64,3,2,11 ,064344223221321321ixxxxxxxxxxxi58第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃注意注意: :上述計算步驟還可以進一步得到改善，即對極上述計算步驟還可以進一步得到改善，即對極大化問題，若將目標函數(shù)中大化問題，若將目標函數(shù)中x xj j的價值系數(shù)按遞增（不的價值系數(shù)按遞增（不減）的次序排列（求極小，價值系數(shù)按照遞減的次減）的次序排列（求極小，價值系數(shù)按照遞減的次序排列）。即序排列）。即則可知則

33、可知(0,0,1)(0,0,1)的目標值一定不小于的目標值一定不小于(0,1,0)(0,1,0)及及(1,0,0)(1,0,0)的目標值。同樣的目標值。同樣(0,1,1)(0,1,1)的目標值一定不小的目標值一定不小于于(1,1,0)(1,1,0)與與(1,0,1)(1,0,1)的目標值。故若的目標值。故若(0,0,0)(0,0,0)、(0,0,1)(0,0,1)、(0,1,1)(0,1,1)、(1,1,1)(1,1,1)都為可行解，則其他變都為可行解，則其他變量的組合可不必考慮。量的組合可不必考慮。312532maxxxxz第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃59第五節(jié)指派問題一、指問題的標準形式

34、及數(shù)學模型一、指問題的標準形式及數(shù)學模型二、匈牙利方法二、匈牙利方法三、非標準形式的指派問題三、非標準形式的指派問題601、指派問題（、指派問題（assignment problem)假定假定n個人去做個人去做n件事，并指定每人完成其中一項，每項件事，并指定每人完成其中一項，每項交給其中一個人去完成（即人與事一一對應交給其中一個人去完成（即人與事一一對應)，問應如何分，問應如何分配才能使完成這件事的總費用最少。配才能使完成這件事的總費用最少。2、標準形式的數(shù)學模型、標準形式的數(shù)學模型指派問題的系數(shù)矩陣指派問題的系數(shù)矩陣設第設第i人完成第人完成第j件事的費用為件事的費用為cij ，則稱，則稱一、

35、指派問題的標準形式及數(shù)學模型一、指派問題的標準形式及數(shù)學模型nnijcC)(第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃61為指派問題的系數(shù)矩陣（為指派問題的系數(shù)矩陣（coefficient matrix)或效率矩陣。或效率矩陣。令令01ijx指派第指派第i人做第人做第j件事件事不指派第不指派第i人做第人做第j件事件事則數(shù)學模型則數(shù)學模型為：為：ninjijijxcz11minniijnjx1),2, 1(1njij,n),(ix1211), 2, 1,(1 , 0njixij第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃62 可以可以看出：看出： 標準標準形式的指派問題是特殊的運輸問題形式的指派問題是特殊的運輸問題。也。

36、也是特殊是特殊的的0-1整數(shù)規(guī)劃問題。整數(shù)規(guī)劃問題。每一個可行解可用一個解矩陣表示每一個可行解可用一個解矩陣表示nnnnnnnnijxxxxxxxxxxX212222111211)(X中每行及每列都有且僅有一個，所以共有中每行及每列都有且僅有一個，所以共有! npnn個可行解。個可行解。第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃63第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃 1、思想依據(jù)、思想依據(jù)如果系數(shù)矩陣的所有元素如果系數(shù)矩陣的所有元素cij0 ，而其中存在，而其中存在n個位于不同個位于不同行不同列的零元素，則對應的指派方案總費用為零，從而行不同列的零元素，則對應的指派方案總費用為零，從而也一定是最優(yōu)的。也一定是

37、最優(yōu)的。如如0141208302323020939140C令令144322311xxxx二二、匈牙利方法、匈牙利方法64問題：如何產(chǎn)生或者尋找n個位于不同行不同列的零元素定理1、如果從分配問題的系數(shù)矩陣nnijcC)(的每行（或每列）各元素分別減去(或加上)一個常數(shù)，得到一個新的矩陣nnijcC)(則以C和C為系數(shù)矩陣的兩個指派問題有相同的最優(yōu)解（見下頁）。2、理論基礎（康尼格定理）第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃65第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃minZ= c11 x11+ c12 x12+ cnn xnnx11+ x12+ x1n =1.xn1+ xn2+ xnn =1x11+ x21+ x

38、n1 =1x1n+ x2n+ xnn =1xij =0或或1minZ(1)= (c11 k)x11+ (c12 k) x12+ (c1n k)x1n + c21 x21+ cnn xnnminZ(1) = c11 x11+ c12 x12+ cnn xnn -k(x11 + x12+ + x1n ) = c11 x11+ c12 x12+ cnn xnn -k66第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃651141143452115281417023090032217067第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃若矩陣若矩陣C的元素可分成的元素可分成“”與非與非“”兩兩部分，則覆蓋部分，則覆蓋“”元素的最少直線數(shù)

39、目，等元素的最少直線數(shù)目，等于位于不同行不同列于位于不同行不同列獨立零元素獨立零元素的最大個數(shù)。的最大個數(shù)。417023090032217068第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃1、變換系數(shù)矩陣、變換系數(shù)矩陣對各行元素分別減去該行中的最小元素，再對各列元素分別減對各行元素分別減去該行中的最小元素，再對各列元素分別減去該列中的最小元素。直到每行每列都有去該列中的最小元素。直到每行每列都有0元素為止。元素為止。61012961061476781296101417971215784C04630408101263037102081134004320405001232037710811030三、匈牙利方法步

40、驟三、匈牙利方法步驟69第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃在零元素最少的行（或列）開始，選擇一個在零元素最少的行（或列）開始，選擇一個0元素，并元素，并加上標記：加上標記：獨立零元素的含義是：它所在行的人，已經(jīng)不能再安排獨立零元素的含義是：它所在行的人，已經(jīng)不能再安排其他的事情做；它所在列的事（工作），已經(jīng)有人去做。其他的事情做；它所在列的事（工作），已經(jīng)有人去做。 如此反復，直到所有的零元素都被劃去為止。在此過程如此反復，直到所有的零元素都被劃去為止。在此過程中，若存在零元素的閉回路，可任選其中一個零元素加標記，中，若存在零元素的閉回路，可任選其中一個零元素加標記，同時劃去同行和同列中的其他零元素。同時劃去同行和同列中的其他零元素。2、在變換后的矩陣中確定獨立零元素、在變換后的矩陣中確定獨立零元素 同時，劃去此零元素所在行及其列的其他零元素。獲同時，劃去此零元素所在行及其列的其他零元素。獲標記的零元素稱為標記的零元素稱為獨立零元素獨立零元素。70第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃0432040500123203771081103071第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃3、覆、覆 蓋蓋(1)對沒有獨立零元素的行打?qū)]有獨立零元素的行打 。(2)在已打在已打 的行中的行中,對對 元素所在的列打