第八章標準服務系統(tǒng)

M/M/n系統(tǒng)魚與熊掌兼得？28.1M/M/n損失制

8.1.1M/M/n損失制，無限源

(M/M/n:/n/FIFO)令從顧客源來的顧客到達率為

，每臺的服務率為

則有

j=

,j=0,1,...,n–1;

n=0，

j=j,j=1,...,n將

j,

j

代入生滅方程，得式中

=

/

稱為業(yè)務量(traffic)，是無量綱量；表示單位時間內(nèi)要求系統(tǒng)提供的服務時間；

和

的單位必須一致；由于紀念Erlang，用愛爾蘭作單位(Erl)3

系統(tǒng)的服務質(zhì)量系統(tǒng)的質(zhì)量用顧客的損失率來度量，有兩種度量方法按時間計算的損失率pn，即單位時間內(nèi)服務臺全被占用的時間按顧客計算的損失率B，即單位時間內(nèi)損失的顧客數(shù)與到達顧客數(shù)之比在本系統(tǒng)中有B=pn=En(

)，稱為愛爾蘭損失公式不是所有系統(tǒng)都有B=pn

的性質(zhì)工程上經(jīng)常是已知

，給定B，求所需最少的服務臺n求n

一般有三種方法：迭代計算，查圖，查表4

求所需服務臺的方法1、查圖，如書上262頁2、迭代計算無法由En(

)給出n

的逆函數(shù)，因此采用逐次試算的方法注意，En(

)有較簡單的遞推公式3、工程上經(jīng)常采用查表的方法愛爾蘭表最左邊一列為服務臺數(shù)n，最上面一行為服務質(zhì)量的不同等級，即B愛爾蘭表中元素的值為

，表示服務臺數(shù)為n，服務質(zhì)量為B時，系統(tǒng)最大所能承擔的業(yè)務量；工程上經(jīng)常用A表示

，A

是加入話務量5愛爾蘭損失表n=3,B=0.01,查表得

=0.455已知n

和

如何求B，線性內(nèi)插法；例：n=3，

=2.5，由表可知B

落在0.2~0.3之間，若假設在這區(qū)間所承擔的業(yè)務量與B

成線性關系，則有線性內(nèi)插公式B2.5=0.2+(0.3-0.2)(2.5-1.930)/(2.633-1.930)=0.2816例1M/M/n損失制無限源系統(tǒng)，已知n=3，

=5人/小時，平均服務時長30分鐘/人，試求：(1)系統(tǒng)中沒有顧客的概率；(2)只有一個服務臺被占用的概率；(3)系統(tǒng)的損失率解：由題意可知

=60/30=2人/小時，所以

=

/

=2.5Erl(1)p0=(1+2.5+2.52/2+2.53/3!)1=0.108(2)p1=

p0=2.50.108=0.27(3)B=E3(2.5)=p0

3/3!=0.1082.604=0.28例2

兩市話局間的忙時平均呼叫次數(shù)為240，每次通話平均時長為5分鐘，規(guī)定兩局間中繼線的服務等級為B

0.01,問：(1)應配備多少條中繼線？(2)中繼線群的利用率為多少？解：中繼線群上的加入話務量為

=2405/60=20Erl，

(1)查262頁圖，n=30條；

(2)查愛爾蘭表可知：n=30，B=0.01時可承擔A=20.337，B=0.005時可承擔A=19.034，因此，E30(20)=0.005+0.005(2019.034)/(20.33719.034)=0.008707

中繼線群利用率

=

(1B)/n=20(1-0.008707)/30=0.6608627

服務臺利用率與服務臺數(shù)量的關系

n

圖當給定n

和B

后，系統(tǒng)所能承擔的業(yè)務量

可以通過愛爾蘭公式求出，從而可計算出服務臺利用率

；若保持B

不變，不斷增加服務臺數(shù)n，

也會發(fā)生變化，就可以得到

n

圖如下；通過觀察，有幾點結論：1、B不變時，

隨

n增加；說明大電路群效率高2、n不變時，

隨

B增加；說明效率與質(zhì)量是矛盾的；(高效路由)3、

具有邊際遞減規(guī)律4、

越大，系統(tǒng)抗過負荷能力越差8

系統(tǒng)過負荷特性

B

圖過負荷是指系統(tǒng)加入的業(yè)務量A,超過給定服務質(zhì)量所能承擔的業(yè)務量A過負荷用過載業(yè)務量與標準應承擔的業(yè)務量的比值來表示，即

=(A

A)/A=A/A

En(A)=B,En(A)=B

由圖可見，在同樣標準的服務質(zhì)量和同樣的過負荷率下，大系統(tǒng)的質(zhì)量劣化嚴重；說明效率與可靠性是矛盾的9例3

某服務部門把顧客分為兩組，分別組成兩個單獨的服務系統(tǒng)。各系統(tǒng)的到達率分別為

1=4人/小時，

2=8人/小時，每人的平均占用時長都為6分鐘；給定損失率為B

0.01，試求：(1)分組服務時每組應配備的服務臺數(shù)；(2)合并為一個服務系統(tǒng)時，各種條件不變，應配備的服務臺數(shù)；(3)比較兩種組織方式的服務臺利用率。解：(1)分組時：

1=40.1=0.4Erl,

2=80.1=0.8Erl

查愛爾蘭表，得n1=3臺，n2=4臺，共需7臺。

B1=0.005+0.005(0.40.349)/(0.4550.349)=0.0074

B2=0.005+0.005(0.80.701)/(0.8690.701)=0.00795

=[

1(1B1)+

2(1B2)]/(n1+n2)=0.17(2)合組時：

=120.1=1.2Erl,

查愛爾蘭表，得n

=5臺，節(jié)省了2臺。

B

=0.005+0.005(1.21.132)/(1.3611.132)=0.006485

=(1B)/n=0.238108.2.1M/M/n損失制，有限源

(M/M/n:N/n/FIFO)例交換機內(nèi)部有n

條繩路，N條入中繼線，N>n；每條入中繼線上的呼叫到達強度為

，且為波松分布，通話時長為負指數(shù)分布(參數(shù)為m)，問入中繼線上呼叫的損失率為多少？上述例子就是一個M/M/n損失制，有限源系統(tǒng)。當已經(jīng)接受繩路服務的中繼線在通話中，該中繼線上就不會有新的呼叫。因此，整個系統(tǒng)的呼叫到達率是與系統(tǒng)中被服務的中繼線數(shù)相關的。這就是有限源系統(tǒng)的特點顯然，系統(tǒng)在各狀態(tài)下的到達率和離去率分別為

j=(N–j)

,j=0,1,...,n–1,

n=0，

j=j,j=1,...,n將

j,

j

代入生滅方程，得11

當j=n

時，pn表示按時間計算的損失率下面分析按顧客計算的損失率BB=單位時間平均損失顧客數(shù)/單位時間平均到達顧客數(shù)在有限源系統(tǒng)中，顧客到達率隨系統(tǒng)狀態(tài)變化，因此有平均顧客到達率

，又稱為有效到達率

12可見，在有限源情況下，系統(tǒng)按時間計算的損失率pn

