理論模型建模方法課件

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

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

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

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

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

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

(3)活動(Activity)實(shí)體在一段時間內(nèi)持續(xù)進(jìn)行的操作或過程。活動所占用的時間區(qū)段稱為忙期(duration)，忙期可以是定時的或隨機(jī)的。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

例3.1中假定：

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

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

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

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

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

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

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

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

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)，有標(biāo)記和無標(biāo)記，則稱該庫所為條件。(6)事件涉及條件的變遷稱為事件。(7)容量庫所對儲存資源的數(shù)量限制稱為庫所的容量。3.4.1Petri網(wǎng)的基本概念1．基本術(shù)語552．Petri網(wǎng)的數(shù)學(xué)結(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是兩集合的直積運(yùn)算。(3)令F所含有序偶的第一個元素和第二個元素所成的集合分別為dom(F)和cod(F)，滿足，這意味著N不能有孤立元素，P、T、F均不能為空集。我們把不屬于dom(F)和cod(F)的元素叫做孤立元素。

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

定義3.4.1一個Petri56定義3.4.2元素的輸入集和輸出集設(shè)為網(wǎng)N(S，T；F)的一個元素，令則稱為x的輸入集或前集；稱為x的輸出集或后集。Petri網(wǎng)的標(biāo)準(zhǔn)圖形表示是用圓圈代表庫所，用方框或豎線表示變遷，用從x到y(tǒng)的有向弧表示序偶（x,y)。如果(x，y)是從x到y(tǒng)的有向?。头Qx是y的輸入，y是x的輸出。定義3.4.2元素的輸入集和輸出集設(shè)為網(wǎng)57Petri網(wǎng)建模的基本步驟1、辨明系統(tǒng)中的實(shí)體及其屬性2、分析確定各類實(shí)體的活動和狀態(tài)，以及各個活動發(fā)生和結(jié)束對應(yīng)的事件，同時分析狀態(tài)和事件的邏輯順序關(guān)系。3、將實(shí)體的狀態(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)中的實(shí)體及其屬性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)購票者到達(dá)(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容量、標(biāo)識和權(quán)設(shè)N=(S，T;F)是有向網(wǎng)，則(1)映射K：稱為N上的一個容量函數(shù)。對于表示s的容量為無窮(2)若K是N上的容量函數(shù)．映射M：稱為N的一個標(biāo)識的充要條件是,均滿足(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)線，它要完成兩項(xiàng)工業(yè)操作，這個操作用t1和t2表示。第一個變遷t1將傳入生產(chǎn)線的半成品sl和部件s2用兩個螺絲釘s3固定在一起，變成半成品s4。第二個變遷再將s4和部件s5用3個螺絲釘s3固定在一起，得到新的半成品fs。完成入和4操作時都要用到工具s7。假定由于存放空間的限制，停放在生產(chǎn)線上的半成品s4,最多不能超過5件。首先看一個例子。有一條工業(yè)生產(chǎn)線，它要完成兩項(xiàng)工業(yè)操作63用K給出的數(shù)字說明某一庫所中允許存放資源的最大數(shù)量，即為庫所的容量值。未加標(biāo)注的庫所容量為無窮大。庫所中的黑點(diǎn)數(shù)表示該庫所當(dāng)前的實(shí)際資源／產(chǎn)品數(shù)。這里，同一庫所中的資源或產(chǎn)品被看作是完全等價的個體，均用黑點(diǎn)表示；黑點(diǎn)稱為令牌或標(biāo)記，各個庫所中的黑點(diǎn)數(shù)就是標(biāo)識。

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

定義3.4.5中的變遷條件和發(fā)生規(guī)則可以解釋如下：(1)一個變遷被授權(quán)發(fā)生，當(dāng)且僅當(dāng)該變遷的每一個輸入庫所中的令牌致大于或等于輸入弧的權(quán)值，并且該變遷的輸出庫所中已有的令牌數(shù)與輸出孤權(quán)值之和小于輸出庫所的容量；簡單地說就是“前面夠用，后面夠放”。(2)變遷發(fā)生(點(diǎn)火)的充要條件是該變遷是授權(quán)的。(3)變遷發(fā)生時，從該變遷的輸入庫所中移出與輸入弧權(quán)值相等的令牌數(shù)，在輸出庫所中產(chǎn)生與輸出弧權(quán)值相等的令牌數(shù)。定義3.4.5中的變遷條件和發(fā)生規(guī)則可以解釋如下：67理論模型建模方法課件68根據(jù)容量函數(shù)和權(quán)函數(shù)的持點(diǎn)，可將網(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表示事件集合，則標(biāo)識可以用B的子集表示。因此基本網(wǎng)系統(tǒng)用4元組(B，E，F(xiàn)，C0)表示。C0是網(wǎng)系統(tǒng)的初始標(biāo)識。稱為事件的前置條件，稱為事件的后置條件。事件e發(fā)生的條件是前置條件為真而后置條件為值。根據(jù)容量函數(shù)和權(quán)函數(shù)的持點(diǎn)，可將網(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)的主要特點(diǎn)(1)能很好地描述和表達(dá)系統(tǒng)中的并行、同步、沖突和因果依賴等關(guān)系，而這些關(guān)系在離散事件動態(tài)系統(tǒng)(DEDS)建模中是經(jīng)常遇到的。(2)有堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)，有語義清晰的語法，這為進(jìn)行形式化分析提供了良好的條件。至今，已提出了多種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ǔ)上直接實(shí)現(xiàn)控制系統(tǒng)。5．Petri網(wǎng)的主要特點(diǎn)72例3.9加工車間Petri網(wǎng)系統(tǒng)某加工車間有3臺不同的機(jī)器M1、M2和M3；兩個操作工F1和F2，操作工F1可以操作機(jī)器M1和M2，操作工F2可以操作機(jī)器M1和M3。工件分為兩個階段加工，第1階段必須用機(jī)器M1加工，第2階段可用M2或M3加工。當(dāng)M2和M3均處于空閑狀態(tài)時，工件在M2上加工；否則哪個空閑就在哪個上面加工。試建立該加工車間的Petri網(wǎng)系統(tǒng)模型。例3.9加工車間Petri網(wǎng)系統(tǒng)某加工車間有3臺不同73（1）一個自動面包售貨機(jī)的Petri網(wǎng)圖所示為一個自動面包售貨機(jī)的Petri網(wǎng)圖，該售貨機(jī)可接收0.5元和1.0元的硬幣，銷售價格為1.5元和2.0元的面包。售貨機(jī)的最大硬幣儲存量為2.0元，其最初儲存量為0元，以庫所P1中放置一個標(biāo)記作為初始標(biāo)識。在這個Petri網(wǎng)中的每個變遷都正好有一條輸入弧和一條輸出弧，具有這種性質(zhì)的Petri網(wǎng)子類叫做狀態(tài)機(jī)。圖中5個狀態(tài)0，0.5，l，1.5和2元分別由5個庫所表示；狀態(tài)的變換由變遷表示的輸入條件決定，諸如投“0.5元”等。（1）一個自動面包售貨機(jī)的Petri網(wǎng)圖所示為一個自動面包74

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