運籌學(xué)第五章 整數(shù)規(guī)劃

1、整數(shù)規(guī)劃 整數(shù)規(guī)劃 v整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點 v解純整數(shù)規(guī)劃的割平面法* v分支定界法 v0-1型整數(shù)規(guī)劃* v指派問題 例1 某廠擬用集裝箱托運甲乙兩種貨物,每箱的體積、重量、 可獲利潤以及托運所受限制見下表.問每集裝箱中兩種貨物 各裝多少箱,可使所獲利潤最大? 1 整 數(shù) 規(guī) 劃的數(shù)學(xué)模型 一、問題的提出 貨物/箱體積/米3重量/百斤利潤/百元 甲5220 乙4510 托運限制/集 裝箱 2413 表 3. 1貨物/箱體積/米3重量/百斤利潤/百元 甲5220 乙4510 托運限制/集 裝箱 2413 解 設(shè) 分別為甲、乙兩種貨物的托運箱數(shù).則這是一個 純整數(shù)規(guī)劃問題 .其數(shù)學(xué)模型為

2、: 21,x x 21 1020maxxxZ 整數(shù), 0, 1352 2445 . 21 21 21 xx xx xx ts 在許多線性規(guī)劃問題中,要求最優(yōu)解必須取整數(shù).例如 所求的解是機(jī)器的臺數(shù)、人數(shù)車輛船只數(shù)等.如果所得的解 中決策變量為分?jǐn)?shù)或小數(shù)則不符合實際問題的要求. 且部分或全部為整數(shù) 或 n)1.2(j 0 )2 .1( . )min(max 1 1 j n j ijij n j jj x mibxa st xcZZ 二、整數(shù)規(guī)劃問題的數(shù)學(xué)模型 對于一個規(guī)劃問題,如果要求全部決策變量都取整數(shù), 稱為純(或全)整數(shù)規(guī)劃;如果僅要求部分決策變量取整數(shù), 稱為混合整數(shù)規(guī)劃問題.有的問題要

3、求決策變量僅取0或l兩 個值,稱為0-l規(guī)劃問題. 整數(shù)規(guī)劃簡稱為IP問題.這里主要討論的是整數(shù)線性規(guī) 劃問題,簡稱為ILP問題. 形線性規(guī)劃 混合整數(shù)線性規(guī)劃 純整數(shù)線性規(guī)劃 整數(shù)線性規(guī)劃問題 10 (pure integer linear programming) (mixed integer linear programming) (zero-one integer linear programming) 若不考慮整數(shù)條件，由余下的目標(biāo)函數(shù)和約束條件構(gòu)成 的規(guī)劃問題稱為該整數(shù)規(guī)劃問題的松弛問題（slack problem） 且部分或全部為整數(shù) 或 n)1.2(j 0 )2.1( . )m

4、in(max 1 1 j n j ijij n j jj x mibxa st xcZZ 整數(shù)線性規(guī)劃數(shù)學(xué) 模型的一般形式 n)1.2(j 0 )2.1( . )min(max 1 1 j n j ijij n j jj x mibxa st xcZZ或 該整數(shù)規(guī)劃問題的 松弛問題 三、整數(shù)規(guī)劃問題解的特點 對于整數(shù)線性規(guī)劃問題,為了得到整數(shù)解,初看起來,似乎只 要先不管整數(shù)要求,而求線性規(guī)劃的解,然后將求得的非整 數(shù)最優(yōu)解“舍零取整”就可以了.但實際上,這個想法卻常 常行不通,有時“舍零取整”后的整數(shù)解根本就不是可行解, 有的雖然為可行解,卻不是最優(yōu)解 . 例1 某廠擬用集裝箱托運甲乙兩種貨

5、物,每箱的體積、重量、 可獲利潤以及托運所受限制見下表.問每集裝箱中兩種貨物 各裝多少箱,可使所獲利潤最大? 貨物/箱體積/米3重量/百斤利潤/百元 甲5220 乙4510 托運限制/集 裝箱 2413 解 設(shè) 分別為甲、乙兩種貨物的托運箱數(shù).則這是一個 純整數(shù)規(guī)劃問題 .其數(shù)學(xué)模型為: 21,x x 21 1020maxxxZ 整數(shù), 0, 1352 2445 . 21 21 21 xx xx xx ts （1） 若暫且不考慮 取整數(shù)這一條件.則(1)就變?yōu)橄铝?線性規(guī)劃 : 21,x x 21 1020maxxxZ 0, 1352 2445 . 21 21 21 xx xx xx ts （

6、2） 我們將式(2)稱為(1)的松弛問題.解(2)得到最優(yōu)解: , 8 . 4 * 1 x, 0 * 2 x.96 * Z（3） 但它不滿足(1)的整數(shù)要求.因此它不是(1)的最優(yōu)解,若把 解(3)“舍零取整”,如取X1=(5,0)T,但它不是式(1)的可行 解. 因為它不滿足 (1) 中的約束條件。 若取X2=(4,0)T，X2是 (1) 的可行解, 但它卻不是(1) 的最優(yōu)解, 因 為當(dāng)X2=(4,0)T 時,Z2 = 80, 但當(dāng)X3 = (4,1)T 時,Z3 = 90 Z2。 即伴隨規(guī)劃的最優(yōu)解通過 “ 舍零取整 ” 得到的X1,X2 都不是 (1) 的最優(yōu)解 .因此通過松弛問題最優(yōu)

