管理運(yùn)籌學(xué) 課件 田世海 第11、12章 有約束非線性規(guī)劃、排隊(duì)論

1OperationalResearch

運(yùn)籌學(xué)2Chapter11第11章ConstrainedOptimization約束極值問題OperationalResearchNonlinearProgramming非線性規(guī)劃3ConstrainedOptimization約束極值及最優(yōu)性條件不等式約束一般約束問題主要內(nèi)容等式約束約束極值問題的算法內(nèi)點(diǎn)法乘子法外點(diǎn)法41、約束極值問題的表示一、約束極值問題的最優(yōu)性條件562約束極值及最優(yōu)性條件——Kuhn-Tucker條件（1）等式約束性問題的最優(yōu)性條件

考慮minf(x)s.t.h(x)=0

回顧高等數(shù)學(xué)中所學(xué)的條件極值：

問題求z=f(x,y)極值，在ф(x,y)=0的條件下。即：minf(x,y)s.t.ф(x,y)=0

引入Lagrange乘子：λ

Lagrange函數(shù)L(x,y;λ)=f(x,y)+λф(x,y)7若x*是其的最優(yōu)解,則存在υ*∈Rl

使8

幾何意義：考慮一個(gè)約束的情況：x'

最優(yōu)性條件即：9(2)不等式約束極值問題的最優(yōu)性條件可行方向:①可行方向與積極約束:10積極約束:例:或起作用約束（緊約束\積極約束\有效約束）。11②如何判斷一個(gè)方向是可行方向?12證明:定理1:可行下降方向:13定理2:定理3:證略③極值點(diǎn)的必要條件:1415161718定理4(K-T條件):192021222324252627282930313233作業(yè):

求約束極值問題34353637（一）懲罰函數(shù)法（SUMT）二、約束極值問題的算法

將有約束優(yōu)化問題轉(zhuǎn)化為一系列無約束優(yōu)化問題進(jìn)行求解。（SequentialUnconstrainedMinimizationTechnique-SUMT）1、算法思想：2、算法類型：

外點(diǎn)法（外懲法）內(nèi)點(diǎn)法（內(nèi)懲法）383、問題：394、外點(diǎn)法（外部懲罰函數(shù)法）40414243（1）幾何解釋44（2）算法步驟（外點(diǎn)法）：45yesNo（3）外點(diǎn)法框圖46（4）應(yīng)注意的問題47例:

484950

（5）一般模型的外點(diǎn)法

算法步驟相同51例:

525354555、內(nèi)點(diǎn)法（閘函數(shù)法、障礙函數(shù)法）（1）集合結(jié)構(gòu)56（2）算法思想

內(nèi)點(diǎn)法（障礙函數(shù)法）的迭代點(diǎn)是在可行域點(diǎn)集內(nèi)部移動(dòng)的，對接近可行域邊界上的點(diǎn)施加越來越大的懲罰，對可行域邊界上的點(diǎn)施加無限大的懲罰，這好比邊界是一道障礙物，阻礙迭代點(diǎn)穿越邊界。

內(nèi)點(diǎn)法要求可行點(diǎn)集的內(nèi)點(diǎn)集合非空，否則算法無法運(yùn)行。這樣一來內(nèi)點(diǎn)法只對不等式約束的優(yōu)化問題才可能有效。57（3）算法分析5859（4）算法步驟（內(nèi)點(diǎn)法）：60內(nèi)點(diǎn)法框圖yesNo61例解6263例解6465例解66（5）罰函數(shù)法的缺點(diǎn)67(6)內(nèi)、外點(diǎn)法的優(yōu)缺點(diǎn)的比較1.x(0)∈S02.等式約束不適用3.障礙函數(shù)B(x)在S0的可微階數(shù)與gi(x)相同(可選用的無約束最優(yōu)化方法廣)4.迭代中x（k）∈R

（隨時(shí)可取x（k）≈x*）5.非凸規(guī)劃適用1.任意x(0)∈Rn2.等式約束適用3.懲罰項(xiàng)的二階偏導(dǎo)在S的邊界上不存在4.5.非凸規(guī)劃適用內(nèi)點(diǎn)法外點(diǎn)法迭代中x（k）R?686.乘子法乘子罰函數(shù):乘子罰函數(shù)與Langrange函數(shù)及懲罰函數(shù)的區(qū)別：多一項(xiàng)。

