整數(shù)規(guī)劃培訓(xùn)

整數(shù)規(guī)劃的模型分支定界法割平面法0－1整數(shù)規(guī)劃指派問題整數(shù)規(guī)劃例一、合理下料問題設(shè)用某型號(hào)的圓鋼下零件A1,

A2,…,Am

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

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

設(shè)：xj

表示用Bj(j=1.2…n)種方式下料根數(shù)模型：整數(shù)規(guī)劃的模型例三、機(jī)床分配問題設(shè)有m臺(tái)同類機(jī)床，要加工n種零件。已知各種零件的加工時(shí)間分別為a1,a2,…an

，問如何分配，使各機(jī)床的總加工任務(wù)相等，或者說盡可能平衡。設(shè)：1分配第i臺(tái)機(jī)床加工第j種零件；

xij＝（i=1,2,…,m;j=1,2,…,n）

0相反。于是，第i臺(tái)機(jī)床加工各種零件的總時(shí)間為：整數(shù)規(guī)劃的模型因此，求xij

，使得又由于一個(gè)零件只能在一臺(tái)機(jī)床上加工，所以有整數(shù)規(guī)劃的模型整數(shù)規(guī)劃一般形式依照決策變量取整要求的不同，整數(shù)規(guī)劃可分為純整數(shù)規(guī)劃、全整數(shù)規(guī)劃、混合整數(shù)規(guī)劃、0－1整數(shù)規(guī)劃。整數(shù)規(guī)劃的數(shù)學(xué)模型部分或者全部為整數(shù)純整數(shù)規(guī)劃：所有決策變量要求取非負(fù)整數(shù)（這時(shí)引進(jìn)的松弛變量和剩余變量可以不要求取整數(shù)）。全整數(shù)規(guī)劃：除所有決策變量要求取非負(fù)整數(shù)外，系數(shù)aij和常數(shù)bi也要求取整數(shù)（這時(shí)引進(jìn)的松弛變量和剩余變量也必須是整數(shù)）?；旌险麛?shù)規(guī)劃：只有一部分的決策變量要求取非負(fù)整數(shù)，另一部分可以取非負(fù)實(shí)數(shù)。0－1整數(shù)規(guī)劃：所有決策變量只能取0或1兩個(gè)整數(shù)。整數(shù)規(guī)劃的數(shù)學(xué)模型從數(shù)學(xué)模型上看整數(shù)規(guī)劃似乎是線性規(guī)劃的一種特殊形式，求解只需在線性規(guī)劃的基礎(chǔ)上，通過舍入取整，尋求滿足整數(shù)要求的解即可。但實(shí)際上兩者卻有很大的不同，通過舍入得到的解（整數(shù)）也不一定就是最優(yōu)解，有時(shí)甚至不能保證所得倒的解是整數(shù)可行解。整數(shù)規(guī)劃與線性規(guī)劃的關(guān)系例：設(shè)整數(shù)規(guī)劃問題如下首先不考慮整數(shù)約束，得到線性規(guī)劃問題（一般稱為松弛問題）。整數(shù)規(guī)劃與線性規(guī)劃的關(guān)系且為整數(shù)用圖解法求出最優(yōu)解x1＝3/2,x2=10/3且有Z=29/6x1x2⑴⑵33(3/2,10/3)現(xiàn)求整數(shù)解（最優(yōu)解）：如用“舍入取整法”可得到4個(gè)點(diǎn)即(1，3),(2，3),(1，4),(2，4)。顯然，它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問題的可行域內(nèi)且為整數(shù)點(diǎn)。故整數(shù)規(guī)劃問題的可行解集是一個(gè)有限集，如圖所示。整數(shù)規(guī)劃與線性規(guī)劃的關(guān)系因此，可將集合內(nèi)的整數(shù)點(diǎn)一一找出，其最大目標(biāo)函數(shù)的值為最優(yōu)解，此法為完全枚舉法。如上例：其中（2，2）（3，1）點(diǎn)為最大值，Z=4。目前，常用的求解整數(shù)規(guī)劃的方法有：分支定界法和割平面法；對(duì)于特別的0－1規(guī)劃問題采用隱枚舉法和匈牙利法。整數(shù)規(guī)劃與線性規(guī)劃的關(guān)系考慮純整數(shù)問題：整數(shù)問題的松弛問題：分枝定界法1、先不考慮整數(shù)約束，解(

IP)的松弛問題(LP)，可能得到以下情況之一：⑴.若(LP)沒有可行解，則(IP)也沒有可行解，停止計(jì)算。⑵.若(LP)有最優(yōu)解，并符合(IP)的整數(shù)條件，則(LP)的最優(yōu)解即為(IP)的最優(yōu)解，停止計(jì)算。⑶.若(LP)有最優(yōu)解，但不符合(IP)的整數(shù)條件，轉(zhuǎn)入下一步。為討論方便，設(shè)(LP)的最優(yōu)解為：分枝定界法2、定界：記(

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

作為Z*

的上界，記為＝Z(0)

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

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

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

（不為整數(shù)），以[b’r

]表示不超過b’r

的最大整數(shù)。構(gòu)造兩個(gè)約束條件

xr≤[b’r

]和xr≥[b’r

]＋1分枝定界法

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

IP)，形成兩個(gè)子問題(

IP1)和(

IP2)，再解這兩個(gè)問題的松弛問題(LP1)和(LP2)。4、修改上、下界：按照以下兩點(diǎn)規(guī)則進(jìn)行。⑴.在各分枝問題中，找出目標(biāo)函數(shù)值最大者作為新的上界；⑵.從已符合整數(shù)條件的分枝中，找出目標(biāo)函數(shù)值最大者作為新的下界。5、比較與剪枝：各分枝的目標(biāo)函數(shù)值中，若有小于Z者，則剪掉此枝，表明此子問題已經(jīng)探清，不必再分枝了;否則繼續(xù)分枝。如此反復(fù)進(jìn)行，直到得到Z＝Z*＝為止，即得最優(yōu)解X*

