第4章-離散事件仿真基礎(chǔ)

第4章離散事件仿真基礎(chǔ)離散事件系統(tǒng)通常是指受事件驅(qū)動(dòng)、系統(tǒng)狀態(tài)跳躍式變化的動(dòng)態(tài)系統(tǒng)，系統(tǒng)的遷移發(fā)生在一串離散事件點(diǎn)上。離散事件系統(tǒng)和連續(xù)系統(tǒng)在性質(zhì)上是完全不同的，這類系統(tǒng)中的狀態(tài)在時(shí)間上和空間上都是離散的。這種系統(tǒng)往往是隨機(jī)的，具有復(fù)雜的變化關(guān)系，難于用常規(guī)的微分方程、差分方程等方程模型來描述，一般只能用流程圖或網(wǎng)絡(luò)圖來描述。離散事件系統(tǒng)與模型離散事件仿真排隊(duì)系統(tǒng)的仿真隨機(jī)數(shù)和隨機(jī)變量的生成一、離散事件系統(tǒng)與模型概述描述離散事件系統(tǒng)的基本要素離散事件系統(tǒng)模型的建立（一）概述離散事件系統(tǒng)大量地存在于我們周圍，如：超級(jí)市場(chǎng)管理系統(tǒng)、銀行服務(wù)系統(tǒng)、公交管理系統(tǒng)、車間加工調(diào)度系統(tǒng)等，其中到大市場(chǎng)和銀行的顧客、上下車的旅客、等待加工的工件，都是影響系統(tǒng)變化的“事件”。事件是在離散時(shí)刻隨機(jī)發(fā)生的，利用仿真技術(shù)對(duì)這些系統(tǒng)進(jìn)行研究分析，可以了解它們的動(dòng)態(tài)運(yùn)行規(guī)律，從而幫助人們做出是否需要增加新的市場(chǎng)和銀行的決定，可以幫助人們合理地調(diào)度車輛和安排工序。（二）描述離散事件系統(tǒng)的基本要素[例4-1]一個(gè)單人理發(fā)館系統(tǒng)，理發(fā)館在工作時(shí)間中，有且僅有一個(gè)工作人員為客人服務(wù)，營(yíng)業(yè)時(shí)間為9:00-19:00，顧客到達(dá)時(shí)間一般是隨機(jī)的，而且是獨(dú)立的，每位顧客接受服務(wù)的時(shí)間長(zhǎng)短也是隨機(jī)的。描述該系統(tǒng)的狀態(tài)是服務(wù)臺(tái)的狀態(tài)(忙或閑)、顧客排隊(duì)等待的隊(duì)長(zhǎng)，等等。顧客到達(dá)排隊(duì)等待理發(fā)員忙否服務(wù)服務(wù)完畢(顧客離去)置理發(fā)員閑忙否（1）實(shí)體（Entity）實(shí)體是描述系統(tǒng)的三個(gè)基本要素之一。連續(xù)系統(tǒng)一樣，離散事件也是由實(shí)體組成的。在離散事件系統(tǒng)中的實(shí)體可以分為兩大類：臨時(shí)實(shí)體和永久實(shí)體。臨時(shí)實(shí)體:在系統(tǒng)中只存在一段時(shí)間的實(shí)體稱為臨時(shí)實(shí)體。這類實(shí)體是由系統(tǒng)的外部到達(dá)并進(jìn)人系統(tǒng)的，然后通過系統(tǒng)，并最終離開系統(tǒng)。例4-1中的顧客顯然是臨時(shí)實(shí)體。永久性地駐留在系統(tǒng)中的實(shí)體稱為永久實(shí)體。例4-1中的服務(wù)員就是永久實(shí)體。（2）事件（Event）引起系統(tǒng)狀態(tài)變化的行為稱為事件。它是在某一時(shí)間點(diǎn)的瞬時(shí)行為，從某種意義上來說，系統(tǒng)是由事件來驅(qū)動(dòng)的。事件不僅用來協(xié)調(diào)兩個(gè)實(shí)體之間的同步活動(dòng)，還用于各個(gè)實(shí)體之間傳遞信息。例如，在例4-1中就可以把“顧客到達(dá)”稱為一類事件，因?yàn)檎怯捎陬櫩偷牡竭_(dá)，系統(tǒng)的狀態(tài)——服務(wù)員的“狀態(tài)”才能由閑變忙(如果無人排隊(duì)的話)，或者使系統(tǒng)的狀態(tài)——排隊(duì)的顧客人數(shù)發(fā)生變化(隊(duì)列人數(shù)加1)。一個(gè)顧客接受服務(wù)完畢后離開系統(tǒng)，也可以定義為一類事件，因?yàn)榉?wù)員由忙變?yōu)殚e，或者等待的隊(duì)列發(fā)生變化。（3）活動(dòng)（activity）離散事件中的活動(dòng)，通常用于表示兩個(gè)可以區(qū)分的事件之間的過程，它標(biāo)志著系統(tǒng)狀態(tài)之間的轉(zhuǎn)移。把實(shí)體所做的、或?qū)?shí)體施加的事件稱為活動(dòng)，它是實(shí)體在兩個(gè)事件之間保持某一個(gè)狀態(tài)的持續(xù)過程。在例4-1中，顧客的到達(dá)事件與顧客的開始接受服務(wù)事件之間的過程可以稱為一個(gè)活動(dòng)，該活動(dòng)使系統(tǒng)的狀態(tài)(隊(duì)長(zhǎng))發(fā)生變化，從顧客開始接受服務(wù)到對(duì)該顧客服務(wù)完畢后離去的過程也可以被看成是一個(gè)活動(dòng)，它可能使隊(duì)長(zhǎng)減1或使服務(wù)員由忙轉(zhuǎn)閑。（4）進(jìn)程（process）進(jìn)程由若干個(gè)事件及若干個(gè)活動(dòng)組成，它描述了事件及活動(dòng)之間的相互邏輯關(guān)系及時(shí)序關(guān)系。例4-1中的“顧客到達(dá)系統(tǒng)--排隊(duì)--開始接受服務(wù)一服務(wù)完畢的過程”就構(gòu)成了一個(gè)進(jìn)程。[例4-2]在一個(gè)有較大水位落差河段上的船閘運(yùn)行系統(tǒng)，從上游新來的船只到達(dá)船閘或當(dāng)原有的船只完成過閘運(yùn)行時(shí)，系統(tǒng)的狀態(tài)就發(fā)生了變化，我們把船只到達(dá)、過閘完畢這一類引起系統(tǒng)狀態(tài)變化的行為稱為事件，當(dāng)船只尚在船閘內(nèi)(忙態(tài))而又有新的船只到達(dá)時(shí)，則新到的船只就進(jìn)入到等侯的隊(duì)列(排隊(duì)的隊(duì)長(zhǎng)加1)，把排隊(duì)過程，船只過閘過程稱為活動(dòng)，把船只到達(dá)

