系統(tǒng)模擬課件

緒論建模理論、模擬和性能評(píng)價(jià)技術(shù)簡(jiǎn)介建模與仿真的歷史發(fā)展1600－1940 在物理學(xué)基礎(chǔ)上的建模20世紀(jì)40年代計(jì)算機(jī)出現(xiàn)20世紀(jì)50年代仿真應(yīng)用于航空領(lǐng)域20世紀(jì)60年代工業(yè)操作過(guò)程的方真20世紀(jì)70年代社會(huì)、經(jīng)濟(jì)和環(huán)境等20世紀(jì)80年代集成化建模與仿真環(huán)境20世紀(jì)90年代可視化建模與仿真、虛擬現(xiàn)實(shí)仿真、分布交互仿真1.1建模與仿真的基本概念建模活動(dòng)是具有特殊形式的人與外界的相互作用模型的建立或形式化，產(chǎn)生出一個(gè)現(xiàn)實(shí)世界系統(tǒng)的模型，是通過(guò)建立一種抽象的表示方法以獲得對(duì)自然現(xiàn)象的充分理解對(duì)形式化的模型進(jìn)行分析和利用，以掌握如何按照人的意志對(duì)現(xiàn)實(shí)系統(tǒng)進(jìn)行控制仿真程序的運(yùn)行，該程序表示了一個(gè)抽象的模型，用來(lái)研究顯示系統(tǒng)的一些特性1.1建模與仿真的基本概念實(shí)際系統(tǒng)模型計(jì)算機(jī)建模仿真修正1.1建模與仿真的基本概念建模關(guān)系主要研究實(shí)際系統(tǒng)與模型之間的關(guān)系對(duì)實(shí)際系統(tǒng)的觀測(cè)和檢測(cè)，忽略次要因素即不可檢測(cè)變量用數(shù)學(xué)的方法進(jìn)行描述，從而獲得實(shí)際系統(tǒng)的簡(jiǎn)化近似模型1.1建模與仿真的基本概念仿真主要研究計(jì)算機(jī)的程序?qū)崿F(xiàn)與模型之間的關(guān)系程序能為計(jì)算機(jī)所接收并能在計(jì)算機(jī)上運(yùn)行1.1建模與仿真的基本概念實(shí)際系統(tǒng)自然的人工的未來(lái)計(jì)劃的三要素實(shí)體組成系統(tǒng)的具體對(duì)象（相對(duì)獨(dú)立、相互聯(lián)系）屬性實(shí)體特征的描述，用特征參數(shù)或變量表示活動(dòng)實(shí)體在一段時(shí)間內(nèi)進(jìn)行的操作或過(guò)程1.1建模與仿真的基本概念例子（進(jìn)銷(xiāo)存系統(tǒng)）實(shí)體經(jīng)理部門(mén)商品倉(cāng)庫(kù)職員商品屬性生產(chǎn)日期、進(jìn)貨價(jià)格、庫(kù)存數(shù)量等屬性某段時(shí)間庫(kù)存商品數(shù)量的變化1.1建模與仿真的基本概念系統(tǒng)模型用來(lái)收集系統(tǒng)有關(guān)信息和描述系統(tǒng)的有關(guān)實(shí)體模型是為了產(chǎn)生行為數(shù)據(jù)的一組指令，可以用數(shù)學(xué)公式、圖、表等形式表示模型是對(duì)應(yīng)的真實(shí)對(duì)象和真實(shí)關(guān)系中那些有用的和令人感興趣的特性的抽象，是系統(tǒng)某些本質(zhì)的描述模型的描述可視為對(duì)真實(shí)世界中的物體和過(guò)程的相關(guān)信息進(jìn)行形式化的結(jié)果模型是系統(tǒng)的代表，同時(shí)也是系統(tǒng)的簡(jiǎn)化1.1建模與仿真的基本概念從系統(tǒng)構(gòu)造模型建立模型選擇系統(tǒng)的邊界，鑒別系統(tǒng)的實(shí)體、屬性、活動(dòng)提供數(shù)據(jù)能夠使包含在活動(dòng)中的各個(gè)屬性之間有確定的關(guān)系1.1建模與仿真的基本概念選擇模型結(jié)構(gòu)細(xì)化模型研究的目的了解有特定關(guān)系的建模目標(biāo)與系統(tǒng)結(jié)構(gòu)性質(zhì)之間的關(guān)系模型結(jié)構(gòu)的性質(zhì)相似性簡(jiǎn)單性多面性1.1建模與仿真的基本概念模型是否有效？實(shí)際系統(tǒng)的數(shù)據(jù)和模型產(chǎn)生的數(shù)據(jù)之間是否符合，符合程度實(shí)際系統(tǒng)數(shù)據(jù)？＝模型產(chǎn)生的數(shù)據(jù)分三個(gè)級(jí)別1.1建模與仿真的基本概念復(fù)制有效黑箱，模型產(chǎn)生的輸入輸出數(shù)據(jù)和實(shí)際系統(tǒng)得到的輸入輸出數(shù)據(jù)相匹配預(yù)測(cè)有效對(duì)模型總體結(jié)構(gòu)了解可預(yù)測(cè)實(shí)際系統(tǒng)將來(lái)的狀態(tài)和行為變化，實(shí)際系統(tǒng)取得數(shù)據(jù)前，由模型可以看出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)有效能重復(fù)觀察實(shí)際系統(tǒng)的行為能反映實(shí)際系統(tǒng)產(chǎn)生這個(gè)行為的操作過(guò)程1.1建模與仿真的基本概念模型的非形式描述實(shí)體包括參變量的描述變量實(shí)體之間的相互關(guān)系必要的描述為模型的形式描述、程序描述、有效性等打下基礎(chǔ)1.1建模與仿真的基本概念仿真關(guān)注計(jì)算機(jī)執(zhí)行模型所規(guī)定的指令的真實(shí)性模型的程序能否真實(shí)地體現(xiàn)模型所具有的內(nèi)涵，稱之為程序的正確性細(xì)分為5要素：實(shí)際系統(tǒng)實(shí)驗(yàn)框架基本模型集總模型計(jì)算機(jī)1.1建模與仿真的基本概念實(shí)際系統(tǒng)輸入輸出的行為實(shí)際系統(tǒng)抽象為可觀察的數(shù)據(jù)源，即為系統(tǒng)的行為實(shí)驗(yàn)框架有效性觀測(cè)實(shí)際系統(tǒng)和做有關(guān)實(shí)驗(yàn)的環(huán)境的一個(gè)有限集為實(shí)際系統(tǒng)輸入輸出行為的一個(gè)子集某種條件假設(shè)，某種限制模型的有效性和實(shí)驗(yàn)框架有關(guān)1.1建模與仿真的基本概念計(jì)算機(jī)復(fù)雜性仿真所需時(shí)間程序所需空間排除故障、調(diào)整參數(shù)和實(shí)驗(yàn)框架1.2性能評(píng)價(jià)性能的分類處理能力計(jì)算速度：峰值速度；持續(xù)可用速度；定點(diǎn)、浮點(diǎn)運(yùn)算速度吞吐率：?jiǎn)挝粫r(shí)間內(nèi)計(jì)算機(jī)系統(tǒng)完成的任務(wù)數(shù)（這是系統(tǒng)管理員所關(guān)心的）響應(yīng)時(shí)間／平均響應(yīng)時(shí)間：從計(jì)算機(jī)系統(tǒng)得到輸入到給出輸出結(jié)果之間的時(shí)間。這是用戶所關(guān)心的1.2性能評(píng)價(jià)可靠性：計(jì)算機(jī)系統(tǒng)正常工作的能力包含兩個(gè)方面的含義首先是計(jì)算機(jī)系統(tǒng)是可靠的一旦計(jì)算機(jī)系統(tǒng)發(fā)生故障時(shí)計(jì)算機(jī)系統(tǒng)的容錯(cuò)能力利用率硬件利用率、軟件利用率、指令利用率，即在一段時(shí)間內(nèi)被使用的時(shí)間（次數(shù)）占總時(shí)間（總使用次數(shù)）的百分比率這是計(jì)算機(jī)系統(tǒng)的設(shè)計(jì)人員、管理人員所關(guān)心的1.2性能評(píng)價(jià)易用性功耗及對(duì)環(huán)境的要求1.2性能評(píng)價(jià)性能評(píng)價(jià)以這些性能標(biāo)準(zhǔn)為基礎(chǔ)性能標(biāo)準(zhǔn)可以分為三類：越高也好越低越好適中為好1.2性能評(píng)價(jià)工作負(fù)載（workload）工作負(fù)載是指用戶給計(jì)算機(jī)系統(tǒng)的輸入，如程序、數(shù)據(jù)命令等上述性能指標(biāo)與工作負(fù)載的大小、類型有很大關(guān)系1.2性能評(píng)價(jià)系統(tǒng)性能評(píng)價(jià)的產(chǎn)生在60年代中期，多任務(wù)、多用戶計(jì)算機(jī)系統(tǒng)的出現(xiàn)，使人們發(fā)現(xiàn)，系統(tǒng)的實(shí)際性能不如預(yù)計(jì)性能高，故引發(fā)了對(duì)計(jì)算機(jī)系統(tǒng)性能評(píng)價(jià)的研究1.2性能評(píng)價(jià)奧運(yùn)售票系統(tǒng)為例10月30日，因系統(tǒng)負(fù)載過(guò)大而導(dǎo)致歌華特瑪捷系統(tǒng)癱瘓實(shí)際訪問(wèn)量800萬(wàn)次/小時(shí)，設(shè)計(jì)訪問(wèn)量100萬(wàn)次/小時(shí)該系統(tǒng)于11月2日完成軟件故障修正后的系統(tǒng)功能測(cè)試，11月3日完成系統(tǒng)壓力測(cè)試因系統(tǒng)初始設(shè)計(jì)問(wèn)題，由“先到先得”的方式改為“抽簽售票”方式系統(tǒng)在設(shè)計(jì)時(shí)沒(méi)有超負(fù)荷情況的考慮可用性沒(méi)有經(jīng)過(guò)充分的評(píng)測(cè)處理性能與可用性融合的評(píng)測(cè)要始終貫穿于系統(tǒng)設(shè)計(jì)、原型與應(yīng)用的全過(guò)程

建模的邏輯方法抽象歸納演繹類比移植建模的邏輯方法抽象揭示事物的共性和聯(lián)系的規(guī)律，忽略每個(gè)具體事物的特殊性，著眼于整體和一般規(guī)律例子四條腿的凳子只需原地旋轉(zhuǎn)就能四只腳著地、放穩(wěn)

建模的邏輯方法關(guān)鍵是用數(shù)學(xué)語(yǔ)言把四只腳同時(shí)著地的條件和結(jié)論表示出來(lái)椅子的位置和調(diào)整的表述椅子腳連線成正方形，以中心點(diǎn)對(duì)稱，正方形圍繞圓心旋轉(zhuǎn)表示了椅子位置的改變假設(shè)椅子位置調(diào)整中只是旋轉(zhuǎn)而沒(méi)有平移因此可以用旋轉(zhuǎn)角度這一變量來(lái)表示椅子的位置

建模的邏輯方法建模的邏輯方法腳著地的數(shù)學(xué)表示用變量表示椅腳與地面的距離變量為零時(shí)，四腳著地需引入四個(gè)變量化簡(jiǎn)正方形中心對(duì)稱，只需計(jì)算兩個(gè)距離即可A、C與地面的距離之和為B、D與地面的距離之和為建模的邏輯方法三腳著地和四腳著地的描述椅子在任何位置至少有三只腳著地即任意至少有一個(gè)為零因此恒有當(dāng)＝0時(shí)，不妨設(shè)g()=0，f()>0，若四條腿一樣長(zhǎng)，旋轉(zhuǎn)90度后，只是兩個(gè)對(duì)角線互換，因此當(dāng)＝π/2時(shí)，f()=0，g()>0在＝0時(shí)，四腳著地，即f(0)=g(0)＝0