和按顧客計算的損失率B是不相等的；其原因就是輸入過程隨系統(tǒng)狀態(tài)而變從一個極端情況看，若N=n，則B=0，但pn

0雖然愛爾蘭損失公式和恩格謝特損失公式都是在負指數(shù)服務時長假設下推導出來的，但已證明服務時間是其它一般平穩(wěn)分布，結論仍是正確的服務臺利用率：13例4

有一電話查詢服務處集中答復三個查詢點的所有查詢事項。查詢服務處與查詢點之間用電話聯(lián)系。查詢服務處只有一名值班員答復所有的查詢。已知每個查詢點平均每小時有兩次查詢，每次平均通話12分鐘，問：(1)值班員空閑的概率；(2)值班員打電話的概率；(3)查詢時值班員忙的概率；(4)服務處查詢電話的平均到達率；(5)值班員的工時利用率。解：系統(tǒng)是有限源

M/M/1損失制。q=

/

=(2/60)12=0.4Erl (1)p0=1/(1+Nq)=0.4545148.2M/M/n等待制，無限源，無限容量

(M/M/n://FIFO)

8.2.1系統(tǒng)穩(wěn)態(tài)概率及等待概率令從顧客源來的顧客到達率為

，每臺的服務率為

則有

j=

,j0;

j=j,j<n；

j=n,j

n將

j,

j

代入生滅方程，得15當

n

時，則p0

中第二項不收斂，系統(tǒng)中隊長將趨于無窮當

<n

時，系統(tǒng)有穩(wěn)態(tài)，處于動態(tài)平衡；無限容量等待制，每個顧客早晚都會得到服務，因此系統(tǒng)完成的業(yè)務量也是

顧客進入系統(tǒng)必須排隊等待的概率為D

愛爾蘭等待公式排隊等待的概率是等待制系統(tǒng)的重要指標之一n=1時，D=

公式

D的記憶法168.2.2系統(tǒng)的各種指標等待制系統(tǒng)的指標有：平均逗留隊長；平均等待隊長；平均逗留時長；平均等待時長和服務臺利用率等n=1時，D=

，Ld=

/(1

)，Lq=

2/(1

)，Wq=

/(

)例5

書上273頁178.2.3等待時間的概率分布前面只推導了要等待的概率D=P{W>0}，但在很多情況下我們希望知道等待時長的分布，即P{W>t}系統(tǒng)中有j

個顧客，j

n

時，新來顧客要排隊等待，采用FIFO規(guī)則；令新顧客到達時為0時刻，顯然，只有服務臺上離去j

n個顧客時，新顧客才排到隊首當n

個服務臺連續(xù)服務時，顧客離去率為n，因此服務臺空出的過程是波松流，在(0,t)內(nèi)空出i

次的概率為18

等待時長分布的推導19例6

某儲蓄所內(nèi)，已知忙時顧客到達率

=40人/小時，窗口營業(yè)員服務率為

=16人/小時，要求：(1)工時利用率不低于60%；(2)顧客平均等待時間不超過5分鐘；問：設幾個窗口適當。解：系統(tǒng)是無限源

M/M/n

等待制。

=

/

=40/16=2.5Erl (1)

=

/n0.6，解出n4.17，故n

可取值3，4(2)n=3時，p0=(1++2/2!

+(

3/3!)(3/(3-2.5))1=0.04520例7

興建一座港口碼頭，只有一個裝卸泊位，要求設計泊位的生產(chǎn)能力，能力用日裝卸船只數(shù)表示。已知單位裝卸能力日平均生產(chǎn)費用為a=2000元；船只到港后若不能及時裝卸，逗留一日要損失運輸費b=1500元；預計船只的平均到達率為

=3只/日。設船只到達的間隔時間和裝卸時間都服從負指數(shù)分布，問港口生產(chǎn)能力設計為多大時，每天總費用最?。拷猓合到y(tǒng)是無限源

M/M/1等待制，生產(chǎn)能力用

(只/日)表示 目標函數(shù)：minC=a+bLd21例8M/M/1等待制系統(tǒng),無限隊長,顧客到達與隊長有關該系統(tǒng)仍為無限源，但考慮到顧客對排隊的心理，假設顧客到達率與隊長成反比關系即

j=

0

/(1+j)，

0為隊長為0時的顧客到達率從而系統(tǒng)的

j

和

j

為將

j

和

j

代入生滅方程，得第二章

線性規(guī)劃的對偶理論及其應用窗含西嶺千秋雪，門泊東吳萬里船對偶是一種普遍現(xiàn)象232.1線性規(guī)劃的對偶理論

2.1.1線性規(guī)劃原問題與對偶問題的表達形式任何線性規(guī)劃問題都有其對偶問題對偶問題有其明顯的經(jīng)濟含義

假設有商人要向廠方購買資源A和B，問他們談判原料價格的模型是怎樣的？24

例2.1.1設A、B資源的出售價格分別為y1

和

y2顯然商人希望總的收購價越小越好工廠希望出售資源后所得不應比生產(chǎn)產(chǎn)品所得少目標函數(shù)ming(y)=25y1+15y2252.1.1線性規(guī)劃原問題與對偶問題的表達形式262.1.1線性規(guī)劃原問題與對偶問題的表達形式272.1.2標準(max,)型的對偶變換目標函數(shù)由max型變?yōu)閙in型對應原問題每個約束行有一個對偶變量yi，i=1,2,…,m對偶問題約束為型，有n

行原問題的價值系數(shù)C變換為對偶問題的右端項原問題的右端項

b變換為對偶問題的價值系數(shù)原問題的技術系數(shù)矩陣A轉(zhuǎn)置后成為對偶問題的技術系數(shù)矩陣原問題與對偶問題互為對偶對偶問題可能比原問題容易求解對偶問題還有很多理論和實際應用的意義2.1.3非標準型的對偶變換29

表2.1.1對偶變換的規(guī)則約束條件的類型與非負條件對偶非標準的約束條件類型對應非正常的非負條件對偶變換是一一對應的302.2線性規(guī)劃的對偶定理

2.2.1弱對偶定理定理對偶問題(min)的任何可行解Y0，其目標函數(shù)值總是不小于原問題(max)任何可行解X0的目標函數(shù)值

為了便于討論，下面不妨總是假設31

弱對偶定理推論max問題的任何可行解目標函數(shù)值是其對偶min問題目標函數(shù)值的下限；min問題的任何可行解目標函數(shù)值是其對偶max問題目標函數(shù)值的上限如果原max(min)問題為無界解，則其對偶min(max)問題無可行解如果原max(min)問題有可行解，其對偶min(max)問題無可行解，則原問題為無界解注：有可能存在原問題和對偶問題同時無可行解的情況322.2.2最優(yōu)解判別定理定理若原問題的某個可行解X0的目標函數(shù)值與對偶問題某個可行解Y0的目標函數(shù)值相等，則X0,Y0分別是相應問題的最優(yōu)解證：由弱對偶定理推論1，結論是顯然的。即CX0

=Y0b

CX,Y0b=CX0

Yb

。證畢。

2.2.3主對偶定理定理如果原問題和對偶問題都有可行解，則它們都有最優(yōu)解，且它們的最優(yōu)解的目標函數(shù)值相等。證：由弱對偶定理推論1可知，原問題和對偶問題的目標函數(shù)有界，故一定存在最優(yōu)解?，F(xiàn)證明定理的后一句話。

33

主對偶定理的證明

證：現(xiàn)證明定理的后一句話。設X0為原問題的最優(yōu)解，它所對應的基矩陣是B，X0=B

1

b，則其檢驗數(shù)滿足C

CBB

1A0

令Y0=

CBB

1，則有Y0

A

C；而對原問題松弛變量的檢驗數(shù)有0

CBB

1I0，即Y0

0

。

顯然Y0為對偶問題的可行解。因此有對偶問題目標函數(shù)值，g(Y0)=Y0b=CBB

1

b

而原問題最優(yōu)解的目標函數(shù)值為

f(X0)=CX0=CBB

1

b故由最優(yōu)解判別定理可知Y0為對偶問題的最優(yōu)解。證畢。該定理的證明告訴我們一個非常重要的概念：對偶變量的最優(yōu)解等于原問題松弛變量的機會成本即對偶變量的最優(yōu)解是原問題資源的影子價格342.2.4互補松弛定理定理設X0,Y0分別是原問題和對偶問題的可行解，U0為原問題的松弛變量的值、V0為對偶問題剩余變量的值。X0,Y0分別是原問題和對偶問題最優(yōu)解的充分必要條件是Y0

U0+

V0X0=0證：由定理所設，可知有

AX0+U0=bX0,U0

0(1)Y0A

V0

=CY0,V0

0(2)分別以Y0左乘(1)式，以X0右乘(2)式后，兩式相減，得

Y0U0+V0X0

=Y0b

CX0若Y0U0+V0X0

=0，根據(jù)最優(yōu)解判別定理，X0,Y0分別是原問題和對偶問題最優(yōu)解。反之亦然。證畢。352.2.4互補松弛定理Y0

U0+

V0X0=0有什么應用若(Y0

)i>0，則(U0

)i=0，意味著原問題第i

約束行必須為=約束；對(X0

)i>0亦如此可用來簡化問題的求解線性規(guī)劃的高級算法：利用互補松弛定理，原問題與對偶問題同時解原問題為基礎可行解，對偶問題為非可行解，但滿足互補松弛條件；則當對偶問題為可行解時，取得最優(yōu)解362.2.5原問題檢驗數(shù)與對偶問題的解在主對偶定理的證明中我們有：對偶(min型)變量的最優(yōu)解等于原問題松弛變量的機會成本，或者說原問題松弛變量檢驗數(shù)的絕對值容易證明，對偶問題最優(yōu)解的剩余變量解值等于原問題對應變量的檢驗數(shù)的絕對值由于原問題和對偶問題是相互對偶的，因此對偶問題的檢驗數(shù)與原問題的解也有類似上述關系。更一般地講，不管原問題是否標準，在最優(yōu)解的單純型表中，都有原問題虛變量(松弛或剩余)的機會成本對應其對偶問題實變量

(對偶變量)的最優(yōu)解，原問題實變量(決策變量)的檢驗數(shù)對應其對偶問題虛變量

(松弛或剩余變量)的最優(yōu)解。因此，原問題或?qū)ε紗栴}只需求解其中之一就可以了。37