進(jìn)入排隊(duì)隊(duì)列一開閘門

過閘服務(wù)

出閘門這三個(gè)事件和兩項(xiàng)活動(dòng)稱為過閘進(jìn)程。船只過閘服務(wù)進(jìn)程排隊(duì)活動(dòng)過閘服務(wù)活動(dòng)船只到達(dá)事件過閘服務(wù)開始事件過閘服務(wù)結(jié)束事件（5）仿真鐘(simulationclock)仿真鐘用于表示仿真時(shí)間的變化，在連續(xù)系統(tǒng)中，仿真時(shí)間的變化基于仿真步長(zhǎng)的確定，可以是定步長(zhǎng)，也可以是變步長(zhǎng)。在離散事件動(dòng)態(tài)系統(tǒng)中，引起狀態(tài)變化的事件的發(fā)生時(shí)間是隨機(jī)的，因而仿真時(shí)鐘的推進(jìn)步長(zhǎng)完全是隨機(jī)的，而且，在兩個(gè)相鄰發(fā)生的事件之間系統(tǒng)狀態(tài)不會(huì)發(fā)生任何變化，因而，仿真鐘可以跨過這些“不活動(dòng)”周期，從一個(gè)事件發(fā)生時(shí)刻直接推進(jìn)到下一個(gè)事件發(fā)生時(shí)刻，仿真鐘的推進(jìn)呈現(xiàn)跳躍性，推進(jìn)的速度具有隨機(jī)性，可見，仿真模型中時(shí)間控制部件是必不可少的，以便按一定的規(guī)律來控制仿真鐘的推進(jìn)。（6）統(tǒng)計(jì)計(jì)數(shù)器（stat.counter）連續(xù)系統(tǒng)仿真的目的是要得到狀態(tài)變量的動(dòng)態(tài)變化過程并由此分析系統(tǒng)的性能。離散事件系統(tǒng)的狀態(tài)變量隨事件的不斷發(fā)生也呈現(xiàn)出動(dòng)態(tài)變化過程，但仿真的主要目的不是要得到這些狀態(tài)變量是如何變化的。因?yàn)檫@種變化是隨機(jī)的，所以某一次運(yùn)行得到的狀態(tài)變化過程只不過是隨機(jī)過程的一次取樣，因而，如果進(jìn)行另一次獨(dú)立的仿真運(yùn)行，則所得到的變化過程完全是另外一種情況，所以它們只有在統(tǒng)計(jì)意義下才有參考價(jià)值。在例4-1中，由于顧客到達(dá)的時(shí)間間隔具有隨機(jī)性，服務(wù)員為每位為顧客服務(wù)的時(shí)間長(zhǎng)度也是隨機(jī)的，因而，在某一時(shí)刻，顧客排隊(duì)的隊(duì)長(zhǎng)或服務(wù)員的忙、閑情況是完全不確定的。從系統(tǒng)分析的角度看，感興趣的可能是系統(tǒng)的平均隊(duì)長(zhǎng)，顧客的平均等待時(shí)間，或者是服務(wù)員的利用率等。在仿真模型中，需要有一個(gè)統(tǒng)計(jì)計(jì)數(shù)器，以便統(tǒng)計(jì)系統(tǒng)中的有關(guān)變量（三）離散事件系統(tǒng)模型的建立離散事件系統(tǒng)研究和仿真中最基本的問題就是系統(tǒng)的建模。那么采用什么方式來概括和抽象化分析處理這些離散事件呢?20世紀(jì)自80年代初期，美國(guó)哈佛大學(xué)著名的學(xué)者Y.C.Ho教授倡導(dǎo)對(duì)離散事件動(dòng)態(tài)系統(tǒng)(DistributedEventDynamicSystem,DEDS)理論進(jìn)行研究以來，這個(gè)問題受到了足夠的重視，許多學(xué)者圍繞著這個(gè)問題從不同的層次或用不同的數(shù)學(xué)工具進(jìn)行了描述，形成了許多的方法體系，并出現(xiàn)了多種形式的DEDS模型設(shè)計(jì)方法。例如，對(duì)所考慮對(duì)象演變過程的分析，根據(jù)事件發(fā)生的時(shí)間是否有必要納入研究范圍，可以劃分為：①不帶時(shí)標(biāo)的DEDS模型：有限狀態(tài)自動(dòng)機(jī)模型、Peri網(wǎng)絡(luò)模型、過程代數(shù)模型、時(shí)序邏輯模型等。②帶時(shí)標(biāo)的DEDS模型：賦時(shí)Petrt網(wǎng)絡(luò)模型、TIM／RTIL模型、雙子代數(shù)模型、排隊(duì)網(wǎng)絡(luò)模型、Markov鏈與CSMP模型等。離散事件的建模型步驟（1）明確仿真目的（2）正確描述系統(tǒng)組成成分：指對(duì)描述系統(tǒng)仿真目的有意義的實(shí)體，這些實(shí)體的行為往往是隨機(jī)分布的。描述變量和參數(shù)：描述變量和參數(shù)是指系統(tǒng)各實(shí)體的屬性。描述變量包括內(nèi)部變量和外部變量，除了輸入/輸出變量外，其余均為狀態(tài)變量。參數(shù)可以在仿真前由用戶設(shè)置或在仿真過程當(dāng)中根據(jù)用戶的命令加以改變。相互關(guān)系：相互關(guān)系規(guī)定了系統(tǒng)中不同變量的相互關(guān)聯(lián)，是指影響系統(tǒng)變化的各實(shí)體、變量和參數(shù)之間的連接關(guān)系和作用關(guān)系。相互關(guān)系大部分反映在各成分的活動(dòng)之中，而活動(dòng)又由事件所引發(fā)，所以弄清事件、活動(dòng)的關(guān)系是系統(tǒng)描述中極為重要的。（3）仿真模型的建立（4）輸出函數(shù)的確定船只到達(dá)排隊(duì)等候船閘服務(wù)船只離開置船閘為閑查詢閘閑？NY開始置仿真開始時(shí)間和結(jié)束時(shí)間船只到過時(shí)間間隔70min系統(tǒng)流程大于結(jié)束時(shí)間？結(jié)束NY船閘服務(wù)系統(tǒng)流程圖船閘服務(wù)系統(tǒng)仿真模型圖二、離散事件仿真離散事件系統(tǒng)的仿真模型離散事件系統(tǒng)仿真策略離散事件仿真研究的一般步驟（一）離散事件系統(tǒng)的仿真模型1．仿真程序的主要成分采用步長(zhǎng)法仿真的程序主要由以下部分組成：①仿真時(shí)鐘：提供仿真時(shí)間的當(dāng)前值；②事件表：由策劃和事件調(diào)度生成事件名稱、時(shí)間的二維表，即有關(guān)未來事件的表；③系統(tǒng)的狀態(tài)變量：描述系統(tǒng)狀態(tài)的變量；④初始化子程序：用于模型初始化；⑤事件子程序：每一類事件的服務(wù)子程序；⑥調(diào)度子程序：將未來事件插入事件表中的子程序；⑦時(shí)鐘推進(jìn)子程序：根據(jù)事件表決定下次(最早發(fā)生的)事件，然后將仿真事件推進(jìn)到事件發(fā)生時(shí)刻；⑧隨機(jī)數(shù)產(chǎn)生子程序：產(chǎn)生給定分布的隨機(jī)數(shù)的子程序；⑨輸出函數(shù)子程序：用于系統(tǒng)性能分析的子程序；⑩統(tǒng)計(jì)計(jì)數(shù)器：用來存放與系統(tǒng)性能分析有關(guān)的統(tǒng)計(jì)數(shù)據(jù)的各個(gè)變量值；⑩主程序：調(diào)用上述各子程序并完成仿真任務(wù)全過程。2．仿真程序的流程管理仿真流程管理(即仿真調(diào)度)是仿真建模的核心，在此主要討論事件進(jìn)程管理、同時(shí)事件管理等。這個(gè)過程主要用到了仿真時(shí)鐘和事件表兩個(gè)概念。（1）仿真時(shí)鐘：注意與仿真機(jī)時(shí)之間的區(qū)別。時(shí)間步長(zhǎng)法：在進(jìn)行系統(tǒng)仿真的同時(shí)，可以把整個(gè)仿真過程分為許多相等的時(shí)間間隔，時(shí)間步長(zhǎng)的長(zhǎng)度可根據(jù)實(shí)際問題分別取秒、分、小時(shí)等，程序中按此步長(zhǎng)前進(jìn)的時(shí)鐘就是仿真時(shí)鐘。選取系統(tǒng)的一個(gè)初始狀態(tài)作為仿真時(shí)鐘的零點(diǎn)，仿真時(shí)鐘每步進(jìn)一次，就對(duì)系統(tǒng)的所有實(shí)體、屬性和活動(dòng)進(jìn)行一次全面的掃描考察，按照預(yù)定的計(jì)劃和目標(biāo)進(jìn)行分析、計(jì)算和記錄系統(tǒng)狀態(tài)的變化，這個(gè)過程一直進(jìn)行到仿真時(shí)鐘結(jié)束為止。事件步長(zhǎng)法：事件步長(zhǎng)法是以事件發(fā)生的時(shí)間為增量，按照時(shí)間的進(jìn)展，一步一步地對(duì)系統(tǒng)的行為進(jìn)行仿真，直到預(yù)定的仿真時(shí)間結(jié)束為止。事件步長(zhǎng)法與時(shí)間步長(zhǎng)法的主要區(qū)別：①事件步長(zhǎng)法與時(shí)間步長(zhǎng)法都是以時(shí)間為增量來考察系統(tǒng)狀態(tài)的變化的。但在時(shí)間步長(zhǎng)法中，仿真時(shí)鐘以等步長(zhǎng)前進(jìn)，而在事件步長(zhǎng)法仿真中，仿真時(shí)鐘的步長(zhǎng)取決于事件之間的時(shí)間間隔。②時(shí)間步長(zhǎng)法在一個(gè)步長(zhǎng)內(nèi)，認(rèn)為系統(tǒng)所處的狀態(tài)相同，因而所選的步長(zhǎng)的大小將影響仿真的精度。而在事件步長(zhǎng)法中，每個(gè)事件的發(fā)生均有確切的時(shí)刻，不需要人為地選取步長(zhǎng)，步長(zhǎng)的大小對(duì)仿真的精度影響較小。③時(shí)間步長(zhǎng)法每步進(jìn)一個(gè)步長(zhǎng)就要對(duì)整個(gè)系統(tǒng)進(jìn)行一次全面的考察，即使?fàn)顟B(tài)沒有發(fā)生變化時(shí)也要進(jìn)行掃描。而事件步長(zhǎng)法只是在某一事件發(fā)生時(shí)才進(jìn)行掃描。無論采用哪種方法仿真，在仿真過程中每一個(gè)時(shí)間點(diǎn)上總是要判斷相比較事件是否出現(xiàn)，因此，一般地講，當(dāng)判斷比較的數(shù)目較大或事件變化呈周期性特點(diǎn)時(shí)，用時(shí)間步長(zhǎng)法可以節(jié)省用機(jī)時(shí)間，而當(dāng)相繼兩個(gè)事件出現(xiàn)的平均間隔較長(zhǎng)時(shí)，更適合于采用事件步長(zhǎng)法。（2）事件表：應(yīng)用于變步長(zhǎng)法仿真。（3）同時(shí)事件管理同類同時(shí)事件的管理：發(fā)生在同一時(shí)刻且隸屬于同一類型的幾個(gè)事件叫同類同時(shí)事件。同類同時(shí)事件的發(fā)生會(huì)導(dǎo)致模型的下一狀態(tài)出現(xiàn)多種可能值，即可能出現(xiàn)幾種排隊(duì)順序。為此，我們需要先定好條件，以使?fàn)顟B(tài)取值成為惟一，也就是要規(guī)定一種排隊(duì)規(guī)則來管理這些同類同時(shí)事件。例如，先進(jìn)先出〔或先到先服務(wù))規(guī)則、后進(jìn)先出(或后到先服務(wù))規(guī)則、隨機(jī)規(guī)則以及優(yōu)先服務(wù)規(guī)則?；旌贤瑫r(shí)事件的管理：發(fā)生在同一時(shí)刻但不屬于同一類型的幾個(gè)事件叫混合同時(shí)事件。確定這些混合同時(shí)事件所造成的狀態(tài)的變化，通常有一步法與解結(jié)法。一步法就是直接確定混合同時(shí)事件所形成的結(jié)果狀態(tài)；解結(jié)法卻是把幾個(gè)同時(shí)事件分解成多個(gè)單獨(dú)事件的序列進(jìn)行處理。對(duì)于簡(jiǎn)單的情況，一步法與解結(jié)法將會(huì)得到相同的結(jié)果。但一步法不易寫成通用的形式，且流程管理中的通道選擇較復(fù)雜；而解結(jié)法通用于各種仿真語言中，是因?yàn)槭褂迷摲椒〞r(shí)模型簡(jiǎn)單，便于寫成通式。（二）離散事件系統(tǒng)仿真策略因?yàn)殡x散事件模型的特點(diǎn)，實(shí)體活動(dòng)、進(jìn)程都是以事件為基礎(chǔ)構(gòu)成的，所以從事件、活動(dòng)、進(jìn)程三個(gè)層次來組織事件構(gòu)成了處理離散事件模型的三種典型的處理方法：事件調(diào)度法、活動(dòng)掃描法和進(jìn)程交互法，相應(yīng)地要采用三種不同的仿真策略，在復(fù)雜系統(tǒng)仿真中，按進(jìn)程來組織事件可以使眾多的事件條理清晰，因而成為最通用的仿真方法。1．事件調(diào)度法（EventScheduling）這種方法有一個(gè)時(shí)間控制程序，從事件表中選擇具有最早發(fā)生時(shí)間的事件，并將仿真鐘修改到該事件發(fā)生的時(shí)刻，再調(diào)用與該事件相應(yīng)的程序模塊，對(duì)事件進(jìn)行處理，該事件處理完畢后，返回時(shí)間控制程序。這樣，事件的選擇與處理不斷地交替進(jìn)行，直到仿真終止的程序事件發(fā)生為止。在這種方法中，任何條件的測(cè)試，均在相應(yīng)的事件模塊中進(jìn)行，這顯然是一種面向事件的仿真方法。2．活動(dòng)掃描法（ActivityScanning）在這類仿真中，系統(tǒng)由部件(相應(yīng)于實(shí)體)組成，而部件包含著活動(dòng)，該活動(dòng)是否發(fā)生，視規(guī)定的條件是否滿足而定，因而有一個(gè)專門的模塊來確定激活條件。若條件滿足，則激活相應(yīng)部件的活動(dòng)模塊。時(shí)間控制程序較之其他的條件具有更高的優(yōu)先級(jí)，即在判斷激活條件時(shí)首先判斷該活動(dòng)發(fā)生的時(shí)間是否滿足，然后再判斷其他的條件。若所有的條件都滿足，則執(zhí)行該部件的活動(dòng)模塊。然后再對(duì)其他部件進(jìn)行掃描，對(duì)所有部件掃描一遍后，又按同樣順序進(jìn)行循環(huán)掃描，直到仿真終止。3．進(jìn)程交互法(ProcessInteraction)這種方法綜合了事件調(diào)度法和活動(dòng)掃描法的特點(diǎn)，采用兩張事件表，即當(dāng)前事件表(CEL)和將來事件表(FEL)。它首先按一定的分布產(chǎn)生到達(dá)實(shí)體并置于FEL中，實(shí)體進(jìn)入排隊(duì)等待；然后對(duì)CEL進(jìn)行活動(dòng)掃描，判斷各種條件是否滿足；再將滿足條件的活動(dòng)進(jìn)行處理，仿真鐘推進(jìn)到服務(wù)結(jié)束并將相應(yīng)的實(shí)體從系統(tǒng)中清除；最后將FEL中最早發(fā)生的當(dāng)前事件的實(shí)體移到CEL中，繼續(xù)推進(jìn)仿真時(shí)鐘，對(duì)CEL進(jìn)行活動(dòng)掃描，直到仿真結(jié)束。（三）離散事件仿真研究的一般步驟①系統(tǒng)建模及模型改進(jìn)；②確定仿真算法；③建立仿真模型；④設(shè)計(jì)仿真程序，運(yùn)行仿真程序，仿真模型的檢驗(yàn)與改進(jìn)⑤仿真結(jié)果輸出處理；⑥仿真分析。三、排隊(duì)系統(tǒng)的仿真排隊(duì)問題實(shí)質(zhì)上是一個(gè)平衡等待時(shí)間和服務(wù)臺(tái)空閑時(shí)間的問題，也就是如何確定一個(gè)排隊(duì)系統(tǒng)，使實(shí)體(指等待服務(wù)的人、物體或信息)和服務(wù)臺(tái)兩者都有利，排隊(duì)論就是解決這類問題的一門學(xué)科，它又稱隨機(jī)服務(wù)理論，因?yàn)?，?shí)體到達(dá)和接受服務(wù)的時(shí)間常常是某種概率分布的隨機(jī)變量。排隊(duì)論的基本概念到達(dá)時(shí)間間隔和服務(wù)時(shí)間的分布排隊(duì)系統(tǒng)分析（一）排隊(duì)論的基本概念1．排隊(duì)系統(tǒng)的組成一般的排隊(duì)系統(tǒng)都由三個(gè)基本部分組成：①到達(dá)模式--指動(dòng)態(tài)實(shí)體按什么樣的規(guī)則到達(dá)，描寫實(shí)體到達(dá)的統(tǒng)計(jì)特性。②服務(wù)機(jī)構(gòu)--指同一時(shí)間有多少服務(wù)臺(tái)可以接納動(dòng)態(tài)實(shí)體，它們的服務(wù)需要多少時(shí)間，服從什么樣的分布。③服務(wù)規(guī)則--指對(duì)下一個(gè)實(shí)體服務(wù)的選擇原則。動(dòng)態(tài)實(shí)體排隊(duì)服務(wù)機(jī)構(gòu)到達(dá)接受服務(wù)排隊(duì)系統(tǒng)的基本結(jié)構(gòu)2．到達(dá)模式（1）平均到達(dá)時(shí)間間隔Ta假設(shè)在仿真總時(shí)間T內(nèi)一共到達(dá)了n個(gè)“顧客”，則平均到達(dá)時(shí)間間隔定為Ta=T/n（2）平均到達(dá)速率

