第五章動態(tài)規(guī)劃多階段決策過程的最優(yōu)化動態(tài)規(guī)劃的基本概念和基本原理動態(tài)規(guī)劃方法的基本步驟動態(tài)規(guī)劃方法應用舉例本章內容重點11、多階段決策過程的最優(yōu)化圖5-11運輸網絡圖示2多階段決策過程特點:要點：階段，狀態(tài)，決策，狀態(tài)轉移方程，k-后部子過程狀態(tài)

x1階段1T1決策u1狀態(tài)

x2決策u2階段2T2狀態(tài)

x3...狀態(tài)

xk決策uk階段kTk狀態(tài)

xk+1...狀態(tài)

xn決策un階段nTn狀態(tài)

xn+11、多階段決策過程的最優(yōu)化32、動態(tài)規(guī)劃的基本概念

一、動態(tài)規(guī)劃的基本概念使用動態(tài)規(guī)劃方法解決多階段決策問題，首先要將實際問題寫成動態(tài)規(guī)劃模型，同時也為了今后敘述和討論方便，這里需要對動態(tài)規(guī)劃的下述一些基本術語進一步加以說明和定義：42、動態(tài)規(guī)劃的基本概念(一)階段和階段變量為了便于求解和表示決策及過程的發(fā)展順序，而把所給問題恰當地劃分為若干個相互聯(lián)系又有區(qū)別的子問題，稱之為多段決策問題的階段。一個階段，就是需要作出一個決策的子問題，通常，階段是按決策進行的時間或空間上先后順序劃分的．用以描述階段的變量叫作階段變量，一般以k表示階段變量．階段數等于多段決策過程從開始到結束所需作出決策的數目，圖5—1所示的最短路問題就是一個四階段決策過程．52、動態(tài)規(guī)劃的基本概念

（二）狀態(tài)、狀態(tài)變量和可能狀態(tài)集1、狀態(tài)與狀態(tài)變量．用以描述事物(或系統(tǒng))在某特定的時間與空間域中所處位置及運動特征的量，稱為狀態(tài)．反映狀態(tài)變化的量叫作狀態(tài)變量。狀態(tài)變量必須包含在給定的階段上確定全部允許決策所需要的信息．按照過程進行的先后，每個階段的狀態(tài)可分為初始狀態(tài)和終止狀態(tài)，或稱輸入狀態(tài)和輸出狀態(tài)，階段k的初始狀態(tài)記作Sk，終止狀態(tài)記為Sk+1。但為了清楚起見，通常定義階段的狀態(tài)即指其初始狀態(tài)．62、動態(tài)規(guī)劃的基本概念

2．可能狀態(tài)集一般狀態(tài)變量的取值有一定的范圍或允許集合，稱為可能狀態(tài)集，或可達狀態(tài)集．可能狀態(tài)集實際上是關于狀態(tài)的約束條件．通?？赡軤顟B(tài)集用相應階段狀態(tài)sk的大寫字母Sk表示，sk∈Sk，可能狀態(tài)集可以是一離散取值的集合，也可以為一連續(xù)的取值區(qū)間，視具體問題而定．在圖5—1所示的最短路問題中，第一階段狀態(tài)為V1，狀態(tài)變量s1的狀態(tài)集合S1={V1}；第二階段則有三個狀態(tài)：V2,V3,V4,狀態(tài)變量s2的狀態(tài)集合S2={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}

；7（三）決策、決策變量和允許決策集合所謂決策就是確定系統(tǒng)過程發(fā)展的方案，決策的實質是關于狀態(tài)的選擇，是決策者從給定階段狀態(tài)出發(fā)對下一階段狀態(tài)作出的選擇．用以描述決策變化的量稱之決策變量，和狀態(tài)變量一樣，決策變量可以用一個數，一組數或一向量來描述．也可以是狀態(tài)變量的函數，記以uk=uk(sk)，表示于階段k狀態(tài)sk時的決策變量．決策變量的取值往往也有一定的允許范圍，稱之允許決策集合．決策變量uk(sk)的允許決策集用Uk(sk)表示,uk(sk)∈Uk(sk)允許決策集合實際是決策的約束條件．2、動態(tài)規(guī)劃的基本概念

8

（四）、策略和允許策略集合策略(Policy)也叫決策序列．策略有全過程策略和k部子策略之分，全過程策略是指具有n個階段的全部過程，由依次進行的n個階段決策構成的決策序列，簡稱策略，表示為p1,n{u1,u2,…,un}。從k階段到第n階段，依次進行的階段決策構成的決策序列稱為k部子策略,表示為pk,n{uk,uk+1,…,un}，顯然當k=1時的k部子策略就是全過程策略。在實際問題中，由于在各個階段可供選擇的決策有許多個，因此，它們的不同組合就構成了許多可供選擇的決策序列(策略)，由它們組成的集合，稱之允許策略集合，記作P1,n，從允許策略集中，找出具有最優(yōu)效果的策略稱為最優(yōu)策略。2、動態(tài)規(guī)劃的基本概念

9（五）狀態(tài)轉移方程系統(tǒng)在階段k處于狀態(tài)sk，執(zhí)行決策uk(sk)的結果是系統(tǒng)狀態(tài)的轉移，即系統(tǒng)由階段k的初始狀態(tài)sk轉移到終止狀態(tài)sk+1，或者說，系統(tǒng)由k階段的狀態(tài)sk轉移到了階段k+1的狀態(tài)sk+1，多階段決策過程的發(fā)展就是用階段狀態(tài)的相繼演變來描述的。對于具有無后效性的多階段決策過程,系統(tǒng)由階段k到階段k+1的狀態(tài)轉移完全由階段k的狀態(tài)sk和決策uk(sk)所確定，與系統(tǒng)過去的狀態(tài)s1,s2,…sk-1及其決策u1(s1),u2(s2)…uk-1(sk-1)無關．系統(tǒng)狀態(tài)的這種轉移，用數學公式描述即有：2、動態(tài)規(guī)劃的基本概念

(5-1)10通常稱式(5-1)為多階段決策過程的狀態(tài)轉移方程。有些問題的狀態(tài)轉移方程不一定存在數學表達式，但是它們的狀態(tài)轉移，還是有一定規(guī)律可循的。(六)指標函數用來衡量策略或子策略或決策的效果的某種數量指標，就稱為指標函數。它是定義在全過程或各子過程或各階段上的確定數量函數。對不同問題，指標函數可以是諸如費用、成本、產值、利潤、產量、耗量、距離、時間、效用，等等。例如：圖5—1的指標就是運費。2、動態(tài)規(guī)劃的基本概念