7、解的 “ 舍零取 整 ” 的辦法 , 一般得不到原整數(shù)規(guī)劃問題的最優(yōu)解 . 對上面的問題，我們從幾何的角度來觀察： 若松弛問題(2)的可行域 K 是有界的,則原整數(shù)規(guī)劃(1)的可行 域 K 0應(yīng)是K中有限個格點(整數(shù)點）的集合.見圖1, 圖中 “* 為整數(shù)點(格點). 圖1 中四邊形 OABC 是松弛 問題(2)的可行域.它的最優(yōu)解 為 C 點(4.8, 0)。 而 (1) 的可行域為k0 = (0,0),(0,1), (0,2), (1,0),(1, l),(1,2), (2,0), (2,1),(3,0), (3,1),(4,0),(4, l) . 將C點“舍零取整”后得到的 X1=(5.

8、0,0)T不在 K0中,而X2=(4,0)T在K0中,但不是(1)的最優(yōu) 解,最優(yōu)解在B點左側(cè)（4，1）。 1 12348 . 4 2 1 x 2 x A C B O 當(dāng)然, 我們也會想到能否用“窮舉法”來求解整數(shù)規(guī)劃.如(1) 問題,將 K0 中所有整數(shù)點的目標(biāo)函數(shù)值都計算出來,然后逐 一比較找出最優(yōu)解.這種方法對變量所能取的整數(shù)值個數(shù)較少 時,勉強(qiáng)可以應(yīng)用.如本例 可取 0,1,2,3,4共5個數(shù)值。 而 只能取0,1,2共三個數(shù)值,因此其組合最多為15個(其中 有不可行的點). 1 x 2 x 但對大型問題,這種組合數(shù)的個數(shù)可能大得驚人! 如在指派 問題中,有n 項任務(wù)指派n個人去完成,

9、不同的指派方案共有 n! 種 .當(dāng) n=20 時 ,這個數(shù)超過21018. 如果用窮舉法每 一個方案都計算一遍 , 就是用每秒百萬次的計算機(jī),也要 幾萬年 . 顯然 “窮舉法” 并不是一種普遍有效的方法 因此研究求解整數(shù)規(guī)劃的一般方法是有實際意義的. 窮舉法 舍零取整 求解整數(shù)規(guī)劃 整數(shù)規(guī)劃解的特點 整數(shù)線性規(guī)劃及其松弛問題，從解的特點上來說，二者之 間既有密切的聯(lián)系，又有本質(zhì)的區(qū)別。 松弛問題作為一個線性規(guī)劃問題，其可行解的集合是一個 凸集，任意兩個可行解的凸組合仍為可行解。 整數(shù)規(guī)劃問題的可行解集合是它的松弛問題可行解集合的 一個子集，任意兩個可行解凸組合不一定滿足整數(shù)約束條 件，因而不一

10、定仍為可行解。 由于整數(shù)規(guī)劃問題的可行解是其松弛問題的可行解的子集， 所以，其松弛問題的最優(yōu)解目標(biāo)函數(shù)值是整數(shù)規(guī)劃問題目標(biāo) 函數(shù)值的上界。 在一般情況下，松弛問題的最優(yōu)解不會剛好滿足變量 的整數(shù)約束條件，因而不是整數(shù)規(guī)劃的可行解，自然也不 是整數(shù)規(guī)劃的最優(yōu)解。 1 12348 . 4 2 1 x 2 x A C B O 但松弛問題的最優(yōu)解恰好滿足變量的整數(shù)約束條件，那么 它必然同時是整數(shù)規(guī)劃問題和其松弛問題的最優(yōu)解。 目前，常用的求解整數(shù)規(guī)劃的方法有：目前，常用的求解整數(shù)規(guī)劃的方法有： l 分支定界法和割平面法；分支定界法和割平面法； l 對于特別的對于特別的01規(guī)劃問題采用隱枚舉法和匈牙利法

11、。規(guī)劃問題采用隱枚舉法和匈牙利法。 自20世紀(jì)60年代以來, 已發(fā)展了一些常用的解整數(shù)規(guī)劃的算 法,如各種類型的割平面法、分枝定界法、解 0-1 規(guī)劃的隱枚 舉法、分解方法、群論方法、動態(tài)規(guī)劃方法等等。 近十年來有人發(fā)展了一些近似算法及用計算機(jī)模擬法,也取得 了較好的效果 . 背景 1 1 max 1,2. .01,2. 1,2,. n jj j n ijji j j j Zc x a xbim s txjn xjn 取整數(shù) 2 解純整數(shù)規(guī)劃的割平面法 考慮純整數(shù)規(guī)劃問題 純整數(shù)規(guī)劃的松弛問題是一個線性規(guī)劃問題，可用單純形法求解。 在松弛問題的最優(yōu)單純形表中，記Q為m個基變量的下標(biāo)集合，K 為

12、n-m個非基變量的下標(biāo)集合，則m個約束方程可示為： Qibxaxij Kj iji 5.4式 而對應(yīng)的最優(yōu)解X*=(x1*,x2*, ,xn*)，其中 Kj Qjb x j j 0 * 若各 皆為整數(shù)，則X* 滿足整數(shù)約束，因 而就是純整數(shù)規(guī)劃的最優(yōu)解；若 不全為整數(shù)， 則 X* 不滿足整數(shù)約束，因而就不是純整數(shù)規(guī)劃的可行解， 自然也不是該整數(shù)規(guī)劃的最優(yōu)解。 )(Qjbj )(Qjbj 割平面法的基本思想： 用割平面法(cutting plane approach)解整數(shù)規(guī)劃時，若 其松弛問題的最優(yōu)解不滿足整數(shù)約束，則從X*的非整分 量中選取一個，用以構(gòu)造一個線性約束條件，將其加入 原松弛問題

13、中，形成一個新的線性規(guī)劃，然后求解之。 若新的最優(yōu)解滿足整數(shù)要求，則它就是整數(shù)規(guī)劃的最優(yōu) 解；否則重復(fù)上述步驟，直到獲得整數(shù)最優(yōu)解為止。 為最終獲得整數(shù)最優(yōu)解，每次增加的線性約束條件應(yīng)當(dāng)具備 兩個基本性質(zhì)： 已獲得的不符合整數(shù)要求的松弛問題最優(yōu)解不滿足該線性 約束條件，從而不可能在以后的解中再出現(xiàn)。 凡整數(shù)可行解均滿足該線性約束條件，因而整數(shù)最優(yōu)解始 終被保留在每次形成的松弛問題（線性規(guī)劃）可行域中。 我們應(yīng)該怎樣構(gòu)造新的約束條件？ 為此，若 不是整數(shù)，在（5.4）中對應(yīng)的約 束方程為 Qibxaxij Kj jii 00 )( 0 0 Qib i 其中 按假設(shè)不是整數(shù)； 可能是整數(shù)，也 可能

14、不是整數(shù)。 0 i b )( 0 Kja ji 0 i b ji a 0 10, )( 10, 000000 000000 ijiiiiji jijijijijiji fbNfNb KjfaNfNa 其中 其中 5.6式 5.7式 5.8式 分解 和 成兩部分。一部分是不超過該數(shù)的最大整數(shù)， 另一部分是余下的小數(shù)即 將（5.7）和（5.8）式代入（5.6）式，移項以后得： KjKj jjiiijjii xffNxNx 00000 5.9式 對5.9式分別討論當(dāng)前解（非整數(shù)解）和可行域中整數(shù)解的情況： 對于當(dāng)前解5.9式右端有 10 00 Kj jjii xff 對于整數(shù)解5.9式左端表明 為整

15、數(shù)，又因為 本身不能 1，故 Kj jjii xff 00 Kj jjii xff 00 0 00 Kj jjii xff 由此我們以 （5.10式）作為標(biāo)尺來， 將當(dāng)前不滿足整數(shù)約束的最優(yōu)解去掉，而完全保留了原整 數(shù)規(guī)劃問題的可行解。 0 00 Kj jjii xff 綜上所述，線性約束條件(5.10)式具備上述的兩個性 質(zhì)。將其與原整數(shù)規(guī)劃的松弛問題合并，構(gòu)成一個新的 線性規(guī)劃。 記R為原松弛問題可行域，R為新的線性規(guī)劃可行域。 從幾何意義上看，(5.10)式實際上對R做了一次“切割”， 在留下的R 中，保留了整數(shù)規(guī)劃的所有可行解，但不符合 整數(shù)要求的X*被“切割”掉了。隨著“切割”過程的

16、不斷 繼續(xù)，整數(shù)規(guī)劃最優(yōu)解最終有機(jī)會成為某個線性規(guī)劃可行 域的頂點，作為該線性規(guī)劃的最優(yōu)解而被解得。 割平面法在1958年由高莫瑞（R.E.Gomory）首先提 出，故又稱Gomory割平面法。在割平面法中，每次增加 得用于“切割”的線性約束稱為割平面約束或Gomory約 束. 構(gòu)造割平面約束的方法很多，但（5.10）式是最常 用的一種，它可以從相應(yīng)線性規(guī)劃的最終單純形表中直 接產(chǎn)生。 實際解題時，經(jīng)驗表明若從最終單純行表中選擇具有最 大分?jǐn)?shù)部分的非整分量所在行構(gòu)造割平面約束，往往可 以提高“切割”效果，減少“切割”次數(shù) 例：用割平面法求解整數(shù)規(guī)劃問題 且為整數(shù)且為整數(shù)0, 023 623 m