定義單位時(shí)間內(nèi)到達(dá)的“顧客”數(shù)，為平均到達(dá)速即

＝1/Ta＝n/T（3）到達(dá)時(shí)間間隔分布函數(shù)A0(t)定義為到達(dá)時(shí)間間隔大于t的概率。設(shè)累計(jì)分布函數(shù)F(t)是到達(dá)時(shí)間間隔小于t概率，則A0(t)＝1-F(t)顯然，函數(shù)A0(t)在t=0時(shí)，取得最大值1；當(dāng)t增加時(shí)，A0(t)逐漸減小。（4）到達(dá)時(shí)間變化系數(shù)定義為到達(dá)時(shí)間間隔的標(biāo)準(zhǔn)差Sn與平均到達(dá)時(shí)間間隔Ta的比值Sn/Tn，它是一個(gè)無量綱的系數(shù)，描述了數(shù)據(jù)圍繞平均值的分散程度指數(shù)分布的平均值與標(biāo)準(zhǔn)差相同，所以其變化系數(shù)為1。如果觀測(cè)到的變化系數(shù)接近于1，則用指數(shù)分布去擬合這些數(shù)據(jù)是合理的。當(dāng)變化系數(shù)比1小得多時(shí)，經(jīng)常應(yīng)用愛爾朗分布。顧客的到達(dá)模式如果按顧客到來的方式劃分，那么可能是一個(gè)一個(gè)的，也可能是成批的；如果按相繼到達(dá)的時(shí)間間隔劃分，那么可以是確定型的，也可以是隨機(jī)型的；如果技按到達(dá)的過程劃分，那么可以是平穩(wěn)的，也可以是非平穩(wěn)的。3．服務(wù)機(jī)構(gòu)同到達(dá)時(shí)間一樣，首先定義T為平均服務(wù)時(shí)間，

