所有分類05整數(shù)規(guī)劃2

第五章整數(shù)規(guī)劃整數(shù)規(guī)劃分類：全整數(shù)規(guī)劃（純整數(shù)規(guī)劃）—所有變量均取整部分整數(shù)規(guī)劃（混合整數(shù)規(guī)劃）—部分變量取整0—1整數(shù)規(guī)劃—變量的取值為0或1例1：集裝箱運(yùn)貨：貨物體積m3/箱重量百公斤/箱利潤(rùn)千元/箱甲5220乙4510貨運(yùn)限制2413一、整數(shù)規(guī)劃數(shù)學(xué)模型：數(shù)學(xué)模型：Maxz=20X1+10X25X1+4X2≤242X1+5X2≤13X1，X2≥0X1，X2為整數(shù)二、整數(shù)規(guī)劃的解法：LP問題可行域?yàn)樗倪呅蜲ABC，是凸集ILP問題可行域?yàn)樗倪呅蜲ABC中整數(shù)解常用方法：分枝定界法、割平面法、隱枚舉法例1數(shù)學(xué)模型：Maxz=20X1+10X25X1+4X2≤242X1+5X2≤13X1，X2≥0X1，X2為整數(shù)例1：線性規(guī)劃問題最優(yōu)解X=（4.8，0）；Z=96，該解為非整數(shù)最優(yōu)解若X=（4，0），Z=80；若X=（5，0），Z=100為非可行解其整數(shù)規(guī)劃問題最優(yōu)解X=（4，1）；Z=90X2﹢﹢﹢﹢﹢﹢﹢X1OABC﹢﹢﹢﹢123412第二節(jié)分枝定界法設(shè)整數(shù)規(guī)劃問題（記為A）該整數(shù)規(guī)劃相應(yīng)的線性規(guī)劃（松弛問題記為B）：其最優(yōu)解為：分枝定界法步驟：1.先不考慮整數(shù)約束條件，求相應(yīng)的線性規(guī)劃最優(yōu)解，若最優(yōu)解的所有分量都為整數(shù)，則已經(jīng)得到原整數(shù)規(guī)劃問題的最優(yōu)解,停止。否則，進(jìn)行分枝、定界2.進(jìn)行分枝、定界分枝:增加約束條件，將LP問題B的可行域分成若干子區(qū)域（子問題）定界：松弛問題最優(yōu)解一定是整數(shù)規(guī)劃問題最優(yōu)解目標(biāo)函數(shù)值的上限；已得到的整數(shù)解的目標(biāo)函數(shù)是整數(shù)規(guī)劃最優(yōu)解目標(biāo)函數(shù)值的下限。

上界：下界：分枝方法：在相應(yīng)線性規(guī)劃非整數(shù)最優(yōu)解中取某一非整數(shù)分量Xj，構(gòu)造兩個(gè)約束條件，形成兩個(gè)子線性規(guī)劃問題。設(shè)令[bj]表示小于bj的最大整數(shù)，則可構(gòu)造兩個(gè)新的約束條件為：將這兩個(gè)約束條件分別加入到相應(yīng)線性規(guī)劃問題B中，得到兩個(gè)子問題B1，B2。B1為：

B2為：例一：用分枝定界法求解

Maxz=40X1+90X29X1+7X2≤567X1+20X2≤70X1，X2≥0

X1，X2為整數(shù)問題(1)Maxz=40X1+90X29X1+7X2≤567X1+20X2≤70X1，X2≥0步驟：1、先解松弛問題x*=

4.8091.817Z*=355.89(A點(diǎn))2、分枝定界①定界：0≤Z≤355.89②選X1分枝

問題（2）(1)

X1≤4問題（3）(1)

X1≥5（3）45ABC（2）注：4<

X1<

