非線性規(guī)劃講稿交通系統(tǒng)工程

1、非線性規(guī)劃講稿交通系統(tǒng)工程2022/9/14第1頁，共90頁，2022年，5月20日，15點8分，星期四線性規(guī)劃：目標(biāo)函數(shù) 線性函數(shù) 約束條件非線性規(guī)劃：目標(biāo)函數(shù) 非線性函數(shù) 線性函數(shù) 約束條件第四章 非線性規(guī)劃2022/9/14第2頁，共90頁，2022年，5月20日，15點8分，星期四數(shù)學(xué)規(guī)劃問題的分類若f(x),gi(x),hj(x)為線性函數(shù)，即為線性規(guī)劃(LP)；若f(x),gi(x),hj(x)至少一個為非線性，即為非線性規(guī)劃(NLP)；對于非線性規(guī)劃，若沒有g(shù)i(x),hj(x)即X=Rn,稱為無約束非線性規(guī)劃或無約束最優(yōu)化問題；否則稱為約束非線性規(guī)劃或約束最優(yōu)化問題。2022/

2、9/14第3頁，共90頁，2022年，5月20日，15點8分，星期四X*=(1,1)X2X102121X2X102121線性規(guī)劃：如果最優(yōu)解存在，它一定存在于其可行域的邊界上 非線性規(guī)劃：如果最優(yōu)解存在，它未必一定存在于其可行域的邊界上，也可以出現(xiàn)在可行域的內(nèi)部2022/9/14第4頁，共90頁，2022年，5月20日，15點8分，星期四例:2022/9/14第5頁，共90頁，2022年，5月20日，15點8分，星期四三角形表示的是可行域同心圓表示的是目標(biāo)函數(shù)的等值線最優(yōu)解為（1/2，1/2） 最優(yōu)值為1/21/21/22022/9/14第6頁，共90頁，2022年，5月20日，15點8分，星

3、期四非線性規(guī)劃方法概述微分學(xué)方法的局限性：實際的問題中，函數(shù)可能是不連續(xù)或者不可微的。需要解復(fù)雜的方程組，而方程組到目前仍沒有有效的算法。實際的問題可能含有不等式約束，微分學(xué)方法不易處理。2022/9/14第7頁，共90頁，2022年，5月20日，15點8分，星期四數(shù)值方法的基本思路：迭代給定初始點x0根據(jù)x0,依次迭代產(chǎn)生點列xkxk的最后一點為最優(yōu)解xk有限xk無限xk收斂于最優(yōu)解2022/9/14第8頁，共90頁，2022年，5月20日，15點8分，星期四 迭代格式:xkxk+1pk稱pk為第k輪搜索方向，tk為第k輪沿pk方向的步長。產(chǎn)生tk和pk的不同方法，形成了不同的算法。2022

4、/9/14第9頁，共90頁，2022年，5月20日，15點8分，星期四一、無約束的數(shù)學(xué)模型解法：一維搜索法(無約束極小點問題) 最速下降法（無約束最優(yōu)化問題） 牛頓法 擬牛頓法 2022/9/14第10頁，共90頁，2022年，5月20日，15點8分，星期四一維搜索方法單峰函數(shù) 值得注意的是單峰函數(shù)不一定可導(dǎo)，也不一定連續(xù)；嚴(yán)格凸函數(shù)及其許多推廣都是單峰函數(shù)；另外，單峰函數(shù)有一個性質(zhì)通過在區(qū)間內(nèi)相異兩點函數(shù)值的計算就能劃定極小點的位置。 單峰函數(shù)舉例2022/9/14第11頁，共90頁，2022年，5月20日，15點8分，星期四搜索區(qū)間2022/9/14第12頁，共90頁，2022年，5月20

5、日，15點8分，星期四一維搜索方法搜索法發(fā)展的理由：在許多實際問題中，目標(biāo)函數(shù)不滿足凸性，于是促使人們考慮直接從函數(shù)的特性出發(fā)，對局部最優(yōu)解進行搜索?；窘Y(jié)構(gòu)：初始點t(0)確定移動方向t(k)精度檢查YN停止2022/9/14第13頁，共90頁，2022年，5月20日，15點8分，星期四一維搜索方法基本原理（1）通過比較搜索區(qū)間內(nèi)兩點的函數(shù)值，逐步縮短搜索區(qū)間。比如：（2）控制縮短率（每次留下的區(qū)間與原區(qū)間長度之比）的變化，使整體效益最佳。如何控制縮短率？上述兩個問題是有聯(lián)系的。2022/9/14第14頁，共90頁，2022年，5月20日，15點8分，星期四但由于事先不能估計t*的確切位置，