為平均服務(wù)速率，S0(t)為服務(wù)時(shí)間大于t的概率。服務(wù)機(jī)構(gòu)按機(jī)構(gòu)形式可以分為無服務(wù)臺(tái)、只有一個(gè)服務(wù)臺(tái)或有多個(gè)服務(wù)臺(tái)的情況。在有多個(gè)服務(wù)臺(tái)的情形中，它們可以是平行排列(并列)的，也可以是前后排列(串列)的，也可以是混合的；按服務(wù)方式可以是對(duì)單個(gè)顧客進(jìn)行，也可以是對(duì)成批顧客進(jìn)行；按服務(wù)時(shí)間可以是確定型的，也可以是隨機(jī)型的；按服務(wù)過程可以是平穩(wěn)的，也可以是非平穩(wěn)的。非平穩(wěn)情形處理起來是十分復(fù)雜的，所以同到達(dá)過程一樣，服務(wù)時(shí)間的分布都假定是平穩(wěn)的。4．排隊(duì)規(guī)則（1）先到先服務(wù)（2）后到先服務(wù)（3）隨機(jī)服務(wù)（4）優(yōu)先權(quán)服務(wù)（5）多個(gè)服務(wù)臺(tái)（如n個(gè)）情形5．隊(duì)列的度量已知平均到達(dá)率和平均服務(wù)速率，定義業(yè)務(wù)量強(qiáng)度為：=/定義服務(wù)設(shè)備利用率為得到服務(wù)的動(dòng)態(tài)實(shí)體的到達(dá)速率與服務(wù)速率之比：=/nn--服務(wù)臺(tái)數(shù)目；

