1、第三章 離散系統仿真概述離散系統的狀態只是在離散時間點上發生變化，而且這些離散時間點一般是隨機的。離散系統的數學模型通常用流程圖或網絡圖來描述。離散仿真的目的是實體的活動以找出(分析)系統的(潛在)行為。離散仿真事件(event)時間因變量隨(事件)時間離散變化。因變量時間基本概念實體 構成系統的各種成分稱為實體，系統的研究對象。 臨時實體、永久實體。屬性 反映實體的某些性質。狀態 在某一確定時間點，系統的狀態是系統中所有實體屬性的集合?；靖拍钍录?引起系統狀態發生變化的行為，它是在某一時間點上的瞬間行為。活動 實體在某一狀態的持續過程。進程 進程由和實體相關的事件及若干活動組成，一個進程描

2、述了它所包括的事件及活動間的相互邏輯關系和時序關系。車輛到達事件服務開始事件服務結束事件服務活動進程排隊活動事件、活動、進程三者之間的關系基本概念仿真時鐘 仿真時鐘用于表示仿真時間的變化，仿真時鐘推進的時間間隔稱為時間步長。 時間步長法、事件步長法統計計數器 離散系統的狀態隨事件的不斷發生呈現動態變化過程，這種動態變化過程在統計意義下才有參考價值。 統計計數器用于記錄仿真規程中系統性能的統計信息。離散仿真模型建立步驟定義系統的參變量集合，構造系統映象；定義事件類型及其發生時點；定義每一事件時間發生狀態變化的點；描述系統中實體的活動；構造狀態轉移函數或算法；通過系統流圖描述整個過程。構造初始映象

3、找一個盡可能簡單的系統狀態作為初始狀態；從一個遠離平衡狀態但容易構造的狀態開始進行模擬，當運行一段時間之后，系統的狀態會接近或處于穩定狀態（平衡狀態）。離散仿真中的關鍵問題事件取舍： 確定改變系統狀態的事件集，并將它們用邏輯關系聯系起來。 系統仿真就是靠按順序執行聯系這些事件的邏輯來實現的。 活動掃描： 要描述系統中實體的活動，設定引起活動開始及結束的條件。啟動或結束活動的事件不由建模者設定，而隨仿真推進而自動進行。為保證活動得到記錄，每一次推進均需要掃描活動中的實體集。 由于需要在每一次推進中掃描每一活動，這種方法的效率不太高。過程定位： 提供整個仿真過程中實體流的一種用仿真語言描述的方法。

4、系統仿真的推進時間步長法 以固定的時間間隔進行驅動；事件步長法 按下一類最早發生事件的發生時間推進。t時間步長法在進行系統仿真的同時，把整個仿真過程分為許多相等的時間間隔，程序按此步長前進的時鐘就是仿真時鐘。在每個時間間隔做如下處理：該步內若無事件發生，則仿真時鐘再推進一個單位時間；若在該步內有若干個事件發生，則認為這些事件均發生在這一步的結束時刻，同時必須規定當出現這種情況時各類事件處理的優先順序。掃描與處理方法對每一類事件或每一個主導實體設置一個模擬時鐘，以此記錄和控制實體活動的延續時間。對系統實體進行掃描；對系統事件進行掃描；對事件和實體結合起來進行掃描。改變狀態，預測下一事件。時間步長

5、法流程圖事件步長法仿真時鐘不斷地從一個事件發生時間推進到下一個最早發生事件的發生時間。以事件發生的時間點相互間隔作為步長，按照時間的進展，一步一步地對系統的行為進行仿真，直到預定的仿真時間為止。事件表按照事件發生時間先后順序安排事件，將仿真過程看作一個事件點序列。事件控制部件始終從事件表中選擇最早發生時間的事件記錄，然后將仿真時鐘該事件發生的時刻。時鐘推進舉例模擬運行150個時間單位，顧客到達事件、顧客服務完畢離去事件，Ti到達時間間隔，Si第i個顧客服務時間，Di第i個顧客等待時間，Ci= Ti+Si+Di第i個顧客離開系統的時間, qi第i個顧客排隊的對長，bi模擬時鐘推進到第i次的時間，