5的中間區(qū)域不包含X1為整數(shù)的解,去掉,保留兩邊的子區(qū)域,構(gòu)成兩個(gè)子問題B1，B23.對(duì)B1及B2仍不考慮整數(shù)約束條件，分別進(jìn)行求解，進(jìn)一步修正上下界。為B1，B2最優(yōu)解中較大的目標(biāo)函數(shù)值為符合整數(shù)條件的整數(shù)解中最大目標(biāo)函數(shù)值，否則為零4.剪枝對(duì)于子問題的最優(yōu)目標(biāo)函數(shù)值小于下界的，可剪去。對(duì)于子問題最優(yōu)目標(biāo)函數(shù)值大于下界的，而又沒有得到整數(shù)解，可繼續(xù)分枝，直到得到整數(shù)規(guī)劃問題的最優(yōu)解或者判定原問題無最優(yōu)解。問題(1)

Maxz=40X1+90X29X1+7X2≤567X1+20X2≤70X1，X2≥0步驟：1、解松弛問題(1)x*=

4.8091.817Z*=355.89(A點(diǎn))2、分枝定界①定界：0≤Z≤355.89②選X1分枝

問題（2）

(1)

X1≤4問題（3）(1)

X1≥5最優(yōu)解為x*=(4,2.1)Z*=349（B點(diǎn)）最優(yōu)解為x*=(5,1.57)Z*=341.39（C點(diǎn)）3、選（2）繼續(xù)分枝定界：0≤Z≤349問題（5）(2)

X2≥3問題（4）(2)

X2≤2上例:A（4.81，1.82）Z=355.89B（4，2.1)，Z=349C（5，1.57），Z=341.3945ABC問題(1)

Maxz=40X1+90X29X1+7X2≤567X1+20X2≤70X1，X2≥0(1)

Z=0

4.809355.89

1.817

X1≤4X1≥5

(2)

Z=0

4349

2.1

(3)

Z=0

5

341.39

1.571

X2≤2X2≥3

(4)

Z=0

4340

2

(5)

Z=340

1.428

327.12

3

X2≤1X2≥2×剪枝

(6)

Z=340

5.444

307.76

1

×剪枝

(7)

Z=340

無解

分枝定界一般步驟：1.先解（A）的松弛問題（B）（B）的解有下列三種情況①（B）無可行解→（A）無可行解②（B）的最優(yōu)解符合（A）的要求，停；③（B）的最優(yōu)解不符合（A）的要求，其目標(biāo)值作為上限ZO2.用觀察法找（A）的一個(gè)整數(shù)可行解；一般取xj=0，j=1，2，3，…n，其目標(biāo)函數(shù)值作為整數(shù)最優(yōu)解目標(biāo)值的下界，記z3.選（B）解中不符合整數(shù)要求的分量xj（xj=bj）分枝，作（B）的后續(xù)問題（C）、（D）（C）：（B）加約束xj≤[bj]

（D）：（B）加約束xj≥[bj]+1剪枝條件①（C）（D）無可行解②（C）（D）對(duì)應(yīng)的目標(biāo)值

≤

z

③（C）（D）對(duì)應(yīng)的目標(biāo)值z(mì)c

≧

z

且解為整數(shù)解，令

zc

=

z

且解為非整數(shù)解，令（C）（D）取代（B）返回（4）4.全部枝剪完3200CB

XB

b

x1x2x3x40x3921109/20x414230114/2-Z032003200CB

XB

b

x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4-1/4解:用單純形法解對(duì)應(yīng)的(LP)問題,如表所示,獲得最優(yōu)解。初始表最終表例二、用分枝定界法求解整數(shù)規(guī)劃問題（單純形法）

x1=13/4

x2=5/2Z(0)=59/4≈14.75

選x2進(jìn)行分枝，即增加兩個(gè)約束，2≥x2≥3有下式：分別在(LP1)和(LP2)中引入松弛變量x5和x6

，將新加約束條件加入上表計(jì)算。即x2+x5=2,－x2+x6=－3

得下表:32000CB

XB

b

x1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200x5201001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x5-1/2001/2