6、于是考慮采取下面的對策：使所選點在搜索區(qū)間內(nèi)處于對稱位置取點對稱原則，這樣無論去掉哪一段區(qū)間都差別不大。為了使搜索區(qū)間縮短的快一些，希望每次從原搜索區(qū)間中去掉的部分大一些。假定選的兩個內(nèi)點偏向一側(cè)，其中 ，則可能去掉較大的一段區(qū)間2022/9/14第15頁，共90頁，2022年，5月20日，15點8分，星期四在上述原則下，為使去掉的區(qū)間長一些，就一次而論，應(yīng)使兩點盡量靠近區(qū)間中點，這樣無論去掉哪一側(cè)，都可使區(qū)間縮短近一半，但是，由于此次留下的內(nèi)點相當(dāng)靠近留下的區(qū)間的一側(cè)，下一步再按對稱原則增選內(nèi)點時，在去掉的區(qū)間部分必然較小，總體效益不好。于是考慮采取如下對策，區(qū)間縮短率固定。由于取點對稱，區(qū)

7、間縮短率0.5。按照取點對稱和縮短率恒定兩條原則，計算縮短率。2022/9/14第16頁，共90頁，2022年，5月20日，15點8分，星期四區(qū)間縮小比例的確定：區(qū)間縮短比例為(t2-a)/(b-a)縮短比例為(b-t1)/(b-a)縮短比例 滿足：每次插入搜索點使得兩個區(qū)間a,t2和t1,b相等；每次迭代都以相等的比例縮小區(qū)間。0.618法t1t2ababt1t2退 出前一頁后一頁一維搜索方法0.618法2022/9/14第17頁，共90頁，2022年，5月20日，15點8分，星期四確定a,b,計算探索點t1=a+0.382(b-a)t2=a+0.618(b-a)是否是停止，輸出t1否以a,

8、t2為新的搜索區(qū)間是停止，輸出t2否以t1,b為新的搜索區(qū)間退 出前一頁后一頁如果給定下單峰區(qū)間a,b及控制誤差 ，0.618法解題步驟如下：2022/9/14第18頁，共90頁，2022年，5月20日，15點8分，星期四例：解：t1t230t1、第一輪：t1=1.146, t2=1.854t200.5退 出前一頁后一頁2022/9/14第19頁，共90頁，2022年，5月20日，15點8分，星期四2、第二輪：t2=1.146, t1=0.708t20=1.1460.53、第三輪：t1=0.438, t2=0.708b-t1=1.146-0.4380.51.8540tt2t11.4160tt2

9、t1退 出前一頁后一頁2022/9/14第20頁，共90頁，2022年，5月20日，15點8分，星期四4、第四輪：t2=0.876, t1=0.708b-t1=1.146-0.7080.5輸出：t*=t2=0.876為最優(yōu)解，最優(yōu)值為-0.079801.416tt1t2退 出前一頁后一頁2022/9/14第21頁，共90頁，2022年，5月20日，15點8分，星期四一般來說，0.618法的計算步驟如下：2022/9/14第22頁，共90頁，2022年，5月20日，15點8分，星期四0.618法中采用進退算法求初始區(qū)間2022/9/14第23頁，共90頁，2022年，5月20日，15點8分，星期

10、四關(guān)于梯度的復(fù)習(xí)：梯度是一個向量。n元函數(shù)f(x1 ,x2 ,xn)在某點x處的梯度為：梯度的方向與函數(shù)f的等值線的一個法線方向相同，從較低的等值線指向較高的等值線。梯度的方向就是函數(shù)f的值增加最快的方向，其相反方向就是函數(shù)值降低最快的方向。無約束最優(yōu)化方法最速下降法退 出前一頁后一頁2022/9/14第24頁，共90頁，2022年，5月20日，15點8分，星期四 第八章 一、方向?qū)?shù) 機動 目錄 上頁 下頁 返回 結(jié)束 二、梯度 三、物理意義 方向?qū)?shù)與梯度2022/9/14第25頁，共90頁，2022年，5月20日，15點8分，星期四一、方向?qū)?shù)定義: 若函數(shù)則稱為函數(shù)在點 P 處沿方向

11、l 的方向?qū)?shù).在點 處沿方向 l (方向角為 ) 存在下列極限: 機動 目錄 上頁 下頁 返回 結(jié)束 記作 2022/9/14第26頁，共90頁，2022年，5月20日，15點8分，星期四定理:則函數(shù)在該點沿任意方向 l 的方向?qū)?shù)存在 ,證明: 由函數(shù)且有在點 P 可微 ,得機動 目錄 上頁 下頁 返回 結(jié)束 故2022/9/14第27頁，共90頁，2022年，5月20日，15點8分，星期四機動 目錄 上頁 下頁 返回 結(jié)束 對于二元函數(shù)為, ) 的方向?qū)?shù)為特別: 當(dāng) l 與 x 軸同向 當(dāng) l 與 x 軸反向向角2022/9/14第28頁，共90頁，2022年，5月20日，15點8分，