(1)等式約束69乘子罰函數(shù):70(2)等式、不等式約束71算法步驟（乘子罰函數(shù)法）：72解：1.懲罰函數(shù)法。對于懲罰函數(shù)例：問題的最優(yōu)解為x*=(0.25,0.75),分別用懲罰函數(shù)法和乘子法求它的迭代點(diǎn)列。

可求得最優(yōu)解為：

2.乘子法。對于乘子罰函數(shù)73可求得最優(yōu)解為：74

從表中可見，xk*比

xk近于x*的速度慢得多，用乘子法迭代6次就達(dá)到懲罰函數(shù)法迭代15次的效．這里，懲罰因子在懲罰函數(shù)法中要增大到u15＝3276.8，而在乘子法中只要增大到u6=6.4．相比之下，乘子法不需過分地增大懲罰因子，確實(shí)比懲罰函數(shù)法有效很多.OperationalResearch

運(yùn)籌學(xué)

第三章

排隊(duì)論本章要點(diǎn)：

1.排隊(duì)系統(tǒng)的組成；

2.排隊(duì)模型的研究方式；

3.典型排隊(duì)系統(tǒng)模型結(jié)構(gòu)及應(yīng)用。

內(nèi)容框架：輸入過程排隊(duì)規(guī)則服

務(wù)

臺排隊(duì)系統(tǒng)符號表示研究方式

明確系統(tǒng)意義

畫狀態(tài)轉(zhuǎn)移速度圖→

狀態(tài)概率方程

計(jì)算基本數(shù)量指標(biāo)

應(yīng)用舉例分

類典型模型及其應(yīng)用

3.1排隊(duì)系統(tǒng)的特征與基本排隊(duì)系統(tǒng)一、引言1、排隊(duì)服務(wù)系統(tǒng)

在生產(chǎn)和日常生活中，經(jīng)?？梢耘龅礁鞣N各樣的服務(wù)系統(tǒng)。比如：（1）到商店買東西，顧客和售貨員構(gòu)成一個(gè)服務(wù)系統(tǒng)，服務(wù)的對象是顧客，服務(wù)機(jī)構(gòu)是售貨員；（2）病人到醫(yī)院看病也構(gòu)成一個(gè)服務(wù)系統(tǒng)，服務(wù)的對象是病人，服務(wù)機(jī)構(gòu)是醫(yī)生。這些服務(wù)系統(tǒng)都有一個(gè)共同的特征——排隊(duì)等候服務(wù)。這是因?yàn)?，在某時(shí)刻要求服務(wù)的數(shù)量超過服務(wù)機(jī)構(gòu)（售貨員，醫(yī)生等）的容量時(shí)，也就是說，到達(dá)的顧客不能立即得到服務(wù)時(shí)，這時(shí)（若情況允許排隊(duì)等候的話）有的必須等候，因而出現(xiàn)排隊(duì)現(xiàn)象，稱這種排隊(duì)等候服務(wù)系統(tǒng)為排隊(duì)服務(wù)系統(tǒng)。

定義1稱排隊(duì)等候服務(wù)系統(tǒng)為排隊(duì)服務(wù)系統(tǒng)。說明：（1）排隊(duì)服務(wù)系統(tǒng)遠(yuǎn)不僅在個(gè)人日常生活中出現(xiàn)。例如，電話局的占線問題，車站、碼頭等交通樞紐的車船堵塞和疏通，故障機(jī)器的停機(jī)待修，水庫的存貯調(diào)節(jié)等都是排隊(duì)服務(wù)系統(tǒng)。在一個(gè)服務(wù)系統(tǒng)中，若到達(dá)服務(wù)系統(tǒng)的顧客完全按固定的間隔時(shí)間到達(dá)，又服務(wù)設(shè)施用在每個(gè)顧客身上的服務(wù)時(shí)間也是固定的，就象工廠流水生產(chǎn)線的生產(chǎn)那樣，有固定的節(jié)拍，那么這類服務(wù)系統(tǒng)的設(shè)計(jì)計(jì)算是比較方便的。（2）在大多數(shù)服務(wù)系統(tǒng)中顧客到達(dá)是隨機(jī)的，服務(wù)設(shè)施用于每個(gè)顧客身上的服務(wù)時(shí)間也是隨機(jī)的。