-1/21-Z-59/400-5/4-1/403x17/2101/20-1/22x22010010x4100-11-2-Z-29/200-3/20-1/2x1=7/2,x2=2

Z(1)=29/2=14.5繼續(xù)分枝，加入約束

3≥x1≥4LP132000CB

XB

b

x1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200x6-30-1001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x6-1/200-1/2

1/21-Z-59/400-5/4-1/403x15/21001/23/22x230100-10x31001-1-2-Z-27/2000-3/2-5/2LP2x1=5/2,x2=3

Z(2)=27/2=13.5∵

Z(2)<Z(1)∴先不考慮分枝接(LP1)繼續(xù)分枝，加入約束4≤x1≤3，有下式：分別引入松弛變量x7和x8，然后進(jìn)行計(jì)算。CB

XB

b

x1x2x3x4x5x73x17/2101/20-1/202x220100100x4100-11-200x73100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100x4100-11-200x7-1/200-1/201/21-Z-29/200-3/20-1/203x131000012x220100100x420001-3-20x310010-1-2-Z-130000-2-3

x1=3,x2=2

Z(3)=13找到整數(shù)解，問題已探明，停止計(jì)算。LP3CB

XB

b

x1x2x3x4x5x83x17/2101/20-1/202x220100100x4100-11-200x8-4-100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100x4100-11-200x8-1/2001/20-1/21-Z-29/200-3/20-1/203x1410000-12x210110020x4300-310-40x5100-101-2-Z-1400-200-1

x1=4,x2=1

Z(4)=14找到整數(shù)解，問題已探明，停止計(jì)算。LP4樹形圖如下：LP1x1=7/2,x2=2Z(1)＝29/2=14.5LPx1=13/4,x2=5/2Z(0)＝59/4=14.75LP2x1=5/2,x2=3Z(2)＝27/2=13.5LP3x1=3,x2=2Z(3)＝13LP4x1=4,x2=1Z(4)＝14x2≤2x2≥3x1≤3x1≥4＃＃＃割平面法◆用于解決純整數(shù)規(guī)劃問題計(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)入下一步。例:Maxz=X1+X2﹣X1+X2≤13X1+X2≤4X1,X2≧0且為整數(shù)

松弛問題:

Maxz=X1+X2

﹣X1+X2≤1

3X1+X2≤4X1,X2≧0先求松弛問題最優(yōu)解最終表見右表XbbX1

X2X3X4X13/410﹣1/41/4X27/4013/41/4

00﹣1/2﹣1/22.增加約束條件切割松弛問題可行域。從(LP)的最優(yōu)解中，任選一個(gè)不為整數(shù)的分量xr,,將最優(yōu)單純形表中該行的系數(shù)和右端常數(shù)分解為整數(shù)和非負(fù)真分?jǐn)?shù)之和，建立割平面方程。若選X1，寫出X1在最終表中對(duì)應(yīng)的方程

X1﹣1/4X3+1/4X4=3/4XbbX1

X2

X3X4X13/410﹣1/41/4X27/4013/41/4

00﹣1/2﹣1/2

◆割平面求法:X1在最終表中對(duì)應(yīng)的方程

X1﹣1/4X3+1/4X4=3/4

將所有變量系數(shù)及右端常數(shù)表示成整數(shù)和小數(shù)（或非負(fù)真分?jǐn)?shù)）之和X1+（﹣1+3/4）X3+1/4X4=3/4

將整數(shù)及整數(shù)系數(shù)的變量移至左側(cè)，其余在右側(cè)

X1﹣X3=3/4﹣(3/4X3+1/4X4)

若所有變量均取整數(shù)，則3/4﹣(3/4X3+1/4X4)≤0﹣3/4X3﹣

1/4X4≤﹣3/4

割平面方程即：﹣3X3﹣X4≤

﹣3

化標(biāo)準(zhǔn)型﹣3X3﹣X4+X5=