12、星期四例1. 求函數(shù) 在點 P(1, 1, 1) 沿向量3) 的方向?qū)?shù) .機動 目錄 上頁 下頁 返回 結(jié)束 解: 向量 l 的方向余弦為2022/9/14第29頁，共90頁，2022年，5月20日，15點8分，星期四例2. 求函數(shù) 在點P(2, 3)沿曲線朝 x 增大方向的方向?qū)?shù).解:將已知曲線用參數(shù)方程表示為它在點 P 的切向量為機動 目錄 上頁 下頁 返回 結(jié)束 2022/9/14第30頁，共90頁，2022年，5月20日，15點8分，星期四例3. 設(shè)是曲面在點 P(1, 1, 1 )處指向外側(cè)的法向量,解: 方向余弦為而同理得方向的方向?qū)?shù).在點P 處沿求函數(shù)機動 目錄 上頁 下頁

13、 返回 結(jié)束 2022/9/14第31頁，共90頁，2022年，5月20日，15點8分，星期四二、梯度 方向?qū)?shù)公式令向量這說明方向：f 變化率最大的方向模 : f 的最大變化率之值方向?qū)?shù)取最大值：機動 目錄 上頁 下頁 返回 結(jié)束 2022/9/14第32頁，共90頁，2022年，5月20日，15點8分，星期四1. 定義即同樣可定義二元函數(shù)稱為函數(shù) f (P) 在點 P 處的梯度記作(gradient),在點處的梯度 機動 目錄 上頁 下頁 返回 結(jié)束 說明:函數(shù)的方向?qū)?shù)為梯度在該方向上的投影.向量2. 梯度的幾何意義2022/9/14第33頁，共90頁，2022年，5月20日，15點8

14、分，星期四函數(shù)在一點的梯度垂直于該點等值面(或等值線) ,機動 目錄 上頁 下頁 返回 結(jié)束 稱為函數(shù) f 的等值線 . 則L*上點P 處的法向量為 同樣, 對應(yīng)函數(shù)有等值面(等量面)當(dāng)各偏導(dǎo)數(shù)不同時為零時, 其上 點P處的法向量為指向函數(shù)增大的方向.2022/9/14第34頁，共90頁，2022年，5月20日，15點8分，星期四最速下降法又稱為梯度法，由Cauchy于1847年給出。最速下降法解決的是具有連續(xù)可微的目標(biāo)函數(shù)的UMP問題。最速下降法的基本思想：從當(dāng)前點xk出發(fā)尋找使得目標(biāo)函數(shù)下降最快的方向，即負(fù)梯度方向。退 出前一頁后一頁2022/9/14第35頁，共90頁，2022年，5月2

15、0日，15點8分，星期四最速下降法計算步驟：選區(qū)初始點x0和精度計算是否停止，輸出x0求p0=計算t0,使計算x1= x0-t0 p0退 出前一頁后一頁2022/9/14第36頁，共90頁，2022年，5月20日，15點8分，星期四例解：退 出前一頁后一頁2022/9/14第37頁，共90頁，2022年，5月20日，15點8分，星期四第六章 排隊論 排隊論(Queuing Theory)，又稱隨機服務(wù)系統(tǒng)理論(Random Service System Theory),是一門研究擁擠現(xiàn)象(排隊、等待)的科學(xué)。具體地說，它是在研究各種排隊系統(tǒng)概率規(guī)律性的基礎(chǔ)上，解決相應(yīng)排隊系統(tǒng)的最優(yōu)設(shè)計和最優(yōu)控

16、制問題。前 言2022/9/14第38頁，共90頁，2022年，5月20日，15點8分，星期四排隊是我們在日常生活和生產(chǎn)中經(jīng)常遇到的現(xiàn)象。 例如，上、下班搭乘公共汽車；顧客到商店購買物品；病員到醫(yī)院看??；旅客到售票處購買車票；學(xué)生去食堂就餐等就常常出現(xiàn)排隊和等待現(xiàn)象。除了上述有形的排隊之外，還有大量的所謂“無形”排隊現(xiàn)象，如幾個顧客打電話到出租汽車站要求派車，如果出租汽車站無足夠車輛、則部分顧客只得在各自的要車處等待，他們分散在不同地方，卻形成了一個無形隊列在等待派車。2022/9/14第39頁，共90頁，2022年，5月20日，15點8分，星期四排隊的不一定是人，也可以是物例如，通訊衛(wèi)星與地

