動態(tài)規(guī)劃和排隊論

1、1第五章 動態(tài)規(guī)劃多階段決策過程的最優(yōu)化動態(tài)規(guī)劃的基本概念和基本原理動態(tài)規(guī)劃方法的基本步驟動態(tài)規(guī)劃方法應用舉例本章內(nèi)容重點21 1、多階段決策過程的最優(yōu)化、多階段決策過程的最優(yōu)化圖5-11 運輸網(wǎng)絡圖示3多階段決策過程特點多階段決策過程特點: :要點：要點：階段，狀態(tài)，決策，狀態(tài)轉(zhuǎn)階段，狀態(tài)，決策，狀態(tài)轉(zhuǎn)移方程，移方程，k-k-后部子過程后部子過程狀態(tài)狀態(tài) x x1 1階段階段1 1T T1 1決策決策u u1 1狀態(tài)狀態(tài) x x2 2決策決策u u2 2階段階段2 2T T2 2狀態(tài)狀態(tài) x x3 3.狀態(tài)狀態(tài) x xk k決策決策u uk k階段階段k kT Tk k狀態(tài)狀態(tài) x xk+1

2、k+1.狀態(tài)狀態(tài) x xn n決策決策u un n階段階段n nTnTn狀態(tài)狀態(tài) x xn+1n+11 1、多階段決策過程的最優(yōu)化、多階段決策過程的最優(yōu)化4 2 2、動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念 一、動態(tài)規(guī)劃的基本概念一、動態(tài)規(guī)劃的基本概念 使用動態(tài)規(guī)劃方法解決多階段決策問題，首先要將實際問題寫成動態(tài)規(guī)劃模型，同時也為了今后敘述和討論方便，這里需要對動態(tài)規(guī)劃的下述一些基本術(shù)語進一步加以說明和定義： 5 2 2、動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念 ( (一一) ) 階段和階段變量階段和階段變量 為了便于求解和表示決策及過程的發(fā)展順序，而把所給問題恰當?shù)貏澐譃槿舾蓚€相互聯(lián)系又有區(qū)別的子問

3、題，稱之為多段決策問題的階段。一個階段，就是需要作出一個決策的子問題，通常，階段是按決策進行的時間或空間上先后順序劃分的用以描述階段的變量叫作階段變量，一般以k表示階段變量階段數(shù)等于多段決策過程從開始到結(jié)束所需作出決策的數(shù)目，圖51所示的最短路問題就是一個四階段決策過程6 2 2、動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念（二）狀態(tài)、狀態(tài)變量和可能狀態(tài)集（二）狀態(tài)、狀態(tài)變量和可能狀態(tài)集 1、狀態(tài)與狀態(tài)變量用以描述事物(或系統(tǒng))在某特定的時間與空間域中所處位置及運動特征的量，稱為狀態(tài)反映狀態(tài)變化的量叫作狀態(tài)變量。狀態(tài)變量必須包含在給定的階段上確定全部允許決策所需要的信息按照過程進行的先后，每個階段的狀

4、態(tài)可分為初始狀態(tài)和終止狀態(tài)，或稱輸入狀態(tài)和輸出狀態(tài)，階段k的初始狀態(tài)記作Sk，終止狀態(tài)記為Sk+1。但為了清楚起見，通常定義階段的狀態(tài)即指其初始狀態(tài)7 2 2、動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念2可能狀態(tài)集 一般狀態(tài)變量的取值有一定的范圍或允許集合，稱為可能狀態(tài)集，或可達狀態(tài)集可能狀態(tài)集實際上是關(guān)于狀態(tài)的約束條件通常可能狀態(tài)集用相應階段狀態(tài)sk的大寫字母Sk表示，skSk，可能狀態(tài)集可以是一離散取值的集合，也可以為一連續(xù)的取值區(qū)間，視具體問題而定在圖51所示的最短路問題中，第一階段狀態(tài)為V1，狀態(tài)變量s1的狀態(tài)集合S1=V1；第二階段則有三個狀態(tài)：V2,V3,V4 ,狀態(tài)變量s2的狀態(tài)集合S

5、2=V2,V3,V4 ；第三階段也有三個狀態(tài):V5,V6,V7 ，狀態(tài)變量s3的狀態(tài)集合S3=V5,V6,V7 ；第四階段則有二個狀態(tài)： V8,V9, 狀態(tài)變量s4的狀態(tài)集合S4=V8,V9 ；8 （三）決策、決策變量和允許決策集合三）決策、決策變量和允許決策集合 所謂決策就是確定系統(tǒng)過程發(fā)展的方案，決策的實質(zhì)是關(guān)于狀態(tài)的選擇，是決策者從給定階段狀態(tài)出發(fā)對下一階段狀態(tài)作出的選擇 用以描述決策變化的量稱之決策變量，和狀態(tài)變量一樣，決策變量可以用一個數(shù)，一組數(shù)或一向量來描述也可以是狀態(tài)變量的函數(shù)，記以uk= uk(sk)，表示于階段k狀態(tài)sk時的決策變量 決策變量的取值往往也有一定的允許范圍，稱之

6、允許決策集合決策變量uk(sk)的允許決策集用Uk(sk)表示, uk(sk) Uk(sk)允許決策集合實際是決策的約束條件 2 2、動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念9 （四）、策略和允許策略集合（四）、策略和允許策略集合 策略(Policy)也叫決策序列策略有全過程策略和k部子策略之分，全過程策略是指具有n個階段的全部過程，由依次進行的n個階段決策構(gòu)成的決策序列，簡稱策略，表示為p1,nu1,u2,un。從k階段到第n階段，依次進行的階段決策構(gòu)成的決策序列稱為k部子策略,表示為pk,nuk,uk+1,un ，顯然當k=1時的k部子策略就是全過程策略。 在實際問題中，由于在各個階段可供選擇

7、的決策有許多個，因此，它們的不同組合就構(gòu)成了許多可供選擇的決策序列(策略)，由它們組成的集合，稱之允許策略集合，記作P1,n ，從允許策略集中，找出具有最優(yōu)效果的策略稱為最優(yōu)策略。 2 2、動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念10（五）狀態(tài)轉(zhuǎn)移方程（五）狀態(tài)轉(zhuǎn)移方程 系統(tǒng)在階段k處于狀態(tài)sk，執(zhí)行決策uk(sk)的結(jié)果是系統(tǒng)狀態(tài)的轉(zhuǎn)移，即系統(tǒng)由階段k的初始狀態(tài)sk轉(zhuǎn)移到終止狀態(tài)sk+1 ，或者說，系統(tǒng)由k階段的狀態(tài)sk轉(zhuǎn)移到了階段k+1的狀態(tài)sk+1 ，多階段決策過程的發(fā)展就是用階段狀態(tài)的相繼演變來描述的。 對于具有無后效性的多階段決策過程,系統(tǒng)由階段k到階段k+1的狀態(tài)轉(zhuǎn)移完全由階段k的狀態(tài)