﹣33、把新增約束加到原整數(shù)規(guī)劃問題中，仍不考慮整數(shù)約束條件，求相應(yīng)松弛問題最優(yōu)解。

11000XB

bX1X2

X3

X4

X5X1X2X53/47/4﹣3

10﹣1/41/40

013/41/40

00

﹣3*﹣1100﹣1/2﹣1/20X1X2

X31

11

1001/31/1201001/4001-1-1/3000

-1/3-1/6割平面方程的幾何意義：割平面方程

-3/4X3-1/4X4≤-3/4

即-3X3-X4≤-3，將X3、X4用X1、X2表示-3（1+X1-X2）-（4-3X1–X2）≤-3即X2≤1∵∵∵∵∵∵∵∵∵∵∵∵。11（3/4，7/4）X2X1∷松弛問題:

Maxz=X1+X2

﹣X1+X2≤1

3X1+X2≤4X1,X2≧0例二：用割平面法求解數(shù)規(guī)劃問題Cj1100CBXBbx1x2x3x40x3621100x4204501－Z1100CBXBbx1x2x3x41x15/3105/6－1/61x28/301－2/31/3－Z-13/300－1/6－1/6初始表最優(yōu)表在松弛問題最優(yōu)解中，x1,x2

均為非整數(shù)解，由上表有：將系數(shù)和常數(shù)都分解成整數(shù)和非負(fù)真分?jǐn)?shù)之和以上式子只須考慮一個(gè)即可，解題經(jīng)驗(yàn)表明，考慮式子右端最大真分?jǐn)?shù)的式子，往往會(huì)較快地找到所需割平面約束條件。以上兩個(gè)式子右端真分?jǐn)?shù)相等，可任選一個(gè)考慮。現(xiàn)選第二個(gè)式子，并將真分?jǐn)?shù)移到右邊得：引入松弛變量s1后得到下式，將此約束條件加到上表中，繼續(xù)求解。Cj11000CBXBbx1x2x3x4s11x15/3105/6－1/601x28/301－2/31/300s1－2/300－1/3－1/31－Z－13/300－1/6－1/60Cj11000CBXBbx1x2x3x4s11x10100－101x240101－20x320011－3－Z－40000－1/2﹡得到整數(shù)最優(yōu)解，即為整數(shù)規(guī)劃的最優(yōu)解，而且此整數(shù)規(guī)劃有兩個(gè)最優(yōu)解：X＊=(0,4),Z=4,或X＊=(2,2),Z=4。

割平面求法：設(shè)松弛問題的最優(yōu)解X*=（X1，X2，……Xn，Y1，Y2，……Yn）基變量X1，X2，……Xn；非基變量Y1，Y2，……YnXi不是整數(shù)Xi+∑aijyj

=bi（誘導(dǎo)方程）①——bi=bi+βibi、

aij為整數(shù)

aij

=aij

+αij0

＜

βi＜1

、0＜

αij

＜1～～～～——①式變?yōu)?/p>

Xi

+∑aijyj

–bi=βi—∑αijyj②～～且βi—∑αijyj

≤0加松弛變量Si（整數(shù)

）

βi—∑αijyj+

Si=0③——割平面方程③式滿足（1）沒有割去原來的整數(shù)解（2）割去了非整數(shù)最優(yōu)解小結(jié)（1）適宜中小型問題，也可解混合整數(shù)規(guī)劃問題（2）收斂較慢，舍入誤差大（3）割平面取法不唯一LP1x1=1,x2=7/3Z(1)＝10/3LPx1=3/2,x2=10/3Z(0)＝29/6LP2x1=2,x2=23/9Z(2)＝41/9x1≤1x1≥2LP5x1=1,x2=2Z(5)＝3LP6無可行解＃＃x2≤2x2≥3LP3x1=33/14,x2=2Z(3)＝61/14LP4無可行解x2≤2x2≥3＃LP7x1=2,x2=2Z(7)＝4LP8x1=3,x2=1Z(8)＝4x1≤2x1≥3＃＃作業(yè)0—1整數(shù)規(guī)劃問題例2：背包問題：背包可裝8公斤重量、10單位體積物品物品名稱重量體積價(jià)值1書52202攝象機(jī)31303飲料14104食品23185衣服4515Maxz=20X1+30X2+10X3+18X4+15X55X1+3X2+X3+2X4+4X5≤82X1+X2+4X3+3X4+5X5≤10Xi=0或1數(shù)學(xué)模型：設(shè)Xi表示是否帶第I種物品，Xi=0或1i=1，2，3，4，5）Xi=0表示不帶第i種物品；

