第5章整數線性規劃第1節整數線性規劃問題的提出第2節分支定界解法第3節割平面解法第4節0-1型整數線性規劃第5節指派問題

第1節整數線性規劃問題的提出線性規劃問題的最優解可能是分數或小數，但對于某些具體問題，常有要求解必須是整數。例如，所求解是機器的臺數、完成工作的人數或裝貨的車數等，分數或小數的解答就不合要求。經過“舍入化整”常常是不行的，因為化整后不見得是可行解；或雖是可行解，但不一定是最優解。我們稱求最優整數解的問題為整數線性規劃(integerlinearprogramming)，簡稱ILP，整數線性規劃是最近幾十年來發展起來的規劃論中的一個分支。整數線性規劃中如果所有的變數都限制為(非負)整數，就稱為純整數線性規劃(pureintegerlinearprogramming)或稱為全整數線性規劃(allintegerlinearprogramming)；如果僅一部分變數限制為整數，則稱為混合整數規劃(mixedintegerlinearprogramming)。整數線性規劃的一種特殊情形是0-1規劃，它的變數取值僅限于0或1。1324托運限制1054乙2025甲利潤每箱（百元）重量每箱（百斤）體積每箱（m3）貨物問如何選擇甲、乙兩種貨物的托運數量，使獲得的利潤最大？例1某廠擬用集裝箱托運甲乙兩種貨物，每箱的體積、重量、可獲利潤以及托運所受限制如表：1324托運限制1054乙2025甲利潤每箱（百元）重量每箱（百斤）體積每箱（m3）貨物解:設x1，x2分別為甲、乙兩種貨物的托運箱數。

maxz=20x1+10x2①5x1+4x2≤24②2x1+5x2≤13③(5.1)x1，x2≥0④x1，x2整數⑤它和線性規劃問題的區別僅在于最后的條件⑤。現在我們暫不考慮這一條件，即解①～④(以后我們稱這樣的問題為與原問題相應的線性規劃問題)，很容易求得最優解為:x1=4.8，x2=0，maxz=96

是不是可以把所得的非整數的最優解經過“化整”就可得到合于條件⑤的整數最優解呢?如將(x1=4.8，x2=0)湊整為(x1=5，x2=0)，這樣就破壞了條件②(關于體積的限制)，因而它不是可行解；如將(x1=4.8，x2=0)舍去尾數0.8，變為(x1=4，x2=0)，這當然滿足各約束條件，因而是可行解，但不是最優解，因為當x1=4，x2=0,時z=80.非整數的最優解在C(4.8，0)點達到。但當x1=4，x2=1(這也是可行解)時，z=90。由上例看出，將其相應的線性規劃的最優解“化整”來解原整數線性規劃，常常得不到整數線性規劃的最優解，甚至根本不是可行解。第2節分支定界解法在求解整數線性規劃時，如果可行域是有界的，首先容易想到的方法就是窮舉變量的所有可行的整數組合，就像在圖5-1中畫出所有“+”號的點那樣，然后比較它們的目標函數值以定出最優解。對于小型的問題，變量數很少，可行的整數組合數也是很小時，這個方法是可行的，也是有效的。在例1中，x1所能取的整數值為0、1、2、3、4共5個；x2所能取的整數值為0、1、2共3個，它的組合(不都是可行的)數是3×5=15個，窮舉法還是勉強可用的。對于大型的問題，可行的整數組合數是很大的。例如將n項任務指派n個人去完成，不同的指派方案共有n!種，當n=10，這個數就超過300萬；當n=20，這個數就超過2×1018，用每秒百萬次的計算機，也要幾萬年的功夫。所以我們的方法一般應是僅檢查可行的整數組合的一部分，就能定出最優的整數解。分支定界解法(branchandboundmethod)就是其中的一個。原問題A：相應線性規劃問題B：設A有一可行解，其目標函數值是Z的一個下界(定界)。從解B0開始，若其最優解符合整數條件則得到A的解，否則取此解不滿足整數條件的分量，在B0問題中分別加入約束條件： 從而得到B0的兩個子問題B1和B2(分枝)。分別解B1和B2，根據它們解的情況，或增大(定界)、或繼續分枝、或終止分枝。重復分枝定界過程，直至不能增大、不能分枝為止。其中，[xk]為xk的整數部分。

