混合整數(shù)線性規(guī)劃

整數(shù)規(guī)劃(IntegerProgramming)整數(shù)規(guī)劃的模型分支定界法0－1整數(shù)規(guī)劃指派問題（一）、整數(shù)規(guī)劃問題實例

例一、合理下料問題設(shè)某型號圓鋼可生產(chǎn)零件毛坯為A1,

A2,…,Am

。在一根圓鋼上下料的方式有B1,B2,…,Bn

種，每種下料方式可以得到各種零件的毛坯數(shù)以及每種零件的需要量，如表所示。問怎樣安排下料方式，使得即滿足需要，所用的原材料又最少？零件方個數(shù)式零件零件毛坯數(shù)一、整數(shù)規(guī)劃的模型

設(shè)：xj

表示用Bj(j=1.2…n)

種方式下料根數(shù)模型：例二、某公司計劃在m個地點建廠，可供選擇的地點有A1,A2…Am

，他們的生產(chǎn)能力分別是a1,a2,…am（假設(shè)生產(chǎn)同一產(chǎn)品）。第i個工廠的建設(shè)費用為fi

(i=1.2…m),又有n個地點B1,B2,…Bn

需要銷售這種產(chǎn)品，其銷量分別為b1.b2…bn

。從工廠運往銷地的單位運費為Cij。試決定應(yīng)在哪些地方建廠，即滿足各地需要，又使總建設(shè)費用和總運輸費用最??？單銷地廠址價生產(chǎn)能力建設(shè)費用銷量

設(shè)：

xij

表示從工廠運往銷地的運量(i=1.2…m、j=1.2…n),1在Ai建廠又設(shè)Yi＝（i=1.2…m）

0不在Ai建廠模型：（二）、整數(shù)規(guī)劃的數(shù)學模型一般形式

依照決策變量取整要求的不同，整數(shù)規(guī)劃可分為純整數(shù)線性規(guī)劃、混合整數(shù)線性規(guī)劃、0－1整數(shù)線性規(guī)劃。

純整數(shù)線性規(guī)劃：所有決策變量要求取非負整數(shù)。

混合整數(shù)規(guī)劃：只有一部分的決策變量要求取非負整數(shù)，另一部分可以取非負實數(shù)。0－1整數(shù)規(guī)劃：所有決策變量只能取0或1兩個整數(shù)。（三）、整數(shù)規(guī)劃與線性規(guī)劃的關(guān)系

從數(shù)學模型上看整數(shù)規(guī)劃似乎是線性規(guī)劃的一種特殊形式，求解只需在線性規(guī)劃的基礎(chǔ)上，通過舍入取整，尋求滿足整數(shù)要求的解即可。但實際上兩者卻有很大的不同，通過舍入得到的解（整數(shù)）也不一定就是最優(yōu)解，有時甚至不能保證所得到的解是整數(shù)可行解。舉例說明。例：設(shè)整數(shù)規(guī)劃問題如下

首先不考慮整數(shù)約束，得到線性規(guī)劃問題（一般稱為松弛問題）。用解法求出最優(yōu)解x1＝3/2,x2=10/3且有Z=29/6x1x2⑴⑵33(3/2,10/3)

現(xiàn)求整數(shù)解（最優(yōu)解）：如用“舍入取整法”可得到4個點即(1，3)(2，3)(1，4)(2，4)。顯然，它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。

按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問題的可行域內(nèi)且為整數(shù)點。故整數(shù)規(guī)劃問題的可行解集是一個有限集，如圖所示。圖

因此，可將集合內(nèi)的整數(shù)點一一找出，其最大目標函數(shù)的值為最優(yōu)解，此法為完全枚舉法。如上例：其中（2，2）（3，1）點為最大值，Z=4。

目前，常用的求解整數(shù)規(guī)劃的方法有：

割平面法和分支定界法；對于特別的0－1規(guī)劃問題采用隱枚舉法和匈牙利法。（一）、基本思路

考慮純整數(shù)問題：整數(shù)問題的松弛問題：二、分支定界法

