管理運(yùn)籌學(xué)03整數(shù)規(guī)劃

1、3.1 3.1 整數(shù)規(guī)劃問題及其建模整數(shù)規(guī)劃問題及其建模3.2 3.2 分支定界法分支定界法3.3 3.3 割平面法割平面法3.4 0-13.4 0-1型整數(shù)線性規(guī)劃的解法型整數(shù)線性規(guī)劃的解法3.5 3.5 指派問題指派問題3.6 3.6 整數(shù)規(guī)劃應(yīng)用整數(shù)規(guī)劃應(yīng)用第3章 整數(shù)規(guī)劃2整數(shù)規(guī)劃整數(shù)規(guī)劃：變量取整數(shù)的線性規(guī)劃；純整數(shù)規(guī)劃純整數(shù)規(guī)劃：所有變量都取整數(shù)的線性規(guī)劃；混合整數(shù)規(guī)劃：混合整數(shù)規(guī)劃：部分變量取整數(shù)的線性規(guī)劃；0-10-1規(guī)劃：規(guī)劃：所有變量都取0、1兩個值的規(guī)劃；0-10-1混合規(guī)劃：混合規(guī)劃：部分變量取0、1兩個值的規(guī)劃。例3-1背包問題 4線性規(guī)劃最優(yōu)解為: x1=0，x2=

2、0，x3=2.5而整數(shù)規(guī)劃的最優(yōu)解是 x1=1，x2=0，x3=2maxmaxs.t.s.t.z=z=17x17x1 110 x10 x1 1x x1 1, ,x x1 1, ,+72x+72x2 2+42x+42x2 2x x2 2, ,x x2 2, ,+35x+35x3 3+20 x+20 x3 3x x3 3x x3 3為整數(shù)為整數(shù)505000例3-2廠址選擇問題在n個地點(diǎn)中選r個（nr）建廠，在第i個地點(diǎn)建廠（i=1，2，n）所需投資為ii萬元，占地li畝，建成以后的生產(chǎn)能力為pi萬噸?，F(xiàn)在有總投資i萬元，土地l畝，應(yīng)如何選擇廠址，使建成后總生產(chǎn)能力最大。設(shè) 5整數(shù)規(guī)劃模型為:地建廠

