第五章 整數(shù)規(guī)劃

第五 整數(shù)規(guī)第一節(jié)ProgrammingProgrammingProgramming0-1010-1例1 以及托運(yùn)所受限制如表5-1：5-貨體每箱重每箱（百斤利每箱（百元都是非負(fù)整數(shù)。這是一個(gè)（純）Maxz=20x1+10 5x14x2 2x5x

x,x x1=4.8，x2=0，maxz=0條件②（關(guān)于體積的限制，因而它不是可行解；如將（x1=4.8x2=0）舍去=0x1=4x2=0時(shí)，zx1=4x2=1時(shí)（這也是可行解）時(shí)，z=905-1C（4.8，0）點(diǎn)達(dá)Cz的等值線必須zz=96z=90，它們的差值△z表示利潤(rùn)的降低，這是由于變量的不可分性（裝箱）第二 分解（1）R(pi)R(P)（2）R(pi)R(pj)

成立，則稱問(wèn)題（P）被分解為子問(wèn)題p1、p2、…、pm)之和。最常xi是問(wèn)題（P）0-1變量，則問(wèn)題（P）xi=0xi=1”分解為兩個(gè)子問(wèn)題之和。衍生松弛， ~。由此易知松弛問(wèn)題有如下三個(gè)有用的R(P性質(zhì) 若松弛問(wèn)題沒(méi)有可行解，則原問(wèn)題也一定沒(méi)有可行解性質(zhì) 松弛問(wèn)題目標(biāo)函數(shù)的最優(yōu)值給出原問(wèn)題目標(biāo)函數(shù)最優(yōu)值的一個(gè)（P）極大（?。┲挡淮螅ㄐ。┯冢≒）目標(biāo)函數(shù)的極大（?。┬再|(zhì)3 13132，通過(guò)求解第三節(jié)分枝定界法（BranchandBoundMethod）是通過(guò)有系統(tǒng)的“分枝”和“定例 求解下述整數(shù)規(guī)maxz4x1 4x1x2 2x13x2

x1,x2 x1x2 X(0)11

6

問(wèn)題（4.3）624.1另一方面，(0,0)T顯然是（4.3）0，

11,

6x2（x1當(dāng)然也可以

6x2=1x2=2，故可把原問(wèn)題（4.3）分解（即所謂進(jìn)行分枝）為如下兩個(gè)子問(wèn)maxz4x1 4x1x2 2x13x2

x1,x2 x2 x1x2maxz4x1 4x1x2 2x13x2

x1,x2 x2 x1x2X(1)

;

X(2)1,2T;z2X(2)1,2T已是問(wèn)題（4.5）的可行解從而也是其最優(yōu)解，故此解為原問(wèn)題（4.3）z2=10＞0，可知原問(wèn)題（4.3）目標(biāo)函數(shù)最優(yōu)值010z2z1z0，故4.2所示。（4.4

9,

1

9，按上面所說(shuō)的同樣方法，將問(wèn)題（4.4）

maxz4x1 4x1x2 2x13x2

0x 0x1 x1x2maxz4x1 4x1x2 2x13x2

0x x1 x1x24.3：

z3此解已是整數(shù)解，故為原問(wèn)題（4.3）z3=11＞10z2，z311作為原問(wèn)題（4.3）最優(yōu)目標(biāo)值的新上界。此時(shí)，問(wèn)題（4.3）的目標(biāo)函數(shù)最優(yōu)值的上界和下界相等，均為11z311，相應(yīng)的XnX(3)(2,1)T。用分枝定界法進(jìn)行求解的過(guò)程常表示成樹(shù)狀圖，并稱之為枚舉樹(shù)Treez。然后，解該整數(shù)規(guī)劃對(duì)應(yīng)的線性規(guī)劃2，規(guī)劃即其松弛問(wèn)題zznz。（1）xj≤[bj（2）xj≥[bj其中，bj]為數(shù)值不大于bj2繼續(xù)進(jìn)行分枝。第四節(jié)個(gè)有整數(shù)坐標(biāo)的極點(diǎn)恰好是問(wèn)題的最優(yōu)解為止。這個(gè)方法是由R．E．Gomory1958Gomory割平面法。例2 maxzx1x x1x2 3x1x2

x1,x2 x1x2

x3

x c—5/24.1x3x4分別4.5A點(diǎn)。x24.1x2所在這一行相當(dāng)于x3x1x4 4

03x01x1 3 4 4

14

3(1x 4

14

3 34

1x4

為了用原來(lái)的變量（而不是用松弛變量）表示，現(xiàn)將x31x1x2x443x1x2代入式（4.9）x2 （4.10，得maxzx1 x1x2 3x1x2

x1,x2A點(diǎn)在內(nèi)的一個(gè)三角形（4.6。（4.11（4.9，而不用（4.10x1x2=1z=2。這就是原整數(shù)規(guī)劃問(wèn)題（4.8）的最優(yōu)解。迭代過(guò)程于表4.2中，最優(yōu)點(diǎn)為圖4.6B點(diǎn)。cc3M M 3M 2 B1B

B1b, B1bi個(gè)分量bxiaijxj

現(xiàn)將系數(shù)aij和右側(cè)常數(shù)bi分為整數(shù)和非負(fù)真分?jǐn)?shù)兩部分，即

[bi]f(bif（）f(aij)xjf(bi)[bi]xi[aij]xj

當(dāng)要求解為非負(fù)整數(shù)時(shí)，式（4.15）的右端為整數(shù)，注意到0f(bi＜1f(aij)xj≥0，故上式右端為非負(fù)整數(shù)，從而應(yīng)有f(aij)xj現(xiàn)引入?？谱兞縮if(aij)xjsi

ff

si

式（4.16）和（4.17）Gomory約束，稱式（4.17）Gomory切割方由于在切割方程中sif(bi常常為正，故在把它加入松弛問(wèn)性質(zhì) 證假定問(wèn)題（4.1） B1b(b,b,,b)T,

(aij)0 f(bi)

f（4.161表明，切割方程（4.17）對(duì)可行域進(jìn)行了切割，它把非整數(shù)最優(yōu)解性質(zhì)2 足（4.162成立。（4.2則（4.1）也沒(méi)有可行解，停止；若（4.2）XnXn即為

xiaijxj

出的最優(yōu)解為整數(shù)解，則它就是問(wèn)題（4.1）2例3

z6x1 2x14x2 2x1x2 x1,x2 x1x2解先不考慮整數(shù)條件，解此問(wèn)題的松弛問(wèn)題。為此，在兩個(gè)約束不等式4.3cx5x x1 6

2x3 6

23

x5 56

23

4.4cj/都不是整數(shù)，我們?nèi)i的分?jǐn)?shù)部分最大者所對(duì)應(yīng)的變量為退出變量，因?yàn)閙ax4,634x4.4x10