17、ax 21 21 21 2 xx xx xx xZ 解：增加松弛變量x3和x4 ，得到(LP)的初始單純形表和最優(yōu)單純 形表： Cj0100 CBXBbx1x2x3x4 0 x363210 0 x40-3201 j 0100 Cj0100 CBXBbx1x2x3x4 0 x11101/6-1/6 1x23/2011/41/4 j 00-1/4 -1/4 割平面約束： 34 111 442 xx 加入割平面約束后得到的新的線性規(guī)劃問題為： 0, 2 1 4 1 4 1 023 623 max 54321 543 421 321 2 xxxxx xxx xxx xxx xZ 我們可用使用單純行法從

18、頭開始解這個線性規(guī)劃問題。 但更簡便的方法是使用對偶單純形法： 將生成的割平面條件加入松弛變量，然后加到表中 2 1 4 1 4 1 43 xx割平面約束： 2 1 4 1 4 1 543 xxx Cj01000 CBXBbx1x2x3x4x5 0 x11101/6-1/60 1x23/2011/41/40 0 x5-1/200-1/4-1/41 j 00-1/4-1/40 CBXBbx1x2x3x4x5 0 x12/3100-1/32/3 1x2101001 0 x320011-4 j 0000-1 將 x3=6-3x1-2x2 , x4=3x1-2x2 ,帶入 中，得到等價的割平面條件：

19、x21 見下圖。 2 1 4 1 4 1 43 xx x1 x2 3 3 第一個割平面第一個割平面 此時，X1 (2/3, 1), Z=1,仍不是整數(shù)解。繼續(xù)以x1為源行生成 割平面，其條件為： 3 2 3 2 3 2 54 xx 將生成的割平面條件加入松弛變量，然后加到表中： 3 2 3 2 3 2 654 xxx CBXBbx1x2x3x4x5x6 0 x12/3100-1/32/30 1x21010010 0 x320011-40 0 x6-2/3000-2/3-2/31 j -10000-10 CBXBbx1x2x3x4X5x6 0 x10100-101 1x20010-103/2 0

20、 x3600150-6 0 x5100011-3/2 j 000010-3/2 CBXB bx1x2x3x4s1s2 0 x1110001-1/2 1x21010010 0 x310010-53/2 0 x4100011-3/2 Z -10000-10 至此得到最優(yōu)表，其最優(yōu)解為 X= (1 , 1) , Z = 1, 這也是原 問題的最優(yōu)解。 3 2 3 2 3 2 54 xx 等價的約束割平面條件為x1 x2 x1 x2 3 3 第一個割平面第一個割平面 第二個割平面第二個割平面 3 分枝定界法 v在20世紀(jì)60年代初 Land Doig 和 Dakin 等人提出了分枝定 界法.由于該方法

21、靈活且便于用計算機(jī)求解,所以目前已成為 解整數(shù)規(guī)劃的重要方法之一。 v適用范圍：分枝定界法既可用來解純整數(shù)規(guī)劃,也可用來 解混合整數(shù)規(guī)劃. 分枝定界法由來： 混合整數(shù)規(guī)劃問題一般有無限多個可行解。即使是純整 數(shù)規(guī)劃問題，隨著問題規(guī)模的擴(kuò)大，其可行解的數(shù)目也將急 劇增加。因此通過枚舉全部可行解，并從中篩選出最優(yōu)解的 算法無實際應(yīng)用價值。 分枝定界法（branch and bound）是一種隱枚舉或部分枚 舉法，是在枚舉法基礎(chǔ)上的改進(jìn)。分枝定界法的關(guān)鍵是分枝 和定界。 分枝定界法的基本思想：( 分枝和定界的思想) 若整數(shù)規(guī)劃的松弛問題的最優(yōu)解不符合整數(shù)要求，假 設(shè) 不符合整數(shù)要求， 是不超過 的最

