隨機過程模擬

1、回顧：n隨機模擬n隨機數(shù)的生成n隨機過程模擬：n建立模型：時間步長，事件表法例子：出行天氣模擬；市場服務；戰(zhàn)爭模擬二、隨機型動態(tài)系統(tǒng)仿真1. 時間步長法n與確定型離散時間動態(tài)系統(tǒng)模擬方法一樣，在進行系統(tǒng)模擬時把整個仿真的時間過程分為許多相等的時間間隔。n步長的長度根據(jù)實際問題來決定, 通過循環(huán)程序控制時間步進的過程。n只是在每一個時間步長上仿真系統(tǒng)動態(tài)時， 引入隨機數(shù)以模擬隨機因素的影響。 n例4.市場服務n超市有兩個出口的收款臺，n兩項服務：收款、裝袋。n兩名職工在出口處工作。n有兩種安排方案：n開一個出口，一人收款、一人裝袋；n開兩個出口，每個人既收款又裝袋。n問商店經(jīng)理應選擇哪一種收款臺

2、的服務方案 n目標：選擇什么方案？n依據(jù)是什么？n主體：顧客和商家n顧客的滿意度排隊時間盡可能的短，服務時間短。n商家希望付出的人力少，得到更好的顧客滿意度。n排隊問題有隨機因素參加隨機模擬n研究開一個收款臺的情況研究開一個收款臺的情況n假設：假設：n 1. 1. 顧客的到達是隨機的。顧客的到達是隨機的。n 2. 2. 收款裝袋的時間是相同的。收款裝袋的時間是相同的。n 3. 3. 收款與裝袋同時進行收款與裝袋同時進行n時間步長法：時間步長法：n 把整個仿真過程分為許多相等的時間間隔把整個仿真過程分為許多相等的時間間隔n 每個間隔為一個時間單位每個間隔為一個時間單位時間步長。時間步長。n 在每

3、個時間步長內(nèi)模擬系統(tǒng)的動態(tài)。在每個時間步長內(nèi)模擬系統(tǒng)的動態(tài)。 n 仿真時鐘：用以控制時間步進的過程仿真時鐘：用以控制時間步進的過程n （每一次步進一個步長）（每一次步進一個步長）n參量、變量：n n(t) 到達顧客人數(shù)，L(t) 隊列長, 服務時間n T1 總合排隊時間, T2 總合服務時間，t 時間步長n模型：平衡關(guān)系n 當L(t)=0 且n(t)=0 時n L(t+t)=L(t); n T1(t+t)=T1(t); T2(t+t)=T2(t);n 否則n L(t+t)=L(t)+n(t)-1;n T1(t+t)=T1(t)+L(t+t) t;n T2(t+t)=T2(t)+ n取時間步長t

4、=1，收款或裝袋的時間=1。n仿真30分鐘內(nèi)收款臺處的排隊情況L=zeros(1,31); % L 等待的顧客人數(shù)，等待的顧客人數(shù)，T1=zeros(1,31); %T1總合等待時間，總合等待時間，T2=zeros(1,31); %T2總合服務時間總合服務時間,L1=zeros(1,31); %L1總合到達顧客人數(shù)?？偤系竭_顧客人數(shù)。t=1;tau=1;x=0:30;r=rand(1,30); %隨機數(shù)隨機數(shù)%隨機模擬隨機模擬顧客到來情況顧客到來情況for i=1:30; t=t+1; if 0=r(i) & r(i)0.4 n=0; elseif 0.4=r(i) & r(i)eL)L3=s