Xi=1表示帶第i

種物品0—1決策變量可應(yīng)用于相互排斥的計(jì)劃中例3：若例一運(yùn)輸方式為火車或船火車：5X1+4X2≦

24（體積）船：7X1+3X2≦45

（體積）

X3=0時(shí)用火車；

X3=1用船2X1+5X2≤135X1+4X2≤24+MX37X1+3X2≤45+M（1-X3）X1X2≧0且為整數(shù)；X3=0或1；M＞0例一數(shù)學(xué)模型：Maxz=20X1+10X25X1+4X2≤242X1+5X2≤13X1，X2≥0X1，X2為整數(shù)增加0——1變量

X3,當(dāng)例4：選址問題：B3B4B2A3B1A2A1Ai可建倉庫地點(diǎn)、容量為ai

，投資費(fèi)bi，建2個(gè)；Bj商店，需求dj

,

j=1，2，3，4Cij

倉庫i到倉庫j單位運(yùn)費(fèi)要求選擇適當(dāng)?shù)攸c(diǎn)建倉庫，在滿足商店需求條件下，總費(fèi)用最小設(shè)Xi表示是否在Ai

建倉庫，

Xi=1建，Xi=0不建Yij表示從i倉庫到j(luò)商店運(yùn)量Minz=∑biXi+∑∑CijYij∑Xi=2

Y11+Y21=d1

Y12+Y22+Y32=d2

Y23+Y33=d3

Y14+Y24+Y34=d4Y11+Y12+Y14≤a1X1Y21+Y22+Y23+Y24≤a2X2Y32+Y33+Y34≤a3X3Xi為0或1，Yij≥0

隱枚舉法用于解決0——1規(guī)劃問題步驟1）用試探法求出一可行解，其目標(biāo)值作為當(dāng)前最好值ZO2）增加過濾條件Z≥ZO

3）將Xj按Cj由小到大排列觀察得解（X1，X2，X3）=（1，0，0）Z0=3

過濾條件3X1-2X2+5X3≥3

將（X1，X2，X3）→（X2，X1，X3）（X2，X1，X3）目標(biāo)值

Z0①②③④當(dāng)前最大值0000＜0015＞√√√√50103

＜0118＞√√√√8100-2＜1

013

＜11

01＜1116＜最優(yōu)解為（1，0，1）maxz=3X1-2X2+5X3

X1+2X2-

X3≤2

X1+4

X2+

X3≤4X1+

X2≤3

4

X2+

X3

≤6X1，X2，X3等于0或1一、數(shù)學(xué)模型；例：有一份中文說明書需翻譯成英、日、德、俄四種文字，有甲乙丙丁四人，他們將中文說明書翻譯成不同語種需要的時(shí)間如表所示，問派何人完成何工作，使所需總時(shí)間指派問題

EJGR甲215134乙1041415丙9141613丁78119EJGR甲215134乙1041415丙9141613丁78119Minz=2X11+15X12+13X13+4X14

+10X21+4X22+14X23+15X24+9X31+14X32+…+9X44

引入變量Xij=數(shù)學(xué)模型：1表示第I人完成第j項(xiàng)工作0表示第I人不完成第j項(xiàng)工作每人只做一項(xiàng)工作X11+X12+X13+X14=1X21+X22+X23+X24=1X31+X32+X33+X34=1X41+X42+X43+X44=1Xij=1或0每項(xiàng)工作由一人來做

