運(yùn)籌學(xué)課件：空中交通系統(tǒng)整數(shù)規(guī)劃

空中交通系統(tǒng)優(yōu)化與管理

整數(shù)規(guī)劃4.1

整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn)純整數(shù)線性規(guī)劃問題：所有

xj

的解為整數(shù)混合整數(shù)規(guī)劃問題：部分

xj

的解為整數(shù)0-1整數(shù)規(guī)劃問題：所有

xj

的解為0或者14.1.1

模型的一般形式：maxz

CX

X

0 且為整數(shù)

AX

bs.t.若線性規(guī)劃問題xj不取整，則稱該線性規(guī)劃為對(duì)應(yīng)該整數(shù)問題的松弛問題，解為整數(shù)問題解的松馳解4.1.1

整數(shù)規(guī)化數(shù)學(xué)模型的一般形式：4.1.2

整數(shù)規(guī)化的例子及模型建立：例4.1：某廠用集裝箱托運(yùn)甲、乙兩種貨物，每個(gè)集裝箱的體積、積重量、可獲利及托運(yùn)限制如下表所示。問兩種貨物各托運(yùn)多少箱可使獲得的利潤(rùn)最大？貨物體積(米3)重量(百斤)利潤(rùn)(百元)甲5220乙4510托運(yùn)限制2413解：設(shè)x1

，x2分別為甲、乙兩種貨物托運(yùn)的箱數(shù)。則數(shù)學(xué)模型為：maxz

20x1

10x2

1 2

x

,

x

0 且為整數(shù)

s.t.

2x1

5x2

135x1

4x2

244.1

整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn)4.1

整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn)產(chǎn)品A產(chǎn)品B資源限量勞動(dòng)力84360設(shè)

備35200原材料210300利潤(rùn)元/臺(tái)60804.1.2

整數(shù)規(guī)化的例子及模型建立：例4.2 設(shè)備生產(chǎn)計(jì)劃問題某設(shè)備可以生產(chǎn)兩種產(chǎn)品，需要三種資源，已知各產(chǎn)品的利潤(rùn)、各資源的限量和各產(chǎn)品的資源消耗系數(shù)如表4-1,問題是如何安排生產(chǎn)計(jì)劃，使得獲利最多?表4-14.1

整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn)x1

臺(tái)，B產(chǎn)品x2臺(tái)maxz

60x1

80x28x1

4x2

3603x1

5x2

2002x1

10x2

300x1

0,x2

0解：建模分析步驟為：1、確定決策變量：設(shè)生產(chǎn)A產(chǎn)品2、確定目標(biāo)函數(shù)：3、確定約束條件：人力約束設(shè)備約束原材料約束非負(fù)性整數(shù)約束且取整數(shù)4.1.2

整數(shù)規(guī)化的例子及模型建立：4.1

整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn)4.1.2

整數(shù)規(guī)化的例子及模型建立：例4.2

人員安排問題對(duì)于一個(gè)零售企業(yè)的部門經(jīng)理，需要根據(jù)實(shí)際情況安排職員的工作時(shí)間。根據(jù)統(tǒng)計(jì)和調(diào)查，每天需要在班上工作的職員數(shù)目分別為：工作日星期一星期二星期三星期四星期五星期六星期日要求人數(shù)20131012161820每個(gè)職員要求5天一次輪班，即連續(xù)工作5天，然后連續(xù)休息2天；正常工作日（星期一~星期五）每個(gè)員工每天工資60元，星期六、星期日每人每天工資分別為85元和95元。在滿足如上要求的前提下，如何安排每天（星期一~星期日）開始輪班的人數(shù)，才能使企業(yè)每周所支出的總工資最少，試建立該問題的數(shù)學(xué)模型。4.1

整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn)17155 6 74.1.2

整數(shù)規(guī)化的例子及模型建立：解：設(shè)星期一到星期日開始輪班的人數(shù)分別為x1、x2、x3、x4、x5、x6、x7，根據(jù)分析計(jì)算，對(duì)應(yīng)每人每周的工資分別為：300元/人、325元/人、360元/人、360元/人、360元/人、360元/人、335元/人。要求每周支出總工資最小，且滿足每天的職員數(shù)目要求，即：Min z

300x1

325x2

360(x2

x4

x5

x6)

335x7

x1

x4

x5

x6

x7

20

x

x1

x2

x5

x6

x7

13

x2

x3

x6

x7

10

x

1

x

x2

x3

x4

xx2

x3

x4

x5

x6

x2

x3

x4

x

12

16

18

x3

x4

x

x

x

20x

j

(

j

1,

,

7)為非負(fù)整數(shù)4.1.2

整數(shù)規(guī)化的例子及模型建立：例4.3 設(shè)備購置問題某個(gè)航空公司為了擴(kuò)大經(jīng)營(yíng)規(guī)模想購置一批航空維修設(shè)備，投資的資金總額為N元，想購買的設(shè)備種類為n種分別為A1,

A2,

......,

An，其中設(shè)備Ai單價(jià)為Pi

(i=1,2,…,n)，現(xiàn)有m個(gè)不同的分公司B1,

B2,

......

,

