整數(shù)規(guī)劃(運(yùn)籌學(xué))

第

3

章Integer

ProgrammingI

P整數(shù)規(guī)劃3.1整數(shù)規(guī)劃問題及其建模3.2分支定界法3.3割平面法3.40-1型整數(shù)線性規(guī)劃的解法3.5指派問題第3章整數(shù)規(guī)劃第3章整數(shù)規(guī)劃2基本概念整數(shù)規(guī)劃：變量取整數(shù)的線性規(guī)劃；純整數(shù)規(guī)劃：所有變量都取整數(shù)的線性規(guī)劃；混合整數(shù)規(guī)劃：部分變量取整數(shù)的線性規(guī)劃；0-1規(guī)劃：所有變量都取0、1兩個值的規(guī)劃；0-1混合規(guī)劃：部分變量取0、1兩個值的規(guī)劃。1、0-1變量的應(yīng)用

例1：某油田在10個有油氣構(gòu)造處要選擇若干個鉆探采油，設(shè)第j個構(gòu)造開采時需投資aj元，投產(chǎn)后預(yù)計年收益為cj元，若該油田投資的總限額為b元，問：應(yīng)選擇哪幾個構(gòu)造開采最為有利？設(shè)xj=10---選擇開采第j個構(gòu)造---不選擇開采第j個構(gòu)造maxz=Σcjxjj=110∑ajxjbxj＝0或1(j=1,2,---,10)j=110-----年總收益----投資額限制3.1

整數(shù)規(guī)劃問題及其建模

例2：上述例題中，如果在開采中需用電力，解決的方案或由電網(wǎng)供電或由自備的柴油機(jī)發(fā)電。已知第j個構(gòu)造開采時每天耗電量為dj度，電網(wǎng)每天供電量限制為f度。當(dāng)使用自備柴油機(jī)發(fā)電時，每度電平均耗油0.3公斤，而柴油供應(yīng)量限額為每天p公斤。試在模型中表示出該限制條件。采用電網(wǎng)供電：∑djxjf采用自備柴油機(jī)發(fā)電：∑0.3djxjpj=110j=110+(1－y1)M+(1－y2)My1+y2=1y1,y2=0或1M-----非常大的正數(shù)例3：若在開采時還需滿足下述條件：（a）若開采8號，則必須同時開采6號；（b）若開采5號，則不許開采3號；（c）2號和4號至少開采一個；（d）8號與7號必須同時開采；（e）1號、4號、6號、9號開采時不能超過兩個，試表示上述約束條件。（a）當(dāng)x8=1x6=1，x6≠0當(dāng)x8=0x6=1，x6=0∴x8

x6

（b）當(dāng)x5=1x3=0，x3≠1當(dāng)x5=0x3=0，x3=1∴

x5+x3

1（c）x2+x4

1（d）x8=x7（e）x1+x4+x6+x9

2例4：兩組條件滿足其中一組若x14，則x21，否則(x14)，則x23。設(shè)yi=10第i組條件起作用第i組條件不起作用則i=1,2x14＋(1-y1)Mx21－(1-y1)MM——充分大正數(shù)x14－(1-y2)Mx23＋(1-y2)My1＋y2=1y1，y2=0或1例3-1考慮固定成本的最小生產(chǎn)費(fèi)用問題

在最小成本問題中，設(shè)第j種設(shè)備的固定成本為

，運(yùn)行的變動成本為

，則生產(chǎn)成本與設(shè)備運(yùn)行時間的關(guān)系為：設(shè)第j種設(shè)備運(yùn)行每小時可以生產(chǎn)第i種產(chǎn)品

件，而第i種產(chǎn)品的定貨為

件。要滿足定貨同時使設(shè)備運(yùn)行的總成本最小的問題為：9混合0-1規(guī)劃線性規(guī)劃與整數(shù)規(guī)劃的關(guān)系10線性規(guī)劃整數(shù)規(guī)劃X*=（13/5，19/5）Z*=89/5=17.8X*=（5，3）Z*=17一、引例

某廠擬用集裝箱托運(yùn)甲、乙兩種貨物，每箱的體積、重量、可獲利潤及托運(yùn)時所受的限制如下表所示，問如何托運(yùn)能使總收益最大？貨物體積(米3/箱)重量(噸/箱)利潤(千元/箱)甲乙2 2 33 1 214 米3 9噸托運(yùn)限制3.2分支定界法建模：解：設(shè)托運(yùn)甲貨物x1箱，乙貨物x2箱Maxz=3x1+2x2 2x1+3x214 2x1+x29 x10，x20，且為整數(shù)24624(3.25,2.5)x1x22x1+3x2=142x1+x2=93x1+2x2=624624(3.5,2)x1x22x1+3x2=142x1+x2=93x1+2x2=6(2.5,3)24624(4,1)x1x22x1+3x2=142x1+x2=93x1+2x2=6(2.5,3)(3,2)分枝定界法:L0：z0=14.75x1=3.25，x2=2.5L1：z1=14.5L2：z2=13.5L3：z3=13L4：z4=14x1=3.5，x2=2x1=2.5，x2=3x1=3，x2=2x1=4，x2=1x2≤2x2≥3x1≤3x1≥4基本思想分支（Branch）定界（Bound）3.2分支定界法（B&B）第3章整數(shù)規(guī)劃xr≤Irxr≥Ir+1例3-2