6、Zi第i個事件發生時服務員的狀態。 Ti=15,32,24,40,22,； Si=43,36,34,28, 初始狀態： q0=0, Z0=0求： bi 、Ci、離散系統仿真程序的結構狀態變量；時鐘變量；事件表（按時間順序記錄仿真過程中將要發生的事件）統計計數器初始化子程序時鐘推進子程序 （由事件表確定下一事件，然后將將仿真時鐘推進到該事件發生的時間）調度子程序（將仿真過程中產生的未來事件插入事件表）離散系統仿真程序的結構事件子程序 每一類事件對應一個事件子程序，相應的事件發生時就轉入該事件子程序進行處理，更新系統狀態，產生新的事件。統計報告子程序隨機數發生器主程序 調用時鐘推進子程序，控制轉移

7、到相應的事件子程序，完成仿真程序的總體控制。離散系統仿真程序流程圖離散系統仿真策略建立描述系統行為的仿真模型 由于系統采用偽隨機數，可以得到確定的狀態轉移函數，模型采用流程圖或網絡圖的形式。仿真策略 仿真策略決定仿真模型的結構模型描述中采用的主要術語成分 相當于系統中的實體，用于構造模型中的各個部分。主動成分 （可以主動產生活動的成分） 被動成分 （本身不激發活動，只有在主動成分作用下才能產生狀態變化）描述變量 成分狀態、屬性的描述。成分間的相互關系 描述成分之間相互影響的規律。模型描述中采用的符號C=a1,a2,an為成分集合； CA=a1,a2,am為主動成分子集合；CP=a1,a2,ah

8、為被動成分子集合；Sa為成分a的狀態變量；P=p1,p2,pr為參數（屬性）集合；ta為成分a的狀態下一發生變化的時刻;Da(S)為成分a在狀態變量值S時的條件變量;TIME為模擬時鐘的值。典型仿真策略事件調度法活動描述法進程交互法事件調度法通過定義事件及每個事件發生對系統狀態的變化，按時間順序確定并執行每個事件發生時有關的邏輯關系。所有事件均放在事件表中，模型中設有一個時間控制機構，該機構從事件表中選取最早發生時刻的事件。以事件種類為控制依據，不同種類事件的處理進入相應的事件處理模塊，并在時間處理完畢返回時間控制機構。事件調度法模型的基本結構事件調度算法初始時間t= t0、事件表初始化、置系