1、先不考慮整數(shù)約束，解(

IP)的松弛問題(LP)，可能得到以下情況之一：

⑴.若(LP)沒有可行解，則(IP)也沒有可行解，停止計算。

⑵.若(LP)有最優(yōu)解，并符合(IP)的整數(shù)條件，則(LP)的最優(yōu)解即為(IP)的最優(yōu)解，停止計算。

⑶.若(LP)有最優(yōu)解，但不符合(IP)的整數(shù)條件，轉(zhuǎn)入下一步。為討論方便，設(shè)(LP)的最優(yōu)解為：

2、定界：記(

IP)的目標函數(shù)最優(yōu)值為Z*,以Z(0)

作為Z*

的上界，記為＝Z(0)

。再用觀察法找的一個整數(shù)可行解X′，并以其相應(yīng)的目標函數(shù)值Z′作為Z*

的下界，記為Z＝Z′，也可以令Z＝－∞，則有：

Z≤Z*≤

3、分枝：在(LP)的最優(yōu)解X(0)中，任選一個不符合整數(shù)條件的變量，例如xr=

（不為整數(shù)），以表示不超過的最大整數(shù)。構(gòu)造兩個約束條件

xr≤和xr≥＋1如此反復進行，直到得到Z＝Z*＝為止，即得最優(yōu)解X*

。

將這兩個約束條件分別加入問題(

IP)，形成兩個子問題(

IP1)和(

IP2)，再解這兩個問題的松弛問題(LP1)和(LP2)。4、修改上、下界：按照以下兩點規(guī)則進行。⑴.在各分枝問題中，找出目標函數(shù)值最大者作為新的上界；⑵.從已符合整數(shù)條件的分枝中，找出目標函數(shù)值最大者作為新的下界。5、比較與剪枝：

各分枝的目標函數(shù)值中，若有小于Z者，則剪掉此枝，表明此子問題已經(jīng)探清，不必再分枝了;否則繼續(xù)分枝。例一：用分枝定界法求解整數(shù)規(guī)劃問題（用圖解法計算）記為（IP）解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問題記為（LP）（二）、例題

用圖解法求（LP）的最優(yōu)解，如圖所示。x1x2⑴⑵33(18/11,40/11)⑶對于x1＝18/11≈1.64，取值x1≤1，x1≥2對于x2=40/11≈3.64，取值x2

≤3，x2

≥4先將（LP）劃分為（LP1）和（LP2）,取x1≤1,x1≥2x1＝18/11,x2=40/11Z(0)=－218/11≈(－19.8)即Z也是（IP）最小值的下限。有下式：

現(xiàn)在只要求出（LP1）和（LP2）的最優(yōu)解即可。x1x2⑴⑵33(18/11,40/11)⑶

先求（LP1）,如圖所示。此時B

在點取得最優(yōu)解。x1＝1,x2=3,Z(1)＝－16找到整數(shù)解，問題已探明，此枝停止計算。11同理求（LP2）

,如圖所示。在C

點取得最優(yōu)解。即x1＝2,x2=10/3,Z(2)

＝－56/3≈－18.7∵Z2<Z1＝－16∴原問題有比（－16）更小的最優(yōu)解，但x2不是整數(shù)，故利用

x2≤3,x2≥4

加入條件。BAC加入條件：x2≤3,x2≥4有下式：只要求出（LP3）和（LP4）的最優(yōu)解即可。x1x2⑴⑵33(18/11,40/11)⑶11BAC先求（LP3）,如圖所示。此時D在點取得最優(yōu)解。即x1＝12/5≈2.4,x2=3,Z(3)＝-87/5≈-17.4<Z≈-19.8但x1＝12/5不是整數(shù)，可繼續(xù)分枝。即3≤x1或x1≤2。D求（LP4），如圖所示。無可行解，不再分枝。

在（LP3）的基礎(chǔ)上繼續(xù)分枝。加入條件3≤x1≤2有下式：只要求出（LP5）和（LP6）的最優(yōu)解即可。x1x2⑴⑵33(18/11,40/11)⑶11BACD先求（LP5）,如圖所示。此時E