17、面若干待傳遞的信息；生產(chǎn)線上的原料、半成品等待加工；因故障停止運轉(zhuǎn)的機器等待工人修理；碼頭的船只等待裝卸貨物；要降落的飛機因跑道不空而在空中盤旋等等。2022/9/14第40頁，共90頁，2022年，5月20日，15點8分，星期四 顯然，上述各種問題雖互不相同，但卻都有要求得到某種服務(wù)的人或物和提供服務(wù)的人或機構(gòu)。排隊論里把要求服務(wù)的對象統(tǒng)稱為“顧客”,而把提供服務(wù)的機構(gòu)或人稱為“服務(wù)臺”或“服務(wù)員”。不同的顧客與服務(wù)組成了各式各樣的服務(wù)系統(tǒng)。 顧客為了得到某種服務(wù)而到達系統(tǒng)、若不能立即獲得服務(wù)而又允許排隊等待，則加入等待隊伍，待獲得服務(wù)后離開系統(tǒng)。2022/9/14第41頁，共90頁，202

18、2年，5月20日，15點8分，星期四面對擁擠現(xiàn)象，人們總是希望盡量設(shè)法減少排隊，通常的做法是增加服務(wù)設(shè)施。但是增加的數(shù)量越多，人力、物力的支出就越大，甚至?xí)霈F(xiàn)空閑浪費，如果服務(wù)設(shè)施太少，顧客排隊等待的時間就會很長，這樣對顧客會帶來不良影響。于是，顧客排隊時間的長短與服務(wù)設(shè)施規(guī)模的大小，就構(gòu)成了設(shè)計隨機服務(wù)系統(tǒng)中的一對矛盾。如何做到既保證一定的服務(wù)質(zhì)量指標(biāo)，又使服務(wù)設(shè)施費用經(jīng)濟合理，恰當(dāng)?shù)亟鉀Q顧客排隊時間與服務(wù)設(shè)施費用大小這對矛盾，這就是隨機服務(wù)系統(tǒng)理論排隊論所要研究解決的問題。2022/9/14第42頁，共90頁，2022年，5月20日，15點8分，星期四 排隊論是1909年由丹麥工程師愛爾

19、朗(A .K .Erlang)在研究電話系統(tǒng)時創(chuàng)立的，幾十年來排隊論的應(yīng)用領(lǐng)域越來越廣泛，理論也日漸完善。特別是自二十世紀(jì)60年代以來，由于計算機的飛速發(fā)展，更為排隊論的應(yīng)用開拓了寬闊的前景。2022/9/14第43頁，共90頁，2022年，5月20日，15點8分，星期四排隊論研究的基本問題 排隊論研究的首要問題是排隊系統(tǒng)主要數(shù)量指標(biāo)的概率規(guī)律，即研究系統(tǒng)的整體性質(zhì)，然后進一步研究系統(tǒng)的優(yōu)化問題。與這兩個問題相關(guān)的還包括排隊系統(tǒng)的統(tǒng)計推斷問題。 (1)通過研究主要數(shù)量指標(biāo)在瞬時或平穩(wěn)狀態(tài)下的概率分布及其數(shù)字特征，了解系統(tǒng)運行的基本特征。 (2)統(tǒng)計推斷問題，建立適當(dāng)?shù)呐抨犇Ｐ褪桥抨犝撗芯康牡谝?/p>

20、步，建立模型過程中經(jīng)常會碰到如下問題：檢驗系統(tǒng)是否達到平穩(wěn)狀態(tài)；檢驗顧客相繼到達時間間隔的相互獨立性；確定服務(wù)時間的分布及有關(guān)參數(shù)等。2022/9/14第44頁，共90頁，2022年，5月20日，15點8分，星期四 (3)系統(tǒng)優(yōu)化問題，又稱為系統(tǒng)控制問題或系統(tǒng)運營問題，其基本目的是使系統(tǒng)處于最優(yōu)或最合理的狀態(tài)。系統(tǒng)優(yōu)化問題包括最優(yōu)設(shè)計問題和最優(yōu)運營問題，其內(nèi)容很多，有最少費用問題、服務(wù)率的控制問題、服務(wù)臺的開關(guān)策略、顧客(或服務(wù))根據(jù)優(yōu)先權(quán)的最優(yōu)排序等方面的問題。2022/9/14第45頁，共90頁，2022年，5月20日，15點8分，星期四第一節(jié) 排隊論的基本知識服務(wù)過程特征1）有要求服務(wù)的