--每個(gè)服務(wù)臺(tái)的平均服務(wù)速率。對(duì)于隊(duì)列的度量，通?？疾靸蓚€(gè)量：隊(duì)列的長(zhǎng)度和排隊(duì)的時(shí)間。5．排隊(duì)模型的分類肯德爾（Kendall）對(duì)并列服務(wù)臺(tái)的情形提出一個(gè)分類方法，其符號(hào)形式是：X/Y/ZX--相繼到達(dá)的時(shí)間間隔的分布；Y--服務(wù)時(shí)間的分布；Z--并列的服務(wù)臺(tái)的數(shù)目。目前，這一方法被廣泛采用，常用的表示相繼到達(dá)的時(shí)間間隔和服務(wù)時(shí)間的概率分布的符號(hào)是：M--負(fù)指數(shù)分布（M是指Markov性，因負(fù)提數(shù)分布具有無記已憶性，即Markov性）D--確定型(Deterministic)；Ek--k階愛爾朗(Erlang)分布；GI--一般相互獨(dú)立的隨機(jī)分布；G--一般隨機(jī)分布。例如，M/M/1表示相繼到達(dá)的時(shí)間間隔為負(fù)指數(shù)分布，服務(wù)時(shí)間為負(fù)指數(shù)分布，單服務(wù)臺(tái)模型；D/M/2表示確定的到達(dá)時(shí)間間隔，服務(wù)時(shí)間為負(fù)指數(shù)分布，兩個(gè)平行服務(wù)臺(tái)(但顧客是一隊(duì))的模型；GI/G/1表示單服務(wù)臺(tái)，有一般相互獨(dú)立的隨機(jī)到達(dá)分布和一般隨機(jī)服務(wù)時(shí)間分布的模型。（二）到達(dá)時(shí)間間隔和服務(wù)時(shí)間的分布1．定長(zhǎng)分布2．泊松(Poisson)分布(1)平穩(wěn)性：在區(qū)間[a，a+t]內(nèi)有k個(gè)顧客到來的概率與a無關(guān)，只與t，k有關(guān)，將此概率記為Pk(t)(2)無后效性：不相交區(qū)間內(nèi)顧客數(shù)是相互獨(dú)立的。(3)普通性：令