在點取得最優(yōu)解。即x1＝2,x2=3,Z(5)＝－17找到整數(shù)解，問題已探明，此枝停止計算。E求（LP6），如圖所示。此時F在點取得最優(yōu)解。x1＝3,x2=2.5,Z(6)＝－31/2≈－15.5>Z(5)

F

如對Z(6)

繼續(xù)分解，其最小值也不會低于－15.5

，問題探明,剪枝。

至此，原問題（IP）的最優(yōu)解為：

x1=2，

x2=3,

Z*=Z(5)

＝－17以上的求解過程可以用一個樹形圖表示如右：LP1x1=1,x2=3Z(1)

＝－16LPx1=18/11,x2=40/11Z(0)

＝－19.8LP2x1=2,x2=10/3Z(2)

＝－18.5LP3x1=12/5,x2=3Z(3)

＝－17.4LP4無可行解LP5x1=2,x2=3Z(5)

＝－17LP6x1=3,x2=5/2Z(6)

＝－15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃＃＃0－1整數(shù)規(guī)劃是一種特殊形式的整數(shù)規(guī)劃，這時的決策變量xi只取兩個值0或1，一般的解法為隱枚舉法。例一、求解下列0－1規(guī)劃問題三、0－1整數(shù)規(guī)劃

解：對于0－1規(guī)劃問題，由于每個變量只取0，1兩個值，一般會用窮舉法來解，即將所有的0，1組合找出，使目標函數(shù)達到極值要求就可求得最優(yōu)解。但此法太繁瑣，工作量相當大。而隱枚舉法就是在此基礎(chǔ)上，通過加入一定的條件，就能較快的求得最優(yōu)解。x1.x2.x3約束條件滿足條件Z值(1)(2)(3)(4)是∨否×(0.0.0)0000∨0(0.0.1)

－1101∨5(0.1.0)2414∨－2(1.0.0)1110∨3(0.1.1)15 ×(1.0.1)0211∨8(1.1.0)3×(1.1.1)26×

由上表可知，問題的最優(yōu)解為X*=(x1=1x2=0x3=1)由上表可知：x1=0x2=0x3=1

是一個可行解，為盡快找到最優(yōu)解，可將3

x1－2x2＋5x3≥5作為一個約束，凡是目標函數(shù)值小于5的組合不必討論，如下表。x1.x2.x3約束條件滿足條件Z值(0)(1)(2)(3)(4)是∨否×(0.0.0)00000∨0(0.0.1)5－1101∨5(0.1.0)-2×(0.1.1)3×(1.0.0)3×(1.0.1)80211∨8(1.1.0)1×(1.1.1)4×

例二、求解下列0－1規(guī)劃問題

解：由于目標函數(shù)中變量x1,x2,

x4

的系數(shù)均為負數(shù)，可作如下變換：

令x1

＝1－

x1′

,x2=1-x2′,x3=x3′,x4=1-x4′帶入原題中，但需重新調(diào)整變量編號。令x3′

=x1′,x4′=x2′得到下式。

可以從(1.1.1.1)開始試算，x′(3)＝(1.1.0.1)最優(yōu)解?！鄕(3)＝(1.0.1.0)是原問題的最優(yōu)解，Z*=－2例三、求解下列0－1規(guī)劃問題令y1=x5,y2=x4,y3=x2,y4=x3,y5=x1

得到下式y(tǒng)1.y2.y3.y4.y5約束條件滿足條件Z值(1)(2)是∨否×(0.0.0.0.0)00×(1.0.0.0.0)1-1×(0.1.0.0.0)-11×(0.0.1.0.0)-21×(0.0.0.1.0)4-4∨8(0.0.0.0.1)3-2×

所以，

Y*=（0.0.0.1.0），原問題的最優(yōu)解為：

X*

＝（0.0.1.0.0），Z*=8（0.1.1.0.0）練習：用隱枚舉法求解0—1規(guī)劃問題