用分枝定界法求解以下整數(shù)規(guī)劃先求得相應(yīng)的線性規(guī)劃的最優(yōu)解，為3.2分支定界法（B&B）第3章整數(shù)規(guī)劃1819Sub-6無可行解原問題Sub-2Sub-1Sub-3Sub-4Sub-5Sub-7Sub-9Sub-8Sub-10無可行解x2≤2x2≥3x1≤5x1≥5x2≤1x2≥2x1≤4x1≥6x2≤0x2≥1圖3-3.探索過程示意圖×√√3.3.1割平面法基本思想3.3

割平面法第3章整數(shù)規(guī)劃20設(shè)放棄變量整數(shù)要求得到的線性規(guī)劃的最優(yōu)單純形表如下：設(shè)其中基變量Xr的值br不是整數(shù)，以I表示整數(shù)，以F表示正的真分?jǐn)?shù)，令yrj=Irj+

Frj(0≤

Frj<1)

br=Ir+Fr

(0<

Fi

<1)將上面兩式代入約束r中，得3.3

割平面法第6章整數(shù)規(guī)劃21改寫成因此對于整數(shù)可行解，約束（3-2）可以寫成更嚴(yán)格的不等式這就是源于第r行的割平面。

⑴線性規(guī)劃的任何整數(shù)可行解都滿足這個約束；未切割掉任何一個整數(shù)解。

⑵線性規(guī)劃的非整數(shù)最優(yōu)解不滿足這個約束。切割掉了非整的LP解X；(3-4)3.3

割平面法第3章整數(shù)規(guī)劃22

2°

若Xk的分量全為整數(shù)，則Xk即為原問題的最優(yōu)解，停止計算；

否則根據(jù)Xk的一個非整分量所在單純形表的那一行，譬如第i行，構(gòu)造源于第

i行的割平面(3-4)

，并給它引入一個弛變量xn+k+1，得Frjxj+

xn+k+1

=-Frj=m+1

-

3°

把這個新約束添到最優(yōu)單純形表的倒第2行，并增加一列(即

xn+k+1列)，用對偶單純形法繼續(xù)迭代，求得一個新解Xk+1，令k:=k+1，返2°。

3.3.2割平面法基本步驟

1°

用單純形法求解IP的伴隨LP問題，得到其解X0，令k=0；n3.3

割平面法第6章整數(shù)規(guī)劃23

minz=3x1+4x23x1+x2≥4x1+2x2≥4

x1,

x2≥0

x1,

x2為整數(shù)s.t.例3-3