5、um(L(L2) %未被服務的顧客等待時未被服務的顧客等待時間總和間總和g1=(T1(end)-L3)/eL %平均等待時間平均等待時間g2=g1+tau %平均逗留時間平均逗留時間g3=eL/30 %平均每分鐘服務的顧客人數(shù)平均每分鐘服務的顧客人數(shù)na=x,r,L,L1,T1,T2 n 0 0 0 0 0 0n 1.0000 0.0153 0 0 0 0n 2.0000 0.7468 1.0000 2.0000 1.0000 1.0000n 3.0000 0.4451 1.0000 3.0000 2.0000 2.0000n 4.0000 0.9318 2.0000 5.0000 4.000

6、0 3.0000n 5.0000 0.4660 2.0000 6.0000 6.0000 4.0000n 6.0000 0.4186 2.0000 7.0000 8.0000 5.0000n 7.0000 0.8462 3.0000 9.0000 11.0000 6.0000n 8.0000 0.5252 3.0000 10.0000 14.0000 7.0000n 9.0000 0.2026 2.0000 10.0000 16.0000 8.0000n 10.0000 0.6721 2.0000 11.0000 18.0000 9.0000n 11.0000 0.8381 3.0000 13

7、.0000 21.0000 10.0000n 12.0000 0.0196 2.0000 13.0000 23.0000 11.0000n 13.0000 0.6813 2.0000 14.0000 25.0000 12.0000n 14.0000 0.3795 1.0000 14.0000 26.0000 13.0000n 15.0000 0.8318 2.0000 16.0000 28.0000 14.0000n 16.0000 0.5028 2.0000 17.0000 30.0000 15.0000n 17.0000 0.7095 3.0000 19.0000 33.0000 16.0

8、000n 18.0000 0.4289 3.0000 20.0000 36.0000 17.0000n 19.0000 0.3046 2.0000 20.0000 38.0000 18.0000n 20.0000 0.1897 1.0000 20.0000 39.0000 19.0000n 21.0000 0.1934 0 20.0000 39.0000 20.0000n 22.0000 0.6822 0 21.0000 39.0000 21.0000n 23.0000 0.3028 0 21.0000 39.0000 21.0000n 24.0000 0.5417 0 22.0000 39.

9、0000 22.0000n 25.0000 0.1509 0 22.0000 39.0000 22.0000n 26.0000 0.6979 0 23.0000 39.0000 23.0000n 27.0000 0.3784 0 23.0000 39.0000 23.0000n 28.0000 0.8600 1.0000 25.0000 40.0000 24.0000n 29.0000 0.8537 2.0000 27.0000 42.0000 25.0000n 30.0000 0.5936 2.0000 28.0000 44.0000 26.0000neL= 26 %已被服務的人數(shù)n（30分

10、鐘內(nèi)服務的顧客人數(shù)）nL2 = 30 31nL3 = 4 %未被服務的顧客等待時間總和ng1 = 1.5385 %（已被服務顧客）平均等待時間ng2 = 2.5862 %平均逗留時間n=平均等待時間+服務時間ng3 = 0.8667 %平均每分鐘服務的顧客人數(shù)n注意：n必須經(jīng)過多次模擬，求得統(tǒng)計意義上的顧客平均等待時間，以及平均每分鐘服務人數(shù)。n問題1. 編寫設兩個收款臺時的仿真程序，根據(jù)兩個模擬結(jié)果評價兩個方案n問題2. 編寫設一個收款臺，取時間步長t=1，收款和裝袋的時間=2的仿真程序。 n2. 事件表法（面向事件法）：n將整個仿真過程分解成時間點的序列，按事件發(fā)生的前后順序逐個進行分析。

11、n每處理一個事件就前進一步，每步的時間可能不同，記錄每步的時間。n每前進一步，對系統(tǒng)狀態(tài)計算更新一次，稱為仿真計算。記錄狀態(tài)變化。n設置狀態(tài)閾值或停止時間，結(jié)束仿真過程。得到系統(tǒng)狀態(tài)隨時間變化全過程。例4. 市場服務一個收款臺情況假設：1.顧客的到達收款臺是隨機的，平均時間間隔為0.5分鐘，即間隔時間服從=2的(負)指數(shù)分布。2.對不同的顧客收款和裝袋的時間服從正態(tài)分布 N(1，1/3)。參量，變量： t(i): 第i位顧客到達時間， t2(i):第i位顧客受到的服務時間(隨機變量)，T(i): 第i位顧客離去時間.將第i位顧客到達作為第i件事發(fā)生; t(i+1)- t(i)= t1(i) (

12、隨機變量)平衡關(guān)系：當 t(i+1)T(i) 時, T(i+1)=t(i+1)+t2(i+1);否則, T(i+1)=T(i)+t2(i+1)模擬20位顧客到收款臺前的排隊情況。注：1.練習寫隨機過程仿真?zhèn)未a。2.多次模擬，得統(tǒng)計意義上的平均等待時間等。MatlabMatlab程序程序function y=paiduiren(n)t=zeros(1,n);%每位顧客到達時間T=zeros(1, n);%每位顧客離去時間w=zeros(1, n);%顧客等待時間累加t1=exprnd(2,1, n);%服從均值為2的指數(shù)分布的隨機數(shù) t2=normrnd(1,1/3,1, n);%服從正態(tài)分布

