第2章離散事件系統仿真的基本知識主講人：趙月霞zhaoyuexia@物流系統建模與仿真本章主要內容DEDS的概念DEDS的基本要素

DEDS仿真的基本步驟仿真實例物流系統建模與仿真1.DEDS的概念根據仿真的研究對象，系統仿真可以分成連續系統仿真和離散事件系統仿真（DiscreteEventDynamicSystem

）。離散事件系統的特點是：系統的狀態變化只在離散點上發生，且發生的時刻往往是隨機的，系統的狀態變化是由隨機事件驅動的。舉例：排隊系統生產領域和物流領域的大多數系統為離散事件系統物流系統建模與仿真2.1離散事件系統的基本要素5個基本要素：實體、屬性、事件、活動、進程。實體：系統中我們感興趣的對象。屬性：實體的屬性或性質。活動:具有一定時間長度的任務或工作事件:導致系統狀態改變的瞬間行為。進程：在一些更確切的術語中，進程是事件、活動和延遲按時間順序排列的表，這個表定義了一個實體經過系統時的生命周期。延遲：與活動相比，延遲的持續時間不由建模者事先指定，而是由系統條件決定的。狀態：變量集，它們包含描述系統在任何時間所必需的所有信息。注：分析系統必須要首先明確仿真目的物流系統建模與仿真顧客n的進程時間到達事件開始服務結束服務事件延遲活動Dump-TruckProblem

：6輛翻斗車用于從小煤礦到鐵路裝卸煤。每一輛車由兩臺裝載機之一進行裝煤。裝載完畢后，卡車立即開到地秤處盡可能快地稱重。物流系統建模與仿真以排隊系統和庫存系統為例。在倉儲系統中，貨物是臨時實體；貨位、搬運機器是永久實體。屬性：貨物的幾何物理特性、到達時間間隔、到達批量。事件：貨物入庫，物品出庫。活動：存儲。在銀行排隊系統中，顧客和服務員是實體，顧客到達時間間隔、服務時間是屬性，事件：顧客到達和顧客離去。狀態變量：隊列長度和服務員忙閑程度。思考：請在下列系統中命名一些實體、屬性、事件、活動和進程：零售商店，汽車總裝線，醫院手術室，銀行儲蓄所。物流系統建模與仿真仿真鐘：定義：仿真模型中用來記錄仿真當前時刻的變量。仿真鐘的推進有兩種經典方法：固定步長推進法和變步長推進法。舉例物流系統建模與仿真統計累加器離散事件系統的狀態變量隨著事件的不斷發生而呈現出動態變化的過程。由于這種變化是隨機性的，某一次仿真運行得到的狀態變化過程，只不過是隨機過程的一次取樣，它們只有在統計意義下才有參考價值。因此，需要有一個統計累加器構建，用來跟蹤記錄各種輸出性能指標在仿真進程中的中間結果。物流系統建模與仿真2.2蒙特卡羅方法

2.2.1蒙特卡羅方法的基本思想

2.2.2蒙特卡羅方法的應用

物流系統建模與仿真102.2.1蒙特卡羅方法的基本思想

蒙特卡羅（MonteCarlo）方法，也稱為隨機抽樣方法或統計測試方法，是一種與一般數值計算方法有本質區別的計算方法，屬于實驗數學的一個分支。基本思想：當實驗次數充分多時，某一事件出現的頻率近似等于該事件發生的概率。即：當N充分大時，有（2-1）2.2蒙特卡羅方法物流系統建模與仿真式中，p為某一事件發生的概率；

N為實驗次數；

n在N次實驗中該事件出現的次數。物流系統建模與仿真圖2-3運用蒙特卡羅方法的隨機采樣來求解圓面積圖2-4進行多次采樣的蒙特卡羅方法計算單位圓面積的值物流系統建模與仿真132.2.2蒙特卡羅方法的應用應用蒙特卡羅方法進行仿真分析的原理利用各種不同分布隨機變量的抽樣序列來仿真實際系統的概率模型，給出問題數值解的漸近統計估計值。要點如下對問題建立一個簡單且便于實現的概率統計模型，使要求的解恰好是所建模型的概率分布或數學期望；物流系統建模與仿真根據概率統計模型的特點和實際計算的需要，對模型進行改進，以便減小仿真結果的方差，降低成本、提高效率；建立隨機變量的抽樣方法，其中包括產生偽隨機數及各種分布隨機變量抽樣序列的方法；給出問題解的統計估計值及其方差或標準差。物流系統建模與仿真15蒙特卡羅方法應用或實施過程的三個主要步驟構造或描述概率過程