3、表示在地不建廠表示在i1i0 xi1,0 xrxlxlixi. t .sxpzmaxin1iin1iiin1iiin1iii0-10-1規(guī)劃規(guī)劃例3-3 考慮固定成本的最小生產(chǎn)費(fèi)用問題 在最小成本問題中，設(shè)第j種設(shè)備的固定成本為 ，運(yùn)行的變動成本為 ，則生產(chǎn)成本與設(shè)備運(yùn)行時間的關(guān)系為：6000)(jjjjjjjxxcdxxf當(dāng)當(dāng)jdjcibija1 , 0, 0, 2 , 1, 2 , 1. .)(min11jjjjnjijijnjjjjjyxnjmyxmibxatsxcydz混合混合0-10-1規(guī)劃規(guī)劃設(shè)第j種設(shè)備運(yùn)行每小時可以生產(chǎn)第i種產(chǎn)品 件，而第i種產(chǎn)品定貨為 件。要滿足定貨同時使設(shè)備

4、運(yùn)行的總成本最小的問題為：7且為整數(shù)0,521964214. .4max21214121xxxxxxtsxxz0,521964214. .4max21214121xxxxxxtsxxz線性規(guī)劃整數(shù)規(guī)劃x*=（13/5，19/5）z*=89/5=17.8x*=（5，3）z*=17基本思想分支（branch）定界（bound）第3章 整數(shù)規(guī)劃80xbaxcxzmin0xixbaxcxzminrr01xixbaxcxzminrrx xr riir rx xr r ir+1分支（branch）這兩個子問題的可行域都是原線性規(guī)劃問題可行域的子集，這兩個子問題的最優(yōu)解的目標(biāo)函數(shù)值都不會比原線性規(guī)劃問題的最

5、優(yōu)解的目標(biāo)函數(shù)值更小。如果這兩個問題的最優(yōu)解仍不是整數(shù)解，則繼續(xù)選擇一個非整數(shù)的變量，繼續(xù)將這個子問題分解為兩個更下一級的子問題。這個過程稱為“分枝（branch）”。定界（bound）如果某一個子問題的最優(yōu)解是整數(shù)解，則它的目標(biāo)函數(shù)值可作為整數(shù)規(guī)劃最優(yōu)目標(biāo)函數(shù)值的上界。如果某一個子問題的解還不是整數(shù)解，但這個非整數(shù)解的目標(biāo)函數(shù)值已經(jīng)超過這個上界，那么這個子問題不必再進(jìn)行分枝。如果在分枝過程中得到新的整數(shù)解且該整數(shù)解的目標(biāo)函數(shù)值小于已記錄的上界，則用較小的整數(shù)解的目標(biāo)函數(shù)值代替原來的上界。上界的值越小，就可以避免更多不必要的分枝。確定整數(shù)解目標(biāo)函數(shù)值上界并不斷更新上界，并且不斷“剪除”目標(biāo)函數(shù)

6、值超過上界的分枝的過程，稱為定界（bound）。第3章 整數(shù)規(guī)劃9例例3-43-4 用分枝定界法求解以下整數(shù)規(guī)劃先求得相應(yīng)的線性規(guī)劃的最優(yōu)解，為第3章 整數(shù)規(guī)劃1012121212min235735. . 4936,0zxxxxs txxx x 且為整數(shù)17814,1762,1712321zxx11sub-6無可行解原問題原問題121 231 7621 781 41 7xxz sub-2121231731132xxz subxxsub-314142421zzxxsub-47214731,521zxxsub-55114153521zxxsub-714131521zzzx

7、xsub-914140721zzzxxsub-8731475621zxxsub-10無可行解x22x23x15x15x21x22x14x16x20 x21圖3-3. 探索過程示意圖14zz 1第3章 整數(shù)規(guī)劃12首先放棄變量的整數(shù)要求，求得線性規(guī)劃的最優(yōu)解。首先放棄變量的整數(shù)要求，求得線性規(guī)劃的最優(yōu)解。如果最優(yōu)解恰是一個整數(shù)解，則線性規(guī)劃的最優(yōu)解就是相如果最優(yōu)解恰是一個整數(shù)解，則線性規(guī)劃的最優(yōu)解就是相應(yīng)的整數(shù)規(guī)劃的最優(yōu)解。應(yīng)的整數(shù)規(guī)劃的最優(yōu)解。如果線性規(guī)劃的最優(yōu)解不是整數(shù)解，則要構(gòu)造一個新的約如果線性規(guī)劃的最優(yōu)解不是整數(shù)解，則要構(gòu)造一個新的約束，對線性規(guī)劃問題的可行域進(jìn)行切割，切除已經(jīng)得到的束

8、，對線性規(guī)劃問題的可行域進(jìn)行切割，切除已經(jīng)得到的線性規(guī)劃的最優(yōu)解，但保留原可行域中所有的整數(shù)解，求線性規(guī)劃的最優(yōu)解，但保留原可行域中所有的整數(shù)解，求解新的線性規(guī)劃問題解新的線性規(guī)劃問題如果最優(yōu)解仍不是整數(shù)解，再增加附加的約束將其切除，如果最優(yōu)解仍不是整數(shù)解，再增加附加的約束將其切除，但仍保持最初可行域中所有的整數(shù)解，如此一直進(jìn)行，直但仍保持最初可行域中所有的整數(shù)解，如此一直進(jìn)行，直至得到一個整數(shù)的最優(yōu)解為止。至得到一個整數(shù)的最優(yōu)解為止。第3章 整數(shù)規(guī)劃13設(shè)放棄變量整數(shù)要求得到的線性規(guī)劃的最優(yōu)單純形表如下：設(shè)放棄變量整數(shù)要求得到的線性規(guī)劃的最優(yōu)單純形表如下：設(shè)其中基變量設(shè)其中基變量xr的值的值

9、br不是整數(shù)，以不是整數(shù)，以i表示整數(shù)，以表示整數(shù)，以 f表表示正的真分?jǐn)?shù)，令示正的真分?jǐn)?shù)，令yrj = irj + frj (0 frj 1) r= i + f (0 f 1)將上面兩式代入將上面兩式代入約束約束r中，得中，得第6章 整數(shù)規(guī)劃14改寫成改寫成因此對于整數(shù)可行解，約束（因此對于整數(shù)可行解，約束（3-2）可以寫成更嚴(yán)格的不等式）可以寫成更嚴(yán)格的不等式這就是源于第這就是源于第 行的行的。 線性規(guī)劃的任何整數(shù)可行解都滿足這個約束；線性規(guī)劃的任何整數(shù)可行解都滿足這個約束；未切割掉未切割掉任何一個整數(shù)解。任何一個整數(shù)解。 線性規(guī)劃的非整數(shù)最優(yōu)解不滿足這個約束。線性規(guī)劃的非整數(shù)最優(yōu)解不滿足