定義2若一個(gè)排隊(duì)服務(wù)系統(tǒng)中顧客到達(dá)是隨機(jī)的，服務(wù)設(shè)施用于每個(gè)顧客身上的服務(wù)時(shí)間也是隨機(jī)的，則稱此排隊(duì)服務(wù)系統(tǒng)為隨機(jī)服務(wù)系統(tǒng)。

對于隨機(jī)服務(wù)系統(tǒng)，我們應(yīng)開設(shè)多少服務(wù)設(shè)施比較合適呢？如果開設(shè)多了，就要增加服務(wù)人員及相應(yīng)的設(shè)施，增加服務(wù)費(fèi)用；如果開設(shè)少了排隊(duì)現(xiàn)象就會嚴(yán)重，對顧客個(gè)人和對社會都會帶來不利影響，到底怎樣才能做到既保證一定的服務(wù)質(zhì)量指標(biāo)，又使服務(wù)設(shè)施費(fèi)用經(jīng)濟(jì)合理，恰當(dāng)?shù)亟鉀Q顧客排隊(duì)時(shí)間與服務(wù)設(shè)施費(fèi)用大小這對矛盾，這就是研究隨機(jī)服務(wù)系統(tǒng)的理論——排隊(duì)論所要研究解決的問題。（3）排隊(duì)系統(tǒng)的統(tǒng)計(jì)推斷，即判斷一個(gè)給定的排隊(duì)系統(tǒng)符合那種類型，以便根據(jù)排隊(duì)理論進(jìn)行分析研究。本章著重研究性態(tài)問題。排隊(duì)論研究的內(nèi)容有下列三部分：（1）性態(tài)問題：即研究各種隨機(jī)服務(wù)系統(tǒng)的概率規(guī)律性。如研究隊(duì)長分布、等待時(shí)間分布和忙期分布等。（2）最優(yōu)化問題：分靜態(tài)最優(yōu)和動(dòng)態(tài)最優(yōu)，前者指最優(yōu)設(shè)計(jì)；后者指現(xiàn)有排隊(duì)系統(tǒng)的最優(yōu)運(yùn)營；2、什么是排隊(duì)論？

排隊(duì)論是研究擁擠現(xiàn)象的一門學(xué)科。

它是在研究各種排隊(duì)系統(tǒng)概率規(guī)律性的基礎(chǔ)上，解決有關(guān)排隊(duì)系統(tǒng)的最優(yōu)設(shè)計(jì)（靜態(tài)）和最優(yōu)控制（動(dòng)態(tài)）問題。3、排隊(duì)論的起源與應(yīng)用領(lǐng)域

20世紀(jì)初——Bell電話公司為減少用戶呼叫，研究電話線路合理配置問題；

1909年丹麥工程師A.K.Erlang

受熱力學(xué)統(tǒng)計(jì)平衡概念啟發(fā)

論文“概率論與電話交換”，解決了上述問題；

應(yīng)用于：通訊系統(tǒng)、交通運(yùn)輸、機(jī)器維修、庫存控制、計(jì)算機(jī)設(shè)計(jì)……

二、排隊(duì)系統(tǒng)的特征及其組成1、排隊(duì)系統(tǒng)的特征即擁擠現(xiàn)象的共性:

有請求服務(wù)的人或物

；

有為顧客服務(wù)的人或物

；

具有隨機(jī)性

；（各種排隊(duì)系統(tǒng)中，顧客相繼到達(dá)的間隔時(shí)間以及對每一位顧客的服務(wù)時(shí)間是隨機(jī)的）

隨機(jī)性是排隊(duì)系統(tǒng)的一個(gè)重要特征

。2、排隊(duì)系統(tǒng)的基本組成

顧客源等待隊(duì)列顧客離去（輸出）服務(wù)機(jī)構(gòu)排隊(duì)規(guī)則？（1）輸入過程

：

刻劃顧客到達(dá)排隊(duì)系統(tǒng)的規(guī)律。排隊(duì)系統(tǒng)123顧客到達(dá)（輸入）服務(wù)機(jī)構(gòu)

