運(yùn)籌學(xué)全套課件

第八章標(biāo)準(zhǔn)服務(wù)系統(tǒng)

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

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

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

，每臺(tái)的服務(wù)率為

則有

j=

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

n=0，

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

j,

j

代入生滅方程，得式中

=

/

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

和

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

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

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

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

，給定B，求所需最少的服務(wù)臺(tái)n求n

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

求所需服務(wù)臺(tái)的方法1、查圖，如書上262頁2、迭代計(jì)算無法由En(

)給出n

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

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

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

，A

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

=0.455已知n

和

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

=2.5，由表可知B

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

成線性關(guān)系，則有線性內(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人/小時(shí)，平均服務(wù)時(shí)長30分鐘/人，試求：(1)系統(tǒng)中沒有顧客的概率；(2)只有一個(gè)服務(wù)臺(tái)被占用的概率；(3)系統(tǒng)的損失率解：由題意可知

=60/30=2人/小時(shí)，所以

=

/

=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í)平均呼叫次數(shù)為240，每次通話平均時(shí)長為5分鐘，規(guī)定兩局間中繼線的服務(wù)等級(jí)為B

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

=2405/60=20Erl，

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

(2)查愛爾蘭表可知：n=30，B=0.01時(shí)可承擔(dān)A=20.337，B=0.005時(shí)可承擔(dān)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

服務(wù)臺(tái)利用率與服務(wù)臺(tái)數(shù)量的關(guān)系

n

圖當(dāng)給定n

和B

后，系統(tǒng)所能承擔(dān)的業(yè)務(wù)量

可以通過愛爾蘭公式求出，從而可計(jì)算出服務(wù)臺(tái)利用率

；若保持B

不變，不斷增加服務(wù)臺(tái)數(shù)n，

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

n

圖如下；通過觀察，有幾點(diǎn)結(jié)論：1、B不變時(shí)，

隨

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

隨

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

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

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

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

B

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

=(A

A)/A=A/A

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

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

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

1=4人/小時(shí)，

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

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

1=40.1=0.4Erl,

2=80.1=0.8Erl

查愛爾蘭表，得n1=3臺(tái)，n2=4臺(tái)，共需7臺(tái)。

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)合組時(shí)：

=120.1=1.2Erl,

查愛爾蘭表，得n

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

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)例交換機(jī)內(nèi)部有n

條繩路，N條入中繼線，N>n；每條入中繼線上的呼叫到達(dá)強(qiáng)度為

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

j=(N–j)

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

n=0，

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

j,

j

代入生滅方程，得11

當(dāng)j=n

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

，又稱為有效到達(dá)率

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

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

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

有一電話查詢服務(wù)處集中答復(fù)三個(gè)查詢點(diǎn)的所有查詢事項(xiàng)。查詢服務(wù)處與查詢點(diǎn)之間用電話聯(lián)系。查詢服務(wù)處只有一名值班員答復(fù)所有的查詢。已知每個(gè)查詢點(diǎn)平均每小時(shí)有兩次查詢，每次平均通話12分鐘，問：(1)值班員空閑的概率；(2)值班員打電話的概率；(3)查詢時(shí)值班員忙的概率；(4)服務(wù)處查詢電話的平均到達(dá)率；(5)值班員的工時(shí)利用率。解：系統(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)概率及等待概率令從顧客源來的顧客到達(dá)率為

，每臺(tái)的服務(wù)率為

則有

j=

,j0;

j=j,j<n；

j=n,j

n將

j,

j

代入生滅方程，得15當(dāng)

n

時(shí)，則p0

中第二項(xiàng)不收斂，系統(tǒng)中隊(duì)長將趨于無窮當(dāng)

<n

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

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

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

公式

D的記憶法168.2.2系統(tǒng)的各種指標(biāo)等待制系統(tǒng)的指標(biāo)有：平均逗留隊(duì)長；平均等待隊(duì)長；平均逗留時(shí)長；平均等待時(shí)長和服務(wù)臺(tái)利用率等n=1時(shí)，D=

，Ld=

/(1

)，Lq=

2/(1

)，Wq=

/(

)例5

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

個(gè)顧客，j

n

時(shí)，新來顧客要排隊(duì)等待，采用FIFO規(guī)則；令新顧客到達(dá)時(shí)為0時(shí)刻，顯然，只有服務(wù)臺(tái)上離去j