21、人或物。如：去食堂就餐的顧客，去醫(yī)院看病的病人，要求通過交叉口的汽車，請求著陸的飛機等。2）有為顧客服務(wù)的人或物。如：食堂服務(wù)員，醫(yī)院大夫，信號交叉口，飛機跑道等，在排隊論中，統(tǒng)稱它們?yōu)椤胺?wù)員”或“服務(wù)臺”。由顧客和服務(wù)員組成一個服務(wù)系統(tǒng)。2022/9/14第46頁，共90頁，2022年，5月20日，15點8分，星期四3）顧客到達服務(wù)系統(tǒng)的時刻是隨機的。 如：汽車到達交叉口，顧客到達商店等都是隨機的。每位顧客需要的服務(wù)時間也是隨機的，有的服務(wù)時間長，有的服務(wù)時間短。因而整個服務(wù)系統(tǒng)的狀態(tài)也是隨機的。服務(wù)系統(tǒng)的隨機性造成某個階段顧客排隊長，而某些時候，服務(wù)員又空閑無事。2022/9/14第47

22、頁，共90頁，2022年，5月20日，15點8分，星期四 一般的排隊過程為：顧客由顧客源出發(fā)，到達服務(wù)機構(gòu)（服務(wù)臺、服務(wù)員）前，按排隊規(guī)則排隊等待接受服務(wù)，服務(wù)機構(gòu)按服務(wù)規(guī)則給顧客服務(wù)，顧客接受完服務(wù)后就離開。排隊過程的一般過程可用下圖表示。我們所說的服務(wù)系統(tǒng)就是指圖中實框所包括的部分。對上面所說的“顧客”和“服務(wù)員”要作廣泛的理解。它們可以是人，也可以是某種物質(zhì)或設(shè)備。排隊可以是有形的，也可以是無形的。排隊過程的一般表示2022/9/14第48頁，共90頁，2022年，5月20日，15點8分，星期四損失制系統(tǒng) 當(dāng)顧客到達這種服務(wù)系統(tǒng)時，若服務(wù)員都忙著，則顧客立即離去，另求服務(wù)。例如，打電話遇

23、到占線，用戶擱置而去；汽車停車場放滿時，就立即離去，另找停車場。等待制系統(tǒng) 顧客到達該服務(wù)系統(tǒng)時，服務(wù)員都在為先到的顧客服務(wù)，后到的顧客只好參加排隊，等候服務(wù)，一直等到有空的服務(wù)員來為它服務(wù)為止。例如，汽車在通過信號交叉口時，如果遇到紅燈，汽車只好在停車線后排隊等候，等到綠燈時通過。服務(wù)系統(tǒng)分類2022/9/14第49頁，共90頁，2022年，5月20日，15點8分，星期四混合制系統(tǒng) 介于前兩個系統(tǒng)之間，當(dāng)顧客到達時，若服務(wù)員都不空，他就排隊，但如果顧客到達時服務(wù)員都不空，且排隊位置已滿，顧客就立即離去，這是排隊長度有限制的服務(wù)系統(tǒng)。例如，去理發(fā)店理發(fā)，當(dāng)?shù)却戆l(fā)的位置都滿時，后來的顧客只得離

24、去。 在混合制中，還有另外一種形式：當(dāng)顧客到達時，服務(wù)員不空，他就排隊，等待服務(wù)，當(dāng)顧客等了一段時間后，仍輪不到為他服務(wù)，顧客就離開隊列，另求服務(wù)，這稱為排隊時間有限制的服務(wù)系統(tǒng)。例如，藥品、電子元件等過期失效均屬此類系統(tǒng)。 如果服務(wù)系統(tǒng)中只有一個服務(wù)員，則稱為單通道服務(wù)系統(tǒng)，若在系統(tǒng)中配備多個服務(wù)員則稱之為多通道服務(wù)系統(tǒng)。服務(wù)系統(tǒng)分類2022/9/14第50頁，共90頁，2022年，5月20日，15點8分，星期四服務(wù)系統(tǒng)組成 盡管排隊系統(tǒng)是多種多樣的，但從決定排隊系統(tǒng)進程的因素來看，它有三個基本的組成部分，這就是輸入過程、排隊規(guī)則及服務(wù)機構(gòu)。 1)輸入過程：描述顧客來源以及顧客到達排隊系統(tǒng)的

25、規(guī)律。包括： 顧客源中顧客的數(shù)量是確定型的還是隨機型的； 如：列車是按列車時刻表進站，到站時刻是確定型的；城市信號交叉口，汽車到達交叉口的時刻是隨機的。 顧客的總體（即顧客源）的組成是無限的還是有限的。 如，在道路交叉口，到達車輛的總體可以看成是無限的，而工廠內(nèi)停機待修的機器顯然是有限的。2022/9/14第51頁，共90頁，2022年，5月20日，15點8分，星期四2）排隊規(guī)則:（在損失制系統(tǒng)中，沒有顧客排隊，所以不存在排隊問題，這里的排隊規(guī)則是相對于等待制和混合制系統(tǒng)而言的）先到先服務(wù)（FCFS）：即按顧客到達的先后次序給予服務(wù)，這是最普遍的情況。后到先服務(wù)（LCFS）：如在情報系統(tǒng)中，最