顧客總體數(shù)（顧客源）有限或無限；

顧客到達(dá)方式是單個(gè)到達(dá)或成批到達(dá)；

顧客相繼到達(dá)的間隔時(shí)間服從什麼樣的概率分布；（2）服務(wù)規(guī)則

：描述顧客到達(dá)排隊(duì)系統(tǒng)后接受服務(wù)的先后次序，一般可分為即時(shí)制或損失制、等待制和混合制三類：

損失制(Losingsystem)——當(dāng)顧客到達(dá)排隊(duì)系統(tǒng)時(shí)，若所有的服務(wù)臺均被占用(正在進(jìn)行服務(wù))，則離開系統(tǒng)，永不再來

；

等待制(Waitingsystem)——顧客到達(dá)系統(tǒng)時(shí)，所有的服務(wù)臺均被占用（正在進(jìn)行服務(wù)），顧客就加入排隊(duì)行列等待服務(wù)，服務(wù)臺可按照下面的規(guī)則進(jìn)行排序服務(wù)：①

先到先服務(wù)（FCFS）FirstComeFirstserve②

后到先服務(wù)（LCFS）Last

ComeFirstserve③

隨機(jī)服務(wù)（SIRO）ServeInRandomOrder④

有優(yōu)先權(quán)的服務(wù)（PR）Preference

混合制(LosingsystemandWaitingsystem)——損失制和等待制的結(jié)合，一般是指允許排隊(duì)，但又不允許隊(duì)列無限長下去。主要有以下3種情況：①隊(duì)長有限。當(dāng)?shù)却?wù)的顧客人數(shù)超過規(guī)定數(shù)量時(shí)，后來的顧客就自動(dòng)離去，另求服務(wù)，即系統(tǒng)的等待空間是有限的。②等待時(shí)間有限。即顧客在系統(tǒng)中的等待時(shí)間不超過某一給定的長度T，當(dāng)?shù)却龝r(shí)間超過時(shí)間T時(shí)，顧客將自動(dòng)離去，并不再回來。③逗留時(shí)間（等待時(shí)間與服務(wù)時(shí)間之和）有限。（3）服務(wù)機(jī)構(gòu)（服務(wù)臺）：

數(shù)量及布置形式——見下頁圖

某一時(shí)刻接受服務(wù)的顧客數(shù)——單個(gè)服務(wù)還是成批服務(wù)；

服務(wù)時(shí)間的分布——最常見的有定常分布、負(fù)指數(shù)分布、k階愛爾朗分布、一般分布等

；

。。。。。。12┇n。。。。。。。。。12┇n（a）單隊(duì)單臺。。。。。。12312(d)混合多服務(wù)臺。。。。。。。。。12…n(e)串聯(lián)多服務(wù)臺排隊(duì)系統(tǒng)服務(wù)臺布置形式

(b)多隊(duì)多臺(c)單隊(duì)多臺三、排隊(duì)模型的符號表示——

肯道爾分類方法(D.G.kendall)

表示為：

A/B/C/D/E/F或

[A/B/C]：[d/e/f]A

表示輸入過程——顧客相繼到達(dá)的間隔時(shí)間的分布；B

表示服務(wù)時(shí)間服從的分布；C

表示服務(wù)臺的個(gè)數(shù)；D

表示系統(tǒng)容量；E

表示顧客源包含的全部個(gè)體數(shù)量；F表示服務(wù)規(guī)則

；舉例：

M/M/1/∞/∞/FCFS表示泊松輸入、服務(wù)時(shí)間服從負(fù)指數(shù)分布、1個(gè)服務(wù)臺、系統(tǒng)容量無限制（即等待制）、顧客源無限、先到先服務(wù)的排隊(duì)系統(tǒng)

；

GI/EK/1/N/∞/FCFS表示一般獨(dú)立輸入（顧客到達(dá)的間隔時(shí)間服從一般獨(dú)立分布）、服務(wù)時(shí)間服從K階愛爾朗分布、1個(gè)服務(wù)臺、系統(tǒng)容量為N、顧客源無限、先到先服務(wù)的排隊(duì)系統(tǒng)。