11(1)階段指標函數（也稱階段效應）。用gk(sk,uk)表示第k段處于sk狀態(tài)且所作決策為uk(sk)時的指標，則它就是第k段指標函數，簡記為gk。圖5-1的gk值就是從狀態(tài)sk到狀態(tài)sk+1的距離。譬如，gk(v2,v5)=3,即v2到v5的距離為3。(2)過程指標函數（也稱目標函數）。用Rk(sk,uk)表示第k子過程的指標函數。如圖5-1的Rk(sk,uk)表示處于第k段sk狀態(tài)且所作決策為uk時，從sk點到終點v10的距離。由此可見，Rk(sk,uk)不僅跟當前狀態(tài)sk有關，還跟該子過程策略pk(sk)有關，因此它是sk和pk(sk)的函數，嚴格說來，應表示為:2、動態(tài)規(guī)劃的基本概念

12不過實際應用中往往表示為Rk(sk,uk)或Rk(sk)。還跟第k子過程上各段指標函數有關，過程指標函數Rk(sk)通常是描述所實現(xiàn)的全過程或k后部子過程效果優(yōu)劣的數量指標，它是由各階段的階段指標函數gk(sk,uk)累積形成的，適于用動態(tài)規(guī)劃求解的問題的過程指標函數（即目標函數），必須具有關于階段指標的可分離形式．對于部子過程的指標函數可以表示為：式中，

表示某種運算，可以是加、減、乘、除、開方等．2、動態(tài)規(guī)劃的基本概念

(5-2)13多階段決策問題中，常見的目標函數形式之一是取各階段效應之和的形式，即:

(5-3)有些問題，如系統(tǒng)可靠性問題，其目標函數是取各階段效應的連乘積形式，如：

(5-4)總之，具體問題的目標函數表達形式需要視具體問題而定。2、動態(tài)規(guī)劃的基本概念

14

(七)最優(yōu)解用fk(sk)表示第k子過程指標函數在狀態(tài)sk下的最優(yōu)值,即

稱fk(sk)為第k子過程上的最優(yōu)指標函數；與它相應的子策略稱為sk狀態(tài)下的最優(yōu)子策略，記為pk*(sk)；而構成該子策賂的各段決策稱為該過程上的最優(yōu)決策，記為；有簡記為2、動態(tài)規(guī)劃的基本概念

15特別當k=1且s1取值唯一時，f1(s1)就是問題的最優(yōu)值，而p1*就是最優(yōu)策略。如例5.1只有唯一始點v1即s1取值唯一,故f1(s1)=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、動態(tài)規(guī)劃的基本概念16按上述定義，所謂最優(yōu)決策，是指它們在全過程上整體最優(yōu)(即所構成的全過程策略為最優(yōu))，而不一定在各階段上單獨最優(yōu)。(八)多階段決策問題的數學模型綜上所述，適于應用動態(tài)規(guī)劃方法求解的一類多階段決策問題，亦即具有無后效性的多階段決策問題的數學模型呈以下形式:2、動態(tài)規(guī)劃的基本概念

（5-5）17式中“OPT”表示最優(yōu)化，視具體問題取max或min.

上述數學模型說明了對于給定的多階段決策過程，求取一個(或多個)最優(yōu)策略或最優(yōu)決策序列，使之既滿足式(5-5)給出的全部約束條件，又使式(5-5)所示的目標函數取得極值，并且同時指出執(zhí)行該最優(yōu)策略時，過程狀態(tài)演變序列即最優(yōu)路線2、動態(tài)規(guī)劃的基本概念18二、動態(tài)規(guī)劃的最優(yōu)化原理與基本方程

1．標號法標號法是借助網絡圖通過分段標號來求出最優(yōu)路線的一種簡便、直觀的方法。通常標號法采取“逆序求解”的方法來尋找問題的最優(yōu)解，即從最后階段開始，逐次向階段數小的方向推算，最終求得全局最優(yōu)解。2、動態(tài)規(guī)劃的基本原理

19下面給出標號法的一般步驟：1.從最后一段標起，該段各狀態(tài)(即各始點)到終點的距離用數字分別標在各點上方的方格內，并用粗箭線連接各點和終點。2.向前遞推，給前一階段的各個狀態(tài)標號。每個狀態(tài)上方方格內的數字表示該狀態(tài)到終點的最短距離。即為該狀態(tài)到該階段已標號的各終點的段長，再分別加上對應終點上方的數字而取其最小者。將剛標號的點沿著最短距離所對應的已標號的點用粗箭線連接起來，表示出各剛標號的點到終點的最短路線。2、動態(tài)規(guī)劃的基本原理203.逐次向前遞推，直到將第一階段的狀態(tài)(即起點)也標號，起點方格內的數字就是起點到終點的最短距離，從起點開始連接終點的粗箭線就是最短路線。用標號法來求解下例例5.2：下列網絡圖5—2表示某城市的局部道路分布圖。一貨運汽車從S出發(fā)，最終到達目的地E。其中Ai(i＝1，2，3),Bj(j＝1，2)和Ck(k＝1，2)是可供汽車選擇的途經站點，各點連線上的數字表示兩個站點問的距離。問，此汽車應走哪條路線，使所經過的路程距離最短?

2、動態(tài)規(guī)劃的基本原理212、動態(tài)規(guī)劃的基本原理圖5-2某城市的局部道路分布圖22第一步：先考慮第四階段，即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ā)有兩種決策:B1→C1，B1→C2。記d3(B1,C1)表示B1到C1的距離,即,這里的每一種決策的階段指標函數就是距離，所以，B1→C1的階段指標函數為d3(B1,C1)＝6，B1→C2的階段指標函數為d3(B1,C2)＝5。因此有,f3(B1)＝min{d3(B1,C1)+f4(C1),d3(B1,C2)+f4(C2)}＝min(6十5，5十8)＝11。那么，從出發(fā)到E的最短路線是B1→C1→E，對應的決策u3(B1)=C1。2、動態(tài)規(guī)劃的基本原理23(2)從B2出發(fā)也有兩種決策:B2→C1,B2→C2同理,有f3(B2)=min{d3(B2,C1)+f4(C1),d3(B2,C2)+f4(C2)}＝min(9+5，8+87)＝14，那么，從B2出發(fā)到E的最短路線是B2→C1→E，且u3(B2)=C1。

第三步：即k＝2,該階段共有三個狀態(tài):Al,A2,A3(1)從Al出發(fā)有兩種決策：A1→B1,A1→B2。則f2(A1)=min{d2(A1,B1)+f3(B1),d2(A1,B2)+f3(B2)}＝min{6十11，5十14}＝17，即A1到E的最短路線為A1→B1→C1→E，且u3(A1)＝B1。(2)從A2出發(fā)也有兩種決策:A2→B1,A2→B2。此時，f2(A2)＝min{d2(A2,B1)+f3(B1),d2(A2,B2)+f3(B2)}＝min{8+11，6+14}＝19，即A2到E的最短路線為A2→B1→C1→E，且u3(A2)＝B1。2、動態(tài)規(guī)劃的基本原理24(3)從A3出發(fā)也有兩種決策:A3→B1,A3→B2

