理論模型建模方法課件

第三章理論模型建模方法第三章理論模型建模方法1本章內(nèi)容要求：1、掌握實體流圖法、活動周期法、Petri網(wǎng)法、Euler網(wǎng)法建模的基本原理。2、能夠應(yīng)用所學建模方法建立并分析實際系統(tǒng)模型重點：實體流圖法、Petri網(wǎng)法本章內(nèi)容要求：2本章介紹幾種典型的離散事件建模方法。

實體流圖法與計算機程序流程圖的方法類似，可以描述臨時實體產(chǎn)生、流動、消亡及其被永久實體加工、處理的過程和邏輯關(guān)系。

活動周期圖法針對實體的行為模式進行建模，可以直觀地表示出某類實體生命周期中的活動和狀況、具有規(guī)范化的特點。Petri網(wǎng)方法適于建立加工系統(tǒng)等多種離散事件系統(tǒng)的模型，并可對網(wǎng)系統(tǒng)的特性進行比較嚴密的數(shù)學分析，得到對并發(fā)、沖突、死鎖等現(xiàn)象的深刻認識，應(yīng)用也比較廣泛。Euler網(wǎng)方法以圖論和網(wǎng)論為數(shù)學描述語言,貫穿了面向?qū)ο蟮慕Ｋ枷?，描述方法比較規(guī)范，可以建立連續(xù)—離散事件混合系統(tǒng)模型，方法的通用性較強。

本章介紹幾種典型的離散事件建模方法。33.1基本概念和術(shù)語(1)實體(Entity)實體是構(gòu)成系統(tǒng)的可單獨辨識和描述的功能單元。例如．工廠中的機器，商店中的服務(wù)員，生產(chǎn)線上的工件，交通道路上的車輛等。屬性和行為相同或相近的實體可以用一類來描述，這樣做可以簡化系統(tǒng)的組成和關(guān)系。例如，理發(fā)店服務(wù)系統(tǒng)可以看成是由“服務(wù)員”和“顧客”兩類實體組成的.而兩類實體之間存在服務(wù)與被服務(wù)的關(guān)系。3.1基本概念和術(shù)語(1)實體(Entity)實體是構(gòu)4(2)屬性(Attribute)屬性是實體特征的描述．一般是實體所擁有的全部特征的一個子集，用特征參數(shù)或變量表示。選用哪些特征參數(shù)作為實體的屬性與建模目的有關(guān),可參照下述原則選?。?/p>

①便于實體的分類：例如將理發(fā)店顧客的性別(“男”或“女”）作為屬性考慮，可將“顧客”實體分為二類．每類顧客占用不同的服務(wù)臺。②便于實體行為的描述例如將飛機的飛行速度作為屆性考慮．便于對“飛機”實體的行為(如兩地間的飛行時間)進行描述。③便于排隊規(guī)則的確定

例如生產(chǎn)線上待處理工件的優(yōu)先級水平有時需考慮為便于“按優(yōu)先級排隊”規(guī)則的建立和實現(xiàn)。(2)屬性(Attribute)屬性是實體特征的描述5

(3)活動(Activity)實體在一段時間內(nèi)持續(xù)進行的操作或過程?；顒铀加玫臅r間區(qū)段稱為忙期(duration)，忙期可以是定時的或隨機的。

(4)狀態(tài)(State)對實體活動的特征狀況或性態(tài)的劃分，其表征量稱為狀態(tài)變量。在理發(fā)店服務(wù)系統(tǒng)模型中，“顧客”有“等待服務(wù)”、“接受服務(wù)”等狀態(tài)，“服務(wù)員”有“忙”和“閑’’等狀態(tài)?；顒涌偸桥c一個或幾個實體的狀態(tài)相對應(yīng)。狀態(tài)可作為動態(tài)屬性進行描述。

(5)事件(Event)導(dǎo)致系統(tǒng)狀態(tài)產(chǎn)生變化的瞬間操作或行為。事件發(fā)生的時刻稱為事件點。不關(guān)心事件所代表的操作和行為意義時，事件與事件點是同義語。若事件的發(fā)生是有前提的．則稱為條件事件。

活動、狀態(tài)和事件三者間的聯(lián)系:由子事件的發(fā)生會導(dǎo)致狀態(tài)的變化，而實體的活動可以與一定的狀態(tài)相對應(yīng)，因此可以用事件來標識活動的開始和結(jié)束。其間的關(guān)系如圖3.1所示，圖中S表示狀態(tài)，A表示活動，E表示事件，P表示進程。(3)活動(Activity)6

(6)進程(Process)一組按發(fā)生時間排列的事件／活動序列稱為一個進程。

(7)隊列(Queue)處于等待狀態(tài)的實體序列。一般按新到的實體排在隊后的次序組成隊列。離散事件建模中，隊列可作為一種狀態(tài)或特殊實體對待。圖3.1活動、狀態(tài)、事件及進程(6)進程(Process)圖3.1活動、狀態(tài)、事73．2實體流圖法3．2．1實體流圖

在離散事件系統(tǒng)中，實體可以分為兩大類：臨時實體和永久實體。

臨時實體按一定規(guī)律由系統(tǒng)外部到達系統(tǒng)，在系統(tǒng)中接受永久實體的作用，按照一定的流程通過系統(tǒng)，最后離開系統(tǒng)。

例如進入商店購物的顧客、交通路口的車輛、生產(chǎn)線上的電視機、進人防空火力網(wǎng)的戰(zhàn)斗機，駛?cè)氲叵峦＼噲龅钠嚨取?/p>