10、這個約束。切割掉了非切割掉了非整的整的lp解解x；rrnmjjrjrjrfixfix1)(nmjjrjrrnmjjrjrxffixix11011nmjjrjrrnmjjrjrxffixix第3章 整數(shù)規(guī)劃15 2 若若xk的分量全為整數(shù)的分量全為整數(shù)，則，則xk即為原問題的最優(yōu)解，停止計算即為原問題的最優(yōu)解，停止計算； 否則根據(jù)否則根據(jù)xk的一個非整分量所在單純形表的那一行，譬如第的一個非整分量所在單純形表的那一行，譬如第 r 行，行， 構(gòu)造源于第構(gòu)造源于第 i行行的的給它引入一個弛變量給它引入一個弛變量 n+k+1， 得得 frj j + n+k+1 =-f-fj =m+1 - - 3 把這

11、個新約束添到最優(yōu)單純形表中，并增加一列把這個新約束添到最優(yōu)單純形表中，并增加一列( 即即 n+k+1列列 )，用對偶單純形法繼續(xù)迭代，求得一個新解，用對偶單純形法繼續(xù)迭代，求得一個新解xk+1， 令令k: = k+1，返，返2。 1 用單純形法求解用單純形法求解ip的伴隨的伴隨lp問題問題，得到其解得到其解x0，令，令k=0；n第6章 整數(shù)規(guī)劃16 min z = 3x1+4x23x1+x24x1+2x24 x1, , x20 x1, , x2 為整數(shù)s.t.例例3-53-5 試用割平面法求解以下整數(shù)規(guī)劃：試用割平面法求解以下整數(shù)規(guī)劃：解解 求解線性規(guī)劃得最優(yōu)單純形表求解線性規(guī)劃得最優(yōu)單純形表

12、選擇一個非整數(shù)的基變量，例如選擇一個非整數(shù)的基變量，例如 x x2 2=8/5=8/5，構(gòu)造約束條件，構(gòu)造約束條件(3-4(3-4） b2=8/5=1+3/5，i2=1，f2=3/5 y23=1/5=0+1/5，i23=0，f23=1/5 y24=-3/5=-1+2/5，i24=-1，f24=2/5附加的約束條件 為 3/5-（1/5x3+2/5x4）0即1/5x3+2/5x43/5將這個約束加到線性規(guī)劃的最優(yōu)單純形表中，并增加一個松弛變量x5, ,得下表得下表第3章 整數(shù)規(guī)劃17第3章 整數(shù)規(guī)劃18用對偶單純形法，用對偶單純形法，x5x5離基，離基，x3x3進(jìn)基進(jìn)基已獲得整數(shù)的最優(yōu)解：已獲得

13、整數(shù)的最優(yōu)解： x*=（2，1） z*=10為了得到切割約束1/5x3+2/5x43/5在（x1, x2）平面中的表達(dá)式，將其中的松弛變量x3，x4用x1，x2表示 x3=3x1+x2-4，x4=x1+2x2-4代入切割約束，得到 x1+x23這個切割過程的圖解如下圖第3章 整數(shù)規(guī)劃19整數(shù)規(guī)劃最優(yōu)解0123451234切割直線線性規(guī)劃最優(yōu)解隱枚舉法（implicit eumeration）例例3-6 3-6 用隱枚舉法求解下列問題 可行解：x=(1，0，0)，z=3 增加過濾條件（filtering constraint） 第3章 整數(shù)規(guī)劃201231231231213123max32522

14、44. .346,01zxxxxxxxxxstxxxxx x x或1233253xxx第3章 整數(shù)規(guī)劃21按價值系數(shù)從小到大排列max z=-2x2+3x1+5x3 -2x2+3x1+5x33 2x2+x1-x32 4x2+x1+x34 x2+x1 3 4x1+x36 第3章 整數(shù)規(guī)劃22點(diǎn)條件滿足條件？是（t）否（f）z（0 0 0）0f（0 0 1）5-1101t5第3章 整數(shù)規(guī)劃23點(diǎn)條件滿足條件？是（t）否（f）z（0 1 0）3f（0 1 1）80215t8點(diǎn)條件滿足條件？是（t）否（f）z（1 0 0）-2f（1 0 1）3f（1 1 0）1f（1 1 1）6f指派問題或分派問題（

15、指派問題或分派問題（assignment problemassignment problem）：）：需完成n項任務(wù)，恰好有n個人可承擔(dān)這些任務(wù)。各人完成任務(wù)的效率(或所費(fèi)時間) 不同。應(yīng)指派哪個人去完成哪項任務(wù)，使完成n項任務(wù)的總效率最高(或所需總時間最小)。例例3-5 3-5 甲、乙、丙、丁四人配送a,b,c,d四種貨物, 所需時間如下表所示。若一種貨物只交一人送貨，則應(yīng)指派何人配送何種貨物, 能使總的時間最少？第3章 整數(shù)規(guī)劃24工件工件工人工人abcd甲149415乙117910丙132105丁1791513效率矩陣設(shè)xij=1表示第 i人送j貨，否則xij=0 上述問題的模型為：第3章

16、 整數(shù)規(guī)劃251 , 04 , 2 , 114 , 2 , 11. .min41414141ijiijjijijijijxjxixtsxcz1 , 0, 0, 2 , 11, 2 , 11. .min1111ijijniijnjijninjijijxxnjxnixtsxcz一般指派問題的模型指派問題的求解方法指派問題的求解方法匈牙利法匈牙利法性質(zhì)性質(zhì)3-13-1. 若從系數(shù)矩陣(cij)的一行(列)各元素中分別減去該行(列)的最小元素，得到新矩陣(bij)，那么以(bij)為系數(shù)矩陣求得的最優(yōu)解和用原系數(shù)矩陣求得的最優(yōu)解相同 。性質(zhì)性質(zhì)3-23-2. 若一個方陣的一部分元素為0，另一部分元素不

17、為0，則覆蓋方陣內(nèi)所有0元素的最少直線數(shù)恰好等于獨(dú)立0元素（位于不同行，不同列的0元素）的最多個數(shù)。第3章 整數(shù)規(guī)劃26例3-7：匈牙利法的步驟一、系數(shù)矩陣經(jīng)變換，在各行各列中都出現(xiàn)一、系數(shù)矩陣經(jīng)變換，在各行各列中都出現(xiàn)0 0元素。元素。二、尋找獨(dú)立二、尋找獨(dú)立0 0元素元素最優(yōu)值為：z* =11+9+4+5=29第3章 整數(shù)規(guī)劃273004160408070200805646083801132041105109274131591751021310971115491416040807020080560010100000010100)(ijx甲甲cc，乙乙aa，丙丙dd，丁丁bb例3-5：先減列

18、元素獨(dú)立0元素的個數(shù)為3，小于矩陣的階數(shù)。第3章 整數(shù)規(guī)劃28542112510060255501007360008117606025550100731315917510213109711154914三、找出找出能覆蓋非最優(yōu)陣中所有能覆蓋非最優(yōu)陣中所有0 0元的元的最少直線集合最少直線集合第6章 整數(shù)規(guī)劃29(1) 對沒有對沒有 元的行打元的行打號；號；0 (2) 對打?qū)Υ蛱柕男猩纤刑柕男猩纤?元所在的列打元所在的列打號；號；0 (3) 對打?qū)Υ蛱柕牧猩纤刑柕牧猩纤?元所在的行打元所在的行打號；號；0 (4) 重復(fù)重復(fù)(2)、(3)步驟，直到找不出新的打步驟，直到找不出新的打 號的行、

19、列為止；號的行、列為止； (5) 對沒有打?qū)]有打號的行畫橫線，對所有打號的行畫橫線，對所有打號號 的列畫豎線，這就是能覆蓋所有的列畫豎線，這就是能覆蓋所有0元的最少元的最少 直線的集合。直線的集合。三、用最少的直線數(shù)覆蓋矩陣中的所有三、用最少的直線數(shù)覆蓋矩陣中的所有0 0元素元素第3章 整數(shù)規(guī)劃3025100602555010073四、增加矩陣中的四、增加矩陣中的0 0元素元素 在沒有被直線覆蓋的部分中找出最小元素。然后在打行各元素中都減去這最小元素，而在打列的各元素都加上這最小元素。 若得到n個獨(dú)立的0元素，則已得最優(yōu)解，否則回到第三步重復(fù)進(jìn)行。14000603444010074第3章 整