n個(gè)顧客時(shí)，新顧客才排到隊(duì)首當(dāng)n

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

次的概率為18

等待時(shí)長分布的推導(dǎo)19例6

某儲(chǔ)蓄所內(nèi)，已知忙時(shí)顧客到達(dá)率

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

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

M/M/n

等待制。

=

/

=40/16=2.5Erl (1)

=

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

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

+(

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

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

=3只/日。設(shè)船只到達(dá)的間隔時(shí)間和裝卸時(shí)間都服從負(fù)指數(shù)分布，問港口生產(chǎn)能力設(shè)計(jì)為多大時(shí)，每天總費(fèi)用最??？解：系統(tǒng)是無限源

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

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

j=

0

/(1+j)，

0為隊(duì)長為0時(shí)的顧客到達(dá)率從而系統(tǒng)的

j

和

j

為將

j

和

j

代入生滅方程，得第二章

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

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

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

例2.1.1設(shè)A、B資源的出售價(jià)格分別為y1

和

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

行原問題的價(jià)值系數(shù)C變換為對(duì)偶問題的右端項(xiàng)原問題的右端項(xiàng)

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

表2.1.1對(duì)偶變換的規(guī)則約束條件的類型與非負(fù)條件對(duì)偶非標(biāo)準(zhǔn)的約束條件類型對(duì)應(yīng)非正常的非負(fù)條件對(duì)偶變換是一一對(duì)應(yīng)的302.2線性規(guī)劃的對(duì)偶定理

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

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

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

=Y0b

CX,Y0b=CX0

Yb

。證畢。

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

33

主對(duì)偶定理的證明

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

1

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

CBB

1A0

令Y0=

CBB

1，則有Y0

A

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

CBB

1I0，即Y0

0

。

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

1

b

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

f(X0)=CX0=CBB

1

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

U0+

V0X0=0證：由定理所設(shè)，可知有

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分別是原問題和對(duì)偶問題最優(yōu)解。反之亦然。證畢。352.2.4互補(bǔ)松弛定理Y0

U0+

V0X0=0有什么應(yīng)用若(Y0

)i>0，則(U0

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

約束行必須為=約束；對(duì)(X0

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

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

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

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

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

0(max)或cj–zj

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

0(max)或cj–zj

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

1b

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

設(shè)j*

列滿足(2.3.1)式，j*

列稱為主列，xj*

為出變量

以主元ai*j*

為中心迭代

檢查當(dāng)前基礎(chǔ)解是否為可行解

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

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

的迭代也滿足四角運(yùn)算法則令xr

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

觀察出變量xr

對(duì)應(yīng)的檢驗(yàn)數(shù)變化，因?yàn)橛衋i*r

=1，故

由于vj*

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

若xj

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

=0

,43最大比例原則若xj

為非基變量，則當(dāng)ai*j>

0時(shí)，顯然有

結(jié)合上述的幾個(gè)條件，則得到最大比例原則

若ai*j

<

0

時(shí)，則要求vj-vj*ai*j

/ai*j*

0,可解出注：這里的aij

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

例2.3.1對(duì)偶單純型解法解：化原問題為適合對(duì)偶解法的標(biāo)準(zhǔn)型45

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

M/G/1

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

1/

和方差

2設(shè)到達(dá)率為

，平均服務(wù)時(shí)長為h=1/

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

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

<1

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

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

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

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

，所以有48Ld，Lq

不但與

有關(guān)，而且與

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

，不需等待的概率為1

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

但在M/G/1中，平均剩余服務(wù)時(shí)間Tr

需要研究，它與顧客排隊(duì)等待的時(shí)間Wq

有關(guān)；顯然，Wq分為兩部分：(1)等待服務(wù)臺(tái)空出的平均時(shí)間，(2)排在隊(duì)中所有顧客的服務(wù)時(shí)間50對(duì)于定長分布，

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

=2，Tr=h對(duì)于k

階愛爾蘭分布，

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

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

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

i，波松流，各級(jí)顧客的平均服務(wù)時(shí)長都為hi，方差為

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

=

i

hi，

<1利用上節(jié)推導(dǎo)出的等待服務(wù)臺(tái)空出的時(shí)間T1，可知W1=T1/(1

1)，遞推得第k

級(jí)顧客的平均等待時(shí)間Wk52

k

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

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

1=2個(gè)/秒，定長服務(wù)h1=0.1秒/個(gè)；第二類顧客

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

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)先權(quán)，屬純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)非強(qiáng)占優(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秒 非強(qiáng)占優(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

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

個(gè)獨(dú)立并聯(lián)服務(wù)臺(tái)，各級(jí)顧客的平均服務(wù)時(shí)間都是h各級(jí)顧客到達(dá)率為

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

=

i，總業(yè)務(wù)量

=

i

h，

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

為全體顧客的平均等待時(shí)間，Lq

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

，而Ao23

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

和一個(gè)等效電路群n，使A

通過n

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

是A23

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

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

經(jīng)過通路n

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

o2)反解A

和n

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

加載到n+N

的通路上，給定呼損B，有5、計(jì)算各通路的呼損將最終呼損AoN按各通路的溢流分?jǐn)偫展嚼?求溢流通路(A,D)的電路數(shù)NAD，要求B0.011、計(jì)算(D,B)(D,C)的溢流Ao1,