與臨時實體相反、那些永久駐留在系統(tǒng)中的實體稱為永久實體。系統(tǒng)要對臨時實體產(chǎn)生作用，就必須有永久實體的活動，臨時實體和永久實體協(xié)同完成某項活動．如理發(fā)店的理發(fā)員，生產(chǎn)線上的加工、裝配機械，交通路口的紅綠燈等，都是永久實體的例子。3．2實體流圖法3．2．1實體流圖8

實體流圖法（entityflowchart,EFC)采用與計算機程序流程圖相類似的圖示符號和原理，建立表示臨時實體產(chǎn)生、在系統(tǒng)中流動、接受永久實體“服務(wù)”以及消失等過程的流程圖。借助實體流程圖、可以表示事件、狀態(tài)變化及實體間相互作用的邏輯關(guān)系。

建立實際系統(tǒng)的實體流圖模型一是要對實際系統(tǒng)的工作過程有深刻的理解和認識，二是要將事件、狀態(tài)變化、活動和隊列等概念貫穿于建模過程中。常用的圖示符號只有菱形框(表示判斷)、矩形框(表示事件、狀態(tài)、活動等中間過程)、圓端矩形框(表示開始和結(jié)束)及箭頭線(表示邏輯關(guān)系)等。實體流圖法（entityflowchart,E9建模時可按照以下思路進行：

(1)辨識組成系統(tǒng)的實體及屬性。將隊列作為一種特殊的實體來考慮。(2)分析各種實體的狀態(tài)和活動，及其相互間影響，隊列實體的狀態(tài)是隊列的長度。(3)考察有哪些事件導(dǎo)致了活動的開始或結(jié)束，或者可以作為活動開始或結(jié)束的標志，以確定引起實體狀態(tài)變化的事件，并合并條件事件。(4)分析各種事件發(fā)生時，實體狀態(tài)的變化規(guī)律。(5)在一定的服務(wù)流程下，分析與隊列實體有關(guān)的特殊操作(如換隊等)。(6)通過以上分析，以臨時實體的流動為主線，用約定的圖示符號畫出鎮(zhèn)仿真系統(tǒng)的實體流程圖。(7)給出模型參數(shù)的取值、參變量的計算方法及屬性描述變量的取值方法。屬性描述變量，例如顧客到達時間、服務(wù)時間等，可以取一組固定值，可以由某一計算公式取值．還可以是一個隨機變量。屬性描述變量是隨機變量時，應(yīng)給出其分布函數(shù)。(8)給出隊列的排隊規(guī)則。有多個隊列存在時，還應(yīng)給出其服務(wù)規(guī)則．包括隊列的優(yōu)先序、換隊規(guī)則等。建模時可按照以下思路進行：10(1)辨識系統(tǒng)實體（2）分析實體狀態(tài)變化情況(1)辨識系統(tǒng)實體（2）分析實體狀態(tài)變化情況11（3）分析引起狀態(tài)變化的事件(4)分析隊列實體的操作