常用的各種分布符號：M——負(fù)指數(shù)分布(兼指泊松輸入)；D——定長分布；EK

——

K階愛爾朗分布；GI——

一般獨(dú)立隨機(jī)分布；G——

一般隨機(jī)分布；四、排隊(duì)系統(tǒng)研究的問題

1、排隊(duì)系統(tǒng)的數(shù)量指標(biāo)(特征量

)（1）

研究的目的是：了解系統(tǒng)的基本特征和性態(tài)，揭示其表現(xiàn)的概率規(guī)律性，以便對系統(tǒng)作出評價(jià)。（2）主要的數(shù)量指標(biāo)：*

隊(duì)長（Ls）——排隊(duì)系統(tǒng)中顧客的平均數(shù)（期望值），包括正在接受服務(wù)和等待接受服務(wù)的顧客總數(shù)期望值。

已知隊(duì)長分布，就能計(jì)算隊(duì)長超過某個(gè)數(shù)量的概率，據(jù)此可以考慮是否應(yīng)改變服務(wù)方式、設(shè)計(jì)合理的等待空間等；*

隊(duì)列長（排隊(duì)長Lq）——系統(tǒng)中排隊(duì)等待接受服務(wù)的顧客數(shù)期望值；*

逗留時(shí)間（Ws）——顧客在系統(tǒng)內(nèi)停留時(shí)間（包括排隊(duì)等待時(shí)間和接受服務(wù)的時(shí)間）的期望值；*

等待時(shí)間（Wq）——顧客從到達(dá)系統(tǒng)的時(shí)刻到開始接受服務(wù)的時(shí)刻止的時(shí)間段；

*忙期和閑期分布——忙期指從有顧客到達(dá)空閑服務(wù)臺接受服務(wù)開始到服務(wù)臺再度空閑為止的這段時(shí)間，即服務(wù)臺連續(xù)工作的時(shí)間。“忙期”是一個(gè)隨機(jī)變量，可以表征服務(wù)臺的工作強(qiáng)度；

服務(wù)臺連續(xù)保持空閑的時(shí)間長度稱為閑期。

在排隊(duì)系統(tǒng)中忙期和閑期是交替出現(xiàn)的。*

服務(wù)設(shè)備利用率——指服務(wù)設(shè)備工作時(shí)間占總時(shí)間的比例。

該指標(biāo)可以衡量服務(wù)設(shè)備的工作強(qiáng)度、磨損和疲勞程度。*顧客損失率——由于服務(wù)能力不足而造成的顧客流失的概率稱為顧客損失率。

該指標(biāo)過高會造成服務(wù)系統(tǒng)利潤減少，因此損失制和混合制排隊(duì)系統(tǒng)均會重視對該指標(biāo)的研究。

2、統(tǒng)計(jì)推斷問題的研究

對實(shí)際問題建立排隊(duì)模型時(shí)，必須判斷該系統(tǒng)適合建立何種排隊(duì)模型，從而進(jìn)一步用排隊(duì)理論進(jìn)行分析研究。

首先必須進(jìn)行現(xiàn)實(shí)數(shù)據(jù)的收集、處理；

進(jìn)而研究相繼到達(dá)的間隔時(shí)間是否獨(dú)立分布、確定其分布類型和有關(guān)參數(shù)，研究服務(wù)時(shí)間與相繼到達(dá)的間隔時(shí)間之間的獨(dú)立性以及服務(wù)時(shí)間的分布等；

判斷該系統(tǒng)適合建立何種類型的排隊(duì)模型，再用排隊(duì)理論進(jìn)行分析研究。

3、排隊(duì)系統(tǒng)的優(yōu)化

研究排隊(duì)系統(tǒng)最優(yōu)設(shè)計(jì)的靜態(tài)優(yōu)化和研究排隊(duì)系統(tǒng)最優(yōu)控制的動(dòng)態(tài)優(yōu)化。

最優(yōu)設(shè)計(jì)：通常是在輸入和服務(wù)參數(shù)給定的條件下，確定系統(tǒng)的設(shè)計(jì)參數(shù)（如服務(wù)臺數(shù)量），以求系統(tǒng)運(yùn)行指標(biāo)達(dá)到最優(yōu)。

