排隊(duì)論教案范文

排隊(duì)論教案范文 排隊(duì)論排隊(duì)論是研究排隊(duì)系統(tǒng)（又稱隨機(jī)服務(wù)系統(tǒng)）的數(shù)學(xué)理論和方法，是運(yùn)籌學(xué)的一個(gè)重要分支。 有形排隊(duì)現(xiàn)象進(jìn)餐館就餐，到圖書(shū)館借書(shū)，車(chē)站等車(chē)，去醫(yī)院看病，售票處售票，到工具房領(lǐng)物品等現(xiàn)象。 無(wú)形排隊(duì)現(xiàn)象如幾個(gè)旅客同時(shí)打電話訂車(chē)票；如果有一人正在通話，其他人只得在各自的電話機(jī)前等待，他們分散在不同的地方，形成一個(gè)無(wú)形的隊(duì)列在等待通電話。 排隊(duì)的不一定是人，也可以是物。 如生產(chǎn)線上的原材料，半成品等待加工；因故障而停止運(yùn)行的機(jī)器設(shè)備在等待修理；碼頭上的船只等待裝貨或卸貨；要下降的飛機(jī)因跑道不空而在空中盤(pán)旋等。 當(dāng)然，進(jìn)行服務(wù)的也不一定是人，可以是跑道，自動(dòng)售貨機(jī)，公共汽車(chē)等。 為了一致，統(tǒng)一規(guī)定為顧客要求服務(wù)的對(duì)象。 服務(wù)員提供服務(wù)的服務(wù)者（也稱服務(wù)機(jī)構(gòu)）。 顧客、服務(wù)員的含義是廣義的。 排隊(duì)的類型（見(jiàn)ppt）排隊(duì)系統(tǒng)的描述排隊(duì)系統(tǒng)的描述實(shí)際中的排隊(duì)系統(tǒng)各不相同，但概括起來(lái)都由三個(gè)基本部分組成輸入過(guò)程，排隊(duì)及排隊(duì)規(guī)則和服務(wù)機(jī)構(gòu)。 （一）輸入過(guò)程描述顧客按照什么樣的規(guī)律到達(dá)系統(tǒng)，從三個(gè)方面描述一個(gè)輸入顧客總體（顧客源）數(shù)可能是有限，也可能是無(wú)限。 到達(dá)方式是單個(gè)到達(dá)還是成批到達(dá)。 庫(kù)存問(wèn)題中，若把進(jìn)來(lái)的貨看成顧客，則為成批到達(dá)的例子。 顧客（單個(gè)或成批）相繼到達(dá)的時(shí)間間隔分布這是刻劃輸入過(guò)程的最重要內(nèi)容。 令T0=0，T n表示第n顧客到達(dá)的時(shí)刻，則有T0?T1?T2?T u?記X n?T n?T n?1,n?1,2,?，則X n是第n顧客與第n-1顧客到達(dá)的時(shí)間間隔。 一般假定Xn是獨(dú)立同分布，并記分布函數(shù)為A(t)。 X n的分布A(t)常見(jiàn)的有定常分布（D）顧客相繼到達(dá)的時(shí)間間隔為確定的。 如產(chǎn)品通過(guò)傳送帶進(jìn)入包裝箱就是定常分布。 最簡(jiǎn)流（或稱Poisson)（M）顧客相繼到達(dá)的時(shí)間間隔Xn為獨(dú)立的，同為負(fù)指數(shù)分布，其密度函數(shù)為?e?t t?0a(t)?0t0（二）排隊(duì)及排隊(duì)規(guī)則 （1）排隊(duì)有限排隊(duì)排隊(duì)系統(tǒng)中顧客數(shù)是有限的。 無(wú)限排隊(duì)顧客數(shù)是無(wú)限，隊(duì)列可以排到無(wú)限長(zhǎng)（等待制排隊(duì)系統(tǒng)）。 有限排隊(duì)還可以分成損失制排隊(duì)系統(tǒng)排隊(duì)空間為零的系統(tǒng)，即不允許排隊(duì)。 （顧客到達(dá)時(shí)，服務(wù)臺(tái)占滿，顧客自動(dòng)離開(kāi)，不再回來(lái)）（電話系統(tǒng)）混合制排隊(duì)系統(tǒng)是等待制與損失制結(jié)合，即允許排隊(duì)，但不允許隊(duì)列無(wú)限長(zhǎng)。 B排隊(duì)規(guī)則當(dāng)顧客到達(dá)時(shí)，若所有服務(wù)臺(tái)都被占有且又允許排隊(duì)，則該顧客將進(jìn)入隊(duì)列等待。 服務(wù)臺(tái)對(duì)顧客進(jìn)行服務(wù)所遵循的規(guī)則通常有先來(lái)先服務(wù)（FCFS）后來(lái)先服務(wù)（LCFS）。 在許多庫(kù)存系統(tǒng)中就會(huì)出現(xiàn)這種情況，如鋼板存入倉(cāng)庫(kù)后，需要時(shí)總是從最上面取出；又如在情報(bào)系統(tǒng)中，后來(lái)到達(dá)的信息往往更重要，首先要加以分析和利用。 具有優(yōu)先權(quán)的服務(wù)（PS）。 服務(wù)臺(tái)根據(jù)顧客的優(yōu)先權(quán)的不同進(jìn)行服務(wù)。 如病危的病人應(yīng)優(yōu)先治療；重要的信息應(yīng)優(yōu)先處理；出價(jià)高的顧客應(yīng)優(yōu)先考慮。 （2）服務(wù)機(jī)制包括服務(wù)員的數(shù)量及其連接方式（串聯(lián)還是并聯(lián)）；顧客是單個(gè)還是成批接受服務(wù)；服務(wù)時(shí)間的分布。 記某服務(wù)臺(tái)的服務(wù)時(shí)間為V，其分布函數(shù)為B(t),密度函數(shù)為b(t),則常見(jiàn)的分布有i.ii.定長(zhǎng)分布（D）每個(gè)顧客接受的服務(wù)時(shí)間是一個(gè)確定的常數(shù)。 負(fù)指數(shù)分布（M）每個(gè)顧客接受的服務(wù)時(shí)間相互獨(dú)立，具有相同的負(fù)指數(shù)分布i.iii.?e?t t?0b(t)?,?為常數(shù)?0t0K階愛(ài)爾朗分布（En）k?(k?t)k?1?k?tb(t)?e(k?1)!當(dāng)k=1時(shí)即為負(fù)指數(shù)分布；k?30,近似于正態(tài)分布。 當(dāng)k?時(shí)，方差?0即為完全非隨機(jī)的。 （三）排隊(duì)系統(tǒng)的符號(hào)表示D.G.Kendall在1953年提出了一份分類方法，按照最主要的影響最大的特征表示為“Kendall”記號(hào)X/Y/Z其中X表示顧客相繼到達(dá)的時(shí)間間隔分布；Y表示服務(wù)時(shí)間的分布；Z表示服務(wù)臺(tái)個(gè)數(shù)；表示相繼到達(dá)間隔時(shí)間和服務(wù)時(shí)間的各種分布的符號(hào)M負(fù)指數(shù)分布，（M是Markov的字頭，因?yàn)樨?fù)指數(shù)分布具有無(wú)記憶性，即Markov性）D確定型（Deterministic）E rk階愛(ài)爾朗分布（Erlang）GI一般相互獨(dú)立（General Independent）的時(shí)間間隔分布G一般（General）服務(wù)時(shí)間分布在1971年將其擴(kuò)充為X/Y/Z/A/B/C前三項(xiàng)意義不變，而A填寫(xiě)系統(tǒng)容量限制B填寫(xiě)顧客源書(shū)目C填寫(xiě)服務(wù)規(guī)則（先到先服務(wù)FCFS，后到先服務(wù)LCFS等）如果略去后三項(xiàng)，則代表X/Y/Z/?/?/FCFS排隊(duì)系統(tǒng)的主要數(shù)量指標(biāo)隊(duì)長(zhǎng)記為L(zhǎng) s，指排隊(duì)系統(tǒng)中的顧客數(shù)（排隊(duì)等待的顧客數(shù)與正在接受服務(wù)的顧客數(shù)之和）。 排隊(duì)長(zhǎng)又稱為隊(duì)列長(zhǎng)，記為L(zhǎng) q，系統(tǒng)中正在排隊(duì)等待服務(wù)的顧客數(shù)。 逗留時(shí)間指一個(gè)顧客在系統(tǒng)中的停留時(shí)間，其期望值為記作W s等待時(shí)間指一個(gè)顧客在系統(tǒng)中排隊(duì)等待的時(shí)間，其期望值記為W q系統(tǒng)狀態(tài)系統(tǒng)中的顧客數(shù)。 如果系統(tǒng)中有n個(gè)顧客就說(shuō)明系統(tǒng)的狀態(tài)是n，其可能值為隊(duì)長(zhǎng)沒(méi)有限制時(shí)，n?0,1,2,?,N隊(duì)長(zhǎng)有限制，最大數(shù)為N時(shí)，n?0,1,2,?,c即時(shí)制服務(wù)臺(tái)個(gè)數(shù)是c時(shí)，n?0,1,2,到達(dá)間隔分布和服務(wù)時(shí)間分布泊松流（普阿松流）設(shè)N(t)表示在時(shí)間區(qū)間0,t)內(nèi)到達(dá)的顧客數(shù)令Pn(t1,t2)表示在時(shí)間區(qū)間t1,t2)(t1?t2),內(nèi)有n(n?0)個(gè)顧客到達(dá)的概率，即P n(t1,t2)?PN(t2)?N(t1)?n(t2?t1,n?0)當(dāng)Pn(t1,t2)滿足下列三個(gè)條件時(shí)，認(rèn)為顧客的到達(dá)形成了泊松流。 這三個(gè)條件是 (1)在不相重疊的時(shí)間區(qū)間內(nèi)顧客到達(dá)數(shù)是相互獨(dú)立的，稱此性質(zhì)為無(wú)后效性； (2)對(duì)充分小的?t，在時(shí)間區(qū)間t,t?t)內(nèi)有1個(gè)顧客到達(dá)的概率與t無(wú)關(guān)，而與區(qū)間長(zhǎng)?t成正比，即P1(t,t?t)?t?(?t)，?0是常數(shù)，它表示單位時(shí)間有一個(gè)顧客到達(dá)的概率，稱為概率強(qiáng)度； (3)對(duì)于充分小的?t，在時(shí)間區(qū)間t,t?t)內(nèi)有2個(gè)或2個(gè)以上顧客到達(dá)的概率極小，以至于可以忽略，即?P(t,t?t)?(?t)nn?2?在條件2，我們可以從上時(shí)間0算起，記為Pn(0,t)?P n(t)不加證明的給出(?t)n?tP n(t)?e,t?0n!n?0,1,2?P n(t)表示長(zhǎng)為t的時(shí)間區(qū)間內(nèi)到達(dá)n個(gè)顧客的概率。 其數(shù)學(xué)期望和方差分別是EN(t)?t;VarN(t)?t其中，?表示單位時(shí)間平均到達(dá)的顧客數(shù)，所以1?表示相繼顧客到達(dá)平均間隔時(shí)間，和ET的意義相符。 負(fù)指數(shù)分布隨機(jī)變量T的概率密度若是?e?t,t?0f T(t)?，?0,tK?1?1k?1?1?1?其中，p0?k11?n?1?n?1?K?1可以得到當(dāng)?1時(shí)，L s?nP n?n?p0?p0?n?nn?0n?1n?1K KKn?1dKn d?(1?k)?p0?p0d?(1?)d?n?1因?yàn)閐 f(x)(f?(x)g(x)?f(x)g?(x)()?，可以求得g2(x)dx g(x)d?(1?k)?(1?k?(1?)K?K?(1?k?1?k?1?k?(1?)K?K)L s?p0()?d?1?(1?)(1?k?1)(1?)(1?k?1)(K?1)?k?1?1?(1?k?1)?1KK當(dāng)?1時(shí)，表達(dá)式變?yōu)長(zhǎng) s?np n?n?p0?n?K?12k?0k?1k?1nK K其排隊(duì)長(zhǎng)為L(zhǎng) q?(n?1)p n?L s?(1?p0)k?1K對(duì)于系統(tǒng)來(lái)說(shuō)，由于容量有限，當(dāng)系統(tǒng)的人數(shù)達(dá)到K時(shí)，由于系統(tǒng)滿而造成顧客不能進(jìn)入。 假設(shè)顧客到達(dá)率為?，當(dāng)系統(tǒng)處于狀態(tài)K時(shí)，顧客不能進(jìn)入系統(tǒng)，即顧客可以進(jìn)入的概率為1?p k，因此，單位時(shí)間內(nèi)顧客可進(jìn)入的平均數(shù)為?e?(1?p k)?p0?p0?n nn?0n?0K k1?k1?1?k1?k1?k?1?1?1?p0?(1?)?(1?p0)k?1k?1k?1k?11?1?1?1?1?1?根據(jù)little公式，得到平均逗留時(shí)間W s?L sL s?(1?p0)?eL q?平均等待時(shí)間W q?e?W s?1?多服務(wù)臺(tái)模型M/M/K設(shè)顧客單個(gè)到達(dá)，相繼到達(dá)時(shí)間服從參數(shù)為?的負(fù)指數(shù)分布，系統(tǒng)中共有s個(gè)服務(wù)臺(tái)，每個(gè)服務(wù)臺(tái)的服務(wù)時(shí)間相互獨(dú)立，且服從參數(shù)為?的負(fù)指數(shù)分布。 當(dāng)顧客到達(dá)時(shí)，若有空閑的服務(wù)臺(tái)則馬上接受服務(wù)，否則便排隊(duì)等候，隊(duì)列為無(wú)限制。 討論其穩(wěn)態(tài)分布記p n?pN?n(n=0,1,2?)為系統(tǒng)達(dá)到平穩(wěn)狀態(tài)后隊(duì)長(zhǎng)N的概率分布，注意到有s?n=1,2,?,s的服務(wù)臺(tái)，有?n?和?n?s?n=s,s+1,?記?s?s?，則當(dāng)?s1時(shí)，有以前的計(jì)算的s?(?)n?n=1,2,?,s?n!C n?n?s?()?n?s(?)s()?n?s?n?ss!s?s!s?n?1p n=1,2,?s?s?1?n?s?n!0?，其中p0?p n?nn!s!(1?)?n?0?p n?s0?s!sn?s平均排隊(duì)長(zhǎng)為p0?(n?s)?np0?(n?s)?n?s+sL q?(n?s)p n?sn?s n?ss!s s!n?s?1n?s?1n?s?1?p0?s?s!(n?s)?n?sp0?s?n?ss s!n?s?1?n?s?1?(n?s)(s?n?sn?sp0?s)?s!n?s?1?(n?s)(?)s?n?s1?1p0?s?sp0?s?sp0?s?sd1n?s?1n?s?(n?s)(?s)?(?s)?s!n?s?1s!d?s!(1?s)2在以上公式中，同理，L q?L s得以得到平均隊(duì)長(zhǎng)同樣，根據(jù)Litter公式可以得到逗留時(shí)間和排隊(duì)時(shí)間。 獨(dú)立同分布Independent andidentically di