26、后到達的情報往往是最有價值的，應(yīng)優(yōu)先采用；如堆在倉庫中的鋼板，使用時先用堆在上面的（即后堆上去的）鋼板。2022/9/14第52頁，共90頁，2022年，5月20日，15點8分，星期四隨機服務(wù)（RSS）：當(dāng)一個顧客被服務(wù)完了之后，服務(wù)員從排隊的顧客中任取一個，給予服務(wù)。如電話交換臺接通呼叫電話就是一例。有優(yōu)先權(quán)的服務(wù)（PR）：分輕重緩急給予服務(wù)。如加急電報要先于普通電報拍發(fā)；重病號應(yīng)先于輕病號醫(yī)療等。2022/9/14第53頁，共90頁，2022年，5月20日，15點8分，星期四3）服務(wù)機構(gòu)： 包括為每個顧客服務(wù)所需時間的概率分布，服務(wù)臺的數(shù)目以及服務(wù)臺的排列方式（串聯(lián)、并聯(lián)等）。顧客的服務(wù)時

27、間一般具有兩種形式：一種是每個顧客的服務(wù)時間是一個確定量，一種是每個顧客的服務(wù)時間是一個隨機變量，它服從某一概率分布。對于服務(wù)臺的排列方式，分單通道與多通道兩種。單通道服務(wù)系統(tǒng)單通道單服務(wù)臺系統(tǒng)單通道多服務(wù)臺串聯(lián)系統(tǒng) (如裝配流水線)2022/9/14第54頁，共90頁，2022年，5月20日，15點8分，星期四多通道服務(wù)系統(tǒng)可通的多通道系統(tǒng)不可通的多通道系統(tǒng)多通道混合系統(tǒng)2022/9/14第55頁，共90頁，2022年，5月20日，15點8分，星期四 排隊模型的表示方法 D.G.Kendall在1953年提出了一個分類方法，按照系統(tǒng)的三個最主要的、影響最大的三個特征要素進行分類，它們是：顧客

28、相繼到達的間隔時間分布、服務(wù)時間的分布、并列的服務(wù)臺個數(shù)。按照這三個特征要素分類的排隊系統(tǒng)，用符號（稱為Kendall記號）表示為 X/Y/Z其中X處填寫顧客相繼到達的間隔時間分布，Y處填寫服務(wù)時間的分布，Z處填寫并列的服務(wù)臺個數(shù)。 例如M/M/1，表示顧客相繼到達的間隔時間為負(fù)指數(shù)分布、服務(wù)時間為負(fù)指數(shù)分布、單服務(wù)臺的模型。2022/9/14第56頁，共90頁，2022年，5月20日，15點8分，星期四 后來，在1971年關(guān)于排隊論符號標(biāo)準(zhǔn)化的會議上決定，將Kendall符號擴充為： X/Y/Z/A/B/C 其中前三項意義不變。 A處填寫系統(tǒng)容量限制; B處填寫顧客源中的顧客數(shù)目; C處填寫

29、服務(wù)規(guī)則（如先到先服務(wù)FCFS，后到先服務(wù)LCFS）。 表示相繼到達間隔時間和服務(wù)時間的各種分布的符號為： M-指數(shù)分布或泊松輸入；D-定長分布；Ek-k階愛爾朗分布；GI-一般獨立隨機分布；G-一般隨機分布。2022/9/14第57頁，共90頁，2022年，5月20日，15點8分，星期四第二節(jié) 顧客到達分布和服務(wù)時間分布泊松分布負(fù)指數(shù)分布2022/9/14第58頁，共90頁，2022年，5月20日，15點8分，星期四 泊松(poisson)輸入，又稱最簡單流。滿足下面3個條件的輸入稱之為最簡單流。 (1) 平穩(wěn)性。又稱作輸入過程是平穩(wěn)的，指在長度為t的時段內(nèi)恰好到達k個顧客的概率僅與時段長度