如xk=3.5，[xk]=3；xk=-1.5，[xk]=-2。分枝定界法的基本思想：

xk

≤[xk]和xk≥[xk]+1(4.81,1.82)9x1+7x2=567x1+20x2=70z=40x1+90x2

B0的最優解為x1=4.81，x2=1.82，z0=356，不是A的可行解。B1的可行域B2的可行域（4，2.1）（5,1.57）由x1=4.81產生兩個約束條件x1≤4,x1≥5

注意：這樣分枝并沒有減少A的可行解，但增加了可能符合整數條件的頂點1B4的可行域B3的可行域（4,2）（1.42,3）再將B1分枝，在B1中分別加x2

2，x2

3得到：B5的可行域（5.44,1）

更新=340，得到新的界。由于z4<，知B4的可行域內不可能含有比(4，2)T更優的解，故B4不再分枝。回到B2，由于z2>，不排除B2的可行域中有比(4，2)T更好的整數解的可能，故要繼續分枝。在B2中分別加約束條件：x2

1，x2

2, 得到問題B5和B6x21x22B5x1=5.44x2=1.00z5=308B6無可行解z=340=z*B4x22B3x1=4.00x2=2.00z3=340x1=1.42x2=3.00z4=327x23z=340x1=5.00x2=1.57

B1x1=4.00x2=2.10z1=349x14x15z2=341

B2z=0Bx1=4.81

x2=1.82z0=356z=0×××從以上解題過程可得到，用分支定界法求解整數線性規劃(最大化)問題的步驟為：

將要求解的整數線性規劃問題稱為問題A，將與它相應的線性規劃問題稱為問題B。(1)解問題B，可能得到以下情況之一。①B沒有可行解，這時A也沒有可行解，則停止。②B有最優解，并符合問題A的整數條件，B的最優解即為A的最優解，則停止。③B有最優解，但不符合問題A的整數條件，記它的目標函數值為

(2)用觀察法找問題A的一個整數可行解，一般可取xj=0，j=1，…，n，試探，求得其目標函數值，并記作。

以z*表示問題A的最優目標函數值；這時有

進行迭代第一步：分支，在B的最優解中任選一個不符合整數條件的變量xj，其值為bj，以［bj］表示小于bj的最大整數。構造兩個約束條件xj≤［bj］和xj≥［bj］+1將這兩個約束條件，分別加入問題B，求兩個后繼規劃問題B1和B2。不考慮整數條件求解這兩個后繼問題。定界，以每個后繼問題為一分支標明求解的結果，與其他問題的解的結果中，找出最優目標函數值最大者作為新的上界。從已符合整數條件的各分支中，找出目標函數值為最大者作為新的下界，若無可行解，

第二步：比較與剪支各分支的最優目標函數中若有小于者，則剪掉這支(用打×表示)，即以后不再考慮了。若大于，且不符合整數條件，則重復第一步驟。一直到最后得到z*為止，得最優整數解xj*，j=1，…，n。用分支定界法可解純整數線性規劃問題和混合整線性規劃問題。它比窮舉法優越。因為它僅在一部分可行解的整數解中尋求最優解，計算量比窮舉法小。若變量數目很大，其計算工作量也是相當可觀的。第3節割平面解法割平面解法的思路是：首先不考慮變量xi是整數這一條件，用解線性規劃的方法去解整數線性規劃問題，若得到非整數的最優解，然后增加能割去非整數解的線性約束條件(或稱為割平面)使得由原可行域中切割掉一部分，這部分只包含非整數解，但沒有切割掉任何整數可行解。這個方法就是指出怎樣找到適當的割平面(不見得一次就找到)，使切割后最終得到這樣的可行域，它的一個有整數坐標的極點恰好是問題的最優解。為了最終獲得整數最優解,每次增加的線性約束條件應具備兩個基本性質:(1)已獲得的不符合整數要求的線性規劃最優解不滿足該約束條件,從而不可能在以后的解中出現;(2)凡整數可行解均滿足該線性約束條件,因而整數最優解始終被保留在每次形成的線性可行域中。例3求解目標函數