例2.2.3原問題檢驗數(shù)與對偶問題的解3839402.3對偶單純型算法

2.3.1基本思路原單純型迭代要求每步都是基礎可行解達到最優(yōu)解時，檢驗數(shù)cj–zj

0(max)或cj–zj

0(min)但對于(min,)型所加的剩余變量無法構成初始基礎可行解，因此通過加人工變量來解決大M法和二階段法較繁能否從剩余變量構成的初始基礎非可行解出發(fā)迭代，但保證檢驗數(shù)滿足最優(yōu)條件，cj–zj

0(max)或cj–zj

0(min)每步迭代保持檢驗數(shù)滿足最優(yōu)條件，但減少非可行度如何判斷達到最優(yōu)解如何保證初始基礎解滿足最優(yōu)條件為什么叫對偶單純型法b=B

1b

0412.3.2迭代步驟確定出變量找非可行解中最小者，即min{bi|bi<0}，設第i*行的最負，則i*行稱為主行，該行對應的基變量為出變量，xi*確定入變量最大比例原則

設j*

列滿足(2.3.1)式，j*

列稱為主列，xj*

為出變量

以主元ai*j*

為中心迭代

檢查當前基礎解是否為可行解

若是，則當前解即為最優(yōu)解否則，返回步驟142最大比例原則令V=C-CBB-1A

為檢驗數(shù)向量對min問題，V0稱為正則，即滿足最優(yōu)判定條件可以證明，V

的迭代也滿足四角運算法則令xr

為出變量，在第i*行；若選非基變量xj*為入變量必須滿足什么條件才能保證迭代后的解仍為正則的？因此只需考慮非基變量xj

觀察出變量xr

對應的檢驗數(shù)變化，因為有ai*r

=1，故

由于vj*

0，故必有ai*j*<0，即主元必須為負值

若xj

仍為基變量，則可知ai*j

=0

,43最大比例原則若xj

為非基變量，則當ai*j>

0時，顯然有

結合上述的幾個條件，則得到最大比例原則

若ai*j

<

0

時，則要求vj-vj*ai*j

/ai*j*

0,可解出注：這里的aij

都表示當前單純性表中的技術系數(shù)44

例2.3.1對偶單純型解法解：化原問題為適合對偶解法的標準型45

表2.3.1對偶單純型法的單純型表(min)答：最優(yōu)解為x1=14,x3=8,x2=x4=0,OBJ=14第九章特殊隨機服務系統(tǒng)秩序影響服務質(zhì)量9.1

M/G/1

等待制，無限源，無限容量G表示一般獨立分布，沒有具體的分布函數(shù)，但知道該分布的數(shù)學期望

1/

和方差

2設到達率為

，平均服務時長為h=1/

，則系統(tǒng)業(yè)務量為

=h；同樣，系統(tǒng)有穩(wěn)態(tài)的條件是

<1

9.1.1系統(tǒng)中逗留顧客的平均數(shù)由于服務時長不具有馬氏性，不能套用生滅方程求穩(wěn)態(tài)pj以第n

個顧客離去瞬間系統(tǒng)內(nèi)顧客數(shù)表示系統(tǒng)狀態(tài)，如圖Ln

為第n個顧客離開系統(tǒng)瞬間的系統(tǒng)排隊隊長Yn+1

為第n+1個顧客服務時間內(nèi)到達的顧客數(shù)47E[Yn+1]代表一個服務時長內(nèi)到達系統(tǒng)的平均顧客數(shù)E[U(Ln)]代表系統(tǒng)中有顧客逗留的概率，也即服務臺被占用的概率；服務臺被占用的概率就是

，所以有48Ld，Lq

不但與

有關，而且與

2有關(5),(6)式以俄國數(shù)學家樸拉切克—欣欽命名49顧客等待的概率為D=E[U(Ln)]=

，不需等待的概率為1

9.1.2平均剩余服務時間對于負指數(shù)服務時間分布，眾所周知剩余服務時間仍服從原來的分布，即h=1/