22、大整數(shù)， 則構(gòu)造兩個約束條件 。分別將 其并入上述松弛問題中，從而形成兩個分枝，即兩個后續(xù) 問題。 i b i b i b 1 iiii bxbx和 這就是所謂分枝。 兩個后續(xù)問題的可行域中包含原整數(shù)規(guī)劃問題的所有 可行解。而在原松弛問題可行域中，滿足 的一部分區(qū)域在以后的求解過程中被遺棄了，讓而它不包 含整數(shù)規(guī)劃的任何可行解。根據(jù)需要，各后續(xù)問題可用類 似地產(chǎn)生自己的分枝，即自己的后續(xù)問題。 1 iii bxb “分枝”為整數(shù)規(guī)劃最優(yōu)解的出現(xiàn)創(chuàng)造了條件 * * (4,4) 35 X Z * * (5,3) 20 X Z 什么是定界： 所謂“定界”，是在分枝過程中，若某個后續(xù)問題的最 優(yōu)解恰巧

23、獲得整數(shù)規(guī)劃問題的一個可行解（即其解滿足整數(shù) 約束），那么，它的目標(biāo)函數(shù)值就是一個“界限”，可作為 衡量處理其他分枝的一個依據(jù)。 因為整數(shù)規(guī)劃問題的可行解集是其松弛問題的可行解集 的一個子集，所以其松弛問題的最優(yōu)解目標(biāo)函數(shù)值是原整數(shù) 規(guī)劃問題的上界。所以，對于那些相應(yīng)松弛問題最優(yōu)解的目 標(biāo)函數(shù)值比上述“界限”值差的后續(xù)問題，就可以剔除而不 再考慮。 當(dāng)然，如果在以后的分枝過程中出現(xiàn)了更好的“界限”， 則以它來取代原來的界限，這樣可以提高定界的效果。 “定界”則可用提高搜索的效率 * * (4,4) 35 X Z * * (5,3.17) 20 X Z “分枝”為整數(shù)規(guī)劃最優(yōu)解的出現(xiàn)創(chuàng)造了條件，

24、 而“定界”則可用提高搜索的效率。 下面，通過例子來闡明分枝定界法的基本思想和一般步驟: 例 求解整數(shù)規(guī)劃問題 12 12 12 1,2 12 m ax57 72484 3218 . . 0 , Zxx xx xx s t x x xx 為 整 數(shù) 解：去掉整數(shù)要求，得其相應(yīng)得線性規(guī)劃（在分枝定界法中， 將此記為B，稱其為原整數(shù)規(guī)劃A的松弛問題）： 12 12 12 1,2 m ax57 72484 .3218 0 Zxx xx s txx x x 用任一種方法解問題B得最優(yōu)解和最優(yōu)值為： x1=4.55, x2=2.17, Z=37.97 B的可行解集記為R0,如圖所示： A(4.55,2.

25、17) Y 軸 612 9 4 3 上面B的最優(yōu)解不滿足整數(shù)要求，即不是整數(shù)規(guī)劃的最 優(yōu)解。為尋求原整數(shù)規(guī)劃的最優(yōu)解，我們把B劃分為兩 個子問題（分枝）。 任選一個不滿足整數(shù)約束的變量，這里我們?nèi)1 構(gòu)造兩個約束條件： 在B中分別增加上述約束條件，得到B的兩個子問題： 54 11 xx和 0 4 1823 84327 . 75max 2,1 1 21 21 21 xx x xx xx ts xxZ 0 5 1823 84327 . 75max 2,1 1 21 21 21 xx x xx xx ts xxZ 問題問題 x1=4, x2=2.33, Z= 36.33x1=5, x2=1.5,

26、Z= 35.5 此時，B的可行解被分成了三個部分，即問題的可行解 R1, 問題的可行解R2，以及不含整數(shù)可行解的4x15的 部分 Y 軸 612 9 4 3 4 5 LP1 x1=4, x2=2.33 Z(1) 36.33 LP x1=4.55, x2=2.17 Z(0) 37.97 LP2 x1=5, x2=1.5 Z(2) 35.5 x14x15 整個求解過程 問題B 問題 問題 由于問題和問題的最優(yōu)解仍不滿足整數(shù)要求，則把和 繼續(xù)進(jìn)行類似的劃分。 由于的最優(yōu)值較大，則其包含原整數(shù)規(guī)劃最優(yōu)解的可能 形更大些，因此先分解。在中分別增加約束條件 得到的兩個子問題和。 32 22 xx和 0 4

27、 1823 84327 . 75max 2,1 1 21 21 21 xx x xx xx ts xxZ 問題 在中分別增加 兩個約束，得到的兩個子問 題和 32 22 xx和 0 2 4 1823 84327 . 75max 2,1 2 1 21 21 21 xx x x xx xx ts xxZ 0 3 4 1823 84327 . 75max 2,1 2 1 21 21 21 xx x x xx xx ts xxZ 問題問題 x1=4, x2=2, Z=34x1=1.71, x2=3, Z=29.57 Y 軸 612 9 4 3 4 5 2 此時，問題1的可行域被分成三部分，即的可行集R

28、3, 的可行解集R4，以及不含整數(shù)可行解的2x2 34，即的 可行解集中還有可能含有原整數(shù)規(guī)劃的最優(yōu)解（比 的最優(yōu)解目標(biāo)函數(shù)值大的整數(shù)解）。 21 22 xx和因此需要考察問題，分別增加約束條件 得到問題的兩個子問題和 0 5 1823 84327 . 75max 2,1 1 21 21 21 xx x xx xx ts xxZ 問題 0 1 5 1823 84327 . 75max 2,1 2 1 21 21 21 xx x x xx xx ts xxZ 0 2 5 1823 84327 . 75max 2,1 2 1 21 21 21 xx x x xx xx ts xxZ 問題 問題 引

29、入約束 21 22 xx和 x1=5.33, x2=1,Z=33.67無可行解 問題的可行域R5 問題無可行解 此時，問題的可行域被分成兩部分部分，即的可行集 R5,和不含整數(shù)可行解的1x2所有分 枝末梢的Z值，則得最優(yōu)解。否則， 取Z值最大的非整數(shù)解， 繼續(xù)分解，Go to 3 ii xb 1 iiji xbxb 和 LP1 x1=4, x2=2.33 Z(1) 36.33 LP x1=4.55, x2=2.17 Z(0) 37.97 LP2 x1=5, x2=1.5 Z(2) 35.5 x14 x15 問題問題 x22x13x21 x22 LP3 x1=4, x2=2 Z(3) 34 LP