(t)為時(shí)間t內(nèi)至少有兩個(gè)顧客到達(dá)的概率，則（4）有限性：任意區(qū)間內(nèi)到達(dá)有限個(gè)顧客的概率之和為1，即如果顧客到達(dá)時(shí)間滿足泊松分布，則在時(shí)間t內(nèi)到達(dá)k個(gè)顧客的概率為3．愛爾朗(Erlang)分布設(shè)

1,2,…k,是k個(gè)相互獨(dú)立的隨機(jī)變量，服從相同的參k數(shù)的負(fù)指數(shù)分布，則T=1+2+…+k的概率密度為稱T服從k階愛爾朗分布。易求得

E(T)=1/

，D(T)=1(2k)愛爾朗分布的概率密度示意圖當(dāng)k增大時(shí)，愛爾朗分布的圖形逐漸變得對(duì)稱，變化系數(shù)減小，也就是說，這時(shí)曲線族表示的數(shù)據(jù)要比指數(shù)分布表示的數(shù)據(jù)更接近平均值；當(dāng)k

30時(shí)，愛爾朗分布可以用正態(tài)分布近似；當(dāng)k→m時(shí)，D(T)→0，這時(shí)它化為確定型分布。所以一般k階愛爾朗分布可以看成不完全確定的中間型，能對(duì)現(xiàn)實(shí)世界提供具有更為廣泛的適應(yīng)性。完全隨機(jī)和完全確定的愛爾朗到達(dá)分布為4．一般相互獨(dú)立的隨機(jī)分布所有活動(dòng)實(shí)體的服務(wù)時(shí)間是相互獨(dú)立分布的。5．一般隨機(jī)分布如果到達(dá)時(shí)間和服務(wù)時(shí)間不能用上述幾種典型的分布簡(jiǎn)單地表示出來，那么可以先從先驗(yàn)數(shù)據(jù)中獲得統(tǒng)計(jì)數(shù)據(jù)，再加上適當(dāng)?shù)念A(yù)測(cè)推算，求出其概率分布。6．正態(tài)分布在服務(wù)時(shí)間近似于常數(shù)的情況下，多種隨機(jī)因素的影響使得服務(wù)時(shí)間圍繞此常數(shù)值波動(dòng)，此時(shí)可以用正態(tài)分布來描述。（三）排隊(duì)系統(tǒng)分析對(duì)于隨機(jī)排隊(duì)系統(tǒng)，在給定的到達(dá)條件下，研究系統(tǒng)的下述行為指標(biāo)：①系統(tǒng)中顧客數(shù)的期望值Ls，在隊(duì)列中等待的顧客數(shù)(隊(duì)列的長(zhǎng)度)的期望值Lq；②在系統(tǒng)中顧客逗留時(shí)間的期望值Ws，在隊(duì)列中顧客等待時(shí)間期望值Wq。求這些指標(biāo)時(shí)，都是以求解系統(tǒng)的狀態(tài)為n(有n個(gè)顧客)的概率Pn(t)為基礎(chǔ)的。1．單服務(wù)臺(tái)M/M/1模型標(biāo)推的M/M/1模型是指適合下列條件的排隊(duì)系統(tǒng)：(1)到達(dá)模式顧客源是無限的，顧客一個(gè)接一個(gè)地到達(dá)，相互獨(dú)立，在給定的時(shí)間區(qū)間內(nèi)到達(dá)的人數(shù)服從泊松分布，到達(dá)過程是平穩(wěn)的。(2)排隊(duì)規(guī)則單隊(duì)，對(duì)隊(duì)長(zhǎng)無限制，先到先服務(wù)。(3)服務(wù)臺(tái)單服務(wù)臺(tái)，各顧客的服務(wù)時(shí)間是相互獨(dú)立的，服從相同的指數(shù)分布。此外，還假定到達(dá)的時(shí)間間隔和服務(wù)時(shí)間是相互獨(dú)立的。在分析標(biāo)準(zhǔn)的M/M/1模型時(shí)，首先要求出系統(tǒng)在任意時(shí)刻t的狀態(tài)為n(系統(tǒng)中有n個(gè)顧客)的概率Pn(t)，它決定了系統(tǒng)運(yùn)行的特征。設(shè)到達(dá)模式服從參數(shù)為