Bm需要安裝這些設(shè)備，其中Bj公司最多可需要bj臺(tái)(j=1,2,…,m)。預(yù)計(jì)將一臺(tái)設(shè)備Ai裝置于Bj公司可以盈利cij元，則該航空公司應(yīng)如何購買安裝這些設(shè)備，使得航空公司獲得的整體利潤(rùn)最大。4.1

整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn)解：分別設(shè)yi為購買設(shè)備Ai的臺(tái)數(shù)，xij為將設(shè)備Ai裝置于Bj公司的臺(tái)數(shù)，z為預(yù)計(jì)總利潤(rùn)（元）。根據(jù)題意得數(shù)學(xué)規(guī)劃模型為n mz

cijxiji

1 j

1mnmaxxij

yi

0，

i

1，2，

，ns.t.ijx

b

j，

j

1，2，

，

mijiiji

0，

y

0，

x ，

y

均為整數(shù)

j

1

i

1

n

i

1

x

piyi

M4.1

整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn)4.1.2

整數(shù)規(guī)化的例子及模型建立：4.1.2

整數(shù)規(guī)化的例子及模型建立：例4.4 機(jī)場(chǎng)選址問題為了實(shí)現(xiàn)n個(gè)城市間實(shí)現(xiàn)航線連接要修建機(jī)場(chǎng)，不同城市間的客流量為bj人/天(j=1,2,…,n)，現(xiàn)擬在m個(gè)城市中進(jìn)行選擇修建機(jī)場(chǎng)，來滿足客流量的需求，備選的每個(gè)城市最多只能修建一個(gè)機(jī)場(chǎng)。若選擇i城市修建機(jī)場(chǎng)，將來的運(yùn)輸能力為ai人/天，固定費(fèi)用為di元/天(i=1,2,…,m)，已知i城市至j城市運(yùn)輸成本為cij元/人。如何選擇機(jī)場(chǎng)的位置，能使總的運(yùn)輸成本最低？4.1

整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn)解：設(shè)y

1，若在i城市修建機(jī)場(chǎng)i

0，否則xij表示從城市i到城市j的運(yùn)量（人次/天），m nz表示預(yù)計(jì)總費(fèi)用（元/天）mini

1 j

1m

di

yii

1z

cijxijnijmijx

b

j，

j

1，2，

，

ni

0為整數(shù)，

y

0或1

j

1

s.t.

i

1

x

ij

x

ai

y

i，

i

1，2，

，

m

根據(jù)題意，該問題的數(shù)學(xué)模型為4.1

整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn)4.1.2

整數(shù)規(guī)化的例子及模型建立：解的特點(diǎn)：松馳問題的可行解是凸集，兩個(gè)可行解的線性組合還是可行解；整數(shù)規(guī)劃問題的可行解是松馳問題可行解的一個(gè)子集，兩個(gè)線性組合不一定是可行解。整數(shù)規(guī)劃的最優(yōu)解≤其松弛問題的最優(yōu)解整數(shù)規(guī)劃的解是可數(shù)個(gè)的，最優(yōu)解不一定發(fā)生在極點(diǎn)4.1

整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn)松馳問題最優(yōu)解：

x1*=24/5，x2*=0，z*=96整數(shù)問題最優(yōu)解：

x1*=4，x2*=1，z*=904.1

整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn)4.1.3

解的特點(diǎn)：整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn)

4.1.4整數(shù)規(guī)化的解題方法：

割平面法分枝定界法隱枚舉法用割平面法(cutting

plane

approach)解整數(shù)規(guī)劃時(shí)，若其松弛問題的最優(yōu)解x*不滿足整數(shù)規(guī)劃條件，則從x*的非整分量中選取一個(gè)，用以構(gòu)造一個(gè)線性約束條件，將其加入原松弛問題中，形成一個(gè)新的線性規(guī)劃、然后求解之。若新的最優(yōu)解滿足整數(shù)要求，則它就是整數(shù)規(guī)劃的最優(yōu)解；否則，重復(fù)上述步驟，直到獲得整數(shù)最優(yōu)解為止。每次增加的線性約束條件應(yīng)當(dāng)具備兩個(gè)基本性質(zhì)：其一是己獲得的不符合整數(shù)要求的線性規(guī)劃最優(yōu)解不滿足該線性約束條件，從而不可能在以后的解中再出現(xiàn)；其二是凡整數(shù)可行解均滿足該線性約束條件，因而整數(shù)最優(yōu)解始終被保留在每次形成的線性規(guī)劃可行域中。4.2整數(shù)規(guī)化的割平面法4.2.1

整數(shù)規(guī)化的割平面法：

a x

a xm1 1 m

2 2s.t.

a x

a x21 1 22 2

考慮純整數(shù)規(guī)劃問題：maxz

c1x1

c2x2

cnxna11x1

a12x2

a1nxn

b1

a2

n

xn

b2

amnxn

bmx1

,

x2

,

,

xn

0且為整數(shù)

設(shè)aij和bi均為整數(shù)純整數(shù)規(guī)劃的松弛問題是一個(gè)線性規(guī)劃問題記Q為m個(gè)基變量的下標(biāo)集合，K為n-m個(gè)非基變量的下標(biāo)集合，則m個(gè)約束方程可表示為:對(duì)應(yīng)的最優(yōu)解為:

X*

[x

*

,

x

*

,...,

x

*

]T1 2 ni

Q,

j

Kj

Kxi

aij

x

j

bij

0j

Qj

K

其中:x

*

b

j若各b

皆j 為整數(shù)．是純整數(shù)規(guī)劃的最優(yōu)解；?若各 b

j

(

j

Q

)

不全為整數(shù)，不是純整數(shù)規(guī)劃的可行解，自然也不是原整數(shù)規(guī)劃的最優(yōu)解。4.2.1

整數(shù)規(guī)化的割平面法：000i0j 0ai,j

x若bi (i

Q)不是整數(shù),

其約束方程為:x

bi i

Q (1)

00i0

,

j i0

,

j i0,

ji0,

j00i0 i0 i0 i0ai,

j

=N

f,

N

ai

,

j且為整數(shù),0

f

1

(2)(3)bi

=N

f ,

N

bi

且為整數(shù),0

f

14.2.1

整數(shù)規(guī)化的割平面法：0j

K其中:xi

為整數(shù),

bi0

不是整數(shù),

ai0

,

j不一定是整數(shù)分解bi0

和ai0

,

j為兩部分,一部分為最大的整數(shù),一部分為余下的小數(shù).xi0xi0

Ni

fi0 0(4)

1j

K

j

Kj

K

j

K

j

Kj

KNi

fi0 0

Ni0

,

j

xj

fi0

,

j

xjj

K

Ni0

,

j

xj

fi0

,

j

xjxj

0

fi0

,

j

xj

0

fi0

,

j

x

j

0

fi0

fi0

,

j

xj

fi04.2.1

整數(shù)規(guī)化的割平面法：（5）式為整數(shù)規(guī)化的割平面法所要增加的約束

(

fi0

,

j

)xj

fi0j

K0

i0

,

j j而(4)式左邊是整數(shù),右邊<1,所以有fi

f x

0,即j

K(5)4.2.1

整數(shù)規(guī)化的割平面法：a) 將現(xiàn)有的有非整解的X*代入，有,和（3）式矛盾，則X*不滿足（5）式b) 整數(shù)規(guī)劃模型的整數(shù)解一定滿足（500

fi

（5）式的實(shí)際意義：記R為原松弛問題可行域，R’為新約線性規(guī)劃可行域。從幾何意義上看，(5．10)實(shí)際上對(duì)R做了一次“切割”，在留下的R’中，保留了整數(shù)規(guī)劃的所有整數(shù)可行解，但不符合整數(shù)要求的X*被“切割’掉了。隨著”切割”過程的不斷繼續(xù)，整數(shù)規(guī)劃最優(yōu)解最終有機(jī)會(huì)成為某個(gè)線性規(guī)劃可行域的頂點(diǎn)，作為該線性規(guī)劃的最優(yōu)解而被解得。0）式（前提 i

是整數(shù)）x00i0 i0 i0 i0bi =N

f ,

N

bi

且為整數(shù),

0

f

1 (3)j

K

(

fi0

,

j

)xj

fi0（5）式的性質(zhì)：4.2.2

割平面法舉例：例：用割平面法求解純整數(shù)規(guī)劃：maxz

3x1

x21 25x1

4x2

102x1

x2

5

3x

2x

3

s.t.

x1,x2

0 且為整數(shù)maxz

3x1

x21 2412

3x1

2x2

x3

3

5x

4x

x

10s.t.

2x

x

x

5

5

x1,x2

0 且為整數(shù)解：加入松馳變量化為標(biāo)準(zhǔn)形并用單純形法解得松馳最優(yōu)解：Cj3-1000CBXBbx1x2x3x4x53-1x1x213/79/710011/7-2/7002/73/70x431/700-3/7122/7σ00-5/70-3/7由約束的第一行產(chǎn)生割平面約束：3 5 63 5 67 7 71

x

2

x

6

,引入松馳變量x

得:7 7 71

x

2

x

x

6

,

代入單純形表,用對(duì)偶單純形法解得:Cj3-10000CBXBbx1x2x3x4x5x63x113/7101/702/70-1x29/701-2/703/700x531/700-3/7122/700x6-6/700-1/70-2/71σ00-5/70-3/704.2.2

割平面法舉例：Cj3-10000CBXBbx1x2x3x4x5x63-1x1x213/79/710011/7-2/7002/73/7000x431/700-3/7122/700x6-6/700-1/70-2/71σ00-5/70-3/70Cj3-10000CBXBbx1x2x3x4x5x63-1x1x215/41001000-1/4001-5/40x35/2001-1/20-11/20x57/40001/41-3/4σ000-1/40-17/44 6 74 6 74 4 4第四行割平面約束:

1

x

1

x

3

,引入松馳變量x

得:4 4 41

x

1

x

x

3

,

代入單純形表,用對(duì)偶單純形法解得:Cj3-10000CBXBbx1x2x3x4x5x6x73-1x1x21210010000001-10-10x3400100-5-20x5100001-110x43000101-4σ00000-4-14.2.2

割平面法舉例：4.2.3切割平面的幾何意義：由原約束：maxz

