第4講-排隊(duì)系統(tǒng)仿真課件

計(jì)算機(jī)仿真清華大學(xué)自動(dòng)化系2009-2010學(xué)年度秋學(xué)期ComputerSimulation第4講排隊(duì)系統(tǒng)建模與仿真范文慧4.0排隊(duì)系統(tǒng)仿真基礎(chǔ)知識(shí)4.1排隊(duì)系統(tǒng)仿真實(shí)例4.2離散事件系統(tǒng)仿真原理4.3隨機(jī)數(shù)發(fā)生器4.4隨機(jī)變量產(chǎn)生4.5排隊(duì)系統(tǒng)仿真實(shí)例4.6仿真結(jié)果輸出分析4.7小結(jié)目錄2（1）基本概念總體參數(shù)樣本統(tǒng)計(jì)量隨機(jī)抽取平均數(shù)標(biāo)準(zhǔn)差比例概率與數(shù)理統(tǒng)計(jì)知識(shí)名稱樣本特征值總體數(shù)字特征均值數(shù)學(xué)期望方差標(biāo)準(zhǔn)差變異系數(shù)（1）基本概念概率與數(shù)理統(tǒng)計(jì)知識(shí)方差：

標(biāo)準(zhǔn)差：

協(xié)方差：

相關(guān)系數(shù)：

（1）基本概念概率與數(shù)理統(tǒng)計(jì)知識(shí)Page6均值的方差期望值：均值的方差估計(jì)值：（1）基本概念概率與數(shù)理統(tǒng)計(jì)知識(shí)Page7（2）抽樣分布1)樣本均值抽樣分布概率與數(shù)理統(tǒng)計(jì)知識(shí)（2）抽樣分布中心極限定理：從總體均值μ，方差為σ2的總體中，抽取容量為n的隨機(jī)樣本，當(dāng)n（≧30)充分大時(shí)，樣本均值的抽樣分布服從均值為μ，方差為σ2/n的正態(tài)分布當(dāng)時(shí)，接近標(biāo)準(zhǔn)正態(tài)分布隨機(jī)變量的分布函數(shù)，即：實(shí)際應(yīng)用：概率與數(shù)理統(tǒng)計(jì)知識(shí)（2）抽樣分布2)樣本方差抽樣分布總體為正態(tài)分布概率與數(shù)理統(tǒng)計(jì)知識(shí)（2）抽樣分布概率與數(shù)理統(tǒng)計(jì)知識(shí)樣本統(tǒng)計(jì)量正態(tài)分布非正態(tài)分布正態(tài)分布大樣本非正態(tài)總體（小樣本）正態(tài)總體或非正態(tài)總體（大樣本）樣本均值樣本比例樣本方差分布樣本統(tǒng)計(jì)量的抽樣分布（2）抽樣分布3)兩個(gè)樣本均值差的抽樣分布概率與數(shù)理統(tǒng)計(jì)知識(shí)Page124)兩個(gè)樣本方差比的抽樣分布（2）抽樣分布概率與數(shù)理統(tǒng)計(jì)知識(shí)用樣本均值（）估計(jì)總體均值（μ

）(3)參數(shù)估計(jì)參數(shù)估計(jì)：（根據(jù)樣本統(tǒng)計(jì)量來推斷總體的參數(shù)）用樣本方差（）估計(jì)總體方差（

）用樣本比例（）估計(jì)總體比例（）用估計(jì)總體參數(shù)的統(tǒng)計(jì)量，稱為估計(jì)量用樣本統(tǒng)計(jì)量去估計(jì)總體的參數(shù)（θ）概率與數(shù)理統(tǒng)計(jì)知識(shí)無偏性：估計(jì)量抽樣分布的數(shù)學(xué)期望等于被估計(jì)的總體參數(shù)點(diǎn)估計(jì)：用樣本估計(jì)量的值，直接作為總體參數(shù)的估計(jì)值區(qū)間估計(jì)：在點(diǎn)估計(jì)的基礎(chǔ)上，給出總體參數(shù)估計(jì)的一個(gè)范圍，衡量點(diǎn)估計(jì)值的可靠性的度量置信水平：重復(fù)構(gòu)造置信區(qū)間多次，包含總體參數(shù)真值的次數(shù)所占的比率（1－α）置信區(qū)間：由樣本統(tǒng)計(jì)量所構(gòu)造的總體參數(shù)的估計(jì)區(qū)間(3)參數(shù)估計(jì)概率與數(shù)理統(tǒng)計(jì)知識(shí)Page151)總體均值的區(qū)間估計(jì)正態(tài)總體、方差已知，或非正態(tài)總體、大樣本置信區(qū)間非正態(tài)總體、大樣本置信區(qū)間正態(tài)總體、方差已知總體均值μ在1－α的置信水平下的置信區(qū)間正態(tài)總體、方差未知、小樣本總體均值μ在1－α的置信水平下的置信區(qū)間(3)參數(shù)估計(jì)概率與數(shù)理統(tǒng)計(jì)知識(shí)Page162)總體方差區(qū)間估計(jì)總體方差在1－α的置信水平下的置信區(qū)間正態(tài)總體，樣本方差服從由于則即(3)參數(shù)估計(jì)概率與數(shù)理統(tǒng)計(jì)知識(shí)Page173）兩個(gè)總體參數(shù)（均值差）的區(qū)間估計(jì)（獨(dú)立樣本）大樣本:若總體方差未知：若總體方差已知：(3)參數(shù)估計(jì)概率與數(shù)理統(tǒng)計(jì)知識(shí)Page184）估計(jì)總體均值的樣本容量的確定點(diǎn)估計(jì)值區(qū)間半長(zhǎng)度或邊際誤差E(3)參數(shù)估計(jì)概率與數(shù)理統(tǒng)計(jì)知識(shí)Page19(4)假設(shè)檢驗(yàn)(σ2未知)(σ2已知)P0為假設(shè)的總體比例總體的方差先對(duì)總體參數(shù)提出一個(gè)假設(shè)值，然后利用樣本信息判斷這一假設(shè)是否成立概率與數(shù)理統(tǒng)計(jì)知識(shí)排隊(duì)常常是件很令人惱火的事情……

尤其是在我們這樣的人口大國(guó)?4.0排隊(duì)系統(tǒng)仿真基礎(chǔ)知識(shí)20

排隊(duì)論：1918年，Erlang提出排隊(duì)論，并將它用于電話系統(tǒng)。

有形排隊(duì)現(xiàn)象：

進(jìn)餐館就餐，到圖書館借書，車站等車，去醫(yī)院看病，售票處售票，到工具房領(lǐng)物品等現(xiàn)象。

無形排隊(duì)現(xiàn)象：如幾個(gè)旅客同時(shí)打電話訂車票，如果有一人正在通話，其他人只得在各自的電話機(jī)前等待，他們分散在不同的地方，形成一個(gè)無形的隊(duì)列在等待通電話。4.0排隊(duì)系統(tǒng)仿真基礎(chǔ)知識(shí)隨機(jī)性：

顧客到達(dá)情況與顧客接受服務(wù)的時(shí)間是隨機(jī)的。排隊(duì)論所研究的排隊(duì)系統(tǒng)中，顧客相繼到達(dá)時(shí)間間隔和服務(wù)時(shí)間這兩個(gè)量中至少有一個(gè)是隨機(jī)的。

排隊(duì)論又稱隨機(jī)服務(wù)理論。4.0排隊(duì)系統(tǒng)仿真基礎(chǔ)知識(shí)排隊(duì)的不一定是人，也可以是物。

如生產(chǎn)線上的原材料，半成品等待加工；因故障而停止運(yùn)行的機(jī)器設(shè)備在等待修理；碼頭上的船只等待裝貨或卸貨；要下降的飛機(jī)因跑道不空而在空中盤旋等。服務(wù)的也不一定是人，

可以是跑道，自動(dòng)售貨機(jī)，公共汽車等。顧客——要求服務(wù)的對(duì)象。服務(wù)員——提供服務(wù)的服務(wù)者（也稱服務(wù)機(jī)構(gòu)）。顧客、服務(wù)員的含義是廣義的。4.0排隊(duì)系統(tǒng)仿真基礎(chǔ)知識(shí)服務(wù)臺(tái)顧客到達(dá)服務(wù)完成后離開單服務(wù)臺(tái)排隊(duì)系統(tǒng)4.0排隊(duì)系統(tǒng)仿真基礎(chǔ)知識(shí)排隊(duì)系統(tǒng)類型：排隊(duì)系統(tǒng)類型：服務(wù)臺(tái)2顧客到達(dá)服務(wù)完成后離開S個(gè)服務(wù)臺(tái)，一個(gè)隊(duì)列的排隊(duì)系統(tǒng)服務(wù)臺(tái)s服務(wù)臺(tái)14.0排隊(duì)系統(tǒng)仿真基礎(chǔ)知識(shí)排隊(duì)系統(tǒng)類型：服務(wù)臺(tái)2顧客到達(dá)服務(wù)完成后離開S個(gè)服務(wù)臺(tái)，S個(gè)隊(duì)列的排隊(duì)系統(tǒng)服務(wù)臺(tái)s服務(wù)臺(tái)1服務(wù)完成后離開服務(wù)完成后離開4.0排隊(duì)系統(tǒng)仿真基礎(chǔ)知識(shí)服務(wù)臺(tái)1顧客到達(dá)離開多服務(wù)臺(tái)串聯(lián)排隊(duì)系統(tǒng)服務(wù)臺(tái)s4.0排隊(duì)系統(tǒng)仿真基礎(chǔ)知識(shí)排隊(duì)系統(tǒng)類型：排隊(duì)系統(tǒng)的描述