13、的隨機數(shù)t(1)=t1(1); T(1)=t(1)+t2(1);for i=1:n-1 t(i+1)=t(i)+t1(i); if t(i+1)=T(i); T(i+1)=t(i+1)+t2(i+1); w(i+1)=w(i); else T(i+1)=T(i)+t2(i+1); w(i+1)=T(i)-t(i+1)+w(i);end;end;g1=w(end)/n; %平均等待時間g2=sum(T-t)/n; %平均逗留時間g3= n / T(end);%平均每分鐘服務的顧客人數(shù)y=g1 g2 g3;問題3.進一步建模分析市場服務的問題， 10. 假設一位服務員收款又裝袋所需的服務時間服從正

14、態(tài)分布 N(2，2/3)，兩位服務員分別收款裝袋所需的服務時間服從正態(tài)分布 N(1，1/3). 20. 假設顧客到達的平均時間間隔是0.9分鐘。根據(jù)兩個模擬結(jié)果評價兩個服務員在一個收款臺和分別在兩個收款臺的工作方案。兩個款臺：由于一位服務員既要收款又要裝袋，所以設一個收款臺的服務時間服從正態(tài)分布 N(2，2/3)。平衡關(guān)系：當 t(i+1)max(T(i),T(i-1)，即前兩位顧客都已離開收款臺，或t(i+1)max(min(T(i),T(i-1),max(T(1:i-2) 即前兩位顧客中至少有一位已經(jīng)離開，兩位之前的顧客都已離開時，第i+1位顧客到達收款處時至少有一個收款臺是空閑著， 所以

15、他馬上接受服務 T(i+1)=t(i+1)+t2(i+1)，沒有增加顧客等待的總時間; n否則, 他要排隊等待前兩位中還逗留在收款臺的那位顧客離去n或在兩位前的某位因收款拖延較長時間的顧客離去，n記他跟隨的那位顧客的離去時間為k,即nk=max(min(T(i),T(i-1),max(T(1:i-2),n則 T(i+1)=k+t2(i+1)，n顧客等待的總時間增加 k-t(i+1)。n例 5*. 計劃對敵方一個有很好的防衛(wèi)的目標使用高空戰(zhàn)略轟炸機實行空中打擊。 n 每一架轟炸機如果它能夠穿過空中防線且發(fā)現(xiàn)目標n將有0.5的可能摧毀目標。n轟炸機發(fā)現(xiàn)目標的概率是0.9。n目標由兩個地對空導彈（S

16、AM）陣地和若干防空火炮保護。n飛機的飛行高度使得它們有效的避開了防空火炮。n每一個SAM陣地有它自己的計算機指揮設備它能夠跟蹤兩架飛機，同時指揮兩枚導彈。n情報估計一枚導彈有0.6的概率摧毀目標飛行器。n兩個SAM陣地共用一個目標搜索雷達，n雷達對于5英里以上的高空轟炸機非常有效。n搜索雷達的有效范圍是15英里。n轟炸機以500英里/小時的速度在5英里的高空飛行n發(fā)起攻擊需要在目標的上空盤旋一分鐘。n每一個SAM陣地每30秒可以發(fā)射一枚導彈，n導彈以1000英里/小時的速度飛行。n要派出多少架轟炸機才能確保摧毀這個目標。n分析:n1. 我們希望知道要多少架飛機去完成這個任務。目的是摧毀目標，

17、n我們不可能要求100%地保證成功。 n希望有99%的把握摧毀目標。n稍后我們將在這個數(shù)上做靈敏性分析。n2. 假設N架飛機被派出執(zhí)行這個任務。n在它們完成攻擊目標之前被空防擊落的飛機的數(shù)目是隨機變量。n用X表示這個隨機變量。n3. 為了得到任務完成的概率S的表達式，n我們將分成兩個階段進行。n首先將得到給定在完成攻擊目標的任務之前nX = i 架飛機被擊落時任務完成的概率Pi。n一旦將得到X的概率分布，這時就可以算出n S=PiPrX=i n 4. 如果N架飛機被派出同時X= i 在它們到達目標之前被擊落，這時就有（N - i）架攻擊的飛機n如果 p 是一架攻擊的飛機摧毀目標的概率，n則（1

18、 - p）為一架攻擊的飛機沒有摧毀目標的概率n(N i) 架攻擊的飛機至少一架摧毀目標的概率是 n Pi=1-(1-p)N-i,n5. 在飛往目標的途中在攻擊之前暴露于空中防線的全部時間是n同時再加上在目標上空盤旋的一分鐘，一共是2.8分n在這段時間內(nèi)每個SAM陣地可以發(fā)射5枚導彈。n于是，攻擊的飛機將暴露于總共m10枚導彈的射程之內(nèi)。n我們假設被擊落的飛機的數(shù)量X將有二項分布分小時分小時英里英里8 . 160/50015其中其中q 表示導彈成功擊落飛機的概率。表示導彈成功擊落飛機的概率。imiimqqCiX)1 (Prn假設：n1. 每一架飛機發(fā)現(xiàn)目標是獨立的，且以相同的概率發(fā)現(xiàn)目標；n2.

19、 SAM陣地不會朝著同一架飛機射擊兩次。n參量、變量： nN = 派出的轟炸機的數(shù)量 nm = 發(fā)射的導彈的數(shù)量 np = 一架轟炸機能夠摧毀目標的概率 nq = 一枚導彈能夠擊落轟炸機的概率 X = 攻擊之前被擊落的轟炸機的數(shù)量 nPi = 給定X = i 完成任務的概率 n目標： 求最小的N使得S0.99 n模型n算法： BOMBING RUN PROBLEMn變量： N = 派出的轟炸機的數(shù)量n m = 發(fā)射的導彈的數(shù)量n p = 一架轟炸機能夠摧毀目標的概率n q = 一枚導彈能夠擊落轟炸機的概率n S = 任務完成的最終概率n輸入： N，m，p，qn過程：過程：n Begin n S

20、0n for i=0 to m don Begin n P 1-(1-p)N-1n B Binomial(m, I, q)n S S+PBn Endn Endn輸出：輸出： S n輸入輸入n m=10, p=0.90.5, q=0.6n取不同的取不同的N進行模擬，可以得到進行模擬，可以得到nN 10 11 12 13 14 15 16 17 18 19 20 nS .86 .92 .96 .978 .988 .99 .992 .998 .999n結(jié)論結(jié)論n最少需要最少需要N = 15架飛機架飛機n才能保證有才能保證有99%的可能完成任務。的可能完成任務。 n靈敏性分析靈敏性分析n壞的天氣將降低發(fā)現(xiàn)目標的概率，它是壞的天氣將降低發(fā)現(xiàn)目標的概率，它是p=0.90.5 的一個因子，的一個因子，n如果發(fā)現(xiàn)目標的概率如果發(fā)現(xiàn)目標的概率0.9降低到降低到0.5，n則則 p = 0.25，n對于對于S 0.99我們將需要至少我們將需要至少N = 23架飛機。架飛機。n如果發(fā)現(xiàn)目標的概率是如果發(fā)現(xiàn)目標的概率是0.3，n則需要則需要N = 35架飛機。架飛機。 n在壞的天氣