排隊(duì)模型的計(jì)算機(jī)模擬

排隊(duì)論模型的計(jì)算機(jī)模擬數(shù)值模擬是依據(jù)被模擬對(duì)象的數(shù)學(xué)或邏輯模型,利用計(jì)算機(jī)進(jìn)行實(shí)驗(yàn)的一種技術(shù).已成為與理論分析,實(shí)驗(yàn)室實(shí)驗(yàn)并列的重要研究方法.如飛機(jī)船舶的設(shè)計(jì)等大型項(xiàng)目,美國軍隊(duì)的計(jì)算機(jī)推演.排隊(duì)論模型的計(jì)算機(jī)模擬,目的是研究系統(tǒng)性狀隨時(shí)間的發(fā)展,特別是它們能否具有某種穩(wěn)定的時(shí)間平均性質(zhì),研究系統(tǒng)對(duì)參數(shù)的敏感性以及系統(tǒng)的優(yōu)化與設(shè)計(jì).由于它涉及從一定的概率分布抽取若干隨機(jī)變量的值,因而是隨機(jī)模擬,屬M(fèi)onteCarlo模擬的范疇.一.實(shí)例考慮一小型機(jī)械加工車間,該車間加工四種不同類型的零件,零件相繼到達(dá)的時(shí)間間隔T是隨機(jī)的,無妨設(shè)其按照P(T<=x)=F(x)分布;每次來到的零件類型也是隨機(jī)的,假設(shè)第i種類型的零件出現(xiàn)的概率為Pi.車間里有三臺(tái)機(jī)床,每臺(tái)機(jī)床可以加工任何一種零件.零件的加工時(shí)間由類型決定,是確定的.規(guī)則:如果零件到達(dá)車間時(shí)有空閑機(jī)床,則該零件被立即加工,否則需排隊(duì)等待;先來到的零件排在前面.當(dāng)機(jī)床加工完零件時(shí),如果有零件在等待加工,則該機(jī)床立即加工排在隊(duì)列前面的零件.加工完的零件分送不同部門,不再跟蹤,但記錄下來.1.系統(tǒng)圖像首先,我們用一組數(shù)來描述系統(tǒng)在任何時(shí)刻所處的狀態(tài),這組數(shù)稱為系統(tǒng)圖像.隨著時(shí)間的發(fā)展,系統(tǒng)的狀態(tài)不斷變化,相應(yīng)地我們只有修改系統(tǒng)圖像即可.我們以下表為例.設(shè)目前的時(shí)間是2000(分).零件類型加工時(shí)間到達(dá)時(shí)間下一事件時(shí)刻下一零件37520022002----排隊(duì)零件1521992-4431976-44319722040加工零件2211936201737518962003現(xiàn)在時(shí)間2000已加工數(shù)(1)33(2)14(3)24(4)22下一零件的信息可由F(x)及Pi(x)(i=1,2,3,4)對(duì)進(jìn)行隨機(jī)抽樣得到.表1零件類型加工時(shí)間到達(dá)時(shí)間下一事件時(shí)刻下一零件37520022002----排隊(duì)零件1521992-4431976-44319722040加工零件2211936201737518962003現(xiàn)在時(shí)間2001已加工數(shù)(1)33(2)14(3)24(4)22時(shí)間過了1分鐘,則圖像基本不變,就是將現(xiàn)在時(shí)間調(diào)為2001.2.過程模擬從2000分的初始表格,即系統(tǒng)圖像開始,我們來進(jìn)行過程模擬.先查看所以下一步可能事件發(fā)生的時(shí)間.由于加工零件的結(jié)束時(shí)間在表中是按順序排列的,因此我們只需要考慮表中被加工零件的最后一行,并與第一行中的下一零件的達(dá)到時(shí)刻比較,看看那個(gè)更早.零件類型加工時(shí)間到達(dá)時(shí)間下一事件時(shí)刻下一零件221201820183752002-排隊(duì)零件1521992-4431976-44319722040加工零件2211936201737518962003現(xiàn)在時(shí)間2002已加工數(shù)(1)33(2)14(3)24(4)22下一零件的信息可由F(x)及Pi(x)(i=1,2,3,4)對(duì)進(jìn)行隨機(jī)抽樣得到.表2注:模擬程序交替地在處理系統(tǒng)圖像和計(jì)算抽樣值的子程序間運(yùn)行.從表2可知,下一事件是加工完畢一個(gè)3型零件.將時(shí)鐘撥到2003分,將這個(gè)3型零件移出系統(tǒng),并在表的最后一行的統(tǒng)計(jì)數(shù)據(jù)中將3型零件的數(shù)量加1,得到表3.零件類型加工時(shí)間到達(dá)時(shí)間下一事件時(shí)刻下一零件22120182018----排隊(duì)零件3752002-1521992-44319762046加工零件4431972204022119362017現(xiàn)在時(shí)間2003已加工數(shù)(1)33(2)14(3)25(4)22表3由表可知,下一事件的時(shí)間是2017.零件類型加工時(shí)間到達(dá)時(shí)間下一事件時(shí)刻下一零件22120182018----排隊(duì)零件----3752002工零件4431976204644319722040現(xiàn)在時(shí)間2017已加工數(shù)(1)33(2)15(3)25(4)22表4由表可知,下一事件的時(shí)間是2018.我們?cè)俚玫叫碌谋砀?即系統(tǒng)圖像.3.統(tǒng)計(jì)量的計(jì)算模擬的目的是為了得到系統(tǒng)的統(tǒng)計(jì)性質(zhì),本例中我們只按類型統(tǒng)計(jì)了加工完畢的零件數(shù).在不同的問題中,根據(jù)模擬的實(shí)際目的,可以得到各種有關(guān)參數(shù)的點(diǎn)估計(jì)或區(qū)間估計(jì).如一個(gè)顧客的平均服務(wù)時(shí)間,平均等待時(shí)間,平均隊(duì)列的長度等等.初值的選擇:許多時(shí)候,模擬的目的是為了得到系統(tǒng)平衡是的統(tǒng)計(jì)參數(shù),在初始階段往往受到初始值的影響,因此我們舍棄一適當(dāng)長度的初始模擬數(shù)據(jù).當(dāng)然,若我們選擇了恰當(dāng)?shù)某踔?便不必舍棄了.4.表處理技術(shù)在處理排隊(duì)論模擬中的表格時(shí),形成了一定的技巧.主要是使用指針來處理鏈接表格中的每一條記錄.表格中的一行表示一個(gè)零件的相關(guān)信息,我們稱之為一條記錄.在計(jì)算機(jī)內(nèi)存中,每條記錄用固定長度的若干連續(xù)單元存放,而系統(tǒng)圖像中的連續(xù)兩條記錄則不必連續(xù)放置,因?yàn)樵诿織l記錄所使用的單元中其實(shí)存放了兩部分的信息,一是模擬信息,二是加入一個(gè)指針變量的值,用以表示此記錄的下一記錄的首地址.當(dāng)然在表頭（第一條記錄）、表末(最后一條記錄)都要引入特殊標(biāo)志.這樣就形成一個(gè)鏈表.對(duì)記錄的處理時(shí),我們就只要對(duì)指針進(jìn)行操作即可.二.隨機(jī)數(shù)的生成在排隊(duì)模型的數(shù)值模擬中,必須按照各種給定的概率分布,得到所需要的隨機(jī)數(shù).在上面的實(shí)例中,按照給定的分布,決定下一零件的到來時(shí)間與類型.但是在計(jì)算機(jī)上,所有的這些數(shù)據(jù)都是按照一定的算法生成的,因此不是真正隨機(jī)的.但是,只要其統(tǒng)計(jì)特性與真正的隨機(jī)數(shù)很相似,就可以達(dá)到我們的目的.我們稱它們?yōu)閭坞S機(jī)數(shù).下面我們來介紹(0,1)區(qū)間上的均勻分布,一般的偽隨機(jī)數(shù)如不特別指明分布時(shí),就是專指這種分布.均勻分布偽隨機(jī)數(shù)的生成1.混同余法適當(dāng)取定非負(fù)整數(shù)a,c,m及x0,稱x0為種子,按照以下公式生成一個(gè)整數(shù)序列:則序列ui即給出了(0,1)區(qū)間上的偽隨機(jī)數(shù).容易看出,這樣產(chǎn)生的偽隨機(jī)數(shù)序列有一個(gè)周期,設(shè)其長度偽p,最大可能的周期是p=m.周期為m的偽隨機(jī)數(shù)序列稱為具有完全周期.利用數(shù)論中的知識(shí)來研究它.現(xiàn)狀:當(dāng)m=235時(shí),取a=27+1=129,c=1.2.乘同余法混同余法中包含乘法和加法兩種運(yùn)算,下面介紹的算法僅包含乘法,故名.取定非負(fù)整數(shù)a,m及x0,令仍以序列ui為(0,1)區(qū)間上的偽隨機(jī)數(shù).一般來說,乘同余法給出的序列不能達(dá)到完全周期;但是,當(dāng)m與x0互素,a滿足一定的條件時(shí),可達(dá)到一個(gè)最大的周期,非常接近m.m=235時(shí),取a=217+3,x0為奇數(shù).3.偽隨機(jī)數(shù)在微機(jī)上的生成算法上面介紹的兩種算法中的運(yùn)算都是整數(shù)運(yùn)算,不能進(jìn)行舍入.而現(xiàn)在的微機(jī)的整數(shù)不能超過15個(gè)二進(jìn)位(-32767~32768),因此上面的算法不能在微機(jī)上實(shí)現(xiàn).許多人想方設(shè)法來克服它,下面介紹Wichmann和Hill的公式:則偽隨機(jī)數(shù)為從均勻分布隨機(jī)數(shù)生成其他分布的隨機(jī)數(shù)有各種方法.如變換法,舍選法等待.我們不再介紹.三.過程模擬的更新方法我們?cè)趯?shí)例中介紹的方法可以視為一次隨機(jī)實(shí)驗(yàn),目的是得到一些統(tǒng)計(jì)推斷.但是,由于相繼時(shí)刻的系統(tǒng)狀態(tài)是高度相關(guān)的,這樣就不利于統(tǒng)計(jì)分析.還有,傳統(tǒng)的方法不能回答應(yīng)該模擬多長時(shí)間以及得到的結(jié)果精度如何等問題.克服這一困難的方法是更新模擬.本節(jié)前面介紹的例子中,我們假設(shè)輸入過程是時(shí)齊的,即轉(zhuǎn)移矩陣Q=(pij)與時(shí)間無關(guān).設(shè)初始時(shí)刻為三臺(tái)機(jī)床都閑置,沒有零件等待,當(dāng)恰有一個(gè)零件到來的瞬間我們記為T0,那么今后所以的這種時(shí)刻都是更新時(shí)刻.因此模擬更新法的思想是:我們將