“顧客到達”或“顧客結(jié)束排隊”可以導(dǎo)致“服務(wù)”活動的開始，面“顧客理完離去”可以導(dǎo)致“服務(wù)”活動的結(jié)束，因此這三件事情均可作為事件看待。但是,由于”顧客結(jié)束排隊”是以理發(fā)員狀態(tài)是“閑”為條件的，因此是條件事件；而隊列狀態(tài)為“非零”時理發(fā)員狀態(tài)為“閑”是由事件“顧客理完離去”導(dǎo)致的,因此將“顧客結(jié)束排隊”事件并入“顧客理完離去”事件，不予單獨考慮。這是實體流圖法建模的一般原則?！邦櫩偷竭_”將使理發(fā)員由“閑”變?yōu)椤懊Α?，或使“隊列長度”加1?！邦櫩屠硗觌x去”將使理發(fā)員由“忙”變?yōu)椤伴e”?！邦櫩徒Y(jié)束排隊”將使“隊列長度”減1，并使理發(fā)員由“閑”變?yōu)椤懊Α?。由于本問題中只有一個隊列，面且顧客不會因排隊人數(shù)太多而離去、因此隊列規(guī)則很簡單，沒有特殊的隊列操作。（3）分析引起狀態(tài)變化的事件(4)分析隊列實體的操作“顧客12（5）畫出系統(tǒng)實體流程圖通過以上分析，以顧客活動為主線畫出理發(fā)店服務(wù)系統(tǒng)的實體流圖。NoYES顧客排隊等待顧客進入隊列有其他顧客離開顧客排在隊首No顧客到達進入理發(fā)店理發(fā)員閑置理發(fā)員為忙顧客開始理發(fā)接受理發(fā)服務(wù)顧客理完離去置理發(fā)員為閑YES（5）畫出系統(tǒng)實體流程圖通過以上分析，以顧客活動13(6)確定模型參變量需給出的模型屬性變量有：顧客的到達時間（隨機變量）、理發(fā)員為一個顧客理發(fā)所需的服務(wù)時間（隨機變量）等，它們的值可分別從不同的分布函數(shù)中抽取。（7）給出排隊規(guī)則隊列的排隊規(guī)則是先到先服務(wù)（FIFO），即每到一名顧客就排在隊尾，服務(wù)員先為排在隊首的顧客服務(wù).(6)確定模型參變量需給出的模型屬性變量有：顧客的到達時14例3.2分時計算機系統(tǒng)分時計算機系統(tǒng)由一個CPU和多臺計算機輸入終端組成(圖3.3）。用戶從終端輸入作業(yè)，請求CPU為其服務(wù)。所有終端輸入的作業(yè)由一個CPU執(zhí)行，因而形成單一隊列。CPU按FIFO(先進先出)的服務(wù)規(guī)則分時輪流為各終端的作業(yè)服務(wù)。如果一個作業(yè)的CPU執(zhí)行時間大于一個時間片te，則該任務(wù)執(zhí)行一段時間te后退出CPU，并重新參加排隊。只有當某一終端發(fā)出的服務(wù)請求執(zhí)行完畢退出CPU后，才允許該終端重新輸入一個新的作業(yè)，建模的目的是研究用戶的等待時間。例3.2分時計算機系統(tǒng)分時計算機系統(tǒng)由一個C15實體活動狀態(tài)用戶輸入作業(yè)等待輸入輸入等候CPU執(zhí)行作業(yè)等待作業(yè)忙閑作業(yè)輸入作業(yè)進入隊列執(zhí)行作業(yè)接受輸入等待執(zhí)行接受處理隊列隊列長度分時計算機系統(tǒng)實體列表本系統(tǒng)的實體為計算機用戶、計算機的CPU及用戶請求執(zhí)行的作業(yè)，其中前二類實體是水久實體。作業(yè)是臨時實體。實體活動狀態(tài)用戶輸入作業(yè)輸入CP16實體狀態(tài)變化對應(yīng)的活動活動開始事件活動結(jié)束事件變化前變化后用戶輸入等候等待輸入輸入完畢作業(yè)執(zhí)行完畢等候輸入輸入作業(yè)前一作業(yè)執(zhí)行完畢輸入完畢CPU閑忙執(zhí)行作業(yè)接到作業(yè)請求執(zhí)行完畢或執(zhí)行了一個時間片忙閑等待作業(yè)執(zhí)行完畢或執(zhí)行了一個時間片接到作業(yè)請求作業(yè)接受輸入等待執(zhí)行進入隊列輸入完畢前一作業(yè)執(zhí)行完畢等待執(zhí)行接受處理執(zhí)行作業(yè)前一作業(yè)執(zhí)行完畢作業(yè)執(zhí)行完畢接受處理接受輸入輸入作業(yè)作業(yè)執(zhí)行完畢輸入完畢長度1+1作業(yè)進入隊列長度-1隊首作業(yè)開始執(zhí)行分時計算機系統(tǒng)活動與事件關(guān)系狀態(tài)變化變化前變化后用戶輸入等候等待輸入輸入完畢作業(yè)17假定作業(yè)“輸入完畢”到CPU“接到執(zhí)行請求”之間無時間延遲。則可將二者看成同一事件。根據(jù)與例3．1同樣的理由，“開始輸入”和“作業(yè)結(jié)柬排隊”均為條件事件，且均可并入“執(zhí)行完畢”事件處理。另外，“作業(yè)執(zhí)行了一個時間片”與“執(zhí)行完畢”標志著同樣的事件處理—只是前者發(fā)生時需將作業(yè)送去重新排隊，因此可看作同一類事件。這樣模型中只需考慮“輸入完畢”和“執(zhí)行完畢或執(zhí)行了一個時間片”兩種類型的事件即可。要注意作業(yè)的輸入(到達)是有條件的且需耗費一定的時間；而且，執(zhí)行作業(yè)的結(jié)束(離去)可能是暫時的，也可能是永久的，需要加以判斷。模型參數(shù)包括：終端數(shù)量，時間片長度、輔助操作時間(若一個作業(yè)在一個時間片內(nèi)執(zhí)行不完，CPU為完成該作業(yè)重新入隊并從隊列中取出下一作業(yè)所需要的時間)。模型屬性變量有：作業(yè)輸入時間(隨機變量)、作業(yè)所需執(zhí)行的時間(隨機變量）等排隊規(guī)則同例3．1。假定作業(yè)“輸入完畢”到CPU“接到執(zhí)行請求”之間無時間延遲。18開始前一作業(yè)執(zhí)行完畢開始輸入輸入完畢CPU閑置CPU為忙開始執(zhí)行作業(yè)作業(yè)執(zhí)行完置CPU為閑用戶等待作業(yè)等待NOYESNONOYESYES執(zhí)行完一個時間片其他作業(yè)執(zhí)行完一個時間片作業(yè)排在隊首開始前一作業(yè)執(zhí)行完畢開始輸入輸入完畢CPU閑置CPU為忙開始19例3.3劇院雇傭一名售票員同時負責劇票的窗口銷售和對電話問訊者的咨詢服務(wù)。購票者按先到先服務(wù)的原則在窗口排隊買票，問訊者打來的電話由電話系統(tǒng)存儲后按先來先服務(wù)的原則一一予以答復(fù)，電話服務(wù)比窗口服務(wù)有更高的優(yōu)先級。售票員正在售票時若有電話打入，則售票員必須完成本次售票活動后再接聽電話。系統(tǒng)建模的目的是研究售票員的忙閑率。本系統(tǒng)有—個永久實體，即售票員、售祟員有“窗口售票”和“電話服務(wù)”兩種活動，狀態(tài)包括‘空閑”、“回電話”和“售票”。電話問訊者和購票者為兩類臨時實體，其行為模式均與例3．1中的顧客實體類似。本例與前二個例子的主要區(qū)別是有兩條服務(wù)途徑，因此可同時存在二個隊列，但顧客不可能換隊。實體流圖模型如圖3.5所示。例3.3劇院雇傭一名售票員同時負責劇票的窗口銷售和對電話20電話撥入購票者到達售票員閑售票員閑有電話同時接入購票者進入隊列售票員完成一個服務(wù)置售票員為忙電話撥入排在隊首售票員完成一個服務(wù)電話進入隊列電話隊列為空排在隊首開始電話服務(wù)開始售票服務(wù)電話服務(wù)完畢售票服務(wù)完畢置售票員為閑YESNoYESYESYESYESYESYESNoNoNoNoNoNo圖3.5售票窗口服務(wù)系統(tǒng)實體流圖電話撥入購票者到達售票員閑售票員閑有電話同時接入購票者進入隊21模型屬性變量有“購票者到達時間”、“電話問訊者到達時間”、“售票服務(wù)時間”和“電話服務(wù)時間”，均為隨機變量。排隊規(guī)則為FIFO，服務(wù)規(guī)則是“窗口購票者和電話問訊者分別排隊，優(yōu)先進行電話服務(wù)”。注意，圖3.5中有二處是與服務(wù)規(guī)則有關(guān)的判斷相特殊操作。當“電話問訊者”和“窗口購票音”同時到達而售票員處于“閑”狀態(tài)時，前者接受服務(wù)，后者加入購票者隊列；當服務(wù)完畢而購票隊列和電話隊列均不為空時，先進行電話服務(wù)。模型屬性變量有“購票者到達時間”、“電話問訊者到達時間223.2.2模型的人工運行

建立實體流圖模型后，選取有代表性的例子將流圖全部走一遍，即所謂人工運行。人工運行模型要求遍歷流圖的各個分支和實體的各種可能狀態(tài)，在時間逐步變化的動態(tài)條件下，分析事件的發(fā)生及狀態(tài)的變化過程、以檢查模型酌組成和邏輯關(guān)系是否正確。

例3.1中假定：

(1)系統(tǒng)的初始狀態(tài)永久實體“理發(fā)員”的狀態(tài)及特殊實體“隊列”的狀態(tài)。所謂初始時刻是指仿真開始的時刻，可以對應(yīng)為實際系統(tǒng)(理發(fā)店)開門營業(yè)的時間。此時，理發(fā)員為“閑”，隊列長度是o。

(2)模型參數(shù)及變量的取值本模型的變量包括第i個顧客與第i-1個顧客到達的時間間隔Ai．以及理發(fā)員為第i個顧客的理發(fā)時間Si。一般說來，Ai,Si均為隨機變量，應(yīng)根據(jù)其分布函數(shù)來產(chǎn)生。這里，為了便于解釋．取其樣本值為A1=15A2=32A3=24A4=40A5=22,…3.2.2模型的人工運行

建立實體流圖模型后，23模型需按一定的規(guī)則運行。本模型的人工運行規(guī)則如下：

規(guī)則1——確定當前時間模型人工運行開始時，取當前時間，TIME=t0(t0為仿真初始時刻)。人工運行開始后，當前時間逐步向前推移．且遞取下一最早發(fā)生事件的發(fā)生時刻。如果當前時間有顧客到達事件發(fā)生，轉(zhuǎn)規(guī)則2；若有顧客離去事件發(fā)生，則轉(zhuǎn)規(guī)則3。

規(guī)則2——顧客到達事件處理假定在時刻TIME有顧客i到達。根據(jù)圖3.2知，如果此時理發(fā)員忙。則入隊列等待．隊列長度加上1,否則置理發(fā)員為“忙”狀態(tài)，顧客開始理發(fā)，且在di＝TIME+Si時刻理畢離去。

規(guī)則3----顧客離去事件處理

假定在時刻了TIME有顧客i離去。根據(jù)圖3．2知，如果此時隊列長度為0，則置理發(fā)員為”閑”狀態(tài);否則,隊列中排在隊首的一名顧客開始理發(fā)，隊列長度減去1.并且該顧客在di＝TIME+Si時刻理畢離去。模型需按一定的規(guī)則運行。本模型的人工運行規(guī)則如下：24理論模型建模方法課件25理論模型建模方法課件26理論模型建模方法課件273.3活動周期圖法在上節(jié)關(guān)于實體流圖法的介紹中，我們可以看到這樣一種現(xiàn)象：實體的行為模式在有限的幾種情況之間周而復(fù)始地變化．表現(xiàn)出一定的生命周期形式。例如，例3．1中的理發(fā)員實體的狀態(tài)在“閑”和“忙”之間不斷變化．而“忙”狀態(tài)意味著理發(fā)員與顧客協(xié)同完成“理發(fā)”活動。顧客實體是臨時實體，雖然單個實體僅在系統(tǒng)中停留一段時間，但是顧客實體的群體行為則是在“到達”、“等待”、“理發(fā)”和“離去”之間周而復(fù)始地變化，出現(xiàn)局而復(fù)姑的行為模式?；顒又芷趫D(ActivltycycLeDi“8ram，AcD)正是基于這樣一種思想逐步形成的一種離散事件建模方法。活動周期圖以直觀的方式顯示了實體的狀態(tài)變化歷程和各實體之間的交互作用關(guān)系，便于理解和分析?；顒又芷趫D可以充分反映各類實體的行為模式，并將系統(tǒng)的狀態(tài)變化以“個體”狀態(tài)變化的集合方式表示出來，因此可以更好地表達眾多實體的并發(fā)活動和實體之間的協(xié)同。但是，它只描述了系統(tǒng)的穩(wěn)態(tài)，而沒有表示系統(tǒng)的瞬態(tài)，即活動的開始和結(jié)束事件。3.3活動周期圖法在上節(jié)關(guān)于實體流圖法的介紹中，我們可以283.3.1活動周期圖實體狀態(tài)：靜寂(Dead)和激活（Active)靜寂狀態(tài)（無活動）激活狀態(tài)（活動）ACD基本圖符不同實體采用不同線型顧客理發(fā)員3.3.1活動周期圖實體狀態(tài)：靜寂(Dead)和激活29活動周期圖的建模過程：(1)辨識系統(tǒng)的實體組成及其屬性(2)分別畫出各實體活動周期圖遵循原則：a交替原則靜寂狀態(tài)與激活狀態(tài)必須交替出現(xiàn)。直聯(lián)活動與前置活動之間存在虛擬的隊列。b閉合原則臨時實體的活動周期圖表示一個或單位實體從產(chǎn)生到消失的循環(huán)過程。(3)將各實體的活動聯(lián)接成系統(tǒng)活動周期圖（以協(xié)同活動為紐帶）(4)增添必要的虛擬實體活動周期圖的建模過程：(1)辨識系統(tǒng)的實體組成及其屬性30(5)標明活動發(fā)生的約束條件和占用的資源數(shù)量包括：a活動活動是否可以發(fā)生的判斷條件（表達式）b永久實體在參加一次協(xié)同活動所占用的資源數(shù)量（＋/－符號）(6)給出模型參數(shù)的取值，參變量的計算方法及屬性描述變量的取值方法并給出排隊規(guī)則和服務(wù)規(guī)則。(5)標明活動發(fā)生的約束條件和占用的資源數(shù)量31例3.4機床加工系統(tǒng)

例3.4機床加工系統(tǒng)322)機床三種激活狀態(tài)：安裝刀具（RETOOL)、安裝工件（RESET)、加工（RUNNING)2)機床三種激活狀態(tài)：安裝刀具（RETOOL)、安裝工件（333)將工人和機床活動周期圖合并3)將工人和機床活動周期圖合并34理論模型建模方法課件35確定模型的參變量和屬性描述模型參數(shù)：1、機床數(shù)量2、累計加工工件數(shù)3、累計加工時間屬性變量：1、加工工件時間2、安裝刀具時間3、安裝工件時間4、飲茶時間5、輪休時間確定模型的參變量和屬性描述模型參數(shù)：36例3.5售票窗口服務(wù)系統(tǒng)三類實體：售票員、窗口購票者、電話問詢者1、售票員兩種激活：窗口售票、電話服務(wù)例3.5售票窗口服務(wù)系統(tǒng)三類實體：售票員、窗口購票者、電372、窗口售票者激活狀態(tài)—窗口服務(wù)，到達靜寂狀態(tài)—排隊等待、外部2、窗口售票者激活狀態(tài)—窗口服務(wù)，到達383、電話問詢者激活狀態(tài)—電話服務(wù)、打電話靜寂狀態(tài)—等接電話、局外3、電話問詢者激活狀態(tài)—電話服務(wù)、打電話39理論模型建模方法課件40例3.6貨物轉(zhuǎn)運系統(tǒng)例3.6貨物轉(zhuǎn)運系統(tǒng)41實體：大貨車、小貨車、卸貨倉位、工人、進站通道和出站通道實體：大貨車、小貨車、卸貨倉位、工人、進站通道和出站通道422）小貨車2）小貨車433）裝卸倉位3）裝卸倉位444）進出通道4）進出通道455）裝卸工人5）裝卸工人46貨物轉(zhuǎn)運系統(tǒng)活動周期圖貨物轉(zhuǎn)運系統(tǒng)活動周期圖47理論模型建模方法課件48理論模型建模方法課件49以機床加工系統(tǒng)為例以機床加工系統(tǒng)為例50理論模型建模方法課件51理論模型建模方法課件52實體流圖法和活動周期圖之間的區(qū)別及各自的特點(1)實體流程圖(以下簡稱為EFC)是以臨時實體在系統(tǒng)中的流動過程為主線建立的模型、永久實體濃縮于表示狀態(tài)和事件的圖示符號之中，隊列被作為一種特殊的實體來對待。對這三種實體的描述交織在一起、使得各類臨時和永久實體沒有單獨的圖示。活動周期圖ACD則基于各類臨時和水久實體的行為模式，它們均有其單獨的圖示表達，隊列很自然地成為實體生命周期中的一種狀態(tài)。(2)ACD中，各類實體的圖示是“環(huán)形”的循環(huán)圖，整個系統(tǒng)的ACD由多個環(huán)套在一起組成；而EFC則是帶有小循環(huán)的“樹形”流程團。(3)事件是EFC的重要組成部分，在EFC中有顯式的表達，而在ACD中，事件蘊含在活動之中，沒有顯式表達。(4)狀態(tài)判斷框在EFC中的作用十分重要。ACD將EFC中需作判斷的狀態(tài)用“空閑”、“等待”等靜寂狀態(tài)表示，而對實體是否處于該狀態(tài)的判斷則勿需標在圖中．因為它已升華為模型運行時的一般規(guī)則。實際上．根據(jù)EFC人工運行規(guī)則，每一個靜寂狀態(tài)都有“條件”的底蘊．(5)從人工運行規(guī)則來看，ACD存在普適性很強的運行規(guī)則，它與每個具體的ACD無關(guān)；而EFC的運行規(guī)則中只有第1條是通用的(體現(xiàn)了事件調(diào)度法)，其它各條均從具體的EFC中抽取，普適性很差。(6)由(1)和(5)知，ACD更易于用而向?qū)ο蟮募夹g(shù)實現(xiàn)，軟件上也更易于實現(xiàn)仿真程序的自動生成。另外．由(1)知，ACD表示沖突和并發(fā)現(xiàn)象更方便、直觀。(7)正是由于EFC沒有ACD那樣規(guī)范，因此如果不考慮模型的遠行間題，EFC比ACD的適用范圍更廣。另外，EFC中可以對隊列的排隊規(guī)則和服務(wù)規(guī)則進行比較詳細的描述。實體流圖法和活動周期圖之間的區(qū)別及各自的特點(1)實體533.4Petri網(wǎng)方法對活動周期圖建模方法作以下改變：(1)取消臨時實體ACD中的“源”狀態(tài)”，即不再考慮臨時實體的生命周期循環(huán)；(2)將活動看作是“開始事件+狀態(tài)+結(jié)束事件”，這樣一來，建模的元素就變成“事件”和“狀態(tài)”，后者包括ACD中的激活狀態(tài)和靜寂狀態(tài).(3)不強調(diào)實體模型之間的獨立性。