3x1

x21 2412

3x1

2x2

x3

3

5x

4x

x

10s.t.

2x

x

x

5

5

x1,x2

0 且為整數(shù)得：3 1 2

x

3

3x

2x

x5

5

2x1

x2357代入：

1

x7 7

2x

61得： x

1

x4

5x1

4x2

106 31 27 7

x

1

x

12x

x

3 5 67 7 7

1

x

2

x

x

6而：46141434x

x

代入：

得：x1

x2

34.3

整數(shù)規(guī)劃的分枝定界法4.3.1

思路與解題步驟只解松弛問題1、在全部可行域上解松弛問題若松弛問題最優(yōu)解為整數(shù)解，則其也是整數(shù)規(guī)劃的最優(yōu)解2、分枝過程若松弛問題最優(yōu)解中某個(gè)

xk=bk

不是整數(shù)，令

bk

為

bk

的整數(shù)部分構(gòu)造兩個(gè)新的約束條件

xk

bk

和

xk

bk

+1，分別加于原松弛問題，形成兩個(gè)新的整數(shù)規(guī)劃3、求解分枝的松弛問題—

定界過程設(shè)兩個(gè)分枝的松弛問題分別為問題

1

和問題

2

，它們的最優(yōu)解有如下情況序號(hào)問題

1問題

2說 明1無可行解無可行解整數(shù)規(guī)劃無可行解2無可行解整數(shù)解此整數(shù)解即最優(yōu)解3無可行解非整數(shù)解對(duì)問題

2

繼續(xù)分枝4整數(shù)解整數(shù)解較優(yōu)的一個(gè)為最優(yōu)解5整數(shù)解，

目標(biāo)函數(shù)優(yōu)于問題

2非整數(shù)解問題

1

的解即最優(yōu)解6整數(shù)解非整數(shù)解，目標(biāo)函數(shù)優(yōu)于問題

1問題 1 停止分枝(

剪枝)，

其整數(shù)解為界，對(duì)問題

2

繼續(xù)分枝表4.3.1

分枝問題解可能出現(xiàn)的情況情況

2,4,5

找到最優(yōu)解情況

3在縮減的域上繼續(xù)分枝定界法情況

6

問題

1

的整數(shù)解作為界被保留，用于以后與問題

2的后續(xù)分枝所得到的解進(jìn)行比較，結(jié)論如情況

4或5

1 2x

,

x

0

且為整數(shù)2x1

x2

74.3.2 分枝定界法舉例例4.2.1 max

f

(

x)

6x1

4

x2解：松弛問題的最優(yōu)解為

x1=2.5,

x2=2,

OBJ=23由

x1=2.5得到兩個(gè)分枝如下：

問題I1

x1,x2

0 且為整數(shù)x

22x1

4x2

132x1

x2

7

問題II1

x1,x2

0 且為整數(shù)x

32x1

4x2

132x1

x2

7maxf(x)

6x1

4x2 maxf(x)

6x1

4x2

1 2 3 4 5 6 7x1A(2.5,

2)OBJ:

23C(3,

1)OBJ:

22x2 B(2,

9/4)7 OBJ:

216542x1

4x2

13 321

表4.3.3

分枝問題的松弛解 問題

I問題

IIx123x29/41f(x)2122問題II的解即原整數(shù)問題的最優(yōu)解可能存在兩個(gè)分枝都是非整數(shù)解的情況，則需要兩邊同時(shí)繼續(xù)分枝，直到有整數(shù)解出現(xiàn)，就可以進(jìn)行定界過程當(dāng)有很多變量有整數(shù)約束時(shí)，分枝即廣又深，在最壞情況下相當(dāng)于組合所有可能的整數(shù)解一般整數(shù)規(guī)劃問題屬于一類未解決的難題，NP-complete，只有少數(shù)特殊問題有好的算法，如任務(wù)分配問題、匹配問題4.3.2 分枝定界法舉例例：maxZ=40X1+

90X29X1+7X2

567X1+20X2

70X1,X2

0X1

,

X2為整數(shù)解：先解(1)的松弛問題X*

=4.8091.817Z*

=355.890，

上界Z*選X1分枝問題(2)(1)X1

4問題(3)(1)X1

5問題(4)(2)X2

2問題(5)(2)X2

3解為X2

=2.1先選(2)繼續(xù)分枝X1

=4Z=349.0解為X1

=5X2

=1.571Z=341.39(1)S0

=04.8091.817355.890(2)S0

=042.1349.0(3)S0

=051.571341.39(4)S0

=042340(5)3401.4283327.12(6)3405.4441307.76(7)無解X1

4X1

5X2

2X2

1X2

2X2

3分枝定界法一般步驟：、(A),

先解(A)的松弛問題(B)、① (B)無可行解→(A)無可行解。②

(B)最優(yōu)解符合(A)要求，停。③

(B)最優(yōu)解不符合(A)要求，轉(zhuǎn)(3)。(3)、估整數(shù)解S0

，作下界(4)、選(B)解中不符合整數(shù)條件的分量Xj

(Xj=

bj

)分枝，作(B)的后續(xù)問題(C)、(D)。(C)：