在實際中經(jīng)常會遇到這樣的問題，有n項不同的任務(wù)，需要n個人分別完成其中的一項，但由于任務(wù)的性質(zhì)和各人的專長不同，因此各人去完成不同的任務(wù)的效率（或花費的時間或費用）也就不同。于是產(chǎn)生了一個問題，應(yīng)指派哪個人去完成哪項任務(wù)，使完成n項任務(wù)的總效率最高（或所需時間最少），這類問題稱為指派問題或分派問題。

（一）、指派問題的數(shù)學模型設(shè)n個人被分配去做n件工作，規(guī)定每個人只做一件工作，每件工作只有一個人去做。已知第i個人去做第j件工作的的效率（時間或費用）為Cij(i=1.2…n;j=1.2…n)并假設(shè)Cij≥0。問應(yīng)如何分配才能使總效率（時間或費用）最高？四、指派問題設(shè)決策變量1分配第i個人去做第j件工作

xij=0相反(I,j=1.2.…n)其數(shù)學模型為：

（二）、解題步驟：

指派問題是0-1規(guī)劃的特例，當然可用整數(shù)規(guī)劃，0-1規(guī)劃的解法去求解，但是利用指派問題的特點可有更簡便的解法，這就是匈牙利法。

第一步：變換指派問題的系數(shù)矩陣（cij）為(bij)，使在(bij)的各行各列中都出現(xiàn)0元素，即

(1)從（cij）的每行元素都減去該行的最小元素；

(2)再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素。

第二步：進行試指派，以尋求最優(yōu)解。在(bij)中找盡可能多的獨立0元素，若能找出n個獨立0元素，就以這n個獨立0元素對應(yīng)解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。找獨立0元素，常用的步驟為：

(1)從只有一個0元素的行(列)開始，給這個0元素加圈，記作◎。然后劃去◎所在列(行)的其它0元素，記作?；這表示這列所代表的任務(wù)已指派完，不必再考慮別人了。

(2)給只有一個0元素的列(行)中的0元素加圈，記作◎；然后劃去◎所在行的0元素，記作?．

(3)反復進行(1)，(2)兩步，直到盡可能多的0元素都被圈出和劃掉為止。(4)若仍有沒有劃圈的0元素，且同行(列)的0元素至少有兩個，則從剩有0元素最少的行(列)開始，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個0元素加圈(表示選擇性多的要“禮讓”選擇性少的)。然后劃掉同行同列的其它0元素。可反復進行，直到所有0元素都已圈出和劃掉為止。

（5）若◎元素的數(shù)目m等于矩陣的階數(shù)n，那么這指派問題的最優(yōu)解已得到。若m<n,則轉(zhuǎn)入下一步。

第三步：作最少的直線覆蓋所有0元素。

(1)對沒有◎的行打√號；

(2)對已打√號的行中所有含?元素的列打√號；

(3)再對打有√號的列中含◎元素的行打√號；(4)重復(2)，(3)直到得不出新的打√號的行、列為止；

(5)對沒有打√號的行畫橫線，有打√號的列畫縱線，這就得到覆蓋所有0元素的最少直線數(shù)l。l應(yīng)等于m，若不相等，說明試指派過程有誤，回到第二步(4)，另行試指派；若l＝m<n，須再變換當前的系數(shù)矩陣，以找到n個獨立的0元素，為此轉(zhuǎn)第四步。例一：

任務(wù)人員ABCD甲215134乙1041415丙9141613丁78119249742◎?◎??◎◎第四步：變換矩陣(bij)以增加0元素。在沒有被直線覆蓋的所有元素中找出最小元素，然后打√各行都減去這最小元素；打√各列都加上這最小元素（以保證系數(shù)矩陣中不出現(xiàn)負元素）。新系數(shù)矩陣的最優(yōu)解和原問題仍相同。轉(zhuǎn)回第二步。

有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作A、B、C、D。現(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時間如下表所示，問如何分派任務(wù)，可使總時間最少？

任務(wù)人員ABCD甲67112乙4598丙31104丁5982例二、求解過程如下：第一步，變換系數(shù)矩陣：