此時f2(A2)=min{d2(A3,B1)+f3(B1),d2(A3,B2)+f3(B2)}＝min{7+11，4+14}＝18，即A3到E的最短路線為A3→B1→C1→E，對應的u2(A3)＝B2。第四步：即k＝1，該階段只有一個狀態(tài)S,從S出發(fā)有三種決策:S→A1,S→A2,S→A3,那么,f1(S)=min{d1(S,A1)+f2(A1),d2(S,B2)+f3(B2)}＝min{8+11，6+14}＝19，即A2到E的最短路線為A2→B1→C1→E，且u3(A2)＝B1。那么,從S到E共有三條最短路線：此時,u1(S)＝A1題和此時,u1(S)＝A3，最短距離為21。2、動態(tài)規(guī)劃的基本原理25結果如圖5-3所示。每個狀態(tài)上方的方格內的數字表示該狀態(tài)到E的最短距離，首尾相連的粗箭線構成每一狀態(tài)到E的最短路線。因此，標號法不但給出起點到終點的最短路線和最短距離，同時也給出每一狀態(tài)到終點的最短路線及其最短距離。如,A1到E的最短路線是,最短矩離是17圖見下頁2、動態(tài)規(guī)劃的基本原理262、動態(tài)規(guī)劃的基本原理圖5-3某城市局部道路求最短路徑的過程272．最優(yōu)化原理（貝爾曼最優(yōu)化原理）作為一個全過程的最優(yōu)策略具有這樣的性質：對于最優(yōu)策略過程中的任意狀態(tài)而言，無論其過去的狀態(tài)和決策如何，余下的諸決策必構成一個最優(yōu)子策略。該原理的具體解釋是，若某一全過程最優(yōu)策略為：2、動態(tài)規(guī)劃的基本原理則對上述策略中所隱含的任一狀態(tài)而言，第k子過程上對應于該狀態(tài)的最優(yōu)策略必然包含在上述全過程最優(yōu)策略p1*中，即為28如第一節(jié)所述，基于上述原理，提出了一種逆序遞推法；這里可以指出，該法的關鍵在于給出一種遞推關系。一般把這種遞推關系稱為動態(tài)規(guī)劃的函數基本方程。3.函數基本方程在例5.2中，用標號法求解最短路線的計算公式可以概括寫成：(5-6)其中，在這里表示從狀態(tài)sk到由決策uk(sk)所決定的狀態(tài)sk+1之間的距離。是邊界條件，表示全過程到第四階段終點結束。2、動態(tài)規(guī)劃的基本原理29一般地，對于n個階段的決策過程，假設只考慮指標函數是“和”與“積”的形式，第k階段和第k+1階段間的遞推公式可表示如下：(1)當過程指標函數為下列“和”的形式時，

相應的函數基本方程為

（5.7）2、動態(tài)規(guī)劃的基本原理30(2)當過程指標函數為下列“積”的形式時,相應的函數基本方程為

（5.8）可以看出，和、積函數的基本方程中邊界條件(即的取值)是不同的。2、動態(tài)規(guī)劃的基本原理313、動態(tài)規(guī)劃方法的基本步驟

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

1．應將實際問題恰當地分割成n個子問題(n個階段)。通常是根據時間或空間而劃分的，或者在經由靜態(tài)的數學規(guī)劃模型轉換為動態(tài)規(guī)劃模型時，常取靜態(tài)規(guī)劃中變量的個數n，即k=n。2．正確地定義狀態(tài)變量sk，使它既能正確地描述過程的狀態(tài)，又能滿足無后效性．動態(tài)規(guī)劃中的狀態(tài)與一般控制系統(tǒng)中和通常所說的狀態(tài)的概念是有所不同的，動態(tài)規(guī)劃中的狀態(tài)變量必須具備以下三個特征：333、動態(tài)規(guī)劃方法的基本步驟

(1)要能夠正確地描述受控過程的變化特征．(2)要滿足無后效性．即如果在某個階段狀態(tài)已經給定，那么在該階段以后，過程的發(fā)展不受前面各段狀態(tài)的影響，如果所選的變量不具備無后效性，就不能作為狀態(tài)變量來構造動態(tài)規(guī)劃的模型。(3)要滿足可知性．即所規(guī)定的各段狀態(tài)變量的值，可以直接或間接地測算得到．一般在動態(tài)規(guī)劃模型中，狀態(tài)變量大都選取那種可以進行累計的量。此外，在與靜態(tài)規(guī)劃模型的對應關系上，通常根據經驗，線性與非線性規(guī)劃中約束條件的個數，相當于動態(tài)規(guī)劃中狀態(tài)變量sk的維數．而前者約束條件所表示的內容，常就是狀態(tài)變量sk所代表的內容。343、動態(tài)規(guī)劃方法的基本步驟

3．正確地定義決策變量及各階段的允許決策集合Uk(sk)，根據經驗，一般將問題中待求的量，選作動態(tài)規(guī)劃模型中的決策變量?；蛘咴诎鸯o態(tài)規(guī)劃模型(如線性與非線性規(guī)劃)轉換為動態(tài)規(guī)劃模型時，常取前者的變量xj為后者的決策變量uk。4.能夠正確地寫出狀態(tài)轉移方程，至少要能正確反映狀態(tài)轉移規(guī)律。如果給定第k階段狀態(tài)變量sk的值，則該段的決策變量uk一經確定，第k+1段的狀態(tài)變量sk+1的值也就完全確定，即有sk+1=Tk(sk,uk)353、動態(tài)規(guī)劃方法的基本步驟

5．根據題意,正確地構造出目標與變量的函數關系——目標函數，目標函數應滿足下列性質：(1)可分性，即對于所有k后部子過程，其目標函數僅取決于狀態(tài)sk及其以后的決策uk,uk+1,┈,un,就是說它是定義在全過程和所有后部子過程上的數量函數。(2)要滿足遞推關系，即(3)函數對其變元Rk+1來說要嚴格單調。366．寫出動態(tài)規(guī)劃函數基本方程例如常見的指標函數是取各段指標和的形式

其中表示第i階段的指標，它顯然是滿足上述三個性質的。所以上式可以寫成：3、動態(tài)規(guī)劃方法的基本步驟37二．動態(tài)規(guī)劃方法的基本步驟為進一步說明動態(tài)規(guī)劃模型建立的基本方法及其求解過程,下面通過實際例子用上述方法具體給出求解動態(tài)規(guī)劃方法的基本步驟：例5.3有某種機床,可以在高低兩種不同的負荷下進行生產,在高負荷下生產時,產品的年產量為g,與年初投入生產的機床數量u1的關系為g=g(u1)=8u1,這時,年終機床完好臺數將為au1,(a為機床完好率，0<a<1,設a=0.7).在低負荷下生產時,產品的年產量為h,和投入生產的機床數量u2的關系為h=h(u2)=5u2,相應的機床完好率為b(0<b<1,設b=0,9),一般情況下a<b。3、動態(tài)規(guī)劃方法的基本步驟38假設某廠開始有x=1000臺完好的機床，現(xiàn)要制定一個五年生產計劃，問每年開始時如何重新分配完好的機床在兩種不同的負荷下生產的數量，以使在5年內產品的總產量為最高。