(B）加約束Xj

[bj](D)：(B)加約束Xj

[bj

]+1(5)、解(C)、(D)剪枝條件：① (C)，[(D)]無可行解② (C)，[(D)]對(duì)應(yīng)的目標(biāo)值S

S0③

(C)，[(D)]對(duì)應(yīng)的目標(biāo)值Sc>S0且解為整數(shù)解，令Sc

S0且解為非整數(shù)解，令(C)，[(D)]取代(B)

返回(4)(6)、全部枝剪完，停優(yōu)點(diǎn)：(1)、任何模型均可用；(2)、思路簡(jiǎn)單、靈活；(3)、速度快；(4)、適合上機(jī)。4.3.3分枝定界法注意事項(xiàng)：(1)、分枝變量選擇原則：① 按目標(biāo)函數(shù)系數(shù)：選系數(shù)絕對(duì)值最大者變量先分。對(duì)目標(biāo)值升降影響最大。② 選與整數(shù)值相差最大的非整數(shù)變量先分枝。③ 按使用者經(jīng)驗(yàn)，對(duì)各整數(shù)變量排定重要性的優(yōu)先順序。(2)、分枝節(jié)點(diǎn)選擇：① 深探法(后進(jìn)先出法)：最后打開的節(jié)點(diǎn)最先選，盡快找到整數(shù)解。整數(shù)解質(zhì)量可能不高。② 廣探法：選目標(biāo)函數(shù)當(dāng)前最大值節(jié)點(diǎn)，找到的整數(shù)解質(zhì)量高。慢。4.4 0-1規(guī)劃4.4.1 0-1規(guī)劃舉例0-1型整數(shù)規(guī)劃是整數(shù)規(guī)劃中的特殊情形，它的變量xi僅取值0或1，這時(shí)xi稱為0-1變量，或稱二進(jìn)制變量?？梢砸?-1變量的實(shí)際問題很多，如相互排斥的計(jì)劃，相互排斥的約束條件等等?！纠?.4.1】(廠址的選定)某公司擬在市東、西、南三區(qū)建立門市部，擬議中有7個(gè)位置（點(diǎn)），Ai（i=1，2，…，7）可供選擇。規(guī)定：在東區(qū)，由A1，A2，A3三個(gè)點(diǎn)中至多選兩個(gè)；在西區(qū)，由A4，A5兩個(gè)點(diǎn)中至少選一個(gè)；在南區(qū)，由A6，A7兩個(gè)點(diǎn)中至少選一個(gè)；如選用Ai點(diǎn)，設(shè)備投資估計(jì)為bi元，每年可獲利潤(rùn)估計(jì)為Ci元，但投資總額不能超過B元。問應(yīng)選擇哪幾個(gè)點(diǎn)可使年利潤(rùn)為最大？

當(dāng)A點(diǎn)被選用時(shí)

0, 當(dāng)A點(diǎn)未被選用時(shí)x

1,i解：引入0-1變量xi,

(i=1,2,

…

,7)則該問題的數(shù)學(xué)模型可寫成：4.4.1 0-1規(guī)劃舉例

i

x

0或1

B

2

1

1(i

1,2,...,7)x4

x5x6

x71

x2

x3

x7max

z

ci

xii

1b

xs.t.

i

17

i i【例4.3.2】(

可用于相互排斥計(jì)劃中)兩種運(yùn)貨方式：火車、船?；疖嚕簃axZ=20X1+

10X22X1+5X2

135X1+4X2

24+My7X1+3X2

45+M(1-y

)X1,

X2

0 整數(shù)y為0或1 M>04.4.1 0-1規(guī)劃舉例5X

+4X

24

(體積)1 2船：7X

+3X1 2

45

(體積)貨物體積(米3)（船）體積(米3)（火車）重量(百斤)利潤(rùn)(百元)甲75220乙34510托運(yùn)限制452413引入0-1變量y，令當(dāng)y=0

時(shí)采用火車運(yùn)輸y =1

時(shí)采用船運(yùn)輸

0-1變量作為邏輯變量(logical

variable)，常被用來表示系統(tǒng)是否處于某個(gè)特定狀態(tài)，或者決策時(shí)是否取某個(gè)特定方案。4.4.2 0-1變量及其應(yīng)用x

1,

當(dāng)決策方案取P時(shí)

0, 當(dāng)決策不取P時(shí)

當(dāng)問題含有多項(xiàng)要素，而每項(xiàng)要素皆有兩種選擇時(shí)，可用一組0-1變量來描述。1x

1, 當(dāng)Ej選擇Aj時(shí)(

j

1,

2,

,

n)jT1 n向量(x

,

,

x

) 就描述了問題的特定狀態(tài)或方案T1 n如(1,1,

,1) 表示(A

,

,

A

)Tn(0,1,

,1) 表示(

A

,

,

A

)

j j

0, 當(dāng)E

不選擇A

時(shí)例：

maxZ=12X1

+

12X2

+

9X3

+

15X4

+

90X5+26X6+

112X7(A)3X1

+

4X2

+

3X3

+

3X4

+

15X5

+

13X6+

16X7

35Xj為0或1，(j=1…7)松弛問題(B)為同于(A)約束，目標(biāo)0

Xj

1(j=1…7)4.4.2

0－1問題的分枝定界法（背包問題)重量?jī)r(jià)值價(jià)/重13124④24123339343155③515906②6132627161127①解:“單位重量?jī)r(jià)值大的先放”(0)Z=221X7=X5=X4=1(1)219X1=X7=X5=1X1=1 X1=1/3(2)220X7=X5=X4=1X1=0(3)214X2=X7=X5=1X2=1 X2=1/4(4)220X7=X5=X4=1X2=0(5)216X3=X7=X5=1X4=1/3X3=1 X3=1/3(6)219X7=X5=X4=1X6=1/13X3=0(9)217X1=X4=X7=1X5=13/5X4=1(10)217X1=X7=X5=1X2=1/44X4=1/3X

