《管理系統(tǒng)模擬》PPT課件.ppt

管理系統(tǒng)模擬,系統(tǒng)研究的有效方法,哈爾濱工業(yè)大學(xué)管理學(xué)院 馬維忠副教授 ,管理科學(xué)與工程系列課程,緒論,討論一些概念 引出模擬的概念,管理系統(tǒng)模擬 馬維忠,3,概念,系統(tǒng)？ System 元素 關(guān)系 集合 系統(tǒng)研究：物理、解析。 模型？ Model 模擬=仿真？ Simulation Modelling & Simulation,管理系統(tǒng)模擬 馬維忠,4,用途,有必要仿真的情形： 1 系統(tǒng)不存在 2 在系統(tǒng)上實(shí)驗(yàn)會(huì)造成破壞或損失 3 系統(tǒng)無(wú)法恢復(fù) 4 實(shí)驗(yàn)條件無(wú)法保障,管理系統(tǒng)模擬 馬維忠,5,類(lèi)型,仿真分類(lèi)： 物理仿真 數(shù)學(xué)仿真 物力-數(shù)學(xué)仿真,管理系統(tǒng)模擬 馬維忠,6,計(jì)算機(jī)的作用,計(jì)算機(jī)仿真常用于以下幾種情況： 難以建立數(shù)學(xué)模型，無(wú)法用數(shù)學(xué)公式表示； 數(shù)學(xué)模型過(guò)于復(fù)雜，而用計(jì)算機(jī)仿真能提供簡(jiǎn)單的方法 系統(tǒng)的運(yùn)行由于費(fèi)用過(guò)高或者有一定的危險(xiǎn)性，不適合實(shí)際運(yùn)行，比如研究航天飛船的飛行 某些數(shù)學(xué)模型可通過(guò)計(jì)算機(jī)仿真進(jìn)行檢驗(yàn),管理系統(tǒng)模擬 馬維忠,7,管理系統(tǒng),連續(xù)系統(tǒng) 離散（事件）系統(tǒng),管理系統(tǒng)模擬 馬維忠,8,課程內(nèi)容 一、數(shù)理統(tǒng)計(jì)基礎(chǔ) 二、概念模型及建模 三、物理模型及建模 四、結(jié)果分析 五、仿真模型校驗(yàn) 六、仿真語(yǔ)言與集成環(huán)境,管理系統(tǒng)模擬 馬維忠,9,參考書(shū)目,1、孫錚編，管理系統(tǒng)模擬，哈爾濱工業(yè)大學(xué)，1996 2、王維平等編著，離散事件系統(tǒng)建模與仿真，國(guó)防科技大學(xué)出版社，1997 3、顧啟泰編著，離散事件系統(tǒng)建模與仿真，清華大學(xué)出版社，1999 4、周德才等編著，計(jì)算機(jī)隨機(jī)模擬原理、方法及計(jì)算程序，華中理工大學(xué)出版社，1998 5、王維平等編著，仿真模型有效性確認(rèn)與驗(yàn)證，國(guó)防科技大學(xué)出版社，1998,管理系統(tǒng)模擬 馬維忠,10,6 何江華。計(jì)算機(jī)仿真導(dǎo)論?？茖W(xué)出版社。2001 7 黃柯棣等。系統(tǒng)仿真技術(shù)。國(guó)防科技大學(xué)出版社。1998 8 肖田元等。系統(tǒng)仿真導(dǎo)論。清華大學(xué)出版社。2000 9 陳理榮。數(shù)學(xué)建模。北京郵電大學(xué)出版社。1999,一、數(shù)理統(tǒng)計(jì)基礎(chǔ),概率論的基本概念 數(shù)值屬性的相關(guān)算法,管理系統(tǒng)模擬 馬維忠,12,本部分內(nèi)容,1 概率統(tǒng)計(jì)基本概念 2 常用的概率分布形 3 系統(tǒng)概率分布模型 4 隨機(jī)變量模型的確定 5 隨機(jī)數(shù)的產(chǎn)生 6 隨機(jī)變量的產(chǎn)生,管理系統(tǒng)模擬 馬維忠,13,1 概率統(tǒng)計(jì)基本概念,確定事件： 在給定條件下進(jìn)行的試驗(yàn)中，一定發(fā)生或一定不發(fā)生的事件稱(chēng)為必然事件和不可能事件，這類(lèi)事件是確定性的，總稱(chēng)為確定事件。,管理系統(tǒng)模擬 馬維忠,14,隨機(jī)事件： 在給定條件下進(jìn)行的試驗(yàn)中，可能發(fā)生也可能不發(fā)生，而在大量重復(fù)試驗(yàn)中卻具有某種規(guī)律性的事件，稱(chēng)為隨機(jī)事件。,管理系統(tǒng)模擬 馬維忠,15,隨機(jī)變量： 如果試驗(yàn)的每個(gè)結(jié)果用變量的一個(gè)值來(lái)表示，即變量的值根據(jù)試驗(yàn)結(jié)果來(lái)確定，因而它的取值是隨機(jī)的，而且對(duì)任意實(shí)數(shù)，是一個(gè)隨機(jī)事件，這種變量稱(chēng)為隨機(jī)變量。,管理系統(tǒng)模擬 馬維忠,16,概率： 對(duì)大量重復(fù)試驗(yàn)，得到統(tǒng)計(jì)規(guī)律的屬性， 表明事件發(fā)生的可能性大小是事件本身固有的客觀屬性。 稱(chēng)事件發(fā)生的可能性的大小為事件的概率，記為P(A)。當(dāng)試驗(yàn)次數(shù)n足夠大時(shí)，可以用事件的頻率作為事件概率的近似值，即P(A)m/n。,管理系統(tǒng)模擬 馬維忠,17,概率分布： 對(duì)于隨機(jī)變量，事件x的概率Px是實(shí)變量x的函數(shù)，稱(chēng)之為的概率分布函數(shù)，簡(jiǎn)稱(chēng)為分布函數(shù)，記為F(x),即F(x)= Px， （-x+） 離散型隨機(jī)變量可能取的值為x1,x2,xn, = xk 為一隨機(jī)事件，其發(fā)生概率記為Pk=P=xk,k=1,2,n。Pk為離散型隨機(jī)變量的概率分布，Pk滿(mǎn)足Pk0。,管理系統(tǒng)模擬 馬維忠,18,分布密度函數(shù)： 連續(xù)型隨機(jī)變量的分布函數(shù)F(x)能表示成某個(gè)函數(shù)f(x)的積分，f(x)稱(chēng)的分布密度函數(shù)，簡(jiǎn)稱(chēng)密度函數(shù)。,管理系統(tǒng)模擬 馬維忠,19,均值，也稱(chēng)數(shù)學(xué)期望：E(),表示隨機(jī)變量取值的平均大小。,離散型隨機(jī)變量 連續(xù)型隨機(jī)變量,管理系統(tǒng)模擬 馬維忠,20,方差： D(),描述隨機(jī)變量的取值與其均值E()的分散程度，反映了數(shù)據(jù)波動(dòng)的大小。,離散型隨機(jī)變量 連續(xù)型隨機(jī)變量,管理系統(tǒng)模擬 馬維忠,21,總體：概率統(tǒng)計(jì)計(jì)算的全部元素所組成的集合。 個(gè)體：組成總體的最小研究單位。 抽樣：通過(guò)試驗(yàn)觀測(cè)得到的總體的部分結(jié)果。 樣本量：抽樣中包括的個(gè)體數(shù)量。,管理系統(tǒng)模擬 馬維忠,22,2 常用的概率分布形,(0-1)分布：隨機(jī)變量只能取0和1二值 P=1=p P=0=1-p E()=1*p + 0*(1-p)=p D()=(1-p)2*p+(0-p)2*(1-p)=p(1-p),管理系統(tǒng)模擬 馬維忠,23,二項(xiàng)分布：設(shè)試驗(yàn)E只有兩種可能結(jié)果，成功（記為A）和失?。ㄓ洖锽）,P(A)=p, P(B)=1-p, 將E獨(dú)立地重復(fù)進(jìn)行n次，則稱(chēng)這n次重復(fù)獨(dú)立的試驗(yàn)為n重Bernoulli試驗(yàn)，簡(jiǎn)稱(chēng)Bernoulli試驗(yàn)。以隨機(jī)變量表示n重Bernoulli試驗(yàn)中事件A發(fā)生的次數(shù)，則A恰好發(fā)生k(0kn)次的概率為P(=k)=Pn(k)=,k=0,1,n E()=np D()=np(1-p),管理系統(tǒng)模擬 馬維忠,24,幾何分布：幾何分布式關(guān)于Bernoulli試驗(yàn)的序列問(wèn)題，所考慮的隨機(jī)變量定義為達(dá)到第一次成功的試驗(yàn)次數(shù)。 P(=K)=(1-P)K-1P E()= 1/p D()= (1-p)/p2,管理系統(tǒng)模擬 馬維忠,25,泊松(Poisson)分布：隨機(jī)變量所有可能取值為0，1，2，P(=k)=,E()=D()=,管理系統(tǒng)模擬 馬維忠,26,均勻分布：連續(xù)型隨機(jī)變量在有限區(qū)間（a,b）內(nèi)取值，且落在任意等長(zhǎng)的子區(qū)間的可能性相同。,管理系統(tǒng)模擬 馬維忠,27,E()=(a+b)/2 D()=(b-a)2/12,管理系統(tǒng)模擬 馬維忠,28,指數(shù)分布：稱(chēng)服從參數(shù)為的指數(shù)分布，若,E()=1/,D()=1/2,管理系統(tǒng)模擬 馬維忠,29,正態(tài)分布：稱(chēng)服從參數(shù)為，的正態(tài)分布，若,E()= D()=2,管理系統(tǒng)模擬 馬維忠,30,3 系統(tǒng)概率分布模型,在離散事件系統(tǒng)的建模過(guò)程中，經(jīng)常要研究一些不確定的隨機(jī)事件，需要引入概率分布 排隊(duì)系統(tǒng) 庫(kù)存系統(tǒng) 系統(tǒng)可靠性、維修性研究,管理系統(tǒng)模擬 馬維忠,31,排隊(duì)服務(wù)系統(tǒng),在排隊(duì)系統(tǒng)中，主要有兩種類(lèi)型的活動(dòng)，即實(shí)體到達(dá)和實(shí)體接受服務(wù) 實(shí)體到達(dá)的時(shí)間間隔： 固定值 隨機(jī)變量：泊松/指數(shù)，均勻 實(shí)體接受服務(wù)的時(shí)間： 固定值 隨機(jī)變量：均勻，指數(shù)，正態(tài),管理系統(tǒng)模擬 馬維忠,32,服從泊松分布到達(dá)的實(shí)體： 在一定時(shí)間間隔內(nèi)到達(dá)實(shí)體的數(shù)目?jī)H與時(shí)間間隔的長(zhǎng)短有關(guān)，而與這段時(shí)間間隔的起始時(shí)刻無(wú)關(guān)。 在某個(gè)時(shí)間間隔內(nèi)到達(dá)的實(shí)體數(shù)目與在此之前到達(dá)的實(shí)體數(shù)目無(wú)關(guān)，也不影響在此之后的實(shí)體到達(dá)。 不存在兩個(gè)或兩個(gè)以上實(shí)體同時(shí)到達(dá)的情況。 若在一定時(shí)間內(nèi)到達(dá)系統(tǒng)的實(shí)體數(shù)目x服從參數(shù)為的泊松分布，則相鄰到達(dá)的兩個(gè)實(shí)體之間的到達(dá)時(shí)間間隔T服從參數(shù)為的指數(shù)分布。,管理系統(tǒng)模擬 馬維忠,33,庫(kù)存系統(tǒng),在現(xiàn)實(shí)庫(kù)存系統(tǒng)中有三個(gè)隨機(jī)變量： 每次訂貨或單位周期內(nèi)的需求量； 兩次需求間的時(shí)間間隔； 發(fā)出訂單到收到訂貨的時(shí)間間隔，也成為提前期。,管理系統(tǒng)模擬 馬維忠,34,可靠性與維修性,在系統(tǒng)可靠性與維修性建模中，優(yōu)先考慮的隨機(jī)變量是系統(tǒng)中部件的無(wú)故障工作時(shí)間和故障后的修復(fù)時(shí)間 通常部件發(fā)生故障的時(shí)間分布和修復(fù)時(shí)間分布用指數(shù)分布來(lái)描述。正態(tài)分布適用于多數(shù)故障是由于磨損產(chǎn)生的系統(tǒng)。,管理系統(tǒng)模擬 馬維忠,35,綜上所述，在離散事件系統(tǒng)建模過(guò)程中，隨機(jī)變量較常采用的分布形式是指數(shù)分布和正態(tài)分布， 其主要原因是： 指數(shù)分布簡(jiǎn)單，數(shù)據(jù)處理容易。,管理系統(tǒng)模擬 馬維忠,36,指數(shù)分布的一個(gè)重要特點(diǎn)是無(wú)記憶性，這與大多數(shù)與時(shí)間有關(guān)的隨機(jī)現(xiàn)象是一致的 指數(shù)分布與許多其他分布形式有關(guān)。 正態(tài)分布雖然沒(méi)有指數(shù)分布那樣多的優(yōu)點(diǎn)，但也是描述隨機(jī)變量所必不可少的一種分布形式。正態(tài)分布的特點(diǎn)之一是可以使隨機(jī)變量取值相對(duì)集中或者使隨機(jī)變量散布很大甚至接近于均勻分布。這個(gè)特點(diǎn)使它具有很廣的應(yīng)用范圍。,管理系統(tǒng)模擬 馬維忠,37,4 隨機(jī)變量模型的確定,在獲得了有關(guān)隨機(jī)變量概率分布的觀測(cè)數(shù)據(jù)后，可以分析隨機(jī)變量的分布特性，并在此基礎(chǔ)上建立相應(yīng)的模型。在建模過(guò)程中，需要完成以下兩個(gè)任務(wù)： 由觀測(cè)數(shù)據(jù)確定隨機(jī)變量的概率分布形式。 在隨機(jī)變量概率分布類(lèi)型已知的情況下，由觀測(cè)數(shù)據(jù)確定分布參數(shù)。,管理系統(tǒng)模擬 馬維忠,38,分布類(lèi)型假設(shè) 由觀測(cè)數(shù)據(jù)來(lái)確定隨機(jī)變量的分布類(lèi)型，最常用的方法是對(duì)觀測(cè)數(shù)據(jù)進(jìn)行適當(dāng)?shù)念A(yù)處理， 然后將預(yù)處理的結(jié)果與已知分布類(lèi)型的相應(yīng)結(jié)果進(jìn)行比較，做出隨機(jī)變量概率分布的假設(shè)。,管理系統(tǒng)模擬 馬維忠,39,預(yù)處理的方法有兩種： 點(diǎn)統(tǒng)計(jì)法 直方圖法,管理系統(tǒng)模擬 馬維忠,40,點(diǎn)統(tǒng)計(jì)法的思想是比較隨機(jī)變量概率分布數(shù)字特征之間的關(guān)系，即通過(guò)比較概率分布的偏差系數(shù)來(lái)進(jìn)行分布類(lèi)型的假設(shè)。 對(duì)于隨機(jī)變量，其偏差系數(shù)定義為： = D()1/2/E()，即偏差系數(shù)為均方差與期望值的比。,管理系統(tǒng)模擬 馬維忠,41,管理系統(tǒng)模擬 馬維忠,42,直方圖法是一種直觀的近似求分布密度函數(shù)的圖解方法。它將觀測(cè)數(shù)據(jù)的取值范圍(a0,a1)劃分為k個(gè)斷開(kāi)的相鄰區(qū)間，每個(gè)區(qū)間寬度相等。令fj表示第j個(gè)區(qū)間上觀測(cè)數(shù)據(jù)出現(xiàn)的頻率，構(gòu)成分段函數(shù)h(x)。根據(jù)函數(shù)h(x)圖像的形狀選擇類(lèi)似的分布。,管理系統(tǒng)模擬 馬維忠,43,分布參數(shù)的估計(jì) 對(duì)隨機(jī)變量的觀測(cè)數(shù)據(jù)可以用來(lái)判斷隨機(jī)變量的分布類(lèi)型，同時(shí)也需要利用觀測(cè)數(shù)據(jù)來(lái)確定分布中的參數(shù)。 參數(shù)估計(jì)分為點(diǎn)估計(jì)和區(qū)間估計(jì)，以下僅討論分布參數(shù)的點(diǎn)估計(jì)問(wèn)題。,管理系統(tǒng)模擬 馬維忠,44,每一類(lèi)分布都具有其相應(yīng)的分布參數(shù)，分布參數(shù)影響分布的統(tǒng)計(jì)性質(zhì)。從幾何角度看，分布參數(shù)的影響主要體現(xiàn)在三個(gè)方面： a位置參數(shù)：確定一個(gè)分布的密度函數(shù)在橫坐標(biāo)上的取值范圍，以及分布密度曲線(xiàn)與坐標(biāo)原點(diǎn)的相對(duì)位置。P(x - ) b比例參數(shù)：決定分布密度函數(shù)在其取值范圍內(nèi)的比例尺，比例參數(shù)的改變只是使分布密度取現(xiàn)在橫坐標(biāo)上壓縮或擴(kuò)張。 P(x) c形狀參數(shù)：確定分布函數(shù)的形狀，影響分布行數(shù)的性質(zhì)。 P(x),管理系統(tǒng)模擬 馬維忠,45,5 隨機(jī)數(shù)的產(chǎn)生,在許多系統(tǒng)中，事件的發(fā)生是隨機(jī)的，或者事件的屬性值的確定具有偶然性 要模仿這些偶然性 需要隨機(jī)數(shù),管理系統(tǒng)模擬 馬維忠,46,使用過(guò)的真正隨機(jī)數(shù)的發(fā)生源有： 一袋小球，進(jìn)行可替換抽樣； 微秒級(jí)時(shí)鐘上的低階數(shù)字； 一個(gè)隨機(jī)電子噪聲源的周期性量化輸出值 共同的缺點(diǎn)是在仿真過(guò)程中，用這些方法產(chǎn)生的隨機(jī)數(shù)通常不能復(fù)現(xiàn),管理系統(tǒng)模擬 馬維忠,47,偽隨機(jī)數(shù) 所產(chǎn)生的數(shù)必須服從均勻分布 所產(chǎn)生的數(shù)必須是統(tǒng)計(jì)獨(dú)立的 所產(chǎn)生的隨機(jī)數(shù)序列必須是可以重現(xiàn)的 所產(chǎn)生的隨機(jī)數(shù)序列在需要的長(zhǎng)度內(nèi)必須不重復(fù)-周期。 隨機(jī)數(shù)產(chǎn)生的速度必須快 用于產(chǎn)生隨機(jī)數(shù)的方法應(yīng)當(dāng)占用盡可能小的存儲(chǔ)空間,管理系統(tǒng)模擬 馬維忠,48,第一種方法是利用某種手段生成一個(gè)隨機(jī)數(shù)序列并將它永久保存起來(lái)，例如存在計(jì)算機(jī)硬盤(pán)上 第二種方法是利用某種手段生成一個(gè)隨機(jī)數(shù)序列并將其保留在計(jì)算機(jī)內(nèi)存中 第三種方法也是最常用的一種方法，是利用某種算法根據(jù)指定的輸入值來(lái)產(chǎn)生隨機(jī)數(shù),管理系統(tǒng)模擬 馬維忠,49,平方取中法 平方取中法是馮紐曼（John von Neumann）在40年代中期提出的 這個(gè)方法首先從某個(gè)初始的種子數(shù)開(kāi)始，求出這個(gè)數(shù)的平方，取這個(gè)平方數(shù)的中間幾位數(shù)作為隨機(jī)數(shù)序列中的第2個(gè)數(shù)；再求出第2個(gè)數(shù)的平方，又取這個(gè)平方數(shù)的中間幾位數(shù)作為隨機(jī)數(shù)序列中的第3個(gè)數(shù)；不斷按這個(gè)方式繼續(xù)此算法，即可得到相應(yīng)的偽隨機(jī)序列。,管理系統(tǒng)模擬 馬維忠,50,管理系統(tǒng)模擬 馬維忠,51,線(xiàn)性同余法 線(xiàn)性同余法在1951年由萊默爾（Lehmer）首先提出。 在這個(gè)算法中，隨機(jī)數(shù)序列中的數(shù)由下列遞推關(guān)系產(chǎn)生,種子,乘子,增量,模數(shù),管理系統(tǒng)模擬 馬維忠,52,常數(shù)的值對(duì)所產(chǎn)生的隨機(jī)數(shù)序列的周期長(zhǎng)度有很大影響。 例如設(shè)a=5 c=3 m=16，取x0=7，利用線(xiàn)性同余法產(chǎn)生隨機(jī)數(shù)序列。 在n=16時(shí)出現(xiàn)循環(huán)。 為了使重復(fù)周期充分長(zhǎng)，對(duì)常數(shù)的選擇比較重要,管理系統(tǒng)模擬 馬維忠,53,加同余法 加同余法需要個(gè)數(shù)的序列作為種子，這個(gè)序列可以應(yīng)用其它的方法產(chǎn)生，應(yīng)用家同與法可以是這個(gè)序列不斷擴(kuò)大。其算法是,管理系統(tǒng)模擬 馬維忠,54,二次平方同余法 二次平方同余法適用于為的冪次的情況，這種方法的遞推關(guān)系式為,管理系統(tǒng)模擬 馬維忠,55,偽隨機(jī)數(shù)系列的質(zhì)量需要檢驗(yàn) 偽隨機(jī)數(shù)的產(chǎn)生用于模仿在一個(gè)連續(xù)分布上的抽樣，對(duì)偽隨機(jī)數(shù)序列的檢驗(yàn)和確認(rèn)通常需要將該偽隨機(jī)數(shù)序列與均勻分布的期望情況進(jìn)行比較 隨機(jī)度 均勻 獨(dú)立性 周期,管理系統(tǒng)模擬 馬維忠,56,6 隨機(jī)變量的產(chǎn)生,隨機(jī)變量的產(chǎn)生就是生成非均勻分布的隨機(jī)數(shù)的過(guò)程。 方法 常用的隨機(jī)變量,管理系統(tǒng)模擬 馬維忠,57,反變換法 當(dāng)分布密度函數(shù)f(X)可積分得出累計(jì)分布函數(shù)F(X)或F(X)是一個(gè)經(jīng)驗(yàn)分布,管理系統(tǒng)模擬 馬維忠,58,例1：某隨機(jī)變量的概率分布函數(shù)由下式給出,管理系統(tǒng)模擬 馬維忠,59,求出其逆函數(shù)為,管理系統(tǒng)模擬 馬維忠,60,若產(chǎn)生的標(biāo)準(zhǔn)均勻分布的偽隨機(jī)數(shù)序列為0.1021, 0.2162, 0.7621，則得到的隨機(jī)變量為：,管理系統(tǒng)模擬 馬維忠,61,例2：隨機(jī)變量x的概率分布函數(shù)由下表確定,若x為連續(xù)的隨機(jī)變量，可以根據(jù)例1中的方法產(chǎn)生，如生成的標(biāo)準(zhǔn)均勻分布隨機(jī)數(shù)為0.25， 則可以在1.0與1.5之間線(xiàn)性插值獲得，x=1.0833。 若x為離散性的隨機(jī)變量，x=1.0。,管理系統(tǒng)模擬 馬維忠,62,函數(shù)變換法 當(dāng)通過(guò)F(x)無(wú)法獲得反函數(shù)表達(dá)式時(shí)，函數(shù)變換是一種變通方式。做法是利用變量替換，試圖獲得一種能求出反函數(shù)的形式，求出隨機(jī)變量后再替換回來(lái)。,管理系統(tǒng)模擬 馬維忠,63,設(shè)連續(xù)型隨機(jī)變量x的概率分布函數(shù)F(x)不存在反函數(shù)形式，做變量替換，令,管理系統(tǒng)模擬 馬維忠,64,設(shè)g(y)的一階導(dǎo)數(shù)存在，則隨機(jī)變量y的概率密度函數(shù)為,管理系統(tǒng)模擬 馬維忠,65,從而得到其分布函數(shù),管理系統(tǒng)模擬 馬維忠,66,若G(y)的反函數(shù)存在，則可確定隨機(jī)變量y,從而得到隨機(jī)變量x的值為,管理系統(tǒng)模擬 馬維忠,67,組合法 組合法的基礎(chǔ)思想是隨機(jī)變量的分布函數(shù)可以表示成若干其他分布之和,其中Fj(x)比F(x)容易獲得。,管理系統(tǒng)模擬 馬維忠,68,拒絕法，也稱(chēng)接受拒絕法。 基本思想是構(gòu)造隨機(jī)變量概率密度函數(shù)f(x)的變換Cf(x)，使,管理系統(tǒng)模擬 馬維忠,69,步驟為 a)將f(x)的值域歸一化，即選擇常數(shù)C，使,b)定義x為a, b上的均勻連續(xù)隨機(jī)變量,管理系統(tǒng)模擬 馬維忠,70,c)生成一對(duì)隨機(jī)數(shù)r1，r2 d)若,則隨機(jī)變量取,否則返回c),管理系統(tǒng)模擬 馬維忠,71,常用分布的隨機(jī)變量產(chǎn)生,非標(biāo)準(zhǔn)均勻分布 標(biāo)準(zhǔn)均勻分布的取值范圍在0, 1)，因此a, b上均勻分布的隨機(jī)變量可用,管理系統(tǒng)模擬 馬維忠,72,指數(shù)分布 指數(shù)分布的概率密度函數(shù)為,利用反變換法，取其逆函數(shù),指數(shù)分布的隨機(jī)變量x可由下式產(chǎn)生,管理系統(tǒng)模擬 馬維忠,73,正態(tài)分布 利用組合法：根據(jù)中心極限定理，n個(gè)均值為 方差為 的獨(dú)立同分布的隨機(jī)變量 的和服從均值為 方差為 的近似正態(tài)分布,管理系統(tǒng)模擬 馬維忠,74,拒絕法：標(biāo)準(zhǔn)正態(tài)分布的概率密度函數(shù)為,在,時(shí)取得極大值,，因此取,管理系統(tǒng)模擬 馬維忠,75,1)生成一對(duì)隨機(jī)數(shù)r1，r2 2)若,，則隨機(jī)變量取,；否則返回1),二、概念模型及建模,模型 建模方法 實(shí)例,管理系統(tǒng)模擬 馬維忠,77,模型：為了達(dá)到系統(tǒng)研究的目的，用于收集和描述系統(tǒng)有關(guān)信息的實(shí)體。 模型是為研究用的和系統(tǒng)有關(guān)的信息的組合，他放映了系統(tǒng)某些方面屬性的本質(zhì)。,管理系統(tǒng)模擬 馬維忠,78,離散事件系統(tǒng)的時(shí)間是連續(xù)變化的，而系統(tǒng)的狀態(tài)僅在一些離散的時(shí)刻上由于隨機(jī)事件的驅(qū)動(dòng)而發(fā)生變化。 由于狀態(tài)是離散變化的，而引發(fā)狀態(tài)變化的事件是隨機(jī)發(fā)生的，因此這類(lèi)系統(tǒng)的模型很難用數(shù)學(xué)方程是來(lái)描述。,管理系統(tǒng)模擬 馬維忠,79,實(shí)體流程圖法與計(jì)算機(jī)流程圖的畫(huà)法類(lèi)似，可以描述臨時(shí)實(shí)體的產(chǎn)生、流動(dòng)、消亡及其被永久實(shí)體加工、處理的過(guò)程和邏輯關(guān)系，應(yīng)用比較廣泛；所建立的實(shí)體流程圖模型易于轉(zhuǎn)換為面向事件的仿真模型。,管理系統(tǒng)模擬 馬維忠,80,活動(dòng)周期圖法針對(duì)實(shí)體的行為模式進(jìn)行建模，可以直觀地表示出某類(lèi)實(shí)體生命周期中的活動(dòng)和狀況，具有規(guī)范化的特點(diǎn)，對(duì)不同實(shí)體之間協(xié)同關(guān)系的描述十分清晰、明確。而且，應(yīng)用活動(dòng)周期圖法建立的系統(tǒng)模型，轉(zhuǎn)換為面向活動(dòng)的仿真模型比較方便。,管理系統(tǒng)模擬 馬維忠,81,Petri網(wǎng)方法適用于建立加工系統(tǒng)等多種離散事件系統(tǒng)的模型，并可對(duì)網(wǎng)系統(tǒng)的特性進(jìn)行比較嚴(yán)密的數(shù)學(xué)分析，得到對(duì)并發(fā)、沖突、死鎖等現(xiàn)象的深刻認(rèn)識(shí)，應(yīng)用也比較廣泛。,管理系統(tǒng)模擬 馬維忠,82,1 基本建模術(shù)語(yǔ),實(shí)體（Entity） 實(shí)體是被仿真系統(tǒng)中可單獨(dú)辨識(shí)和刻劃的構(gòu)成要素。例如，工廠中的機(jī)器，商店中的服務(wù)員，生產(chǎn)線(xiàn)上的工作，交通道路上的車(chē)輛等。在建模人員看來(lái)，實(shí)際系統(tǒng)就是由互相存在一定關(guān)系的實(shí)體集合組成的，實(shí)體間的相互聯(lián)系和作用產(chǎn)生系統(tǒng)特定的行為。 屬性和行為相同或相近的實(shí)體可以用類(lèi)來(lái)描述，這樣可以簡(jiǎn)化系統(tǒng)的組成和關(guān)系。例如，理發(fā)店服務(wù)系統(tǒng)可以看成是由“服務(wù)員”和“顧客”兩類(lèi)實(shí)體組成的，而兩類(lèi)實(shí)體間存在服務(wù)與被服務(wù)的關(guān)系。,管理系統(tǒng)模擬 馬維忠,83,屬性（Attribute） 屬性是實(shí)體特征的描述，一般是實(shí)體所擁有的全部特征的一個(gè)子集，用特征參數(shù)或變量表示。選用哪些特征參數(shù)作為實(shí)體的屬性與建模目的有關(guān)，可以參照下屬原則選?。?a便于實(shí)體的分類(lèi)：例如，考慮將顧客的“性別”作屬性，每類(lèi)顧客占用不同的服務(wù)臺(tái)； b便于實(shí)體行為描述：飛機(jī)的“速度”屬性便于描述飛行時(shí)間； c便于排隊(duì)規(guī)則的確定：工件加工的“優(yōu)先級(jí)”屬性便于按有限級(jí)別分別排隊(duì)。,管理系統(tǒng)模擬 馬維忠,84,活動(dòng)（Activity） 實(shí)體在一段時(shí)間內(nèi)持續(xù)進(jìn)行的操作或過(guò)程?；顒?dòng)所占用的世間區(qū)段稱(chēng)為忙期（Duration），忙期可以是定時(shí)的或隨機(jī)的。在離散事件系統(tǒng)建模中，一般要給出忙期的計(jì)算公式或概率分布函數(shù)，保證實(shí)體一進(jìn)入某一活動(dòng)時(shí)期忙期就可以計(jì)算，或從某一分布函數(shù)中抽取到。,管理系統(tǒng)模擬 馬維忠,85,狀態(tài)（State） 對(duì)實(shí)體活動(dòng)的特征狀況或狀態(tài)的劃分，其表征量稱(chēng)為狀態(tài)變量?；顒?dòng)總是與一個(gè)或幾個(gè)實(shí)體的狀態(tài)相對(duì)應(yīng)的。,管理系統(tǒng)模擬 馬維忠,86,事件（Event） 導(dǎo)致系統(tǒng)狀態(tài)產(chǎn)生變化的瞬間操作或行為。事件發(fā)生的時(shí)刻稱(chēng)為事件點(diǎn)。不關(guān)心事件所代表的操作和行為意義時(shí)，事件和事件點(diǎn)是同義語(yǔ)。若事件的發(fā)生是有前提的，則稱(chēng)為條件事件。 考察活動(dòng)、狀態(tài)和事件三者的聯(lián)系。由于事件的發(fā)生會(huì)導(dǎo)致?tīng)顟B(tài)的變化，而實(shí)體的活動(dòng)可以與一定的狀態(tài)相對(duì)應(yīng)，因此可以用事件來(lái)標(biāo)識(shí)活動(dòng)的開(kāi)始和結(jié)束。,管理系統(tǒng)模擬 馬維忠,87,進(jìn)程（Process） 一組按發(fā)生時(shí)間排列的事件/活動(dòng)序列。,管理系統(tǒng)模擬 馬維忠,88,管理系統(tǒng)模擬 馬維忠,89,隊(duì)列（Queue） 處于等待狀態(tài)的實(shí)體序列。一般按新到的實(shí)體排在隊(duì)尾的次序組成隊(duì)列。在離散事件系統(tǒng)建模中，隊(duì)列可以作為一種狀態(tài)或特殊實(shí)體對(duì)待。,管理系統(tǒng)模擬 馬維忠,90,2 實(shí)體流圖法,在離散事件系統(tǒng)中，實(shí)體可以分為兩大類(lèi)： 臨時(shí)實(shí)體 永久實(shí)體,管理系統(tǒng)模擬 馬維忠,91,臨時(shí)實(shí)體按一定的規(guī)律由系統(tǒng)外部進(jìn)入系統(tǒng)，在系統(tǒng)內(nèi)部接受永久實(shí)體的作用，按照一定的流程通過(guò)系統(tǒng)，最后離開(kāi)系統(tǒng)。因此，臨時(shí)實(shí)體只在系統(tǒng)中存在一段時(shí)間即自行消失。,管理系統(tǒng)模擬 馬維忠,92,與臨時(shí)實(shí)體相反，那些永久駐留在系統(tǒng)中的實(shí)體稱(chēng)為永久實(shí)體，它們是系統(tǒng)產(chǎn)生功能的必要條件。 系統(tǒng)要對(duì)臨時(shí)實(shí)體產(chǎn)生作用，就必須有永久實(shí)體的活動(dòng)，這是臨時(shí)實(shí)體和永久實(shí)體協(xié)同完成了某項(xiàng)活動(dòng)，永久實(shí)體被作為活動(dòng)的資源而占用。,管理系統(tǒng)模擬 馬維忠,93,實(shí)體流程圖法采用計(jì)算機(jī)程序流程圖的圖示符號(hào)，建立表示臨時(shí)實(shí)體產(chǎn)生、在系統(tǒng)中流動(dòng)、接受永久實(shí)體服務(wù)以及消失等過(guò)程的流程圖。借助實(shí)體流程圖，可以表示事件、狀態(tài)變化及實(shí)體間相互作用的邏輯關(guān)系。,管理系統(tǒng)模擬 馬維忠,94,建?？梢园慈缦滤悸罚?辨識(shí)組成系統(tǒng)的實(shí)體及屬性。將隊(duì)列作為一種特殊的實(shí)體來(lái)考慮。 分析各種實(shí)體的狀態(tài)和活動(dòng)，及其相互間的影響。隊(duì)列實(shí)體的狀態(tài)是隊(duì)列的長(zhǎng)度。 考察有哪些事件導(dǎo)致了活動(dòng)的開(kāi)始和結(jié)束，或者可以作為活動(dòng)開(kāi)始或結(jié)束的標(biāo)志，以確定引起實(shí)體狀態(tài)變化的時(shí)間，并合并條件事件。 分析各種事件發(fā)生時(shí)，實(shí)體狀態(tài)的變化規(guī)律。 在一定的服務(wù)流程下，分析與隊(duì)列實(shí)體有關(guān)的特殊操作（如換隊(duì)等）。 通過(guò)以上分析，以臨時(shí)實(shí)體的流動(dòng)為主線(xiàn)，用約定的圖示符號(hào)畫(huà)出被仿真系統(tǒng)的實(shí)體流程圖。 給出模型參數(shù)的取值、參變量的計(jì)算方法及屬性描述變量的取值方法。 給出隊(duì)列的排隊(duì)規(guī)則。有多個(gè)隊(duì)列存在時(shí)，還應(yīng)給出其服務(wù)規(guī)則，包括隊(duì)列的優(yōu)先次序、換隊(duì)規(guī)則等。,管理系統(tǒng)模擬 馬維忠,95,例1 理發(fā)店服務(wù)系統(tǒng)：有一個(gè)理發(fā)店只有一個(gè)理發(fā)員。顧客來(lái)到理發(fā)店后，若有人正在理發(fā)就坐在一旁等候。理發(fā)員按先來(lái)先服務(wù)的原則為每位顧客服務(wù)，而且只要有顧客就不停歇。建模的目的是在假定顧客到達(dá)時(shí)間間隔和理發(fā)花費(fèi)的時(shí)間服從一定的概率分布時(shí)，考察理發(fā)員的忙閑情況。,管理系統(tǒng)模擬 馬維忠,96,該系統(tǒng)由3類(lèi)實(shí)體組成：理發(fā)員、顧客及顧客隊(duì)列。 理發(fā)員是永久實(shí)體，其活動(dòng)為“理發(fā)”，由“忙”和“閑”兩種狀態(tài)。 顧客是臨時(shí)實(shí)體，他與理發(fā)員協(xié)同完成“理發(fā)”活動(dòng)，有“等待服務(wù)”、“接受服務(wù)”等狀態(tài)，其中“接受服務(wù)”狀態(tài)對(duì)應(yīng)理發(fā)員的“忙”狀態(tài)。 顧客隊(duì)列是抽象實(shí)體，其狀態(tài)以隊(duì)列長(zhǎng)度標(biāo)識(shí)。,管理系統(tǒng)模擬 馬維忠,97,三類(lèi)實(shí)體的活動(dòng)和狀態(tài)之間存在如下邏輯關(guān)系： (1) 一個(gè)顧客到達(dá)時(shí)，若理發(fā)員處于“忙”狀態(tài)，則顧客進(jìn)入“等待服務(wù)”狀態(tài)；否則，進(jìn)入“接受服務(wù)”狀態(tài)； (2) 理發(fā)員完成對(duì)一個(gè)顧客的服務(wù)后，如果隊(duì)列處于“非零”狀態(tài)，則立即開(kāi)始服務(wù)活動(dòng)；否則進(jìn)入閑狀態(tài)。,管理系統(tǒng)模擬 馬維忠,98,“顧客到達(dá)”或“顧客結(jié)束排隊(duì)”可以導(dǎo)致“服務(wù)”活動(dòng)的開(kāi)始，而“顧客離去”可以導(dǎo)致“服務(wù)”活動(dòng)的結(jié)束，可以看作事件。而“顧客結(jié)束排隊(duì)”是以理發(fā)員的狀態(tài)為“閑”為條件的，是條件事件，可以不單獨(dú)考慮。,管理系統(tǒng)模擬 馬維忠,99,管理系統(tǒng)模擬 馬維忠,100,例2 分時(shí)計(jì)算機(jī)系統(tǒng)：分時(shí)計(jì)算機(jī)系統(tǒng)由一個(gè)CPU和多臺(tái)終端組成。用戶(hù)從終端輸入作業(yè)，請(qǐng)求CPU服務(wù)。CPU按FIFO分時(shí)輪流執(zhí)行作業(yè)，每個(gè)作業(yè)執(zhí)行一個(gè)時(shí)間片后若未完成則重新排隊(duì)。某終端的作業(yè)完成后才可以繼續(xù)輸入作業(yè)。建模的目的是研究用戶(hù)的等待時(shí)間。,管理系統(tǒng)模擬 馬維忠,101,管理系統(tǒng)模擬 馬維忠,102,例3 售票窗口系統(tǒng)：劇院由一名售票員負(fù)責(zé)在窗口售票并同時(shí)接待電話(huà)咨詢(xún)服務(wù)，窗口服務(wù)比電話(huà)服務(wù)優(yōu)先。問(wèn)訊電話(huà)可以由電話(huà)存儲(chǔ)系統(tǒng)按先后順序存儲(chǔ)并由售票員一一答復(fù)。建模的目的是研究售票員的忙閑情況。,活動(dòng)周期模型,管理系統(tǒng)模擬 馬維忠,103,管理系統(tǒng)模擬 馬維忠,104,模型的人工運(yùn)行 建立實(shí)體流程圖模型后，選取有代表性的例子觀察系統(tǒng)按模型的運(yùn)行情況，稱(chēng)人工運(yùn)行。人工運(yùn)行模型的要求是遍歷流程圖的各個(gè)分支和實(shí)體的各種狀態(tài)，在時(shí)間逐步變化的動(dòng)態(tài)條件下，分析事件的發(fā)生及狀態(tài)的變化過(guò)程，以檢驗(yàn)?zāi)Ｐ偷慕M成關(guān)系和邏輯關(guān)系是否正確。,管理系統(tǒng)模擬 馬維忠,105,在例1中，假定： 系統(tǒng)的初始狀態(tài)：初始時(shí)刻，理發(fā)店開(kāi)門(mén)營(yíng)業(yè)時(shí)；理發(fā)員狀態(tài)，閑；隊(duì)列狀態(tài)，長(zhǎng)度為0；,管理系統(tǒng)模擬 馬維忠,106,模型參數(shù)及變量取值：本模型的參變量包括第I個(gè)顧客與第I-1個(gè)顧客到達(dá)的時(shí)間間隔Ai，以及理發(fā)員為第I個(gè)顧客理發(fā)的時(shí)間Si。一般來(lái)說(shuō)，Ai與Si均為隨機(jī)變量，這里為便于解釋?zhuān)∑錁颖局禐椋?A1=15，A2=32，A3=24，A4=40，A5=22， S1=43，S2=36，S3=34，S4=28，,管理系統(tǒng)模擬 馬維忠,107,本模型運(yùn)行的規(guī)則： 規(guī)則1確定當(dāng)前時(shí)間。當(dāng)前時(shí)間TIME在開(kāi)始運(yùn)行時(shí)取仿真初始時(shí)刻，并隨時(shí)間逐步推移遞取最早事件發(fā)生的時(shí)刻。在當(dāng)前時(shí)間，若發(fā)生顧客到達(dá)事件，執(zhí)行規(guī)則2；若發(fā)生顧客離去事件，執(zhí)行規(guī)則3。 規(guī)則2顧客到達(dá)事件處理。若理發(fā)員忙，隊(duì)列長(zhǎng)度加1；否則，開(kāi)始理發(fā)，置理發(fā)員為“忙”，經(jīng)Si后離去。 規(guī)則3顧客離去事件處理。若隊(duì)列長(zhǎng)為0，置理發(fā)員為“閑”；否則，隊(duì)列首的顧客開(kāi)始理發(fā)，隊(duì)列長(zhǎng)度減1，經(jīng)Si后離去。,管理系統(tǒng)模擬 馬維忠,108,人工運(yùn)行過(guò)程如下：,管理系統(tǒng)模擬 馬維忠,109,3 活動(dòng)周期圖法,系統(tǒng)中實(shí)體的行為模式在有限的幾種情況之間周而復(fù)始地變化，表現(xiàn)出一定的生命周期形式。活動(dòng)周期圖（Activity Cycle Diagram, ACD）正是基于這樣的一種思想逐步形成的離散事件系統(tǒng)建模方法。,管理系統(tǒng)模擬 馬維忠,110,活動(dòng)周期圖以直觀的方式顯示了實(shí)體的狀態(tài)變化歷程和各實(shí)體之間的交互作用關(guān)系，便于理解和分析?；顒?dòng)周期圖可以充分反映各類(lèi)實(shí)體的行為模式，并將系統(tǒng)的狀態(tài)變化以“個(gè)體”狀態(tài)變化的集合方式表示出來(lái)，因此可以更好地表達(dá)眾多實(shí)體的并發(fā)活動(dòng)和實(shí)體之間的協(xié)同。但是，它只描述了系統(tǒng)的穩(wěn)態(tài)，而沒(méi)有表示系統(tǒng)的瞬態(tài)，即活動(dòng)的開(kāi)始和結(jié)束事件。,管理系統(tǒng)模擬 馬維忠,111,活動(dòng)周期圖建模方法將實(shí)體的狀態(tài)分為靜寂（Dead）和激活（Active）兩種，并分別用不同的符號(hào)表示。,管理系統(tǒng)模擬 馬維忠,112,管理系統(tǒng)模擬 馬維忠,113,狀態(tài)之間用箭頭線(xiàn)相連，不同的實(shí)體用不同的線(xiàn)型，表示各種實(shí)體的狀態(tài)變化歷程。,管理系統(tǒng)模擬 馬維忠,114,激活狀態(tài)通常是實(shí)體的活動(dòng)，模型中活動(dòng)的忙期可以采用隨機(jī)抽樣的方法事先加以確定。 靜寂狀態(tài)通常表示無(wú)活動(dòng)發(fā)生，是實(shí)體等待參加某一活動(dòng)的狀態(tài)，其持續(xù)時(shí)間在模型中無(wú)法事先確定，取決于有關(guān)活動(dòng)的發(fā)生時(shí)刻和忙期。,管理系統(tǒng)模擬 馬維忠,115,每一類(lèi)實(shí)體的生命周期都由一系列狀態(tài)組成。隨著時(shí)間的推移和實(shí)體間的相互作用，各個(gè)實(shí)體從一個(gè)狀態(tài)變化到另一個(gè)狀態(tài)，形成一個(gè)動(dòng)態(tài)變化過(guò)程。,管理系統(tǒng)模擬 馬維忠,116,活動(dòng)周期圖建模過(guò)程如下： 1、辨識(shí)組成系統(tǒng)的實(shí)體及屬性 辨識(shí)組成系統(tǒng)的永久實(shí)體和臨時(shí)實(shí)體，隊(duì)列不作為實(shí)體考慮。 2、分別畫(huà)出各實(shí)體的活動(dòng)周期圖 實(shí)體活動(dòng)周期圖的繪制要以實(shí)際過(guò)程為依據(jù)。隊(duì)列作為排隊(duì)等待狀態(tài)來(lái)處理。在實(shí)體流程圖法中當(dāng)作事件看待的某些操作獲悉，要拓展為活動(dòng)來(lái)處理。,管理系統(tǒng)模擬 馬維忠,117,活動(dòng)周期圖服從以下原則： 交替原則 靜寂狀態(tài)和激活狀態(tài)必須交替出現(xiàn)。如果系統(tǒng)中某一活動(dòng)完成后其后續(xù)活動(dòng)就立即開(kāi)始，則后續(xù)活動(dòng)稱(chēng)直聯(lián)活動(dòng)。為了使直聯(lián)活動(dòng)與其前置活動(dòng)的連接仍符合交替規(guī)則，規(guī)定這兩個(gè)活動(dòng)之間存在一個(gè)虛擬隊(duì)列。 閉合原則 每類(lèi)實(shí)體的活動(dòng)周期圖必須是閉合的，其中臨時(shí)實(shí)體的活動(dòng)周期表是一個(gè)或單位實(shí)體從產(chǎn)生到消失的循環(huán)過(guò)程，而永久實(shí)體的活動(dòng)周期則表示一個(gè)或幾個(gè)實(shí)體被占用和釋放的循環(huán)往復(fù)過(guò)程。,管理系統(tǒng)模擬 馬維忠,118,3、將各實(shí)體的活動(dòng)周期圖連接成系統(tǒng)活動(dòng)周期圖 以各實(shí)體之間的協(xié)同活動(dòng)為紐帶，將各種實(shí)體的活動(dòng)周期圖合并在一起。,管理系統(tǒng)模擬 馬維忠,119,4、添加必要的虛擬實(shí)體 在活動(dòng)周期圖中，當(dāng)一個(gè)活動(dòng)的所有前置靜寂狀態(tài)取非0值（隊(duì)列不空）時(shí)，該活動(dòng)才可能發(fā)生。利用這一特性，可以添加某些必要的虛擬實(shí)體，并假定它們與另外的實(shí)體協(xié)同完成某項(xiàng)活動(dòng)。用這種辦法可以為實(shí)體活動(dòng)的發(fā)生加上某種附加條件，從而實(shí)現(xiàn)“隔時(shí)發(fā)生”的建模效果。,管理系統(tǒng)模擬 馬維忠,120,5、標(biāo)明活動(dòng)發(fā)生的約束條件和占用資源數(shù)量 包括：活動(dòng)是否可以發(fā)生的判斷條件，這些條件應(yīng)是用ACD圖示符號(hào)無(wú)法或不便表達(dá)的；永久實(shí)體在參加一次協(xié)同活動(dòng)是被占用或活動(dòng)完成時(shí)釋放的數(shù)量?；顒?dòng)發(fā)生的條件一般是某種表達(dá)式，標(biāo)在活動(dòng)框的旁邊。協(xié)同活動(dòng)發(fā)生時(shí)占用/釋放永久實(shí)體的數(shù)量標(biāo)在相應(yīng)箭頭線(xiàn)的旁邊（帶有+/-符號(hào)），數(shù)量為1時(shí)不標(biāo)。,管理系統(tǒng)模擬 馬維忠,121,6、給出模型參數(shù)的取值、參變量的計(jì)算方法及屬性描述變量的取值方法，并給出排隊(duì)規(guī)則和服務(wù)規(guī)則。,管理系統(tǒng)模擬 馬維忠,122,例1 機(jī)床加工系統(tǒng)：考慮一個(gè)簡(jiǎn)單的加工車(chē)間。車(chē)間內(nèi)有數(shù)臺(tái)自動(dòng)機(jī)床，由1名工人負(fù)責(zé)看管。工人的任務(wù)是：如果機(jī)床的刀具完好，則為機(jī)床安裝工件，然后按下運(yùn)行按鈕；如果機(jī)床的刀具損壞，則先要重裝刀具，然后完成任務(wù)。只有當(dāng)機(jī)床完成一次自動(dòng)加工工序并停止運(yùn)行后，工人才能執(zhí)行上述兩項(xiàng)任務(wù)。假定每臺(tái)機(jī)床均可加工各種工件，并且不會(huì)發(fā)生工件短缺的情況。建模的目的是研究工人的忙閑情況。,管理系統(tǒng)模擬 馬維忠,123,顯然，建模時(shí)要考慮兩類(lèi)實(shí)體：機(jī)床和工人。 1）工人 工人從事兩項(xiàng)主要活動(dòng)：“安裝工件”和“安裝刀具”。當(dāng)工人不處于上述兩種激活狀態(tài)時(shí)，就處于靜寂狀態(tài)“等待”。,管理系統(tǒng)模擬 馬維忠,124,管理系統(tǒng)模擬 馬維忠,125,2）機(jī)床 機(jī)床有三種激活狀態(tài)：“安裝刀具”、“安裝工件”和“加工”，其中前兩個(gè)是與工人實(shí)體協(xié)同完成的活動(dòng)。,管理系統(tǒng)模擬 馬維忠,126,管理系統(tǒng)模擬 馬維忠,127,管理系統(tǒng)模擬 馬維忠,128,例2 售票窗口系統(tǒng)：劇院由一名售票員負(fù)責(zé)在窗口售票并同時(shí)接待電話(huà)咨詢(xún)服務(wù)，窗口服務(wù)比電話(huà)服務(wù)優(yōu)先。問(wèn)訊電話(huà)可以由電話(huà)存儲(chǔ)系統(tǒng)按先后順序存儲(chǔ)并由售票員一一答復(fù)。建模的目的是研究售票員的忙閑情況。,實(shí)體流程模型,管理系統(tǒng)模擬 馬維忠,129,管理系統(tǒng)模擬 馬維忠,130,模型的人工運(yùn)行 在運(yùn)行模型之前，首先要確定系統(tǒng)的初始狀態(tài)。系統(tǒng)出是狀態(tài)的確定要符合被仿真系統(tǒng)運(yùn)行前的實(shí)際情況。 標(biāo)記臨時(shí)實(shí)體在初始狀態(tài)下的位置。一般，它們處于靜寂狀態(tài)。 標(biāo)記永久實(shí)體在初始狀態(tài)下的位置。一般，它們處在“等待”、“空閑”等靜寂狀態(tài)。,管理系統(tǒng)模擬 馬維忠,131,初始狀態(tài)確定后，按下列規(guī)則運(yùn)行模型： 規(guī)則1活動(dòng)的發(fā)生與執(zhí)行 按照服務(wù)優(yōu)先級(jí)，依次檢查各臨時(shí)實(shí)體每項(xiàng)活動(dòng)的前置狀態(tài)（均為靜寂狀態(tài)）和標(biāo)在活動(dòng)上訪的發(fā)生條件，判斷活動(dòng)是否可以開(kāi)始。滿(mǎn)足以下2條件的活動(dòng)可以開(kāi)始： a. 活動(dòng)的所有前置狀態(tài)中均有實(shí)體停留，且各類(lèi)永久實(shí)體的數(shù)量超過(guò)或等于相應(yīng)箭頭上標(biāo)明的資源占用量。 b. 活動(dòng)發(fā)生的約束條件已經(jīng)滿(mǎn)足。 如果某項(xiàng)活動(dòng)可以開(kāi)始，則將其前置狀態(tài)中標(biāo)號(hào)最小的臨時(shí)實(shí)體的標(biāo)記移至該活動(dòng)框中。然后，修改該活動(dòng)前置狀態(tài)中各永久實(shí)體當(dāng)前資源量，修改方法是從各永久實(shí)體的當(dāng)前資源量中分別減去該活動(dòng)對(duì)該資源的占用量。如果某類(lèi)永久實(shí)體的當(dāng)前資源量變?yōu)?，則取消其在活動(dòng)前置狀態(tài)中的標(biāo)記；否則予以保留。 對(duì)于那些被確定可以開(kāi)始的活動(dòng)，需根據(jù)各項(xiàng)活動(dòng)的忙期分別確定其活動(dòng)終止時(shí)間，并將終止時(shí)間表在活動(dòng)框外，然后轉(zhuǎn)規(guī)則2。,管理系統(tǒng)模擬 馬維忠,132,規(guī)則2確定當(dāng)前時(shí)間 檢查所有活動(dòng)的終止時(shí)間，從中選出最小者作為當(dāng)前時(shí)間，然后轉(zhuǎn)為規(guī)則3。,管理系統(tǒng)模擬 馬維忠,133,規(guī)則3活動(dòng)完成 從所有已發(fā)生的活動(dòng)中，檢出終止時(shí)間等于當(dāng)前時(shí)間的臨時(shí)實(shí)體，刪掉其標(biāo)在活動(dòng)框外的終止時(shí)間。然后，將相應(yīng)活動(dòng)框內(nèi)的臨時(shí)實(shí)體的標(biāo)記移至相關(guān)的后續(xù)狀態(tài)之中。參與活動(dòng)的永久實(shí)體的資源量增加，增加的數(shù)量等于該活動(dòng)完成后的釋放量。最后，將參與活動(dòng)的各永久實(shí)體的后續(xù)狀態(tài)分別作上標(biāo)記，轉(zhuǎn)規(guī)則1。,管理系統(tǒng)模擬 馬維忠,134,25 18 27 16 31,5 9 8 11 3 ,15 32 24 40 22 ,2 4 5 4 3,管理系統(tǒng)模擬 馬維忠,135,現(xiàn)在，我們總結(jié)一下實(shí)體流程圖法與活動(dòng)周期法的區(qū)別與各自特點(diǎn)：,管理系統(tǒng)模擬 馬維忠,136,實(shí)體流程圖（以下簡(jiǎn)記為EFC）是以臨時(shí)實(shí)體在系統(tǒng)中的流動(dòng)過(guò)程為主線(xiàn)建立的模型，永久實(shí)體濃縮于表示狀態(tài)和事件的圖示符號(hào)之中，隊(duì)列被作為一種特殊的實(shí)體來(lái)對(duì)待。對(duì)這三種實(shí)體的描述交織在一起，使得臨時(shí)實(shí)體和永久實(shí)體沒(méi)有單獨(dú)的圖示。活動(dòng)周期圖ACD則基于各類(lèi)臨時(shí)實(shí)體和永久實(shí)體的行為模式，它們均有單獨(dú)的圖示表達(dá)，隊(duì)列很自然地成為實(shí)體生命周期中的一種狀態(tài)。,管理系統(tǒng)模擬 馬維忠,137,ACD種，各類(lèi)實(shí)體的圖示是“環(huán)形”的循環(huán)圖，整個(gè)系統(tǒng)的ACD由多個(gè)環(huán)組成；而EFC則是帶有小循環(huán)的“樹(shù)型”流程圖。,管理系統(tǒng)模擬 馬維忠,138,事件是EFC的重要組成部分，在EFC中有顯示的表達(dá)；而在ACD種，事件蘊(yùn)含在活動(dòng)中，沒(méi)有顯示表達(dá)。,管理系統(tǒng)模擬 馬維忠,139,狀態(tài)判斷框在EFC中的作用十分重要。ACD將EFC中需要作判斷的狀態(tài)用“空閑”、“等待”等靜寂狀態(tài)表示，而對(duì)于實(shí)體是否處于該狀態(tài)中的判斷則勿需標(biāo)在圖中，而升華為規(guī)則。,管理系統(tǒng)模擬 馬維忠,140,從運(yùn)行規(guī)則看，ACD的運(yùn)行規(guī)則與模型無(wú)關(guān)；而EFC除第1條規(guī)則是通用的外，其余的規(guī)則要從EFC中抽取，普適性很差。,管理系統(tǒng)模擬 馬維忠,141,由和知，ACD更易于用面向?qū)ο蟮募夹g(shù)實(shí)現(xiàn)，軟件上也更易于實(shí)現(xiàn)仿真程序的自動(dòng)生成。另外，由知，ACD表示沖突和并發(fā)現(xiàn)象更為方便、直觀。,管理系統(tǒng)模擬 馬維忠,142,正由于EFC沒(méi)有ACD那樣規(guī)范，因此，在不考慮模型運(yùn)行問(wèn)題時(shí)，EFC比ACD的適用范圍更廣。另外，EFC中可以對(duì)隊(duì)列的排隊(duì)規(guī)則和服務(wù)規(guī)則進(jìn)行比較詳細(xì)的描述。,管理系統(tǒng)模擬 馬維忠,143,4 Perti網(wǎng)方法,Petri網(wǎng)的概念是德國(guó)Carl Adam Petri博士1960年首先提出的。 經(jīng)過(guò)近40年的發(fā)展，Petri網(wǎng)建模方法已經(jīng)在機(jī)械加工、計(jì)算機(jī)通訊系統(tǒng)、C3I系統(tǒng)等多個(gè)領(lǐng)域內(nèi)得到廣泛的應(yīng)用，并得到不斷改進(jìn)，產(chǎn)生了很多改進(jìn)形式。,管理系統(tǒng)模擬 馬維忠,144,網(wǎng),定義1 Petri網(wǎng) 三元組,稱(chēng)為Petri網(wǎng)的充要條件是：,管理系統(tǒng)模擬 馬維忠,145,條件和表明，Petri網(wǎng)由S和T兩類(lèi)元素組成；其中S叫做的庫(kù)所集，T叫做變遷集。條件表明，F(xiàn)是由一個(gè)元素S和一個(gè)元素T組成的有序偶的集合；F稱(chēng)為的流關(guān)系。,管理系統(tǒng)模擬 馬維忠,146,條件表明，,不能有孤立元素，從而,和,均不能為空集。,管理系統(tǒng)模擬 馬維忠,147,Petri網(wǎng)又稱(chēng)有向網(wǎng)，簡(jiǎn)稱(chēng)網(wǎng)。,稱(chēng)為,的元素集。,管理系統(tǒng)模擬 馬維忠,148,定義2 元素的輸入和輸出集,設(shè),為網(wǎng),的一個(gè)元素，令,，則,稱(chēng)為,的輸入集或前集；,稱(chēng)為,的輸出集或后集。,管理系統(tǒng)模擬 馬維忠,149,Petri網(wǎng)的標(biāo)準(zhǔn)圖形表示是用圓圈代表庫(kù)所，用方框或豎線(xiàn)表示變遷，用從x到y(tǒng)的有向弧線(xiàn)表示有序偶(x, y)。如果(x, y)是從x到y(tǒng)的有向弧，就稱(chēng)x是y的輸入，y是x的輸出。,管理系統(tǒng)模擬 馬維忠,150,下圖給出了窗口售票系統(tǒng)的Petri網(wǎng)模型圖。,管理系統(tǒng)模擬 馬維忠,151,庫(kù)所集： a 購(gòu)票者等待 b 售票員為購(gòu)票者售票 c 買(mǎi)票的顧客 d 售票員閑 e 問(wèn)訊者等待 f 售票員為問(wèn)訊者咨詢(xún) g 問(wèn)訊完的顧客,管理系統(tǒng)模擬 馬維忠,152,變遷集： 1 購(gòu)票者到達(dá) 2 開(kāi)始購(gòu)票 3 購(gòu)票完畢 4 購(gòu)票者離去 5 問(wèn)訊電話(huà)打入 6 開(kāi)始問(wèn)訊 7 問(wèn)訊完畢 8 問(wèn)訊者離開(kāi),管理系統(tǒng)模擬 馬維忠,153,網(wǎng)系統(tǒng),網(wǎng)是系統(tǒng)靜態(tài)結(jié)構(gòu)的基本描述，要模擬系統(tǒng)的動(dòng)態(tài)特性，需要定義網(wǎng)系統(tǒng)。,管理系統(tǒng)模擬 馬維忠,154,定義3 容量、標(biāo)識(shí)和權(quán),設(shè),是有向圖，,稱(chēng)為,上的一個(gè)容量函數(shù)。,表示,的容量為無(wú)窮。,映射,管理系統(tǒng)模擬 馬維忠,155,若,是,上的容量函數(shù)，映射,稱(chēng)為,的一個(gè)標(biāo)識(shí)的充要條件是,，均滿(mǎn)足,。,管理系統(tǒng)模擬 馬維忠,156,映射,稱(chēng)為,的權(quán)函數(shù)。,在弧,上的值用,表示。,管理系統(tǒng)模擬 馬維忠,157,管理系統(tǒng)模擬 馬維忠,158,管理系統(tǒng)模擬 馬維忠,159,弧上標(biāo)出的整數(shù)用以表示某一變遷對(duì)資源的消耗量或產(chǎn)品的生產(chǎn)量（默認(rèn)1），也就是弧上的權(quán)值。 用給出的數(shù)字說(shuō)明某一庫(kù)所中允許存放資源的最大數(shù)量，即為庫(kù)所的容量值。未加標(biāo)注的庫(kù)所的容量為無(wú)窮大。,管理系統(tǒng)模擬 馬維忠,160,庫(kù)所中的黑點(diǎn)數(shù)表示該庫(kù)所當(dāng)前的實(shí)際資源/產(chǎn)品數(shù)。這里，同一庫(kù)所中的資源或產(chǎn)品被看作是完全等價(jià)的個(gè)體，均用黑點(diǎn)表示；黑點(diǎn)稱(chēng)為令牌或標(biāo)記，各個(gè)庫(kù)所中的黑點(diǎn)數(shù)就是標(biāo)識(shí)。,管理系統(tǒng)模擬 馬維忠,161,管理系統(tǒng)模擬 馬維忠,162,管理系統(tǒng)模擬 馬維忠,163,管理系統(tǒng)模擬 馬維忠,164,管理系統(tǒng)模擬 馬維忠,165,管理系統(tǒng)模擬 馬維忠,166,當(dāng)變遷不斷發(fā)生時(shí)，網(wǎng)系統(tǒng)的狀態(tài)也不斷發(fā)生變化，這一過(guò)程稱(chēng)為網(wǎng)系統(tǒng)的執(zhí)行。網(wǎng)系統(tǒng)的執(zhí)行規(guī)則由定義5給出。,管理系統(tǒng)模擬 馬維忠,167,管理系統(tǒng)模擬 馬維忠,168,管理系統(tǒng)模擬 馬維忠,169,定義5中的變遷條件和發(fā)生規(guī)則可以解釋如下： 一個(gè)變遷被授權(quán)發(fā)生，當(dāng)且僅當(dāng)該變遷的每一個(gè)輸入庫(kù)所的令牌數(shù)大于或等于輸入弧的權(quán)值，并且該變遷的輸出庫(kù)所已有令牌數(shù)與輸出弧權(quán)值的和小于輸出庫(kù)所的容量；簡(jiǎn)言之，“前面夠用，后面夠放”。,管理系統(tǒng)模擬 馬維忠,170,變遷發(fā)生（點(diǎn)火）的充要條件是該變遷是授權(quán)的。 變遷發(fā)生時(shí)，從該變遷的輸入庫(kù)所中移出與輸入弧權(quán)值相等的令牌數(shù)，在該變遷的輸出庫(kù)所中產(chǎn)生與數(shù)出弧權(quán)值相等的令牌數(shù)。,管理系統(tǒng)模擬 馬維忠,171,管理系統(tǒng)模擬 馬維忠,172,管理系統(tǒng)模擬 馬維忠,173,管理系統(tǒng)模擬 馬維忠,174,在網(wǎng)系統(tǒng)中，可以定義變遷之間的順序、并發(fā)、沖突和沖撞關(guān)系，如下圖。另外，庫(kù)所集還存在死鎖和陷阱的可能性。,管理系統(tǒng)模擬 馬維忠,175,管理系統(tǒng)模擬 馬維忠,176,管理系統(tǒng)模擬 馬維忠,177,管理系統(tǒng)模擬 馬維忠,178,管理系統(tǒng)模擬 馬維忠,179,管理系統(tǒng)模擬 馬維忠,180,定時(shí)Petri網(wǎng)（Timed Petri Net）考慮事件發(fā)生到結(jié)束所需的時(shí)間。它將每一時(shí)間標(biāo)在對(duì)應(yīng)的庫(kù)所旁，這樣庫(kù)所中的令牌要經(jīng)過(guò)一段時(shí)間才能參與到Petri網(wǎng)的運(yùn)行。,管理系統(tǒng)模擬 馬維忠,181,也可以將時(shí)間標(biāo)在變遷上，這樣授權(quán)發(fā)生的變遷需要延遲一段時(shí)間才能發(fā)生； 或者變遷發(fā)生后立即叢輸入庫(kù)所移走相應(yīng)數(shù)量的令牌，但要延遲一定的時(shí)間才在輸出庫(kù)所產(chǎn)生令牌。,管理系統(tǒng)模擬 馬維忠,182,高級(jí)Petri網(wǎng)（High-level Nets）給令牌賦予某種屬性，以豐富Petri網(wǎng)的模型語(yǔ)義。 典型的高級(jí)Petri網(wǎng)有謂詞/變遷網(wǎng)（Predicate/Transition Nets），著色Petri網(wǎng)（Colored Petri Nets, CPN）和隨機(jī)Petri網(wǎng)（Statistic Petri Nets, SPN）。,管理系統(tǒng)模擬 馬維忠,183,謂詞變遷網(wǎng)為變遷的發(fā)生規(guī)定了謂詞條件； 著色Petri網(wǎng)為網(wǎng)中每一個(gè)庫(kù)所定義了一個(gè)令牌色彩集，并且為網(wǎng)中的每一個(gè)變遷定義了一個(gè)動(dòng)作色彩集； 隨機(jī)Petri網(wǎng)則把變遷的發(fā)生看作是一個(gè)隨機(jī)過(guò)程，其持續(xù)時(shí)間服從一定的概率分布。,三、物理模型及建模,模型結(jié)構(gòu) 程序設(shè)計(jì) 實(shí)例,管理系統(tǒng)模擬 馬維忠,185,前面一講介紹了離散事件系統(tǒng)模型的建模方法。 為了使模型能在計(jì)算機(jī)上運(yùn)行，需要將系統(tǒng)模型轉(zhuǎn)換為仿真模型（也稱(chēng)計(jì)算機(jī)模型，Computerized Model），這是從模型到計(jì)算機(jī)仿真的一個(gè)必不可少的步驟。,管理系統(tǒng)模擬 馬維忠,186,將系統(tǒng)模型轉(zhuǎn)換為一個(gè)可以在計(jì)算機(jī)上運(yùn)行的仿真模型，一般需要完成三部分工作： 設(shè)計(jì)仿真策略，具體地說(shuō)，就是確定仿真模型的控制邏輯和仿真時(shí)鐘推進(jìn)機(jī)制； 構(gòu)造仿真模型，即確定模型的具體操作； 仿真程序設(shè)計(jì)與實(shí)現(xiàn)，即采用某種程序設(shè)計(jì)方法及語(yǔ)言，實(shí)現(xiàn)仿真策略和仿真模型。,管理系統(tǒng)模擬 馬維忠,187,上述過(guò)程稱(chēng)為仿真模型的設(shè)計(jì)與實(shí)現(xiàn)。,管理系統(tǒng)模擬 馬維忠,188,3.1 仿真策略,要將系統(tǒng)模型轉(zhuǎn)換為計(jì)算機(jī)模型，首先要從總體上確定仿真模型的控制邏輯和仿真時(shí)鐘推進(jìn)機(jī)制，即確定仿真策略。 仿真策略是仿真模型的核心，反映了仿真模型的本質(zhì)，從根本上決定了仿真模型的結(jié)構(gòu)。,管理系統(tǒng)模擬 馬維忠,189,迄今為止，離散事件系統(tǒng)已形成三種基本的仿真策略，分別是 事件調(diào)度法（Event Scheduling, ES） 活動(dòng)掃描法（Activity Scanning, AS） 進(jìn)程交互法（Process Interaction, PI）。 其它仿真策略均是以這三種仿真策略為基礎(chǔ)的。,管理系統(tǒng)模擬 馬維忠,190,3.1.1 事件調(diào)度法,事件調(diào)度法最早于1963年由蘭德公司的Markowitz等人提出。 它的基本思想是，將事件例程作為仿真模型的基本模型單元，按照事件發(fā)生的先后順序不斷執(zhí)行相應(yīng)的事件例程。 每一事先可預(yù)知其發(fā)生時(shí)間的確定事件都帶有一個(gè)事件例程，用以處理事件發(fā)生后對(duì)實(shí)體狀態(tài)所產(chǎn)生的影響，并安排后續(xù)事件；條件事件不具有事件例程，對(duì)它的處理隱含在某一確定事件的例程中。,管理系統(tǒng)模擬 馬維忠,191,因此，事件調(diào)度法中所說(shuō)的事件是指確定事件。 對(duì)實(shí)體流程圖法建立的概念模型，一般可采用事件調(diào)度法建立其仿真模型。,管理系統(tǒng)模擬 馬維忠,192,1初始化 置仿真的開(kāi)始時(shí)間t0和結(jié)束時(shí)間tf； 置實(shí)體的初始狀態(tài)； 置初始事件及其發(fā)生時(shí)間ts； 2仿真時(shí)鐘TIME=ts； 3確定當(dāng)前時(shí)鐘TIME下發(fā)生的事件類(lèi)型Ei，i=1,2,n，并按解結(jié)規(guī)則排序； 4如果TIMEtf，執(zhí)行 case Ei of E1：執(zhí)行E1的事件例程，產(chǎn)生后續(xù)事件類(lèi)型及發(fā)生時(shí)間； En：執(zhí)行En的事件例程，產(chǎn)生后續(xù)事件類(lèi)型