A6離散事件系統(tǒng)仿真基礎(chǔ).ppt

離散事件動態(tài)系統(tǒng)仿真基礎(chǔ),離散事件動態(tài)系統(tǒng)系統(tǒng)的狀態(tài)只是在離散時間點上發(fā)生變化， 而且這些離散時間點一般是不確定的。 由于離散事件系統(tǒng)固有的隨機性，對這類系統(tǒng)的研究往往十分困難。 經(jīng)典的的概率及數(shù)理統(tǒng)計理論和隨機過程理論雖然為這類系統(tǒng)提供了 理論基礎(chǔ)，并能對一些簡單系統(tǒng)提供解析解，但對工程實際中的大量實用系統(tǒng)，惟有依靠計算機仿真技術(shù)才能提供較為完整的結(jié)果。,隊列,服務(wù)員,排隊系統(tǒng),離散事件動態(tài)系統(tǒng)仿真基礎(chǔ),離散事件動態(tài)系統(tǒng)仿真基礎(chǔ),基本概念: (1)實體: 分為臨時實體和永久實體. 臨時實體-在系統(tǒng)中只存在一段時間的實體 (顧客) 永久實體-永遠駐留在系統(tǒng)中的實體 (服務(wù)員) (2)事件: 引起系統(tǒng)狀態(tài)發(fā)生變化的行為.(這類系統(tǒng)是由事件來驅(qū)動的,為了 實現(xiàn)對系統(tǒng)中的事件進行管理,仿真模型中必須建立事件表） (3)活動: 通常用于表示兩個可以區(qū)分的事件之間的過程，它標(biāo)志著系統(tǒng)狀 態(tài)的轉(zhuǎn)移. ( 例如顧客開始接受服務(wù)到服務(wù)結(jié)束之間可稱為活動) (4)進程: 進程由若干個有序事件及若干個有序 活動組成,它描述了所包含的事件及活 動間的相互邏輯關(guān)系及時序關(guān)系。 (5)仿真鐘: 在離散事件系統(tǒng)中仿真鐘的推進呈 現(xiàn)跳躍性,推進速度具有隨機性. (6)統(tǒng)計計數(shù)器: 離散事件系統(tǒng)仿真的結(jié)果具有統(tǒng)計性質(zhì).,顧客到達事件,服務(wù)開始事件,服務(wù)結(jié)束事件,排隊活動,服務(wù)活動,進程,離散事件系統(tǒng)仿真基礎(chǔ),仿真鐘的推進離散事件系統(tǒng)仿真的基礎(chǔ) 離散事件系統(tǒng)仿真的時鐘推進方法有兩大類： 1）事件調(diào)度法時鐘是按下一個最早發(fā)生事件的發(fā)生時刻推進。 舉例: 單服務(wù)臺排隊系統(tǒng) 事件表: 2）固定增量法類似于連續(xù)系統(tǒng)仿真中的定（等）步長算法。,顧客到達時間間隔 A,服務(wù)員空閑?,A 15 32 24 40 22,S 43 36 34 28 ,經(jīng)過S,開始服務(wù),時間,47,15,0,58,58,71,94,事件,顧客 1到達,顧客 2到達,顧客 1 服務(wù)完畢,顧客 2 開始服務(wù),顧客 3 到達,顧客 2 服務(wù)完畢,仿真開始,服務(wù)員狀態(tài),排隊長度,0,閑,閑,閑,忙,忙,忙,忙,0,1,1,1,1,0,0,15,47,58,71,94,仿真開始,服務(wù)員,隊列,顧客,服務(wù)完畢,顧客離去,排隊等待,離散事件系統(tǒng)仿真基礎(chǔ),單服務(wù)臺排隊系統(tǒng)仿真：1918年，Erlang提出排隊系統(tǒng)，并將它用于電話系 統(tǒng)，其實質(zhì)就是研究服務(wù)臺與顧客之間的效率問題，希望服務(wù)臺效率高，而顧客 的等待時間又不太長。 排隊論又稱隨機服務(wù)理論。 （1）實體（顧客）到達模式：一般用到達時間間隔描述，可分為確定性到達及 隨機性到達。隨機性到達采用概率分布來描述，最長采用泊松到達。 泊松到達在 內(nèi)到達的實體數(shù) 的概率為 其中 表示在 區(qū)間內(nèi)到達實體的個數(shù)， 為到達概率。 到達時間間隔服從指數(shù)分布，其密度函數(shù)為 為到達時間間隔。 （2）服務(wù)模式：服務(wù)臺為顧客服務(wù)的時間可以是確定性的，也可能是隨機的。隨機的服務(wù)時間也用概率分布來描述。,離散事件系統(tǒng)仿真基礎(chǔ),排隊系統(tǒng)的組成: 1) 到達模式 : 指動態(tài)實體(顧客)按怎樣的規(guī)律到達; 2) 服務(wù)模式 : 指同一時刻有多少服務(wù)設(shè)備可以接納動態(tài)實體,它們的服務(wù) 需要多少時間; 3) 排隊模式: 指對下一個實體服務(wù)的選擇原則,通常采用: FIFO 先進先出 LIFO 后進先出 SIRO 隨機服務(wù),動態(tài)實體,排隊,服務(wù)機構(gòu),離散事件系統(tǒng)仿真基礎(chǔ),研究排隊系統(tǒng)的目的是為了得到系統(tǒng)的統(tǒng)計性能，比較普遍使用的性能有以下四種： （1）穩(wěn)態(tài)平均延誤時間 ：（實體在隊列中的平均等待時間） 為第 個實體的延誤時間； 是接受服務(wù)的實體數(shù)。 （2）實體通過系統(tǒng)的穩(wěn)態(tài)平均滯留時間 為第 個實體通過系統(tǒng)時的滯留時間，它等于實體在隊列中的等待時間 與 該實體接受服務(wù)的時間 之和。 （3）穩(wěn)態(tài)平均隊長 為 時刻的隊列長度， 為系統(tǒng)運行時間。 （4）系統(tǒng)中穩(wěn)態(tài)平均實體數(shù) 為 時刻系統(tǒng)中的實體數(shù)，它是在隊列中的實體數(shù) 與正在接受服務(wù)的實體 數(shù) 之和。,離散事件系統(tǒng)仿真基礎(chǔ),上述四個性能指標(biāo)存在的條件是服務(wù)臺的利用率為： 的定義是： 平均服務(wù)時間 平均到達時間間隔 對于 M/M/1 排隊系統(tǒng)，上述4項指標(biāo)可解析計算得到，即,單服務(wù)臺排隊系統(tǒng)仿真舉例,系統(tǒng)的有關(guān)參數(shù)： （1）實體到達模式：到達時間間隔 服從均值為 的指數(shù)分布，即 （2）服務(wù)模式：服務(wù)時間為 ，它也服從均值為 的指數(shù)分布，即 （3）服務(wù)規(guī)則：按 FIFO方式服務(wù)。 根據(jù)均勻分布的隨機數(shù)求指數(shù)分布的方法（反變換法）： 令 u 是取值為0，1范圍內(nèi)服從均勻分布的隨機變量，即 反變換法要求用 u 對 F(A)或 F(S) 進行取樣，即令 可得：,離散事件系統(tǒng)仿真舉例,事件調(diào)度法程序結(jié)構(gòu)： 事件類型表 仿真結(jié)果： 理論計算結(jié)果： 由 可得 所以,仿真鐘初始化，系統(tǒng)狀態(tài)初始化 事件表初始化，統(tǒng)計計數(shù)初始化,主程序,輸入仿真控制參數(shù),調(diào)用初始化子程序,調(diào)用時間控制程序,調(diào)用事件 I 子程序,仿真結(jié)束否？,調(diào)用輸出 報告子程序,主程序,操作事件表，確定下一個最早發(fā)生的事件（類型 I ）；推進仿真鐘,修改系統(tǒng)狀態(tài)，修改統(tǒng)計計數(shù)器 產(chǎn)生將來事件，加到事件表中,根據(jù)統(tǒng)計計數(shù)器進行統(tǒng)計分析 打印輸出報告,初始化子程序,時間控制 子程序,報告產(chǎn)生器,時間類型,服務(wù)結(jié)束，離開系統(tǒng),事件描述,屬性