。分枝定界法例一：用分枝定界法求解整數(shù)規(guī)劃問題記為（IP）解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問題記為（LP）分枝定界法用圖解法求（LP）的最優(yōu)解，如圖所示。x1x2⑴⑵33(18/11,40/11)⑶對(duì)于x1＝18/11≈1.64，取值x1≤1，x1≥2對(duì)于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）,如圖所示。此時(shí)B

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

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

＝－56/3≈－18.7

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

加入條件。BAC分枝定界法加入條件：x2≤3,x2≥4有下式：只要求出（LP3）和（LP4）的最優(yōu)解即可。分枝定界法x1x2⑴⑵33(18/11,40/11)⑶11BAC先求（LP3）,如圖所示。此時(shí)D在點(diǎn)取得最優(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≤2。D求（LP4），如圖所示。無可行解，不再分枝。分枝定界法在（LP3）的基礎(chǔ)上繼續(xù)分枝。加入條件3≤x1≤2有下式：只要求出（LP5）和（LP6）的最優(yōu)解即可。分枝定界法x1x2⑴⑵33(18/11,40/11)⑶11BACD先求（LP5）,如圖所示。此時(shí)E

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

F如對(duì)Z(6)繼續(xù)分解，其最小值也不會(huì)低于－15.5，問題探明,剪枝。分枝定界法

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

x1=2，

x2=3,

Z*=Z(5)

＝－17以上的求解過程可以用一個(gè)樹形圖表示如右：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＃＃＃＃分枝定界法（一）、計(jì)算步驟：1、用單純形法求解(IP)對(duì)應(yīng)的松弛問題(LP)：⑴.若(LP)沒有可行解，則(IP)也沒有可行解，停止計(jì)算。⑵.若(LP)有最優(yōu)解，并符合(IP)的整數(shù)條件，則(LP)的最優(yōu)解即為(IP)的最優(yōu)解，停止計(jì)算。⑶.若(LP)有最優(yōu)解，但不符合(IP)的整數(shù)條件，轉(zhuǎn)入下一步。割平面法2、從(LP)的最優(yōu)解中，任選一個(gè)不為整數(shù)的分量xr,,將最優(yōu)單純形表中該行的系數(shù)和分解為整數(shù)部分和小數(shù)部分之和，并以該行為源行，按下式作割平面方程：3、將所得的割平面方程作為一個(gè)新的約束條件置于最優(yōu)單純形表中（同時(shí)增加一個(gè)單位列向量），用對(duì)偶單純形法求出新的最優(yōu)解，返回1。的小數(shù)部分的小數(shù)部分割平面法例一：用割平面法求解整數(shù)規(guī)劃問題解：增加松弛變量x3和x4

，得到(LP)的初始單純形表和最優(yōu)單純形表：Cj0100CBXBbx1x2x3x40x3632100x40-3201－Z00100Cj0100CBXBbx1x2x3x40x11101/6-1/61x23/2011/41/4－Z-3/200-1/4-1/4割平面法

此題的最優(yōu)解為：X*=

(1,3/2)Z=3/2但不是整數(shù)最優(yōu)解，引入割平面。以x2為源行生成割平面，由于1/4=0+1/4,3/2=1+1/2,我們已將所需要的數(shù)分解為整數(shù)和分?jǐn)?shù)，所以，生成割平面的條件為:也即：割平面法將x3=6-3x1-2x2,x4=3x1-2x2,帶入x1x2⑴⑵33第一個(gè)割平面得到等價(jià)的割平面條件：x2≤1,見下圖。割平面法Cj01000CBXBbx1x2x3x4s10x11101/6-1/601x23/2011/41/400s1-1/200-1/4-1/41－Z-3/200-1/4-1/40現(xiàn)將生成的割平面條件加入松弛變量，然后加到表中：CBXBbx1x2x3x4s10x12/3100-1/32/31x21010010x320011-4－Z-10000-1割平面法