但在M/G/1中，平均剩余服務時間Tr

需要研究，它與顧客排隊等待的時間Wq

有關；顯然，Wq分為兩部分：(1)等待服務臺空出的平均時間，(2)排在隊中所有顧客的服務時間50對于定長分布，

=1，Tr=h/2對于負指數(shù)分布，

=2，Tr=h對于k

階愛爾蘭分布，

=？，Tr=？519.2優(yōu)先權服務系統(tǒng)

9.2.1M/G/1非強占優(yōu)先系統(tǒng)設有m

級顧客，1級顧客為最高優(yōu)先權，每級內(nèi)采用FIFO各級顧客到達率為

i，波松流，各級顧客的平均服務時長都為hi，方差為

i2；系統(tǒng)總業(yè)務量

=

i

hi，

<1利用上節(jié)推導出的等待服務臺空出的時間T1，可知W1=T1/(1

1)，遞推得第k

級顧客的平均等待時間Wk52

k

級顧客的平均等待時間與比之高級顧客的業(yè)務量有關平均服務時間短的顧客有高優(yōu)先權，可以減少總的排隊時間優(yōu)先權級別不宜太多，插隊現(xiàn)象就是增加等級，使總等待時間增加例1

在M/G/1服務系統(tǒng)中，有兩類顧客，都是波松到達過程。第一類顧客

1=2個/秒，定長服務h1=0.1秒/個；第二類顧客

2=0.5個/秒，負指數(shù)服務h2=1.2秒/個，試求：(1)不分優(yōu)先權時的顧客平均等待時間；(2)非強占優(yōu)先權，第一類顧客或第二類顧客優(yōu)先時，各類顧客的平均等待時間。解：

1=2，h1=0.1，

1=0.2Erl，

12=0；

2=0.5，h2=1.2，

2=0.6Erl，

22=h22=1.22=1.44 (1)不分優(yōu)先權，屬純M/G/1系統(tǒng)，由T1

公式，得

T1=(2/2)(0+0.12)+(0.5/2)(1.22+1.22)=0.73秒

Wq=T1/(1

)=0.73/(10.20.6)=3.65秒

(2)非強占優(yōu)先，第一類顧客優(yōu)先

W1=T1/(1

1)=0.73/(10.2)=0.9125秒

W2=T1/(1

1)(1

1

2)=0.73/(10.2)(10.8)=4.563秒 非強占優(yōu)先，第二類顧客優(yōu)先

W2=T1/(1

2)=0.73/(10.6)=1.825秒

W1=T1/(1

2)(1

1

2)=0.73/(10.6)(10.8)=9.125秒539.2.3M/M/n

服務系統(tǒng)，非強占優(yōu)先權與M/G/1非強占優(yōu)先權系統(tǒng)的基本假設大多數(shù)一樣，但有n

個獨立并聯(lián)服務臺，各級顧客的平均服務時間都是h各級顧客到達率為

i，系統(tǒng)總到達率

=

i，總業(yè)務量

=

i

h，

<n上節(jié)(10)式仍成立，有54令Wq

為全體顧客的平均等待時間，Lq

為平均隊長，則9.3溢流通路計算9.3.1部分利用度的概念當服務臺可以為所有進入系統(tǒng)的顧客服務時，稱為全利用度系統(tǒng)(Fullyprovided)當服務臺部分分組使用，部分公用，則稱為部分利用度系統(tǒng)，如圖所示55全利用度系統(tǒng)利用率最高，但不易組織分組專用效率低，但容易組織部分利用度系統(tǒng)綜合兩者的優(yōu)點9.3.2溢流通路的概念在電信網(wǎng)的組織中，由于經(jīng)濟的原因，并不是任兩個交換機之間都有直達的中繼線群在話務量適當?shù)狞c間開高效直達路由是經(jīng)濟的。所謂高效路由是指呼損率大的中繼線群(如B>0.02)，但當該中繼線忙時，允許通過迂回路由接通呼叫；在高效路由上呼損而轉(zhuǎn)移到迂回路由上的話務流量稱為溢流，如圖所示溢流具有突發(fā)性，不再是波松流，目前仍不清楚其分布具有溢流的系統(tǒng)是一個部分利用度系統(tǒng)569.3.3溢流通路的計算已知A23和給定的B23，可以用愛爾蘭損失公式直接求n23如何求溢流通路(2,1)的容量n21，因為其上除直達業(yè)務量A21，還有(2,3)的溢出流量Ao23

，而Ao23

不是波松流，不能簡單迭加，因而也不能直接用愛爾蘭損失公式求n21威爾金森(R.IWilkinson,1956)提出了“等效隨機流法”的近似計算方法就是給出一種溢出流的迭加方法，然后求一個等效波松流A

和一個等效電路群n，使A

通過n

后的溢流等于原溢出流的迭加，如圖所示57等效隨機流的計算方法與步驟1、計算(2,3)的溢流均值和方差由于n23

是A23

的專用通路，給定B23，有58威爾金森給出求溢流方差的公式2、計算各通路上的溢流總和的均值和方差注意，波松流自身的方差等于均值，即A21=

2213、計算等效隨機流A和等效通路數(shù)n波松流A

經(jīng)過通路n

都會有公式(1),(2)給出的溢流如何根據(jù)已知溢流(Ao,

o2)反解A

和n

拉普(Y.Rapp,1964)給出了反解公式等效隨機流的計算方法與步驟594、計算溢流通路的電路數(shù)N等效于將A

加載到n+N

的通路上，給定呼損B，有5、計算各通路的呼損將最終呼損AoN按各通路的溢流分攤拉普公式例1求溢流通路(A,D)的電路數(shù)NAD，要求B0.011、計算(D,B)(D,C)的溢流Ao1,

2o1

查表，并利用線性內(nèi)插，得602、計算(A,D)的總溢流Ao,

2o3、計算等效流

A

和等效電路n例1求溢流通路(A,D)的電路數(shù)NAD，要求B0.014、計算溢流通路(A,D)所需通路數(shù)N615、計算(A,D),(D,B)(D,C)的呼損有不合理現(xiàn)象，低等級點間的呼損小于骨干上點間呼損例2網(wǎng)路優(yōu)化問題1、各點間每條直達電路的成本不一樣2、匯接局的交換機每個路端的成本比非匯接局(端局)要高很多3、因此，網(wǎng)路優(yōu)化是線路成本和交換成本的平衡4、有三種基本結構：純匯接(星型)、獨立直達和高效直達5、高效直達中還可以進一步優(yōu)化62第六章圖與網(wǎng)路分析圖是最直觀的模型64BACD圖論

GraphTheory哥尼斯堡七橋問題(K?nigsbergBridgeProblem)LeonhardEuler(1707-1783)在1736年發(fā)表第一篇圖論方面的論文，奠基了圖論中的一些基本定理很多問題都可以用點和線來表示，一般點表示實體，線表示實體間的關聯(lián)656.1圖與網(wǎng)路的基本概念

6.1.1圖與網(wǎng)路節(jié)點

(Vertex)物理實體、事物、概念一般用vi

表示邊

(Edge)節(jié)點間的連線，表示有關聯(lián)一般用eij

表示圖