3.4Petri網(wǎng)方法對活動周期圖建模方法作以下改543.4.1Petri網(wǎng)的基本概念1．基本術(shù)語

(1)資源與系統(tǒng)狀態(tài)發(fā)生變化有關(guān)的因京，稱為資源。如原料、部件、產(chǎn)品(成品或半成品)、人員、工具、設(shè)備、數(shù)據(jù)及信息等。(2)狀態(tài)元素資源按其在系統(tǒng)巾的作用分類，每一類存放一處，則該處抽象為一個相應(yīng)的狀態(tài)元素。(3)庫所狀態(tài)元索又稱庫所。它不僅表示一個場所，而且表示在該場所存放了一定的資源(4)變遷資源的消耗、使用及產(chǎn)生對應(yīng)于狀態(tài)元素的變化，網(wǎng)論中將此變化叫做變遷。

(5)條件如果一個庫所只有兩種狀態(tài)，有標記和無標記，則稱該庫所為條件。(6)事件涉及條件的變遷稱為事件。(7)容量庫所對儲存資源的數(shù)量限制稱為庫所的容量。3.4.1Petri網(wǎng)的基本概念1．基本術(shù)語552．Petri網(wǎng)的數(shù)學結(jié)構(gòu)

定義3.4.1一個Petri網(wǎng)(PN)是一個三元組N(S，T，F(xiàn))，式中(1)S和T分別是庫所和變遷的有限集，滿足(2)F是由一個S元素和一個T元素組成的有序偶的集合，叫做流關(guān)系，滿足，X是兩集合的直積運算。(3)令F所含有序偶的第一個元素和第二個元素所成的集合分別為dom(F)和cod(F)，滿足，這意味著N不能有孤立元素，P、T、F均不能為空集。我們把不屬于dom(F)和cod(F)的元素叫做孤立元素。