試用割平面法求解以下整數(shù)規(guī)劃：解求解線性規(guī)劃得最優(yōu)單純形表選擇一個非整數(shù)的基變量，例如x2=8/5，構(gòu)造約束條件(3-4）3.3割平面法第3章整數(shù)規(guī)劃24用對偶單純形法，x5離基，x3進(jìn)基，已獲得整數(shù)的最優(yōu)解：X*=（2，1）Z*=10第6章整數(shù)規(guī)劃25

maxz=

x1+x22x1+x2≤54x1-x2≥2

x1,

x2≥0

x1,

x2為整數(shù)s.t.

maxz=

x1+x2

2x1+x2+x3=5

-4x1+x2+x4

=

-2

x1,

x2,x3,

x4≥

0s.t.例:

試用割平面法求解：解

標(biāo)準(zhǔn)化并獲取排列陣：第6章整數(shù)規(guī)劃26

cj

基

解

x1

x2x3

x4

1

1

00序號

2

110x3x4

5-2

-

4

1

0100

0

1

1

00-

4

4

0

3/2

1

1/2x3x1

01

1/21

-1/4

0-1/4

1/2

0

5/4

0

1/43/211

x2x17/6

1

0

1/6

-1/6

8/3

0

1

2/3

1/323/60

0

-5/6

-1/6(a)(b)(c)

源于第一行構(gòu)造割平面：-

(x3+

x4)≤0232313

-

x3-

x4+

x5=

-232313①等價于x2

≤2

2

00

21

-3110

3/2101/2

0-1/2x2x1x4(b)cj

基

解

x1

x2x3

x4x5

1

1

00

0序號

x2x1x5

23/6

0

0

5/6

1/6

0-2/30

0-2/3

-1/31-1/3110

7/61

0

1/6-1/6

0

8/30

1

2/3

1/3

0(a)

2

01

001

7/2

00

1/2

0

1/2第6章整數(shù)規(guī)劃28源于第二行構(gòu)造割平面：-

(x3+

x5)≤0121212

-

x3-

x5+

x6=

-121212X1*=

(1,2)TX2*=

(2,1)Tz*

=

3②

等價于

x1+x2

≤3cj

基

解

x1x2

x3x4x5

x63

5

00

0

0

0

1

0

0

1

0x2x1

x4

x6

23/2

2

1

01/2

0

-1/2

01100

0

0

2

1

-3

07/2

0

01/2

0

1/2

0-1/2

0

0-1/2

0-1/2

1-1/2x2x1

x4

x3

1

0

0

1

0

1-2

0

0

0

0

1

-5

4

1

1

0

0

0

-1

1

2

0

1

0

0

10

3

0

0

0

0

01110010

11

22x1x2A(7/6,8/3)①x2

≤

2B(1,2)C(3/2,2)②x1

+

x2

≤

3

11

22x1x2B(1,2)C(3/2,2)D(2,1)隱枚舉法（ImplicitEumeration）例3-4用隱枚舉法求解下列問題

④③①②可行解：X=(1，0，0)，Z=3

增加過濾條件（filteringconstraint）

◎3.40-1型整數(shù)規(guī)劃的解法第3章整數(shù)規(guī)劃303.40-1型整數(shù)規(guī)劃的解法第3章整數(shù)規(guī)劃313.5指派問題及匈牙利算法(AssignmentProblem)一、問題的提出和數(shù)學(xué)模型例：有一份說明書，要分別譯成英、日、德、俄四種文字，交與甲、乙、丙、丁四個人去完成，因各人專長不同，他們完成翻譯不同文字所需要的時間（小時）如表所示。規(guī)定每項工作只能交與其中的一個人完成，每個人只能完成其中的一項工作。問：如何分配，能使所需的總時間最少？甲乙丙丁工作人譯英文譯日文譯德文譯俄文2109715414813141611415139建立模型：設(shè)xij=10譯英文：x11+x12+x13+x14=1譯日文：x21+x22+x23+x24=1譯德文：x31+x32+x33+x34=1譯俄文：x41+x42+x43+x44=1甲：x11+x21+x31+x41=1乙：x12+x22+x32+x42=1丙：x13+x23+x33+x43=1丁：x14+x24+x34+x44=1xij=0或1(i=1,2,3,4;j=1,2,3,4)Minz=aijxij (aij---效率)i=1j=144若第i項工作交與第j個人完成若第i項工作不交與第j個人完成分配問題一般數(shù)學(xué)模型結(jié)構(gòu)：

設(shè)有m項工作要交與m個人完成，其中第i項工作交與第j個人完成時所需花費(fèi)的時間為

aij。規(guī)定每項工作只能交與其中的一個人完成，而每個人只能完成其中的一項工作。問：如何分配，可使所需的總時間最少？Minz=aijxijst.xij=1xij=1i=1j=1j=1i=1mmmmxij=0或1(i=1,2,···,m;j=1,2,···,m)(i=1,2,···,m)(j=1,2,···,m)二、匈牙利法：基本思想：(0)564(0)563(0)(0)562

克尼格定理(konig)：如果從效率矩陣[aij]的每一行元素中分別減去(或加上)一個常數(shù)ui,從每列中分別減去(或加上)一個常數(shù)vj,得到一個新的效率矩陣[bij],其中bij=aij-ui-vj,則以[bij]為效率矩陣的最優(yōu)解等價于以[aij]為效率矩陣的最優(yōu)解.證明:以[aij]為效率矩陣的目標(biāo)函數(shù)值：z0=aijxij以[bij]為效率矩陣的目標(biāo)函數(shù)值：z=bijxijmmi=1j=1i=1j=1mm∵

bij=aij-ui-vj∴z=(aij-ui-vj)xij=aijxij-uixij-vjxij

=z0-uixij-

vjxijmmmmmmmmmm=z0-ui-vj=z0-constantmmi=1j=1i=1j=1i=1j=1i=1j=1i=1j=1j=1i=1i=1j=1mm三、步驟⑴使每行、每列都出現(xiàn)0元素方法：每行減該行最小元素；2109715414813141611415139-2-4-11-4min0875110104235001195min-0-0-5-0082511054230001145-2-2 -2+2+2080311032450001123每列減該列最小元素。⑵尋找位于不同行不同列的0元素準(zhǔn)則：A）從第一行開始，若只有一個0，則記（0），同時作直線覆蓋該列的元素。否則，轉(zhuǎn)下行；B）從第一列開始，若只有一個0，則記（0），同時作直線覆蓋該行的元素。否則，轉(zhuǎn)下列；C）重復(fù)A）、B），至再找不出這樣的0元素，轉(zhuǎn)D）D）可能出現(xiàn)三種情況： ①每行均有（0）元素，則在有（0）位置構(gòu)成最優(yōu)解中xij=1； ②多于兩行和兩列存在未被直線覆蓋的0元素，即存在0元素的閉回路，則沿回路頂點每間隔一個0記（），同時作直線覆蓋該列的元素；③所有0元素均有直線覆蓋，但記（0）的個數(shù)<m個，轉(zhuǎn)⑶。000000⑶迭代，尋找新的位于不同行不同列的0元素a）從未被直線覆蓋的元素中找出一個最小的元素amin； b）對行，若無直線覆蓋，則-amin；