的泊松分布，服務(wù)時(shí)間服從參數(shù)為

的指數(shù)分布，則在時(shí)間區(qū)間[t,t+t]內(nèi)：①有一個(gè)顧客到達(dá)的概率為

t+0(t)；沒有顧客到達(dá)的概率為1-[t+0(t)]②當(dāng)有顧客在接受服務(wù)的時(shí)候，一個(gè)顧客接受完服務(wù)后離去的概率為

t+0(t)，沒有離去的概率為1-[t+0(t)]③一個(gè)以上的顧客到達(dá)或離去的概率是0(

t)，可以忽略。在時(shí)刻t+

t，如果系統(tǒng)內(nèi)有n個(gè)顧客，那么就會(huì)有下表列出來的四種情況〔到達(dá)或離去兩人以上的情況沒有列出，可以忽略不計(jì))。情況時(shí)刻t顧客數(shù)（位）在區(qū)間[t,t+t]時(shí)刻t+t顧客數(shù)（位）到達(dá)離去An--nBn+1-+nCn-1+-nDn++n注：表中減號(hào)（-）表示沒有發(fā)生；加號(hào)（+）表示發(fā)生一個(gè)它們的概率分別是：情況A：Pn(t)(1-t)(1-t)情況B：Pn+1(t)(1-t)(t)情況C：Pn-1(t)(t)(1-t)情況D：Pn(t)(t)(t)由于以上四種情況是互不相容的，所以Pn(t+t)應(yīng)是以上四項(xiàng)的和：

Pn(t+t)=Pn(t)(1-t-t)+Pn+1(t)t+Pn-1(t)(t)(4.1)當(dāng)n=0時(shí)，只出現(xiàn)上表中的A，B兩種情形，即

P0(t+t)=P0(t)(1-t)+P1(t)(1-

t)t(4.2)當(dāng)t很大時(shí)，Pn(t)與t無關(guān)，將其記為Pn，它的導(dǎo)數(shù)為零，由式(4.1)、(4.2)得(4.3)這是關(guān)于Pn的差分方程，具體解為(4.4)式(4.5)便是系統(tǒng)狀態(tài)方程為n的概率。以它為基礎(chǔ)可以求得系統(tǒng)的一些運(yùn)算指標(biāo)：（1）在系統(tǒng)中的平均顧客數(shù)（期望）(4.5)（2）在隊(duì)列中等待的顧客數(shù)（3）顧客在系統(tǒng)中逗留的平均時(shí)間由于在M/M/1模型中，顧客在系統(tǒng)中停留的時(shí)間服從參數(shù)為

-的負(fù)指數(shù)分布，即（4）顧客在隊(duì)列中等待的平均時(shí)間[例]某醫(yī)院手術(shù)室根據(jù)病人就診和完成手術(shù)時(shí)間的記錄，任意抽查100個(gè)工作小時(shí)，每個(gè)小時(shí)來就診的病人數(shù)n的出現(xiàn)頻率如表4-1所示，又任意抽查了100個(gè)完成手術(shù)的病例，所用的手術(shù)時(shí)間(小時(shí))列于表4-2中。到達(dá)病人數(shù)n(位)出現(xiàn)頻數(shù)fn（次）012345