30、有關(guān)，而與時段起點無關(guān)。即對任意(0,)，在(,+t或(0,t)內(nèi)恰好到達k個顧客的概率相等： 設(shè)初始條件為 ,且有 。2022/9/14第59頁，共90頁，2022年，5月20日，15點8分，星期四 (2)無后效性。指在任意幾個不相交的時間區(qū)間內(nèi)，各自到達的顧客數(shù)是相互獨立的。通俗地說就是以前到達的顧客情況，對以后顧客的到來沒有影響。否則就是關(guān)聯(lián)的。 (3)單個性又稱普通性。指在充分小的時段內(nèi)最多到達一個顧客。在一個充分小的時間間隔里不可能有兩個或兩個以上的顧客到達，只能有一個顧客到達。換句話說，有兩個或兩個以上的顧客到達的概率與有一個顧客到達的概率相比小到可以忽略的程度。因為泊松流實際應(yīng)用

31、最廣，也最容易處理，因而研究得也較多可以證明，對于泊松流，在長度為t的時間內(nèi)到達K個顧客的概率vk(t)服從泊松分布，即2022/9/14第60頁，共90頁，2022年，5月20日，15點8分，星期四如果顧客的到達過程（在確定的時間區(qū)間內(nèi)到達的顧客數(shù)）服從最簡單流，則顧客的到達時間間隔服從參數(shù)為 的負(fù)指數(shù)分布。如果顧客的服務(wù)過程（即離開服務(wù)臺的過程）服從最簡單流，則顧客的服務(wù)時間服從參數(shù) 的負(fù)指數(shù)分布。2022/9/14第61頁，共90頁，2022年，5月20日，15點8分，星期四第三節(jié) 生滅過程考察一個隨機過程，若己知現(xiàn)在t的狀態(tài)X(t)，那么將來的狀態(tài)X(t+n)取值（或取某些狀態(tài)）的概率

32、與過去狀態(tài)X(s)（st）取值無關(guān)，或更簡單的說，己知現(xiàn)在，將來與過去無關(guān)（條件獨立），則稱此性質(zhì)為馬爾可夫性（無后效性或簡稱馬氏性）。具有這種馬爾可夫性的過程稱為馬爾可夫過程。 2022/9/14第62頁，共90頁，2022年，5月20日，15點8分，星期四+O(t)+O(t)2022/9/14第63頁，共90頁，2022年，5月20日，15點8分，星期四 設(shè)有某個系統(tǒng)，具有0，1，2狀態(tài)，令N（t）表示系統(tǒng)在時刻t所處的狀態(tài)（即顧客數(shù)）。在任一時刻t，若系統(tǒng)處于狀態(tài)j，則在（t，t+t）內(nèi)系統(tǒng)由狀態(tài)j轉(zhuǎn)移到狀態(tài)j+1 （j0）的概率為 ，而由狀態(tài)j轉(zhuǎn)移到狀態(tài)j-1（j 1）的概率為 其中

33、為固定常數(shù)，并且在（t，t+t）內(nèi)發(fā)生兩次以上轉(zhuǎn)移的概率為 o（t ），這樣的一個系統(tǒng)狀態(tài)隨時間變化的過程就稱為一個生滅過程。生滅過程之定義2022/9/14第64頁，共90頁，2022年，5月20日，15點8分，星期四系統(tǒng)在t+t時刻有j個顧客，共有四種情況（這幾種情況是互斥的）：2022/9/14第65頁，共90頁，2022年，5月20日，15點8分，星期四若排隊系統(tǒng)的容量為無限，則在式中，令n=并去掉式即可。上面得到的哥爾莫可爾夫方程，它的解與系統(tǒng)所處的時刻有關(guān)。一般來說，當(dāng)系統(tǒng)處于運行的最初階段，它與系統(tǒng)的初始條件有關(guān)，但我們關(guān)心的是系統(tǒng)處于長期工作的情況。可以證明，當(dāng)t時，Pj（t）

34、趨于一個常數(shù)，即系統(tǒng)達到了統(tǒng)計平衡狀態(tài)，或者說系統(tǒng)達到了穩(wěn)定。2022/9/14第66頁，共90頁，2022年，5月20日，15點8分，星期四排隊系統(tǒng)的狀態(tài)概率j 表示系統(tǒng)中有j個顧客的狀態(tài)2022/9/14第67頁，共90頁，2022年，5月20日，15點8分，星期四各狀態(tài)概率間的關(guān)系在實際應(yīng)用中，我們不可能等到當(dāng)t，但對于絕大多數(shù)實際問題，系統(tǒng)會很快地趨于統(tǒng)計平衡狀態(tài)。2022/9/14第68頁，共90頁，2022年，5月20日，15點8分，星期四例6-2P1472022/9/14第69頁，共90頁，2022年，5月20日，15點8分，星期四第四節(jié) 標(biāo)準(zhǔn)M/M/1模型(M/M/1/) 排隊

35、系統(tǒng)的狀態(tài)n（n個顧客，其中n-1個顧客排隊）隨時間變化的過程稱為生滅過程，設(shè)平均到達率為,平均服務(wù)率為,負(fù)指數(shù)分布排隊系統(tǒng)（M/M/1/）的生滅過程可用下面的狀態(tài)轉(zhuǎn)移圖表示：01 n-1n n+1. 穩(wěn)態(tài)概率方程如下： -P0=P1 Pn-1+Pn+1=Pn+Pn設(shè)=/1，考慮到Pn=1，解得 P0=1- Pn=(1-) n , n1 這里的稱為服務(wù)強度，它刻劃了服務(wù)機構(gòu)的繁忙程度，所以又稱服務(wù)機構(gòu)的利用率。2022/9/14第70頁，共90頁，2022年，5月20日，15點8分，星期四 在M/M/1/排隊系統(tǒng)中，必須有1，即單位時間內(nèi)到達服務(wù)系統(tǒng)的顧客數(shù)大于離開服務(wù)系統(tǒng)的顧客數(shù)，那么當(dāng)t時

36、，排隊長度將無限增加，使系統(tǒng)達不到穩(wěn)定狀態(tài)。當(dāng)=1時，系統(tǒng)的負(fù)荷水平達到100%，即單位時間內(nèi)到達的顧客數(shù)等于離開的顧客數(shù)，但這時也無法達到穩(wěn)定狀態(tài)。雖然這時平均到達率等于平均服務(wù)率，但由于到達是隨機的，可能有些時候服務(wù)臺是空閑的，因而失去了一些可用于服務(wù)的時間，這種時間損失越多，排隊積累越快，漸漸的越排越長，而達不到統(tǒng)計平衡。2022/9/14第71頁，共90頁，2022年，5月20日，15點8分，星期四服務(wù)系統(tǒng)的運行指標(biāo) 對于一個排隊系統(tǒng)，運行狀況的好壞既涉及到顧客的利益，又涉及到服務(wù)機構(gòu)的利益，還有社會效果好壞的問題。為了研究排隊系統(tǒng)運行的效率、估計服務(wù)質(zhì)量、研究設(shè)計改進措施，必須確定一

37、些基本指標(biāo)，用以判斷系統(tǒng)運行狀況的優(yōu)劣。下面介紹幾種常用的指標(biāo)。 1)隊長：把系統(tǒng)中的顧客數(shù)稱為隊長，它的期望值記作Ls。而把系統(tǒng)中排隊等待服務(wù)的顧客數(shù)稱為排隊長（隊列長），它的期望值記作Lq。顯然有 隊長排隊長正被服務(wù)的顧客數(shù)。2022/9/14第72頁，共90頁，2022年，5月20日，15點8分，星期四 2)逗留時間：一個顧客從到達排隊系統(tǒng)到服務(wù)完畢離去的總停留時間稱為逗留時間，它的期望值記作Ws。 一個顧客在系統(tǒng)中排隊等待的時間稱為等待時間（或排隊時間），它的期望值記作Wq。顯然有 逗留時間等待時間服務(wù)時間。 3）忙期：指從顧客到達空閑服務(wù)機構(gòu)起到服務(wù)機構(gòu)再次空閑止的時間長度，即服務(wù)機