8、sk和決策uk(sk)所確定，與系統(tǒng)過去的狀態(tài)s1,s2, sk-1及其決策u1(s1), u2(s2)uk-1(sk-1)無關(guān)系統(tǒng)狀態(tài)的這種轉(zhuǎn)移，用數(shù)學公式描述即有： 2 2、動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念)(,(1kkkkksusTs(5-1)11 通常稱式(5-1)為多階段決策過程的狀態(tài)轉(zhuǎn)移方程。有些問題的狀態(tài)轉(zhuǎn)移方程不一定存在數(shù)學表達式，但是它們的狀態(tài)轉(zhuǎn)移，還是有一定規(guī)律可循的。 ( (六六) ) 指標函數(shù)指標函數(shù) 用來衡量策略或子策略或決策的效果的某種數(shù)量指標，就稱為指標函數(shù)。它是定義在全過程或各子過程或各階段上的確定數(shù)量函數(shù)。對不同問題，指標函數(shù)可以是諸如費用、成本、產(chǎn)值、利

9、潤、產(chǎn)量、耗量、距離、時間、效用，等等。例如：圖51的指標就是運費。 2 2、動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念12 (1)階段指標函數(shù)（也稱階段效應）。用gk(sk,uk)表示第k段處于sk狀態(tài)且所作決策為uk(sk)時的指標，則它就是第k段指標函數(shù)，簡記為gk 。圖5-1的gk值就是從狀態(tài)sk到狀態(tài)sk+1的距離。譬如，gk(v2,v5)=3,即v2到v5的距離為3。 (2)過程指標函數(shù)（也稱目標函數(shù)）。用Rk(sk,uk)表示第k子過程的指標函數(shù)。如圖5-1的Rk(sk,uk)表示處于第k段sk狀態(tài)且所作決策為uk時，從sk點到終點v10的距離。由此可見， Rk(sk,uk)不僅跟當前

10、狀態(tài)sk有關(guān)，還跟該子過程策略pk(sk)有關(guān)，因此它是sk和pk(sk)的函數(shù)，嚴格說來，應表示為: 2 2、動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念)(,(kkkkspsR13 不過實際應用中往往表示為Rk(sk,uk)或Rk(sk)。還跟第k子過程上各段指標函數(shù)有關(guān)，過程指標函數(shù)Rk(sk)通常是描述所實現(xiàn)的全過程或k后部子過程效果優(yōu)劣的數(shù)量指標，它是由各階段的階段指標函數(shù)gk(sk,uk)累積形成的，適于用動態(tài)規(guī)劃求解的問題的過程指標函數(shù)（即目標函數(shù)），必須具有關(guān)于階段指標的可分離形式對于部子過程的指標函數(shù)可以表示為： 式中，表示某種運算，可以是加、減、乘、除、開方等 2 2、動態(tài)規(guī)劃的基

11、本概念動態(tài)規(guī)劃的基本概念),(),(),(),(11111,nnnkkkkkknnkkkknknkusgusgusgusususRR (5-2)14 多階段決策問題中，常見的目標函數(shù)形式之一是取各階段效應之和的形式，即: (5-3) 有些問題，如系統(tǒng)可靠性問題，其目標函數(shù)是取各階段效應的連乘積形式，如： (5-4) 總之，具體問題的目標函數(shù)表達形式需要視具體問題而定。 2 2、動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念nkiiiikusgR),(nkiiiikusgR),(15 ( (七七) ) 最優(yōu)解最優(yōu)解 用fk(sk)表示第k子過程指標函數(shù) 在狀態(tài)sk下的最優(yōu)值,即 稱fk(sk)為第k子過程

12、上的最優(yōu)指標函數(shù)；與它相應的子策略稱為sk狀態(tài)下的最優(yōu)子策略，記為pk*(sk) ；而構(gòu)成該子策賂的各段決策稱為該過程上的最優(yōu)決策，記為 ；有 簡記為 2 2、動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念)(,(kkkkspsRnkspsRoptsfkkkksPpkkkKk, 2 , 1),(,()()()(,),(),(11nnkkkksususunksusususpnnkkkkkk, 2 , 1),(,),(),()(11nkuuupnkkk, 2 , 1,116 特別當k=1且s1取值唯一時，f1(s1)就是問題的最優(yōu)值，而p1*就是最優(yōu)策略。如例5.1只有唯一始點v1即s1取值唯一,故f1(s

13、1)=18就是例5.1的最優(yōu)值，而 就是例5.1的最優(yōu)策略。 但若取值不唯一,則問題的最優(yōu)值記為f0有 最優(yōu)策略即為s1=s1*狀態(tài)下的最優(yōu)策略： 我們把最優(yōu)策略和最優(yōu)值統(tǒng)稱為問題的最 優(yōu)解。 2 2、動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念,109731vvvvp)()(11111011ssfsfoptfSs,),()(211111nuusussp17 按上述定義，所謂最優(yōu)決策，按上述定義，所謂最優(yōu)決策， 是指它們在全過程上整體最優(yōu)(即所構(gòu)成的全過程策略為最優(yōu))，而不一定在各階段上單獨最優(yōu)。 ( (八八) ) 多階段決策問題的數(shù)學模型多階段決策問題的數(shù)學模型 綜上所述，適于應用動態(tài)規(guī)劃方法求解的

14、一類多階段決策問題，亦即具有無后效性的多階段決策問題的數(shù)學模型呈以下形式: 2 2、動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念), 2 , 1(nkuknkUuSsusTstsusususRRoptfkkkkkkkknnuun,2, 1),(.),(122111（5-5）18 式中“OPT”表示最優(yōu)化，視具體問題取max或min. 上述數(shù)學模型說明了對于給定的多階段決策過程，求取一個(或多個)最優(yōu)策略或最優(yōu)決策序列 ，使之既滿足式(5-5)給出的全部約束條件，又使式(5-5)所示的目標函數(shù)取得極值，并且同時指出執(zhí)行該最優(yōu)策略時，過程狀態(tài)演變序列即最優(yōu)路線 2 2、動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念

15、,21nuuu,121nnssss19 二、動態(tài)規(guī)劃的最優(yōu)化原理與基本方程二、動態(tài)規(guī)劃的最優(yōu)化原理與基本方程 1 1標號法標號法 標號法是借助網(wǎng)絡圖通過分段標號來求出最優(yōu)路線的一種簡便、直觀的方法。通常標號法采取“逆序求解”的方法來尋找問題的最優(yōu)解，即從最后階段開始，逐次向階段數(shù)小的方向推算，最終求得全局最優(yōu)解。 2 2、動態(tài)規(guī)劃的基本原理動態(tài)規(guī)劃的基本原理20下面給出標號法的一般步驟：1.從最后一段標起，該段各狀態(tài)(即各始點)到終點的距離用數(shù)字分別標在各點上方的方格內(nèi)，并用粗箭線連接各點和終點。2.向前遞推，給前一階段的各個狀態(tài)標號。每個狀態(tài)上方方格內(nèi)的數(shù)字表示該狀態(tài)到終點的最短距離。即為該

16、狀態(tài)到該階段已標號的各終點的段長，再分別加上對應終點上方的數(shù)字而取其最小者。將剛標號的點沿著最短距離所對應的已標號的點用粗箭線連接起來，表示出各剛標號的點到終點的最短路線。 2 2、動態(tài)規(guī)劃的基本原理動態(tài)規(guī)劃的基本原理21 3.逐次向前遞推，直到將第一階段的狀態(tài)(即起點)也標號，起點方格內(nèi)的數(shù)字就是起點到終點的最短距離，從起點開始連接終點的粗箭線就是最短路線。 用標號法來求解下例 例例5.25.2：下列網(wǎng)絡圖52表示某城市的局部道路分布圖。一貨運汽車從S出發(fā)，最終到達目的地E。其中Ai(i1，2，3),Bj(j1，2)和Ck(k1，2)是可供汽車選擇的途經(jīng)站點，各點連線上的數(shù)字表示兩個站點問的

17、距離。問，此汽車應走哪條路線，使所經(jīng)過的路程距離最短? 2 2、動態(tài)規(guī)劃的基本原理動態(tài)規(guī)劃的基本原理22 2 2、動態(tài)規(guī)劃的基本原理動態(tài)規(guī)劃的基本原理圖5-2 某城市的局部道路分布圖23 第一步：先考慮第四階段，即k=4，該階段共有兩個狀態(tài)：C1、C2，設f4(C1)和f4(C2)分別表示C1、C2到E的最短距離，顯然有f4(C1)=5和f4(C2)=8，邊界條件f5(E)=0 。 第二步：即k=3,該階段共有兩個狀態(tài):B1 , B2 (1) 從B1出發(fā)有兩種決策:B1C1，B1C2 。記d3(B1,C1)表示B1到C1的距離,即,這里的每一種決策的階段指標函數(shù)就是距離，所以，B1C1的階段指

18、標函數(shù)為d3(B1,C1)6，B1C2的階段指標函數(shù)為d3(B1,C2)5。因此有,f3(B1)mind3(B1,C1)+f4(C1),d3(B1,C2)+ f4(C2)min(6十5，5十8)11。那么，從出發(fā)到E的最短路線是B1C1E，對應的決策u3(B1) = C1 。 2 2、動態(tài)規(guī)劃的基本原理動態(tài)規(guī)劃的基本原理24 (2)從B2出發(fā)也有兩種決策:B2C1,B2C2同理, 有f3(B2)=mind3(B2,C1)+f4(C1),d3(B2,C2)+f4(C2)min(9+5，8+87)14，那么，從B2出發(fā)到E的最短路線是B2C1E，且u3(B2)=C1 。 第三步：即k2,該階段共有

19、三個狀態(tài):Al,A2,A3 (1)從Al出發(fā)有兩種決策：A1B1,A1B2。則f2(A1) =mind2(A1,B1)+f3(B1),d2(A1,B2)+f3(B2)min6十11，5十1417，即A1到E的最短路線為A1B1C1E，且u3(A1)B1 。 (2)從A2出發(fā)也有兩種決策:A2B1,A2B2。此時， f2(A2) mind2(A2,B1)+f3(B1),d2(A2,B2)+f3(B2) min8+11，6+1419，即A2到E的最短路線為A2B1C1E，且u3(A2)B1。 2 2、動態(tài)規(guī)劃的基本原理動態(tài)規(guī)劃的基本原理25(3)從A3出發(fā)也有兩種決策:A3B1,A3B2 此時f2

20、(A2)=mind2(A3,B1)+f3(B1),d2(A3,B2)+f3(B2) min7+11，4+1418，即A3到E的最短路線為A3B1C1E ，對應的u2(A3)B2 。第四步：即k1，該階段只有一個狀態(tài)S,從S出發(fā)有三種決策:SA1,SA2,SA3,那么,f1(S)=mind1(S,A1)+f2(A1),d2(S,B2)+f3(B2) min8+11，6+1419，即A2到E的最短路線為A2B1C1E ，且u3(A2)B1 。那么,從S到E共有三條最短路線：此時,u1(S)A1題 和此時,u1(S)A3 ，最短距離為21。 2 2、動態(tài)規(guī)劃的基本原理動態(tài)規(guī)劃的基本原理ECBAS11

21、1ECBAS113ECBAS12326 結(jié)果如圖5-3所示。 每個狀態(tài)上方的方格內(nèi)的數(shù)字表示該狀態(tài)到E的最短距離，首尾相連的粗箭線構(gòu)成每一狀態(tài)到E的最短路線。因此，標號法不但給出起點到終點的最短路線和最短距離，同時也給出每一狀態(tài)到終點的最短路線及其最短距離。如,A1到E的最短路線是 ,最短矩離是17 圖見下頁 2 2、動態(tài)規(guī)劃的基本原理動態(tài)規(guī)劃的基本原理ECBA11127 2 2、動態(tài)規(guī)劃的基本原理動態(tài)規(guī)劃的基本原理圖5-3某城市局部道路求最短路徑的過程28 2最優(yōu)化原理 （貝爾曼最優(yōu)化原理） 作為一個全過程的最優(yōu)策略具有這樣的性 質(zhì)：對于最優(yōu)策略過程中的任意狀態(tài)而言， 無論其過去的狀態(tài)和決策

22、如何，余下的諸 決策必構(gòu)成一個最優(yōu)子策略。 該原理的具體解釋是，若某一全過程最優(yōu) 策略為： 2 2、動態(tài)規(guī)劃的基本原理動態(tài)規(guī)劃的基本原理)(),(,),(),()(221111nnkksususususp 則對上述策略中所隱含的任一狀態(tài)而言， 第k子過程上對應于該狀態(tài)的最優(yōu)策略必然 包含在上述全過程最優(yōu)策略p1*中，即為)(,),(),()(11nnkkkkkksusususp29 如第一節(jié)所述，基于上述原理，提出了一 種逆序遞推法；這里可以指出，該法的關(guān) 鍵在于給出一種遞推關(guān)系。一般把這種遞 推關(guān)系稱為動態(tài)規(guī)劃的函數(shù)基本方程。 3.函數(shù)基本方程 在例5.2中，用標號法求解最短路線的計 算公式

23、可以概括寫成：(5-6) 其中， 在這里表示從狀態(tài)sk到 由決策uk(sk)所決定的狀態(tài)sk+1之間的距離。 是邊界條件，表示全過程到 第四階段終點結(jié)束。 2 2、動態(tài)規(guī)劃的基本原理動態(tài)規(guī)劃的基本原理1 , 2 , 3 , 4),()(,(min)(0)(111)(55ksufsusgsfsfkkkkkkksUukkkkk)(,(kkkksusg0)(55sf30 一般地，對于n個階段的決策過程，假設只考慮指標函數(shù)是“和”與“積”的形式，第k階段和第k+1階段間的遞推公式可表示如下： (1)當過程指標函數(shù)為下列“和”的形式時， 相應的函數(shù)基本方程為 （5.7） 2 2、動態(tài)規(guī)劃的基本原理動態(tài)規(guī)

24、劃的基本原理)(,()()(kkkksPpkkspsRoptsfkKknkiiiiusg),(1 , 2 , 1,),()(,()(0)(11111nnksufsusgoptsfsfkkkkkkkUukknnkk31 (2) 當過程指標函數(shù)為下列“積”的形式時, 相應的函數(shù)基本方程為 （5.8） 可以看出，和、積函數(shù)的基本方程中邊界 條件(即 的取值)是不同的。 2 2、動態(tài)規(guī)劃的基本原理動態(tài)規(guī)劃的基本原理)(,()()(kkkksPpkkspsRoptsfkKknkiiiiusg),(1 , 2 , 1,),()(,()(1)(11111nnksufsusgoptsfsfkkkkkkkUuk

25、knnkk)(11nnsf323 3、動態(tài)規(guī)劃方法的基本步驟、動態(tài)規(guī)劃方法的基本步驟 一動態(tài)規(guī)劃的建模一動態(tài)規(guī)劃的建模 標號法僅適用于求解象最短路線問題那樣可以用網(wǎng)絡圖表示的多階段決策問題。但不少多階段決策問題不能用網(wǎng)絡圖表示。此時,應該用函數(shù)基本方程來遞推求解.一般來說,要用函數(shù)基本方程逆推求解,首先要有效地建立動態(tài)規(guī)劃模型,然后再遞推求解,最后得出結(jié)論.然而,要把一個實際問題用動態(tài)規(guī)劃方法來求解,還必須首先根據(jù)問題的要求。把它構(gòu)造成動態(tài)規(guī)劃模型,這是非常重要的一步。正確地建立一個動態(tài)規(guī)劃模型,往往問題也就解決了一大半,而一個正確的動態(tài)規(guī)劃模型,應該滿足哪些條件呢?333 3、動態(tài)規(guī)劃方法的

26、基本步驟、動態(tài)規(guī)劃方法的基本步驟1應將實際問題恰當?shù)胤指畛蒼個子問題(n個階段)。通常是根據(jù)時間或空間而劃分的，或者在經(jīng)由靜態(tài)的數(shù)學規(guī)劃模型轉(zhuǎn)換為動態(tài)規(guī)劃模型時，常取靜態(tài)規(guī)劃中變量的個數(shù)n，即k=n。2正確地定義狀態(tài)變量sk，使它既能正確地描述過程的狀態(tài)，又能滿足無后效性動態(tài)規(guī)劃中的狀態(tài)與一般控制系統(tǒng)中和通常所說的狀態(tài)的概念是有所不同的，動態(tài)規(guī)劃中的狀態(tài)變量必須具備以下三個特征：343 3、動態(tài)規(guī)劃方法的基本步驟、動態(tài)規(guī)劃方法的基本步驟(1)要能夠正確地描述受控過程的變化特征(2)要滿足無后效性即如果在某個階段狀態(tài)已經(jīng)給定，那么在該階段以后，過程的發(fā)展不受前面各段狀態(tài)的影響，如果所選的變量不具

27、備無后效性，就不能作為狀態(tài)變量來構(gòu)造動態(tài)規(guī)劃的模型。(3)要滿足可知性即所規(guī)定的各段狀態(tài)變量的值，可以直接或間接地測算得到一般在動態(tài)規(guī)劃模型中，狀態(tài)變量大都選取那種可以進行累計的量。此外，在與靜態(tài)規(guī)劃模型的對應關(guān)系上，通常根據(jù)經(jīng)驗，線性與非線性規(guī)劃中約束條件的個數(shù)，相當于動態(tài)規(guī)劃中狀態(tài)變量sk的維數(shù)而前者約束條件所表示的內(nèi)容，常就是狀態(tài)變量sk所代表的內(nèi)容。353 3、動態(tài)規(guī)劃方法的基本步驟、動態(tài)規(guī)劃方法的基本步驟3正確地定義決策變量及各階段的允許決策集合Uk(sk)，根據(jù)經(jīng)驗，一般將問題中待求的量，選作動態(tài)規(guī)劃模型中的決策變量?；蛘咴诎鸯o態(tài)規(guī)劃模型(如線性與非線性規(guī)劃)轉(zhuǎn)換為動態(tài)規(guī)劃模型時，

28、常取前者的變量xj為后者的決策變量uk。4. 能夠正確地寫出狀態(tài)轉(zhuǎn)移方程，至少要能正確反映狀態(tài)轉(zhuǎn)移規(guī)律。如果給定第k階段狀態(tài)變量sk的值，則該段的決策變量uk一經(jīng)確定，第k+1段的狀態(tài)變量sk+1的值也就完全確定，即有sk+1=Tk(sk,uk)363 3、動態(tài)規(guī)劃方法的基本步驟、動態(tài)規(guī)劃方法的基本步驟5根據(jù)題意,正確地構(gòu)造出目標與變量的函數(shù)關(guān)系目標函數(shù)，目標函數(shù)應滿足下列性質(zhì)：(1)可分性，即對于所有k后部子過程，其目標函數(shù)僅取決于狀態(tài)sk及其以后的決策 uk,uk+1,un,就是說它是定義在全過程和所有后部子過程上的數(shù)量函數(shù)。(2)要滿足遞推關(guān)系，即(3)函數(shù) 對其變元Rk+1來說要嚴格單

29、調(diào)。nkkuuu,1),(,),(111111,nkkkkknkkkknkssRussususR),(,111nkkkkkssRus376寫出動態(tài)規(guī)劃函數(shù)基本方程例如常見的指標函數(shù)是取各段指標和的形式 其中 表示第i階段的指標，它顯然是滿足上述三個性質(zhì)的。所以上式可以寫成 ：3 3、動態(tài)規(guī)劃方法的基本步驟、動態(tài)規(guī)劃方法的基本步驟nkiiiikkusgsR),()(),(iiiusg),(),(111nkkkkkkssRusgR38 二動態(tài)規(guī)劃方法的基本步驟二動態(tài)規(guī)劃方法的基本步驟 為進一步說明動態(tài)規(guī)劃模型建立的基本方法及其求解過程,下面通過實際例子用上述方法具體給出求解動態(tài)規(guī)劃方法的基本步驟：

30、 例例5.35.3 有某種機床,可以在高低兩種不同的負荷下進行生產(chǎn),在高負荷下生產(chǎn)時,產(chǎn)品的年產(chǎn)量為g,與年初投入生產(chǎn)的機床數(shù)量u1的關(guān)系為g=g(u1)=8u1,這時,年終機床完好臺數(shù)將為au1,(a為機床完好率，0a1,設a=0.7).在低負荷下生產(chǎn)時,產(chǎn)品的年產(chǎn)量為h,和投入生產(chǎn)的機床數(shù)量u2的關(guān)系為h=h(u2)=5u2,相應的機床完好率為b(0b1,設b=0,9),一般情況下a0所以 d2(x2)=d2|13-x2d217-x2由此 f2(x2)=5(13-x2)-13x2+377 =-18x2+442, d2*=13-x2生生 產(chǎn)產(chǎn) 庫庫 存存 問問 題題111對于k=1f1(x1

31、)=minc1d1+f2(x2) d1D1(x1) =min11d1+442-18x2d1D1(x1) =min11d1+442-18(x1-r1+d1) d1D1(x1) =min11d1+442-18(x1-0+d1) d1D1(x1) =min-7d1-18x1+442 d1D1(x1)D D1 1(x(x1 1)=d)=d1 1|d|d1 1 0,r0,r2 2 x x1 1-r-r1 1+d+d1 1 HH =d =d1 1|d|d1 1 0,r0,r2 2+r+r1 1-x-x1 1 d d1 1 H+rH+r1 1-x-x1 1 =d =d1 1|d|d1 1 0,8-x0,8-

32、x1 1 d d1 1 9-x9-x1 1 生生 產(chǎn)產(chǎn) 庫庫 存存 問問 題題112根據(jù)題意 x1=2所以 D1(x1)=d1| 6d17由此 d1=7f1(x1)=-7d1-18x1+442 =-77182442 =357將以上結(jié)果總結(jié)成下表：k1234567ck11181317201015rk0853274xk2959974dk713-x2=4 14-x3=9 12-x4=3 9-x5=0 11-x6=40生生 產(chǎn)產(chǎn) 庫庫 存存 問問 題題113設設 備備 更更 新新 問問 題題114 一臺設備的價格為P，運行壽命為n年，每年的維修費用是設備役齡的函數(shù)，記為C(t)，新設備的役齡為t=0。

33、舊設備出售的價格是設備役齡的函數(shù)，記為S(t)。在n年末，役齡為t的設備殘值為R(t)?，F(xiàn)有一臺役齡為T的設備，在使用過程中，使用者每年都面臨“繼續(xù)使用”或“更新”的策略，設設 備備 更更 新新 問問 題題115階段 k：運行年份；狀態(tài)變量 xk：設備的役齡 t；決策變量 dk：dRplaceKK eepk(R e)()更 新繼 續(xù) 使 用狀態(tài)轉(zhuǎn)移方程：xdRxdKkkkk111階段指標：vP CS xdRC xdKP CS tdRC tdKkkkkkkk( )()()( )( )( )00116遞推方程： fxPCS xfxdRC xfxdKPCS tfdRC tftdKkkkkkkkkkk

34、kkkk()min( )()()()()min( )( )( )( )()0011111111 終端條件： fn(t)=-R(t) 設設 備備 更更 新新 問問 題題117例設具體數(shù)據(jù)如下：T 0 1 2 3 4 5 6 7 C(t) 10 13 20 40 70 100 100 - S(t) - 32 21 11 5 0 0 0 R(t) - 25 17 8 0 0 0 0 且 n=5，T=2，P=50 由上表開始，終端條件為： f6(1)=-25，f6(2)=-17，f6(3)=-8 f6(4)=f6(5)=f6(6)=f6(7)=0 設設 備備 更更 新新 問問 題題118 對于 k=5

35、: ftPCS tfC tftdRdK56655011( )min( )( )( )( )() fPCSfCfdK5665101112501032251317344( )min( )( )( )( )( )min()()min,* fPCSfCfdK566520212350102125208141212( )min( )( )( )( )( )min()()min,* 119fPC(SfC(fdR566530313450101125400244024( )min)( )( )( )min()min,* fPCSfCfdR56654041455010525700307030( )min( )(

36、)( )( )( )min()min,* fPCSfCfdR5665505156501002510003510035( )min( )( )( )( )( )min()min,* 120fPCSfCfdR5665606167501002510003510035( )min( )( )( )( )( )min()min,* ftPCS tfC tftdRdK45544011( )min( )( )( )( )() fPCSfCfdR4554101112501032413 12242524( )min( )( )( )( )( )min()min,* 對于 k=4:121fPCSfCfdR4554

37、20212350102142024354435( )min( )( )( )( )( )min()min,* fPCSfCfdR455430313450101144030457045( )min( )( )( )( )( )min()min,* 122 fPCSfCfdR455440414550105470355110551( )min( )( )( )( )( )min()min,* fPCSfCfdR4555505156501004100355613556( )min( )( )( )( )( )min()min,* 123 對 于k=3: f tP CStfCtf tdRdK344330

38、11( ) min( )( )( )( )() fP CSfCfdK344310111250 10 32 2413 35524848( ) min( )( )( )( )( )minmin,* 124fPCSfCfdR3443303134501011244051739173( )min( )( )( )( )( )minmin,*fPCSfCfdR344340414550 1052470567912679( )min( )( )( )( )( )minmin,* fPCSfCfdR3443202123501021242045636563( )min( )( )( )( )( )minmin,*

39、125 ftPCS tfC tftdRdK23322011( )min( )( )( )( )() fPCSfCfdKdR23322101112501032481363767676( )min( )( )( )( )( )minmin,*或者 fPCSfCfdR2332202123501021482073879387( )min( )( )( )( )( )minmin,* 對于 k=2: 126fPCSfCfdR23323031345010114840799711973( )min( )( )( )( )( )minmin,* 對 于k = 1 : ftPCS tfC tftdRdK1221

40、1011( )min( )( )( )( )()fPCSfCfdR1221202123501021762097115117115( )min( )( )( )( )( )minmin,*127由以上計算可知，本問題有兩個決策，它們對應的最小費用都是115。年份 1 2 3 4 5 決策 1 更新 更新 繼續(xù) 更新 繼續(xù) 決策 2 更新 繼續(xù) 更新 更新 繼續(xù) 這兩個決策是 設設 備備 更更 新新 問問 題題128第六章 排隊論基本概念輸入過程和服務時間分布泊松輸入指數(shù)服務排隊模型其他模型選介排隊系統(tǒng)的優(yōu)化目標與最優(yōu)化問題本章內(nèi)容重點129 排隊論(Queuing Theory)，又稱隨 機 服

41、 務 系 統(tǒng) 理 論 ( R a n d o m Service System Theory),是一門研究擁擠現(xiàn)象(排隊、等待)的科學。具體地說，它是在研究各種排隊系統(tǒng)概率規(guī)律性的基礎上，解決相應排隊系統(tǒng)的最優(yōu)設計和最優(yōu)控制問題。前前 言言130 排隊是我們在日常生活和生產(chǎn)中經(jīng)常遇到的現(xiàn)象。例如，上、下班搭乘公共汽車；顧客到商店購買物品；病員到醫(yī)院看病；旅客到售票處購買車票；學生去食堂就餐等就常常出現(xiàn)排隊和等待現(xiàn)象。除了上述有形的排隊之外，還有大量的所謂“無形”排隊現(xiàn)象，如幾個顧客打電話到出租汽車站要求派車，如果出租汽車站無足夠車輛、則部分顧客只得在各自的要車處等待，他們分散在不同地方，卻形成

42、了一個無形隊列在等待派車。排隊的不一定是人，也可以是物：前前 言言131 例如，通訊衛(wèi)星與地面若干待傳遞的信息；生產(chǎn)線上的原料、半成品等待加工；因故障停止運轉(zhuǎn)的機器等待工人修理；碼頭的船只等待裝卸貨物；要降落的飛機因跑道不空而在空中盤旋等等。前前 言言132 顯然，上述各種問題雖互不相同，但卻都有要求得到某種服務的人或物和提供服務的人或機構(gòu)。排隊論里把要求服務的對象統(tǒng)稱為“顧客”,而把提供服務的人或機構(gòu)稱為“服務臺”或“服務員”。不同的顧客與服務組成了各式各樣的服務系統(tǒng)。顧客為了得到某種服務而到達系統(tǒng)、若不能立即獲得服務而又允許排隊等待，則加入等待隊伍，待獲得服務后離開系統(tǒng)，見圖61至圖65。

43、前前 言言133 類似地還可畫出許多其它更復雜形式的排隊系統(tǒng)，如串并混聯(lián)的系統(tǒng)，網(wǎng)絡排隊系統(tǒng)等。盡管各種排隊系統(tǒng)的具體形式不同，但都可由圖66加以描述。圖61 單服務臺排隊系統(tǒng)前前 言言134圖62 單隊列S個服務臺并聯(lián)的排隊系統(tǒng)圖6-3 S個隊列S個服務臺的并聯(lián)排隊系統(tǒng)前前 言言135圖64 單隊多個服務臺的串聯(lián)排隊系統(tǒng) 圖65 多隊多服務臺混聯(lián)、網(wǎng)絡系統(tǒng)前前 言言136圖66 隨機服務系統(tǒng)前前 言言137 通常稱由圖66表示的系統(tǒng)為一隨機聚散服務系統(tǒng)，任排隊系統(tǒng)都是一個隨機聚散服務系統(tǒng)。這里，“聚”表示顧客的到達，“散”表示顧客的離去，所謂隨機性則是排隊系統(tǒng)的一個普遍特點，是指顧客的到達情

44、況(如相繼到達時間間隔)與每個顧客接受服務的時間往往是事先無法確切知道的，或者說是隨機的。一般來說，排隊論所研究的排隊系統(tǒng)中，顧客到來的時刻和服務臺提供服務的時間長短都是隨機的，因此這樣的服務系統(tǒng)被稱為隨機服務系統(tǒng)。前前 言言138 面對擁擠現(xiàn)象，人們總是希望盡量設法減少排隊，通常的做法是增加服務設施，但是增加的數(shù)量越多，人力、物力的支出就越大，甚至會出現(xiàn)空閑浪費，如果服務設施太少，顧客排隊等待的時間就會很長，這樣對顧客會帶來不良影響。于是，顧客排隊時間的長短與服務設施規(guī)模的大小，就構(gòu)成了設計隨機服務系統(tǒng)中的一對矛盾。如何做到既保證一定的服務質(zhì)量指標，又使服務設施費用經(jīng)濟合理，恰當?shù)亟鉀Q顧客排

45、隊時間與服務設施費用大小這對矛盾，這就是隨機服務系統(tǒng)理論排隊論所要研究解決的問題。前前 言言139 排隊論是1909年由丹麥工程師愛爾朗(A.KErlang)在研究電活系統(tǒng)時創(chuàng)立的，幾十年來排隊論的應用領(lǐng)域越來越廣泛，理論也日漸完善。特別是自二十世紀60年代以來，由于計算機的飛速發(fā)展，更為排隊論的應用開拓了寬闊的前景。前前 言言1401 1、基、基 本本 概概 念念 一 排隊系統(tǒng)的描述 （一）、系統(tǒng)特征和基本排隊過程 實際的排隊系統(tǒng)雖然千差萬別，但是它們有以下的共同特征： (1)有請求服務的人或物顧客； (2)有為顧客服務的人或物，即服務員或服務臺； (3)顧客到達系統(tǒng)的時刻是隨機的，為每一位

46、顧客提供服務的時間是隨機的，因而整個排隊系統(tǒng)的狀態(tài)也是隨機的。排隊系統(tǒng)的這種隨機性造成某個階段顧客排隊較長，而另外一些時候服務員(臺)又空閑無事。141 任何一個排隊問題的基本排隊過程都可以用圖6-6表示。從圖6-6可知，每個顧客由顧客源按一定方式到達服務系統(tǒng)，首先加入隊列排隊等待接受服務，然后服務臺按一定規(guī)則從隊列中選擇顧客進行服務，獲得服務的顧客立即離開。1 1、基、基 本本 概概 念念142 （二）、排隊系統(tǒng)的基本組成部分 通常，排隊系統(tǒng)都有輸入過程、服務規(guī)則和服務臺等3個組成部分： 1輸入過程這是指要求服務的顧客是按怎樣的規(guī)律到達排隊系統(tǒng)的過程，有時也把它稱為顧客流一般可以從3個方面來

47、描述個輸入過程。 (1)顧客總體數(shù)，又稱顧客源、輸入源。這是指顧客的來源。顧客源可以是有限的，也可以是無限的。例如，到售票處購票的顧客總數(shù)可以認為是無限的，而某個工廠因故障待修的機床則是有限的。1 1、基、基 本本 概概 念念143 (2)顧客到達方式。這是描述顧客是怎樣來到系統(tǒng)的，他們是單個到達，還是成批到達。病人到醫(yī)院看病是顧客單個到達的例子。在庫存問題中如將生產(chǎn)器材進貨或產(chǎn)品入庫看作是顧客，那么這種顧客則是成批到達的。 (3)顧客流的概率分布，或稱相繼顧客到達的時間間隔的分布。這是求解排隊系統(tǒng)有關(guān)運行指標問題時，首先需要確定的指標。這也可以理解為在一定的時間間隔內(nèi)到達K個顧客(K=1、2

48、、)的概率是多大。顧客流的概率分布一般有定長分布、二項分布、泊松流(最簡單流)、愛爾朗分布等若干種。1 1、基、基 本本 概概 念念144 2.服務規(guī)則這是指服務臺從隊列中選取顧客進行服務的順序。一般可以分為損失制、等待制和混合制等3大類。 (1)損失制。這是指如果顧客到達排隊系統(tǒng)時，所有服務臺都已被先來的顧客占用，那么他們就自動離開系統(tǒng)永不再來。典型例子是，如電話拔號后出現(xiàn)忙音，顧客不愿等待而自動掛斷電話，如要再打，就需重新拔號，這種服務規(guī)則即為損失制。1 1、基、基 本本 概概 念念145 (2)等待制。這是指當顧客來到系統(tǒng)時，所有服務臺都不空，顧客加入排隊行列等待服務。例如，排隊等待售票

49、，故障設備等待維修等。等待制中，服務臺在選擇顧客進行服務時，常有如下四種規(guī)則： 先到先服務。按顧客到達的先后順序?qū)︻櫩瓦M行服務，這是最普遍的情形； 后到先服務。倉庫中迭放的鋼材，后迭放上去的都先被領(lǐng)走，就屬于這種情況；1 1、基、基 本本 概概 念念146 隨機服務。即當服務臺空閑時，不按照排隊序列而隨意指定某個顧客去接受服務，如電話交換臺接通呼叫電話就是一例； 優(yōu)先權(quán)服務。如老人、兒童先進車站；危重病員先就診；遇到重要數(shù)據(jù)需要處理計算機立即中斷其他數(shù)據(jù)的處理等，均屬于此種服務規(guī)則。1 1、基、基 本本 概概 念念147 (3)混合制這是等待制與損失制相結(jié)合的一種服務規(guī)則，一般是指允許排隊，但

50、又不允許隊列無限長下去。具體說來，大致有三種： 隊長有限。當排隊等待服務的顧客人數(shù)超過規(guī)定數(shù)量時，后來的顧客就自動離去，另求服務，即系統(tǒng)的等待空間是有限的。例如最多只能容納K個顧客在系統(tǒng)中，當新顧客到達時，若系統(tǒng)中的顧客數(shù)(又稱為隊長)小于K，則可進入系統(tǒng)排隊或接受服務；否則，便離開系統(tǒng)，并不再回來。如水庫的庫容是有限的，旅館的床位是有限的。1 1、基、基 本本 概概 念念148 等待時間有限。即顧客在系統(tǒng)中的等待時間不超過某一給定的長度T，當?shù)却龝r間超過T時，顧客將自動離去，并不再回來。如易損壞的電子元器件的庫存問題，超過一定存儲時間的元器件被自動認為失效。又如顧客到飯館就餐，等了一定時間后

51、不愿再等而自動離去另找飯店用餐。 1 1、基、基 本本 概概 念念149 逗留時間(等待時間與服務時間之和)有限。例如用高射炮射擊敵機，當敵機飛越高射炮射擊有效區(qū)域的時間為t時，若在這個時間內(nèi)未被擊落，也就不可能再被擊落了。 不難注意到，損失制和等待制可看成是混合制的特殊情形，如記s為系統(tǒng)中服務臺的個數(shù)，則當K=s時，混合制即成為損失制；當K=時，混合制即成為等待制.1 1、基、基 本本 概概 念念150 3服務臺情況服務臺可以從以下3方面來描述： (1) 服務臺數(shù)量及構(gòu)成形式。從數(shù)量上說，服務臺有單服務臺和多服務臺之分。從構(gòu)成形式上看，服務臺有：a)單隊單服務臺式，b)單隊多服務臺并聯(lián)式，c

52、)多隊多服務臺并聯(lián)式，d)單隊多服務臺串聯(lián)式，e)單隊多服務臺并串聯(lián)混合式以及多隊多服務臺并串聯(lián)混合式等等。見圖6-1至圖6-5所示。 1 1、基、基 本本 概概 念念151 (2) 服務方式。這是指在某一時刻接受服務的顧客數(shù)，它有單個服務和成批服務兩種。如公共汽車一次就可裝載一批乘客就屬于成批服務。 (3) 服務時間的分布。一般來說，在多數(shù)情況下，對每一個顧客的服務時間是一隨機變量，其概率分布、有定長分布、負指數(shù)分布、K級愛爾良分布、一般分布(所有顧客的服務時間都是獨立同分布的)等等。1 1、基、基 本本 概概 念念152 （三）、排隊系統(tǒng)的描述符號與分類 為了區(qū)別各種排隊系統(tǒng)，根據(jù)輸入過程

53、、排隊規(guī)則和服務機制的變化對排隊模型進行描述或分類，可給出很多排隊模型。為了方便對眾多模型的描述，肯道爾（DGKendall）提出了一種目前在排隊論中被廣泛采用的“Kendall記號”，完整的表達方式通常用到6個符號并取如下固定格式：/各符號的意義為：1 1、基、基 本本 概概 念念153表示顧客相繼到達間隔時間分布，常用下列符號：M表示到達過程為泊松過程或負指數(shù)分布；D表示定長輸入；Ek表示k階愛爾朗分布；G表示一般相互獨立的隨機分布；表示服務時間分布，所用符號與表示顧客到達間隔時間分布相同。M表示服務過程為泊松過程或負指數(shù)分布；D表示定長分布；Ek 表示k階愛爾朗分布；G表示一般相互獨立的

54、隨機分布；1 1、基、基 本本 概概 念念154表示服務臺(員)個數(shù)：“1”則表示單個服務臺，“s”。(s1)表示多個服務臺。表示系統(tǒng)中顧客容量限額，或稱等待空間容量；如系統(tǒng)有K個等待位子，則 0K0為一常數(shù)，表示單位時間內(nèi)到達顧客的平均數(shù)，又稱為顧客的平均到達率。 對于泊松流，不難證明其相繼顧客到達時間間隔i，i=1,2,是相互獨立同分布的，其分布函數(shù)為負指數(shù)分布： （6-6）!)()(KtetVKtk, 2 , 1 , 0K（6-5） 0, 00,1)(ttetFti), 2 , 1(i2 2、輸入過程和服務時間分布、輸入過程和服務時間分布1723.愛爾朗輸入. 這是指相繼顧客到達時間間隔

55、相互獨立，具有相同的分布，其分布密度為 （6-7） 其中k為非負整數(shù)。 可以證明，在參數(shù)為的泊松輸人中，對任意的j與k,設第j與第j+k個顧客之間的到達間隔為 。則隨機變量Tk的分布必遵從參數(shù)為的愛爾朗分布，其分布密度為：0)!1()()(1teKttatK)(21kkkTT2 2、輸入過程和服務時間分布、輸入過程和服務時間分布173 例某排隊系統(tǒng)有并聯(lián)的k個服務臺，顧 客流為泊松流，規(guī)定第i,K+i,2K+i,個顧客排入第i號臺(i=1,2,K)，則第K臺所獲得的顧客流，即為愛爾朗輸入流，其他各臺，從它的第一個顧客到達以后開始所獲得的流也為愛爾朗輸入流。 此外，愛爾朗分布中，當K1時將化為負

56、指數(shù)分布。0)!1()()(1teKttatK2 2、輸入過程和服務時間分布、輸入過程和服務時間分布1744.一般獨立輸入，即相繼顧客到達時間間隔相互獨立、同分布，分布函數(shù)F(t)是任意分布，因此，上面所述的所有輸入都是一般獨立分布的特例。5.成批到達的輸入這時指排隊系統(tǒng)每次到達的顧客不一定是一個，而可能是一批，每批顧客的數(shù)目n是一個隨機變量。其分布為： 到達時間間隔可能是上述幾類輸入中的一種。2 2、輸入過程和服務時間分布、輸入過程和服務時間分布（6-8）kaknP , 2 , 1 , 0K175 二、服務時間分布 1定長分布每一個顧客的服務時間 都是常數(shù)，此時服務時間t的分布函數(shù) 為： （

57、6-9） 2負指數(shù)分布即各個顧客的服務時間相互獨立，具有相同的負指數(shù)分布： (6-10) 其中0為一常數(shù)，服務時間t的數(shù)學期望稱為平均服務時間。顯然，對于負指數(shù)分布2 2、輸入過程和服務時間分布、輸入過程和服務時間分布xxxtPxB01)()(0,00,1)(xxexBx176 3.愛爾朗分布. 即每個顧客的服務時間相互獨立，具有相同的愛爾朗分布。其密度函數(shù)為 其中0為一常數(shù)，此種的平均服務時間為： K=1時愛爾朗分布化歸為負指數(shù)分布當K時，得到長度為1/的定長服務。2 2、輸入過程和服務時間分布、輸入過程和服務時間分布001)()(dxxexxdBtEmx(6-11)(6-12)0,)!1(

58、)()(1xekxkkxbxkk01)()(dxxxbtE(6-13)177 4.一般服務分布所有顧客的服務時間都是相互獨立具有相同分布的隨機變量，其分布函數(shù)記B(X)，前面所述的各種服務分布都是一般服務分布的特例。 5.多個服務臺的服務分布可以假定各個服務臺的服務分布參數(shù)不同或分布類型不同。 6.服務時間依賴于隊長的情況指服務員排隊的人愈多，服務的速度也就愈快。2 2、輸入過程和服務時間分布、輸入過程和服務時間分布178 三、排隊論研究的基本問題 排隊論研究的首要問題是排隊系統(tǒng)主要數(shù)量指標的概率規(guī)律，即研究系統(tǒng)的整體性質(zhì)，然后進一步研究系統(tǒng)的優(yōu)化問題。與這兩個問題相關(guān)的還包括排隊系統(tǒng)的統(tǒng)計推

59、斷問題。(1)通過研究主要數(shù)量指標在瞬時或平穩(wěn)狀態(tài)下的概率分布及其數(shù)字特征，了解系統(tǒng)運行的基本特征。(2)統(tǒng)計推斷問題，建立適當?shù)呐抨犇Ｐ褪桥抨犝撗芯康牡谝徊?，建立模型過程中經(jīng)常會碰到如下問題：檢驗系統(tǒng)是否達到平穩(wěn)狀態(tài)；檢驗顧客相繼到達時間間隔的相互獨立性；確定服務時間的分布及有關(guān)參數(shù)等。2 2、輸入過程和服務時間分布、輸入過程和服務時間分布179(3)系統(tǒng)優(yōu)化問題，又稱為系統(tǒng)控制問題或系統(tǒng)運營問題，其基本目的是使系統(tǒng)處于最優(yōu)或最合理的狀態(tài)。系統(tǒng)優(yōu)化問題包括最優(yōu)設計問題和最優(yōu)運營問題，其內(nèi)容很多，有最少費用問題、服務率的控制問題、服務臺的開關(guān)策略、顧客(或服務)根據(jù)優(yōu)先權(quán)的最優(yōu)排序等方面的問題

60、。 對于一般的排隊系統(tǒng)運行情況的分析，通常是在給定輸入與服務條件下，通過求解系統(tǒng)狀態(tài)為n(有n個顧客)的概率Pn(t)，再進行計算其主要的運行指標:： 2 2、輸入過程和服務時間分布、輸入過程和服務時間分布180 (1)系統(tǒng)中顧客數(shù)(隊長)的期望值L；(2)排隊等待的顧客數(shù)(排隊長)的期望值Lq；(3)顧客在系統(tǒng)中全部時間(逗留時間)的期望值W；(4)顧客排隊等待時間的期望值Wq。 排隊系統(tǒng)中，由于顧客到達分布和服務時間分布是多種多樣的，加之服務臺數(shù)。顧客源有限無限，排隊容量有限無限等的不同組合，就會有不勝枚舉的不同排隊模型，若對所有排隊模型都進行分析與計算，不但十分繁雜而且也沒有必要。下面擬