6102829161061合計(jì)100病人手術(shù)花費(fèi)時(shí)間(h)出現(xiàn)頻數(shù)fn（次）0.0~0.20.2~0.40.4~0.60.6~0.80.8~1.01.0~1.2

1.23825179650合計(jì)100表4-1病人到達(dá)情況表4-2病人手術(shù)花費(fèi)時(shí)間情況解：(2)取

=2.1,

=2.5，經(jīng)統(tǒng)計(jì)檢驗(yàn)可以認(rèn)為病人到達(dá)服從參數(shù)為

=2.1的泊松分布，手術(shù)時(shí)間服從參數(shù)為

=2.5的負(fù)指數(shù)分布。(3)服務(wù)臺(tái)利用率

=/=2.1/2.5=84％，這說明服務(wù)臺(tái)有84％的時(shí)間是繁忙的。(4)其他的各項(xiàng)指標(biāo)如下：在病房中的平均病人數(shù)排隊(duì)等待的病人數(shù)病人在病房中逗留時(shí)間的平均值病人排隊(duì)等待時(shí)間2．多服務(wù)臺(tái)M/M/C模型規(guī)定各服務(wù)臺(tái)工作是相互獨(dú)立的且平均服務(wù)率相同(均為

)。于是整個(gè)服務(wù)機(jī)構(gòu)的平均服務(wù)率為c

，只有當(dāng)

/(c)<l時(shí)隊(duì)列才不會(huì)排成無限長(zhǎng)。令

=/(c)稱

為這個(gè)系統(tǒng)的服務(wù)強(qiáng)度或服務(wù)臺(tái)平均利用率。對(duì)于標(biāo)準(zhǔn)的M/M/C模型，表示Pn(t)的微分方程為當(dāng)t很大時(shí)，令上述微分方程中的導(dǎo)數(shù)為零，得到穩(wěn)態(tài)的差分方程上面的差分方程的解為用

=/(c)代入，得(1)狀態(tài)概率(2)系統(tǒng)中平均顧客數(shù)和平均隊(duì)列長(zhǎng)度[例]某售票點(diǎn)有三個(gè)窗口，顧客的到達(dá)服從泊松分布，平均到達(dá)率為

=0.9(人)，服務(wù)時(shí)間服從負(fù)指數(shù)分布，平均服務(wù)率為

=0.4(人)。現(xiàn)設(shè)顧客到達(dá)后首先排成一隊(duì)，依次向空閑的窗口購票，如下圖所示。(3)平均等待時(shí)間圖:M/M/3系統(tǒng)模型示意圖解:由題意得（1）整個(gè)售票點(diǎn)空閑的概率（2）平均顧客數(shù)和平均隊(duì)列長(zhǎng)度（3）平均等待時(shí)間和逗留時(shí)間四、隨機(jī)數(shù)和隨機(jī)變量的生成均勻隨機(jī)數(shù)的產(chǎn)生及其檢驗(yàn)方法隨機(jī)變量的產(chǎn)生方法（一）均勻隨機(jī)數(shù)的產(chǎn)生及其檢驗(yàn)方法1.均勻隨機(jī)數(shù)所謂均勻隨機(jī)數(shù)是指服從均勻分布的隨機(jī)變量的樣本值。經(jīng)常用到的[0,1]區(qū)間上的均勻隨機(jī)數(shù)，它的密度函數(shù)f(x)和分布函數(shù)F(x)分別為：xx11100f(x)F(x)均勻隨機(jī)數(shù)的均勻性是指在長(zhǎng)度相同的每一子區(qū)間出現(xiàn)的概率值是一個(gè)常數(shù)；它的隨機(jī)性則表現(xiàn)在[0，1]區(qū)間內(nèi)，出現(xiàn)在某一子區(qū)間是沒有規(guī)律、任意和不以人的意示為轉(zhuǎn)移，即它的出現(xiàn)與前面的隨機(jī)數(shù)是不相關(guān)的，是獨(dú)立的。如果已知[0，1]區(qū)間的均勻隨機(jī)數(shù)R，需求[a，b]區(qū)間的均勻隨機(jī)數(shù)Rab則可用：

Rab＝a+(b-a)R

即為所求。均勻隨機(jī)數(shù)的產(chǎn)生方法有下列四種(1)手工方法(2)隨機(jī)數(shù)表法(3)利用計(jì)算機(jī)語言的內(nèi)部函數(shù)(4)利用數(shù)學(xué)公式產(chǎn)生均勻隨機(jī)數(shù)用公式產(chǎn)生的均勻隨機(jī)數(shù)應(yīng)滿足下列要求：(1)有較好的均勻性和隨機(jī)性；(2)產(chǎn)生隨機(jī)數(shù)的速度應(yīng)盡可能快；(3)產(chǎn)生隨機(jī)數(shù)的程序不要占用太多的內(nèi)存；(4)隨機(jī)數(shù)的重復(fù)周期盡可能長(zhǎng)；(5)隨機(jī)數(shù)的精度符合要求，即保證一定的有效數(shù)字位數(shù)，同時(shí)不要有逐漸衰減現(xiàn)象(6)隨機(jī)數(shù)列必須能夠重復(fù)產(chǎn)生，以便能夠重復(fù)模擬實(shí)驗(yàn)，對(duì)程序進(jìn)行調(diào)整和檢驗(yàn)。2.用公式產(chǎn)生均勻隨機(jī)數(shù)的方法（1）中間平方法（又叫自乘取中法）這是由JohnVonNewmamn和Metroplis于上世紀(jì)40年代中期提出來的。它首先給出一個(gè)初始隨機(jī)數(shù)Z0