第七講整數規劃（一）§1概述

§2割平面法§3分枝定界法§1概述（1）

一、定義規劃中的變量（部分或全部）限制為整數時，稱為整數規劃。若在線性規劃模型中，變量限制為整數，則稱為整數線性規劃。二、整數規劃分類如不加特殊說明，一般指整數線性規劃。對于整數線性規劃模型大致可分為兩類：?

變量全限制為整數的，稱純（完全）整數規劃。?

變量部分限制為整數的，稱混合整數規劃。§1概述（2）

三、整數規劃特點整數規劃標準形式（實際為整數線性規劃）

AX=b，X≥0，CTX=min，xj為整數（j=1，…，n）(1)1．原線性規劃有最優解，當自變量限制為整數后，其整數規劃解出現下述情況；①原線性規劃最優解全是整數，則整數規劃最優解與線性規劃最優解一致。②整數規劃無可行解。§1概述（3）

[例2-1]原線性規劃為：2x1+4x2=5，X≥0，CTX=x1+x2=min

其最優實數解為：x1=0，x2=5/4，minCTX=5/4。

③有可行解（當然就存在最優解），但最優解值變差。[例2-2]原線性規劃為：2x1+4x2=6，X≥0，CTX=x1+x2=min

其最優實數解為：x1=0，x2=3/2，minCTX=3/2。

若限制整數則得：x1=1，x2=1，minCTX=2。

§1概述（4）

2．整數規劃最優解不能按照實數最優解簡單取整而獲得。[例2-3]物品裝載問題：有若干類物品需一次性裝運，每件物品的價值及重量分別，為vj和wj(j=1,…,n)，車輛最大載重量為，試求，每件物品應裝多少件才能使總價值最大。[解]令xj表示第j類物品的裝載件數，則可列寫整數規劃如下：

xj≥0且取整

(2)§1概述（5）

若不限制為整數，其最優解的基礎分量xm為：當j≠m，則xj=0當限制為整數時，就需仔細計算（其方法將在后面闡述）。例如，將例[2-3]具體化為： 51x1+50x2+50x3≤100150x1+100x2+99x3=max

xj≥0

§1概述（6）

若不限制整數，得出m=1，比率為150/51→max，故最優實數解為：x1=100/51，x2=x3=0，總價值15000/51=294.12。然而，物品不能切開，故限制為整數時，其最優解為：x1=0，x2=2，x3=0；總價值為200。從該例得出結論，整數規劃最優解不能簡單的從最優實實數解中4舍5入取整所得。因此，對于整數規劃的求解必須開拓新技術。

§1概述（7）

四、求解方法分類：1．

割平面法——主要求解純整數線性規劃2．

分枝定界法——可求純或混合整數線性規劃3．

隱枚舉法——求解“01”整數規劃：①過濾隱枚舉法；②分枝隱枚舉法4．

匈牙利法——解決指派問題（“01”規劃特殊情形）。5．蒙特卡洛法——求解各種類型規劃。

§2割平面法

該法適于求解純整數規劃問題。其基本思路是首先去掉整數約束去求解普通線性規劃問題，若獲得的最優解全為整數，結束；否則，以此最優非整數變量為基準，在原約束條件下，增加割約束，再繼續求解，這樣反復下去，直到結束為止。

§3分枝定界法

（1）

分枝定界法目前已成功地應用于求解整數規劃問題、生產進度表問題、旅行推銷員問題、工廠選址問題、背包問題及分配問題等。因此，分枝定界算法是求解整數規劃的最有用的算法之一。現結合例題說是該算法的思路。[例2-5]求解下述整數規劃目標函數

minz=x1+4x2約束條件2x1+x2≤8

x1+2x2≥6

x1，x2≥0且為整數

§3分枝定界法

（2）

[解]1)不受整數限制，作為普通線性規劃求解，可得出最優解為：x1=10/3，x2=4/3，z=26/3（見圖2-1）。該解示如圖2-4中的節點①。

1245810123456789x1x22x1+x2=8最優解x1+2x2=6圖2-13679§3分枝定界法

（3）

2）因為x1、x2當前均為非整數，故不滿足整數要求，任選1個進取分枝。設選x1進行分枝，把可行集分成2個子集：x1≤[10/3]=3及x1≥[10/3]+1=43)x1≤3時目標函數

minz=x1+4x2約束條件2x1+x2≤8

x1+2x2≥6

x1≤3

x1，x2≥0且為整數。§3分枝定界法

（4）

不加整數限制，求出最優解為：x1=3，x2=3/2，z=9（參見圖2-2）。該解示如圖2-4中的節點②。

圖2-2x1=3最優解x1=3

x2=3/2x1+2x2=641258123456789x1x23672x1+x2=8目標函數§3分枝定界法

（5）

4）x1≥4時目標函數minz=x1+4x2約束條件2x1+x2≤8

x1+2x2≥6

x1≥4

x2≥0x1、x2為整數。§3分枝定界法

（6）

不受整數限制，求解相應線性規劃，用圖解法觀察出無解（參見圖2-3）。該解示如圖2-4中的③。圖2-341258123456789x1x2367x1=42x1+x2=8x1+2x2=6§3分枝定界法

（7）