建模的邏輯方法模型假設(shè)四條腿一樣長(zhǎng)地面高度連續(xù)變化對(duì)腿腳和椅腿的長(zhǎng)度來(lái)說(shuō)，地面相對(duì)平坦，椅子在任何位置至少有三條腿同時(shí)著地建模的邏輯方法模型構(gòu)成令f()為A、C與地面距離之和，g()為B、D與地面距離之和f()和g()是的連續(xù)函數(shù)模型表述如下建模的邏輯方法模型求解建模的邏輯方法歸納從特殊的具體的認(rèn)識(shí)推進(jìn)到一般的抽象的認(rèn)識(shí)的一種思維方式開(kāi)普勒從第谷數(shù)據(jù)中，歸納出行星運(yùn)行的三個(gè)定律行星橢圓軌道，太陽(yáng)位于其中一個(gè)焦點(diǎn)上單位時(shí)間內(nèi)，太陽(yáng)－行星掃過(guò)的面積是一個(gè)常數(shù)（對(duì)一顆行星而言）行星運(yùn)行周期T的平方與其橢圓軌道的長(zhǎng)半軸a的三次方成正比

建模的邏輯方法行星周期T長(zhǎng)半軸aT2a3水星0.2410.3870.0580.058金星0.6150.7230.3780.378地球1.0001.0001.0001.000火星1.8811.5243.5403.540木星11.8625.203140.700140.700土星29.4579.539867.700867.700建模的邏輯方法演繹由一般性的命題推出特殊命題的推理方法特殊情況明晰化有助于科學(xué)的理論化和體系化牛頓利用微積分工具在開(kāi)普勒三定律和牛頓第二定律的基礎(chǔ)上，演繹出萬(wàn)有引力定律

建模的邏輯方法類比在兩個(gè)完全不同的事物之間進(jìn)行對(duì)比，找出若干相同或相似點(diǎn)之后，推測(cè)在其他方面也可能存在相同或相似之處的一種思維方式

建模的邏輯方法移植一個(gè)領(lǐng)域的理論或行之有效的研究方法、研究手段移用到其它領(lǐng)域去把問(wèn)題的關(guān)鍵與已有的理論和原理聯(lián)系起來(lái)，與既存事實(shí)聯(lián)系起來(lái)，從而構(gòu)成一個(gè)新的模型或挖掘其本質(zhì)的概念與思想建模的邏輯方法計(jì)算圓周率π的浦豐投針模型是運(yùn)用移植法的一個(gè)例子幾何概率和大數(shù)定理問(wèn)題描述在平面上等距當(dāng)?shù)禺?huà)一些平行線，相鄰兩條線的距離為a，向此平面任投一長(zhǎng)度為l(l<a)的針用x表示針的中點(diǎn)到最近的一條平行線的距離，φ表示針與平行線的交角

建模的邏輯方法lφxa

建模的邏輯方法針與線相交的條件是建模的邏輯方法此針與任何一條平行線相交的概率為：例子N個(gè)盒子m個(gè)球的方法總數(shù)問(wèn)題（麥克斯韋爾－玻耳茲曼模型），球可分辨，每個(gè)盒子放球的數(shù)目無(wú)限制，方法總數(shù)為：例子（波司－愛(ài)因斯坦分布）球不可分辨，每個(gè)盒子容納的球數(shù)沒(méi)有限制，方法總數(shù)例子費(fèi)米－狄拉克模型，球不可分辨，每個(gè)盒子至多裝一個(gè)球，方法總數(shù)為

概率論基礎(chǔ)相對(duì)頻率定義執(zhí)行一個(gè)經(jīng)驗(yàn)若干次，每一次叫一個(gè)考驗(yàn)。在一個(gè)考驗(yàn)中，觀察事件A是否發(fā)生事件A的概率P(A)定義概率論基礎(chǔ)條件概率在某種事件條件下的概率條件的影響是刪除樣本空間的一些結(jié)果假定事件B已經(jīng)發(fā)生，事件A的條件概率P(A|B)定義為概率論基礎(chǔ)乘法定理設(shè)P(A)>0，有條件概率定義有設(shè)A1,A2,…,An為n個(gè)事件，且P(A1A2…An-1)>0，有概率論基礎(chǔ)全概率公式：給定一組互斥事件E1,E2,

,En，這些事件的并覆蓋所有可能結(jié)果，一個(gè)任意事件A的總概率為概率論基礎(chǔ)貝葉斯（Bayes）公式后驗(yàn)概率，反過(guò)來(lái)計(jì)算已知“結(jié)果”而它是某個(gè)“原因”產(chǎn)生的條件概率概率論基礎(chǔ)例傳輸一組0和1的信號(hào)S0和S1分別是在給定時(shí)間一個(gè)0和一個(gè)1被傳送的事件R0和R1分別是在給定時(shí)間一個(gè)0和一個(gè)1被接收的事件傳輸源的概率，P(S1)＝p，P(S0)＝1–pP(R0|S1)=pa和P(R1|S0)=pb給定一個(gè)0被收到而一個(gè)1被發(fā)送的條件概率？概率論基礎(chǔ)使用貝葉斯公式有：概率論基礎(chǔ)隨機(jī)變量是一個(gè)試驗(yàn)所有可能輸出事件集合(樣本空間

)向?qū)崝?shù)的一個(gè)映射

隨機(jī)變量映射輸出事件到實(shí)數(shù)是給事件一個(gè)數(shù)值解釋

一個(gè)試驗(yàn)連同許多可能結(jié)果，一個(gè)隨機(jī)變量對(duì)每一個(gè)結(jié)果分配一個(gè)值

概率論基礎(chǔ)連續(xù)的隨機(jī)變量X：分布函數(shù)F(x)和密度函數(shù)f(x)分布函數(shù)密度函數(shù)概率論基礎(chǔ)離散的隨機(jī)變量X密度函數(shù)分布函數(shù)概率論基礎(chǔ)隨機(jī)變量數(shù)字的特性數(shù)學(xué)期望連續(xù)情況離散情況 概率論基礎(chǔ)方差標(biāo)準(zhǔn)差概率論基礎(chǔ)方差和標(biāo)準(zhǔn)差是圍繞著數(shù)學(xué)期望值的偏離的測(cè)量。對(duì)于一個(gè)常數(shù)a，我們有對(duì)于兩個(gè)隨機(jī)變量X和Y，有概率論基礎(chǔ)重要分布

指數(shù)分布具有參數(shù)

(

>0)的指數(shù)分布密度函數(shù)

分布函數(shù)概率論基礎(chǔ)數(shù)學(xué)期望等于標(biāo)準(zhǔn)離差指數(shù)分布即有無(wú)后效性（無(wú)記憶特性或馬爾可夫特性）當(dāng)涉及一個(gè)服務(wù)時(shí)間時(shí)，分布就假定作為一個(gè)指數(shù)分布隨機(jī)變量概率論基礎(chǔ)無(wú)記憶性概率論基礎(chǔ)例子已知一個(gè)元器件使用了s小時(shí)，它總共能使用s+t小時(shí)的概率與從開(kāi)始算起它至少能使t小時(shí)的概率相等元器件對(duì)它已使用過(guò)的s小時(shí)沒(méi)有記憶概率論基礎(chǔ)如果兩次輸入（到達(dá)）的時(shí)間間隔是服從指數(shù)分布的，無(wú)記憶特征意味著等待一個(gè)新到達(dá)的時(shí)間與我們已經(jīng)等待的時(shí)間是無(wú)關(guān)的離散型隨機(jī)變量的概率分布中，只有幾何分布具有無(wú)后效性連續(xù)性隨機(jī)變量的概率分布中，只有指數(shù)分布具有無(wú)后效性概率論基礎(chǔ)在排隊(duì)論中，常假定排隊(duì)系統(tǒng)中服務(wù)器的服務(wù)時(shí)間是指數(shù)分布的在隨機(jī)Petri網(wǎng)中，變遷的實(shí)施速率也通常假設(shè)為指數(shù)分布使用指數(shù)分布可以簡(jiǎn)化系統(tǒng)性能的分析概率論基礎(chǔ)泊松(Poisson)分布具有參數(shù)

(

>0)的泊松分布，它在0,1,

時(shí)取值概率論基礎(chǔ)如果

<1，那么對(duì)于k＝0,p(X=k)最大如果

>1且不是整數(shù)，那么對(duì)于小于

的最大整數(shù),p(X=k)最大如果

是正整數(shù)，那么在k=

和k=

-1時(shí)存在兩個(gè)最大整數(shù)一般都要假定任務(wù)的到來(lái)是泊松分布的，通常是有效的概率論基礎(chǔ)泊松分布作為到達(dá)速率的方法可描述如下。如果到達(dá)是一個(gè)泊松過(guò)程，可以表達(dá)為p(在時(shí)間間隔T有k個(gè)顧客到達(dá))＝在時(shí)間間隔T顧客到達(dá)的期望數(shù)量=

T

概率論基礎(chǔ)平均到達(dá)速率(顧客數(shù)量/秒)＝

根據(jù)泊松過(guò)程發(fā)生的到達(dá)經(jīng)常被認(rèn)為是隨機(jī)到達(dá)。一個(gè)顧客在一個(gè)小的時(shí)間間隔內(nèi)到達(dá)的概率是與這個(gè)間隔的長(zhǎng)度成正比的，而且是與從上一個(gè)顧客的到達(dá)到離開(kāi)的時(shí)間總量無(wú)關(guān)概率論基礎(chǔ)具有參數(shù)

和

(

>0)的正態(tài)分布有如下密度函數(shù)概率論基礎(chǔ)在一般條件下，大量獨(dú)立隨機(jī)變量的和或均值基本上是一個(gè)正態(tài)分布這個(gè)結(jié)果是中心限定理論，在統(tǒng)計(jì)中有很重要作用概率論基礎(chǔ)多隨機(jī)變量

一個(gè)變量的變化對(duì)其他變量的影響一些相關(guān)性的重要測(cè)量分布函數(shù)密度函數(shù)概率論基礎(chǔ)離散分布函數(shù)對(duì)于任意兩個(gè)隨機(jī)變量X和Y概率論基礎(chǔ)如果F(x,y)=F(x)F(y)且因此f(x,y)=f(x)f(y)，兩個(gè)隨機(jī)變量X和Y叫做統(tǒng)計(jì)無(wú)關(guān)如果隨機(jī)變量X和Y是離散的它們是統(tǒng)計(jì)無(wú)關(guān)的條件是p(x,y)=p(x)p(y)對(duì)于無(wú)關(guān)隨機(jī)變量，有如下關(guān)系E[XY]=E[X]