解：首先構造這個問題的動態(tài)規(guī)劃模型。1．變量設置(1)設階段變量k表示年度，因此，階段總數n=5。(2)狀態(tài)變量sk表示第k年度初擁有的完好機床臺數，同時也是第k-1年度末時的完好機床數量。3、動態(tài)規(guī)劃方法的基本步驟39(3)決策變量uk，表示第k年度中分配于高負荷下生產的機床臺數。于是sk-uk便為該年度中分配于低負荷下生產的機床臺數．這里sk與uk均取連續(xù)變量，當它們有非整數數值時．可以這樣理解：如sk＝0.6，就表示一臺機器在k年度中正常工作時間只占6/10；uk=0.4時，就表示一臺機床在k年度只有4/10的時間于高負荷下工作．2．狀態(tài)轉移方程為

k=1，2，…,63、動態(tài)規(guī)劃方法的基本步驟403．允許決策集合,在第k段為4．目標函數．設gk(sk,uk)為第k年度的產量，則gk(sk,uk)=8uk+5(sk-uk),因此，目標函數為k＝1,2．．．55．條件最優(yōu)目標函數遞推方程令fk(sk)表示由第k年的狀態(tài)sk出發(fā)，采取最優(yōu)分配方案到第5年度結束這段時間的產品產量，根據最優(yōu)化原理有以下遞推關系：

k=1,2,3,4,53、動態(tài)規(guī)劃方法的基本步驟416.邊界條件為下面采用逆序遞推計算法,從第5年度開始遞推計算．

k=5時有顯然，當u5*=s5時，f5(s5)有最大值，相應的有f5(s5)=8s5

k=4時有

3、動態(tài)規(guī)劃方法的基本步驟,=

=因此，當u4*=s4時，有最大值f4(s4)=13.6s442

k=3時有

可見，當u3*=s3時，f3(s3)有最大值f3(s3)=17.55s3.k=2時有

=+=此時，當取u2*=0時有最大值，即f2(s2)=20.8s2，其中s2=0.7u1+0.9(s1-u1)3、動態(tài)規(guī)劃方法的基本步驟=43

k=1時有+

=當取u1*=0時,f1(s1)有最大值，即f1(s1)=23.7s1,因為s1=1000,故f1(s1)=23700個產品．按照上述計算順序尋蹤得到下述計算結果：3、動態(tài)規(guī)劃方法的基本步驟44上面所討論的最優(yōu)決策過程是所謂始端狀態(tài)s1固定，終端狀態(tài)s6自由．如果終端也附加上一定的約束條件，那么計算結果將會與之有所差別．例如，若規(guī)定在第五個年度結束時，完好的機床數量為500臺(上面只有278臺)，問應該如何安排五年的生產，使之在滿足這一終端要求的情況下產量最高？3、動態(tài)規(guī)劃方法的基本步驟45解：由狀態(tài)轉移方程有得

顯而易見，由于固定了終端的狀態(tài)s6，第五年的決策變量U5的允許決策集合U5(s5)也有了約束，上式說明U5(s5)已退化為一個點，即第五年投入高負荷下生產的機床數只能由式U5=4.5s5-2500作出一種決策，故3、動態(tài)規(guī)劃方法的基本步驟＝50046當k=5時有

當k=4時有

顯然，只有取u4*=0，f4(s4)有最大值，即f4(s4)=21.7s4-7500。同理類推3、動態(tài)規(guī)劃方法的基本步驟====47K=3時有

可知,當u3*=0時,f3(s3)有最大值f4(s4)=24.5s3-7500.K=2時有此時,當u2*=0時有最大值,即f2(s2)=27.1s2-75003、動態(tài)規(guī)劃方法的基本步驟

=

=

=

=

+48

K=1時有

只有取u1*=0時,f1(s1)有最大值，即

f1(s1)=29.4s1-7500。

由此可見，為了使下一個五年計劃開始的一年有完好的機床500臺，其最優(yōu)策略應該為：在前4年中，都應該把全部機床投人低負荷下生產，在第5年，只能把部分完好機投入高負荷下生產。根據最優(yōu)策賂，從始端向終端遞推計算出各年的狀態(tài)，即算出每年年初的完好機床臺數，因為s1＝1000臺，于是有3、動態(tài)規(guī)劃方法的基本步驟==49因此，u5*=4.5s5-2500=425(臺)，這就是說第5年里還有204臺投入低負荷下生產，否則不能保證s6=0.7u5+0.9(u5-s5)=500(臺)。在上述最優(yōu)決策下，5年里所得最高產量為：

f1(s1)＝29.4s1-7500=29400-7500＝21900(個)?？梢?，附加了終端約束條件以后，其最高產量f1(s1)比終端自由時要低一些。3、動態(tài)規(guī)劃方法的基本步驟（臺）（臺）（臺）（臺）（臺）（臺）50例：一個線路網絡圖，從A到E要修建一條石油管道，必須在B、C、D處設立加壓站。各邊上的數為長度，現(xiàn)需要找一條路使總長度最短。B3B2B1C3C2C1D3D2D1EA4563434547426571097863、動態(tài)規(guī)劃方法的基本步驟51

解:可分成4個階段：

A到B、B到C、C到D、D到E；

每個階段k的起點稱為狀態(tài)Sk；從k階段的起點出發(fā)可以做一選擇，即決定到下一階段的哪個節(jié)點,稱為決策Xk；

可見,Sk+1是由Sk和Xk所決定的。

3、動態(tài)規(guī)劃方法的基本步驟52那麼，從A出發(fā)經過4個階段：A到B、B到C、C到D、D到E，逐次作出決策，構成從A到E的一條路線，記為u。

即，

u=S1X1S2X2S3X3S4X4S5

其中S1=A，S5=E

記d為兩個相鄰節(jié)點之間的長度，如d（A，B3）=3。3、動態(tài)規(guī)劃方法的基本步驟53①

記fk(Sk)為從Sk到E的最短長度,稱為從Sk到E的距離。那么，f1(A)是從A到E的最短距離，即最優(yōu)策略的值。3、動態(tài)規(guī)劃方法的基本步驟54

②最短路問題的特點：如果從A到E的最優(yōu)策略經過某節(jié)點，那么這個策略的從該節(jié)點到E的一段，必定是該節(jié)點到E的所有線路中Sk最短的一條，即這一段的長度為fk（Sk）。

（1）逆序法：從E到A（2）順序法：對節(jié)點Sk，從A到Sk