x3 5

2x5 25 2

252

5 5 cxxx至此，我們已得到了原問(wèn)題的（整數(shù)）Xnx1x2)T3(3,1)Tzn=224.7第五節(jié)0-1xi01這量0-1xi01這個(gè)條件可由約束條xi≥0xi≤1xi為整數(shù)來(lái)代替，這和一般整數(shù)規(guī)劃的約束條件形式是一0-10-1變量，可以把有各種情況0-10-1變量還可把多種非線性規(guī)0-10-1規(guī)劃的一些簡(jiǎn)0-1=1，2，…，ncj均是整數(shù)。試問(wèn)為使所得利潤(rùn)最大，應(yīng)選取哪些項(xiàng)目進(jìn)行投資？0-1xjx

jmaxcjj ajxj j x

0或1j0-1背包問(wèn)題nm個(gè)可供選擇的廠址，每個(gè)廠址只能建一個(gè)工廠，在iDi，單位時(shí)間的固定成本為aij的需求量為bj，從廠址ij的單位運(yùn)費(fèi)為cij設(shè)在單位時(shí)間內(nèi)，從廠址ijxij0-1yi

minzcijxijai

j

xijDiyi j xij

i1,2,,j1,2,,

yi0或0-1變量后，就可以適應(yīng)種種“二中選一”或“多抉擇”設(shè)有rA(1)XA(2)Xb(A(r)Xb(rq組約束得到滿足，而其它rq組約束可滿足，也可以不不同）A(kXb(k)M(k對(duì)于與所考慮問(wèn)題有關(guān)Xyk0-1變量，則約束A(k)Xb(k)yM(k在

=0時(shí)相應(yīng)于約束A(kX

；在

=1時(shí)相應(yīng)于約束A(kXb(k)M(k，注意前面對(duì)M(kX不起約束作用。為（k=12rA(k)Xb(k)

M(k)

k1,2,,ykrxj0xjTj，Tj是它的一個(gè)有限的上界。于0 2 x 2x220 2 x（i=0，1，…，r）0-1變量，r是由不等式確定的整數(shù)。實(shí)際上，式（4.20xj

T2r11，就得到Tj0-1變量的通常意xj的又一表達(dá)形式。二、0-10-1規(guī)劃時(shí)，一種自然的想法是用枚舉法01的例

z2x1x2

x3 4x2x3

x3 x14x2x3 xi0或1,i 解（xxx）共有23=8 4.6約束（x1x2x3 0（001（100（1011max（0，－1，2，1）=2maxz2Xn1,0,0)T大（n＞10）2n相當(dāng)大。全枚舉法0-101組合，滿足所有約束條件并使目標(biāo)函數(shù)值最優(yōu)的組合就是0-1規(guī)劃的最優(yōu)解。

zcjxjj1j

aijx

bi,i1,2,, cj≥0bi0，所有約束條件方程必須是“≤”

z2x13x2

z2x13(1x2)

z2x13x23x3z2x13x2xj=0xj=1xj=1xj=010值，檢驗(yàn)解是否可行。若可01，將此子域再分成兩個(gè)子域。如此繼續(xù)第一步xj0值，檢驗(yàn)解是否可行。若可行，第二步10，使問(wèn)題分成兩個(gè)zz值大，不會(huì)是最優(yōu)解；如不可行， 式左端的自由變量當(dāng)系數(shù)為負(fù)時(shí)取值為1，系數(shù)為正時(shí)取值為0，這就是左端所第七步檢查有無(wú)自由變量。若有，轉(zhuǎn)第二步；若沒(méi)有，計(jì)算停止。目標(biāo)1值的一切可能組合都被隱含地考慮過(guò)了，不必再一一列舉。所以這種方法稱例 minz8x12x24x37x43x13x2x32x43x5 5x3x2xxx

7-8所示。經(jīng)過(guò)第一、二、三步，進(jìn)行第四步，子域的1的解[1，0，0，0，0]可z1=82z2=0z1，進(jìn)234。3的解[0，1，0，0，0]z3=2z1，不可行，但能通過(guò)兩個(gè)不等4進(jìn)行檢驗(yàn)計(jì)算。4的解[0，0，0，0，0]z4=0z1，不可行，進(jìn)行x1=0x2=0x3x4x5=0，求出左356。5的解[0，1，1，0，0]，z64x2=01x3=01，這樣計(jì)算速度可能快一些。第六 nn個(gè)人（或呢？這一類問(wèn)題就稱為分派問(wèn)題或指派問(wèn)題（AssignmentProblem。例 4.8所示。問(wèn)應(yīng)分派哪個(gè)人去完成哪項(xiàng)工作，可使總的消耗時(shí)間 工作0—1xijxij

i，jz55項(xiàng)工作所消耗的總時(shí)間，則可得出該問(wèn)題的數(shù)學(xué)

z5x116x128x134x143x214x226x236x245x315x327x339x346x417x425x437x447x414x526x532x54

xij

j

xijj

i

4.8稱為該問(wèn)題的價(jià)值系數(shù)表，它給出了這個(gè)問(wèn)題目標(biāo)函數(shù)中的各個(gè)系現(xiàn)假定一般分派問(wèn)題的價(jià)值系數(shù)矩陣的元素為cij，它表示由第i個(gè)人去完j項(xiàng)工作的資源消耗（價(jià)值或效率 minzcij

j j

1,j

0—1規(guī)劃的特例，也是運(yùn)輸問(wèn)題的特例（即mn，aibjj種有效算法：匈牙利法（HungarianAlgorithm。性質(zhì)假定Ccij為分派問(wèn)題（4.21）C作為（4.21）的價(jià)值系數(shù)矩陣，而構(gòu)成一新的分派問(wèn)題，則這個(gè)新分派問(wèn)Ccijlk，記由此所得的新矩陣為C(cij)。則機(jī)關(guān)報(bào)的分派問(wèn)題的目標(biāo)函數(shù) n z(X)cijxijcijxij(cilk)xij

j

j j cijxijkxili1j cijxijk

j

cijxijk·1z(X)i1j通過(guò)上述變換，即可使新價(jià)值系數(shù)矩陣Ccij)nnxij≥0和cij≥0對(duì)所有ij都成立，這樣的解就是新分派問(wèn)題的最優(yōu)解，它同時(shí)也是于不同行不同列的nxij=1，xij=0，這個(gè)解就是問(wèn)題的最優(yōu)解。因此，問(wèn)題的關(guān)鍵就在于尋求產(chǎn)Konig發(fā)展并證明了設(shè)已給定一個(gè)初始的nnCcij，運(yùn)用匈牙利法求最優(yōu)分找出(cij每行（或每列）的最小元素，將(cij的每行（或每列）的所有m條直線（水平的或豎直的）去覆蓋（或說(shuō)劃去）簡(jiǎn)約化價(jià)m=n，停止；可從上述簡(jiǎn)約化的價(jià)值矩陣的零元中找到一組位于不xij=1xij=0，m＜nm條直線覆蓋的元素中找出最小元素，從所有未被覆蓋3步。C0

找出價(jià)值系數(shù)矩陣C0每行的最小元素，各個(gè)元素分別減去相應(yīng)的最小元素后得新的價(jià)值系數(shù)矩陣C1：

5 1

1 C0

85C1

6

C1

11，得新矩陣C2 C1

10

C2

C2C2

(1)

5*

8

0(

6 8

x11x25x32x43x541xij最后回到原問(wèn)題中，其最優(yōu)目標(biāo)函數(shù)值為5+1+5+5+2=18；即讓甲去干工18。

zcij

j

1,j1,2,,

j

可令cijMcijM（如選cijM即可顯然cij≥0

zcij

j

1,j1,2,,

j

cijxij(Mcij Mxijcij MMxijcij M1cij n·Mcij nM為常數(shù)，故cijxijcijxi