第七講整數規(guī)劃(一)(運籌學清華大學,林謙)

第七講整數規(guī)劃（一）§1概述

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

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

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

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

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

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

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

其最優(yōu)實數解為：x1=0，x2=5/4，minCTX=5/4。

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

其最優(yōu)實數解為：x1=0，x2=3/2，minCTX=3/2。

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

§1概述（4）

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

xj≥0且取整

(2)§1概述（5）

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

xj≥0

§1概述（6）

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

§1概述（7）

四、求解方法分類：1．

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

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

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

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

§2割平面法

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

§3分枝定界法

（1）

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

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

x1+2x2≥6

x1，x2≥0且為整數

§3分枝定界法

（2）

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

1245810123456789x1x22x1+x2=8最優(yōu)解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且為整數?！?分枝定界法

（4）

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

圖2-2x1=3最優(yōu)解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為整數?！?分枝定界法

（6）

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

（7）

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

x1+2x2≥6

x1≤3

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

（8）

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

x1+2x2≥6

x1≤3

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

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

x1≥4

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

圖2-4§3分枝定界法

（10）

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

（11）

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

匈牙利法主要解決指派問題，指派問題是一種特殊的“01”規(guī)劃。例如指派授課問題，現有A、B、C、D四門課程，需由甲、乙、丙、丁四人講授，并且規(guī)定：每人只講且必須講１門課。每門課必須且只需１人講。四人分別講每門課的費用示于表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件工作。該法的主要思路和步驟如下：１．在費用矩陣中，任一行（列）減去或加上１個常數，其最優(yōu)基礎解集不變，只改變費用函數值。從費用矩陣中的i行每個元素減去ai(i=1,…,m)，從j列中每個元素減去bj（j=1,…,m），則新目標函數改變?yōu)椋簃in

z=

－

－§1匈牙利法（5）

=

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

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

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

§5匈牙利法（9）

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

§1匈牙利法（10）

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

§1匈牙利法