所有線路中，最短的一條的長度記為φk（Sk），例如φ1（A）=0，稱為問題的邊界條件。3、動態(tài)規(guī)劃方法的基本步驟55動態(tài)規(guī)劃模型建立后，對基本方程分段求解，不像線性規(guī)劃或非線性規(guī)劃那樣有固定的解法，必須根據具體問題的特點，結合數學技巧靈活求解，如動態(tài)規(guī)劃模型中的狀態(tài)變量與決策變量若被限定只能取離散值，則可采用離散變量的分段窮舉法。當動態(tài)規(guī)劃模型中狀態(tài)變量與決策變量為連續(xù)變量，就要根據方程的具體情況靈活選取連續(xù)變量的求解方法。如經典解析方法、線性規(guī)劃方法、非線性規(guī)劃法或其它數值計算方法等。還有連續(xù)變量的離散化解法和高維問題的降維法及疏密格子點法等等。3、動態(tài)規(guī)劃方法的基本步驟56學習方法建議：第一步先看問題，充分理解問題的條件、情況及求解目標；第二步結合前面講到的理論和解題過程，考慮如何著手進行求解該問題的工作。分析針對該動態(tài)規(guī)劃問題的“四大要素、一個方程”——這一步在開始時，會感到困難，但是一定要下決心去思考，在思考過程中深入理解前文講到的概念和理論；4、動態(tài)規(guī)劃方法應用舉例57第三步動手把求解思路整理出來，或者說，把該問題作為習題獨立的來做；第四步

把自己的求解放到一邊，看書中的求解方法，要充分理解教材中的論述；第五步對照自己的求解，分析成敗。4、動態(tài)規(guī)劃方法應用舉例581、動態(tài)規(guī)劃的四大要素①狀態(tài)變量及其可能集合xk

Xk②

決策變量及其允許集合ukUk③

狀態(tài)轉移方程

xk+1=Tk(xk,uk

)④

階段效應rk(xk,uk)

4、動態(tài)規(guī)劃方法應用舉例592、

動態(tài)規(guī)劃基本方程

fn+1(xn+1)=0(邊界條件)

fk(xk)=optu{rk(xk,uk)+fk+1(xk+1)}

k=n,…,14、動態(tài)規(guī)劃方法應用舉例60求最短路徑

61求最短路徑

62

將問題分成五個階段，第k階段到達的具體地點用狀態(tài)變量xk表示，例如：x2=B3表示第二階段到達位置B3，等等。這里狀態(tài)變量取字符值而不是數值。

將決策定義為到達下一站所選擇的路徑，例如目前的狀態(tài)是x2=B3，這時決策允許集合包含三個決策，它們是D2(x2)=D2(B3)={B3

C1,B3

C2,B3

C3}求最短路徑

63最優(yōu)指標函數fk(xk)表示從目前狀態(tài)到E的最短路徑。終端條件為

f5(x5)=f5(E)=0

其含義是從E到E的最短路徑為0。

第四階段的遞推方程為

:

求最短路徑

64其中*表示最優(yōu)值，在上表中，由于決策允許集合D4(x4)中的決策是唯一的，因此這個值就是最優(yōu)值。

由此得到f4(x4)的表達式。由于這是一個離散的函數，取值用列表表示：求最短路徑

65第三階段的遞推方程為：

求最短路徑

66由此得到f3(x3)的表達式：

求最短路徑

67求最短路徑

68由此得到f2(x2)的表達式：求最短路徑

69第一階段的遞推方程為：求最短路徑

70由此得到f1(x1)的表達式求最短路徑

71資源分配問題72例.有資金4萬元，投資A、B、C三個項目，每個項目的投資效益與投入該項目的資金有關。三個項目A、B、C的投資效益（萬噸）和投入資金（萬元）關系見下表：求對三個項目的最優(yōu)投資分配，使總投資效益最大。

資源分配問題73階段k：每投資一個項目作為一個階段；狀態(tài)變量xk：投資第k個項目前的資金數；決策變量dk：第k個項目的投資；決策允許集合：0≤dk≤xk狀態(tài)轉移方程：xk+1=xk-dk階段指標：vk(xk,dk)見表中所示；遞推方程：fk(xk)=max{vk(xk,dk)+fk+1(xk+1)}終端條件：f4(x4)=0資源分配問題74k=4，f4(x4)=0

k=3，0≤d3≤x3，x4=x3-d3

資源分配問題75k=2，0≤d2≤x2，x3=x2-d2資源分配問題76k=1，0≤d1≤x1，x2=x1-d1資源分配問題77背包問題78背包問題79則Max z= c1x1+c2x2+…+cnxn

s.t.w1x1+w2x2+…+wnxn≤W

x1, x2, …, xn為正整數

階段k： 第k次裝載第k種物品（k=1,2,…,n）狀態(tài)變量xk： 第k次裝載時背包還可以裝載的重量；決策變量dk： 第k次裝載第k種物品的件數；背包問題804.決策允許集合： Dk(xk)={dk|0

dk

xk/wk，dk為整數}；5.狀態(tài)轉移方程：xk+1=xk-wkdk6.階段指標：vk=ckdk7.遞推方程： fk(xk)=max{ckdk+fk+1(xk+1)}=max{ckdk+fk+1(xk-wkdk)}8.終端條件：f4(x4)=0背包問題81例．對于一個具體問題c1=65，c2=80，c3=30；w1=2，w2=3，w3=1；以及 W=5

用動態(tài)規(guī)劃求解對于k=3

背包問題8283848586機器負荷分配問題8788構造動態(tài)規(guī)劃模型如下：

階段k：運行年份（k=1,2,3,4,5,6），其中k=1表示第一年初，…，依次類推；k=6表示第五年末（即第六年初）；

狀態(tài)變量xk：第k年初完好的機器數（k=1,2,3,4,5,6），其中x6表示第五年末（即第六年初）的完好機器數；

決策變量dk：第k年投入高負荷運行的機器數；

狀態(tài)轉移方程：xk+1=0.7dk+0.9(xk-dk)

決策允許集合：Dk(xk)={dk|0

dk

xk}

階段指標：vk(xk,dk)=8dk+5(xk-dk)

終端條件：f6(x6)=0

機器負荷分配問題89遞推方程：

fk(xk)=max{vk(xk,dk)+fk+1(xk+1)}

dk

Dk(xk)

=max

{8dk+5(xk-dk)+fk+1[0.7dk+0.9(xk-dk)]}

0

dk

xk

機器負荷分配問題90f5(x5)=max{8d5+5(x5-d5)+f6(x6)}

0

d5

x5

=max{3d5+5x5}=8x5, d5*=x5

0

d5

x5

f4(x4)=max{8d4+5(x4-d4)+f5(x5)}

0

d4

x4

=max{8d4+5(x4-d4)+8x5}

0

d4

x4

=max{8d4+5(x4-d4)+8[0.7d4+0.9(x4-d4)]}

0

d4

x4

=max{1.4d4+12.3x4}=13.7x4, d4*=x4

0

d4

x4

機器負荷分配問題91f3(x3)=max{8d3+5(x3-d3)+f4(x4)}

0

d3

x3

=max{8d3+5(x3-d3)+13.7x4}

0

d3

x3

=max{8d3+5(x3-d3)+13.7[0.7d3+0.9(x3-d3)]}

0

d3

x3

=max{0.28d3+17.24x3}=17.52x3, d3*=x3