以已知概率分布進行抽樣建立各種估計量物流系統建模與仿真排隊系統仿真實例（教材第二章2~5節）排隊系統的關鍵元素是顧客和服務臺。“顧客”可以指到達設施并請求服務的任何事物，“服務臺”可以指能夠提供所需服務的任何資源。系統顧客服務臺修車廠車維修人員醫院病人醫生生產線箱子打包機洗衣店臟衣服洗衣機公共交通乘客公共汽車公路網絡汽車交通燈.........物流系統建模與仿真1排隊系統的3個基本組成部分：到達模式：顧客的到達規律服務模式：服務臺的個數和服務時間排隊規則：服務時對顧客的選取規則嚴格意義上來說，一個排隊系統由擬到達總體、到達種類、服務機制、系統容量和排隊規則來描述。Kendall[1953]提出了一種被廣泛應用的描述并行服務臺系統的符號體系。其簡單版本基于A/B/c/N/K的形式。A--到達時間間隔的分布B--服務時間的分布c--并行服務臺的個數N--系統的容量K--擬到達總體的大小物流系統建模與仿真2排隊系統常用的輸出參數平均等待時間平均通過系統的時間平均隊長系統中平均滯留的實體數服務臺利用率......物流系統建模與仿真3排隊理論與排隊仿真分析的關系在優化排隊系統時，分析者通常要在服務臺利用率和顧客滿意度之間做出權衡。1）對于一些簡單的系統，系統的性能指標可以通過數學的方法計算出來。與使用仿真模型相比，可以節省時間和費用。2）對于復雜系統的模型，通常通過先做出許多簡化假設，轉變為易解析處理的模型，對系統性能進行粗略評價。然后通過詳細的，更接近實際的仿真模型，對這些粗略的評價進行優化。以下實例僅為較簡單的說明仿真的過程，不是要真正解決系統的實際問題。物流系統建模與仿真Simulationbyhand步驟:

分析模型、畫出事件流程圖。確定仿真的每個輸入數據（主要指概率分布）.

構造仿真表對仿真表的每一行，進行仿真。計算統計數據.

仿真完畢，累加數據，計算性能指標。物流系統建模與仿真例題：單隊列排隊系統顧客以1-8min分鐘等概率分布到達CheckoutCounter（見Table2.6)。服務員的服務時間為1－6min(概率見Table2.7)要求：仿真6個顧客，以分析系統的性能。物流系統建模與仿真第1步：分析模型

實體：服務員、顧客

系統狀態:

顧客數目、服務員狀態（Busy,Idle)

事件：顧客到達事件(ArrivalEvent)

離開事件（DepartureEvent)

活動：

服務、排隊等待（Delay)

仿真時鐘（SimulationClock):

用來記錄當前仿真的時刻。物流系統建模與仿真事件流程圖（ExecutionofEvent)定義：對于每個事件，都有唯一的一個事件流程圖。它表示系統如何對這個事件進行處理、執行。物流系統建模與仿真“離開事件”流程圖（簡化版）圖4.1離開事件（服務完成）的流程圖物流系統建模與仿真到達事件”流程圖（簡化版）圖4.2顧客到達事件的流程圖物流系統建模與仿真第2步：確定仿真的輸入數據—顧客到達間隔、服務時間。（通過查表得到）到達間隔時間/min概率累計概率隨機數區間10.1250.125001～12520.1250.250126～25030.1250.375251～37540.1250.500376～50050.1250.625501～62560.1250.750626～75070.1250.875751～87580.1251.000876～1000服務時間/min概率累計概率隨機數區間10.100.1001～1020.200.3011～3030.300.6031～6040.250.8561～8550.100.9586～9560.051.0095～100表2.6表2.7物流系統建模與仿真到達時間間隔的確定customerrandomdigitstimebetweenarrivals1264131121(由112查表2.6得到)467865289368717物流系統建模與仿真服務時間的確定customerrandomdigitstimebetweenarrivals184421823875(由87查表2.7得到)48145616915物流系統建模與仿真第3步：構造仿真表。（手算仿真的本質是仿真表格）顧客到達間隔到達時間服務時間等待時間服務結束時間逗留時間服務員空閑時間10