X11+

X21+

X31+

X41=1X12+

X22+

X32+

X42=1X13+

X23+

X33+

X43=1X14+

X24+

X34+

X44=1一般類型：Minz=∑∑CijXij

匈牙利法求解思想：◆整體最優(yōu)◆相對(duì)比較選優(yōu)◆系數(shù)矩陣的某行某列減去或加上一個(gè)常數(shù)，不影響分配關(guān)系◆為方便求解，選擇變換系數(shù)矩陣，使每行每列都含有零元素◆位于不同行不同列零元素(獨(dú)立0元素)的最多個(gè)數(shù)等于覆蓋所有零元素的最小直線數(shù)Xij=0或1計(jì)算步驟：◆變換系數(shù)矩陣使每行每列都含零元素◆最優(yōu)解判別若覆蓋所有零元素的最小直線數(shù)等于矩陣行數(shù)，（即有n個(gè)獨(dú)立0元素）則可進(jìn)行最優(yōu)分配。

令n個(gè)獨(dú)立0元素對(duì)應(yīng)解矩陣(xij)中的元素為1，其余為0，就得到最優(yōu)解?！粜拚禂?shù)矩陣所有未被直線覆蓋元素減去其中最小數(shù)，將此最小數(shù)加到交叉位置處◆確定最優(yōu)方案從含零元素最小的行（或列）先分配①每行減去該行最小元素EJGR01311260101105740142甲乙丙?、诿苛袦p去該列最小元素EJGR甲乙丙丁06001305176300920EJGR甲215134乙1041415丙9141613丁781197630EJGR甲乙丙丁0600130510920EJGR甲乙丙丁06001305176300920④最優(yōu)分配：甲→R

乙→J

丙→E丁→G解矩陣?yán)呵笙卤硇示仃嚨闹概蓡栴}最優(yōu)解A

B

CDE甲乙丙丁戊1279798966671712149152466104107109502022300001057298004063657020243000083501180040414370202430000835011800404143所有未被直線覆蓋元素減去其中最小數(shù)，將此最小數(shù)加到交叉位置處當(dāng)n較小時(shí)可直接觀察出覆蓋所有零元素的最小直線數(shù)，當(dāng)n較大時(shí)，可用標(biāo)號(hào)法確定：用標(biāo)號(hào)法確定覆蓋所有零元素的最小直線數(shù)方法：（1）行標(biāo)號(hào)有兩個(gè)以上零的行中的零先不標(biāo)號(hào)有一個(gè)零的行中的零先標(biāo)號(hào)，記作◎，該零所在列中其他零劃掉，表示此項(xiàng)工作已分配，不再分配給其他人（2）列標(biāo)號(hào)同上（3）重復(fù)以上兩步直到出現(xiàn)下面三種情況之一：①每行每列都有一個(gè)◎的零，則可直接進(jìn)行分配②并非所有零均已標(biāo)號(hào)，但按（1）、（2）標(biāo)號(hào)無法進(jìn)行（同行同列至少有兩個(gè)零元素），則從剩有零元素最小的行或列開始標(biāo)，比較該行（列）各零元素所在列中零元素的數(shù)目，選擇零元素小的那列的這個(gè)零先加圈，然后劃掉同行同列中其他零，反復(fù)進(jìn)行直到所有零元素加圈或劃去③所有零均已標(biāo)號(hào)但并非①，則進(jìn)行（4）（4）在未標(biāo)◎行右側(cè)標(biāo)√，在標(biāo)√的行中找出被化掉的零所在的列，在此列下方打√；在打√的列中找出加圈的零所在的行，在此行右側(cè)打√，重復(fù)以上過程，直到無法打√為止50202230000105729800406365√√√（5）對(duì)所有打√的列和未打√的行畫直線就是覆蓋所有零元素的最小直線數(shù)。38