0

d3

x3

機器負荷分配問題92f2(x2)=max{8d2+5(x2-d2)+f3(x3)}

0

d2

x2

=max{8d2+5(x2-d2)+17.52x3}

0

d2

x2

=max{8d2+5(x2-d2)+17.52

[0.7d2+0.9(x2-d2)]}

0

d2

x2

=max{-0.504d2+20.77x2}

=20.77x2,

d2*=00

d2

x2

機器負荷分配問題93f1(x1)=max{8d1+5(x1-d1)+f2(x2)}

0

d1

x1

=max{8d1+5(x1-d1)+20.77x2}

0

d1

x1

=max{8d1+5(x1-d1)+20.77

[0.7d1+0.9(x1-d1)]}

0

d1

x1

=max{-0.05d1+23.69x1}

=23.69x1,

d1*=0

0

d1

x1

機器負荷分配問題94由此可以得到：f1(x1)=23.69x1, d1*=0f2(x2)=20.77x2, d2*=0f3(x3)=17.52x3, d3*=x3f4(x4)=13.60x4, d4*=x4f5(x5)=8x5 d5*=x5用x1=1000代入，得到五年最大產量為f1(x1)=f1(1000)=23690機器負荷分配問題95每年投入高負荷運行的機器數以每年初完好的機器數為：x1=1000d1*=0,x2=0.7d1+0.9(x1-d1)=900d2*=0,x3=0.7d2+0.9(x2-d2)=810d3*=x3=810,x4=0.7d3+0.9(x3-d3)=567d4*=x4=567,x5=0.7d4+0.9(x4-d4)=397d5*=x5=397,x6=0.7d5+0.9(x5-d5)=278機器負荷分配問題96在這個例子中，狀態(tài)變量的終端值x6是未加約束的，如果要求在第五年末（即第六年初）完好的機器數不少于500臺，這時決策變量d5的決策允許集合將成為：

D5(x5)={d5|0.7d5+0.9(x5-d5)

500,d5

0}

即0.9x5-0.2d5

500,

d5

0或0

d5

4.5x5-2500

容易想象，這時的最大產量將比x6是自由的情況下小。這個例子可以推廣到一般情況。設高負荷生產時機器的完好率為k1，單臺產量為p1；低負荷完好率為k2，單臺產量為p2。若有t滿足: 機器負荷分配問題97則從1—t-1年，年初將全部完好機器投入低負荷運行，從t—n年，年初將全部完好機器投入高負荷運行，這樣的決策，將使總產量達到最大。

機器負荷分配問題98生產庫存問題99例.一個工廠生產某種產品,1-7月份生產

成本和產品需求量的變化情況如下表：

生產庫存問題100階段k：月份，k=1,2,…,7,8；狀態(tài)變量xk：第k個月初（發(fā)貨以前）的庫存量；決策變量dk：第k個月的生產量；狀態(tài)轉移方程：xk+1=xk-rk+dk；決策允許集合：Dk(xk)={dk|dk

0,rk+1

xk+1

H} ={dk|dk

0,rk+1

xk-rk+dk

H}；階段指標：vk(xk,dk)=ckdk；終端條件：f8(x8)=0, x8=0；生產庫存問題101遞推方程：fk(xk)=min{vk(xk,dk)+fk+1(xk+1)}

dk

Dk(xk)

=min{ckdk+fk+1(xk-rk+dk)}

dk

Dk(xk)

對于k=7因為x8=0有d7=0遞推方程為f7(x7)=min{c7d7+f8(x8)}=0d7=0生產庫存問題102對于k=6

因為

d7=0，所以 x7=r7=4

而

x6-r6+d6=x7=4

因此有

d6=x7+r6-x6=4+7-x6=11-x6

也是唯一的決策。因此遞推方程為：

f6(x6)=min{c6d6+f7(x7)}d6=11-x6

=10d6=10(11-x6)=110-10x6

生產庫存問題103對于k=5f5(x5)=min{c5d5+f6(x6)}d5

D5(x5) =min{20d5+110-10x6}d5

D5(x5) =min{20d5+110-10(x5-r5+d5)}d5

D5(x5) =min{20d5+110-10(x5-2+d5)} d5

D5(x5) =min{10d5-10x5+130} d5

D5(x5)D5(x5)={d5|d5

0,r6

x5-r5+d5

H} ={d5|d5

0,r6+r5-x5

d5

H+r5-x5} ={d5|d5

0,9-x5

d5

11-x5}生產庫存問題104因為x5

H=9，因此9-x5

0，決策允許集合可以簡化為

D5(x5)={d5|9-x5

d5

11-x5}

遞推方程成為

f5(x5)=min{10d5-10x5+130}

9-x5

d5

11-x5

=10(9-x5)-10x5+130

=220-20x5， d5*=9-x5

生產庫存問題105對于k=4

f4(x4)=min{c4d4+f5(x5)}

d4

D4(x4)

=min{17d4+220-20x5}

d4

D4(x4)

=min{17d4+220-20(x4-r4+d4)}

d4

D4(x4)

=min{17d4+220-20(x4-3+d4)}

d4

D4(x4)

=min{-3d4-20x4+280}

d4

D4(x4)

生產庫存問題106D4(x4)={d4|d4

0,r5

x4-r4+d4

H}

={d4|d4

0,r5+r4-x4

d4

H+r4-x4}

={d4|d4

0,5-x4

d4

12-x4}

={d4|max[0,5-x4]

d4

12-x4}

由于在f4(x4)的表達式中d4的系數是-3，

因此d4在決策允許集合中應取集合中的最大值，即d4=12-x4由此f4(x4)=-3(12-x4)-20x4+280 =-17x4+244

生產庫存問題107對于k=3

f3(x3)=min{c3d3+f4(x4)} d3

D3(x3)

=min{13d3+244-17x4}d3

D3(x3)

=min{13d3+244-17(x3-r3+d3)}d3

D3(x3)

=min{-4d3-17x3+329)}d3

D3(x3)

D3(x3)={d3|d3

0,r4

x3-r3+d3

H}

={d3|d3

0,r4+r3-x3

d3

H+r3-x3}

={d3|d3

0,8-x3

d3

14-x3}

={d3|max[0,8-x3]

d3

14-x3}

由此

f3(x3)=-4(14-x3)-17x3+329

=-13x3+273, d3*=14-x3

生產庫存問題108對于k=2

f2(x2)=min{c2d2+f3(x3)}d2

D2(x2)

=min{18d2+273-13x3}d2

D2(x2)

=min{18d2+273-13(x2-r2+d2)}

d2

D2(x2)

=min{18d2+273-13(x2-8+d2)}

d2

D2(x2)

=min{5d2-13x2+377}d2

D2(x2)

D2(x2)={d2|d2

0,r3

x2-r2+d2

H}

={d2|d2

0,r3+r2-x2

d2

H+r2-x2}

={d2|d2

0,13-x2

d2

17-x2}