實(shí)際中的排隊(duì)系統(tǒng)各不相同，但概括起來都由三個(gè)基本部分組成：。輸入過程，排隊(duì)及排隊(duì)規(guī)則和服務(wù)機(jī)構(gòu)輸入過程顧客總體（顧客源）數(shù)：可能是有限，也可能是無限。

河流上游流入水庫(kù)的水量可認(rèn)為是無限的；車間內(nèi)停機(jī)待修的機(jī)器顯然是有限的。到達(dá)方式：是單個(gè)到達(dá)還是成批到達(dá)。庫(kù)存問題中，若把進(jìn)來的貨看成顧客，則為成批到達(dá)的例子。4.0排隊(duì)系統(tǒng)仿真基礎(chǔ)知識(shí)顧客（單個(gè)或成批）相繼到達(dá)的時(shí)間間隔分布：這是刻劃輸入過程的最重要內(nèi)容。定常分布（D）：顧客相繼到達(dá)的時(shí)間間隔為確定的。如產(chǎn)品通過傳送帶進(jìn)入包裝箱就是定常分布。最簡(jiǎn)流（或稱Poisson)（M）：顧客相繼到達(dá)的時(shí)間間隔為獨(dú)立的，同為負(fù)指數(shù)分布4.0排隊(duì)系統(tǒng)仿真基礎(chǔ)知識(shí)排隊(duì)及排隊(duì)規(guī)則排隊(duì)有限排隊(duì)——排隊(duì)系統(tǒng)中顧客數(shù)是有限的。無限排隊(duì)——顧客數(shù)是無限，隊(duì)列可以排到無限長(zhǎng)（等待制排隊(duì)系統(tǒng)）。4.0排隊(duì)系統(tǒng)仿真基礎(chǔ)知識(shí)有限排隊(duì)還可以分成：損失制排隊(duì)系統(tǒng)：排隊(duì)空間為零的系統(tǒng)，即不允許排隊(duì)。（顧客到達(dá)時(shí)，服務(wù)臺(tái)占滿，顧客自動(dòng)離開，不再回來）（電話系統(tǒng)）混合制排隊(duì)系統(tǒng)：是等待制與損失制結(jié)合，即允許排隊(duì)，但不允許隊(duì)列無限長(zhǎng)。4.0排隊(duì)系統(tǒng)仿真基礎(chǔ)知識(shí)排隊(duì)規(guī)則當(dāng)顧客到達(dá)時(shí)，若所有服務(wù)臺(tái)都被占有且又允許排隊(duì)，則該顧客將進(jìn)入隊(duì)列等待。服務(wù)臺(tái)對(duì)顧客進(jìn)行服務(wù)所遵循的規(guī)則通常有：先來先服務(wù)（FCFS）后來先服務(wù)（LCFS）具有優(yōu)先權(quán)的服務(wù)（PS）4.0排隊(duì)系統(tǒng)仿真基礎(chǔ)知識(shí)服務(wù)機(jī)制服務(wù)員的數(shù)量及其連接方式（串聯(lián)還是并聯(lián)）顧客是單個(gè)還是成批接受服務(wù)服務(wù)時(shí)間的分布4.0排隊(duì)系統(tǒng)仿真基礎(chǔ)知識(shí)排隊(duì)系統(tǒng)的符號(hào)表示：“Kendall”記號(hào)：X/Y/Z/W

X表示顧客到達(dá)的時(shí)間間隔分布

Y表示服務(wù)時(shí)間的分布

Z表示服務(wù)臺(tái)個(gè)數(shù)

W表示系統(tǒng)的容量，即可容納的最多顧客數(shù)4.0排隊(duì)系統(tǒng)仿真基礎(chǔ)知識(shí)M/M/1/M：表示顧客相繼到達(dá)的時(shí)間間隔服從負(fù)指數(shù)分布M：表示服務(wù)時(shí)間為負(fù)指數(shù)分布1：?jiǎn)蝹€(gè)服務(wù)臺(tái)：系統(tǒng)容量為無限（等待制）的排隊(duì)模型4.0排隊(duì)系統(tǒng)仿真基礎(chǔ)知識(shí)M/M/S/KM：表示顧客到達(dá)的時(shí)間間隔服從負(fù)指數(shù)分布M：服務(wù)時(shí)間為負(fù)指數(shù)分布S：S個(gè)服務(wù)臺(tái)K：系統(tǒng)容量為K的排隊(duì)模型。當(dāng)K=S時(shí)為損失制排隊(duì)模型；當(dāng)K=時(shí)為等待制排隊(duì)模型。排隊(duì)系統(tǒng)的主要數(shù)量指標(biāo)：系統(tǒng)狀態(tài)：指排隊(duì)系統(tǒng)中的顧客數(shù)（排隊(duì)等待的顧客數(shù)與正在接受服務(wù)的顧客數(shù)之和）。排隊(duì)長(zhǎng)：系統(tǒng)中正在排隊(duì)等待服務(wù)的顧客數(shù)。4.0排隊(duì)系統(tǒng)仿真基礎(chǔ)知識(shí)記N(t)：時(shí)刻t(t0)的系統(tǒng)狀態(tài)；pn(t)：時(shí)刻t系統(tǒng)處于狀態(tài)n的概率；c：排隊(duì)系統(tǒng)中并行的服務(wù)臺(tái)數(shù)；n：當(dāng)系統(tǒng)處于狀態(tài)n時(shí)，新來的顧客的平均到達(dá)率（單位時(shí)間內(nèi)到達(dá)的平均顧客數(shù)）；n：當(dāng)系統(tǒng)處于狀態(tài)n時(shí)，整個(gè)系統(tǒng)的平均服務(wù)率（單位時(shí)間內(nèi)可以服務(wù)完的平均顧客數(shù)）；4.0排隊(duì)系統(tǒng)仿真基礎(chǔ)知識(shí)當(dāng)n為常數(shù)時(shí)記為；當(dāng)每個(gè)服務(wù)臺(tái)的平均服務(wù)率為常數(shù)時(shí)，記每個(gè)服務(wù)臺(tái)的服務(wù)率為，則當(dāng)nc時(shí)，有n=c。因此，顧客相繼到達(dá)的平均時(shí)間間隔為1/，平均服務(wù)時(shí)間為1/，令=/c，則為系統(tǒng)的服務(wù)強(qiáng)度。4.0排隊(duì)系統(tǒng)仿真基礎(chǔ)知識(shí)pn(t)稱為系統(tǒng)在時(shí)刻t的瞬間分布，一般不容易求得，同時(shí)，由于排隊(duì)系統(tǒng)運(yùn)行一段時(shí)間后，其狀態(tài)和分布都呈現(xiàn)出與初始狀態(tài)或分布無關(guān)的性質(zhì)，稱具有這種性質(zhì)的狀態(tài)或分布為平穩(wěn)狀態(tài)或平穩(wěn)分布，排隊(duì)論一般更注意研究系統(tǒng)在平穩(wěn)狀態(tài)下的性質(zhì)。4.0排隊(duì)系統(tǒng)仿真基礎(chǔ)知識(shí)排隊(duì)系統(tǒng)在平穩(wěn)狀態(tài)時(shí)一些基本指標(biāo)有：Pn:系統(tǒng)中恰有n個(gè)顧客的概率；Ls：系統(tǒng)中顧客數(shù)的平均值，又稱為平均隊(duì)長(zhǎng)；Lq：系統(tǒng)中正在排隊(duì)的顧客數(shù)的平均值，又稱為平均排隊(duì)長(zhǎng)；

T：顧客在系統(tǒng)中的逗留時(shí)間；Ws：顧客在系統(tǒng)中的平均逗留時(shí)間；Wq：顧客在系統(tǒng)中的排隊(duì)等待時(shí)間；4.0排隊(duì)系統(tǒng)仿真基礎(chǔ)知識(shí)某售票所有三個(gè)窗口，顧客到達(dá)服從指數(shù)分布，平均到達(dá)率每分鐘λ

