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

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

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

整數(shù)規(guī)劃的數(shù)學模型及解的特點純整數(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ī)劃為對應該整數(shù)問題的松弛問題，解為整數(shù)問題解的松馳解4.1.1

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

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

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

20x1

10x2

1 2

x

,

x

0 且為整數(shù)

s.t.

2x1

5x2

135x1

4x2

244.1

整數(shù)規(guī)劃的數(shù)學模型及解的特點4.1

整數(shù)規(guī)劃的數(shù)學模型及解的特點產品A產品B資源限量勞動力84360設

備35200原材料210300利潤元/臺60804.1.2

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

整數(shù)規(guī)劃的數(shù)學模型及解的特點x1

臺，B產品x2臺maxz

60x1

80x28x1

4x2

3603x1

5x2

2002x1

10x2

300x1

0,x2

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

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

整數(shù)規(guī)劃的數(shù)學模型及解的特點4.1.2

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

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

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

整數(shù)規(guī)化的例子及模型建立：解：設星期一到星期日開始輪班的人數(shù)分別為x1、x2、x3、x4、x5、x6、x7，根據分析計算，對應每人每周的工資分別為：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)為非負整數(shù)4.1.2

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

A2,

......,

An，其中設備Ai單價為Pi

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

B2,

......

,

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

整數(shù)規(guī)劃的數(shù)學模型及解的特點解：分別設yi為購買設備Ai的臺數(shù)，xij為將設備Ai裝置于Bj公司的臺數(shù)，z為預計總利潤（元）。根據題意得數(shù)學規(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ù)學模型及解的特點4.1.2

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

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

整數(shù)規(guī)劃的數(shù)學模型及解的特點解：設y

1，若在i城市修建機場i

0，否則xij表示從城市i到城市j的運量（人次/天），m nz表示預計總費用（元/天）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

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

整數(shù)規(guī)劃的數(shù)學模型及解的特點4.1.2

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

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

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

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

整數(shù)規(guī)劃的數(shù)學模型及解的特點4.1.3

解的特點：整數(shù)規(guī)劃的數(shù)學模型及解的特點

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

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

plane

approach)解整數(shù)規(guī)劃時，若其松弛問題的最優(yōu)解x*不滿足整數(shù)規(guī)劃條件，則從x*的非整分量中選取一個，用以構造一個線性約束條件，將其加入原松弛問題中，形成一個新的線性規(guī)劃、然后求解之。若新的最優(yōu)解滿足整數(shù)要求，則它就是整數(shù)規(guī)劃的最優(yōu)解；否則，重復上述步驟，直到獲得整數(shù)最優(yōu)解為止。每次增加的線性約束條件應當具備兩個基本性質：其一是己獲得的不符合整數(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ù)

設aij和bi均為整數(shù)純整數(shù)規(guī)劃的松弛問題是一個線性規(guī)劃問題記Q為m個基變量的下標集合，K為n-m個非基變量的下標集合，則m個約束方程可表示為:對應的最優(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）式的實際意義：記R為原松弛問題可行域，R’為新約線性規(guī)劃可行域。從幾何意義上看，(5．10)實際上對R做了一次“切割”，在留下的R’中，保留了整數(shù)規(guī)劃的所有整數(shù)可行解，但不符合整數(shù)要求的X*被“切割’掉了。隨著”切割”過程的不斷繼續(xù)，整數(shù)規(guī)劃最優(yōu)解最終有機會成為某個線性規(guī)劃可行域的頂點，作為該線性規(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）式的性質：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ù)解：加入松馳變量化為標準形并用單純形法解得松馳最優(yōu)解：Cj3-1000CBXBbx1x2x3x4x53-1x1x213/79/710011/7-2/7002/73/70x431/700-3/7122/7σ00-5/70-3/7由約束的第一行產生割平面約束：3 5 63 5 67 7 71

x

2

x

6

,引入松馳變量x

得:7 7 71

x

2

x

x

6

,

代入單純形表,用對偶單純形法解得: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

,

代入單純形表,用對偶單純形法解得: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)解中某個

xk=bk

不是整數(shù)，令

bk

為

bk

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

xk

bk

和

xk

bk

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

定界過程設兩個分枝的松弛問題分別為問題

1

和問題

2

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

1問題

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

2

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

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

2非整數(shù)解問題

1

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

1問題 1 停止分枝(

剪枝)，

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

2

繼續(xù)分枝表4.3.1

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

2,4,5

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

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

6

問題

1

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

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

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得到兩個分枝如下：