2o1

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

2o3、計(jì)算等效流

A

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

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

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

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

表示邊

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

表示圖

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

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

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

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

是eij的端點(diǎn)(endvertex)，而eij

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

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

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

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

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

{v1

,v2

,…,vn

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

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

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

V1,E2

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

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

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

個(gè)節(jié)點(diǎn)的樹T的邊恰好為

n

1條，反之，任何有n

個(gè)節(jié)點(diǎn)，n

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

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

2)個(gè)節(jié)點(diǎn)，有nn

2個(gè)不同的標(biāo)記樹72

6.2.2

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

點(diǎn)，總是從最新標(biāo)記的點(diǎn)向下搜索，若從i

點(diǎn)無法向下標(biāo)記，即與i

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

i

1點(diǎn)繼續(xù)搜索，直到所有點(diǎn)都被標(biāo)記廣探法(breadthfirstsearch)：是一種有層級(jí)結(jié)構(gòu)的搜索，一般得到的是樹形圖736.2.3

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

最小生成樹的算法：Kruskal

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

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

算法基于下述定理定理3

指定圖中任一點(diǎn)vi，如果vj

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

V1，則V1和V2間權(quán)值最小的邊必定在某個(gè)最小生成樹中。746.2.3

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

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

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

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

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

766.3

最短路問題

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

dij

表示

vi

到vj

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

=

，若兩點(diǎn)之間是有向邊，則dji

=

；令dii

=0，s

表示始點(diǎn)，t

表示終點(diǎn)0、令始點(diǎn)Ts=0，并用框住，所有其它節(jié)點(diǎn)臨時(shí)標(biāo)記Tj=

；1、從vs

出發(fā)，對(duì)其相鄰節(jié)點(diǎn)vj1

進(jìn)行臨時(shí)標(biāo)記，有Tj1=ds,j1

；2、在所有臨時(shí)標(biāo)記中找出最小者，并用框住，設(shè)其為vr

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

出發(fā)，對(duì)其相鄰的臨時(shí)標(biāo)記節(jié)點(diǎn)進(jìn)行再標(biāo)記，設(shè)vj2

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

81510121511311378

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

表示vs

到vj

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

k

條邊，因此最多有n1

次迭代可以應(yīng)用于簡單有向圖和混合圖，在臨時(shí)標(biāo)記時(shí)，所謂相鄰必須是箭頭指向的節(jié)點(diǎn)；若第n1

次迭代后仍有節(jié)點(diǎn)的標(biāo)記為，則表明vs

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

到vt

的最短路，則當(dāng)vt

得到永久標(biāo)記算法就結(jié)束了；但算法復(fù)雜度是一樣的應(yīng)用Dijkstra算法n1

次，可以求所有點(diǎn)間的最短路vs

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

，

i。對(duì)一個(gè)固定點(diǎn)j，運(yùn)算dik=min{dik,dij+djk},

i,k