(Graph)節(jié)點和邊的集合一般用G(V,E)表示點集V={v1,v2,…,vn}邊集E={eij}網(wǎng)路

(Network)邊上具有表示連接強度的權值，如wij又稱加權圖(Weightedgraph)666.1.2無向圖與有向圖所有邊都沒有方向的圖稱為無向圖，如圖6.1在無向圖中eij=eji，或(vi,vj)=(vj,vi)當所有邊都有方向時，稱為有向圖，用G(V,A)表示在有向圖中，有向邊又稱為弧，用aij表示，i,j的順序是不能顛倒的，圖中弧的方向用箭頭標識圖中既有邊又有弧，稱為混合圖

6.1.3端點，關聯(lián)邊，相鄰，次圖中可以只有點，而沒有邊；而有邊必有點若節(jié)點vi,vj

之間有一條邊eij，則稱vi,vj

是eij的端點(endvertex)，而eij

是節(jié)點vi,vj的關聯(lián)邊(incidentedge)同一條邊的兩個端點稱為相鄰(adjacent)節(jié)點，具有共同端點的邊稱為相鄰邊一條邊的兩個端點相同，稱為自環(huán)(self-loop)；具有兩個共同端點的兩條邊稱為平行邊(paralleledges)既沒有自環(huán)也沒有平行邊的圖稱為簡單圖(simplegraph)在無向圖中，與節(jié)點相關聯(lián)邊的數(shù)目，稱為該節(jié)點的“次”(degree)，記為d

；次數(shù)為奇數(shù)的點稱為奇點(odd),次數(shù)為偶數(shù)的點稱為偶點(even)；圖中都是偶點的圖稱為偶圖(evengraph)68

6.1.3端點，關聯(lián)邊，相鄰，次有向圖中，由節(jié)點向外指的弧的數(shù)目稱為正次數(shù)，記為d+，指向該節(jié)點的弧的數(shù)目稱為負次數(shù)，記為d–次數(shù)為0的點稱為孤立點(isolatedvertex)

，次數(shù)為1的點稱為懸掛點(pendantvertex)定理1：圖中奇點的個數(shù)總是偶數(shù)個

6.1.4鏈，圈，路徑，回路，歐拉回路相鄰節(jié)點的序列

{v1

,v2

,…,vn

}構成一條鏈(link)，又稱為行走(walk)；首尾相連的鏈稱為圈(loop)，或閉行走在無向圖中，節(jié)點不重復出現(xiàn)的鏈稱為路徑(path)；在有向圖中，節(jié)點不重復出現(xiàn)且鏈中所有弧的方向一致，則稱為有向路徑(directedpath)首尾相連的路徑稱為回路(circuit)；69

走過圖中所有邊且每條邊僅走一次的閉行走稱為歐拉回路定理2：偶圖一定存在歐拉回路(一筆畫定理)

6.1.5連通圖，子圖，成分設有兩個圖G1(V1,E1),G2(V2,E2),若V2

V1,E2

E1，則G2是G1的子圖無向圖中，若任意兩點間至少存在一條路徑，則稱為連通圖(connectedgraph)，否則為非連通圖(discon-nectedgraph)；非連通圖中的每個連通子圖稱為成分

(component)鏈，圈，路徑(簡稱路)，回路都是原圖的子圖平面圖(planargraph)，若在平面上可以畫出該圖而沒有任何邊相交706.2樹圖與最小生成樹一般研究無向圖樹圖：倒置的樹，根(root)在上，樹葉(leaf)在下多級輻射制的電信網(wǎng)絡、管理的指標體系、家譜、分類學、組織結構等都是典型的樹圖716.2.1樹的定義及其性質(zhì)任兩點之間有且只有一條路徑的圖稱為樹(tree)，記為T

樹的性質(zhì)：最少邊的連通子圖，樹中必不存在回路任何樹必存在次數(shù)為1的點具有n

個節(jié)點的樹T的邊恰好為

n

1條，反之，任何有n

個節(jié)點，n

1條邊的連通圖必是一棵樹

6.2.2圖的生成樹樹T是連通圖G的生成樹(spanningtree)，若T是G的子圖且包含圖G的所有的節(jié)點；包含圖G中部分指定節(jié)點的樹稱為steinertree每個節(jié)點有唯一標號的圖稱為標記圖，標記圖的生成樹稱為標記樹(labeledtree)Caylay定理：n(

2)個節(jié)點，有nn

2個不同的標記樹72

6.2.2

圖的生成樹如何找到一棵生成樹深探法(depthfirstsearch)：任選一點標記為0點開始搜索，選一條未標記的邊走到下一點，該點標記為1，將走過的邊標記；假設已標記到i

點，總是從最新標記的點向下搜索，若從i

點無法向下標記，即與i

點相關聯(lián)的邊都已標記或相鄰節(jié)點都已標記，則退回到

i

1點繼續(xù)搜索，直到所有點都被標記廣探法(breadthfirstsearch)：是一種有層級結構的搜索，一般得到的是樹形圖736.2.3

最小生成樹有n個鄉(xiāng)村，各村間道路的長度是已知的，如何敷設光纜線路使n個鄉(xiāng)村連通且總長度最短顯然，這要求在已知邊長度的網(wǎng)路圖中找最小生成樹

最小生成樹的算法：Kruskal

算法：將圖中所有邊按權值從小到大排列，依次選所剩最小的邊加入邊集T，只要不和前面加入的邊構成回路，直到T中有n

1條邊，則T是最小生成樹Kruskal

算法基于下述定理定理3

指定圖中任一點vi，如果vj

是距vi最近的相鄰節(jié)點，則關聯(lián)邊eij必在某個最小生成樹中。推論將網(wǎng)路中的節(jié)點劃分為兩個不相交的集合V1和V2，V2=V

V1，則V1和V2間權值最小的邊必定在某個最小生成樹中。746.2.3

最小生成樹最小生成樹不一定唯一定理3推論是一個構造性定理，它指示了找最小生成樹的有效算法Prim

算法：不需要對邊權排序，即可以直接在網(wǎng)路圖上操作，也可以在邊權矩陣上操作，后者適合計算機運算

邊權矩陣上的Prim算法：1、根據(jù)網(wǎng)路寫出邊權矩陣，兩點間若沒有邊，則用表示；2、從v1

開始標記，在第一行打，劃去第一列；3、從所有打的行中找出尚未劃掉的最小元素，對該元素畫圈，劃掉該元素所在列，與該列數(shù)對應的行打；4、若所有列都劃掉，則已找到最小生成樹(所有畫圈元素所對應的邊)；否則，返回第3步。該算法中，打行對應的節(jié)點在V1中，未劃去的列在V2中756.2.3

最小生成樹Prim算法是多項式算法Prim算法可以求最大生成樹網(wǎng)路的邊權可以有多種解釋，如效率次數(shù)受限的最小生成樹—尚無有效算法最小Steiner樹—尚無有效算法

766.3

最短路問題

6.3.1狄克斯特拉算法(Dijkstraalgorithm,1959)計算兩節(jié)點之間或一個節(jié)點到所有節(jié)點之間的最短路令

dij

表示

vi

到vj

的直接距離(兩點之間有邊)，若兩點之間沒有邊，則令dij

=

