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

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

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

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

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

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

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

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

8、t2為新的搜索區(qū)間是停止，輸出t2否以t1,b為新的搜索區(qū)間退 出前一頁(yè)后一頁(yè)如果給定下單峰區(qū)間a,b及控制誤差 ，0.618法解題步驟如下：2022/9/14第18頁(yè)，共90頁(yè)，2022年，5月20日，15點(diǎn)8分，星期四例：解：t1t230t1、第一輪：t1=1.146, t2=1.854t200.5退 出前一頁(yè)后一頁(yè)2022/9/14第19頁(yè)，共90頁(yè)，2022年，5月20日，15點(diǎn)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退 出前一頁(yè)后一頁(yè)2022/9/14第20頁(yè)，共90頁(yè)，2022年，5月20日，15點(diǎn)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退 出前一頁(yè)后一頁(yè)2022/9/14第21頁(yè)，共90頁(yè)，2022年，5月20日，15點(diǎn)8分，星期四一般來(lái)說(shuō)，0.618法的計(jì)算步驟如下：2022/9/14第22頁(yè)，共90頁(yè)，2022年，5月20日，15點(diǎn)8分，星期四0.618法中采用進(jìn)退算法求初始區(qū)間2022/9/14第23頁(yè)，共90頁(yè)，2022年，5月20日，15點(diǎn)8分，星期

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

32、與過(guò)去狀態(tài)X(s)（st）取值無(wú)關(guān)，或更簡(jiǎn)單的說(shuō)，己知現(xiàn)在，將來(lái)與過(guò)去無(wú)關(guān)（條件獨(dú)立），則稱(chēng)此性質(zhì)為馬爾可夫性（無(wú)后效性或簡(jiǎn)稱(chēng)馬氏性）。具有這種馬爾可夫性的過(guò)程稱(chēng)為馬爾可夫過(guò)程。 2022/9/14第62頁(yè)，共90頁(yè)，2022年，5月20日，15點(diǎn)8分，星期四+O(t)+O(t)2022/9/14第63頁(yè)，共90頁(yè)，2022年，5月20日，15點(diǎn)8分，星期四 設(shè)有某個(gè)系統(tǒng)，具有0，1，2狀態(tài)，令N（t）表示系統(tǒng)在時(shí)刻t所處的狀態(tài)（即顧客數(shù)）。在任一時(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 ），這樣的一個(gè)系統(tǒng)狀態(tài)隨時(shí)間變化的過(guò)程就稱(chēng)為一個(gè)生滅過(guò)程。生滅過(guò)程之定義2022/9/14第64頁(yè)，共90頁(yè)，2022年，5月20日，15點(diǎn)8分，星期四系統(tǒng)在t+t時(shí)刻有j個(gè)顧客，共有四種情況（這幾種情況是互斥的）：2022/9/14第65頁(yè)，共90頁(yè)，2022年，5月20日，15點(diǎn)8分，星期四若排隊(duì)系統(tǒng)的容量為無(wú)限，則在式中，令n=并去掉式即可。上面得到的哥爾莫可爾夫方程，它的解與系統(tǒng)所處的時(shí)刻有關(guān)。一般來(lái)說(shuō)，當(dāng)系統(tǒng)處于運(yùn)行的最初階段，它與系統(tǒng)的初始條件有關(guān)，但我們關(guān)心的是系統(tǒng)處于長(zhǎng)期工作的情況。可以證明，當(dāng)t時(shí)，Pj（t）

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

35、系統(tǒng)的狀態(tài)n（n個(gè)顧客，其中n-1個(gè)顧客排隊(duì)）隨時(shí)間變化的過(guò)程稱(chēng)為生滅過(guò)程，設(shè)平均到達(dá)率為,平均服務(wù)率為,負(fù)指數(shù)分布排隊(duì)系統(tǒng)（M/M/1/）的生滅過(guò)程可用下面的狀態(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 這里的稱(chēng)為服務(wù)強(qiáng)度，它刻劃了服務(wù)機(jī)構(gòu)的繁忙程度，所以又稱(chēng)服務(wù)機(jī)構(gòu)的利用率。2022/9/14第70頁(yè)，共90頁(yè)，2022年，5月20日，15點(diǎn)8分，星期四 在M/M/1/排隊(duì)系統(tǒng)中，必須有1，即單位時(shí)間內(nèi)到達(dá)服務(wù)系統(tǒng)的顧客數(shù)大于離開(kāi)服務(wù)系統(tǒng)的顧客數(shù)，那么當(dāng)t時(shí)

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

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

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

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