=0.9（人），服務(wù)時(shí)間服從負(fù)指數(shù)分布，平均服務(wù)率每分鐘μ＝0.4（人），現(xiàn)在設(shè)顧客到達(dá)后排成一隊(duì)，依次向空閑窗口購(gòu)票，其中c=3;λ/μ=2.25,ρ=λ/（cμ）=2.25/3=0.75<1(服務(wù)臺(tái)的利用率）符合條件，帶入公式即可M/M/3與M/M/1那個(gè)好？414.0排隊(duì)系統(tǒng)仿真基礎(chǔ)知識(shí)窗口1μ＝0.4窗口2μ＝0.4窗口3μ＝0.4顧客到達(dá)顧客離去窗口1μ＝0.4窗口2μ＝0.4窗口3μ＝0.4顧客到達(dá)顧客離去排隊(duì)λ＝0.9排隊(duì)λ＝0.3排隊(duì)λ＝0.3排隊(duì)λ＝0.3424.0排隊(duì)系統(tǒng)仿真基礎(chǔ)知識(shí)服務(wù)臺(tái)空閑的概率顧客必須等待的概率M/M/1M/M/1434.0排隊(duì)系統(tǒng)仿真基礎(chǔ)知識(shí)平均顧客數(shù)和平均隊(duì)列長(zhǎng)度平均等待時(shí)間和逗留時(shí)間M/M/1M/M/1M/M/1M/M/1444.0排隊(duì)系統(tǒng)仿真基礎(chǔ)知識(shí)M/M/3（一隊(duì)）M/M/1（三隊(duì)）服務(wù)臺(tái)空閑的概率P00.07480.25(每個(gè)窗口）顧客必須等待的概率P(n>3)=0.570.75平均隊(duì)列長(zhǎng)度Lq1.702.25(每個(gè)窗口）平均顧客數(shù)Ls3.959.00(全部窗口）平均逗留時(shí)間Ws4.3910平均等待時(shí)間Wq1.897.5單隊(duì)比三隊(duì)有顯著的優(yōu)越性！c=3;λ/μ=2.25,ρ=λ/（cμ）=2.25/3=0.75<14.0排隊(duì)系統(tǒng)仿真基礎(chǔ)知識(shí)怎樣縮短排隊(duì)的等待時(shí)間？銀行的排隊(duì)叫號(hào)機(jī)只是有序的組織了顧客，并沒有減少等待時(shí)間如果能實(shí)現(xiàn)知道輪到自己需要等待多少時(shí)間，再選擇合適的時(shí)間來，豈不很好？4.1排隊(duì)系統(tǒng)仿真實(shí)例（1）46輸入來源隊(duì)列服務(wù)機(jī)構(gòu)排隊(duì)系統(tǒng)顧客服務(wù)完離開排隊(duì)系統(tǒng)的三個(gè)基本組成部分：輸入過程(顧客按照規(guī)律到達(dá))；排隊(duì)規(guī)則(顧客按照一定規(guī)則排隊(duì)等待服務(wù))；服務(wù)機(jī)構(gòu)

(服務(wù)機(jī)構(gòu)的設(shè)置，服務(wù)臺(tái)的數(shù)量，服務(wù)的方式，服務(wù)時(shí)間分布等)4.1排隊(duì)系統(tǒng)仿真實(shí)例（1）474.1排隊(duì)系統(tǒng)仿真實(shí)例（1）

由于離散事件系統(tǒng)固有的隨機(jī)性，對(duì)這類系統(tǒng)的研究往往十分困難。1）為什么這類系統(tǒng)仿真困難？

經(jīng)典的概率及數(shù)理統(tǒng)計(jì)理論、隨機(jī)過程理論雖然為研究這類系統(tǒng)提供了理論基礎(chǔ)，并能對(duì)一些簡(jiǎn)單系統(tǒng)提供解析解，但對(duì)工程實(shí)際中的大量系統(tǒng)，唯有依靠計(jì)算機(jī)仿真才能提供較為完整的結(jié)果。2）為什么傳統(tǒng)的方法無法解決？48單服務(wù)臺(tái)排隊(duì)系統(tǒng)4.1排隊(duì)系統(tǒng)仿真實(shí)例（2）49假設(shè)6個(gè)顧客，到達(dá)時(shí)間間隔是隨機(jī)的，服務(wù)時(shí)間也是隨機(jī)的，如何手工仿真單服務(wù)臺(tái)排隊(duì)系統(tǒng)。(1)假設(shè)

顧客總體（無限）顧客進(jìn)入等候線或進(jìn)入服務(wù)不會(huì)改變?nèi)说牡竭_(dá)率同時(shí)只有一個(gè)顧客以隨機(jī)的方式到達(dá)顧客一旦進(jìn)入等候線最終將得到服務(wù)

服務(wù)時(shí)間服從某一概率分布，并分布不隨時(shí)間而變化

系統(tǒng)的容量無限的（被服務(wù)的人數(shù)加上等候的人數(shù)）

被服務(wù)的規(guī)則服務(wù)員進(jìn)行服務(wù)的次序（FCFS，先來先服務(wù)）

到達(dá)和服務(wù)描述到達(dá)間隔時(shí)間分布和服務(wù)時(shí)間分布描述的整個(gè)有效的到達(dá)率必須小于最大的服務(wù)率4.1排隊(duì)系統(tǒng)仿真實(shí)例（1）501)顧客到達(dá)模式用到達(dá)時(shí)間間隔來描述,可分為確定性到達(dá)及隨機(jī)性到達(dá)。隨機(jī)性到達(dá)采用概率分布來描述,最常采用的泊松到達(dá)。2)服務(wù)模式描述服務(wù)臺(tái)為顧客服務(wù)的時(shí)間：確定性的,也可能是隨機(jī)的3)排隊(duì)規(guī)則服務(wù)臺(tái)完成當(dāng)前的服務(wù)后,從隊(duì)列中選擇下一實(shí)體的原則

FCFS——先到先服務(wù);LCFS——后到先服務(wù);PS——根據(jù)實(shí)體的重要程度選擇最優(yōu)先服務(wù)者4)服務(wù)流程多個(gè)服務(wù)臺(tái),多個(gè)隊(duì)列,如何從某一個(gè)隊(duì)列中選擇某一個(gè)實(shí)體服務(wù),包括實(shí)體可否換隊(duì)及換隊(duì)規(guī)則等4.1排隊(duì)系統(tǒng)仿真實(shí)例（1）（2）排隊(duì)系統(tǒng)的描述51

一個(gè)事件是引起系統(tǒng)狀態(tài)瞬時(shí)變化情況的集合在服務(wù)臺(tái)排隊(duì)系統(tǒng)中兩個(gè)可能的事件會(huì)影響系統(tǒng)的狀態(tài)

顧客進(jìn)入系統(tǒng)（到達(dá)事件）

顧客離開系統(tǒng)（離開事件）系統(tǒng)中顧客數(shù)以及服務(wù)員忙閑狀況。4.1排隊(duì)系統(tǒng)仿真實(shí)例（1）5）系統(tǒng)狀態(tài)52有另一個(gè)顧客等待?服務(wù)員開始閑從隊(duì)列中移走一個(gè)顧客開始對(duì)此顧客服務(wù)否是離開事件恰好完成服務(wù)的流程服務(wù)員忙？顧客進(jìn)入服務(wù)顧客入隊(duì)等待服務(wù)否是到達(dá)事件顧客進(jìn)入系統(tǒng)的流程4.1排隊(duì)系統(tǒng)仿真實(shí)例（1）53隊(duì)列狀態(tài)不空空服務(wù)員狀態(tài)忙進(jìn)入隊(duì)列進(jìn)入隊(duì)列閑不可能進(jìn)入服務(wù)顧客到達(dá)時(shí)可能的動(dòng)作隊(duì)列狀態(tài)不空空服務(wù)員結(jié)果忙不可能閑不可能一個(gè)服務(wù)完成后服務(wù)員的結(jié)果4.1排隊(duì)系統(tǒng)仿真實(shí)例（1）顧客服務(wù)員54