4

物流系統建模與仿真第4步：對每個顧客進行仿真顧客到達間隔到達時間服務時間等待時間服務結束時間逗留時間服務員空閑時間1

04044

2112365031254

11

9

0

468

43

15

7

0

5311

14

16

5

0

6718

50

23

5

2

物流系統建模與仿真第5步：匯總統計數據

顧客的平均等待時間顧客必須等待的概率服務員空閑的比例平均服務時間平均到達間隔時間等待顧客的平均等待時間顧客在系統中的平均逗留時間物流系統建模與仿真平均等待時間=顧客在隊列中等待的總時間/總顧客數顧客必須在隊列中等待的概率=等待的顧客數/總顧客數服務臺空閑的概率=服務臺空閑的總時間/仿真的總運行時間平均服務時間=總服務時間/總顧客數顧客在系統中花費的平均時間=顧客在系統中花費的總時間/總顧客數物流系統建模與仿真報紙經銷商問題仿真（教材第6節）問題描述：報紙的訂購與銷售問題是一個經典的庫存問題。報攤以33美分買進每張報紙，以50美分賣出。當日結束時銷售不完的報紙作為廢品處理，每份賣5美分。報紙以10份為一捆訂購，因此，報攤可以買50份，60份等等。有三種類型的報紙，分別是良、中和差，他們的概率是0.35,0.45和0.20。每天對于報紙需求的分布見下表2-15。要解決的問題是，計算報攤應該訂購報紙的最優數量。為完成這項工作進行了20天的仿真并記錄了每天的利潤。利潤按以下公式計算：利潤=銷售收入-報紙成本-額外需求的利潤損失+報廢報紙的回收費物流系統建模與仿真需求需求概率分布良中差400.030.100.44500.050.180.22600.150.400.16700.200.200.12800.350.080.06900.150.040.001000.070.000.00表2-15每天報紙需求量的分布報紙類型概率累計概率隨機數字分配良0.350.3501～35中0.450.8036～80差0.201.0081～100表2-16報紙類型的隨機數字分布物流系統建模與仿真需求需求概率分布隨機數字分配良中差良中差400.030.100.4401～0301～1001～44500.080.280.6604～0811～2845～66600.230.680.8209～2329～6867～82700.430.880.9624～4369～8883～94800.780.961.0044～7889～9695～100900.931.001.0079～9397～100—1001.001.001.0094～100—

表2-17報紙需求的隨機數字分布物流系統建模與仿真用仿真來解決這一問題，需要設定每天購買的報紙數量（購買策略），進行周期20天的報紙需求仿真來確定總利潤。改變購買策略，重復運行仿真直至找到最佳的值。表2-18為每天訂購70份報紙策略的仿真表格。物流系統建模與仿真天報紙類型的隨機數字報紙類型需求的隨機數字需求銷售收入格外需求的利潤損失廢品回收收入每日利潤158中9380351.7—10.2217良6380

35

1.7

—

10.2

321良3170

35

—

—

11.9

445中1950

25

—

1

2.9

543中9180

35

1.7

—

10.2

……

表2-18物流系統建模與仿真

(M,N)庫存系統---上限訂貨庫存系統的仿真（補充）訂貨Leadtime=0Backorder顧客需求物流系統建模與仿真庫存模型庫存成本:－持有成本(carryingcost):購買貨物的利息、倉庫的租借、人力雇傭。－訂購成本：－損失成本庫存模型的目的：最小化總成本。訂購量=上限訂貨水平-盤點庫存量+短缺量；訂貨將首先滿足短缺；(M,N)庫存模型的研究目的：對不同的M,N組合，哪個成本最小？物流系統建模與仿真系統模型狀態：

庫存水平事件：

“顧客需求”事件（出庫）“庫存檢查”事件（清庫）“訂單到達”事件（入庫）物流系統建模與仿真(M,N)庫存系統仿真（冰箱）Example2.4庫存容量M＝11.庫存檢查周期N=5天.仿真開始時，期初庫存為3.