最優(yōu)控制：在系統(tǒng)運(yùn)行的參數(shù)可以隨時(shí)間或狀態(tài)而變化的情況下（如服務(wù)率隨顧客數(shù)的變化而改變）根據(jù)系統(tǒng)的實(shí)際情況假設(shè)一個(gè)合理或?qū)嶋H可行的控制策略，然后分析確定系統(tǒng)運(yùn)行的最佳參數(shù)或者是對一個(gè)具體系統(tǒng)研究一個(gè)最佳的控制策略。

研究排隊(duì)系統(tǒng)的目的就是通過對該系統(tǒng)概率規(guī)律的研究，達(dá)到系統(tǒng)的最優(yōu)設(shè)計(jì)和最優(yōu)控制，以最少的費(fèi)用實(shí)現(xiàn)系統(tǒng)的最大效益。即使服務(wù)系統(tǒng)既能在適當(dāng)?shù)某潭壬蠞M足顧客需求，同時(shí)又使所需費(fèi)用達(dá)到最小。

服務(wù)費(fèi)用等待費(fèi)用費(fèi)用服務(wù)水平總費(fèi)用費(fèi)用優(yōu)化示意圖

1、

泊松分布（Poisson）也稱為泊松流，在排隊(duì)論中常稱為最簡單流

。

概率分布

：其中，λ>0為一常數(shù)，t≥0。求N(t)的數(shù)學(xué)期望得:則λ=E[N(t)]/t。因此，λ表示單位時(shí)間內(nèi)到達(dá)系統(tǒng)的平均顧客數(shù),又稱平均到達(dá)率

。五、排隊(duì)系統(tǒng)中常見的幾種典型理論分布

最簡單流的4個(gè)基本性質(zhì)：

平穩(wěn)性：在時(shí)間段t內(nèi)，恰有n個(gè)顧客到達(dá)系統(tǒng)的概率P{N(t)=n}僅與t的長短有關(guān),而與該時(shí)間段的起始時(shí)刻無關(guān)；

無后效性：在不相交的時(shí)間區(qū)間內(nèi)到達(dá)的顧客數(shù)是相互獨(dú)立的。如：在[a，a+t]時(shí)段內(nèi)到達(dá)K個(gè)顧客的概率與時(shí)刻a之前到達(dá)多少顧客無關(guān)；

普通性：在充分小的間隔時(shí)間內(nèi)至少到達(dá)兩個(gè)顧客的概率ψ(Δt)=o(t),t→0,即

有限性：在任意有限的時(shí)間區(qū)間內(nèi)，到達(dá)有限個(gè)顧客的概率為1，即

泊松流在排隊(duì)論中的意義：

實(shí)際問題中最常見；

數(shù)字處理簡單；

當(dāng)實(shí)際流與泊松流有較大出入時(shí)，經(jīng)過一定的變換，結(jié)果也可達(dá)到一定的精度；

2、

負(fù)指數(shù)分布

密度函數(shù)和分布函數(shù)

：

數(shù)學(xué)期望和方差：

定理6-1

顧客到達(dá)服從參數(shù)為λ的泊松分布等價(jià)于顧客相繼到達(dá)的間隔時(shí)間是獨(dú)立的且同為負(fù)指數(shù)分布。參數(shù)μ>0表示單位時(shí)間內(nèi)完成服務(wù)的顧客平均數(shù),稱為平均服務(wù)率。

3、

愛爾朗分布

當(dāng)顧客在系統(tǒng)內(nèi)所接受的服務(wù)可以分為K個(gè)階段，每個(gè)階段的服務(wù)時(shí)間T1，T2，…，Tk為服從同一分布

（參數(shù)為kμ的負(fù)指數(shù)分布）的k個(gè)相互獨(dú)立的隨機(jī)變量，顧客在完成全部服務(wù)內(nèi)容并離開系統(tǒng)后，另一個(gè)顧客才能進(jìn)入服務(wù)系統(tǒng)，則顧客在系統(tǒng)內(nèi)接受服務(wù)時(shí)間之和T=T1+T2+…+Tk服從k階愛爾朗分布Ek，其分布密度函數(shù)為：相應(yīng)的數(shù)學(xué)期望和方差為：

