通信工程 - 排隊(duì)模型與最短路徑

第7章排隊(duì)模型與最短路徑

第一部分排隊(duì)模型一、排隊(duì)模型的特征及排隊(duì)論排隊(duì)論(QueuingTheory)，又稱隨機(jī)服務(wù)系統(tǒng)理論(RandomServiceSystemTheory),是一門研究擁擠現(xiàn)象(排隊(duì)、等待)的科學(xué)。具體地說，它是在研究各種排隊(duì)系統(tǒng)概率規(guī)律性的基礎(chǔ)上，解決相應(yīng)排隊(duì)系統(tǒng)的最優(yōu)設(shè)計和最優(yōu)控制問題。排隊(duì)是我們在日常生活和生產(chǎn)中經(jīng)常遇到的現(xiàn)象。例如，上、下班搭乘公共汽車；顧客到商店購買物品；病員到醫(yī)院看?。宦每偷绞燮碧庂徺I車票；學(xué)生去食堂就餐等就常常出現(xiàn)排隊(duì)和等待現(xiàn)象。除了上述有形的排隊(duì)之外，還有大量的所謂“無形”排隊(duì)現(xiàn)象，如幾個顧客打電話到出租汽車站要求派車，如果出租汽車站無足夠車輛、則部分顧客只得在各自的要車處等待，他們分散在不同地方，卻形成了一個無形隊(duì)列在等待派車。排隊(duì)的不一定是人，也可以是物，或者數(shù)據(jù)。例如，通訊衛(wèi)星與地面若干待傳遞的信息；生產(chǎn)線上的原料、半成品等待加工；因故障停止運(yùn)轉(zhuǎn)的機(jī)器等待工人修理；碼頭的船只等待裝卸貨物；要降落的飛機(jī)因跑道不空而在空中盤旋等等。顯然，上述各種問題雖互不相同，但卻都有要求得到某種服務(wù)的人或物和提供服務(wù)的人或機(jī)構(gòu)。排隊(duì)論里把要求服務(wù)的對象統(tǒng)稱為“顧客”,而把提供服務(wù)的人或機(jī)構(gòu)稱為“服務(wù)員”或“服務(wù)機(jī)構(gòu)”。實(shí)際的排隊(duì)系統(tǒng)可以千差萬別，但都可以一般地描述如下：顧客為了得到某種服務(wù)而到達(dá)系統(tǒng)、若不能立即獲得服務(wù)而又允許排隊(duì)等待，則加入等待隊(duì)伍，待獲得服務(wù)后離開系統(tǒng)，見圖7-1至7-4圖7-1單服務(wù)臺排隊(duì)系統(tǒng)圖7-2單隊(duì)列——S個服務(wù)臺并聯(lián)的排隊(duì)系統(tǒng)圖7-3S個隊(duì)列——S個服務(wù)臺的并聯(lián)排隊(duì)系統(tǒng)圖7-4單隊(duì)——多個服務(wù)臺的串聯(lián)排隊(duì)系統(tǒng)類似地還可畫出許多其他形式的排隊(duì)系統(tǒng)，如串并混聯(lián)的系統(tǒng)，網(wǎng)絡(luò)排隊(duì)系統(tǒng)等盡管各種排隊(duì)系統(tǒng)的具體形式不同，但都可以由圖7-5加以描述圖7-5隨機(jī)服務(wù)系統(tǒng)通常稱上圖表示的系統(tǒng)為一隨機(jī)聚散服務(wù)系統(tǒng)，任一排隊(duì)系統(tǒng)都是一個隨機(jī)聚散服務(wù)系統(tǒng)。這里，“聚”表示顧客的到達(dá)，“散”表示顧客的離去。所謂隨機(jī)性則是排隊(duì)系統(tǒng)的一個普遍特點(diǎn)，是指顧客的到達(dá)情況(如相繼到達(dá)時間間隔)與每個顧客接受服務(wù)的時間往往是事先無法確切知道的，或者說是隨機(jī)的。一般來說，排隊(duì)論所研究的排隊(duì)系統(tǒng)中，顧客到來的時刻和服務(wù)臺提供服務(wù)的時間長短都是隨機(jī)的，因此這樣的服務(wù)系統(tǒng)被稱為隨機(jī)服務(wù)系統(tǒng)。排隊(duì)系統(tǒng)的符號表示:

一個排隊(duì)系統(tǒng)的特征可以用五個參數(shù)表示，形式為：A／B／C／D／E其中A––顧客到達(dá)的概率分布，可取M、D、G

、Ek等；B––服務(wù)時間的概率分布，可取M、D、G