，若兩點之間是有向邊，則dji

=

；令dii

=0，s

表示始點，t

表示終點0、令始點Ts=0，并用框住，所有其它節(jié)點臨時標記Tj=

；1、從vs

出發(fā)，對其相鄰節(jié)點vj1

進行臨時標記，有Tj1=ds,j1

；2、在所有臨時標記中找出最小者，并用框住，設其為vr

。若此時全部節(jié)點都永久標記，算法結束；否則到下一步；3、從新的永久標記節(jié)點vr

出發(fā)，對其相鄰的臨時標記節(jié)點進行再標記，設vj2

為其相鄰節(jié)點，則Tj2=min{Tj2,Tr+dr,j2}，返回第2步。77例1狄克斯特拉算法0

81510121511311378

Dijkstra最短路算法的特點和適應范圍一種隱階段的動態(tài)規(guī)劃方法，而且是正向遞推每次迭代只有一個節(jié)點獲得永久標記，若有兩個或兩個以上節(jié)點的臨時標記同時最小，可任選一個永久標記；總是從一個新的永久標記開始新一輪的臨時標記，是一種深探法被框住的永久標記Tj

表示vs

到vj

的最短路，因此要求dij0，第k次迭代得到的永久標記，其最短路中最多有

k

條邊，因此最多有n1

次迭代可以應用于簡單有向圖和混合圖，在臨時標記時，所謂相鄰必須是箭頭指向的節(jié)點；若第n1

次迭代后仍有節(jié)點的標記為，則表明vs

到該節(jié)點無有向路徑如果只求vs

到vt

的最短路，則當vt

得到永久標記算法就結束了；但算法復雜度是一樣的應用Dijkstra算法n1

次，可以求所有點間的最短路vs

到所有點的最短路也是一棵生成樹，但不是最小生成樹796.3.2Warshall-Floyd算法(1962)Warshall-Floyd算法可以解決有負權值邊(弧)的最短路問題該算法是一種整體算法，一次求出所有點間的最短路該算法不允許有負權值回路，但可以發(fā)現(xiàn)負權值回路該算法基于基本的三角運算定義對給定的點間初始距離矩陣{dij}，令dii=

，

i。對一個固定點j，運算dik=min{dik,dij+djk},

i,k

j,稱為三角運算。(注意，這里允許i=k)定理依次對j=1,2,…,n執(zhí)行三角運算，則dik

最終等于i

到k

間最短路的長度。806.3.2Floyd-Warshall算法(1962)fori=1tondodii=;foralleij=0;forj=1tondofori=1tondoifi

jthenfork=1tondoifk

jthenbegin

dik=min{dik,dij+djk};

ifdik>dij+djktheneik=j

end;若網(wǎng)路中存在負回路，則計算中，某些dii會小于0，此時應中斷算法顯然，F(xiàn)loyd算法要進行n(n-1)2次加法和比較如何回溯找出任兩點之間的最短路？在Floyd算法中設一伴隨矩陣E={eik}，eik

記錄了i

到

k

最短路中最后一個中間節(jié)點81小結最短路有廣泛的應用(6.3.4節(jié)市話局擴容方案)最短路的多種形式：無向圖，有向圖無循環(huán)圈，有向圖，混合圖，無負邊權，有負邊權，有負回路，k-最短路等當存在負權值邊時，F(xiàn)loyd算法比Dijkstra算法效率高，且程序極簡單。但Dijkstra算法靈活若圖是前向的，則Dijkstra算法也可以求兩點間最長路一般情況下，兩點間最長路是NP-complete，但最短路是P算法兩點間k-最短路：分為邊不相交的和邊相交的

求邊不相交的k-最短路非常容易：先求最短路，將該最短路中的邊從網(wǎng)路刪去，再用Dijkstra算法可求次最短路，以此類推826.3.4最短路應用舉例——市話擴容(實裝率=0.8)83最短路應用舉例—市話擴容846.4網(wǎng)路的最大流和最小截

6.4.1網(wǎng)路的最大流的概念網(wǎng)路流一般在有向圖上討論定義網(wǎng)路上支路的容量為其最大通過能力，記為cij，支路上的實際流量記為fij圖中規(guī)定一個發(fā)點s，一個收點t節(jié)點沒有容量限制，流在節(jié)點不會存儲容量限制條件：0

fij

cij平衡條件：

滿足上述條件的網(wǎng)路流稱為可行流，總存在最大可行流當支路上fij=cij

，稱為飽和弧最大流問題也是一個線性規(guī)劃問題viA(vi)B(vi)856.4.2截集與截集容量定義：把網(wǎng)路分割為兩個成分的弧的最小集合，其中一個成分包含s

點，另一個包含t

點。一般包含s

點的成分中的節(jié)點集合用V表示，包含t

點的成分中的節(jié)點集合用V表示截集容量是指截集中正向弧的容量之和

福特-富克森定理：網(wǎng)路的最大流等于最小截集容量866.4.3確定網(wǎng)路最大流的標號法從任一個初始可行流出發(fā)，如0流基本算法：找一條從s

到t

點的增廣鏈(augmentingpath)若在當前可行流下找不到增廣鏈，則已得到最大流增廣鏈中與s

到t方向一致的弧稱為前向弧，反之后向弧

增廣過程：前向弧f

ij=fij+q,后向弧f

ij=fij

q

增廣后仍是可行流

87

最大流最小截的標號法步驟第一步：標號過程，找一條增廣鏈1、給源點s

標號[s+,q(s)=]，表示從s點有無限流出潛力2、找出與已標號節(jié)點i

相鄰的所有未標號節(jié)點j，若(1)(i,j)是前向弧且飽和，則節(jié)點

j

不標號；(2)(i,j)是前向弧且未飽和，則節(jié)點

j

標號為[i+,q(j)]，表示從節(jié)點i

正向流出，可增廣q(j)=min[q(i),cij

fij]；(3)(j,i)是后向弧，若fji=0，則節(jié)點j

不標號；(4)(j,i)是后向弧，若fji>0，則節(jié)點j

標號為[i

,q(j)]，表示從節(jié)點j

流向

i，可增廣q(j)=min[q(i),fji]；3、重復步驟2，可能出現(xiàn)兩種情況：(1)節(jié)點t

尚未標號，但無法繼續(xù)標記，說明網(wǎng)路中已不存在增廣鏈，當前流v(f)就是最大流；所有獲標號的節(jié)點在V

中，未獲標號節(jié)點在V

中，V與V

間的弧即為最小截集；算法結束(2)節(jié)點t

獲得標號，找到一條增廣鏈，由節(jié)點t

標號回溯可找出該增廣鏈；到第二步88

最大流最小截的標號法步驟第二步：增廣過程1、對增廣鏈中的前向弧，令f=f+q(t)，q(t)為節(jié)點t

的標記值2、對增廣鏈中的后向弧，令f=f

q(t)3、非增廣鏈上的所有支路流量保持不變第三步：抹除圖上所有標號，回到第一步以上算法是按廣探法描述的，但在實際圖上作業(yè)時，按深探法進行更快捷一次只找一條增廣鏈，增廣一次換一張圖最后一次用廣探法，以便找出最小截集89最大流最小截集的標號法舉例(s+,)(s+,6)(2

,6)(3+,1)(4+,1)(s+,)(s+,5)(2+,2)(5

,2)(4+,2)90最大流最小截集的標號法舉例(s+,)(s+,3)(2

,3)最小截集91