E[Y]和Var[X+Y]=Var[X]+Var[Y］概率論基礎(chǔ)兩個(gè)隨機(jī)變量X和Y的協(xié)方差(Covariance)定義如下

X和Y的相關(guān)系數(shù)定義如下：概率論基礎(chǔ)隨機(jī)變量的函數(shù)分布在一些試驗(yàn)中，所關(guān)心的隨機(jī)變量不能直接測(cè)到，而是某個(gè)能測(cè)到的隨機(jī)變量的函數(shù)由已知的隨機(jī)變量X的概率分布取求得它的函數(shù)

的分布函數(shù)概率論基礎(chǔ)一維情況概率論基礎(chǔ)兩個(gè)隨機(jī)變量的函數(shù)Z=X+YM＝max（X,Y）N＝min（X,Y）概率論基礎(chǔ)Z=X+Y概率論基礎(chǔ)令x=u-yX,Y相互獨(dú)立概率論基礎(chǔ)M＝max（X,Y），X、Y相互獨(dú)立概率論基礎(chǔ)N＝min（X,Y）），X、Y相互獨(dú)立概率論基礎(chǔ)中心極限定理獨(dú)立同分布的中心極限定理隨機(jī)變量X1，X2，X3，…Xn，…獨(dú)立分布，具有相同的數(shù)學(xué)期望和方差隨機(jī)變量之和的標(biāo)準(zhǔn)化變量：概率論基礎(chǔ)分布函數(shù)滿足概率論基礎(chǔ)拉普拉斯定理服從參數(shù)為n，p(0<p<1)的二項(xiàng)分布，對(duì)任意x，有概率論基礎(chǔ)一艘輪船在某海區(qū)航海，已知每遭受一次波浪沖擊，搖角大于3度的概率為1/3，若船遭受了90000次波浪沖擊，問(wèn)其中有29500～30500次搖角大于3度的概率概率論基礎(chǔ)隨機(jī)過(guò)程的概念概率論的“動(dòng)力學(xué)”部分研究的對(duì)象隨時(shí)間演變的隨機(jī)現(xiàn)象不能用隨機(jī)變量或多維隨機(jī)變量合理表達(dá)例如：電子元器件的熱噪聲電壓在任一時(shí)刻t的值是一個(gè)隨機(jī)變量，記為V(t)不同時(shí)刻對(duì)應(yīng)不同的隨機(jī)變量隨著時(shí)間的推移，熱噪聲電壓表現(xiàn)為一族隨機(jī)變量隨機(jī)過(guò)程的概念設(shè)T是一無(wú)限實(shí)數(shù)集，把依賴于參數(shù)tT的一族（無(wú)限多個(gè)）隨機(jī)變量稱為隨機(jī)過(guò)程（記為｛X(t)，tT｝）對(duì)每一個(gè)tT，X(t)是一個(gè)隨機(jī)變量T為參數(shù)集，X(t)為t時(shí)刻的狀態(tài)隨機(jī)過(guò)程的概念對(duì)于一切tT，X(t)的所有可能取的一切值的全體稱為隨機(jī)過(guò)程的狀態(tài)空間樣本函數(shù)或樣本曲線，對(duì)隨機(jī)過(guò)程的一次試驗(yàn)（在T上進(jìn)行的一次全程觀測(cè)）可看作是多維隨機(jī)變量的延伸隨機(jī)過(guò)程的概念常以X（t），t

T

隨機(jī)過(guò)程表示拋擲一枚硬幣，樣本空間是S＝｛H，T｝，定義隨機(jī)過(guò)程的概念隨機(jī)過(guò)程的概念P(H)=P(T)=1/2對(duì)任意固定的t，X(t)是一定義在S上的隨機(jī)變量對(duì)不同的t，X(t)是不同的隨機(jī)變量所以｛X(t)，t

（-∞，+∞）｝是一族隨機(jī)變量，即是隨機(jī)過(guò)程隨機(jī)過(guò)程的概念隨機(jī)過(guò)程分類按狀態(tài)連續(xù)和離散連續(xù)型隨機(jī)過(guò)程離散型隨機(jī)過(guò)程按時(shí)間（參數(shù)）連續(xù)和離散連續(xù)參數(shù)隨機(jī)過(guò)程離散參數(shù)隨機(jī)過(guò)程或離散隨機(jī)序列隨機(jī)過(guò)程的統(tǒng)計(jì)描述隨機(jī)過(guò)程的分布函數(shù)給定隨機(jī)過(guò)程｛X(t)，t

T｝，對(duì)于每一個(gè)固定的t

T，隨機(jī)變量X(t)的分布函數(shù)一般與t有關(guān)稱其為隨機(jī)過(guò)程｛X(t)，t

T｝的一維分布函數(shù)一維分布函數(shù)族隨機(jī)過(guò)程的統(tǒng)計(jì)描述為了描述隨機(jī)過(guò)程在不同時(shí)刻狀態(tài)之間的統(tǒng)計(jì)聯(lián)系，一般可對(duì)n個(gè)不同時(shí)刻，引入n維隨機(jī)變量，其分布函數(shù)為隨機(jī)過(guò)程｛X(t)，t

T｝的n維分布族函數(shù)：隨機(jī)過(guò)程的統(tǒng)計(jì)描述科爾莫戈羅夫定理有限維分布函數(shù)族完全地確定隨機(jī)過(guò)程的統(tǒng)計(jì)特性隨機(jī)過(guò)程的分類本質(zhì)的分類方法是按其分布特性進(jìn)行分類依照過(guò)程在不同時(shí)刻的狀態(tài)之間的特殊統(tǒng)計(jì)依賴方式，抽象出一些不同類型的模型獨(dú)立增量過(guò)程、馬爾可夫過(guò)程、平穩(wěn)過(guò)程等隨機(jī)過(guò)程的統(tǒng)計(jì)描述隨機(jī)過(guò)程的數(shù)及特征給定隨機(jī)過(guò)程｛X(t)，t

T｝，固定t

T，X(t)是一個(gè)隨機(jī)變量稱μX(t)是隨機(jī)過(guò)程｛X(t)，t

T｝的均值函數(shù)，使所有樣本函數(shù)在時(shí)刻t的函數(shù)值的平均值隨機(jī)過(guò)程的統(tǒng)計(jì)描述隨機(jī)過(guò)程的數(shù)及特征二階原點(diǎn)矩（均方值函數(shù)）二階中心矩（方差函數(shù)）隨機(jī)過(guò)程的統(tǒng)計(jì)描述隨機(jī)過(guò)程的數(shù)及特征二階原點(diǎn)混合矩（自相關(guān)函數(shù)）二階混合中心矩（協(xié)方差函數(shù)）隨機(jī)過(guò)程的統(tǒng)計(jì)描述例設(shè)A、B是兩個(gè)隨機(jī)變量。求隨機(jī)過(guò)程X(t)=At+B的均值函數(shù)和二階混合原點(diǎn)矩。如果A，B相互獨(dú)立，且A～N(0，1)，B～U(0，2)隨機(jī)過(guò)程的統(tǒng)計(jì)描述泊松過(guò)程獨(dú)立增量過(guò)程給定二階矩過(guò)程｛X(t)，t

0｝，對(duì)任意選定的正數(shù)n和任意選定的相互獨(dú)立，則稱｛X(t)，t

0｝為獨(dú)立增量過(guò)程泊松過(guò)程對(duì)于獨(dú)立增量過(guò)程，具有在互不重疊的區(qū)間上，狀態(tài)的增量是相互獨(dú)立的特征若對(duì)任意的實(shí)數(shù)h和0

s+h<t+h，X(t+h)-X(s+h)和X(t)-X(s)具有相同的分布，則稱增量具有平穩(wěn)性增量X(t)-X(s)的分布函數(shù)只依賴與時(shí)間差t-s,而不依賴于t和s本身當(dāng)增量具有平穩(wěn)性時(shí)，稱相應(yīng)的獨(dú)立增量過(guò)程是齊次的或時(shí)齊的泊松過(guò)程X(0)=0在和方差函數(shù)VarX（t）為已知的條件下，可以計(jì)算出獨(dú)立增量過(guò)程｛X(t)，t

0｝的二階中心混合矩CX(s,t)泊松過(guò)程泊松過(guò)程考慮下列隨著時(shí)間的推移遲早會(huì)重復(fù)出現(xiàn)的時(shí)間自電子管陰極發(fā)射的電子到達(dá)陽(yáng)極意外事故或意外差錯(cuò)發(fā)生要求服務(wù)的顧客到達(dá)服務(wù)站泊松過(guò)程為建立一般模型，可以把電子、錯(cuò)誤（故障）、顧客等看作是時(shí)間軸上的質(zhì)點(diǎn)電子到達(dá)陽(yáng)極、顧客到達(dá)服務(wù)站等事件的發(fā)生相當(dāng)于質(zhì)點(diǎn)的出現(xiàn)抽象，研究的對(duì)象是隨著時(shí)間的推移，陸續(xù)出現(xiàn)在時(shí)間軸上的許多質(zhì)點(diǎn)所構(gòu)成的隨機(jī)的質(zhì)點(diǎn)流泊松過(guò)程以N(t)，t

0表示在時(shí)間間隔(0，t]出現(xiàn)的質(zhì)點(diǎn)數(shù)｛N(t)，t

0｝是一狀態(tài)取非負(fù)整數(shù)，時(shí)間連續(xù)的隨機(jī)過(guò)程，稱為計(jì)數(shù)過(guò)程將增量N(t)-N(t0)記做N(t0，t)，0

t0<t

，表示時(shí)間間隔(0，t]內(nèi)出現(xiàn)的質(zhì)點(diǎn)數(shù)事件N(t0，t)＝k的概率記為泊松過(guò)程假設(shè)N(t)滿足如下條件1）在互不重疊的區(qū)間上增量具有獨(dú)立性2）對(duì)充分小的Δt泊松過(guò)程3）對(duì)于充分小的Δt即對(duì)于充分小的Δt，在(t，t+Δt]內(nèi)出現(xiàn)2個(gè)或兩個(gè)以上質(zhì)點(diǎn)的概率與出現(xiàn)一個(gè)質(zhì)點(diǎn)的概率相比可以忽略不計(jì)泊松過(guò)程4）N(0)=0把滿足上述4個(gè)條件的計(jì)數(shù)過(guò)程｛N(t)，t

0｝稱做強(qiáng)度為λ的泊松過(guò)程相應(yīng)的質(zhì)點(diǎn)流或即質(zhì)點(diǎn)出現(xiàn)的隨機(jī)時(shí)刻t1，t2…稱做強(qiáng)度為λ的泊松流泊松過(guò)程對(duì)于泊松過(guò)程，有結(jié)合條件2）和3），有泊松過(guò)程確定P0(t0，t)泊松過(guò)程泊松過(guò)程由P0(t0，t0)＝1泊松過(guò)程現(xiàn)在計(jì)算Pk(t0，t)，k1泊松過(guò)程泊松過(guò)程前面的式子可以表示為泊松過(guò)程即可得到泊松過(guò)程泊松過(guò)程由前面的公式泊松過(guò)程設(shè)質(zhì)點(diǎn)依次重復(fù)出現(xiàn)的時(shí)刻t1，t2，…tn，…是一個(gè)強(qiáng)度為λ的泊松流，以記號(hào)Wn是一個(gè)隨機(jī)變量，表示第n個(gè)質(zhì)點(diǎn)出現(xiàn)的等待時(shí)間泊松過(guò)程首先注意事件｛Wn>t｝={N(t)<n}泊松過(guò)程Wn的概率密度為泊松過(guò)程記Ti＝Wi－Wi-1，稱為相繼出現(xiàn)的第i-1個(gè)質(zhì)點(diǎn)和第i個(gè)質(zhì)點(diǎn)的點(diǎn)間間距T1＝W1,服從指數(shù)分布先求第i-1個(gè)質(zhì)點(diǎn)出現(xiàn)在時(shí)刻ti-1的條件下，Ti的條件分布函數(shù)泊松過(guò)程泊松過(guò)程泊松過(guò)程泊松過(guò)程假設(shè)N(t)滿足如下條件1）在互不重疊的區(qū)間上增量具有獨(dú)立性2）對(duì)充分小的Δt泊松過(guò)程3）對(duì)于充分小的Δt即對(duì)于充分小的Δt，在(t，t+Δt]內(nèi)出現(xiàn)2個(gè)或兩個(gè)以上質(zhì)點(diǎn)的概率與出現(xiàn)一個(gè)質(zhì)點(diǎn)的概率相比可以忽略不計(jì)泊松過(guò)程4）N(0)=0把滿足上述4個(gè)條件的計(jì)數(shù)過(guò)程｛N(t)，t

0｝稱做強(qiáng)度為λ的泊松過(guò)程相應(yīng)的質(zhì)點(diǎn)流或即質(zhì)點(diǎn)出現(xiàn)的隨機(jī)時(shí)刻t1，t2…稱做強(qiáng)度為λ的泊松流泊松過(guò)程確定P0(t0，t)泊松過(guò)程泊松過(guò)程由P0(t0，t0)＝1泊松過(guò)程泊松過(guò)程即可得到泊松過(guò)程泊松過(guò)程由前面的公式泊松過(guò)程設(shè)質(zhì)點(diǎn)依次重復(fù)出現(xiàn)的時(shí)刻t1，t2，…tn，…是一個(gè)強(qiáng)度為λ的泊松流，以記號(hào)Wn是一個(gè)隨機(jī)變量，表示第n個(gè)質(zhì)點(diǎn)出現(xiàn)的等待時(shí)間泊松過(guò)程首先注意事件｛Wn>t｝={N(t)<n}泊松過(guò)程Wn的概率密度為泊松過(guò)程設(shè)質(zhì)點(diǎn)依次重復(fù)出現(xiàn)的時(shí)刻t1，t2，…tn，…是一個(gè)強(qiáng)度為λ的泊松流，以記號(hào)Wn是一個(gè)隨機(jī)變量，表示第n個(gè)質(zhì)點(diǎn)出現(xiàn)的等待時(shí)間泊松過(guò)程記Ti＝Wi－Wi-1，稱為相繼出現(xiàn)的第i-1個(gè)質(zhì)點(diǎn)和第i個(gè)質(zhì)點(diǎn)的點(diǎn)間間距T1＝W1,服從指數(shù)分布先求第i-1個(gè)質(zhì)點(diǎn)出現(xiàn)在時(shí)刻ti-1的條件下，Ti的條件分布函數(shù)泊松過(guò)程泊松過(guò)程泊松過(guò)程泊松過(guò)程泊松過(guò)程的應(yīng)用舉例元器件或系統(tǒng)的可靠度R(t)相當(dāng)于P0(0，t),即系統(tǒng)從啟動(dòng)到失效的平均壽命(MTTF)相當(dāng)于E[W1]，即平均系統(tǒng)失效間隔時(shí)間（MTBF）相當(dāng)于E[Ti]馬爾可夫鏈馬爾可夫鏈時(shí)間、狀態(tài)都是離散的馬爾可夫過(guò)程轉(zhuǎn)移概率的確定遍歷性問(wèn)題馬爾可夫鏈馬爾可夫性（無(wú)后效性）系統(tǒng)（過(guò)程）在時(shí)刻t0所處的狀態(tài)為已知的條件下系統(tǒng)（過(guò)程）在時(shí)刻t>t0所處狀態(tài)的條件分布與系統(tǒng)（過(guò)程）在時(shí)刻t0之前所處的狀態(tài)無(wú)關(guān)在已經(jīng)知道過(guò)程“現(xiàn)在”的條件下，其“將來(lái)”不依賴于“過(guò)去”馬爾可夫鏈馬爾可夫性的數(shù)學(xué)描述設(shè)隨機(jī)過(guò)程｛X(t)，t

T｝的狀態(tài)空間為I。如果對(duì)時(shí)間t的任意n個(gè)數(shù)值t1<t2<…<tn，n3在條件X(ti)=xi，xi

I，i=1,2,…,n-1下，X(tn)的條件分布函數(shù)恰等于在條件X(tn-1)=xn-1的條件分布函數(shù)馬爾可夫鏈寫(xiě)成分布函數(shù)的形式稱過(guò)程｛X(t)，t

T｝具有馬爾可夫性或無(wú)后效性，并稱此過(guò)程為馬爾可夫過(guò)程馬爾可夫鏈例獨(dú)立增量過(guò)程｛X(t)，t

0｝，且X(0)＝0，則｛X(t)，t

0｝是一個(gè)馬爾可夫過(guò)程即已知在X(tn-1)=xn-1的情況下馬爾可夫鏈時(shí)間和狀態(tài)都是離散的馬爾可夫過(guò)程稱為馬爾可夫鏈－馬氏鏈記｛Xn＝X(n)，n＝0，1，2，…｝可以看作是時(shí)間集T1＝｛0，1，2，…｝上對(duì)離散狀態(tài)馬爾可夫過(guò)程相繼觀察的結(jié)果鏈的狀態(tài)空間I＝｛a1，a2，…｝，aiR馬爾可夫鏈對(duì)任意正整數(shù)n，r和馬爾可夫鏈上式稱為馬氏鏈在時(shí)刻m處于狀態(tài)ai條件下，在時(shí)刻m+n轉(zhuǎn)移到狀態(tài)aj的轉(zhuǎn)移概率由于鏈在時(shí)刻m從任何一個(gè)狀態(tài)ai出發(fā)，到另一時(shí)刻m+n，必然轉(zhuǎn)移到a1，a2，…這些狀態(tài)中的某一個(gè)馬爾可夫鏈由轉(zhuǎn)移概率組成的矩陣P(m,m+n)=(Pij(m,m+n))稱為馬氏鏈的轉(zhuǎn)移矩陣轉(zhuǎn)移矩陣的每一行之和為1每一列之和＝？馬爾可夫鏈當(dāng)轉(zhuǎn)移概率Pij(m,m+n)只與i,j及時(shí)間間距n有關(guān)時(shí)，把它記為Pij(n)，即稱此轉(zhuǎn)移概率具有平穩(wěn)性，同時(shí)稱此鏈?zhǔn)驱R次的或時(shí)齊的，并稱下式為n步轉(zhuǎn)移概率馬爾可夫鏈P(n)=(Pij(n))為n步轉(zhuǎn)移矩陣特別重要的為一步轉(zhuǎn)移概率或者是由一步轉(zhuǎn)移概率所組成的矩陣馬爾可夫鏈馬爾可夫鏈例一維隨機(jī)游動(dòng)設(shè)一醉漢Q如圖在直線的點(diǎn)集I＝｛1，2，3，4，5｝作隨機(jī)游動(dòng)如果Q位于i（1<i<5）點(diǎn),則在下一時(shí)刻各以概率1/3向左、右移動(dòng)一格或在原地不動(dòng)馬爾可夫鏈如果Q位于1（或5），則下一時(shí)刻就以概率1移動(dòng)到2（或4）1和5這兩點(diǎn)被稱為反射壁該模型稱為帶有兩個(gè)反射壁的隨機(jī)游動(dòng)馬爾可夫鏈一步轉(zhuǎn)移矩陣為馬爾可夫鏈例某一機(jī)房的計(jì)算機(jī)經(jīng)常出現(xiàn)故障，研究者每15分鐘觀察一次運(yùn)行的狀態(tài)，收集了24小時(shí)的數(shù)據(jù)（97次觀察），用1表示正常狀態(tài)，0表示故障狀態(tài)馬爾可夫鏈一步轉(zhuǎn)移概率可近似表示為馬爾可夫鏈已知計(jì)算機(jī)在某一時(shí)段（15分鐘）的狀態(tài)為0，問(wèn)此條件下從此時(shí)刻起計(jì)算機(jī)能連續(xù)正常工作3刻鐘的條件概率是多少？X0=0,由乘法公式、馬氏性和齊次性，得馬爾可夫鏈馬爾可夫鏈齊次馬氏鏈的有限維分布pj(0)＝P{X0=aj}，aj