30、4 x1=1.71, x2=3 Z(4) 29.57 LP5 x1=5.33, x2=1 Z(5) 33.67 LP6 無可行解無可行解 練習(xí) 例：用分枝定界法求解整數(shù)規(guī)劃問題（可用圖解法求解） 且且為為整整數(shù)數(shù)0, 1432 92 )( 23max 21 21 21 21 xx xx xx IP xxZ 樹形圖如下：樹形圖如下： LP1 x1=7/2, x2=2 Z(1)29/2=14.5 LP x1=13/4, x2=5/2 Z(0) 59/4=14.75 LP2 x1=5/2, x2=3 Z(2)27/2=13.5 LP3 x1=3, x2=2 Z(3) 13 LP4 x1=4, x2=

31、1 Z(4) 14 x22x23 x13x14 3 0-1型整數(shù)規(guī)劃 一、 0-1變量及其應(yīng)用 若變量只能取0或1，則稱其為0-1變量。 0-1變量作為邏輯變量(logical variable),常被用來表示系統(tǒng)是 否處于某個特定狀態(tài)，或者決策時是否取某個特定方案。例如 0 1 x P 當(dāng)決策取方案P時 當(dāng)決策不取方案P時（即取 時） 0 1 j x 若Ej選擇Aj 若Ej選擇 jA J=1,2,n 那么，向量(x1,x2,xn)就描述了問題的特定狀態(tài)或方案即： T nn T T nn T T nn T T nn T T n AAAA AAAA AAAA AAAA xxx ),.,(,)0

32、, 0,.0 , 0( ),.,(,)0 , 0,.0 , 1 ( ),.,(,)0 , 1,.1 , 1 ( ),.,(,) 1 , 1,.1 , 1 ( ),.,( 121 121 12 121 21 1 若選擇 若選擇 若選擇 若選擇 當(dāng)問題含有多項要素，而每項要素皆有兩種選擇時，可用一組 0-1變量來描述。一般地，設(shè)問題有有限項要素E1,E2,En,其中 每項Ej有兩種選擇Aj和 ，則可令 j A 投資場所選擇問題 某城市擬在其東、西、南三個區(qū)域設(shè)立郵局，各地區(qū)都由幾 個具體的地點可供選擇。 要求不超過總投資100萬元的條件下，建立盈利最大化0-1 規(guī)劃。 地區(qū)東區(qū)西區(qū)南區(qū)約束 地點A

33、1 A2A3 A4 A5A6 A7 投資B1 B2B3 B4 B5B6 B7100萬元 盈利C1 C2C3 C4 C5C6 C7 選點數(shù) 121 分析：令xj(j1,2.7)為0-1變量 二、 0-1 整數(shù)規(guī)劃舉例 其數(shù)學(xué)模型為： ).2, 1(10 1 2 1 100 . max 76 543 21 7 1 7 1 njx xx xxx xx xB ts xCZ j i ii i ii 或 在應(yīng)用中，有時會遇到變量可以取多個整數(shù)值的問題。 這時，利用0-1變量是二進(jìn)值變量（binary variable）的 性質(zhì)，可以用一組0-1變量來取代該變量。 例如，變量x可取09之間的任意整數(shù)時，可令

34、 92222 3 3 2 2 1 1 0 0 xxxxx 其中x0,x1,x2,x3皆為01變量 0-1變量不僅廣泛應(yīng)用于科學(xué)技術(shù)問題，在經(jīng)濟(jì)管理問題 中也有十分重要的應(yīng)用 1互斥問題 2 固定費用問題 3 工件排序問題 含有相互排斥的約束條件的問題 假設(shè)工序B的每周工時約束條件為 現(xiàn)在假設(shè)工序B還有一種新的加工方式，相應(yīng)的每周工時 約束變成: 如果工序B只能從兩種加工方式中選擇一種，那么（1）式 和（2）式就成為兩個相互排斥的約束條件。為了統(tǒng)一在 一個問題中，就需要 引入01變量 ）（11505 . 03 . 0 21 xx ）（21205 . 02 . 0 21 xx 1 0 2 y 1

35、0 1 y 工序B采用原加工方式 工序B不采用原加工方式 工序B采用新加工方式 工序B不采用新加工方式 于是，通過引入0-1變量，可以將相互排斥的約束條件(1)和 (2)統(tǒng)一起來： ）（ ）（ ）（ 51 41204 . 02 . 0 31505 . 03 . 0 21 2221 1121 yy yMxx yMxx 其中M1和M2都是充分大的數(shù)。由于（5）式?jīng)Q定了y1和y2中 必定有一個是1，另一個是0（互斥條件）。 若y1=1，而y2=0，即采用新的加工方式。此時由于M1是一個 充分大的數(shù)，則(3)式無效。 反之，若y1=0,而y2=1，即采用原加工方式。此時由于M2是一 個充分大的數(shù)，則(

36、4)式無效。 一般地，若需要從p個約束條件 ).2, 1( 1 pibxa i n j jij 中恰好選擇q個約束條件，則可用引入p個0-1向量 1 0 i y 若選擇第i個約束條件 若不選擇第i個約束條件 那么，約束條件組 p j i iii n j jij qpy yMbxa 1 1 就可用達(dá)到這個目的。因為上述約束條件組保證了在p個0-1變 量中有p-q個為1，q個為0。 凡取0值的yi對應(yīng)的約束條件即為原約束條件，而取1的yi對應(yīng)的 約束條件無效。 固定費用問題 有三種資源被用于生產(chǎn)三種產(chǎn)品，資源量、產(chǎn)品單件費 用及售價、資源單耗量及組織三種產(chǎn)品生產(chǎn)的固定費用 見下表。要求定制一個生產(chǎn)

37、計劃，使總收益最大。 IIIIII資源量 A248500 B234300 C123100 單件費用456 單件售價81012 固定費用100150200 建模碰到的困難主要是事先不能確切知道某種產(chǎn)品是否生產(chǎn)， 因而不能確定相應(yīng)的固定費用是否發(fā)生 下面借助0-1變量解決這個困難 設(shè)xj是第j種產(chǎn)品的產(chǎn)量, j=1,2,3;再設(shè) 0 1 i y 生產(chǎn)第 j 種產(chǎn)品(即xj 0) 不生產(chǎn)第 j 種產(chǎn)品(即xj 0) 則問題的整數(shù)規(guī)劃數(shù)學(xué)模型是： 3 , 2 , 1, 10 3 , 2 , 1,0 10032 300432 500842 . . 200150100)612() 510()48(max

38、333 222 111 321 321 321 321321 jy jx yMx yMx yMx xxx xxx xxx ts yyyxxxZ j j 或 且為整數(shù) 如果生產(chǎn)第j種產(chǎn)品，則其產(chǎn)量xj 0。此時由約束條件xj Mjyj， 知yj=1。因此相應(yīng)的固定費用在目標(biāo)函數(shù)中將被考慮。 如果不生產(chǎn)第j種產(chǎn)品，則其產(chǎn)量xj = 0,此時由約束條件xj Mjyj可 知，yj可以是0也可以是1。但yj=1不利于目標(biāo)函數(shù)的最大化，因 而在問題的最優(yōu)解中必然是yj=0，從而相應(yīng)的固定費用將不再被 考慮 工件排序問題 用4臺機(jī)床加工3件產(chǎn)品。各產(chǎn)品的機(jī)床加工順序，以及產(chǎn) 品 i 在機(jī)床 j 上的加工工時

39、 aij 見下表 產(chǎn)品產(chǎn)品1a11 a13 a14 機(jī)床機(jī)床1 機(jī)床機(jī)床3 機(jī)床機(jī)床4 產(chǎn)品產(chǎn)品2a21 a22 a24 機(jī)床機(jī)床1 機(jī)床機(jī)床2 機(jī)床機(jī)床4 產(chǎn)品產(chǎn)品3 a32 a33 機(jī)床機(jī)床2 機(jī)床機(jī)床3 由于某種原因，產(chǎn)品2的加工總時間不得超過d，現(xiàn)要求確定各件 產(chǎn)品在機(jī)床上的加工方案，使在最短的時間內(nèi)加工完全部產(chǎn)品。 解：設(shè) xij 表示產(chǎn)品 i 在機(jī)床 j 上開始加工的時間(i=1,2,3;j=1,2,3,4) 下面將逐步列出問題的整數(shù)規(guī)劃模型 1、同一件產(chǎn)品在不同機(jī)床上的加工順序約束 對于同一件產(chǎn)品，在下一臺機(jī)床上加工的開始時間不得早于在 上一臺機(jī)床上加工的約束時間，故應(yīng)有： 產(chǎn)品

40、產(chǎn)品1：及及 xax 141313 xax 131111 產(chǎn)品產(chǎn)品2：及及 xax 242222 xax 222121 產(chǎn)品產(chǎn)品3： xax 333232 2、每一臺機(jī)床對不同產(chǎn)品的加工順序約束 一臺機(jī)床在工作中，如已開始的加工還沒有結(jié)束，則不能 開始另一件產(chǎn)品的加工。對于機(jī)床1，有兩種加工順序。或 先加工產(chǎn)品1，后加工產(chǎn)品2；或反之。對于其它3臺機(jī)床 ，情況也類似。為了容納兩種相互排斥的約束條件，對于 每臺機(jī)床，分別引入0-1變量 )4 , 3 , 2 , 1( 1 0 j y j 先加工另一件產(chǎn)品 先加工某件產(chǎn)品 則每臺機(jī)床上的加工產(chǎn)品的順序可用下列四組約束條件來保證： 機(jī)床1：及 )1