2．Petri網(wǎng)的數(shù)學結(jié)構(gòu)

定義3.4.1一個Petri56定義3.4.2元素的輸入集和輸出集設(shè)為網(wǎng)N(S，T；F)的一個元素，令則稱為x的輸入集或前集；稱為x的輸出集或后集。Petri網(wǎng)的標準圖形表示是用圓圈代表庫所，用方框或豎線表示變遷，用從x到y(tǒng)的有向弧表示序偶（x,y)。如果(x，y)是從x到y(tǒng)的有向弧．就稱x是y的輸入，y是x的輸出。定義3.4.2元素的輸入集和輸出集設(shè)為網(wǎng)57Petri網(wǎng)建模的基本步驟1、辨明系統(tǒng)中的實體及其屬性2、分析確定各類實體的活動和狀態(tài)，以及各個活動發(fā)生和結(jié)束對應(yīng)的事件，同時分析狀態(tài)和事件的邏輯順序關(guān)系。3、將實體的狀態(tài)作為庫所，將事件作為變遷。根據(jù)狀態(tài)和事件的順序關(guān)系，按照庫所和變遷相互交替的原則，畫出系統(tǒng)的Petri網(wǎng)模型。4、模型參數(shù)和屬性描述變量根據(jù)網(wǎng)系統(tǒng)的特性確定Petri網(wǎng)建模的基本步驟1、辨明系統(tǒng)中的實體及其屬性58圖1為Petri網(wǎng)的圖形表示。用公式表示可寫作N＝(S，T，F(xiàn))，其中庫所集S{s1,s2,s3,s4},變遷集T={t1,t2,t3},流關(guān)系F={（t1,s1),(s2,t1),(s3,t1),(s3,t3),(t3,s4),(s4,t2),(t2,s3),(t2,s3),(t2,s2)}.圖1為Petri網(wǎng)的圖形表示。用公式表示可寫作N＝(S，T，59例3.7售票窗口服務(wù)模型庫所集：(a)購票者等待(b)售票員為購票者售票(c)購買票的顧客(d)售票員閑(e)問訊者等待(f)售票員為問訊者咨詢(g)問訊完的顧容變遷集：(1)購票者到達(2)開始購栗(3)購票畢(4)購票者離去(5)問訊電話打入(6)開始詢問(7)問訊畢(8)問訊者離開例3.7售票窗口服務(wù)模型庫所集：變遷集：603.4.2網(wǎng)系統(tǒng)網(wǎng)是系統(tǒng)靜態(tài)結(jié)構(gòu)的基本描述，要模擬系統(tǒng)的動態(tài)特性．需要定義網(wǎng)系統(tǒng)。

定義3．4．3容量、標識和權(quán)設(shè)N=(S，T;F)是有向網(wǎng)，則(1)映射K：稱為N上的一個容量函數(shù)。對于表示s的容量為無窮(2)若K是N上的容量函數(shù)．映射M：稱為N的一個標識的充要條件是,均滿足(3)映射稱為N的權(quán)函數(shù)。W在弧(x，y)上的值用W(x，y)表示。3.4.2網(wǎng)系統(tǒng)網(wǎng)是系統(tǒng)靜態(tài)結(jié)構(gòu)的基本描述61理論模型建模方法課件62首先看一個例子。有一條工業(yè)生產(chǎn)線，它要完成兩項工業(yè)操作，這個操作用t1和t2表示。第一個變遷t1將傳入生產(chǎn)線的半成品sl和部件s2用兩個螺絲釘s3固定在一起，變成半成品s4。第二個變遷再將s4和部件s5用3個螺絲釘s3固定在一起，得到新的半成品fs。完成入和4操作時都要用到工具s7。假定由于存放空間的限制，停放在生產(chǎn)線上的半成品s4,最多不能超過5件。首先看一個例子。有一條工業(yè)生產(chǎn)線，它要完成兩項工業(yè)操作63用K給出的數(shù)字說明某一庫所中允許存放資源的最大數(shù)量，即為庫所的容量值。未加標注的庫所容量為無窮大。庫所中的黑點數(shù)表示該庫所當前的實際資源／產(chǎn)品數(shù)。這里，同一庫所中的資源或產(chǎn)品被看作是完全等價的個體，均用黑點表示；黑點稱為令牌或標記，各個庫所中的黑點數(shù)就是標識。

更一般化的說明如下：(1)容量K(s)表示庫所S中允許存放令牌的最大數(shù)量，其值標在表示庫所的圓圈旁；不標明時容量為(2)權(quán)W(x,y)表示變遷發(fā)生時消耗和產(chǎn)出的令牌數(shù)量，其值標在弧(x，y)上；不標明時表示權(quán)為1。(3)令牌表示原料、部件、產(chǎn)品、人員、工具、設(shè)備、數(shù)據(jù)和信息等組成系統(tǒng)的“資源”，標識M(s)的值用令牌數(shù)表示，而令牌則表示為庫所中的黑點。用K給出的數(shù)字說明某一庫所中允許存放資源的最大數(shù)量，即64理論模型建模方法課件65理論模型建模方法課件66

定義3.4.5中的變遷條件和發(fā)生規(guī)則可以解釋如下：(1)一個變遷被授權(quán)發(fā)生，當且僅當該變遷的每一個輸入庫所中的令牌致大于或等于輸入弧的權(quán)值，并且該變遷的輸出庫所中已有的令牌數(shù)與輸出孤權(quán)值之和小于輸出庫所的容量；簡單地說就是“前面夠用，后面夠放”。(2)變遷發(fā)生(點火)的充要條件是該變遷是授權(quán)的。(3)變遷發(fā)生時，從該變遷的輸入庫所中移出與輸入弧權(quán)值相等的令牌數(shù)，在輸出庫所中產(chǎn)生與輸出弧權(quán)值相等的令牌數(shù)。定義3.4.5中的變遷條件和發(fā)生規(guī)則可以解釋如下：67理論模型建模方法課件68根據(jù)容量函數(shù)和權(quán)函數(shù)的持點，可將網(wǎng)系統(tǒng)分為3類。（1)庫所／變遷網(wǎng)系統(tǒng)或P/T網(wǎng)系統(tǒng)它的形式就是定義3.4.3中給出的6元組(S,T;F,K,W;M0),其中K和W取任意值。(2)條件／事件系統(tǒng)或C/E網(wǎng)系統(tǒng)C/E網(wǎng)也稱基本網(wǎng)系統(tǒng)。它的容量函數(shù)和權(quán)函數(shù)均取常值1，是P/T網(wǎng)系統(tǒng)在K=W=1時的特例?；揪W(wǎng)系統(tǒng)中，庫所只有兩種狀態(tài)：有一個令牌或無令牌，因此稱為條件。令牌條件滿足(取真值)，無令牌條件不滿足(取假值)。相應(yīng)地，基本網(wǎng)系統(tǒng)中變遷稱為事件。用B表示條件集合，E表示事件集合，則標識可以用B的子集表示。因此基本網(wǎng)系統(tǒng)用4元組(B，E，F(xiàn)，C0)表示。C0是網(wǎng)系統(tǒng)的初始標識。稱為事件的前置條件，稱為事件的后置條件。事件e發(fā)生的條件是前置條件為真而后置條件為值。根據(jù)容量函數(shù)和權(quán)函數(shù)的持點，可將網(wǎng)系統(tǒng)分為3類。69(3)Petri網(wǎng)系統(tǒng)