maxz=x1+x2①

約束條件：

-x1+x2≤1②3x1+x2≤4③(5-3)x1，x2≥0④x1，x2

整數⑤如不考慮條件⑤，容易求得相應的線性規劃的最優解：x1=3/4，x2=7/4，maxz=10/4它就是圖5-5中域R的極點A，但不合于整數條件。現設想，如能找到像CD那樣的直線去切割域R(圖5-6)，去掉三角形域ACD，那么具有整數坐標的C點(1，1)就是域R′的一個極點，如在域R′上求解①～④，而得到的最優解又恰巧在C點就得到原問題的整數解，所以解法的關鍵就是怎樣構造一個這樣的“割平面”CD，盡管它可能不是唯一的，也可能不是一步能求到的。在原問題的前兩個不等式中增加非負松弛變量x3、x4，使兩式變成等式約束：-x1+x2+x3=1⑥3x1+x2+x4=4⑦不考慮條件⑤，用單純形表解題，見表5-2。表5-2從表5-2的最終計算表中，得到非整數的最優解：x1=3/4，x2=7/4，x3=x4=0，maxz=5/2不能滿足整數最優解的要求。為此考慮將帶有分數的最優解的可行域中分數部分割去，再求最優解，就可以得到整數的最優解。可從最終計算表中得到非整數變量對應的關系式：為了得到整數最優解。將上式變量的系數和常數項都分解成整數和非負真分數兩部分之和(1+0)x1+(-1+3/4)x3+1/4x4=0+3/4x2+(3/4)x3+(1/4)x4=1+3/4然后將整數部分與分數部分分開，移到等式左右兩邊，得到：要求x1、x2都是非負整數，于是由條件⑥、⑦可知x3、x4也都是非負整數,這一點對以下推導是必要的，如不都是整數，則應在引入x3、x4之前乘以適當常數，使之都是整數。在上式中(其實只考慮一式即可)從等式左邊看是整數；等式右邊也應是整數。但在等式右邊的(·)內是正數；所以等式右邊必是非正數。就是說，右邊的整數值最大是零。于是整數條件⑤可由下式所代替；

即-3x3-x4≤-3⑧這就得到一個切割方程(或稱為切割約束)，將它作為增加約束條件，再解例3。引入松弛變量x5，得到等式-3x3-x4+x5=-3將這新的約束方程加到表5-2的最終計算表，得表5-3。

表5-3從表5-3的b列中可看到，這時得到的是非可行解，于是需要用對偶單純形法繼續進行計算選擇x5為換出變量，計算將x3做為換入變量，再按原單純形法進行迭代，得表5-4。注意：新得到的約束條件⑧-3x3-x4≤-3如用x1、x2表示，由⑥、⑦式得3(1+x1-x2)+(4-3x1-x2)≥3x2≤1這就是(x1，x2)平面內形成新的可行域，即包括平行于x1軸的直線x2=1和這直線下的可行區域，整數點也在其中，沒有切割掉。直觀地表示在圖5-7中。但從解題過程來看，這一步是不必要的。圖5-7求一個切割方程的步驟：(1)令xi是相應線性規劃最優解中為分數值的一個基變量，由單純形表的最終表得到其中i∈Q(Q指構成基變量號碼的集合)k∈K(K指構成非基變量號碼的集合)(2)將bi和αik都分解成整數部分N與非負真分數f之和，即bi=Ni+fi，其中0＜fi＜1