問題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)解可能存在兩個分枝都是非整數(shù)解的情況，則需要兩邊同時繼續(xù)分枝，直到有整數(shù)解出現(xiàn)，就可以進行定界過程當有很多變量有整數(shù)約束時，分枝即廣又深，在最壞情況下相當于組合所有可能的整數(shù)解一般整數(shù)規(guī)劃問題屬于一類未解決的難題，NP-complete，只有少數(shù)特殊問題有好的算法，如任務分配問題、匹配問題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)要求，轉(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)]對應的目標值S

S0③

(C)，[(D)]對應的目標值Sc>S0且解為整數(shù)解，令Sc

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

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

當A點被選用時

0, 當A點未被選用時x

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

(i=1,2,

…

,7)則該問題的數(shù)學模型可寫成：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】(

可用于相互排斥計劃中)兩種運貨方式：火車、船?；疖嚕簃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)（火車）重量(百斤)利潤(百元)甲75220乙34510托運限制452413引入0-1變量y，令當y=0

時采用火車運輸y =1

時采用船運輸

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

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

1,

當決策方案取P時

0, 當決策不取P時

當問題含有多項要素，而每項要素皆有兩種選擇時，可用一組0-1變量來描述。1x

1, 當Ej選擇Aj時(

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, 當E

不選擇A

時例：

maxZ=12X1

+

12X2

+

9X3

+

15X4

+

90X5+26X6+

112X7(A)3X1

+

4X2

+

3X3

+

3X4

+

15X5

+

13X6+

16X7

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

Xj

1(j=1…7)4.4.2

0－1問題的分枝定界法（背包問題)重量價值價/重13124④24123339343155③515906②6132627161127①解:“單位重量價值大的先放”(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對AX=bX為0或1的2n個可能解，只檢查其中一部分例：maxZ=2x1+4x2

+x33x1-8x2+5x3

-1x1,x2,x3為0

,14.4.3

0－1問題的隱枚舉法(二)、簡單隱枚舉法(max)原則：、用試探法，求出一個可行解，以它的目標值作為當前最好值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

)目標值Z0① ② ③ ④當前最好值(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

任務分配問題例4.5.1

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

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任務工時人員ABCD人員甲乙丙丁105529843776487551111任務1111任務分配問題的數(shù)學模型模型中：xij

為第

i

個工人分配去做第

j

項任務；aij

為第i

個工人為完成第

j

項任務時的工時消耗；

i,j

1,2,

,

m

0 當?shù)趇個工人未分配去做第 j項任務{aij}m

m

稱為效率矩陣

1 當?shù)趇個工人分配去做第 j項任務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任務工時人員ABCD人員甲109781乙58771丙54651丁23451任務1111任務分配問題的數(shù)學模型

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

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

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任務工時人員ABCD人員甲109781乙58771丙54651丁23451任務1111

4.4.1匈牙利算法 定理

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

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

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

vj

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

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

2 若方陣{aij}m

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

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

10 9 78 74 63 4

5

5

25

5

8

行變換第二步：確定獨立零元素的個數(shù)。若獨立零元素有m個，則已得出最優(yōu)解；若獨立零元素少于m個，則作能覆蓋所有零元素的最少直線數(shù)目的直線集合，然后轉步驟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為了確定獨立零元素,

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

標記元素同行同列上其它的零打上/

標記。若該列有二個以上未標記的零，暫不標記，轉下一列檢查，直到所有列檢查完；

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、重復1、2后，直至所有的零被打上O標記或/標記。若O標記的個數(shù)為4個，則已找到最優(yōu)解，否則需確定能覆蓋所有零元的最少直線數(shù)。4、打破僵局。當某些行（或列）剩下未標記的零元的數(shù)量都大于1時，選未標記零元對應個數(shù)最少的行（或列）先標記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劃線過程：對沒有標記O

的行打

對打

行上所有帶/零元素對應的列打

再對打

列上有O標記的零元素對應的行打

重復b

和c

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

的行劃橫線，對所有打

的列劃垂線

3

023020

1

1

001220

2

然后轉到第三步；

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

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

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

4 2 0 0

2 1 0

0 2 0

0 1

01

第一列+1

0d.

回到第二步；重新標記；

1

3 2 0 0

2 1 0

0 2 0

2

1 0 1 1

1

1以上步驟實際上仍是利用定理

11 2

3 2 0 0

0 3 2 1

1 0 2 0

02

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

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

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

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

樞紐機場確定案例分析

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