當(dāng)k=1時(shí)，愛爾朗分布?xì)w結(jié)為負(fù)指數(shù)分布，當(dāng)k增大時(shí)，圖形逐漸變?yōu)閷ΨQ的，當(dāng)k≥30時(shí)，近似于正態(tài)分布，當(dāng)k→∞，由D(T)=0可知,愛爾朗分布?xì)w結(jié)為定長分布。因此，愛爾朗分布類可以看成完全隨機(jī)與完全確定的中間型，能對現(xiàn)實(shí)問題提供更廣泛的模型類。k=∞k=3k=2k=1

3.2單服務(wù)臺負(fù)指數(shù)分布排隊(duì)系統(tǒng)

一、標(biāo)準(zhǔn)的M/M/1模型，即M/M/1/∞

/∞

二、系統(tǒng)容量有限制，即M/M/1/N

/∞

三、顧客源為有限制，即M/M/1/∞/m

一、標(biāo)準(zhǔn)的M/M/1模型1、系統(tǒng)的特點(diǎn)：顧客按泊松流輸入、平均到達(dá)率為λ，服務(wù)時(shí)間服從負(fù)指數(shù)分布、平均服務(wù)率為μ，1個(gè)服務(wù)臺，系統(tǒng)容量和顧客源均為無限。當(dāng)顧客來到系統(tǒng)時(shí)，若服務(wù)臺忙，則顧客排隊(duì)等待服務(wù)，排隊(duì)規(guī)則為先到先服務(wù)的排隊(duì)系統(tǒng)。由于是單服務(wù)臺，單位時(shí)間到達(dá)系統(tǒng)的顧客數(shù)為λ，單位時(shí)間被服務(wù)完的顧客數(shù)為μ。且顧客源無限，因此，在各種狀態(tài)的情況下，系統(tǒng)的“出生率”為λ，系統(tǒng)的“死亡率”為μ。系統(tǒng)在穩(wěn)態(tài)情況下的狀態(tài)轉(zhuǎn)移如下圖所示

0

1

2n-1

nn+1…P0

P1P2Pn-1

PnPn+12、系統(tǒng)的狀態(tài)轉(zhuǎn)移速度圖：3、狀態(tài)概率方程：根據(jù)以上狀態(tài)轉(zhuǎn)移圖，可以得出如下平衡方程…………遞推求解P1，P2，…，Pn，…，得ρ表示平均到達(dá)率與平均服務(wù)率之比，稱為服務(wù)強(qiáng)度要求λ/μ<1,否則系統(tǒng)將是超負(fù)荷的,不能達(dá)到穩(wěn)態(tài)而無法討論?！纠?】高速公路收費(fèi)處設(shè)有一個(gè)收費(fèi)通道，汽車到達(dá)服從泊松分布，平均到達(dá)速率為150輛／小時(shí)，收費(fèi)時(shí)間服從負(fù)指數(shù)分布，平均收費(fèi)時(shí)間為15秒／輛。求(1)收費(fèi)處空閑的概率；(2)收費(fèi)處忙的概率；(3)系統(tǒng)中分別有1，2，3輛車的概率?！窘狻扛鶕?jù)題意,

=150輛/小時(shí),1/μ=15秒/輛=1/240（小時(shí)/輛）,即μ＝240（輛/小時(shí)）。ρ＝λ/μ=150/240=5/8，則有(1)系統(tǒng)空閑的概率為：P0=1－ρ=1－(5/8)=3/8=0.375(2)系統(tǒng)忙的概率為：1-P0=5/8=0.625(3)系統(tǒng)中有1輛車的概率為：P1=ρ(1－ρ)=0.625×0.375=0.234系統(tǒng)中有2輛車的概率為：P2=ρ2(1－ρ)=0.234×0.625=0.146系統(tǒng)中有3輛車的概率為：P3=ρ3(1－ρ)==0.146×0.625=0.0914、系統(tǒng)的運(yùn)行指標(biāo)：（1）在系統(tǒng)中的平均顧客數(shù)隊(duì)長期望值（2）在隊(duì)列中等待的平均顧客數(shù)（隊(duì)列長期望值）（3）在系統(tǒng)中顧客逗留時(shí)間的期望值（4）在系統(tǒng)中顧客等待時(shí)間的期望值（5）系統(tǒng)處于空閑狀態(tài)的概率（6）系統(tǒng)處于忙期的概率（7）系統(tǒng)處于忙期時(shí)隊(duì)列中顧客平均數(shù)（8）系統(tǒng)處于忙期時(shí)顧客平均等待時(shí)間Little公式:【例2】輕軌進(jìn)站口售票處設(shè)有一個(gè)售票窗口，乘客到達(dá)服從泊松分布，平均到達(dá)速率為200人/小時(shí)，售票時(shí)間服從負(fù)指數(shù)分布，平均售票時(shí)間為15秒/人。求L、Lq、W和Wq。【解】根據(jù)題意，λ=200人/小時(shí)，μ=240人/小時(shí)，ρ=5/6。1、系統(tǒng)的特征