38、構(gòu)連續(xù)繁忙的時間長度。研究目的：通過對排隊系統(tǒng)中概率規(guī)律的研究，使系統(tǒng)達到最優(yōu)設(shè)計和最優(yōu)控制，以最小費用實現(xiàn)系統(tǒng)的最大效益。2022/9/14第73頁，共90頁，2022年，5月20日，15點8分，星期四 平均隊長： Ls=nPn=/ ()平均排隊長： Lq=(n1)Pn = (-) =Ls =Ls(1-P0)逗留時間分布函數(shù)為: F()=1e()平均逗留時間: Ws=1 /()=Ls /平均等待時間: Wq=Ws1 /=Lq / 系統(tǒng)的各項運行指標(biāo)計算P1492022/9/14第74頁，共90頁，2022年，5月20日，15點8分，星期四例6-3P1502022/9/14第75頁，共90頁，

39、2022年，5月20日，15點8分，星期四2022/9/14第76頁，共90頁，2022年，5月20日，15點8分，星期四2022/9/14第77頁，共90頁，2022年，5月20日，15點8分，星期四系統(tǒng)運行指標(biāo)系統(tǒng)平均顧客數(shù)（隊長）: 系統(tǒng)平均排隊顧客數(shù)（排隊長）：顧客在系統(tǒng)中的平均逗留時間: 顧客在系統(tǒng)中的平均等待時間: 2022/9/14第78頁，共90頁，2022年，5月20日，15點8分，星期四在系統(tǒng)中，當(dāng)排隊長度未滿排隊容量時，平均到達率為 ，而一旦排滿，到達率為0，即：對于損失制和混合制的排隊系統(tǒng)，顧客在到達服務(wù)系統(tǒng)時，若系統(tǒng)容量已滿，則自行消失。這就是說，到達的顧客不一定全部進入系統(tǒng)，為此：有必要尋求整個過程的有效到達率 ，取有效到達率為到達率的期望值，即每單位時間內(nèi)進入系統(tǒng)的平均顧客數(shù)：2022/9/14第79頁，共90頁，2022年，5月20日，15點8分，星期四工程實例例一 P152例二 P153例三 停車規(guī)劃項目