最大流標號法的復雜度討論找一條增廣鏈的計算量是容易估計的，不會超過O(n2)但是最多迭代多少次(即增廣的次數(shù))就很難估計，在最壞情況下，與邊的容量有關；如上圖：先增廣suvt,然后增廣svut，每次只能增廣1個單位，故要增廣4000次才能結束克服這種缺點的經(jīng)驗方法：盡量先用段數(shù)少的增廣鏈盡量不重復前面出現(xiàn)過的增廣鏈926.4.4多端網(wǎng)路問題936.4.5

最小費用最大流雙權網(wǎng)路：每條弧不但有容量，還有單位流量的通過費用兩種解法：一種基于最小費用路徑算法；一種基于可行弧集的最大流算法基于最小費用路徑算法：總是在當前找到的最小費用的路徑上增廣流；缺點是每次增廣后要改變弧的費用，且出現(xiàn)負權值費用的弧基于可行弧集的最大流算法：從0費用弧集開始應用最大流算法，然后根據(jù)計算信息提高費用的限界P，使可行弧集增大，再應用最大流算法，直至所有弧都進入可行弧集。這種算法是一種主-對偶規(guī)劃的解法。使用這種方法的還有運輸問題、匹配問題946.4.5

以最短路為基礎匯總網(wǎng)路上的流在電路網(wǎng)中每兩點之間都有中繼電路群需求，但并不是任兩點都有物理傳輸鏈路根據(jù)兩點間最短傳輸路徑將該兩點間的電路需求量加載到這條傳輸路徑上去：設a25=10是節(jié)點2和5之間的電路需求，節(jié)點2和5之間的最短傳輸路徑為2

1

3

5，則加載過程為:T21=T21+10,T13=T13+10,T35=T35+10；Tij

是傳輸鏈路i

j

上加載的電路數(shù)；當所有點間電路都加載完則算法結束956.5歐拉回路和中國郵遞員問題中國郵遞員問題(ChinesePostmanProblem,CPP)是由我國管梅谷教授于1962年首先提出并發(fā)表的問題是從郵局出發(fā)，走遍郵區(qū)的所有街道至少一次再回到郵局，走什么路由才能使總的路程最短？如果街區(qū)圖是一個偶圖，根據(jù)定理3，一定有歐拉回路，CPP問題也就迎刃而解了若街區(qū)圖不是偶圖，則必然有一些街道要被重復走過才能回到原出發(fā)點顯然要在奇次點間加重復邊如何使所加的邊長度最少歸結為求奇次點間的最小匹配(minimumweightedmatch)—由Edmons給出多項式算法(1965)96

解中國郵遞員問題的步驟0、將圖中的所有懸掛點依次摘去1、求所有奇次點間的最短距離和最短路徑2、根據(jù)奇次點間的最短距離求最小完全匹配3、根據(jù)最小完全匹配和最短路徑添加重復邊4、將懸掛點逐一恢復，并加重復邊5、根據(jù)得到的偶圖，給出歐拉回路的若干種走法97

解中國郵遞員問題的步驟986.6哈密爾頓回路及旅行推銷員問題

6.6.1哈密爾頓回路(Hamiltoniancircuit)連通圖G(V,E)中的回路稱為哈密爾頓回路，若該回路包括圖中所有的點。顯然哈密爾頓回路有且只有n

條邊，若|V|=n連通圖具有哈密爾頓回路的充分必要條件是什么？這個問題是由愛爾蘭數(shù)學家哈密爾頓1859年提出的，但至今仍未解決歐拉回路是對邊進行訪問的問題，哈密爾頓回路是對點進行訪問的問題搜索哈密爾頓回路的難度是NP-complete任兩點間都有邊的圖稱為完全圖(或全連接圖)完全圖中有多少個不同的哈密爾頓回路？完全圖中有多少個邊不相交的哈密爾頓回路？最小哈密爾頓回路問題

(NP-complete)哈密爾頓路徑：包含圖中所有點的路徑為什么說找兩點間的最長路是非常困難的問題？(n

1)!/2(n

1)/2996.6.2旅行推銷員問題(TravelingSalesman

Problem)旅行推銷員問題(TSP)：設v1,v2,...,vn

為n

個已知城市，城市之間的旅程也是已知的，要求推銷員從v1出發(fā)，走遍所有城市一次且僅一次又回到出發(fā)點，并使總旅程最短這種不允許點重復的旅行推銷員問題就是最小哈密爾頓回路問題一般旅行推銷員問題(GTSP)：允許點重復的TSP當網(wǎng)路邊權滿足三角不等式時，一般旅行推銷員問題就等價于最小哈密爾頓回路問題當網(wǎng)路邊權不滿足三角不等式時，只要用兩點間最短路的距離代替原來的邊權，就可以滿足三角不等式，在此基礎上求最小哈密爾頓回路

典型的應用：鄉(xiāng)郵員的投遞路線郵遞員開郵箱取信的路線問題郵車到各支局的轉(zhuǎn)趟問題100

TSP的啟發(fā)式算法(Heuristicalgorithm)窮舉法：指數(shù)算法分支定界法：隱枚舉法二交換法(two-option,Lin’salgorithm)哈密爾頓回路可以用點的序列表示從任一個哈密爾頓回路(即任何一個序列)出發(fā)按照一定順序試圖交換相鄰兩個點的順序，若路程減少則完成交換，繼續(xù)下一個交換；若沒有改善，則不進行本次交換，嘗試下一個交換；若所有的相臨交換都試過而不能改善，則算法結束，得到一個局部最優(yōu)點模擬退火(SimulatedAnnealing)隨機地采用二交換法當交換后沒有使目標函數(shù)改善，也可能以玻爾茲曼分布概率被接受，但這種概率是隨模擬的溫度下降而減少的發(fā)揮了計算機的優(yōu)點，盡量減少陷入局部極值點模擬物理機制101

二交換法舉例初始解：1-2-3-4-5

1-3-2-4-51-3-2-4-5

1-3-4-2-51-3-4-2-5

1-3-4-5-2

5-3-4-2-13-1-4-2-5102

算法復雜度Prim算法i=1n

1次比較，最多n

1次賦值i=22(n

2)次比較，最多2(n

2)次賦值i=k

k(n

k)次比較，最多k(n

k)次賦值Dijkstra算法i=1n

1次臨時標記，永久標記n

1次比較和賦值i=2n

2次臨時標記，永久標記n

2次比較和賦值i=k

n

k

次臨時標記，永久標記n

k

次比較和賦值103Prim算法的改進增加一個輔助記錄型數(shù)組，用以記錄當前V

中各節(jié)點到V

的最小邊，minedge[i].cost記錄該邊的權值，minedge[i].vex記錄該邊V

中的頂點。若minedge[i].cost<0則表明i

點進入集合Vfori:=2tondobeginminedge[i].vex:=1;minedge[i].cost:=w[1,i]end;fori:=1ton

