第七講整數(shù)規(guī)劃(一)(運(yùn)籌學(xué)清華大學(xué),林謙)

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

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

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

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

變量部分限制為整數(shù)的，稱混合整數(shù)規(guī)劃?！?概述（2）

三、整數(shù)規(guī)劃特點(diǎn)整數(shù)規(guī)劃標(biāo)準(zhǔn)形式（實(shí)際為整數(shù)線性規(guī)劃）

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

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

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

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

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

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

§1概述（4）

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

xj≥0且取整

(2)§1概述（5）

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

xj≥0

§1概述（6）

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

§1概述（7）

四、求解方法分類：1．

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

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

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

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

§2割平面法

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

§3分枝定界法

（1）

分枝定界法目前已成功地應(yīng)用于求解整數(shù)規(guī)劃問(wèn)題、生產(chǎn)進(jìn)度表問(wèn)題、旅行推銷員問(wèn)題、工廠選址問(wèn)題、背包問(wèn)題及分配問(wèn)題等。因此，分枝定界算法是求解整數(shù)規(guī)劃的最有用的算法之一?，F(xiàn)結(jié)合例題說(shuō)是該算法的思路。[例2-5]求解下述整數(shù)規(guī)劃目標(biāo)函數(shù)

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

x1+2x2≥6

x1，x2≥0且為整數(shù)

§3分枝定界法

（2）

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

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

（3）

2）因?yàn)閤1、x2當(dāng)前均為非整數(shù)，故不滿足整數(shù)要求，任選1個(gè)進(jìn)取分枝。設(shè)選x1進(jìn)行分枝，把可行集分成2個(gè)子集：x1≤[10/3]=3及x1≥[10/3]+1=43)x1≤3時(shí)目標(biāo)函數(shù)

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

x1+2x2≥6

x1≤3

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

（4）

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

圖2-2x1=3最優(yōu)解x1=3

x2=3/2x1+2x2=641258123456789x1x23672x1+x2=8目標(biāo)函數(shù)§3分枝定界法

（5）

4）x1≥4時(shí)目標(biāo)函數(shù)minz=x1+4x2約束條件2x1+x2≤8

x1+2x2≥6

x1≥4

x2≥0x1、x2為整數(shù)?！?分枝定界法

（6）

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

（7）

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

x1+2x2≥6

x1≤3

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

（8）

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

x1+2x2≥6

x1≤3

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

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

x1≥4

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

圖2-4§3分枝定界法

（10）

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

（11）

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

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

§1匈牙利法（2）

表2-3授課費(fèi)用表

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

§1匈牙利法（3）

該例便是指派問(wèn)題的典型實(shí)例，該類問(wèn)題的典型數(shù)學(xué)模型為：=1i=1,…,m=1j=1,…,m

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

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

z=

－

－§1匈牙利法（5）

=

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

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

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

§5匈牙利法（9）

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

§1匈牙利法（10）

現(xiàn)在依次檢查每列中只含一個(gè)未標(biāo)記的零元素，并給未標(biāo)記的零元素標(biāo)Δ。對(duì)同一行其它的零元素畫×（如果有的話）。如果有多行多列同時(shí)有2個(gè)或以上的未標(biāo)記零元素，則可將其中的任意行或列中一個(gè)未標(biāo)零元素標(biāo)Δ，并將同行和同列的其他零元素畫×。

§1匈牙利法