=0(7)174X6=X7=1X5=6/15X6=1(8)217X7=X5=X4=1X6=0(一)、基本思想：maxZ=CX對(duì)AX=bX為0或1的2n個(gè)可能解，只檢查其中一部分例：maxZ=2x1+4x2

+x33x1-8x2+5x3

-1x1,x2,x3為0

,14.4.3

0－1問題的隱枚舉法(二)、簡(jiǎn)單隱枚舉法(max)原則：、用試探法，求出一個(gè)可行解，以它的目標(biāo)值作為當(dāng)前最好值Z0、增加過濾條件Z

Z0(3)、將xi

按ci由小

大排列例：maxZ

=

3x1

-2x2+5x3x1+2x2-x3

2x1+4x2+x3

4①②③④x1

+ x2

34x2+x3

6x1

,

x2

,

x3為0或1解：觀察得解(x1

,

x2

,

x3

)=(1

,0

,0)過濾條件：3x1

-

2x2+5x3

3將(x1x2x3)

(x2x1x3

)Z0

=3解(x2

x1

x3

)目標(biāo)值Z0① ② ③ ④當(dāng)前最好值(0,0

,0)0<3(0,0

,1)5>5(0,1

,0)3<(0,1

,1)8>8(1,0

,0)-2<(1,0

,1)3<(1,1

,0)1<(1,1

,1)6<最優(yōu)解

x

=

(1

,0

,1

)T Z=84.5

任務(wù)分配問題例4.5.1

有四個(gè)熟練工人，他們都是多面手，有四項(xiàng)任務(wù)要他們完成。若規(guī)定每人必須完成且只完成一項(xiàng)任務(wù)，而每人完成每項(xiàng)任務(wù)的工時(shí)耗費(fèi)如表4.6.1，問如何分配任務(wù)使完成四項(xiàng)任務(wù)的總工時(shí)耗費(fèi)最少？

i

1

j

1ijx

0,1ijijm mij ij

m

xi

1

j

1

m

xa xminf(x)

1 i

1,2,

,

m

1 j

1,2,

,

m任務(wù)工時(shí)人員ABCD人員甲乙丙丁105529843776487551111任務(wù)1111任務(wù)分配問題的數(shù)學(xué)模型模型中：xij

為第

i

個(gè)工人分配去做第

j

項(xiàng)任務(wù)；aij

為第i

個(gè)工人為完成第

j

項(xiàng)任務(wù)時(shí)的工時(shí)消耗；

i,j

1,2,

,

m

0 當(dāng)?shù)趇個(gè)工人未分配去做第 j項(xiàng)任務(wù){(diào)aij}m

m

稱為效率矩陣

1 當(dāng)?shù)趇個(gè)工人分配去做第 j項(xiàng)任務(wù)xij

i

1

j

1ijx

0,1ijijm mij ij

m

xi

1j

1

m

xa

xminf(x)

1 i

1,2,

,

m

1 j

1,2,

,

m任務(wù)工時(shí)人員ABCD人員甲109781乙58771丙54651丁23451任務(wù)1111任務(wù)分配問題的數(shù)學(xué)模型

運(yùn)輸問題是任務(wù)分配問題的松弛問題任務(wù)分配問題不但是整數(shù)規(guī)劃，而且是0

1規(guī)劃任務(wù)分配問題有2m個(gè)約束條件，但有且只有m個(gè)非零解，自然是高度退化的任務(wù)分配是兩部圖的匹配問題，有著名的匈牙利算法

i

1

j

1ijx

0,1ijijm mij ij

m

xi

1j

1

m

xa

xminf(x)

1 i

1,2,

,

m

1 j

1,2,

,

m任務(wù)工時(shí)人員ABCD人員甲109781乙58771丙54651丁23451任務(wù)1111

4.4.1匈牙利算法 定理

1 如果從效率矩陣{aij}m

m中每行元素分別減去（或加上）一個(gè)常數(shù)

ui，從每列元素分別減去（或加上）一個(gè)常數(shù)

vj

，所得新的效率矩陣{bij}m

m的任務(wù)分配問題的最優(yōu)解等價(jià)于原問題的最優(yōu)解。定理

2 若方陣{aij}m

m中一部分元素為零，一部分元素非零，則覆蓋方陣內(nèi)所有零元素的最少直線數(shù)等于位于不同行、不同列的零元素的最多個(gè)數(shù)。4.5.1匈牙利算法匈牙利算法的基本思路：第一步：根據(jù)定理

