第7章排隊模型與最短路徑

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

一個排隊系統的特征可以用五個參數表示，形式為：A／B／C／D／E其中A––顧客到達的概率分布，可取M、D、G

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

、Ek等；C––服務臺個數，取正整數；D––排隊系統的最大容量，可取正整數或

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

。例如M/M/1/

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

泊松過程

滿足以下條件的隨機過程叫泊松過程：（1）在不相重疊的時間段內事件的出現是互相獨立的；（2）任何時間段內所發生事件次數的分布只與本時間段的長度有關，與時間段何時開始無關；（3）在任意小的時間段

t內事件出現一次的概率為s

t（s為一常數，它表示每單位時間內平均出現的次數）；（4）在

t時間段內事件不出現的概率為（1－s

t）．即在

t

時間內為兩點分布，要么出現一次，要么不出現，不存在一次以上出現的情況。小結排隊系統又稱隨機服務系統①

有請求服務的人或物；②有為顧客服務的人或物；顧客到達時間與接受服務時間是隨機的。結構：

顧客到達-----

排隊------

服務機構服務------

顧客離去數據到達---------------網絡系統-----

-----

-----

-----數據傳出第二部分最短路徑問題

最短（通）路問題是最重要的優化問題之一，例如各種管道的鋪設、線路的安排、廠區的布局、設備的更新及運輸網絡的最小費用流等。（最短距離、費時最少、費用最省）。定義（權、賦權圖）：圖7-4的每一條邊，可賦與一個實數，稱為邊的權。圖7-4連同它邊上的權稱為賦權圖。權可以表示鐵路長度，通訊網絡的造價，友誼圖中的友誼深度，網絡中表示耗時等。109631702115132861722291511914397463109631702115132861722291511914397463一、最短路徑問題的算法109631702115132861722291511914397463求網絡上的一點到其它點

的最短路Dijkstra算法圖示109631702115132861722291511914397463Dijkstra標號算法這是解決網絡中某一點到其它點的最短路問題時目前認為的最好方法。在這個問題中我們討論的是從網絡中的點1到其它各點的最短路。51275634255273135710①從點1出發，因L11=0，在點1處標記

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

最短路問題

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

dij

表示

vi

到vj

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

=

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

=

；令dii

=0，s

表示始點，t

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

；1、從vs

出發，對其相鄰節點vj1

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

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

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

出發，對其相鄰的臨時標記節點進行再標記，設vj2

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

815101215113113

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

表示vs

到vj

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

k

條邊，因此最多有n1

次迭代可以應用