生產庫存問題109因為13-x2>0

所以

d2(x2)={d2|13-x2

d2

17-x2}

由此

f2(x2)=5(13-x2)-13x2+377

=-18x2+442,

d2*=13-x2

生產庫存問題110對于k=1

f1(x1)=min{c1d1+f2(x2)}d1

D1(x1)

=min{11d1+442-18x2}d1

D1(x1) =min{11d1+442-18(x1-r1+d1)}

d1

D1(x1)

=min{11d1+442-18(x1-0+d1)}

d1

D1(x1)

=min{-7d1-18x1+442}

d1

D1(x1)

D1(x1)={d1|d1

0,r2

x1-r1+d1

H} ={d1|d1

0,r2+r1-x1

d1

H+r1-x1} ={d1|d1

0,8-x1

d1

9-x1}生產庫存問題111根據題意x1=2

所以

D1(x1)={d1|6

d1

7}

由此

d1=7

f1(x1)=-7d1-18x1+442

=-7×7－18×2＋442

=357

將以上結果總結成下表：生產庫存問題112設備更新問題113

一臺設備的價格為P，運行壽命為n年，每年的維修費用是設備役齡的函數，記為C(t)，新設備的役齡為t=0。舊設備出售的價格是設備役齡的函數，記為S(t)。在n年末，役齡為t的設備殘值為R(t)?，F(xiàn)有一臺役齡為T的設備，在使用過程中，使用者每年都面臨“繼續(xù)使用”或“更新”的策略，設備更新問題114115設備更新問題116例．設具體數據如下：

設備更新問題117118119120121122123124125126由以上計算可知，本問題有兩個決策，它們對應的最小費用都是115。

這兩個決策是

設備更新問題127第六章排隊論基本概念輸入過程和服務時間分布泊松輸入——指數服務排隊模型其他模型選介排隊系統(tǒng)的優(yōu)化目標與最優(yōu)化問題本章內容重點128排隊論(QueuingTheory)，又稱隨機服務系統(tǒng)理論(RandomServiceSystemTheory),是一門研究擁擠現(xiàn)象(排隊、等待)的科學。具體地說，它是在研究各種排隊系統(tǒng)概率規(guī)律性的基礎上，解決相應排隊系統(tǒng)的最優(yōu)設計和最優(yōu)控制問題。前言129排隊是我們在日常生活和生產中經常遇到的現(xiàn)象。例如，上、下班搭乘公共汽車；顧客到商店購買物品；病員到醫(yī)院看??；旅客到售票處購買車票；學生去食堂就餐等就常常出現(xiàn)排隊和等待現(xiàn)象。除了上述有形的排隊之外，還有大量的所謂“無形”排隊現(xiàn)象，如幾個顧客打電話到出租汽車站要求派車，如果出租汽車站無足夠車輛、則部分顧客只得在各自的要車處等待，他們分散在不同地方，卻形成了一個無形隊列在等待派車。排隊的不一定是人，也可以是物：前言130例如，通訊衛(wèi)星與地面若干待傳遞的信息；生產線上的原料、半成品等待加工；因故障停止運轉的機器等待工人修理；碼頭的船只等待裝卸貨物；要降落的飛機因跑道不空而在空中盤旋等等。前言131顯然，上述各種問題雖互不相同，但卻都有要求得到某種服務的人或物和提供服務的人或機構。排隊論里把要求服務的對象統(tǒng)稱為“顧客”,而把提供服務的人或機構稱為“服務臺”或“服務員”。不同的顧客與服務組成了各式各樣的服務系統(tǒng)。顧客為了得到某種服務而到達系統(tǒng)、若不能立即獲得服務而又允許排隊等待，則加入等待隊伍，待獲得服務后離開系統(tǒng)，見圖6—1至圖6—5。前言132類似地還可畫出許多其它更復雜形式的排隊系統(tǒng)，如串并混聯(lián)的系統(tǒng)，網絡排隊系統(tǒng)等。盡管各種排隊系統(tǒng)的具體形式不同，但都可由圖6—6加以描述。圖6—1單服務臺排隊系統(tǒng)前言133圖6—2單隊列——S個服務臺并聯(lián)的排隊系統(tǒng)圖6-3S個隊列——S個服務臺的并聯(lián)排隊系統(tǒng)前言134圖6—4單隊——多個服務臺的串聯(lián)排隊系統(tǒng)