顧客按泊松流輸入,平均到達(dá)率為λ；

服務(wù)時(shí)間服從負(fù)指數(shù)分布,平均服務(wù)率為μ；

1個(gè)服務(wù)臺；

系統(tǒng)容量為N,顧客源無限,排隊(duì)規(guī)則為先到先服務(wù)的混合制排隊(duì)系統(tǒng)。

當(dāng)顧客來到系統(tǒng)時(shí),若系統(tǒng)中的顧客已經(jīng)等于N，則自動(dòng)離去,另求服務(wù)

。

二、系統(tǒng)容量有限制，即M/M/1/N

/∞顧客到達(dá)因隊(duì)列滿而離去進(jìn)入隊(duì)列接受服務(wù)服務(wù)完畢后離去2、狀態(tài)轉(zhuǎn)移速度圖（1）系統(tǒng)狀態(tài)

：系統(tǒng)中的顧客數(shù)。（2）狀態(tài)轉(zhuǎn)移速度圖：N-1

NN-2

2

1

0……μμμμλλλλ

M/M/1/N/∞/FCFS系統(tǒng)狀態(tài)轉(zhuǎn)移速度圖

圓圈表示狀態(tài)符號

，箭頭表示從一個(gè)狀態(tài)到另一個(gè)狀態(tài)的轉(zhuǎn)移；

3、狀態(tài)概率方程：…4、系統(tǒng)的運(yùn)行指標(biāo)：(1)系統(tǒng)中的平均顧客數(shù)Ls(2)隊(duì)列中的平均顧客數(shù)Lq

λe稱為有效到達(dá)率，即單位時(shí)間內(nèi)到達(dá)并能進(jìn)入隊(duì)列的平均顧客數(shù)。ρe稱為有效服務(wù)強(qiáng)度在研究顧客在系統(tǒng)中平均逗留時(shí)間和在隊(duì)列中平均等待時(shí)間時(shí)，雖然可用公式：但要注意平均到達(dá)率是在系統(tǒng)中有空時(shí)的平均到達(dá)率，當(dāng)系統(tǒng)已滿時(shí)，則到達(dá)率為0，因此需求出有效到達(dá)率。(3)顧客在系統(tǒng)中的平均逗留時(shí)間W(4)顧客在隊(duì)列中的平均逗留時(shí)間(5)有效到達(dá)率的另一種計(jì)算公式λe=λ（1-PN）+0PN

(系統(tǒng)不滿時(shí)顧客以λ的速度進(jìn)入系統(tǒng)）

=μ（1-P0）+0P0

（系統(tǒng)不空時(shí)顧客以μ的速度離開系統(tǒng)）(6)

系統(tǒng)平均每單位時(shí)間損失的顧客數(shù)λ損=λ-λe=λPN(7)

系統(tǒng)平均每單位時(shí)間損失的顧客數(shù)

從服務(wù)臺閑到下一個(gè)顧客來到的平均間隔時(shí)間是1/λ，因此平均閑期長為

T閑=1/λ由于服務(wù)臺忙閑間隔出現(xiàn)，故有：平均忙期長T忙/平均閑期長T閑=P忙/P閑=(1-P0)/P0，于是

T忙=T閑[(1-P0)/P0]=1/λ[(1-P0)/P0]【例3】咨詢中心有一位咨詢工作人員，每次只能咨詢一人，另外有4個(gè)座位供前來咨詢