此時(shí)，X1

＝(2/3,1),Z=1,仍不是整數(shù)解。繼續(xù)以x1為源行生成割平面，其條件為：

用上表的約束解出x4和s1，將它們帶入上式得到等價(jià)的割平面條件：x1≥x2，見圖：x1x2⑴⑵33第一個(gè)割平面第二個(gè)割平面割平面法將生成的割平面條件加入松弛變量，然后加到表中：CBXBbx1x2x3x4s1s20x12/3100-1/32/301x210100100x320011-400s2-2/3000-2/3-2/31－Z-10000-10CBXBbx1x2x3x4s1s20x10100-1011x20010-103/20x3600150-60s1100011-3/2－Z000010-3/2割平面法CBXBbx1x2x3x4s1s20x1110001-1/21x210100100x310010-53/20x4100011-3/2－Z-10000-10

至此得到最優(yōu)表，其最優(yōu)解為X＊=(1,1),Z=1,這也是原問題的最優(yōu)解。

有以上解題過程可見，表中含有分?jǐn)?shù)元素且算法過程中始終保持對(duì)偶可行性，因此，這個(gè)算法也稱為分?jǐn)?shù)對(duì)偶割平面算法。割平面法0－1整數(shù)規(guī)劃是一種特殊形式的整數(shù)規(guī)劃，這時(shí)的決策變量xi只取兩個(gè)值0或1，一般的解法為隱枚舉法。例一、求解下列0－1規(guī)劃問題0－1整數(shù)規(guī)劃

解：對(duì)于0－1規(guī)劃問題，由于每個(gè)變量只取0，1兩個(gè)值，一般會(huì)用窮舉法來解，即將所有的0，1組合找出，使目標(biāo)函數(shù)達(dá)到極值要求就可求得最優(yōu)解。但此法太繁瑣，工作量相當(dāng)大。而隱枚舉法就是在此基礎(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×0－1整數(shù)規(guī)劃由上表可知，問題的最優(yōu)解為X*=(x1=1x2=0x3=1)由上表可知：x1=0x2=0x3=1

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

x1－2x2＋5x3≥5作為一個(gè)約束，凡是目標(biāo)函數(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整數(shù)規(guī)劃

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

xij=0相反(I,j=1.2.…n)解題步驟：第一步：變換指派問題的系數(shù)矩陣（cij）為(bij)，使在(bij)的各行各列中都出現(xiàn)0元素，即(1)從（cij）的每行元素都減去該行的最小元素；(2)再?gòu)乃眯孪禂?shù)矩陣的每列元素中減去該列的最小元素。第二步：進(jìn)行試指派，以尋求最優(yōu)解。在(bij)中找盡可能多的獨(dú)立0元素，若能找出n個(gè)獨(dú)立0元素，就以這n個(gè)獨(dú)立0元素對(duì)應(yīng)解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。找獨(dú)立0元素，常用的步驟為：指派問題(1)從只有一個(gè)0元素的行(列)開始，給這個(gè)0元素加圈，記作◎。然后劃去◎所在列(行)的其它0元素，記作?；這表示這列所代表的任務(wù)已指派完，不必再考慮別人了。(2)給只有一個(gè)0元素的列(行)中的0元素加圈，記作◎；然后劃去◎所在行的0元素，記作?．(3)反復(fù)進(jìn)行(1)，(2)兩步，直到盡可能多的0元素都被圈出和劃掉為止。(4)若仍有沒有劃圈的0元素，且同行(列)的0元素至少有兩個(gè)，則從剩有0元素最少的行(列)開始，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個(gè)0元素加圈(表示選擇性多的要“禮讓”選擇性少的)。然后劃掉同行同列的其它0元素。可反復(fù)進(jìn)行，直到所有0元素都已圈出和劃掉為止。（5）若◎元素的數(shù)目m等于矩陣的階數(shù)n，那么這指派問題的最優(yōu)解已得到。若m<n,則轉(zhuǎn)入下一步。指派問題第三步：作最少的直線覆蓋所有0元素。(1)對(duì)沒有◎的行打√號(hào)；(2)對(duì)已打√號(hào)的行中所有含?元素的列打√號(hào)；(3)再對(duì)打有√號(hào)