9、統初始事件;成分表初始化S =(Sa1,ta1), (Sam,tam), Sam+1, San);操作事件表，取出t =min ta|aCA ，修改事件表;推進時鐘 TIME= t(s);While (TIMETIMEFRESENT(S)=a|ta=TIMEPAST(S)=a|taTIMETIME=min(ta|a FUTURE(S)活動掃描法的算法初始時間t= t0、設置主動成分的模擬時鐘ta(i);成分狀態初始化S =(Sa1,ta1), (Sam,tam), Sam+1, San);設置系統時鐘 TIME= t0;While (TIME= t)，執行掃描 for j=最高優先數到最低優先

10、數 將優先數為j的成分置成i if （ tai(i)= TIME 且 Dai(S)= true） 執行活動子例程 endif endfor TIME=min(ta|aFUTURE(S) endwhile按活動掃描法建立的排對系統模型進程交互法進程由事件的時間序列及若干活動組成具有上述兩種方法的特點，接近實際系統，編程實現非常復雜采用進程描述系統，將模型的主動成分所發生的事件及活動按照時間順序進行組合形成進程表，一個成分一旦進入進程，它將完成進程的全部活動。進程交互法采用兩張事件表，當前事件表、將來事件表；當仿真時鐘推進，滿足條件的所有事件記錄從將來事件表移到當前事件表，取出每個事件記錄，判斷所

11、屬進程與位置，當發生條件真，發生包含該事件的活動，并讓該進程盡可能地推進，直至結束。時間控制以主導實體進入該進程的的時間序列及其經歷該進程的各項活動的時間順序，走向控制主要以斷點為依據。以進程為基礎的排隊系統模型幾種仿真策略的比較系統描述事件調度法中，只有主動成分才能施加作用；事件調度法中，系統的動態特性表現為主動成分不斷產生事件；活動掃描法中表現為主動成分產生活動；進程交互法中則是通過成分在其進程中一步一步地推進描述。 幾種仿真策略的比較建模要點事件調度法中，用戶要對所定義的全部事件進行建 模，條件測試只能在事件處理子程序中進行； 活動掃描法設置了一個條件子例程用于條件測試，還設置了一個活動

12、掃描模塊，該模塊對所定義的活動進行建模； 進程交互法將一個進程分成若干步，每一步包括條件測試及執行活動兩部分。 幾種仿真策略的比較時鐘推進事件調度法中，控制機構從事件表中取出最早發生時間的事件記錄，將時鐘推進到該時刻，執行該事件處理子程序； 活動掃描法除系統時鐘外，每一個主動成分還有成分模擬子時鐘，控制機構選取那些大于當前系統時鐘且所有成分模擬時鐘最小的那個成分模擬時鐘，將系統時鐘推進到該時鐘； 進程交互法中，一旦某個進程被執行，要求盡可能走下去，但并不改變系統時鐘。如果該進程未完成，記錄中斷時間及事件類型放入將來事件表。幾種仿真策略的比較執行控制事件調度法按下一最早發生時間選擇事件記錄； 活

13、動掃描法對全部活動掃描，只有Dai(S)=true且taiTIME的活動才能被執行； 進程交互法對當前事件表中所有的記錄掃描，根據該事件在其進程中的指針進行條件判斷。當Dai(S)=true 執行該進程，并一直執行下去，否則記下斷點。 幾種仿真策略的比較事件調度法建模靈活，建模工作量大；活動掃描法對于各成分相關性很強的系統來說模型效率較高，但執行程序結構復雜；進程交互法建模最直觀，模型表示接近實際系統特別適用于可以預測、順序比較確定的系統，但流程控制復雜，建模靈活性不好。適用性系統中的各個成分相關性較少，宜采用事件調度法，反之宜采用活動掃描法；系統成分的活動比較規則，宜采用進程交互法。排隊系統

14、仿真某個時刻要求服務的的數量超過服務機構的容量。到達模式：顧客按怎樣的規律到達；服務機構：同一時刻有多少服務臺可接納顧客；排隊規則：服務臺完成當前的服務后，從對列選擇下一個實體服務的原則。到達模式平均到達間隔時間Ta=T/n；平均到達率 =1/Ta ；到達間隔時間分布函數；1-F(t)到達時間變化系數Sa/Ta ；服務機構一個或多個服務員，沒有服務員；多個服務臺，并列、串列、混合；單獨服務，成批服務；服務時間，確定、隨機；排隊規則先到先服務FIFO；后到先服務LIFO；隨機服務SIRO；優先權服務PR；最短處理時間先服務SPT。系統容量有限；無限。排隊模型分類A/B/C/D/E A:到達模式；

15、B:服務模式；C:并行服務員的數目； D:系統容量；E:排隊規則。常見的到達和服務間隔時間分布：M(指數分布)、 G(確定型分布)、 M(一般隨機分布)；M/M/1/FIFO排隊系統的特征量服務員利用率P=平均服務時間/平均到達間隔時間；系統中平均顧客數P/1- P；系統內排隊等待的顧客數P2/1- P ；顧客在系統內的停留時間；平均等待時間；系統出現大于n個顧客的概率。研討多隊多服務臺排隊系統模擬 以多出納臺銀行系統為例（換對原則）系統中的成分成分狀態變量系統中的初始狀態顧客到達間隔時間服從的分布 服務時間服從的分布 事件顧客到達銀行顧客完成服務后離開顧客換對銀行關閉系統指標平均等待時間平均對長最大等待時間最大對長多級串聯封閉式排隊系統模擬基于主導實體活動掃描法的模擬模型從一種稱為主導實