I，j=1,2,…稱其為馬氏鏈的初始分布馬氏鏈在任一時(shí)刻n的一維分布pj(n)＝P{Xn

=aj}，aj

I，j=1,2,…，顯然馬爾可夫鏈馬爾可夫鏈一維分布用向量表示用矩陣乘法，則上式可以寫(xiě)成p(n)=p(0)P(n)馬爾可夫鏈齊次馬氏鏈多步轉(zhuǎn)移概率的確定切普曼-科爾莫戈羅夫方程（C-K方程）從s時(shí)刻狀態(tài)ai出發(fā)經(jīng)過(guò)時(shí)間段u+v轉(zhuǎn)移到狀態(tài)aj，可以分解成從ai出發(fā)，經(jīng)過(guò)時(shí)間段u轉(zhuǎn)移到中間狀態(tài)ak，再?gòu)腶k出發(fā)經(jīng)過(guò)時(shí)間段v轉(zhuǎn)移到狀態(tài)aj的和事件馬爾可夫鏈固定ak，有條件概率和乘法定理馬爾可夫鏈C-K方程寫(xiě)成矩陣形式P(u+v)=P(u)P(v)P(n)=PP(n-1)P(n)=Pn對(duì)于齊次馬氏鏈，n步轉(zhuǎn)移概率矩陣是一步轉(zhuǎn)移概率矩陣的n次方馬爾可夫鏈例（0－1傳輸）只傳輸0和1的串聯(lián)系統(tǒng)中，每一級(jí)的傳真率為p，誤碼率為q=1－p，設(shè)一個(gè)單位傳輸一級(jí)馬爾可夫鏈按題意，該過(guò)程是一個(gè)馬氏鏈，并為齊次的一步轉(zhuǎn)移概率和轉(zhuǎn)移矩陣為馬爾可夫鏈轉(zhuǎn)移矩陣為馬爾可夫鏈設(shè)p=0.9，求系統(tǒng)二級(jí)傳輸后的傳真率與三級(jí)后的誤碼率設(shè)初始分布p1(0)=α，p0(0)=1-α已知系統(tǒng)n級(jí)傳輸后輸出為1，問(wèn)原發(fā)字符也為1的概率是多少？馬爾可夫鏈求n步轉(zhuǎn)移概率P(n)=Pn一步轉(zhuǎn)移矩陣的相異的特征值λ1＝1，λ2=p-q馬爾可夫鏈特征矩陣為馬爾可夫鏈對(duì)應(yīng)的特征向量為馬爾可夫鏈特征矩陣馬爾可夫鏈n步轉(zhuǎn)移矩陣為馬爾可夫鏈二級(jí)傳真率和三級(jí)誤碼率P11(2)、P00(2)P10(3)、P01(3)馬爾可夫鏈根據(jù)Bayes公式馬爾可夫鏈齊次馬氏鏈的有限維分布pj(0)＝P{X0=aj}，aj

I，j=1,2,…稱其為馬氏鏈的初始分布馬氏鏈在任一時(shí)刻n的一維分布pj(n)＝P{Xn

=aj}，aj

I，j=1,2,…，顯然馬爾可夫鏈馬爾可夫鏈一維分布用向量表示用矩陣乘法，則上式可以寫(xiě)成p(n)=p(0)P(n)馬爾可夫鏈齊次馬氏鏈多步轉(zhuǎn)移概率的確定切普曼-科爾莫戈羅夫方程（C-K方程）從s時(shí)刻狀態(tài)ai出發(fā)經(jīng)過(guò)時(shí)間段u+v轉(zhuǎn)移到狀態(tài)aj，可以分解成從ai出發(fā)，經(jīng)過(guò)時(shí)間段u轉(zhuǎn)移到中間狀態(tài)ak，再?gòu)腶k出發(fā)經(jīng)過(guò)時(shí)間段v轉(zhuǎn)移到狀態(tài)aj的和事件馬爾可夫鏈固定ak，有條件概率和乘法定理馬爾可夫鏈C-K方程寫(xiě)成矩陣形式P(u+v)=P(u)P(v)P(n)=PP(n-1)P(n)=Pn對(duì)于齊次馬氏鏈，n步轉(zhuǎn)移概率矩陣是一步轉(zhuǎn)移概率矩陣的n次方馬爾可夫鏈例（0－1傳輸）只傳輸0和1的串聯(lián)系統(tǒng)中，每一級(jí)的傳真率為p，誤碼率為q=1－p，設(shè)一個(gè)單位傳輸一級(jí)馬爾可夫鏈按題意，該過(guò)程是一個(gè)馬氏鏈，并為齊次的一步轉(zhuǎn)移概率和轉(zhuǎn)移矩陣為馬爾可夫鏈轉(zhuǎn)移矩陣為馬爾可夫鏈設(shè)p=0.9，求系統(tǒng)二級(jí)傳輸后的傳真率與三級(jí)后的誤碼率設(shè)初始分布p1(0)=α，p0(0)=1-α已知系統(tǒng)n級(jí)傳輸后輸出為1，問(wèn)原發(fā)字符也為1的概率是多少？馬爾可夫鏈求n步轉(zhuǎn)移概率P(n)=Pn一步轉(zhuǎn)移矩陣的相異的特征值λ1＝1，λ2=p-q馬爾可夫鏈對(duì)角陣為馬爾可夫鏈對(duì)應(yīng)的特征向量為馬爾可夫鏈特征矩陣馬爾可夫鏈n步轉(zhuǎn)移矩陣為馬爾可夫鏈二級(jí)傳真率和三級(jí)誤碼率P11(2)、P00(2)P10(3)、P01(3)馬爾可夫鏈根據(jù)Bayes公式馬爾可夫鏈上面的例子可以把轉(zhuǎn)移矩陣表示為一個(gè)有向圖狀態(tài)作為圖中的節(jié)點(diǎn)直接轉(zhuǎn)移關(guān)系表示為一個(gè)有向弧弧上的權(quán)為轉(zhuǎn)移概率馬爾可夫鏈馬爾可夫鏈兩個(gè)狀態(tài)的馬爾可夫鏈一步轉(zhuǎn)移概率一般可以表示為參照上面的方法，可得n步轉(zhuǎn)移矩陣馬爾可夫鏈馬爾可夫鏈遍歷性由前面的公式，可知馬爾可夫鏈Pij(n)極限的含義對(duì)固定的狀態(tài)j，不管鏈在某一時(shí)刻從什么狀態(tài)（i=0或1）通過(guò)長(zhǎng)時(shí)間的轉(zhuǎn)移，到達(dá)狀態(tài)j的概率都趨近于πj如果能用其它簡(jiǎn)便的方法由一步轉(zhuǎn)移概率求得極限概率πj，就可得到n步轉(zhuǎn)移概率的近似值Pij(n)≈πj馬爾可夫鏈設(shè)齊次馬氏鏈的狀態(tài)空間為I，若對(duì)所有ai，aj

I，轉(zhuǎn)移概率Pij(n)存在極限馬爾可夫鏈則稱此鏈具有遍歷性如果則同時(shí)稱鏈的極限分布馬爾可夫鏈有限齊次馬爾可夫鏈的遍歷性的一個(gè)充分條件設(shè)齊次馬氏鏈｛Xn＝X(n)，n＝0，1，2，…｝的狀態(tài)空間為I＝｛a1，a2，…，aN｝，P是它的一步轉(zhuǎn)移矩陣，如果存在正整數(shù)m，使對(duì)任意的ai，aj