1變換效率矩陣。先對(duì)各行元素分別減去本行中的最小元，再對(duì)各列元素減去本列最小數(shù)點(diǎn)元，使每項(xiàng)行每列中至少有一個(gè)零元素，同時(shí)不出現(xiàn)負(fù)元素。轉(zhuǎn)第二步。第二步：在覆蓋變換后的效率矩陣中確定獨(dú)立零元素。若獨(dú)立零元素有m個(gè)，則已得出最優(yōu)解；若獨(dú)立零元數(shù)少于m個(gè)，則作能覆蓋所有零元素的最少直線數(shù)目的直線集合，然后轉(zhuǎn)第三步。第三步：繼續(xù)變換系數(shù)矩陣。方法是在未被直線覆蓋的元素中找出一個(gè)最小元素，對(duì)這一最小元素所在行中各元素減去這一值，同時(shí)這一行會(huì)出現(xiàn)負(fù)元素，因此在負(fù)元素的列中加上最小元素值。返回第二步。匈牙利算法的舉例：例4.5.1第一步：變換效率矩陣，使每行每列至少有一個(gè)零行變換：找出每行最小元素，從該行各元素中減去之列變換：找出每列最小元素，從該列各元素中減去之7

10 9 78 74 63 4

5

5

25

5

8

行變換第二步：確定獨(dú)立零元素的個(gè)數(shù)。若獨(dú)立零元素有m個(gè)，則已得出最優(yōu)解；若獨(dú)立零元素少于m個(gè)，則作能覆蓋所有零元素的最少直線數(shù)目的直線集合，然后轉(zhuǎn)步驟3。

2 0 0

3 2 1

1 0 2 01 2

02

列

3變

換

0

3 1

02 0

0 3 2 2

1 0 2 1

1 2

3

匈牙利算法的舉例：例4.5.1為了確定獨(dú)立零元素,

可以在只有一個(gè)零元素的行或列中加O,每圈一個(gè)0時(shí)，把位于同行或同列的元素劃去（打上/標(biāo)記）。1、逐行檢查，若該行只有一個(gè)未標(biāo)記的零，對(duì)其加O標(biāo)記，將O標(biāo)記元素同行同列上其它的零打上/標(biāo)記。若該行有二個(gè)以上未標(biāo)記的零，暫不標(biāo)記，轉(zhuǎn)下一行檢查，直到所有行檢查完；2、逐列檢查，若該列只有一個(gè)未標(biāo)記的零，對(duì)其加O標(biāo)記，將O

標(biāo)記元素同行同列上其它的零打上/

標(biāo)記。若該列有二個(gè)以上未標(biāo)記的零，暫不標(biāo)記，轉(zhuǎn)下一列檢查，直到所有列檢查完；

13 2 0 0

3 2 1

0 2 0

1 2

02

逐行檢

查

0

1

03 2 0 03 2 1

0 2 0

1 2 2

逐列檢

查

0匈牙利算法的舉例：例4.5.13、重復(fù)1、2后，直至所有的零被打上O標(biāo)記或/標(biāo)記。若O標(biāo)記的個(gè)數(shù)為4個(gè)，則已找到最優(yōu)解，否則需確定能覆蓋所有零元的最少直線數(shù)。4、打破僵局。當(dāng)某些行（或列）剩下未標(biāo)記的零元的數(shù)量都大于1時(shí)，選未標(biāo)記零元對(duì)應(yīng)個(gè)數(shù)最少的行（或列）先標(biāo)記O

。2 0 0

3 20 21 21

1逐行

3逐列

0

0

02

檢查

3 20 21 2

3 2 0 0

01

1

0

02

匈牙利算法的舉例：例4.5.1劃線過程：對(duì)沒有標(biāo)記O

的行打

對(duì)打

行上所有帶/零元素對(duì)應(yīng)的列打

再對(duì)打

列上有O標(biāo)記的零元素對(duì)應(yīng)的行打

重復(fù)b

和c

，直至無法繼續(xù)對(duì)沒有打

的行劃?rùn)M線，對(duì)所有打

的列劃垂線

3

023020

1

1

001220

2

然后轉(zhuǎn)到第三步；

匈牙利算法的舉例：例4.5.1第三步：進(jìn)一步變換；在未劃線的元素中找最小者，設(shè)為

對(duì)未被直線覆蓋的行（或列）各元素減去

對(duì)出現(xiàn)負(fù)元素的行（或列）加上

4 2 0 0

2 1 0

0 2 0

0 1

01

第一列+1

0d.

回到第二步；重新標(biāo)記；

1

3 2 0 0

2 1 0

0 2 0

2

1 0 1 1

1

1以上步驟實(shí)際上仍是利用定理

11 2

3 2 0 0

0 3 2 1

1 0 2 0

02

匈牙利算法的舉例：例4.5.1回到第二步；重新標(biāo)記；逐行檢列

1

查

2

查

檢

1

0

00

20 2 1 0 0 2 1 00 2 0

2 0 2 0

0 1 0 1

4 2 0 0

4 2 0 0

逐

10

2

4 2 0 0

0 2 1 0

0 2

0 0 1 1