引起系統(tǒng)狀態(tài)發(fā)生變化的行為事件表：管理事件的表時(shí)鐘：標(biāo)記事件出現(xiàn)的時(shí)間的時(shí)鐘隨機(jī)數(shù)：事件是隨機(jī)出現(xiàn)的，為了模仿現(xiàn)實(shí)生活中所需的隨機(jī)性，應(yīng)用“隨機(jī)數(shù)”來完成4.1排隊(duì)系統(tǒng)仿真實(shí)例（1）6)事件55隨機(jī)數(shù)（number)是在區(qū)間（0，1)上獨(dú)立和均勻分布的；隨機(jī)數(shù)字(digit)是在集合{0，1，2，3，…，9}上均勻分布的隨機(jī)數(shù)字可用來產(chǎn)生隨機(jī)數(shù)；從隨機(jī)數(shù)字表上選取合適的隨機(jī)數(shù)字，在選取的隨機(jī)數(shù)字的左邊加上十進(jìn)制的小數(shù)點(diǎn)，可以構(gòu)成隨機(jī)數(shù)；當(dāng)用一組過程產(chǎn)生隨機(jī)數(shù)時(shí)，他們經(jīng)常被稱為偽隨機(jī)數(shù)。4.1排隊(duì)系統(tǒng)仿真實(shí)例（1）7)隨機(jī)數(shù)56到達(dá)事件間隔和時(shí)鐘時(shí)間由擲6個(gè)值骰子五次并記錄它們的點(diǎn)數(shù)來產(chǎn)生用來計(jì)算排隊(duì)系統(tǒng)的6個(gè)顧客的到達(dá)時(shí)間顧客123456到達(dá)間隔和時(shí)鐘時(shí)間1)到達(dá)時(shí)間（3）排隊(duì)系統(tǒng)仿真過程到達(dá)的時(shí)鐘時(shí)間026791557到達(dá)間隔時(shí)間--241264.1排隊(duì)系統(tǒng)仿真實(shí)例（1）服務(wù)時(shí)間假設(shè)有1，2，3，4個(gè)時(shí)間單位，假定所有的4個(gè)值等可能出現(xiàn)。把4個(gè)值預(yù)先刻在籌碼上，然后，輪回隨機(jī)抽取籌碼，將選到的數(shù)據(jù)記錄下來。排隊(duì)系統(tǒng)到達(dá)間隔時(shí)間和服務(wù)時(shí)間必須匹配顧客123456服務(wù)時(shí)間4.1排隊(duì)系統(tǒng)仿真實(shí)例（1）2)服務(wù)時(shí)間：58服務(wù)時(shí)間213214顧客到達(dá)時(shí)間（時(shí)鐘）10223647596153)仿真表仿真表是為單服務(wù)臺(tái)隊(duì)列設(shè)計(jì)的。仿真表記錄了每個(gè)事件出現(xiàn)時(shí)的時(shí)鐘時(shí)間。表第2列是到達(dá)時(shí)間的時(shí)鐘時(shí)間；表第5列記錄了每個(gè)離開事件的時(shí)鐘時(shí)間；兩類事件按照時(shí)間順序排列。強(qiáng)調(diào)時(shí)鐘時(shí)間的仿真表4.1排隊(duì)系統(tǒng)仿真實(shí)例（1）開始服務(wù)時(shí)間（時(shí)鐘）02691115服務(wù)時(shí)間（持續(xù)）213214完成服務(wù)時(shí)間239111219597159319事件類型顧客時(shí)鐘時(shí)間到達(dá)10離開12到達(dá)22離開23到達(dá)36到達(dá)47離開39到達(dá)59離開411離開512到達(dá)615離開6195)按時(shí)間次序順序的事件系統(tǒng)中的顧客數(shù)612012143356時(shí)鐘時(shí)間4.1排隊(duì)系統(tǒng)仿真實(shí)例（1）4)服務(wù)顧客的規(guī)則：先進(jìn)先出22451160某雜貨店的收款臺(tái)顧客隨機(jī)地分別以1和8分鐘的間隔到達(dá)，等概率分布；服務(wù)時(shí)間1至6分鐘，等概率分布；模仿20個(gè)顧客到達(dá)和服務(wù)，來分析此系統(tǒng)。到達(dá)時(shí)間間隔概率累積概率隨機(jī)數(shù)區(qū)間10.1250.125001-12520.1250.250126-25030.1250.375251-37540.1250.500376-50050.1250.625501-62560.1250.750626-75070.1250.875751-87580.1251.000876-000到達(dá)時(shí)間間隔分布(已知表）4.1排隊(duì)系統(tǒng)仿真實(shí)例（2）1到8分均勻分布0到1分均勻分布61服務(wù)時(shí)間概率累積概率隨機(jī)數(shù)區(qū)間10.100.1001-1020.200.3011-3030.300.6031-6040.250.8561-8550.100.9586-9560.051.0096-00服務(wù)時(shí)間分布(已知表）1到6分均勻分布0到1分均勻分布4.1排隊(duì)系統(tǒng)仿真實(shí)例（2）62顧客隨機(jī)數(shù)字到達(dá)間隔時(shí)間（分）顧客隨機(jī)數(shù)字到達(dá)間隔時(shí)間（分）1－－－－1110912913812093137276136075401511473865948815359363093168888792281710618753718212292352194934103023205355根據(jù)上述的到達(dá)時(shí)間間隔分布表確定到達(dá)間隔時(shí)間4.1排隊(duì)系統(tǒng)仿真實(shí)例（2）63顧客隨機(jī)數(shù)字服務(wù)時(shí)間（分）顧客隨機(jī)數(shù)字服務(wù)時(shí)間（分）1844113232101129453744137944533140515172157956794168447915175238674185539895193021038320503根據(jù)上述的服務(wù)時(shí)間分布表產(chǎn)生服務(wù)時(shí)間4.1排隊(duì)系統(tǒng)仿真實(shí)例（2）6465顧客到達(dá)時(shí)間間隔到達(dá)時(shí)間服務(wù)時(shí)間開始服務(wù)時(shí)間（分）顧客在隊(duì)列中等待時(shí)間服務(wù)時(shí)間結(jié)束顧客在系統(tǒng)中花費(fèi)時(shí)間服務(wù)員空閑時(shí)間（分）100404402888109143614144018454115183321605823232025226326264030417834345039548741414045429243455250701034650345370111475336569012148565861130135536148651201465965166670153626654719016870714175501717175347870182737835818019477812483602058283318640826856（13）124184.1排隊(duì)系統(tǒng)仿真實(shí)例（2）仿真結(jié)果：1顧客平均等待時(shí)間：顧客在隊(duì)中總等待時(shí)間/總顧客數(shù)＝56/20=2.8分2顧客必須在隊(duì)列中等待的概率：等待顧客數(shù)/顧客總數(shù)＝13/20＝0.653服務(wù)員空閑的比例：服務(wù)員總空閑時(shí)間/仿真運(yùn)行總時(shí)間＝18/86=0.214平均服務(wù)時(shí)間：總服務(wù)時(shí)間/顧客總數(shù)＝68/20=3.4分4.1排隊(duì)系統(tǒng)仿真實(shí)例（2）66

這個(gè)結(jié)果可以和服務(wù)時(shí)間分布的均值進(jìn)行比較：用服務(wù)時(shí)間表求分布的期望值：期望服務(wù)時(shí)間：1(0.10)＋2(0.20)＋3(0.30)＋4(0.25)＋5(0.10)＋6(0.05)=3.2分◆期望服務(wù)時(shí)間略小于仿真的平均服務(wù)時(shí)間◆仿真時(shí)間越長(zhǎng)越接近于E(s)總的服務(wù)時(shí)間/顧客總數(shù)＝68/20=3.4分仿真的平均服務(wù)時(shí)間:4.1排隊(duì)系統(tǒng)仿真實(shí)例（2）675平均到達(dá)間隔時(shí)間:

所有到達(dá)間隔時(shí)間之和/(到達(dá)數(shù)－1）＝82/19=4.3分期望達(dá)到間隔時(shí)間略高于平均值，但是，在更長(zhǎng)的仿真中，到達(dá)間隔時(shí)間的均值應(yīng)接近于理論均值E(A)。分母減去1？分母減去1是因?yàn)榈谝粋€(gè)到達(dá)時(shí)間假定為出現(xiàn)在時(shí)間為0的時(shí)刻離散均勻分布求得的均值的期望到達(dá)間隔時(shí)間，這個(gè)均勻分布的端點(diǎn)是a=1和b=8，于是平均值為：E(A)=(a+b)/2=(1+8)/2=4.5分

4.1排隊(duì)系統(tǒng)仿真實(shí)例（2）68

大多數(shù)顧客必須等待，而平均等待時(shí)間不會(huì)過大，服務(wù)員沒有過多的空閑。6

在隊(duì)列中等待得顧客的平均等待時(shí)間：顧客在隊(duì)列中等待總時(shí)間/在隊(duì)中等待顧客總數(shù)＝56/13=4.3分7顧客消耗在系統(tǒng)中的平均時(shí)間：顧客消耗在系統(tǒng)中的總時(shí)間/顧客總數(shù)＝124/20＝6.2分4.1排隊(duì)系統(tǒng)仿真實(shí)例（2）69SimulationbyHand：Manuallytrackstatevariables,statisticalaccumulatorsUse“given”interarrival,servicetimesKeeptrackofeventcalendar“Lurch”clockfromoneeventtothenext4.1排隊(duì)系統(tǒng)仿真實(shí)例（3）70SomeAdditionalSpecificsfortheSimpleProcessingSystemSimulationclock:variableEventcalendar:Listofeventrecords:[EntityNo.,EventTime,EventType]KeeprankedinincreasingorderonEventTimeNexteventalwaysintoprecordInitially,schedulefirstArrival,TheEnd(Dep.?)Statevariables:describecurrentstatusServerstatusB(t)=1forbusy,0foridleNumberofcustomersinqueueQ(t)Timesofarrivalofeachcustomernowinqueue(alistofrandomlength)4.1排隊(duì)系統(tǒng)仿真實(shí)例（3）71SimulationbyHand:Setup4.1排隊(duì)系統(tǒng)仿真實(shí)例（3）72SimulationbyHand:t=0.00,Initialize4.1排隊(duì)系統(tǒng)仿真實(shí)例（3）73SimulationbyHand:t=0.00,ArrivalofPart114.1排隊(duì)系統(tǒng)仿真實(shí)例（3）74SimulationbyHand:t=1.73,ArrivalofPart2124.1排隊(duì)系統(tǒng)仿真實(shí)例（3）75SimulationbyHand:t=2.90,DepartureofPart124.1排隊(duì)系統(tǒng)仿真實(shí)例（3）76SimulationbyHand:t=3.08,ArrivalofPart3234.1排隊(duì)系統(tǒng)仿真實(shí)例（3）77SimulationbyHand:t=3.79,ArrivalofPart42344.1排隊(duì)系統(tǒng)仿真實(shí)例（3）78SimulationbyHand:t=4.41,ArrivalofPart523454.1排隊(duì)系統(tǒng)仿真實(shí)例（3）79SimulationbyHand:t=4.66,DepartureofPart23454.1排隊(duì)系統(tǒng)仿真實(shí)例（3）80SimulationbyHand:t=8.05,DepartureofPart3454.1排隊(duì)系統(tǒng)仿真實(shí)例（3）81SimulationbyHand:t=12.57,DepartureofPart454.1排隊(duì)系統(tǒng)仿真實(shí)例（3）82SimulationbyHand:t=17.03,DepartureofPart54.1排隊(duì)系統(tǒng)仿真實(shí)例（3）83SimulationbyHand:t=18.69,ArrivalofPart664.1排隊(duì)系統(tǒng)仿真實(shí)例（3）84SimulationbyHand:t=19.39,ArrivalofPart7674.1排隊(duì)系統(tǒng)仿真實(shí)例（3）85SimulationbyHand:t=20.00,TheEnd674.1排隊(duì)系統(tǒng)仿真實(shí)例（3）86SimulationbyHand:FinishingUp平均等待時(shí)間：平均隊(duì)列長(zhǎng)度:服務(wù)臺(tái)的利用率:4.1排隊(duì)系統(tǒng)仿真實(shí)例（3）87CompleteRecordoftheHandSimulation生產(chǎn)率零件數(shù)最大隊(duì)列數(shù)最大服務(wù)時(shí)間最大等待時(shí)間88Event-SchedulingLogicviaProgrammingClearlywellsuitedtostandardprogrammingOftenuse“utility”librariesfor:ListprocessingRandom-numbergenerationRandom-variategenerationStatisticscollectionEvent-listandclockmanagementSummaryandoutputMainprogramtiesittogether,executeseventsinorder4.1排隊(duì)系統(tǒng)仿真實(shí)例（3）89SimulationDynamics:TheProcess-InteractionWorldViewIdentifycharacteristicentitiesinthesystemMultiplecopiesofentitiesco-exist,interact,compete“Code”isnon-proceduralTella“story”aboutwhathappenstoa“typical”entityMayhavemanytypesofentities,“fake”entitiesforthingslikemachinebreakdownsUsuallyrequiresspecialsimulationsoftwareUnderneath,stillexecutedasevent-scheduling4.1排隊(duì)系統(tǒng)仿真實(shí)例（3）90RandomnessinSimulationTheabovewasjustone“replication”—asampleofsizeone(notworthmuch)Madeatotaloffivereplications:values:Ingeneral,Forexpectedtotalproduction,4.1排隊(duì)系統(tǒng)仿真實(shí)例（3）91ComparingAlternativesUsually,simulationisusedformorethanjustasinglemodel“configuration”O(jiān)ftenwanttocomparealternatives,selectorsearchforthebest(viasomecriterion)Simpleprocessingsystem:Whatwouldhappenifthearrivalrateweretodouble?CutinterarrivaltimesinhalfRerunthemodelfordouble-timearrivalsMakefivereplications4.1排隊(duì)系統(tǒng)仿真實(shí)例（3）92Results:Originalvs.Double-TimeArrivalsOriginal–circles○Double-time–triangles△Replication1–filledinReplications2-5–hollowNotevariabilityDangerofmakingdecisionsbasedonone(first)replicationHardtoseeiftherearereallydifferencesNeed:

Statisticalanalysisofsimulationoutputdata4.1排隊(duì)系統(tǒng)仿真實(shí)例（3）93

系統(tǒng)仿真是系統(tǒng)運(yùn)行的快速拍照，是系統(tǒng)運(yùn)行過程真實(shí)的再現(xiàn)。有人又叫快速攝影技術(shù)。在復(fù)雜系統(tǒng)中，每一時(shí)刻都有若干事件發(fā)生，有多個(gè)系統(tǒng)狀態(tài)變量在變化，如何推進(jìn)仿真鐘，使仿真能完整、準(zhǔn)確的記錄這一復(fù)雜過程？4.1排隊(duì)系統(tǒng)仿真實(shí)例（3）94（1）實(shí)體：構(gòu)成系統(tǒng)的各種元素（不僅僅是物理單元）臨時(shí)實(shí)體在系統(tǒng)中只存在一段時(shí)間的實(shí)體。這類實(shí)體由系統(tǒng)外部到達(dá)系統(tǒng),通過系統(tǒng)，最終離開系統(tǒng)。永久實(shí)體永久駐留在系統(tǒng)中的實(shí)體。只要系統(tǒng)處于活動(dòng)狀態(tài),這些實(shí)體就存在，或者說，永久實(shí)體是系統(tǒng)處于活動(dòng)的必要條件。臨時(shí)實(shí)體按一定規(guī)律不斷地到達(dá)（產(chǎn)生）,在永久實(shí)體作用下通過系統(tǒng)，最后離開系統(tǒng)，整個(gè)系統(tǒng)呈現(xiàn)出動(dòng)態(tài)過程。1.基本概念4.2離散事件系統(tǒng)仿真的一般原理95成分與實(shí)體的區(qū)別：概念相同，成分是模型的組成元素；實(shí)體是系統(tǒng)的組成元素主動(dòng)成分：可主動(dòng)產(chǎn)生狀態(tài)變化的成分被動(dòng)成分：只在主動(dòng)成分作用才產(chǎn)生狀態(tài)變化的成分仿真?zhèn)€體：在實(shí)體中流動(dòng)，并且在各道服務(wù)工序停留接受服務(wù)的單個(gè)實(shí)體仿真資源：系統(tǒng)對(duì)個(gè)體提供服務(wù)的物資手段，如超市的收銀員4.2離散事件系統(tǒng)仿真的一般原理96Page97（2）屬性：實(shí)體所有的特性實(shí)體可能具有若干特征，但并不是所有的特征都被稱為仿真系統(tǒng)的實(shí)體屬性

狀態(tài)變量：代表仿真模型里反映系統(tǒng)變化特征的變量單服務(wù)臺(tái)系統(tǒng)可以定義兩個(gè)狀態(tài)變量：

服務(wù)者狀態(tài)：空和閑

等候服務(wù)的個(gè)體數(shù)量：0－N4.2離散事件系統(tǒng)仿真的一般原理97（3）事件引起系統(tǒng)狀態(tài)發(fā)生變化的行為，系統(tǒng)是由事件來驅(qū)動(dòng)的。

顧客到達(dá)為一類事件，顧客到達(dá)使系統(tǒng)狀態(tài)——服務(wù)員的“狀態(tài)”可能從閑變到忙（如果無人排隊(duì))，或者另一系統(tǒng)狀態(tài)——排隊(duì)的顧客人數(shù)發(fā)生變化（隊(duì)列人數(shù)加1)。