∈I

，都有則此鏈具有遍歷性馬爾可夫鏈且具有極限分布是方程組馬爾可夫鏈滿足條件的唯一解前面的方程只有N-1個(gè)變量是獨(dú)立的而唯一解可利用上面的歸一條件來(lái)確定馬爾可夫鏈馬氏鏈的極限分布又是平穩(wěn)分布以π作為鏈的初始分布鏈在任一時(shí)刻n的分布p(n)永遠(yuǎn)與π是一致的馬爾可夫鏈例設(shè)一醉漢Q如圖在直線的點(diǎn)集I＝｛1，2，3，4，5｝作隨機(jī)游動(dòng)馬爾可夫鏈一步轉(zhuǎn)移矩陣為馬爾可夫鏈說(shuō)明該隨機(jī)游動(dòng)是遍歷的，并求其極限分布馬爾可夫鏈按照有限鏈的遍歷性條件該隨機(jī)游動(dòng)是遍歷的馬爾可夫鏈極限分布π=(π1，π2，…，π5)滿足方程馬爾可夫鏈求得極限分布為例排隊(duì)模型服務(wù)系統(tǒng)由一個(gè)服務(wù)員和只容納兩個(gè)人的等候室組成服務(wù)規(guī)則：先到先服務(wù)，后來(lái)者在等候室依次等候服務(wù)馬爾可夫鏈如果需要服務(wù)的顧客發(fā)現(xiàn)系統(tǒng)中已經(jīng)有3個(gè)顧客，則離去設(shè)時(shí)間間隔Δt內(nèi)有一個(gè)顧客進(jìn)入系統(tǒng)的概率為q，離開(kāi)系統(tǒng)的概率pΔt充分小，在這段時(shí)間內(nèi)多于一個(gè)顧客進(jìn)入系統(tǒng)或離開(kāi)系統(tǒng)是不可能的馬爾可夫鏈如果p=q=1/2，試說(shuō)明系統(tǒng)經(jīng)過(guò)長(zhǎng)時(shí)間運(yùn)行后，系統(tǒng)中沒(méi)有人、1個(gè)人、2個(gè)人、3個(gè)人的情況設(shè)Xn=X(nΔt)表示時(shí)刻nΔt系統(tǒng)內(nèi)的顧客數(shù)，既系統(tǒng)的狀態(tài){Xn，n=0,1,2,3,…}是一個(gè)隨機(jī)過(guò)程狀態(tài)空間I={0,1,2,3}是一個(gè)齊次馬爾可夫鏈馬爾可夫鏈求該馬氏鏈的一步轉(zhuǎn)移概率p00，系統(tǒng)沒(méi)有顧客的條件下，經(jīng)過(guò)Δt仍然沒(méi)有顧客p00=1-qp01，系統(tǒng)沒(méi)有顧客的條件下，經(jīng)過(guò)Δt有一個(gè)顧客進(jìn)入系統(tǒng)p01=qp10，系統(tǒng)有1個(gè)顧客的條件下，經(jīng)過(guò)Δt有系統(tǒng)無(wú)人的概率p10=p(1-q)馬爾可夫鏈p11，系統(tǒng)有1個(gè)顧客的條件下，經(jīng)過(guò)Δt后服務(wù)完畢離去并有1人進(jìn)入，或繼續(xù)服務(wù)而無(wú)人進(jìn)入系統(tǒng)p11=pq+(1-p)(1-q)p12，系統(tǒng)有1個(gè)顧客的條件下，經(jīng)過(guò)Δt后有兩個(gè)人p12=(1-p)qp13，系統(tǒng)中一人服務(wù)，兩人進(jìn)入p13=0馬爾可夫鏈類似地，有p21=p32=p(1-q)p22=pq+(1-p)(1-q)p23=q(1-p)p33，一人因服務(wù)完畢離開(kāi)且另一人進(jìn)入系統(tǒng)，或者無(wú)人進(jìn)入系統(tǒng)p23=pq+(

(1-p)其它情況的轉(zhuǎn)移概率為0馬爾可夫鏈馬氏鏈的一步轉(zhuǎn)移概率為馬爾可夫鏈該馬爾可夫鏈?zhǔn)潜闅v的P3無(wú)零元根據(jù)前面條件求得極限分布馬爾可夫鏈如果p=q=1/2，可求得系統(tǒng)中無(wú)人的情況占14%，一人、二人、三人的情況各占約29%馬爾可夫鏈狀態(tài)的分類例設(shè)系統(tǒng)有三個(gè)狀態(tài)I={0,1,2,3}?！?”代表系統(tǒng)運(yùn)行良好，“2”代表系統(tǒng)正常運(yùn)行，“3”表示系統(tǒng)失效以Xn表示系統(tǒng)在時(shí)刻n的狀態(tài)，可知{Xn

，n

≥0}是一個(gè)馬氏鏈在沒(méi)有維修及更換條件下，其自然轉(zhuǎn)移概率為：馬爾可夫鏈可以看出，從狀態(tài)“1”或“2”出發(fā)經(jīng)過(guò)有限次轉(zhuǎn)移后總要到達(dá)“3”狀態(tài)一旦到達(dá)“3”狀態(tài)則永遠(yuǎn)停在“3”狀態(tài)“1”狀態(tài)“2”狀態(tài)和“3”狀態(tài)的概率性質(zhì)不同馬爾可夫鏈如果Pii=1，則稱狀態(tài)i為吸收態(tài)如果對(duì)i,j∈I，如果Pij(n)>0，稱自狀態(tài)i出發(fā)可達(dá)狀態(tài)j，記作i→j。如果i→j且j→i則稱狀態(tài)i,j相通如果馬氏鏈的任意兩個(gè)狀態(tài)相通，則稱該鏈為不可約鏈馬爾可夫鏈狀態(tài)的分類例設(shè)系統(tǒng)有三個(gè)狀態(tài)I={1,2,3}?！?”代表系統(tǒng)運(yùn)行良好，“2”代表系統(tǒng)正常運(yùn)行，“3”表示系統(tǒng)失效以Xn表示系統(tǒng)在時(shí)刻n的狀態(tài)，可知{Xn

，n

≥0}是一個(gè)馬氏鏈在沒(méi)有維修及更換條件下，其自然轉(zhuǎn)移概率為：馬爾可夫鏈可以看出，從狀態(tài)“1”或“2”出發(fā)經(jīng)過(guò)有限次轉(zhuǎn)移后總要到達(dá)“3”狀態(tài)一旦到達(dá)“3”狀態(tài)則永遠(yuǎn)停在“3”狀態(tài)“1”狀態(tài)“2”狀態(tài)和“3”狀態(tài)的概率性質(zhì)不同馬爾可夫鏈如果Pii=1，則稱狀態(tài)i為吸收態(tài)如果對(duì)i,j∈I，如果Pij(n)>0，稱自狀態(tài)i出發(fā)可達(dá)狀態(tài)j，記作i→j。如果i→j且j→i則稱狀態(tài)i,j相通如果馬氏鏈的任意兩個(gè)狀態(tài)相通，則稱該鏈為不可約鏈馬爾可夫鏈?zhǔn)椎竭_(dá)時(shí)間Tij=min{n：n≥1,Xn=j,X0=i}若等式右邊為空集，令Tij=∞Tij表示從i出發(fā)首次到達(dá)j的時(shí)間Tii表示從i出發(fā)首次回到i的時(shí)間馬爾可夫鏈?zhǔn)椎竭_(dá)概率表示從i出發(fā)經(jīng)n步首次到達(dá)j的概率表示從i出發(fā)經(jīng)有限步終于到達(dá)j的概率馬爾可夫鏈如果fii=1稱狀態(tài)i為常返態(tài)；如果fii<1稱狀態(tài)i為非常返態(tài)如果fii=1，記表示從狀態(tài)i出發(fā)再回到狀態(tài)i的平均會(huì)轉(zhuǎn)時(shí)間如果μi<∞,稱狀態(tài)i為正常返態(tài)；如果μi=∞，稱狀態(tài)i為零常返態(tài)馬爾可夫鏈如果集合{n：n≥1，Pii(n)>0}非空，稱該集合的最大公約數(shù)為狀態(tài)i的周期如果最大公約數(shù)大于1，稱i為周期的如果最大公約數(shù)為1，稱i為非周期的如果i為正常返的且非周期的，則稱狀態(tài)i為遍歷狀態(tài)馬爾可夫鏈設(shè)馬氏鏈的I={1，2，3，4}，轉(zhuǎn)移矩陣為馬爾可夫鏈狀態(tài)轉(zhuǎn)移圖為馬爾可夫鏈馬爾可夫鏈μ1<∞、μ2<∞非周期非周期正常返，遍歷狀態(tài)馬爾可夫鏈Pij(n)和fij(n)的關(guān)系馬爾可夫鏈馬爾可夫鏈生滅過(guò)程離散時(shí)間生滅過(guò)程（birth-deathprocess）所有的轉(zhuǎn)移只發(fā)生在相鄰的狀態(tài)之間轉(zhuǎn)移概率矩陣是一個(gè)夾層狀矩陣，其中生滅過(guò)程為了簡(jiǎn)化，定義如下符號(hào)生滅過(guò)程生滅過(guò)程穩(wěn)態(tài)分布生滅過(guò)程生滅過(guò)程排隊(duì)論基礎(chǔ)從排隊(duì)現(xiàn)象得到抽象的物理模型，進(jìn)一步建立數(shù)學(xué)模型的一整套理論研究的是一個(gè)系統(tǒng)對(duì)一個(gè)群體提供某種服務(wù)時(shí)，系統(tǒng)所呈現(xiàn)的狀態(tài)排隊(duì)論是計(jì)算機(jī)通信網(wǎng)絡(luò)和計(jì)算機(jī)系統(tǒng)中通信信息量研究的基礎(chǔ)理論信息系統(tǒng)通信問(wèn)題的定量研究往往要借助排隊(duì)論才能得到解決排隊(duì)論基礎(chǔ)例一個(gè)項(xiàng)目組有10個(gè)成員，每人有一臺(tái)PC，通過(guò)LAN連接到一個(gè)圖形工作站在一天8小時(shí)里，10個(gè)人都將使用工作站，而且某一時(shí)刻只能是一個(gè)人使用每人每次使用的平均花費(fèi)是30分鐘是否還需要再購(gòu)置工作站？如果需要，還須購(gòu)買(mǎi)幾臺(tái)？排隊(duì)論基礎(chǔ)兩個(gè)重要的分布幾何分布指數(shù)分布排隊(duì)論基礎(chǔ)幾何分布隨機(jī)變量X的分布律為K=1,2,3…排隊(duì)論基礎(chǔ)幾何分布無(wú)記憶性排隊(duì)論基礎(chǔ)設(shè)X1，X2，…，Xr為r個(gè)獨(dú)立同分布隨機(jī)變量，X1服從參數(shù)為p的幾何分布，那么排隊(duì)論基礎(chǔ)當(dāng)r=2時(shí)排隊(duì)論基礎(chǔ)假設(shè)當(dāng)r=n時(shí)成立，那么當(dāng)r=n+1時(shí)排隊(duì)論基礎(chǔ)因?yàn)榕抨?duì)論基礎(chǔ)指數(shù)分布指數(shù)分布無(wú)記憶性可以記為設(shè)設(shè)X1，X2，…，Xr為r個(gè)獨(dú)立同分布隨機(jī)變量，X1服從排隊(duì)論基礎(chǔ)排隊(duì)論基礎(chǔ)當(dāng)n=2時(shí)排隊(duì)論基礎(chǔ)設(shè)當(dāng)n=k時(shí)成立，當(dāng)n=k＋1時(shí)排隊(duì)論基礎(chǔ)排隊(duì)論基礎(chǔ)設(shè)Xi～Γ（1,λi）且各隨機(jī)變量相互獨(dú)立，那么設(shè)Xi～Geo(pi)且各隨機(jī)變量相互獨(dú)立，那么排隊(duì)論基礎(chǔ)設(shè)排隊(duì)論基礎(chǔ)排隊(duì)論基礎(chǔ)幾何分布，因?yàn)榕抨?duì)論基礎(chǔ)排隊(duì)系統(tǒng)的組成和數(shù)字特征排隊(duì)論基礎(chǔ)顧客到達(dá)通常是一個(gè)一個(gè)到達(dá)，也可能是成批的到達(dá)過(guò)程或到達(dá)時(shí)間間隔符合一定的分布－到達(dá)分布顧客的到達(dá)或到達(dá)時(shí)的間間隔通常假定為相互獨(dú)立并服從同一分布的隨機(jī)變量輸入過(guò)程通常假定為時(shí)齊的排隊(duì)論基礎(chǔ)在隊(duì)列排隊(duì)隊(duì)列的大小有限的隊(duì)列無(wú)限隊(duì)列排隊(duì)的方式如何通常和服務(wù)協(xié)議相對(duì)應(yīng)有什么樣的服務(wù)協(xié)議就有什么樣的與之對(duì)應(yīng)的排隊(duì)方式排隊(duì)論基礎(chǔ)服務(wù)規(guī)律服務(wù)員對(duì)顧客采用什么樣的方式服務(wù)一般是一個(gè)對(duì)一個(gè)進(jìn)行服務(wù)服務(wù)時(shí)間可看作隨機(jī)變量相互獨(dú)立，服從同一分布排隊(duì)論基礎(chǔ)服務(wù)協(xié)議先來(lái)先服務(wù)（FCFS）后來(lái)先服務(wù)（LCFS）非搶占搶占后接續(xù)搶占后重開(kāi)始隨機(jī)選擇服務(wù)（RSS）排隊(duì)論基礎(chǔ)服務(wù)協(xié)議優(yōu)先服務(wù)和動(dòng)態(tài)優(yōu)先服務(wù)排隊(duì)優(yōu)先權(quán)中斷優(yōu)先權(quán)搶占后接續(xù)搶占后重開(kāi)始動(dòng)態(tài)優(yōu)先權(quán)排隊(duì)論基礎(chǔ)服務(wù)協(xié)議處理器共享（processorsharing，PS）無(wú)限服務(wù)員（infiniteserver，IS）排隊(duì)論基礎(chǔ)服務(wù)員的數(shù)量和質(zhì)量單服務(wù)員多服務(wù)員無(wú)限多服務(wù)員前兩種需要排隊(duì)排隊(duì)論基礎(chǔ)經(jīng)典排隊(duì)模型排隊(duì)模型的通用格式是1953年肯德?tīng)柼岢龅摹翱系聽(tīng)柲Ｐ汀备袷綖锳/B/n/S/ZA：表示顧客到達(dá)的規(guī)律B：服務(wù)時(shí)間分布n：服務(wù)員的數(shù)目S：隊(duì)列容量的大小Z：服務(wù)規(guī)程排隊(duì)論基礎(chǔ)當(dāng)隊(duì)列的大小為無(wú)窮大，服務(wù)規(guī)程為先來(lái)先服務(wù)時(shí)經(jīng)典排隊(duì)模型可以簡(jiǎn)化為A/B/n排隊(duì)論基礎(chǔ)對(duì)不同類型的排隊(duì)，A、B可用以下約定的字母表示M：用來(lái)描述到達(dá)，表示泊松到達(dá)，到達(dá)時(shí)間間隔符合指數(shù)分布如果用于描述服務(wù)，指具有指數(shù)分布的服務(wù)時(shí)間指數(shù)分布具有馬爾可夫特性，所以用Markov的第一個(gè)字母M表示排隊(duì)論基礎(chǔ)A、B可用以下約定的字母表示D：確定性分布，表示到達(dá)間隔時(shí)間或服務(wù)時(shí)間是固定的常數(shù)（Deterministic）G：一般分布，表示到達(dá)間隔或服務(wù)時(shí)間服從一般分布Ek：k-愛(ài)爾朗分布，表示到達(dá)間隔或服務(wù)時(shí)間服從k-愛(ài)爾朗分布H：超幾何分布L：二項(xiàng)式分布排隊(duì)論基礎(chǔ)Z代表的服務(wù)規(guī)程典型的有FCFS：先來(lái)先服務(wù)LCFS：后來(lái)先服務(wù)RSS：隨機(jī)選擇服務(wù)PR：優(yōu)先權(quán)服務(wù)Ba：集體（批量服務(wù)）排隊(duì)論基礎(chǔ)排隊(duì)系統(tǒng)的主要技術(shù)指標(biāo)隊(duì)長(zhǎng)系統(tǒng)中的顧客數(shù)正在接受服務(wù)的顧客和等待服務(wù)的顧客之和等待時(shí)間從顧客到達(dá)時(shí)起一直到他被接受服務(wù)時(shí)止的這段時(shí)間從顧客到達(dá)系統(tǒng)到服務(wù)后離開(kāi)系統(tǒng)的這段時(shí)間成為逗留時(shí)間，等待時(shí)間和服務(wù)時(shí)間之和排隊(duì)論基礎(chǔ)忙期指空閑的服務(wù)機(jī)構(gòu)從有顧客到達(dá)時(shí)起一直到服務(wù)機(jī)構(gòu)又沒(méi)有顧客的這段時(shí)間閑期，服務(wù)機(jī)構(gòu)沒(méi)有顧客到有顧客時(shí)的這段時(shí)間排隊(duì)論基礎(chǔ)設(shè)Xi～Γ（1,λi）且各隨機(jī)變量相互獨(dú)立，那么設(shè)Xi～Geo(pi)且各隨機(jī)變量相互獨(dú)立，那么排隊(duì)論基礎(chǔ)設(shè)排隊(duì)論基礎(chǔ)排隊(duì)論基礎(chǔ)幾何分布，因?yàn)榕抨?duì)論基礎(chǔ)排隊(duì)系統(tǒng)的組成和數(shù)字特征排隊(duì)論基礎(chǔ)顧客到達(dá)通常是一個(gè)一個(gè)到達(dá)，也可能是成批的到達(dá)過(guò)程或到達(dá)時(shí)間間隔符合一定的分布－到達(dá)分布顧客的到達(dá)或到達(dá)時(shí)的間間隔通常假定為相互獨(dú)立并服從同一分布的隨機(jī)變量輸入過(guò)程通常假定為時(shí)齊的排隊(duì)論基礎(chǔ)在隊(duì)列排隊(duì)隊(duì)列的大小有限的隊(duì)列無(wú)限隊(duì)列排隊(duì)的方式如何通常和服務(wù)協(xié)議相對(duì)應(yīng)有什么樣的服務(wù)協(xié)議就有什么樣的與之對(duì)應(yīng)的排隊(duì)方式排隊(duì)論基礎(chǔ)服務(wù)規(guī)律服務(wù)員對(duì)顧客采用什么樣的方式服務(wù)一般是一個(gè)對(duì)一個(gè)進(jìn)行服務(wù)服務(wù)時(shí)間可看作隨機(jī)變量相互獨(dú)立，服從同一分布排隊(duì)論基礎(chǔ)服務(wù)協(xié)議先來(lái)先服務(wù)（FCFS）后來(lái)先服務(wù)（LCFS）非搶占搶占后接續(xù)搶占后重開(kāi)始隨機(jī)選擇服務(wù)（RSS）排隊(duì)論基礎(chǔ)服務(wù)協(xié)議優(yōu)先服務(wù)和動(dòng)態(tài)優(yōu)先服務(wù)排隊(duì)優(yōu)先權(quán)中斷優(yōu)先權(quán)搶占后接續(xù)搶占后重開(kāi)始動(dòng)態(tài)優(yōu)先權(quán)排隊(duì)論基礎(chǔ)服務(wù)協(xié)議處理器共享（processorsharing，PS）無(wú)限服務(wù)員（infiniteserver，IS）排隊(duì)論基礎(chǔ)服務(wù)員的數(shù)量和質(zhì)量單服務(wù)員多服務(wù)員無(wú)限多服務(wù)員前兩種需要排隊(duì)排隊(duì)論基礎(chǔ)經(jīng)典排隊(duì)模型排隊(duì)模型的通用格式是1953年肯德?tīng)柼岢龅摹翱系聽(tīng)柲Ｐ汀备袷綖锳/B/n/S/ZA：表示顧客到達(dá)的規(guī)律B：服務(wù)時(shí)間分布n：服務(wù)員的數(shù)目S：隊(duì)列容量的大小Z：服務(wù)規(guī)程排隊(duì)論基礎(chǔ)當(dāng)隊(duì)列的大小為無(wú)窮大，服務(wù)規(guī)程為先來(lái)先服務(wù)時(shí)經(jīng)典排隊(duì)模型可以簡(jiǎn)化為A/B/n排隊(duì)論基礎(chǔ)對(duì)不同類型的排隊(duì)，A、B可用以下約定的字母表示M：用來(lái)描述到達(dá)，表示泊松到達(dá)，到達(dá)時(shí)間間隔符合指數(shù)分布如果用于描述服務(wù)，指具有指數(shù)分布的服務(wù)時(shí)間指數(shù)分布具有馬爾可夫特性，所以用Markov的第一個(gè)字母M表示排隊(duì)論基礎(chǔ)A、B可用以下約定的字母表示D：確定性分布，表示到達(dá)間隔時(shí)間或服務(wù)時(shí)間是固定的常數(shù)（Deterministic）G：一般分布，表示到達(dá)間隔或服務(wù)時(shí)間服從一般分布Ek：k-愛(ài)爾朗分布，表示到達(dá)間隔或服務(wù)時(shí)間服從k-愛(ài)爾朗分布H：超幾何分布L：二項(xiàng)式分布排隊(duì)論基礎(chǔ)Z代表的服務(wù)規(guī)程典型的有FCFS：先來(lái)先服務(wù)LCFS：后來(lái)先服務(wù)RSS：隨機(jī)選擇服務(wù)PR：優(yōu)先權(quán)服務(wù)Ba：集體（批量服務(wù)）排隊(duì)論基礎(chǔ)排隊(duì)系統(tǒng)的主要技術(shù)指標(biāo)隊(duì)長(zhǎng)系統(tǒng)中的顧客數(shù)正在接受服務(wù)的顧客和等待服務(wù)的顧客之和等待時(shí)間從顧客到達(dá)時(shí)起一直到他被接受服務(wù)時(shí)止的這段時(shí)間從顧客到達(dá)系統(tǒng)到服務(wù)后離開(kāi)系統(tǒng)的這段時(shí)間成為逗留時(shí)間，等待時(shí)間和服務(wù)時(shí)間之和排隊(duì)論基礎(chǔ)忙期指空閑的服務(wù)機(jī)構(gòu)從有顧客到達(dá)時(shí)起一直到服務(wù)機(jī)構(gòu)又沒(méi)有顧客的這段時(shí)間閑期，服務(wù)機(jī)構(gòu)沒(méi)有顧客到有顧客時(shí)的這段時(shí)間排隊(duì)論基礎(chǔ)M/M/n系統(tǒng)系統(tǒng)的輸入過(guò)程{N(t),t≥0}為參數(shù)是λ的泊松過(guò)程服務(wù)機(jī)構(gòu)有n個(gè)（n≥1）服務(wù)臺(tái)每個(gè)服務(wù)臺(tái)獨(dú)立工作，且具有相同分布的服務(wù)時(shí)間B，B~Γ(1，μ)排隊(duì)論基礎(chǔ)設(shè)X(t)表示時(shí)間t系統(tǒng)中的顧客數(shù)（包括正在接受服務(wù)的顧客數(shù)）{X(t)，

t≥0}是一個(gè)隨機(jī)過(guò)程設(shè){t<Xk<t+Δt}表示服務(wù)機(jī)構(gòu)有k個(gè)服務(wù)臺(tái)在時(shí)間間隔(t,t+Δt)中結(jié)束服務(wù)排隊(duì)論基礎(chǔ)一個(gè)服務(wù)臺(tái)在時(shí)刻t正在服務(wù)，經(jīng)過(guò)Δt后，沒(méi)有結(jié)束服務(wù)的概率排隊(duì)論基礎(chǔ)該服務(wù)臺(tái)結(jié)束服務(wù)的概率為排隊(duì)論基礎(chǔ)因?yàn)閧N(t+Δt)-N(t)=n}與{X(t)=i}相互獨(dú)立排隊(duì)論基礎(chǔ)排隊(duì)論基礎(chǔ)排隊(duì)論基礎(chǔ)排隊(duì)論基礎(chǔ)排隊(duì)論基礎(chǔ)排隊(duì)論基礎(chǔ)同理排隊(duì)論基礎(chǔ)排隊(duì)論基礎(chǔ)其中生滅過(guò)程排隊(duì)論基礎(chǔ)生滅過(guò)程排隊(duì)論基礎(chǔ)穩(wěn)定分布的解排隊(duì)論基礎(chǔ)排隊(duì)論的生滅率生率滅率排隊(duì)論基礎(chǔ)排隊(duì)論有穩(wěn)定解的條件排隊(duì)論基礎(chǔ)穩(wěn)定分布的解根據(jù)滅率的不同，所以穩(wěn)定分布的解為排隊(duì)論基礎(chǔ)化簡(jiǎn)，令排隊(duì)論基礎(chǔ)根據(jù)歸一化條件πk表示的是系統(tǒng)平衡之后系統(tǒng)中有k個(gè)顧客的概率該生滅過(guò)程存在平穩(wěn)分布的充分必要條件是ρ<1排隊(duì)論基礎(chǔ)由平穩(wěn)分布可以得到M/M/n系統(tǒng)所關(guān)心的數(shù)量指標(biāo)平均隊(duì)長(zhǎng)平均等待時(shí)間顧客到達(dá)服務(wù)機(jī)構(gòu)需要等待的概率等待時(shí)間的分布逗留時(shí)間分布排隊(duì)論基礎(chǔ)排隊(duì)論基礎(chǔ)由平穩(wěn)分布可以得到M/M/n系統(tǒng)所關(guān)心的數(shù)量指標(biāo)平均隊(duì)長(zhǎng)平均等待時(shí)間顧客到達(dá)服務(wù)機(jī)構(gòu)需要等待的概率等待時(shí)間的分布逗留時(shí)間分布排隊(duì)論基礎(chǔ)平均隊(duì)長(zhǎng)、平均等待隊(duì)長(zhǎng)系統(tǒng)穩(wěn)定狀態(tài)（穩(wěn)定分布）πk的含義系統(tǒng)中有k個(gè)人的概率平均隊(duì)長(zhǎng)為穩(wěn)定分布的？數(shù)學(xué)期望用X來(lái)表示系統(tǒng)在ρ<1下的隊(duì)長(zhǎng)，用Xq表示系統(tǒng)等待隊(duì)長(zhǎng)排隊(duì)論基礎(chǔ)由前面穩(wěn)定分布的穩(wěn)定概率公式，可以得到穩(wěn)定分布的數(shù)學(xué)期望排隊(duì)論基礎(chǔ)平均隊(duì)長(zhǎng)為系統(tǒng)中的總?cè)藬?shù)正在排隊(duì)的人數(shù)＋正在接受服務(wù)的人數(shù)如何求平均等待的隊(duì)長(zhǎng)？排隊(duì)論基礎(chǔ)系統(tǒng)中有k個(gè)人在等待相當(dāng)于系統(tǒng)中有n+k個(gè)人可以得到Xq的分布排隊(duì)論基礎(chǔ)通過(guò)Xq的分布可以求出平均等待的隊(duì)長(zhǎng)排隊(duì)論基礎(chǔ)平均占用服務(wù)臺(tái)數(shù)Kπ0～πn的分布均值，即排隊(duì)論基礎(chǔ)排隊(duì)論基礎(chǔ)排隊(duì)論基礎(chǔ)因?yàn)榕抨?duì)論基礎(chǔ)所以排隊(duì)論基礎(chǔ)顧客到達(dá)要等待的概率p顧客不需要等待的概率為排隊(duì)論基礎(chǔ)等待時(shí)間的分布W為在系統(tǒng)平穩(wěn)條件ρ<1下一個(gè)顧客的等待時(shí)間對(duì)于任意實(shí)數(shù)t>0，W的分布函數(shù)為排隊(duì)論基礎(chǔ)因?yàn)榈却龝r(shí)間大于0表明系統(tǒng)的顧客數(shù)大于等于n排隊(duì)論基礎(chǔ)系統(tǒng)服務(wù)員的服務(wù)時(shí)間服從Γ(1,μ)的分布系統(tǒng)中有n個(gè)服務(wù)員，則服務(wù)時(shí)間的分布為這n個(gè)獨(dú)立同指數(shù)分布的最小分布對(duì)等待時(shí)間來(lái)說(shuō)，系統(tǒng)的服務(wù)時(shí)間相當(dāng)于Γ(1,nμ)系統(tǒng)相當(dāng)于只有一個(gè)服務(wù)時(shí)服從Γ(1,nμ)的服務(wù)員系統(tǒng)中第n+1個(gè)顧客在服務(wù)完之后接受服務(wù)系統(tǒng)中第n+k+1個(gè)顧客必須在前k個(gè)顧客接受服務(wù)后才能接受服務(wù)k的獨(dú)立同分布的指數(shù)分布之和的分布排隊(duì)論基礎(chǔ)因?yàn)榕抨?duì)論基礎(chǔ)排隊(duì)論基礎(chǔ)因?yàn)榕抨?duì)論基礎(chǔ)因?yàn)榕抨?duì)論基礎(chǔ)等待時(shí)間W的概率密度函數(shù)為排隊(duì)論基礎(chǔ)平均等待時(shí)間為排隊(duì)論基礎(chǔ)排隊(duì)論基礎(chǔ)逗留時(shí)間T的分布因?yàn)榈却龝r(shí)間W和服務(wù)時(shí)間B相互獨(dú)立排隊(duì)論基礎(chǔ)T的分布為排隊(duì)論基礎(chǔ)分布函數(shù)為排隊(duì)論基礎(chǔ)概率密度函數(shù)為排隊(duì)論基礎(chǔ)M/M/n隊(duì)列模型總結(jié)生滅過(guò)程生率(顧客到達(dá)速率)λ滅率(服務(wù)速率)min(i,n)μ系統(tǒng)穩(wěn)定的條件為排隊(duì)論基礎(chǔ)系統(tǒng)平穩(wěn)分布的解為排隊(duì)論基礎(chǔ)關(guān)心的性能指標(biāo)平均隊(duì)長(zhǎng)平均等待時(shí)間資源利用率顧客到達(dá)服務(wù)機(jī)構(gòu)需要等待的概率等待時(shí)間的分布逗留時(shí)間分布排隊(duì)論基礎(chǔ)平均隊(duì)長(zhǎng)平均等待隊(duì)長(zhǎng)排隊(duì)論基礎(chǔ)平均占用服務(wù)器的臺(tái)數(shù)資源利用率顧客到達(dá)要等待的概率p排隊(duì)論基礎(chǔ)平均等待時(shí)間平均逗留時(shí)間(平均響應(yīng)時(shí)間)排隊(duì)論基礎(chǔ)M/M/n排隊(duì)模型比較重要的參數(shù)n、ρ、π0、πn對(duì)于單服務(wù)器的排隊(duì)模型M/M/1排隊(duì)論基礎(chǔ)M/M/1排隊(duì)模型平穩(wěn)分布的解有穩(wěn)定分布解的條件為排隊(duì)論基礎(chǔ)平均隊(duì)長(zhǎng)排隊(duì)論基礎(chǔ)平均等待隊(duì)長(zhǎng)平均占用服務(wù)的臺(tái)數(shù)（資源利用率）排隊(duì)論基礎(chǔ)等待時(shí)間的分布函數(shù)等待時(shí)間的概率密度函數(shù)排隊(duì)論基礎(chǔ)平均等待時(shí)間逗留時(shí)間的概率密度函數(shù)排隊(duì)論基礎(chǔ)M/M/1排隊(duì)模型的逗留時(shí)間服從平均逗留時(shí)間排隊(duì)論基礎(chǔ)M/M/*排隊(duì)模型的兩個(gè)重要指標(biāo)平均等待時(shí)間平均逗留時(shí)間在其他類型的排隊(duì)系統(tǒng)中是否也有這樣的性質(zhì)？與到達(dá)間隔、服務(wù)時(shí)間、排隊(duì)規(guī)則無(wú)關(guān)？排隊(duì)論基礎(chǔ)Little

公式E(W)與E(Xq)的關(guān)系E(T)與E(X)的關(guān)系排隊(duì)論基礎(chǔ)設(shè)α(t)為在(0,t]時(shí)間區(qū)間中進(jìn)入系統(tǒng)的顧客數(shù)在這段時(shí)間的進(jìn)入率為排隊(duì)論基礎(chǔ)設(shè)γ(t)為α(t)個(gè)顧客到時(shí)刻t為止在系統(tǒng)中花費(fèi)的總時(shí)間在這段時(shí)間里，每個(gè)顧客的平均逗留時(shí)間為排隊(duì)論基礎(chǔ)設(shè)這段時(shí)間的單位時(shí)間系統(tǒng)的顧客數(shù)那么在系統(tǒng)(0,t]時(shí)間區(qū)間內(nèi)顧客花費(fèi)的總時(shí)間即單位時(shí)間內(nèi)的顧客數(shù)等于花費(fèi)的總時(shí)間除上時(shí)間間隔排隊(duì)論基礎(chǔ)根據(jù)前面的結(jié)果即排隊(duì)論基礎(chǔ)這是系統(tǒng)在(0,t]時(shí)間區(qū)間的結(jié)果單位時(shí)間內(nèi)平均顧客數(shù)等于系統(tǒng)顧客平均逗留時(shí)間與系統(tǒng)進(jìn)入率之積系統(tǒng)平均逗留時(shí)間為單位時(shí)間平均顧客數(shù)除以進(jìn)入率，即排隊(duì)論基礎(chǔ)在系統(tǒng)平衡條件下，有如下極限存在在平衡條件下，系統(tǒng)的每個(gè)顧客平均的逗留時(shí)間為系統(tǒng)的平均隊(duì)長(zhǎng)除以顧客的平均進(jìn)入率，即排隊(duì)論基礎(chǔ)設(shè)γ*(t)為在(0,t]時(shí)間區(qū)間α(t)個(gè)顧客到時(shí)刻t為止等待時(shí)間之和平均每個(gè)顧客的等待時(shí)間為排隊(duì)論基礎(chǔ)設(shè)這段時(shí)間的單位時(shí)間系統(tǒng)的平均等待顧客數(shù)為那么即單位時(shí)間系統(tǒng)平均等待的顧客數(shù)為排隊(duì)論基礎(chǔ)在系統(tǒng)平衡條件下，有如下極限存在在平衡條件下，系統(tǒng)的每個(gè)顧客平均的等待時(shí)間為系統(tǒng)的平均等待隊(duì)長(zhǎng)除以顧客的平均進(jìn)入率，即排隊(duì)論基礎(chǔ)Little公式系統(tǒng)每個(gè)顧客平均逗留時(shí)間系統(tǒng)每個(gè)顧客平均等待時(shí)間與到達(dá)間隔時(shí)間分布、服務(wù)時(shí)間分布、排隊(duì)規(guī)則無(wú)關(guān)排隊(duì)論基礎(chǔ)系統(tǒng)平穩(wěn)分布的解為平均隊(duì)長(zhǎng)平均等待隊(duì)長(zhǎng)排隊(duì)論基礎(chǔ)排隊(duì)論基礎(chǔ)M/M/1排隊(duì)模型平穩(wěn)分布的解有穩(wěn)定分布解的條件為排隊(duì)論基礎(chǔ)平均隊(duì)長(zhǎng)排隊(duì)論基礎(chǔ)平均等待隊(duì)長(zhǎng)平均占用服務(wù)的臺(tái)數(shù)（資源利用率）排隊(duì)論基礎(chǔ)等待時(shí)間的分布函數(shù)等待時(shí)間的概率密度函數(shù)排隊(duì)論基礎(chǔ)平均等待時(shí)間逗留時(shí)間的概率密度函數(shù)排隊(duì)論基礎(chǔ)M/M/1排隊(duì)模型的逗留時(shí)間服從平均逗留時(shí)間排隊(duì)論基礎(chǔ)Little公式系統(tǒng)每個(gè)顧客平均逗留時(shí)間系統(tǒng)每個(gè)顧客平均等待時(shí)間與到達(dá)間隔時(shí)間分布、服務(wù)時(shí)間分布、排隊(duì)規(guī)則無(wú)關(guān)排隊(duì)論基礎(chǔ)mx(r)－百分位函數(shù)在r%的時(shí)間里(情況下)，x的值小于mx(r)對(duì)于M/M/1排隊(duì)模型或M/M/n排隊(duì)模型最關(guān)心的性能指標(biāo)為等待時(shí)間和顧客在系統(tǒng)中的花費(fèi)時(shí)間有時(shí)候平均時(shí)間不能很好地刻劃系統(tǒng)的特征而精確求解有比較困難用百分位函數(shù)可以近似的刻劃排隊(duì)論基礎(chǔ)M/M/1排隊(duì)模型的兩個(gè)百分位函數(shù)等待時(shí)間W逗留時(shí)間T百分之多少的時(shí)間某個(gè)值小于百分位函數(shù)百分之多少相當(dāng)于某個(gè)值小于百分位的概率可以從分布函數(shù)或概率密度函數(shù)得到排隊(duì)論基礎(chǔ)等待時(shí)間W的百分位函數(shù)W的分布函數(shù)和概率密度函數(shù)分別為排隊(duì)論基礎(chǔ)相當(dāng)于排隊(duì)論基礎(chǔ)逗留時(shí)間T的百分位函數(shù)T的概率密度函數(shù)為排隊(duì)論基礎(chǔ)相當(dāng)于排隊(duì)論基礎(chǔ)例假定要確定一個(gè)電話亭可以支持的最大呼叫速率假定一個(gè)電話亭通話的持續(xù)時(shí)間平均為3分鐘一個(gè)人等待電話平均最大可以忍耐3分鐘求可以支持的最大呼叫量排隊(duì)論基礎(chǔ)按照M/M/1排隊(duì)模型λ必須要小于1/3呼叫/分鐘線路才能穩(wěn)定平均等待的時(shí)間為3分鐘，即排隊(duì)論基礎(chǔ)將μ=1/3代入上式，得所以，呼叫速率排隊(duì)論基礎(chǔ)數(shù)據(jù)庫(kù)服務(wù)器的例子一個(gè)LAN有100個(gè)PC和一個(gè)服務(wù)器，服務(wù)器上有一個(gè)公用查詢數(shù)據(jù)庫(kù)服務(wù)器響應(yīng)一個(gè)查詢的平均時(shí)間為0.6秒，標(biāo)準(zhǔn)差估計(jì)等于均值在最忙的時(shí)間里，查詢速率達(dá)到每分鐘20次排隊(duì)論基礎(chǔ)問(wèn)題如果線路開(kāi)銷(xiāo)忽略不記，求系統(tǒng)的平均響應(yīng)時(shí)間如果可以接受的最大響應(yīng)時(shí)間為1.5秒，求最大值達(dá)到前，系統(tǒng)負(fù)載還可以增加多少如果利用率增長(zhǎng)20%，則響應(yīng)時(shí)間的增長(zhǎng)幅度是多少排隊(duì)論基礎(chǔ)由于服務(wù)時(shí)間的標(biāo)準(zhǔn)差估計(jì)等于均值服務(wù)時(shí)間為指數(shù)分布假定系統(tǒng)的模型為M/M/1排隊(duì)模型數(shù)據(jù)庫(kù)是系統(tǒng)中的服務(wù)員忽略LAN線路時(shí)延的影響，設(shè)備利用率如下排隊(duì)論基礎(chǔ)平均響應(yīng)時(shí)間每個(gè)顧客的平均逗留時(shí)間該結(jié)果是考慮了任務(wù)在系統(tǒng)中的排隊(duì)等待的因素而得出的排隊(duì)論基礎(chǔ)第二個(gè)問(wèn)題精確求解很困難不管負(fù)載多大，響應(yīng)時(shí)間超過(guò)1.5秒的概率都是非零的但可以利用百分位函數(shù)來(lái)回答類似于在90%的情況下響應(yīng)時(shí)間小于1.5秒的問(wèn)題排隊(duì)論基礎(chǔ)根據(jù)前面的公式排隊(duì)論基礎(chǔ)將1/μ=0.6代入上面的公式，可以得到利用率為要使響應(yīng)時(shí)間在90%的時(shí)間里都小于1.5秒，系統(tǒng)的利用率（負(fù)載）必須從20%降低到8％排隊(duì)論基礎(chǔ)當(dāng)系統(tǒng)的利用率提高了20%的情況下利用率增長(zhǎng)了100%的情況下系統(tǒng)的平均響應(yīng)時(shí)間響應(yīng)時(shí)間僅僅增長(zhǎng)了33%排隊(duì)論基礎(chǔ)例在設(shè)計(jì)多處理器系統(tǒng)時(shí),希望比較下面兩種方案μμ兩個(gè)分開(kāi)的泊松流μμ速度為λ合并的泊松流排隊(duì)論基礎(chǔ)首先確定判斷性能好壞要評(píng)價(jià)的性能指標(biāo)平均響應(yīng)時(shí)間(平均逗留時(shí)間)第一種方案對(duì)應(yīng)兩個(gè)獨(dú)立無(wú)關(guān)的M/M/1隊(duì)列服務(wù)員利用率排隊(duì)論基礎(chǔ)根據(jù)M/M/1隊(duì)列模型平均逗留時(shí)間服從平均逗留時(shí)間為排隊(duì)論基礎(chǔ)第二種方案對(duì)應(yīng)的是M/M/2隊(duì)列相當(dāng)于系統(tǒng)進(jìn)入速率為λ每個(gè)服務(wù)員的服務(wù)速率為μ其中排隊(duì)論基礎(chǔ)該M/M/2隊(duì)列穩(wěn)定分布的解為排隊(duì)論基礎(chǔ)該M/M/2隊(duì)列穩(wěn)定分布的解為排隊(duì)論基礎(chǔ)平均隊(duì)長(zhǎng)為排隊(duì)論基礎(chǔ)根據(jù)Little公式平均響應(yīng)時(shí)間為排隊(duì)論基礎(chǔ)根據(jù)前面的結(jié)果共享隊(duì)列的方案好于分開(kāi)隊(duì)列的方案該結(jié)論對(duì)N(N>2)個(gè)服務(wù)情形同樣適用排隊(duì)論基礎(chǔ)例仍然考慮用兩個(gè)完全一樣的處理器來(lái)設(shè)計(jì)多處理器操作系統(tǒng)的問(wèn)題有兩個(gè)獨(dú)立的顧客流，但平均到達(dá)的速率不同λ1=20個(gè)/秒，λ2=15個(gè)/秒處理器的處理能力為平均30個(gè)/秒排隊(duì)論基礎(chǔ)比較兩種方案的優(yōu)劣30303030201515201535排隊(duì)論基礎(chǔ)根據(jù)前面的結(jié)果排隊(duì)論基礎(chǔ)例信息從LAN上的計(jì)算機(jī)傳輸?shù)狡渌W(wǎng)絡(luò)，所有分組必須通過(guò)連接LAN和廣域網(wǎng)的路由器從LAN到路由器傳輸?shù)姆纸M到達(dá)的平均速率為每秒5個(gè)分組分組的平均長(zhǎng)度為144個(gè)字節(jié)，假定長(zhǎng)度服從指數(shù)分布從路由器到廣域網(wǎng)的線路速率是9600bps排隊(duì)論基礎(chǔ)問(wèn)題在路由器中分組逗留的平均時(shí)間是多少路由器中平均有多少個(gè)分組在90%的時(shí)間里，路由器中的平均分組數(shù)在95%的時(shí)間里，路由器中的平均分組數(shù)排隊(duì)論基礎(chǔ)數(shù)據(jù)到達(dá)的平均速度λ

=5分組/秒服務(wù)器處理的平均速度1/μ=(144×8)位/(9600位/秒)=0.12秒該服務(wù)模型為M/M/1排隊(duì)模型系統(tǒng)的利用率為排隊(duì)論基礎(chǔ)分組的逗留時(shí)間為路由器中平均的分組數(shù)排隊(duì)論基礎(chǔ)隊(duì)列長(zhǎng)度的百分位函數(shù)根據(jù)前面求百分位函數(shù)的思路排隊(duì)論基礎(chǔ)隊(duì)長(zhǎng)的百分位函數(shù)為分組數(shù)目是整數(shù)，所以還需對(duì)百分位函數(shù)進(jìn)行取整排隊(duì)論基礎(chǔ)根據(jù)隊(duì)長(zhǎng)的百分位函數(shù)計(jì)算若要設(shè)計(jì)一個(gè)滿足95%的時(shí)間里路由器的緩存都不溢出緩存的長(zhǎng)度是至少能存5個(gè)分組排隊(duì)論基礎(chǔ)一個(gè)公司，10個(gè)工程師每人都有一臺(tái)PC機(jī)，這些PC機(jī)通過(guò)LAN連接到一個(gè)圖形工作站進(jìn)行分析和設(shè)計(jì)工作在一天8小時(shí)里，10個(gè)工程師將使用工作站每次使用平均花費(fèi)時(shí)間為30分鐘試分析系統(tǒng)的性能并給出解決方案排隊(duì)論基礎(chǔ)該系統(tǒng)可以等效為一個(gè)M/M/1排隊(duì)模型系統(tǒng)的利用率為系統(tǒng)假設(shè)：無(wú)限顧客、隨機(jī)到達(dá)、指數(shù)服務(wù)時(shí)間排隊(duì)論基礎(chǔ)一個(gè)工程師平均等待時(shí)間為在90%的時(shí)間里，等待時(shí)間的百分位函數(shù)為排隊(duì)論基礎(chǔ)工程師到達(dá)的平均速率平均等待的工程師數(shù)目排隊(duì)論基礎(chǔ)通過(guò)分析表明工程師平均等待的時(shí)間接近1小時(shí)在10%的情況下，一個(gè)工程師的等待時(shí)間將超過(guò)2小時(shí)如果一個(gè)工程師在等待時(shí)間里不能做其它有用的工作，該公司等于每天損失多于1個(gè)工程師的工作量排隊(duì)論基礎(chǔ)改進(jìn)方案通過(guò)前面分析，單隊(duì)列多服務(wù)員的平均響應(yīng)時(shí)間要優(yōu)于多隊(duì)列單服務(wù)員如果1個(gè)工程師的平均等待時(shí)間不超過(guò)10分鐘在90%的時(shí)間里，等待時(shí)間不超過(guò)15分鐘需要再添加幾臺(tái)服務(wù)器排隊(duì)論基礎(chǔ)新增一臺(tái)服務(wù)器，單隊(duì)列多服務(wù)員模型M/M/2排隊(duì)模型每個(gè)工程師平均等待時(shí)間為排隊(duì)論基礎(chǔ)對(duì)于多服務(wù)員的排隊(duì)系統(tǒng)，百分位函數(shù)為對(duì)于M/M/2排隊(duì)模型，等待時(shí)間的百分位函數(shù)為排隊(duì)論基礎(chǔ)對(duì)于這種情形90%的時(shí)間內(nèi)，工程師的等待時(shí)間為平均在等待的工程師的數(shù)量排隊(duì)論基礎(chǔ)如果用兩臺(tái)服務(wù)器，組成兩個(gè)隊(duì)列假設(shè)到達(dá)的速率都相等到達(dá)速率為原來(lái)速率的一半平均等待時(shí)間90%的情況下的等待時(shí)間等待隊(duì)長(zhǎng)排隊(duì)論基礎(chǔ)雙隊(duì)列時(shí)，到達(dá)速度一個(gè)服務(wù)員的利用率為一個(gè)工程師的平均等待時(shí)間排隊(duì)論基礎(chǔ)在90%時(shí)間里的平均等待時(shí)間平均等待的隊(duì)長(zhǎng)排隊(duì)論基礎(chǔ)多服務(wù)員例子比較工作站數(shù)系統(tǒng)模型ρE(W)mW(90)1M/M/10.62550146.62M/M/20.31253.258.642M/M/10.312513.6449.724M/M/10.156255.5615.875M/M/10.1254.297.65排隊(duì)論基礎(chǔ)M/G/1排隊(duì)模型顧客到達(dá)間隔時(shí)間序列{Jn,n≥1}是相互獨(dú)立的隨機(jī)變量序列Jn～Γ(1,λ)，系統(tǒng)輸入過(guò)程{N(t),t

≥0}為強(qiáng)度為λ的泊松流各顧客的服務(wù)時(shí)間序列{Bn,n≥1}是相互獨(dú)立同分布的隨機(jī)變量序列E(Bn)=1/μ，D(Bn)=1/σ2服務(wù)時(shí)間的分布函數(shù)為B(t)排隊(duì)論基礎(chǔ)M/G/1排隊(duì)模型服務(wù)機(jī)構(gòu)只有一個(gè)服務(wù)臺(tái)服務(wù)規(guī)則為先來(lái)先服務(wù)(FCFS)等待機(jī)制{Jn,n≥1}與{Bn,n≥1}相互獨(dú)立排隊(duì)論基礎(chǔ)嵌入馬爾可夫鏈泊松過(guò)程的到達(dá)時(shí)間間隔具有指數(shù)分布如果服務(wù)時(shí)間也服從指數(shù)分布系統(tǒng)中的n時(shí)刻顧客數(shù)與時(shí)刻n-1以前的顧客數(shù)無(wú)關(guān)故系統(tǒng)狀態(tài)