αik=Nik+fik，其中0≤fik＜1(5-5)而N表示不超過b的最大整數。例如：若b=2.35，則N=2，f=0.35若b=-0.45，則N=-1,f=0.55代入(5-4)式得(3)現在提出變量(包括松弛變量)為整數的條件(當然還有非負的條件).這時，上式由左邊看必須是整數，但由右邊看，因為0＜fi＜1，所以不能為正，即這就是一個切割方程。由(5-4)式，(5-6)式，(5-7)式可知：①切割方程(5-7)式真正進行了切割，至少把非整數最優解這一點割掉了。②沒有割掉整數解，這是因為相應的線性規劃的任意整數可行解都滿足(5-7)式的緣故。第4節0-1型整數線性規劃

決策變量僅取為0或1的整數規劃問題。

x-i

是0-1變量的表示：xi

=0或1

或xi

0，xi

1，xi

Z4.1引入0-1變量的實際問題1.投資場所的選定——相互排斥的計劃例4某公司擬在市東、西、南三區建立門市部。擬議中有7個位置(點)Ai(i=1，2，…，7)可供選擇。規定：在東區，由A1，A2，A3三個點中至多選兩個；在西區，由A4，A5兩個點中至少選一個；在南區，由A6，A7兩個點中至少選一個。如選用Ai點，設備投資估計為bi元，每年可獲利潤估計為ci元，但投資總額不能超過B元。問應選擇哪幾個點可使年利潤為最大?解題時先引入0-1變量xi(=1,2，…，7)于是問題可列成：

2.相互排斥的約束條件(1)二者擇一在本章開始的例1中，關于運貨的體積限制為車運5x1+4x2≤24(5-9)設運貨有車運和船運兩種方式，用船運時關于體積的限制條件為船運7x1+3x2≤45(5-10)這兩條件是互相排斥的。為了統一在一個問題中，引入0-1變量y，令

5x1+4x2≤24+yM(5-11)

7x1+3x2≤45+(1-y)M(5-12)

其中y=0或1，M是充分大的數。

引入的變量y不必出現在目標函數內，即認為在

目標函數式內y的系數為0。為了保證這m個約束條件只有一個起作用，我們引入

m個0-1變量yi(i=1,2,…，m)和一個充分大的常數M，

αi1x１+αi2x2+…+αinxn≤bi+yiM，

i=1,2,…，m(5-13)y1+y2+…+ym=m-1(5-14)(2)多擇一有m個互相排斥的約束條件：αi1x1+αi2x2+…+αinxn≤bi，i=1，2，…,m例5某工廠為了生產某種產品，有幾種不同的生產方式可供選擇，如選定投資高的生產方式(選購自動化程度高的設備)，由于產量大，因而分配到每件產品的變動成本就降低；反之，如選定投資低的生產方式，將來分配到每件產品的變動成本可能增加，所以必須全面考慮。今設有三種方式可供選擇，令

xj表示采用第j種方式時的產量；

cj表示采用第j種方式時每件產品的變動成本；

kj表示采用第j種方式時的固定成本。3.關于固定費用的問題

在構成目標函數時，為了統一在一個問題中討論，現引入0-1變量yj，令于是目標函數minz=(k1y1+c1x1)+(k2y2+c2x2)+(k3y3+c3x3)采用各種生產方式的總成本分別為(5-15)式這個規定可由以下3個線性約束條件表示：

xj≤yjM，j=1,2,3(5-16)其中M是個充分大的常數。(5-16)式說明，當xj＞0時yj必須為1；當xj=0時只有yj為0時才有意義，所以(5-16)式完全可以代替(5-15)式