5）節點④，令x2≤[3/2]=1目標函數minz=x1+4x2約束條件2x1+x2≤8

x1+2x2≥6

x1≤3

x2≤1x1、x2≥0，且為整數。用圖解法，知該子集無解，讀者可以自己作。§3分枝定界法

（8）

6)節點⑤，令x2≥[3/2]+1=2目標函數minz=x1+4x2約束條件2x1+x2≤8

x1+2x2≥6

x1≤3

x2≥2x1≥0，全取整。其圖解法見圖2-5，最優解為x1=2，x2=2，z=10。§3分枝定界法

（9）圖2-5x1=3x1=2x2＝241258123456789x1x2367最優整數解目標函數x2=2123z=26/3x1=10/3x2=4/3x1≤3

x1≥4

z=9x1=3x2=3/2不可行

圖2-4§3分枝定界法

（10）

從對求解[例2-5]的過程，可歸納出求解整數規劃的分枝定界法有下述特點：(i)既可求解全整數規劃，亦可求解混合整數規劃。(ii)求解每個子集的最優整數解，都是首先放棄整數約束，用線性規劃解法求出無約束時的最優解，此時的目標函數值即為該子集所有可行解的目標下界（對于求極小值的規劃而言）。(iii)如果子集的非整數最優解的下界超過迄今已得到的最好可行整數解目標值，或者子集無解，則這個子集將被剪掉，又稱剪枝。§3分枝定界法

（11）

(iv)如果子集的非整數最優解符合變量整數要求，則稱為整數規劃的可行解，其目標函數值若低于已得的最好可行整數解目標，則取代原最好解，否則，該子集被剪掉。(v)如果子集的非整數最優解不符合整數要求，但又未被剪掉，則任選一個不符合整數要求的變量進行分枝。(vi)該法只能用于整數線性規劃。第七講整數規劃（二）§1匈牙利法§2蒙特卡洛法（隨機取樣法）（略）§1匈牙利法（1）

匈牙利法主要解決指派問題，指派問題是一種特殊的“01”規劃。例如指派授課問題，現有A、B、C、D四門課程，需由甲、乙、丙、丁四人講授，并且規定：每人只講且必須講１門課。每門課必須且只需１人講。四人分別講每門課的費用示于表2-3中：

§1匈牙利法（2）

表2-3授課費用表

課費用人ABCD甲乙丙丁2109715414813141611415139求何人講何門課才能使總費用最低？

§1匈牙利法（3）

該例便是指派問題的典型實例，該類問題的典型數學模型為：=1i=1,…,m=1j=1,…,m

xij=minz=§1匈牙利法（4）

其中，cij為效能矩陣（或費用矩陣）元素，表示第i人去完成第j任務時的費用。共有m個人去完成m件工作。該法的主要思路和步驟如下：１．在費用矩陣中，任一行（列）減去或加上１個常數，其最優基礎解集不變，只改變費用函數值。從費用矩陣中的i行每個元素減去ai(i=1,…,m)，從j列中每個元素減去bj（j=1,…,m），則新目標函數改變為：min

z=

－

－§1匈牙利法（5）

=

－－顯而易見，變化后的目標函數表達式只相差一個常數，則規劃的最優解集不可能改變。2．用上述方法變換，使費用矩陣每行每列都至少出現1個零，且能達到全分配時，即可令零元素所對應的變量xij=1（當然分配時，必須使每行每列有且僅有1個xij為1）。于是可獲得費用函數值z=0，這必是此次的最優分配，否則，只會使z≥0。例如，由表1所示的授課例子中，經過變換可得最后結果為：§1匈牙利法（6）

當達到右邊費用矩陣時，就已達到全分配，用Δ表示之，即，最優解集為：x13=1(甲講C門課)x22=1（乙講B門課）x34=1（丙講D門課）x41=1（丁講A門課）§1匈牙利法（7）

此時對應的最后規劃模型目標函數必為零，但原始規劃目標函數最優值為變換中歷次從行（列）中減去（或加上的）常數之代數和。該題變換中共減去28，故本例最優費用值為28。3．從前所述，指派問題的關鍵是如何將原規劃的費用矩陣變換成全分配矩陣，現不加證明的闡述其變換步驟（仍結合前例說明）。1)修改費用矩陣，使矩陣的每一行和第一列至少出現1個零元素，處理方法即為每行（每列）都減去該行（列）的最小元素。§1匈牙利法（8）

§5匈牙利法（9）

2)試圖制訂一個完全分配方案，該方案只與表中零元素相對應。從第１行開始，依次檢查各行，直到找出只有一個未標記的零元素的一行為止。如果在零元素上有一個符號Δ或×，則稱零元素已標記。符號Δ表示分配Δ所在行的那一位教師擔任Δ所在列的那一門課程。對未做標記的零元素標Δ后，應對同一列其它的零元素畫×。

§1匈牙利法（10）

現在依次檢查每列中只含一個未標記的零元素，并給未標記的零元素標Δ。對同一行其它的零元素畫×（如果有的話）。如果有多行多列同時有2個或以上的未標記零元素，則可將其中的任意行或列中一個未標零元素標Δ，并將同行和同列的其他零元素畫×。

§1匈牙利法