、Ek等；C––服務(wù)臺個數(shù)，取正整數(shù)；D––排隊(duì)系統(tǒng)的最大容量，可取正整數(shù)或

；E––顧客源的最大容量，可取正整數(shù)或

。例如M/M/1/

表示顧客到達(dá)過程服從泊松分布，服務(wù)時間服從負(fù)指數(shù)分布，一個服務(wù)臺，排隊(duì)的長度無限制和顧客的來源無限制。排隊(duì)模型在排隊(duì)論中，為了完整地描述排隊(duì)模型，常采用以下描述格式：A/B/C/（：）D/E/F

泊松過程

滿足以下條件的隨機(jī)過程叫泊松過程：（1）在不相重疊的時間段內(nèi)事件的出現(xiàn)是互相獨(dú)立的；（2）任何時間段內(nèi)所發(fā)生事件次數(shù)的分布只與本時間段的長度有關(guān)，與時間段何時開始無關(guān)；（3）在任意小的時間段

t內(nèi)事件出現(xiàn)一次的概率為s

t（s為一常數(shù)，它表示每單位時間內(nèi)平均出現(xiàn)的次數(shù)）；（4）在

t時間段內(nèi)事件不出現(xiàn)的概率為（1－s

t）．即在

t

時間內(nèi)為兩點(diǎn)分布，要么出現(xiàn)一次，要么不出現(xiàn)，不存在一次以上出現(xiàn)的情況。小結(jié)排隊(duì)系統(tǒng)又稱隨機(jī)服務(wù)系統(tǒng)①

有請求服務(wù)的人或物；②有為顧客服務(wù)的人或物；顧客到達(dá)時間與接受服務(wù)時間是隨機(jī)的。結(jié)構(gòu)：

顧客到達(dá)-----

排隊(duì)------

服務(wù)機(jī)構(gòu)服務(wù)------

顧客離去數(shù)據(jù)到達(dá)---------------網(wǎng)絡(luò)系統(tǒng)-----

-----

-----

-----數(shù)據(jù)傳出第二部分最短路徑問題

最短（通）路問題是最重要的優(yōu)化問題之一，例如各種管道的鋪設(shè)、線路的安排、廠區(qū)的布局、設(shè)備的更新及運(yùn)輸網(wǎng)絡(luò)的最小費(fèi)用流等。（最短距離、費(fèi)時最少、費(fèi)用最?。６x（權(quán)、賦權(quán)圖）：圖7-4的每一條邊，可賦與一個實(shí)數(shù)，稱為邊的權(quán)。圖7-4連同它邊上的權(quán)稱為賦權(quán)圖。權(quán)可以表示鐵路長度，通訊網(wǎng)絡(luò)的造價，友誼圖中的友誼深度，網(wǎng)絡(luò)中表示耗時等。109631702115132861722291511914397463109631702115132861722291511914397463一、最短路徑問題的算法109631702115132861722291511914397463求網(wǎng)絡(luò)上的一點(diǎn)到其它點(diǎn)

的最短路Dijkstra算法圖示109631702115132861722291511914397463Dijkstra標(biāo)號算法這是解決網(wǎng)絡(luò)中某一點(diǎn)到其它點(diǎn)的最短路問題時目前認(rèn)為的最好方法。在這個問題中我們討論的是從網(wǎng)絡(luò)中的點(diǎn)1到其它各點(diǎn)的最短路。51275634255273135710①從點(diǎn)1出發(fā)，因L11=0，在點(diǎn)1處標(biāo)記

5127563425527313571051275634255273135710②從已標(biāo)號的點(diǎn)出發(fā)，找與這些相鄰點(diǎn)最小權(quán)數(shù)（距離）者，找到之后：標(biāo)號；邊變紅。51275634255273135710251275634255273135710③從已標(biāo)號的點(diǎn)出發(fā)，找與這些相鄰點(diǎn)最小權(quán)數(shù)（距離）者，找到之后：標(biāo)號；邊變紅。251275634255273135710④重復(fù)上述步驟，直至全部的點(diǎn)都標(biāo)完。2351275634255273135710④重復(fù)上述步驟，直至全部的點(diǎn)都標(biāo)完。234512756342552731357102347512756342552731357102347851275634255273135710234785127563425527313571023478135127563425527313571023478137.3

最短路問題

7.3.1狄克斯特拉算法(Dijkstraalgorithm,1959)計算兩節(jié)點(diǎn)之間或一個節(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)臨時標(biāo)記Tj=

；1、從vs

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

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

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

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

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

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

815101215113113

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

表示vs

到vj

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

k

條邊，因此最多有n1

次迭代可以應(yīng)用