顧客離去為一類事件，顧客接受服務(wù)完畢后離開系統(tǒng)服務(wù)臺(tái)“狀態(tài)”由忙變成閑。事件表：對(duì)系統(tǒng)中的事件進(jìn)行管理的表，表中記錄每一發(fā)生了的或?qū)⒁l(fā)生的事件類型，發(fā)生時(shí)間，以及與該事件相聯(lián)的實(shí)體的有關(guān)屬性等等。系統(tǒng)事件：系統(tǒng)中固有事件。程序事件：用于控制仿真進(jìn)程。4.2離散事件系統(tǒng)仿真的一般原理98（4）活動(dòng)

用于表示兩個(gè)可以區(qū)分的事件之間的過程,它標(biāo)志著系統(tǒng)狀態(tài)的轉(zhuǎn)移。顧客的到達(dá)事件與服務(wù)開始事件之間可稱為一個(gè)活動(dòng)（5）進(jìn)程進(jìn)程由若干個(gè)事件及若干活動(dòng)組成,一個(gè)進(jìn)程描述了它所包括的事件及活動(dòng)間的相互邏輯關(guān)系及時(shí)序關(guān)系。進(jìn)程排隊(duì)活動(dòng)服務(wù)活動(dòng)顧客到達(dá)事件服務(wù)開始事件服務(wù)結(jié)束事件圖10.1事件、活動(dòng)、進(jìn)程三者關(guān)系示意圖4.2離散事件系統(tǒng)仿真的一般原理99（6）仿真鐘離散事件動(dòng)態(tài)系統(tǒng)的狀態(tài)本來就只在離散時(shí)間點(diǎn)上發(fā)生變化，因而不需要進(jìn)行離散化處理。由于引起狀態(tài)變化的事件發(fā)生時(shí)間的隨機(jī)性，仿真鐘的推進(jìn)步長(zhǎng)則完全是隨機(jī)的兩個(gè)相鄰發(fā)生的事件之間系統(tǒng)狀態(tài)不會(huì)發(fā)生任何變化，因而仿真鐘可以跨過這些“不活動(dòng)”周期,仿真鐘的推進(jìn)呈現(xiàn)跳躍性，推進(jìn)速度具有隨機(jī)性。時(shí)間控制部件是必不可少的,以便按一定規(guī)律來控制仿真鐘的推進(jìn)。4.2離散事件系統(tǒng)仿真的一般原理100（7）統(tǒng)計(jì)計(jì)數(shù)器 某一次仿真運(yùn)行得到的狀態(tài)變化過程只不過是隨機(jī)過程的一次取樣,它們只有在統(tǒng)計(jì)意義下才有參考價(jià)值。 在仿真模型中,需要有一個(gè)統(tǒng)計(jì)計(jì)數(shù)部件,以便統(tǒng)計(jì)系統(tǒng)中的有關(guān)變量。4.2離散事件系統(tǒng)仿真的一般原理1014.2離散事件系統(tǒng)仿真的一般原理系統(tǒng)銀行交通生產(chǎn)通訊存儲(chǔ)實(shí)體顧客乘車的人機(jī)器信號(hào)倉(cāng)庫(kù)屬性帳目解算起點(diǎn)站終點(diǎn)站速度，能力，故障率長(zhǎng)度，終端容量活動(dòng)存款旅行焊接，沖壓傳輸退回事件到達(dá)到站到達(dá)故障到達(dá)終端需求狀態(tài)變量等待得顧客人數(shù)在每站等待的乘車人數(shù)，在旅行的人數(shù)機(jī)器的狀態(tài)（忙，空閑或故障）等待傳輸數(shù)目存儲(chǔ)量，欠付需求102