j,稱為三角運(yùn)算。(注意，這里允許i=k)定理依次對(duì)j=1,2,…,n執(zhí)行三角運(yùn)算，則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)路中存在負(fù)回路，則計(jì)算中，某些dii會(huì)小于0，此時(shí)應(yīng)中斷算法顯然，F(xiàn)loyd算法要進(jìn)行n(n-1)2次加法和比較如何回溯找出任兩點(diǎn)之間的最短路？在Floyd算法中設(shè)一伴隨矩陣E={eik}，eik

記錄了i

到

k

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

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

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

fij

cij平衡條件：

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

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

點(diǎn)，另一個(gè)包含t

點(diǎn)。一般包含s

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

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

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

到t

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

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

增廣過程：前向弧f

ij=fij+q,后向弧f

ij=fij

q

增廣后仍是可行流

87

最大流最小截的標(biāo)號(hào)法步驟第一步：標(biāo)號(hào)過程，找一條增廣鏈1、給源點(diǎn)s

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

相鄰的所有未標(biāo)號(hào)節(jié)點(diǎn)j，若(1)(i,j)是前向弧且飽和，則節(jié)點(diǎn)

j

不標(biāo)號(hào)；(2)(i,j)是前向弧且未飽和，則節(jié)點(diǎn)

j

標(biāo)號(hào)為[i+,q(j)]，表示從節(jié)點(diǎn)i

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

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

不標(biāo)號(hào)；(4)(j,i)是后向弧，若fji>0，則節(jié)點(diǎn)j

標(biāo)號(hào)為[i

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

流向

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

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

中，未獲標(biāo)號(hào)節(jié)點(diǎn)在V

中，V與V

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

獲得標(biāo)號(hào)，找到一條增廣鏈，由節(jié)點(diǎn)t

標(biāo)號(hào)回溯可找出該增廣鏈；到第二步88

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

的標(biāo)記值2、對(duì)增廣鏈中的后向弧，令f=f

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

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

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

,3)最小截集91

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

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

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

1

3

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

是傳輸鏈路i

j

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

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

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

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

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

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

1)!/2(n

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

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

為n

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

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

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

算法復(fù)雜度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次臨時(shí)標(biāo)記，永久標(biāo)記n

1次比較和賦值i=2n

2次臨時(shí)標(biāo)記，永久標(biāo)記n

2次比較和賦值i=k

n

k

次臨時(shí)標(biāo)記，永久標(biāo)記n

k

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

中各節(jié)點(diǎn)到V

的最小邊，minedge[i].cost記錄該邊的權(quán)值，minedge[i].vex記錄該邊V

中的頂點(diǎn)。若minedge[i].cost<0則表明i

點(diǎn)進(jìn)入集合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;{該算法復(fù)雜度約為5n(n-1)}104

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

之間有邊相連，但X

內(nèi)部和Y

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

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

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

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

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

，故i,j，滿足ai＋bj

cij在滿足ai＋bj＝cij

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

minj{sj}增廣等值子圖，

j，bj＝bj＋S

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

；

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

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

任務(wù)分配問題、匹配問題和TSP的關(guān)系三個(gè)問題都有一個(gè)n

n

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

6.7

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

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

代表vi

與vj

間的最短距離，ars

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

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

h1邊上對(duì)應(yīng)h

的一點(diǎn)到vj

的最短距離為

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

ars+drj,(1

h)

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

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

是邊(r,s)上指定的百分位點(diǎn)，另一邊為(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é)點(diǎn)—節(jié)點(diǎn)距離為基礎(chǔ)，大中取小(maxmin)一般中心：以節(jié)點(diǎn)—邊距離為基礎(chǔ)，大中取小絕對(duì)中心：以點(diǎn)—節(jié)點(diǎn)距離為基礎(chǔ)，大中取小一般絕對(duì)中心：以點(diǎn)—邊距離為基礎(chǔ)，大中取小左圖的中心是v1；而三個(gè)節(jié)點(diǎn)都是一般中心類似也有四種中位點(diǎn)：中位點(diǎn)一般中位點(diǎn)絕對(duì)中位點(diǎn)一般絕對(duì)中位點(diǎn)115

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

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

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

與服務(wù)系統(tǒng)性能相關(guān)的特性7.1.2輸入過程和服務(wù)時(shí)間顧客單個(gè)到達(dá)或成批到達(dá)顧客到達(dá)時(shí)間間隔的分布和服務(wù)時(shí)間的分布顧客源是有限的還是無限