圖6—5多隊——多服務臺混聯(lián)、網絡系統(tǒng)前言135圖6—6隨機服務系統(tǒng)前言136通常稱由圖6—6表示的系統(tǒng)為一隨機聚散服務系統(tǒng)，任—排隊系統(tǒng)都是一個隨機聚散服務系統(tǒng)。這里，“聚”表示顧客的到達，“散”表示顧客的離去，所謂隨機性則是排隊系統(tǒng)的一個普遍特點，是指顧客的到達情況(如相繼到達時間間隔)與每個顧客接受服務的時間往往是事先無法確切知道的，或者說是隨機的。一般來說，排隊論所研究的排隊系統(tǒng)中，顧客到來的時刻和服務臺提供服務的時間長短都是隨機的，因此這樣的服務系統(tǒng)被稱為隨機服務系統(tǒng)。前言137面對擁擠現(xiàn)象，人們總是希望盡量設法減少排隊，通常的做法是增加服務設施，但是增加的數量越多，人力、物力的支出就越大，甚至會出現(xiàn)空閑浪費，如果服務設施太少，顧客排隊等待的時間就會很長，這樣對顧客會帶來不良影響。于是，顧客排隊時間的長短與服務設施規(guī)模的大小，就構成了設計隨機服務系統(tǒng)中的一對矛盾。如何做到既保證一定的服務質量指標，又使服務設施費用經濟合理，恰當地解決顧客排隊時間與服務設施費用大小這對矛盾，這就是隨機服務系統(tǒng)理論——排隊論所要研究解決的問題。前言138排隊論是1909年由丹麥工程師愛爾朗(A.K．Erlang)在研究電活系統(tǒng)時創(chuàng)立的，幾十年來排隊論的應用領域越來越廣泛，理論也日漸完善。特別是自二十世紀60年代以來，由于計算機的飛速發(fā)展，更為排隊論的應用開拓了寬闊的前景。前言1391、基本概念一排隊系統(tǒng)的描述（一）、系統(tǒng)特征和基本排隊過程實際的排隊系統(tǒng)雖然千差萬別，但是它們有以下的共同特征：(1)有請求服務的人或物——顧客；(2)有為顧客服務的人或物，即服務員或服務臺；(3)顧客到達系統(tǒng)的時刻是隨機的，為每一位顧客提供服務的時間是隨機的，因而整個排隊系統(tǒng)的狀態(tài)也是隨機的。排隊系統(tǒng)的這種隨機性造成某個階段顧客排隊較長，而另外一些時候服務員(臺)又空閑無事。140任何一個排隊問題的基本排隊過程都可以用圖6-6表示。從圖6-6可知，每個顧客由顧客源按一定方式到達服務系統(tǒng)，首先加入隊列排隊等待接受服務，然后服務臺按一定規(guī)則從隊列中選擇顧客進行服務，獲得服務的顧客立即離開。1、基本概念141（二）、排隊系統(tǒng)的基本組成部分通常，排隊系統(tǒng)都有輸入過程、服務規(guī)則和服務臺等3個組成部分：1．輸入過程．這是指要求服務的顧客是按怎樣的規(guī)律到達排隊系統(tǒng)的過程，有時也把它稱為顧客流．一般可以從3個方面來描述—個輸入過程。(1)顧客總體數，又稱顧客源、輸入源。這是指顧客的來源。顧客源可以是有限的，也可以是無限的。例如，到售票處購票的顧客總數可以認為是無限的，而某個工廠因故障待修的機床則是有限的。1、基本概念142(2)顧客到達方式。這是描述顧客是怎樣來到系統(tǒng)的，他們是單個到達，還是成批到達。病人到醫(yī)院看病是顧客單個到達的例子。在庫存問題中如將生產器材進貨或產品入庫看作是顧客，那么這種顧客則是成批到達的。(3)顧客流的概率分布，或稱相繼顧客到達的時間間隔的分布。這是求解排隊系統(tǒng)有關運行指標問題時，首先需要確定的指標。這也可以理解為在一定的時間間隔內到達K個顧客(K=1、2、

)的概率是多大。顧客流的概率分布一般有定長分布、二項分布、泊松流(最簡單流)、愛爾朗分布等若干種。1、基本概念1432.服務規(guī)則．這是指服務臺從隊列中選取顧客進行服務的順序。一般可以分為損失制、等待制和混合制等3大類。(1)損失制。這是指如果顧客到達排隊系統(tǒng)時，所有服務臺都已被先來的顧客占用，那么他們就自動離開系統(tǒng)永不再來。典型例子是，如電話拔號后出現(xiàn)忙音，顧客不愿等待而自動掛斷電話，如要再打，就需重新拔號，這種服務規(guī)則即為損失制。1、基本概念144(2)等待制。這是指當顧客來到系統(tǒng)時，所有服務臺都不空，顧客加入排隊行列等待服務。例如，排隊等待售票，故障設備等待維修等。等待制中，服務臺在選擇顧客進行服務時，常有如下四種規(guī)則：①先到先服務。按顧客到達的先后順序對顧客進行服務，這是最普遍的情形；②后到先服務。倉庫中迭放的鋼材，后迭放上去的都先被領走，就屬于這種情況；1、基本概念145③隨機服務。即當服務臺空閑時，不按照排隊序列而隨意指定某個顧客去接受服務，如電話交換臺接通呼叫電話就是一例；④優(yōu)先權服務。如老人、兒童先進車站；危重病員先就診；遇到重要數據需要處理計算機立即中斷其他數據的處理等，均屬于此種服務規(guī)則。1、基本概念146(3)混合制．這是等待制與損失制相結合的一種服務規(guī)則，一般是指允許排隊，但又不允許隊列無限長下去。具體說來，大致有三種：①隊長有限。當排隊等待服務的顧客人數超過規(guī)定數量時，后來的顧客就自動離去，另求服務，即系統(tǒng)的等待空間是有限的。例如最多只能容納K個顧客在系統(tǒng)中，當新顧客到達時，若系統(tǒng)中的顧客數(又稱為隊長)小于K，則可進入系統(tǒng)排隊或接受服務；否則，便離開系統(tǒng)，并不再回來。如水庫的庫容是有限的，旅館的床位是有限的。1、基本概念147②等待時間有限。即顧客在系統(tǒng)中的等待時間不超過某一給定的長度T，當等待時間超過T時，顧客將自動離去，并不再回來。如易損壞的電子元器件的庫存問題，超過一定存儲時間的元器件被自動認為失效。又如顧客到飯館就餐，等了一定時間后不愿再等而自動離去另找飯店用餐。

1、基本概念148③逗留時間(等待時間與服務時間之和)有限。例如用高射炮射擊敵機，當敵機飛越高射炮射擊有效區(qū)域的時間為t時，若在這個時間內未被擊落，也就不可能再被擊落了。

不難注意到，損失制和等待制可看成是混合制的特殊情形，如記s為系統(tǒng)中服務臺的個數，則當K=s時，混合制即成為損失制；當K=∞時，混合制即成為等待制.1、基本概念1493．服務臺情況．服務臺可以從以下3方面來描述：(1)服務臺數量及構成形式。從數量上說，服務臺有單服務臺和多服務臺之分。從構成形式上看，服務臺有：a)單隊——單服務臺式，b)單隊——多服務臺并聯(lián)式，c)多隊——多服務臺并聯(lián)式，d)單隊——多服務臺串聯(lián)式，e)單隊——多服務臺并串聯(lián)混合式以及多隊——多服務臺并串聯(lián)混合式等等。見圖6-1至圖6-5所示。1、基本概念150(2)服務方式。這是指在某一時刻接受服務的顧客數，它有單個服務和成批服務兩種。如公共汽車一次就可裝載一批乘客就屬于成批服務。(3)服務時間的分布。一般來說，在多數情況下，對每一個顧客的服務時間是一隨機變量，其概率分布、有定長分布、負指數分布、K級愛爾良分布、一般分布(所有顧客的服務時間都是獨立同分布的)等等。1、基本概念151（三）、排隊系統(tǒng)的描述符號與分類為了區(qū)別各種排隊系統(tǒng)，根據輸入過程、排隊規(guī)則和服務機制的變化對排隊模型進行描述或分類，可給出很多排隊模型。為了方便對眾多模型的描述，肯道爾（D．G．Kendall）提出了一種目前在排隊論中被廣泛采用的“Kendall記號”，完整的表達方式通常用到6個符號并取如下固定格式：

/

/

/

/

/

/各符號的意義為：1、基本概念152

—表示顧客相繼到達間隔時間分布，常用下列符號：M——表示到達過程為泊松過程或負指數分布；D——表示定長輸入；Ek——表示k階愛爾朗分布；G——表示一般相互獨立的隨機分布；

—表示服務時間分布，所用符號與表示顧客到達間隔時間分布相同。M——表示服務過程為泊松過程或負指數分布；D——表示定長分布；Ek——表示k階愛爾朗分布；G——表示一般相互獨立的隨機分布；1、基本概念153

—表示服務臺(員)個數：“1”則表示單個服務臺，“s”。(s＞1)表示多個服務臺。

—表示系統(tǒng)中顧客容量限額，或稱等待空間容量；如系統(tǒng)有K個等待位子，則0<K<∞，當K=0時，說明系統(tǒng)不允許等待，即為損失制。K=∞時為等待制系統(tǒng)，此時∞般省略不寫。K為有限整數時，表示為混合制系統(tǒng)。

—表示顧客源限額，分有限與無限兩種，∞表示顧客源無限，此時一般∞也可省略不寫。