仿真鐘推進(jìn)方法有兩大類：按下一最早發(fā)生事件的發(fā)生時(shí)間推進(jìn),亦稱為事件調(diào)度法，另一類是固定增量推進(jìn)方法。

為第個(gè)與第個(gè)顧客到達(dá)之間的間隔時(shí)間;=服務(wù)員為第i個(gè)顧客服務(wù)的時(shí)間長(zhǎng)度

=第i個(gè)顧客排隊(duì)等待的時(shí)間長(zhǎng)度;

為第i個(gè)顧客離去的時(shí)間;=第i個(gè)顧客到達(dá)的時(shí)間; =第i個(gè)任何一類事件發(fā)生的時(shí)間;=第i個(gè)事件發(fā)生時(shí)的隊(duì)長(zhǎng); =第i個(gè)事件發(fā)生時(shí)服務(wù)員的狀態(tài),

其中=1表示忙,=0表示閑。例10.2單服務(wù)臺(tái)排隊(duì)系統(tǒng),如單窗口的售票站。設(shè)2.仿真鐘推進(jìn)4.2離散事件系統(tǒng)仿真的一般原理(1)事件調(diào)度法(EventScheduling)103Page104顧客離去經(jīng)過Si服務(wù)員空閑否服務(wù)完畢開始服務(wù)

是顧客到達(dá)(時(shí)間間隔)排隊(duì)等待否圖10.2

單服務(wù)臺(tái)仿真模型4.2離散事件系統(tǒng)仿真的一般原理104若定義如下系統(tǒng)事件類型:

類型1

顧客到達(dá)事件

類型2

顧客接受服務(wù)事件

類型3

顧客服務(wù)完畢并離去事件定義程序事件為:

仿真運(yùn)行到150個(gè)時(shí)間單位(分鐘)結(jié)束假定已經(jīng)得到到達(dá)時(shí)間間隔隨機(jī)變量的樣本值為:

系統(tǒng)初始狀態(tài):4.2離散事件系統(tǒng)仿真的一般原理105時(shí)間事件服務(wù)員狀態(tài)排隊(duì)長(zhǎng)度0仿真開始0015顧客1到達(dá)1047顧客2到達(dá)1158顧客1服務(wù)完畢0158顧客2接受服務(wù)1071顧客3到達(dá)1194顧客2服務(wù)完畢0194顧客3接受服務(wù)10............150仿真結(jié)束4.2離散事件系統(tǒng)仿真的一般原理106Page1074.2離散事件系統(tǒng)仿真的一般原理

為第個(gè)與第個(gè)顧客到達(dá)之間的間隔時(shí)間;=服務(wù)員為第i個(gè)顧客服務(wù)的時(shí)間長(zhǎng)度

=第i個(gè)顧客排隊(duì)等待的時(shí)間長(zhǎng)度;

為第i個(gè)顧客離去的時(shí)間;=第i個(gè)顧客到達(dá)的時(shí)間; =第i個(gè)任何一類事件發(fā)生的時(shí)間;=第i個(gè)事件發(fā)生時(shí)的隊(duì)長(zhǎng); =第i個(gè)事件發(fā)生時(shí)服務(wù)員的狀態(tài),

其中=1表示忙,=0表示閑。

b0b1b2b3b4b5b6b7b8b9t0t1t2t3

t4

t5

150

A1A2A3A4A5S1S2S3S4D2D3D4D5153224402243363428C158C294C3128C4156112317234771111133107事件調(diào)度法仿真鐘推進(jìn)初始值:TIME= 1）下一個(gè)最早發(fā)生事件：為第1號(hào)顧客到達(dá)(A1),發(fā)生時(shí)刻為即： 因，仿真鐘推進(jìn)到,然后處理該事件。

4.2離散事件系統(tǒng)仿真的一般原理——仿真的發(fā)動(dòng)S1b0b1t0t1

c1

150

A1154358因?yàn)槭堑竭_(dá)事件,且,立即服務(wù),即接受服務(wù)，服務(wù)臺(tái)狀態(tài)由變?yōu)閯t其離去時(shí)間：該顧客服務(wù)時(shí)間為1082）下一個(gè)最早發(fā)生事件：仿真鐘推進(jìn)到，處理該到達(dá)事件：4.2離散事件系統(tǒng)仿真的一般原理b0b1b2t0t1t2

c1

A1A2S1D2因?yàn)閺亩?duì)長(zhǎng)該顧客開始等待時(shí)間為因

該到達(dá)顧客只好排隊(duì)等待仍是到達(dá)事件(A2)435832151094.2離散事件系統(tǒng)仿真的一般原理其離去時(shí)間S1D2b0b1b2b3b4t0t1t2

t3

c2

A1A2A3處理第1號(hào)顧客的離去事件,包括：統(tǒng)計(jì)服務(wù)人數(shù);觀察隊(duì)列中是否有顧客等待,目前則該顧客進(jìn)入服務(wù),同時(shí)要計(jì)算其排隊(duì)等待的時(shí)間

修改隊(duì)長(zhǎng)該顧客的服務(wù)時(shí)間：

＝11943）下一個(gè)最早發(fā)生事件：是第1號(hào)顧客離去事件,

因下一個(gè)到達(dá)事件發(fā)生時(shí)間為：

從而 仿真鐘推進(jìn)到t3=t2+A3=47+24=71>C1153224584371S21104）下一最早發(fā)生事件：由因而下一事件應(yīng)是到達(dá)事件(A3),仿真鐘推進(jìn)到依次下去,下到下一事件為仿真結(jié)束的程度事件為止。S1S2D2D3b0b1b2b3b4b5b6t0t1t2c1t3

c2t4

A1A2A3A4b0b1b2b3b4b5b6b7b8b9t0t1t2c1t3

c2

t4

c3t5

150

A1A2A3A4A5S1S2S3S4D2D3D4D54.2離散事件系統(tǒng)仿真的一般原理C2>t3111(2)固定增量時(shí)間推進(jìn)

選擇適當(dāng)?shù)臅r(shí)間單位T做為仿真鐘推進(jìn)時(shí)的增量,每推進(jìn)一步進(jìn)行如下處理:該步內(nèi)若無事件發(fā)生,則仿真鐘再推進(jìn)一個(gè)單位時(shí)間T;若在該步內(nèi)有若干個(gè)事件發(fā)生,則認(rèn)為這些事件均發(fā)生在該步的結(jié)束時(shí)刻。

為便于進(jìn)行各類事件處理，必須事先規(guī)定當(dāng)出現(xiàn)這種情況時(shí)各類事件處理的優(yōu)先順序。4.2離散事件系統(tǒng)仿真的一般原理112缺點(diǎn)：仿真鐘每推進(jìn)一步,均要檢查事件表以確定是否有事件發(fā)生,增加了執(zhí)行時(shí)間;

任何事件的發(fā)生均認(rèn)為發(fā)生在這一步的結(jié)束時(shí)刻,如果T選擇過大,則會(huì)引入較大的誤差;

要求事先確定各類事件的處理順序,增加了建模的復(fù)雜性。

主要用于系統(tǒng)事件發(fā)生時(shí)間具有較強(qiáng)周期性的模型4.2離散事件系統(tǒng)仿真的一般原理113開始結(jié)束正確否正確否是是確定仿真算法輸出仿真結(jié)果并分析否系統(tǒng)建模運(yùn)行仿真程序建立仿真模型設(shè)計(jì)仿真程序否1.系統(tǒng)建模如何由觀測(cè)數(shù)據(jù)確定隨機(jī)變量的分布和參數(shù)？