它是P/T網(wǎng)系統(tǒng)在而時的特例。Petri網(wǎng)系統(tǒng)可用4元組表示。Petri網(wǎng)系統(tǒng)中，變遷發(fā)生的條件是其所有輸入庫所中均至少含有一個令牌。(3)Petri網(wǎng)系統(tǒng)

它是P/T網(wǎng)系統(tǒng)在70列舉了主要的5種關(guān)系。圖中：(a)表示事件t1和t2為先后關(guān)系；(b)t2和t3為并發(fā)關(guān)系；(c)t1和t2為沖突關(guān)系；(d)t1、t2、t3為迷惑關(guān)系，取決于它們的發(fā)生次序；(e)t1和t2為死鎖關(guān)系，事件不可能發(fā)生。列舉了主要的5種關(guān)系。圖中：(a)表示事件t1和t2為先后關(guān)715．Petri網(wǎng)的主要特點(1)能很好地描述和表達系統(tǒng)中的并行、同步、沖突和因果依賴等關(guān)系，而這些關(guān)系在離散事件動態(tài)系統(tǒng)(DEDS)建模中是經(jīng)常遇到的。(2)有堅實的數(shù)學基礎(chǔ)，有語義清晰的語法，這為進行形式化分析提供了良好的條件。至今，已提出了多種Petri網(wǎng)的形式化分析方法。(3)以圖形方式描述系統(tǒng)，使復(fù)雜系統(tǒng)形象化，使人更易理解，降低了建模難度，提高了模型的易讀性。(4)可以分層次建立Petri網(wǎng)圖，適合于描述如柔性制造系統(tǒng)(FMS)那樣的分布式遞階結(jié)構(gòu)。(5)與系統(tǒng)結(jié)構(gòu)關(guān)系密切，既可描述系統(tǒng)內(nèi)部的數(shù)據(jù)流，又可描述系統(tǒng)內(nèi)部的物流，易于在控制模型的基礎(chǔ)上直接實現(xiàn)控制系統(tǒng)。5．Petri網(wǎng)的主要特點72例3.9加工車間Petri網(wǎng)系統(tǒng)某加工車間有3臺不同的機器M1、M2和M3；兩個操作工F1和F2，操作工F1可以操作機器M1和M2，操作工F2可以操作機器M1和M3。工件分為兩個階段加工，第1階段必須用機器M1加工，第2階段可用M2或M3加工。當M2和M3均處于空閑狀態(tài)時，工件在M2上加工；否則哪個空閑就在哪個上面加工。試建立該加工車間的Petri網(wǎng)系統(tǒng)模型。例3.9加工車間Petri網(wǎng)系統(tǒng)某加工車間有3臺不同73（1）一個自動面包售貨機的Petri網(wǎng)圖所示為一個自動面包售貨機的Petri網(wǎng)圖，該售貨機可接收0.5元和1.0元的硬幣，銷售價格為1.5元和2.0元的面包。售貨機的最大硬幣儲存量為2.0元，其最初儲存量為0元，以庫所P1中放置一個標記作為初始標識。在這個Petri網(wǎng)中的每個變遷都正好有一條輸入弧和一條輸出弧，具有這種性質(zhì)的Petri網(wǎng)子類叫做狀態(tài)機。圖中5個狀態(tài)0，0.5，l，1.5和2元分別由5個庫所表示；狀態(tài)的變換由變遷表示的輸入條件決定，諸如投“0.5元”等。（1）一個自動面包售貨機的Petri網(wǎng)圖所示為一個自動面包74

(2)數(shù)據(jù)流計算圖為一個數(shù)據(jù)流計算的Petri網(wǎng)圖。圖中標