1dobeginmi:=maxint;forj:=2tondoif(minedge[j].cost>0)and(minedge[j].cost<mi)thenbegink:=j;mi:=minedge[j].costend;minedge[k].cost:=

minedge[k].cost;{找到k，將k

加入集合V}forj:=2tondoif(w[k,j]<minedge[j].cost)thenbeginminedge[j].cost:=w[k,j];minedge[j].vex:=k;end;end;{該算法復雜度約為5n(n-1)}104

匹配問題(MatchingProblem)定義：圖中一組邊的集合，當圖中的每個節(jié)點最多只與該集合中的一條邊相關聯(lián)，則該邊集就成為匹配。1、兩部圖的匹配問題圖中的節(jié)點可分為兩個集合，X,Y，X與Y

之間有邊相連，但X

內(nèi)部和Y

內(nèi)部無關聯(lián)邊，稱為兩部圖運輸問題實際上是兩部圖的最小費用最大流問題任務分配問題實際上是兩部圖的最小完全匹配問題2、非兩部圖的匹配問題(1)最大基數(shù)匹配(maximumcardinalitymatching)(2)最大權匹配(maximumweightmatching)(3)最小完全匹配(minimumweightperfectmatching)(4)最優(yōu)分數(shù)匹配(optimalfractionalmatching)105兩部圖的最小完全匹配匈亞利算法任務分配問題的抽象就是兩部圖的最小完全匹配問題匈亞利算法(Hungarianmethod)由Kuhn教授提出，它實際上是主對偶算法的先驅(qū)匈亞利算法借助于效率矩陣和兩部圖來完成運算任務分配問題的效率矩陣對應的是兩部圖的邊權{cij}，對偶問題的解對應的是每條邊的兩個端點{ai,bj}；對偶約束為ai,＋bj

cij匈亞利算法的實質(zhì)是通過構造對偶問題的可行解，得到一個等值邊子圖，即所有ai,＋bj＝cij

的邊構成的圖；然后在等值邊子圖上求最大基數(shù)匹配；當?shù)玫皆瓎栴}的完全匹配，則算法結束對偶問題的可行解

等值邊子圖滿足互補松弛定理求原問題的解(部分可行解)檢驗擴充等值邊子圖

106最大基數(shù)匹配最大基數(shù)匹配是基于交錯樹的算法敞露點、根、交錯鏈、外點、內(nèi)點、增廣鏈尚未匹配的節(jié)點稱為敞露點以敞露點為根，由非匹配邊和匹配邊交替構成的鏈稱為交錯鏈交錯鏈的根為外點，其后內(nèi)點與外點交替；外點是交錯鏈的生長點以內(nèi)點結束的交錯鏈稱為增廣鏈，因為反轉(zhuǎn)該鏈上各邊的匹配狀態(tài)可使匹配的邊數(shù)增加一條107匈亞利算法步驟令所有ai＝0在效率矩陣中找每列最小值qj，令bj＝qj

，故i,j，滿足ai＋bj

cij在滿足ai＋bj＝cij

的邊構成的等值子圖中求最大基數(shù)匹配；若達到完全匹配則結束，否則到下一步對敞露點求每列的最小松弛量sj＝mini*{ci*j－ai*－bj}求最大增廣量S＝0.5

minj{sj}增廣等值子圖，

j，bj＝bj＋S

i*(敞露點)，aj＝aj＋S

；

i(非敞露點)，aj＝aj－S返回到第3

步108匈亞利算法舉例**109匈亞利算法舉例*110匈亞利算法舉例111

任務分配問題、匹配問題和TSP的關系三個問題都有一個n

n

正權值的邊權矩陣三個問題的解都可以用代數(shù)置換(permutation)表示i1,i2,i3,i4,i5是1,2,3,4,5的任一排列，表示元素位置的交換輪換，全輪換，對換TSP的解必須是一個全輪換任務分配問題的解可以是任一個置換匹配的解必須是n/2個對換任務分配問題是匹配問題的松弛問題112

6.7

選址問題使所選地址到最遠的服務對象距離盡可能小——中心點使所選地址到各服務對象的總距離最小——中位點有時間限制的多用中心點，如鄉(xiāng)郵局總資源約束的多用中位點，如電話交換局

6.7.1各點之間的距離節(jié)點到節(jié)點間的最短距離，稱為節(jié)點—節(jié)點距離邊上某點到節(jié)點的最短距離，稱為點—節(jié)點距離節(jié)點到某邊上最遠一點的距離，稱為節(jié)點—邊距離邊上一點到另一邊上最遠點的距離，稱為點—邊距離1131、邊上某點到節(jié)點的最短距離dij

代表vi

與vj

間的最短距離，ars

代表邊(r,s)的邊長，令h

為邊(r,s)上一點的百分位，0

h1邊上對應h

的一點到vj

的最短距離為

d[h(r,s),j]=min[h

ars+drj,(1

h)

ars+dsj]2、節(jié)點到某邊上最遠一點的距離指定節(jié)點j，它到邊(r,s)上對應h百分位點有兩條路，最遠點必使兩條路一樣長，故有

d[j,(r,s)]=0.5[djr+djs+ars]3、邊上指定一點到其他邊上最遠點的距離h

是邊(r,s)上指定的百分位點，另一邊為(u,t)d[h(r,s),(u,t)]=min[h

ars+d[r,(u,t)],(1

h)

ars+d[s,(u,t)]]114

6.7.2

中心的選擇中心：以節(jié)點—節(jié)點距離為基礎，大中取小(maxmin)一般中心：以節(jié)點—邊距離為基礎，大中取小絕對中心：以點—節(jié)點距離為基礎，大中取小一般絕對中心：以點—邊距離為基礎，大中取小左圖的中心是v1；而三個節(jié)點都是一般中心類似也有四種中位點：中位點一般中位點絕對中位點一般絕對中位點115

例6.7.1~6.7.2中心一般中心中位點一般中位點第七章隨機服務理論概述確定型只是隨機現(xiàn)象的特例7.1隨機服務系統(tǒng)系統(tǒng)的輸入與輸出是隨機變量A.k.Erlang于1909~1920年發(fā)表了一系列根據(jù)話務量計算電話機鍵配置的方法，為隨機服務理論奠定了基礎又稱為排隊論(QueuingTheory)或擁塞理論(CongestionTheory)117

與服務系統(tǒng)性能相關的特性服務系統(tǒng)存在來自兩個矛盾方面的要求顧客希望服務質(zhì)量好，如排隊等待時間短，損失率低系統(tǒng)運營方希望設備利用率高給用戶一個經(jīng)濟上能夠承受的滿意的質(zhì)量哪些系統(tǒng)特性會影響系統(tǒng)的性能？服務機構的組織方式與服務方式顧客的輸入過程和服務時間分布系統(tǒng)采用的服務規(guī)則

7.1.1服務機構的組織方式與服務方式單臺制和多臺制并聯(lián)服務串聯(lián)服務串并聯(lián)服務、網(wǎng)絡服務全利用度、部分利用度118

與服務系統(tǒng)性能相關的特性7.1.2輸入過程和服務時間顧客單個到達或成批到達顧客到達時間間隔的分布和服務時間的分布顧客源是有限的還是無限