如何產(chǎn)生所需求的隨機(jī)變量？2.確定仿真算法采用什么方法仿真（仿真策略)？3.建立仿真模型建立計(jì)算機(jī)模型（變量定義及程序流程）描述系統(tǒng)狀態(tài)轉(zhuǎn)移(事件、活動(dòng)和進(jìn)程等）

4.設(shè)計(jì)仿真程序采用高級(jí)語言編程實(shí)現(xiàn)，掌握各種語句采用仿真語言編程實(shí)現(xiàn)，掌握各種語句5.運(yùn)行仿真程序仿真發(fā)動(dòng)，進(jìn)行仿真

6.仿真結(jié)果輸出與分析仿真結(jié)果的可信性如何?如何提高仿真結(jié)果的置信度?每次仿真運(yùn)行所得到的結(jié)果僅僅是隨機(jī)變量的一次取樣1144.2離散事件系統(tǒng)仿真的一般原理隨機(jī)數(shù)：隨機(jī)變量的樣本取樣值均勻分布的隨機(jī)數(shù)：隨機(jī)變量x在其可能值范圍中的任一區(qū)間出現(xiàn)的概率正比于此區(qū)間的大小與可能值范圍的比值。(0，1)均勻分布隨機(jī)數(shù)：在各種分布的隨機(jī)數(shù)中，最常用和最重要的是在(0，1)區(qū)間上的均勻分布隨機(jī)數(shù)。4.3隨機(jī)數(shù)發(fā)生器4.3

隨機(jī)數(shù)發(fā)生器

隨機(jī)數(shù)發(fā)生器：產(chǎn)生[0,1]區(qū)間上均勻分布的隨機(jī)變量,亦稱為隨機(jī)數(shù)發(fā)生器。其它各類分布，如正態(tài)分布，分布，分布，泊松分布等，可以用某種方法對(duì)這種均勻分布進(jìn)行某種變換來實(shí)現(xiàn)1）隨機(jī)性（randomness)

偽隨機(jī)數(shù)序列應(yīng)當(dāng)具有獨(dú)立性、均勻性，并具有與真實(shí)隨機(jī)數(shù)具有相同的數(shù)字特征，如期望、方差等。4.3隨機(jī)數(shù)發(fā)生器1.隨機(jī)數(shù)特點(diǎn)或者性質(zhì)？2）長(zhǎng)周期（LargePeriod)

由于隨機(jī)發(fā)生器都是基于準(zhǔn)確的、確定性的公式而設(shè)計(jì)的，所以產(chǎn)生的隨機(jī)數(shù)序列最終不可避免得回到它的起點(diǎn)，并且重復(fù)以前出現(xiàn)過的序列，其中無重復(fù)隨機(jī)數(shù)序列的長(zhǎng)度稱為周期。希望隨機(jī)數(shù)發(fā)生器生成的隨機(jī)數(shù)序列具有較長(zhǎng)的周期，從實(shí)用角度來看，不能在短期內(nèi)出現(xiàn)重復(fù)，即仿真系統(tǒng)運(yùn)行期間盡量不出現(xiàn)隨機(jī)序列重復(fù)的現(xiàn)象。4.3隨機(jī)數(shù)發(fā)生器3）可重現(xiàn)性（Reproducibility)再現(xiàn)同樣的隨機(jī)數(shù)序列當(dāng)我們調(diào)試一個(gè)仿真系統(tǒng)時(shí)，隨機(jī)數(shù)發(fā)生器要求能準(zhǔn)確地多次再現(xiàn)同樣的隨機(jī)數(shù)序列。生成不同以往的隨機(jī)序列根據(jù)分析人員的需要，隨機(jī)數(shù)發(fā)生器既要能再次生成同樣的隨機(jī)序列，又要能生成不同以往的隨機(jī)序列。4.3隨機(jī)數(shù)發(fā)生器4）計(jì)算效率高（computationalefficiency)

時(shí)間盡量的少由于有時(shí)仿真系統(tǒng)在短期內(nèi)需要大量的隨機(jī)數(shù)，所以隨機(jī)數(shù)發(fā)生器要求生成每個(gè)隨機(jī)數(shù)所花費(fèi)時(shí)間盡量的少。占用計(jì)算機(jī)內(nèi)存盡量少不會(huì)占用過多的計(jì)算機(jī)內(nèi)存，特別是可視化仿真系統(tǒng)的運(yùn)行時(shí)，有限的內(nèi)存是非常寶貴的。4.3隨機(jī)數(shù)發(fā)生器Entertainment

娛樂Gambling賭博

Lottery,luckydraw抽獎(jiǎng)Games游戲Cryptography密碼學(xué)KeygenerationComputersimulation仿真Softwaretesting軟件測(cè)試GeneratingtestingdataRandomizedalgorithms隨機(jī)化算法

Avoidingworstcases2、隨機(jī)數(shù)發(fā)生器的應(yīng)用4.3隨機(jī)數(shù)發(fā)生器1)手工方法抽簽、擲骰子、旋轉(zhuǎn)圓盤等優(yōu)點(diǎn)：簡(jiǎn)單；缺點(diǎn)：效率低。4.3隨機(jī)數(shù)發(fā)生器3、隨機(jī)數(shù)的生成方法1222)表格法利用某種手段生成的隨機(jī)數(shù)序列以表格形式存入計(jì)算機(jī)，供給仿真時(shí)調(diào)用。優(yōu)點(diǎn)：直觀、簡(jiǎn)單；缺點(diǎn)：準(zhǔn)備表格不方便，每次對(duì)隨機(jī)數(shù)進(jìn)行一次讀操作非常浪費(fèi)時(shí)間，浪費(fèi)存儲(chǔ)空間。4.3隨機(jī)數(shù)發(fā)生器4.3隨機(jī)數(shù)發(fā)生器3)物理方法將物理隨機(jī)發(fā)生器安裝在計(jì)算機(jī)上，把具有隨機(jī)性質(zhì)的物理過程變換為隨機(jī)數(shù)。缺點(diǎn)：不能重復(fù)生成與原來完全相同的隨機(jī)數(shù)，故無法核對(duì)計(jì)算結(jié)果，且生成過程復(fù)雜。1244)數(shù)學(xué)方法按照一定的算法（遞推公式）來生成“隨機(jī)”序列。只要給定一個(gè)初始值（稱為種子值），當(dāng)調(diào)用該算法時(shí)，即可以按確定的關(guān)系計(jì)算出下一個(gè)“隨機(jī)”數(shù)，多次調(diào)用該算法，就可以生成一個(gè)“隨機(jī)”序列。4.3隨機(jī)數(shù)發(fā)生器（1）中值平方法第一個(gè)隨機(jī)數(shù)發(fā)生器，20實(shí)際40年代由VonNeumann和Metropolis提出的。

1）從一個(gè)四位正整數(shù)Z0開始，將Z0平方得到一個(gè)八位數(shù)（如果需要，在它的左邊附加幾個(gè)零使之成為八位數(shù)），

2）取這個(gè)八位數(shù)的中間四位數(shù)作為下一個(gè)四位數(shù)Z13）同樣，求得Z2，Z3，…，Zi4）在每個(gè)Zi個(gè)的左邊加上小數(shù)點(diǎn)，從而得到一個(gè)[0,1]的均勻的隨機(jī)數(shù)序列U1，U2，…,Ui，4.3隨機(jī)數(shù)發(fā)生器JohnvonNeumann1903-19574、隨機(jī)數(shù)發(fā)生器1261)一旦退化為零，該序列將永遠(yuǎn)停留在零上2)不可避免的具有周期性iZiUiZi20342311716929171690.716951394561239450.394515563025356300.563031696900469690.696948566961556690.566932137561例：取Z0＝34234.3隨機(jī)數(shù)發(fā)生器obsolete!缺點(diǎn)：127（2）線性同余發(fā)生器(linearCongruentialgenerator)是第個(gè)隨機(jī)數(shù)為乘子C為增量,為模數(shù)稱為隨機(jī)數(shù)源或種子,均為非負(fù)整數(shù)。滿足:為了得到[0,1]區(qū)間上所需要的隨機(jī)數(shù)可令:萊默爾（Lehmer）在1951年提出4.3隨機(jī)數(shù)發(fā)生器最簡(jiǎn)單,最常用a=0，為加同余C=0，為乘同余其余為混合同余128例:

觀察的線性同余發(fā)生器。

iZiUiiZiUi071090.563160.3751100.000210.0631230.188380.5001320.1254110.68814130.8135100.6251540.250650.3131670.4387120.7501760.3758150.9381810.0639140.8751980.5004.3隨機(jī)數(shù)發(fā)生器1294.3隨機(jī)數(shù)發(fā)生器1）缺點(diǎn)：設(shè)則…1304.3隨機(jī)數(shù)發(fā)生器(modm)確定,則就完全確定下來了。一旦只要謹(jǐn)慎選取還是可以達(dá)到近似[0,1]均勻隨機(jī)數(shù)的效果實(shí)質(zhì)上完全不是隨機(jī)的由于

不隨機(jī)1314.3隨機(jī)數(shù)發(fā)生器132是區(qū)間上的整數(shù),那么由得到的