訂購只可能發生在庫存檢查的時刻（每個檢查周期的最后一天下班）！訂購數量為:

訂購數量=庫存容量－期末庫存＋缺貨數量(backorder）物流系統建模與仿真問題說明：每天需求的冰箱數量為隨機數，可能為0、1、2、3、4件。其概率分別對應于0.10、0.25、0.35、0.21、0.09。如表2.19所示。訂單的前置期（lead-time)可能為1、2、3天，其概率分別為0.6、0.3、0.1。如表2.20所示。仿真要求：（1）仿真開始時，有3個冰箱在庫存。訂購的8個冰箱將在2天后到達。（2）庫存容量M=11,庫存檢查周期N＝5仿真目的：預測系統的期末平均庫存、平均缺貨數量等。物流系統建模與仿真需求概率累計概率隨機數區間00.100.1001～1010.250.3511～3520.350.7036～7030.210.9171～9140.091.0092～100表2.19日需求量的隨機數字分配表物流系統建模與仿真表2.20訂單前置期的隨機數字分配前置期概率累計概率隨機數字分配區間10.60.6

1－620.30.9

7－930.11

10物流系統建模與仿真Table2.21(M,N)庫存系統仿真表(冰箱）天周期期初庫存隨機數字－需求需求期末庫存缺貨數量訂購數量隨機數字-前置期前置期訂單到達還需的天數113261

2

0

--

--

--

1

21

2

682

0

0

--

--

--

--

3

1

8

331

7

0

--

--

--

--

4

1

7

392

5

0

--

--

--

--

5

1

5

863

2

0

9

82

2

6

22

181

1

0

--

--

--

1

7

2

1

642

0

1

--

--

--

--

8

2

9

793

5

0

--

--

--

--

9

2

5

552

3

0

--

--

--

--

10

2

3

743

0

0

11

72

2

11

30

211

0

1

--

--

--

--

12

3

0

432

0

3

--

--

--

--

13

3

11

492

6

0

--

--

--

--

14

3

6

903

3

0

--

--

--

--

15

3

5

351

2

0

9

21

1物流系統建模與仿真(M,N)庫存系統性能分析期末庫存均值平均缺貨數量物流系統建模與仿真本章學習提示明確手工仿真的目的掌握手工仿真的步驟。課下思考學習：1）執行(M,N)庫存系統手工仿真表的第2個周期，理解事件流程圖在仿真過程中的作用。2）圖片給出了報童模型問題，請有興趣的同學參考。物流系統建模與仿真2.3離散事件系統仿真步驟1）確定仿真目標：針對所關心的問題不同，建立的系統模型、設定的輸入變量和輸出變量都各不相同。確定仿真目標是是系統調研和建模的依據。2）進行系統調研：系統調研時了解系統運行狀況和采集系統數據資料的過程。（將調研所獲取的數據和參數整理列表，由需求方進行針對性的填寫，保證資料的完整性和準確性）3）建立系統模型：系統模型由模型和模型參數兩部分組成離散事件系統模型最常用的是建立系統的流程圖模型。物流系統建模與仿真4）確定仿真算法仿真算法是控制仿真鐘推進的方法，是系統仿真的核心。目前最常用的有事件調度法、活動掃描法和進程交互法。5）建立仿真模型6）驗證與確認模型模型的驗證主要檢驗所建立的仿真模型（包括系統組成的假設、系統結構、參數及其取值、對系統的簡化和抽象）能否被準確地描述成可執行的模型。模型的確認則是考察所建立的模型及模型的運行特征能否代表所要研究的實際系統物流系統建模與仿真驗證主要是檢驗所建立的仿真模型是否被準確的描述為可執行的模型。（計算機程序可以正常運行嗎？模型的輸入參數和邏輯結構被計算機正確表達了嗎？）方法1）仿真低速運行時，觀看動畫和仿真鐘是否同步運行。方法2）通過交互命令窗口，顯示動態圖，詢問資源和流動項目的屬性和狀態。方法3）輸入多組仿真參數值，驗證仿真結果是否合理。物流系統建模與仿真確認模型是考察所建立的模型及模型的運行特征是否能夠代表所