20、數(shù)規(guī)劃3125100602555010073最優(yōu)解可令可令 b bijij=m-c=m-cijij 。其中。其中m m是足夠大的常數(shù)是足夠大的常數(shù)( (如選（如選（c cijij）中）中最大元素為最大元素為m m即可即可) )，這時系數(shù)矩陣可變換為，這時系數(shù)矩陣可變換為b=(bb=(bijij) )第3章 整數(shù)規(guī)劃32ijijijxczmaxijijijijijijijijijijijijijijxcnmxcmxxcmxb)(目標(biāo)函數(shù)經(jīng)變換后，即解目標(biāo)函數(shù)經(jīng)變換后，即解ijijijxbzmin所得所得(b(bijij) )最小解即為原問題最小解即為原問題(c(cijij) )的最大解。的最大解。 例例3-83-8某航空公司是一家經(jīng)營小型飛機(jī)、短途航線的運(yùn)輸企業(yè)。管理層準(zhǔn)備拓展經(jīng)營領(lǐng)域，面臨的問題是：是采購更多的小型飛機(jī)來開辟一些新的短途航，還是開始通過為一些跨地區(qū)航線購買大型飛機(jī)來進(jìn)軍全國市場，或者兩種方法同時進(jìn)行，已知采購成本、年利潤、最多購買的數(shù)量限制如下表。并且可用資金為1億元，如何進(jìn)行決策，能使年利