因此，線性同余隨機(jī)發(fā)生器中模數(shù)m一般非常大，如109或者更大，這樣可以使[0,1]中的取值點(diǎn)變得非常密集。線性同余隨機(jī)發(fā)生器常常取m≥109僅僅是有限個(gè)數(shù),即為0,而不可能位于這些數(shù)值之外，也不能取介于兩個(gè)數(shù)值之間的數(shù)。由于4.3

隨機(jī)數(shù)發(fā)生器

取值有限性

(modm)1334.3隨機(jī)數(shù)發(fā)生器僅僅是有限個(gè)數(shù),即為0,而不可能位于這些數(shù)值之外，也不能取介于兩個(gè)數(shù)值之間的數(shù)。所以，隨機(jī)數(shù)序列不可避免出現(xiàn)相同的元素

取值周期性

不安全公式容易從輸出中反求出來134c)由計(jì)算機(jī)運(yùn)行時(shí)本身帶有的隨機(jī)性事件來生成2）如何選擇種子？數(shù)值多少為好？人工設(shè)置，隨機(jī)性基本保證了,效率太低 a)b)由計(jì)算機(jī)系統(tǒng)時(shí)鐘生成，因?yàn)橄到y(tǒng)時(shí)鐘是不斷推進(jìn)的，所以總能取到不同的種子，目前的開發(fā)語言大都可以讀取系統(tǒng)時(shí)鐘，精確到毫秒，我們從年、月、日、時(shí)、分、秒和毫秒中抽取幾位數(shù)，拼湊一起。人們對(duì)線性同余發(fā)生器進(jìn)行了大量深入的研究，并在它的基礎(chǔ)上擴(kuò)展出多種改進(jìn)的發(fā)生器4.3隨機(jī)數(shù)發(fā)生器1353）特點(diǎn):

4.3隨機(jī)數(shù)發(fā)生器值確位于[0,m-1]區(qū)間上，位于[0,1]區(qū)間內(nèi)a)取值有限性適當(dāng)選擇,可使循環(huán)產(chǎn)生,取何值,其循環(huán)順序是相同的。如果則稱該發(fā)生器具有滿周期。循環(huán)一次稱為發(fā)生器的一個(gè)周期,記為,無論b)周期性iZiUiiZiUi071090.563160.3751100.000210.0631230.188380.5001320.1254110.68814130.8135100.6251540.250650.3131670.4387120.7501760.3758150.9381810.0639140.8751980.500M=16;P=161364.3隨機(jī)數(shù)發(fā)生器,可保證在[0,m-1]區(qū)間上一個(gè)周期內(nèi)每個(gè)適當(dāng)?shù)剡x擇整數(shù)正好出現(xiàn)一次,從而保證了均勻性;c)均勻性的均勻性,要求加大，為提高足夠大,且發(fā)生器具有滿足周期,這就足夠近似于真正的[0,1]區(qū)間上的均勻分布U(0,1)。那么可以預(yù)計(jì),所得到的在[0,1]區(qū)間上是均勻分布的,且取值是相當(dāng)密的。d)[0,1]區(qū)間上的均勻分布U(0,1)1374.3

隨機(jī)數(shù)發(fā)生器

（1）隨機(jī)數(shù)發(fā)生器都采用遞推算法。（2）計(jì)算機(jī)是具有完全確定性的機(jī)器，通過某種固定不變近似地生成隨機(jī)數(shù)。其實(shí)這些數(shù)值并非真正的“隨機(jī)”。

為什么隨機(jī)數(shù)發(fā)生器是偽隨機(jī)數(shù)？

偽隨機(jī)數(shù)表現(xiàn)出某種程度的“隨機(jī)性”，滿足仿真系統(tǒng)能夠?qū)﹄S機(jī)變量統(tǒng)計(jì)特性的要求，所以，在實(shí)際應(yīng)用中假定這些數(shù)值是隨機(jī)數(shù)。如果算法選擇得合適,由這種算法得到的數(shù)據(jù)統(tǒng)計(jì)檢驗(yàn)后能具有較好的統(tǒng)計(jì)特性(如均勻性,獨(dú)立性等),則將這種偽隨機(jī)數(shù)用于仿真仍然是可行的。4.3隨機(jī)數(shù)發(fā)生器為什么偽隨機(jī)數(shù)可以用來仿真？（pseudorandomnumber)139

隨機(jī)數(shù)發(fā)生器的設(shè)計(jì)方法，也就是如何生成具有良好統(tǒng)計(jì)特性的[0,1]均勻分布隨機(jī)數(shù)。

[0,1]均勻分布隨機(jī)數(shù)是生成其它分布類型的隨機(jī)變量的基本要素。因此，統(tǒng)計(jì)上可靠的[0,1]均勻分布隨機(jī)數(shù)發(fā)生器非常重要。4.4隨機(jī)變量產(chǎn)生的原理140如何符合分布的隨機(jī)變量？設(shè)隨機(jī)變量x的分布函數(shù)為1.反變換法（inversetransformmethod）先產(chǎn)生在[0,1]區(qū)間上均勻分布的獨(dú)立隨機(jī)變量即為所需要的隨機(jī)變量:4.4隨機(jī)變量產(chǎn)生的原理連續(xù)隨機(jī)變量的反變換法由反分布函數(shù)得到的值141的取值范圍為[0,1]；原理說明：F(x)為連續(xù)單調(diào)增的函數(shù)F(x)為X的分布函數(shù)f(x)為X的概率密度函數(shù)證明：x服從符合原來給定的密度分布函數(shù)4.4隨機(jī)變量產(chǎn)生的原理142？在[0,1]上均勻分布的獨(dú)立隨機(jī)變量作為的取值規(guī)律；從而隨機(jī)變量x在區(qū)間內(nèi)出現(xiàn)的概率密度函數(shù)當(dāng)趨于0時(shí),其概率密度函數(shù)就等于即符合原來給定的密度分布函數(shù),滿足正確性要求內(nèi)的樣本個(gè)數(shù)的概率就是落在4.4隨機(jī)變量產(chǎn)生的原理需要的隨機(jī)變量143的平均值為例12.1

設(shè)隨機(jī)變量x是[a,b]上均勻分布的隨機(jī)變量,即概率密度函數(shù)：

由可得到的分布函數(shù):

用隨機(jī)數(shù)發(fā)生器產(chǎn)生U(0,1)隨機(jī)變量令 可得:4.4隨機(jī)變量產(chǎn)生的原理144

在使用之前必須先求出分布函數(shù)的反函數(shù)，但是，有些分布函數(shù)（如正態(tài)分布、分布等）的解析的反函數(shù)表達(dá)式是求不出來的。4.4隨機(jī)變量產(chǎn)生的原理連續(xù)隨機(jī)變量的反變換法缺點(diǎn)?

可以利用數(shù)值計(jì)算的方法求得F-1的近似值，或者用冪級(jí)數(shù)展開來求得F-1的近似表達(dá)式的方法來使用反變換法。1452.舍選法（acceptance-rejectionmethod)直接法：直接面向分布函數(shù)，以反變換法為基礎(chǔ)舍選法：當(dāng)反變換法難于使用時(shí)(隨機(jī)變量的分布函數(shù)不存在封閉形式)。舍選法的實(shí)質(zhì)：實(shí)際是提出一定的檢驗(yàn)條件，從許多均勻分布的隨機(jī)數(shù)中選出一部分，使其具有給定分布的隨機(jī)變量，它可以用于產(chǎn)生任意有界的隨機(jī)變量

用舍選法產(chǎn)生服從密度函數(shù)為r(x)的隨機(jī)變量，因此，定義t(x)的時(shí)候，最好是能夠使密度函數(shù)r(x)的隨機(jī)變量容易用反變換法求取。4.4隨機(jī)變量產(chǎn)生的原理因?yàn)?/p>

首先，定義一個(gè)與原分布密度函數(shù)f(x)有相同取值域的函數(shù)t(x),使之覆蓋原分布函數(shù)，即對(duì)于所有f(x)取值域的x，都有t(x)≥f(x)。所以，通常t(x)不是一個(gè)密度函數(shù)，但是，顯然函數(shù)是一個(gè)密度函數(shù)，（1）若獨(dú)立地產(chǎn)生兩個(gè)[0,1]區(qū)間內(nèi)均勻分布的隨機(jī)變量,即,否則舍棄直觀意義：的取值范圍為[0,1]。的密度函數(shù)為的最大值為C,設(shè)隨機(jī)機(jī)變量是在[0,C]區(qū)間內(nèi)均勻分布的隨機(jī)變量（2）則成立,則選取為所需要的隨機(jī)變量若:求的值,（3）以4.4隨機(jī)變量產(chǎn)生的原理產(chǎn)生隨機(jī)變量的步驟如下：舍選法的解釋：若該點(diǎn)位于曲線下面,則認(rèn)為抽樣成功。若x取值僅在（0，1）區(qū)間，則該積分值可視為分布函數(shù)值，就是所需產(chǎn)生的隨機(jī)變量。的縱坐標(biāo)為,橫坐標(biāo)為在1×C這塊矩形上任投一點(diǎn)下的面積可視為在（0，1）區(qū)