41、( 1 112121 yM xax yM xax 1 211111 機(jī)床2：及 )1 ( 2 223232 yM xax yM xax 2 322222 機(jī)床4：及 )1 ( 4 142424 yM xax yM xax 4 241414 機(jī)床3：及 )1 ( 3 133333 yM xax yM xax 3 331313 各yj的意義是明顯的。如當(dāng)y1=0時，表示機(jī)床1先加工產(chǎn)品1， 后加工產(chǎn)品2，當(dāng)y1=1時，表示機(jī)床1先加工產(chǎn)品2，后加工產(chǎn) 品1。 3、產(chǎn)品2的加工時間約束 產(chǎn)品2的開始加工時間是x21，結(jié)束加工時間是x24+a24，故應(yīng)有： d xax 212424 4、目標(biāo)函數(shù)的建立

42、 設(shè)全部產(chǎn)品加工完畢的結(jié)束時間為W，由于三件產(chǎn)品的加 工結(jié)束時間分別為x14+a14， x24+a24， x33+a33，故全部產(chǎn)品 的實際加工結(jié)束時間為： ),max( 333324241414axaxax W 轉(zhuǎn)化為線性表達(dá)式 ax W ax W ax W WZ 3333 2424 1414 min 綜上所述，例 題的整數(shù)規(guī)劃 模型為： 4, 3 ,2, 1, 10 0, )1 ( )1 ( )1 ( )1 ( . min 3332242221141311 3333 2424 1414 212424 4142424 4241414 3133333 3331313 2223232 23222

43、22 1112121 1211111 333232 242222 222121 141312 121111 jy Wxxxxxxxx axW axW axW dxax yMxax Myxax yMxax Myxax yMxax Myxax yMxax Myxax xax xax xax xax xax ts Wz j或 0-1型整數(shù)規(guī)劃是一種特殊的整數(shù)規(guī)劃，若含有n個變 量，則可能產(chǎn)生 2n 個可能的變量組合。當(dāng)n 較大時，采用 完全枚舉法解題幾乎是不可能的。已有的求解0-1型整數(shù)規(guī) 劃的方法一般都屬于隱枚舉法 三、 0-1型整數(shù)規(guī)劃的解法 在2n個可能的變量組合中，往往只有一部分是可行 解。

44、只要發(fā)現(xiàn)某個變量組合不滿足其中一個約束條件 時，就不必再去檢驗其他約束條件。 對于可行解，其目標(biāo)函數(shù)值也有優(yōu)劣之分。若已發(fā)現(xiàn) 一個可行解，則根據(jù)它的目標(biāo)函數(shù)值可以產(chǎn)生一個過濾 條件，對于目標(biāo)函數(shù)值比它差的變量組合就不必再去檢 驗它的可行性。在以后的求解過程中，每當(dāng)發(fā)現(xiàn)比原來 更好的可行解，則以此替換原來的過濾條件。 上述這些做法，都可用減少運算次數(shù)，使最優(yōu)解能 較快地被發(fā)現(xiàn)。 例 求解0-1整數(shù)規(guī)劃 123 123 123 12 23 123 max325 22 44 . .3 46 ,01 Zxxx xxx xxx stxx xx x x x 或 10, 64 3 44 22 . 523ma

45、x 321 32 21 321 321 321 或xxx xx xx xxx xxx ts xxxZ 解 求解過程可以列表表示 (x1,x2,x3)Z值約束條件（a b c d）過濾條件 (0,0,0)0 Z0 (0,0,1)5 Z5 (0,1,0)-2 (0,1,1)3 (1,0,0)3 (1,0,1)8 Z8 a b c d (x1,x2,x3)Z值約束條件（a b c d）過濾條件 (1,1,0)1 (1,1,1)6 接上表 所以，最優(yōu)解（x1,x2,x3）T=(1,0,1)T,max Z = 8 由于采用上述算法，實際只作了20次運算。 例 求解01整數(shù)規(guī)劃 104, 3, 2, 1

46、542315 8443621 143212 . . 432713min 或xxxx xxx xxxx xxxx ts xxxxzZ 解：采用上例那樣的算法，解此例共需作36次運算。為了 進(jìn)一步減少運算量，常按目標(biāo)函數(shù)中各變量系數(shù)的大小順 序重新排列各變量，以便最優(yōu)解有可能較早出現(xiàn)。 對于最大化問題，可按由小到大的順序排列；對于最小化問 題，則相反 本例可寫成下列形式： 10, 553 864 12 . 37min 3412 412 3412 3412 3412 或xxxx xxx xxxx xxxx ts xxxxZ 采取這樣的形式用上法解此例，只需作30次運算。一般 問題的規(guī)模越大，這樣做的

47、好處就越明顯。 籃球隊需要選擇5名隊員組成出場陣容參加比賽. 8 名隊員 的身高及擅長位置見下表: 隊員12345678 身高1.921.901.881.861.851.831.801.78 擅長 位置 中鋒中鋒前鋒前鋒前鋒后衛(wèi)后衛(wèi)后衛(wèi) 出場陣容應(yīng)滿足以下條件: 只能有一名中鋒上場 至少有一名后衛(wèi) 如1號和4號均上場, 則6號不上場 2號和8號至少有一個不出場 問: 應(yīng)當(dāng)選擇哪5名隊員上場,才能使出場隊員平均身高最高? 試建立數(shù)學(xué)模型 有五項設(shè)計任務(wù)可供選擇.各項設(shè)計任務(wù)的預(yù)期完成時間分 別為3, 8, 5, 4, 10 (周), 設(shè)計報酬分別為 7, 17, 11, 9, 21 (萬元).

48、設(shè)計任務(wù)只能一項一項地進(jìn)行, 總的期限是 20 周. 選擇任務(wù)時必須滿足下面要求: 1 至少完成 3 項設(shè)計任務(wù); 2 若選擇任務(wù) 1, 必須同時選擇任務(wù) 2; 3 任務(wù)3 和 任務(wù)4不能同時選擇 應(yīng)當(dāng)選擇那些設(shè)計任務(wù), 才能使總的設(shè)計報酬最大? (試建立數(shù)學(xué)模型) 整數(shù)規(guī)劃 v整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點 v解純整數(shù)規(guī)劃的割平面法* v分支定界法 v0-1型整數(shù)規(guī)劃* v指派問題 5 指派問題 指派問題是整數(shù)規(guī)劃的一類重要問題。也是在實際生活中經(jīng)常 遇到的一種問題：由n項不同的工作或任務(wù)，需要n個人去完成 （每人只能完成一項工作）。由于每人的知識、能力、經(jīng)驗等 不同，故各人完成不同任務(wù)所需的

49、時間（或其它資源）不同。 問應(yīng)只排哪個人完成何項工作所消耗的總資源最少？ 一。 指派問題的數(shù)學(xué)模型 引進(jìn)0-1變量 0 1 ij x 表示按排第i個人完成第j項工作 表示不安排第i個人完成第j項工作 則決策變量矩陣可表示為： nnnn n n xxx xxx xxx X 21 22221 11211 用 表示第i個人完成第j項工作所需的資源數(shù)，稱之為效率 系數(shù)（或價值系數(shù)）。表示為 nnnn n n ccc ccc ccc C 21 22221 11211 ij c 效率矩陣 （Coefficient matrix） 則指派問題的數(shù)學(xué)模型為 n i n j ijijx cZ 11 min nj

50、x nix ts n i ij n j ij , 2 , 11 , 2 , 11 . . 1 1 0 ij x或1 注：指派問題是一種特殊的LP問題，是一種特殊的運輸問題。 下用目前認(rèn)為最簡潔的方法匈牙利法求解。 例1：某商業(yè)公司計劃開辦五家新商店。為了盡早建成 營業(yè)，商業(yè)公司決定由5家建筑公司分別承建。已知建筑 公司 對新商店 的建造 報價（萬元）為 ，見表5-9。商業(yè)公 司應(yīng)當(dāng)對5家建筑公司怎樣分配建筑任務(wù)，才能使總的建 筑費用最少？ )5 , 2 , 1(iA i )5 , 2 , 1(jB j )5 , 2 , 1,(jicij C 5 4 3 2 1 A A A A A 54321

51、BBBBB 810696 1081476 1061296 7141797 1215784 這是一個標(biāo)準(zhǔn)的指派問題。若設(shè)0-1變量 0 1 ij x 當(dāng) 承建 時 i A j B 當(dāng) 不承建 時 i A j B 則問題的數(shù)學(xué)模型為 11125455 min48108Zxxxx 5, 2 , 11 5, 2 , 11 . . 5 1 5 1 jx ix ts i ij j ij 0 ij x或1 C 810696 1081476 1061296 7141797 1215784 5 4 3 2 1 A A A A A 54321 BBBBB 00100 00010 01000 10000 00001

52、 * X 若單說讓誰建，不讓誰建。 C 810696 1081476 1061296 7141797 1215784 5 4 3 2 1 A A A A A 54321 BBBBB -4 14022 32802 30622 081123 59110 -6-7 -6-7 00100 00010 01000 10000 00001 * X 從而導(dǎo)出匈牙利解法的思想： 匈牙利法是1955年由庫恩（W.W.Kuhn）根據(jù)匈牙利 數(shù)學(xué)家狄考尼格（d.konig)關(guān)于矩陣中獨立零元素的定理 發(fā)明的。 匈牙利法的基本原理： 定理1 將效率矩陣的某一行（或某一列）的各個元素都減去 同一個常數(shù)t (t可正可負(fù)）

53、，得到新的矩陣，則以新矩陣為 效率矩陣的指派問題與原指派問題的最優(yōu)解相同。但其最 優(yōu)值比原最優(yōu)值減少t 。 解：設(shè)效率矩陣C為 二。匈牙利解法 nnnn knkk n n ccc ccc ccc ccc C 21 21 22221 11211 nnnn knkk n n ccc tctctc ccc ccc C 21 21 22221 11211 記新指派問題的目標(biāo)函數(shù)為 ，則有 Z n i n j n ki i n j n j kjkjijijijij xcxcxcZ 11111 n j kj n ki i n j n ki i n j n j kjkjijij n j kjkjijij x

54、txcxcxtcxc 1111111 )( n i n j ijij tZtxc 11 1 . 注意到 n j ij x 1 1 所以原式 因此有 tZtZZmin)min(min 而新問題的約束方程同原指派問題。因此其最優(yōu)解比相同， 而最優(yōu)解差一個常數(shù)。 推論 若將指派問題的效率矩陣每一行及每一列分別減去各 行各列的最小元素，則得到的新的指派問題與原指派問題有 相同的最優(yōu)解。 證明：證明：結(jié)論是顯然的。只要反復(fù)運用定理1便可得證。 注： 當(dāng)將效率矩陣的每一行都減去各行的最小元素，將所得的矩 陣的每一列在減去當(dāng)前列中最小元素，則最后得到新效率矩 陣 中必然出現(xiàn)一些零元素。 設(shè) =0，從第i行看

55、，它表示第 i 人去干第 j 項工作效率 （相對）最好，而從第j列來看，它表示第 j 項工作讓第 i 人 來干效率（相對）最高。 C ij c 問題是：能否找到位于不同行、不同列的n個0元素？ 定義 在效率矩陣C中，有一組處于不同行、不同列的零元素， 稱為獨立零元素組，此時其中每個元素稱為獨立零元素。 例 已知 0084 7650 0032 0205 C 則 0, 0, 0, 0 43312412 cccc是一個獨立零元素組， 0, 0, 0, 0 43312412 cccc 分別稱為獨立零元素。 0084 7650 0032 0205 C 也是一個獨立零元素組。 0084 7650 0032

56、 0205 C 不是一個獨立零元素組。 根據(jù)以上對效率矩陣中零元素的分析，對效率矩陣C中出 現(xiàn)的的獨立零元素組中零元素所處的位置，在決策變量矩 陣中令相應(yīng)的 =1，其余的 =0。就可找到指派問題的 一個最優(yōu)解。 ij x ij x 就上例中 (1) 0100 0001 1000 0010 X 就是一個最優(yōu)解。同理 (2) 0100 0010 1000 0001 X 也是一個最優(yōu)解。 3084 0650 7032 0205 C 但是在有的問題中發(fā)現(xiàn)效率矩陣C中獨立零元素的個數(shù) 不夠n個，這樣就無法求出最優(yōu)指派方案，需作進(jìn)一步的 分析。首先給出下述定理。 已知效率矩陣 3084 0650 7032

57、 0205 C 怎么辦？ 定理 效率矩陣C中獨立零元素的最多個數(shù)等于能覆蓋所 有零元素的最少直線數(shù)。 本定理由匈牙利數(shù)學(xué)家狄考尼格證明的。證明的內(nèi)容已超出 所需學(xué)的范圍。 下面通過例子說明上述定理的內(nèi)容 例 已知矩陣 0084 7650 0032 0205 C 3084 0650 7032 0205 C 至于如何找覆蓋零元素的最少直線，通過例子來說明。 例1 現(xiàn)有一個44的指派問題，其效率矩陣為： 91187 1316149 1514410 413152 C 求解該指派問題。 步驟1：變換系數(shù)矩陣，使得每行及每列至少產(chǎn)生一個零元 素。 91187 1316149 1514410 413152

58、C -2 -4 -9 -7 2410 4750 111006 211130 -4-2 1 0010 2350 9606 07130 C 步驟2：用圈0法確定 中的獨立0元素。若獨立零元素個 素有n個，則已得最優(yōu)解。若 獨立零元素的個數(shù) n, 則轉(zhuǎn) 入步驟3。 1 C 1, 1, 1, 1 43312214 xxxx 其余全為0。 在只有一個0元素的行（或列）加圈，表示此人只能做該事 （或此事只能由該人來做），每圈一個“0”，同時把位于同 列（或同行）的其他零元素劃去。表示此時已不能再由他 人來做（或此人已不能做其它事）。如此反復(fù)，直到矩陣 中所有零元素都被圈去或劃去為至。 在遇到所有行和列中，

59、零元素都不止一個時，可任選其中 一個加圈，然后劃去同行、同列其他未被標(biāo)記的零元素。 例 0080 7600 0032 0205 C 步驟3： 若矩陣已不存在未被標(biāo)記的零元素，但圈零的個 數(shù)m n ，作最少直線覆蓋當(dāng)前零元素。 已知例1(工程承包)中的系數(shù)矩陣變?yōu)?4871512 79171410 691287 6714610 6912106 C -4 -7 -6 -6 -6 04630 40810 12630 371020 811340 -1 -3 變換系數(shù)矩陣 04320 40500 12320 37710 811030 1 C 確定獨立零元素. 作最少直線覆蓋當(dāng)前所有零元素。 由于獨立零元

60、素個數(shù)4 5. 對沒有圈0的行打“”。 在已打“”的行中，對零元素所在的列打“”。 在已打“”的列中，對圈0元素所在的行打 “”。 04320 40500 12320 37710 811030 1 C 重復(fù)和，直到再也找不到可以打“”的行或列為 止 對沒有打“”的行畫一橫線，對已打“”的列畫一縱 線， 即得覆蓋當(dāng)前0元素的最少直線數(shù)目的集合。 04320 40500 12320 37710 811030 2 C 繼續(xù)變換系數(shù)矩陣，以增加0元素。 在未被直線覆蓋的元素中找出一個最小的元素。對未被直 04320 40500 12320 37710 811030 1 C 04320 40500 12