4.20-1型整數線性規劃的解法解0-1型整數線性規劃最容易想到的方法就是窮舉法，即檢查變量取值為0或1的每一種組合，比較目標函數值以求得最優解，這就需要檢查變量取值的2n個組合。對于變量個數n較大(例如n＞10)，這幾乎是不可能的。因此常設計一些方法，只檢查變量取值的組合的一部分，就能求到問題的最優解。這樣的方法稱為隱枚舉法(implicitenumeration)，分枝定界法也是一種隱枚舉法。下面舉例說明一種解0-1型整數線性規劃的隱枚舉法例6目標函數maxz=3x1-2x2+3x3

約束條件：

x1+2x2-x3≤2①x1+4x2+x3≤4②x1+x2≤3③(5-17)4x1+x3≤6④x1，x2，x3=0或1⑤解：試探x=(1，0，0)為一可行解，z=3。得過濾條件

3x1

－

2x2

+5x3

≥

3

枚舉所有解，按辭典序列表，先檢查過濾條件，后檢查約束條件是否成立，得出最優解。

見表5-5注意：一般常重新排列xi的順序使目標函數中xi的系數是遞增(不減)的，在上例中，改寫z=3x1-2x2+5x3=-2x2+3x1+5x3因為-2，3，5是遞增的序，變量(x2，x1，x3)也按下述順序取值：(0，0，0)，

(0，0，1)，(0，1，0)，(0，1，1)，…，這樣，最優解容易比較早的發現。

表5-6（a）（b）表5-6（c）

第5節指派問題

在生活中經常遇到這樣的問題，某單位需完成n項任務，恰好有n個人可承擔這些任務。由于每人的專長不同，各人完成任務不同(或所費時間)，效率也不同。于是產生應指派哪個人去完成哪項任務，使完成n項任務的總效率最高(或所需總時間最小)。這類問題稱為指派問題或分派問題(assignmentproblem)。有n項任務，恰好n個人承擔，第i人完成第j項任務的花費(時間或費用等)為cij，如何指派使總花費最省？第j項工作由一個人做第i人做一項工作指派問題是0-1規劃的特例，也是運輸問題的特例，即n=m,aj=bi=1

當然可用整數線性規劃，0-1規劃或運輸問題的解法去求解，這就如同用單純形法求解運輸問題一樣是不合算的。利用指派問題的特點可有更簡便的解法。

指派問題的最優解有這樣性質，若從系數矩陣(cij)的一行(列)各元素中分別減去該行(列)的最小元素，得到新矩陣(bij)，那么以(bij)為系數矩陣求得的最優解和用原系數矩陣求得的最優解相同。

利用這個性質，可使原系數矩陣變換為含有很多0元素的新系數矩陣，而最優解保持不變，在系數矩陣(bij)中，我們關心位于不同行不同列的0元素，以下簡稱為獨立的0元素。若能在系數矩陣(bij)中找出n個獨立的0元素；則令解矩陣(xij)中對應這n個獨立的0元素的元素取值為1，其他元素取值為0。將其代入目標函數中得到zb=0，它一定是最小。這就是以(bij)為系數矩陣的指派問題的最優解。也就得到了原問題的最優解。例7有一份中文說明書，需譯成英、日、德、俄四種文字。分別記作E、J、G、R。現有甲、乙、丙、丁四人，他們將中文說明書翻譯成不同語種的說明書所需時間如下表。問應指派何人去完成何工作，使所需總時間最少？已知條件可用系數矩陣（效率矩陣）表示為：其可行解也可用每行僅有一個1，每列也僅有一個1的矩陣表示，如：-2-4-9-7

若某行(列)已有0元素，那就不必再減了。例7的計算為： 匈牙利法解題步驟：10

使系數矩陣各行、各列出現零元素作法：系數矩陣各行元素減去所在行的最小元素，再從所得矩陣的各列減去所在列最小元素。(因一行中xij

取值一個1，其余為0，cij

同時減去一常數不影響xij取值)。-4-2

20

試求最優解。如能找出n個位于不同行不同列的零元素，令對應的xij=1，其余xij