4 2 0 0

0 2 1 0

0 20 0 1

打破僵局

答：最優(yōu)分配方案為x =x =x =

x13 21 34 42=1，其余為0，即甲

C，乙

A，丙

D，丁

B，OBJ=204.4

.2 一般的指派問題

9

2 15 13 4

10 4 14 15

9 14 16 13

7 8 11最大化指派問題: C

最大化指派問題—用矩陣中最大元素的值減去所有元素的值，對(duì)新的矩陣求最小化指派問題的解，其解等于原矩陣最大化指派問題的解。

7

916

9

16

13

7 2 0 3

8 516

1616

1116

1416

8

16

9

16

7

16

216

1516

1316

4

1413

16

1016

416

1416

15

6122B

化為最小化指派問題，其解與最大化指派問題的解相等：12

1

一般的指派問題人數(shù)和事數(shù)不等的指派問題若人少事多，則增加虛擬的人，做各事費(fèi)用系數(shù)可取為0，理解為這些費(fèi)用不會(huì)發(fā)生。若事少人多，則增加虛擬的事，每人做此事費(fèi)用系數(shù)也取為0，理解為這些費(fèi)用不會(huì)發(fā)生。一個(gè)人可做幾件事–將該人化做相同的幾個(gè)人來接受指派，這幾個(gè)人做相同的事費(fèi)用是一樣的。當(dāng)某事一定不能由某人做–將此人做此事的費(fèi)用取為足夠大的正數(shù)M。4.5 樞紐機(jī)場(chǎng)的確定問題中樞輻射航線網(wǎng)絡(luò)的特點(diǎn):非樞紐機(jī)場(chǎng)之間的客源通過樞紐機(jī)場(chǎng)中轉(zhuǎn)來體現(xiàn)規(guī)模經(jīng)濟(jì)效應(yīng)。機(jī)場(chǎng)的選擇是航空公司長(zhǎng)期的戰(zhàn)略決策。取消已有的樞紐機(jī)場(chǎng)或者增加新的樞紐機(jī)場(chǎng)都要消耗航空公司大量的時(shí)間和費(fèi)用,而對(duì)非樞紐機(jī)場(chǎng)與樞紐機(jī)場(chǎng)連接的改變,航空公司的花費(fèi)相對(duì)較少,更具有可行性。航空公司籌建中樞輻射航線網(wǎng)絡(luò),在一些備選機(jī)場(chǎng)中選擇幾個(gè)機(jī)場(chǎng)作為自己中樞輻射航線網(wǎng)絡(luò)的樞紐。樞紐機(jī)場(chǎng)選擇的問題描述如下所述：從n個(gè)備選機(jī)場(chǎng)中選擇p個(gè)機(jī)場(chǎng)(p一般不會(huì)很大)作為樞紐,對(duì)于每個(gè)機(jī)場(chǎng),航空公司的收益部門通過一系列的指標(biāo)如市場(chǎng)預(yù)測(cè)、自身所占的份額以及建設(shè)樞紐機(jī)場(chǎng)所需的前期投入等,得到該機(jī)場(chǎng)作為樞紐能給航空公司帶來的效益值,然后選擇p個(gè)使總效益最大的機(jī)場(chǎng)作為自己的樞紐。4.5 樞紐機(jī)場(chǎng)的確定問題樞紐機(jī)場(chǎng)的確定問題可以用0-1整數(shù)規(guī)劃問題來加以分析解決。樞紐機(jī)場(chǎng)的確定相當(dāng)于集覆蓋問題，主要是將一個(gè)集合的每一個(gè)元素指派給另一個(gè)集合的某個(gè)元素或與另一個(gè)集合的某個(gè)元素配對(duì)，比如機(jī)組與航班配對(duì)、飛機(jī)分配到航線上。集覆蓋問題的目標(biāo)就是尋求配對(duì)成本的最小化。4.5.1

樞紐機(jī)場(chǎng)確定案例分析

例如某航空公司要建立一個(gè)“樞紐”式航線網(wǎng)絡(luò)的機(jī)場(chǎng)，該機(jī)場(chǎng)要把其方圓1000英里以內(nèi)的城市銜接起來，這個(gè)航空公司要開辟到下列城市的航班：亞特蘭大、波士頓、芝加哥、丹麥、休斯頓、洛杉磯、新奧爾良、紐約、匹茲堡、鹽湖城、舊金山和西雅圖。該航空公司想要知道覆蓋所有這些城市最少需要建立幾個(gè)航空樞紐，條件是每個(gè)城市到最近一個(gè)航空樞紐的距離不能超過1000英里。表4-5列出了這些城市間的距離。亞特蘭大、波士頓、芝加哥、丹佛、休斯頓、洛杉磯、新奧爾良、紐約、匹茲堡、鹽湖城、舊金山和西雅圖ATBOCHDEHOLANONYPISLSFSEAT0103767413987892182479841687187824962618BO1037010051949180429791507222574234330952976CH67410050100810672054912802452139021422013DE13981949100801019105912731771141150412351307HO7891804106710190153835616081313143819122274LA2182297920541059153801883278624267153791131NO479150791212733561883013111070173822492574NY8412228021771160827861311036821822934