动态规划和排队论

1、1第五章 动态规划多阶段决策过程的最优化动态规划的基本概念和基本原理动态规划方法的基本步骤动态规划方法应用举例本章内容重点21 1、多阶段决策过程的最优化、多阶段决策过程的最优化图5-11 运输网络图示3多阶段决策过程特点多阶段决策过程特点: :要点：要点：阶段，状态，决策，状态转阶段，状态，决策，状态转移方程，移方程，k-k-后部子过程后部子过程状态状态 x x1 1阶段阶段1 1T T1 1决策决策u u1 1状态状态 x x2 2决策决策u u2 2阶段阶段2 2T T2 2状态状态 x x3 3.状态状态 x xk k决策决策u uk k阶段阶段k kT Tk k状态状态 x xk+1

2、k+1.状态状态 x xn n决策决策u un n阶段阶段n nTnTn状态状态 x xn+1n+11 1、多阶段决策过程的最优化、多阶段决策过程的最优化4 2 2、动态规划的基本概念动态规划的基本概念 一、动态规划的基本概念一、动态规划的基本概念 使用动态规划方法解决多阶段决策问题，首先要将实际问题写成动态规划模型，同时也为了今后叙述和讨论方便，这里需要对动态规划的下述一些基本术语进一步加以说明和定义： 5 2 2、动态规划的基本概念动态规划的基本概念 ( (一一) ) 阶段和阶段变量阶段和阶段变量 为了便于求解和表示决策及过程的发展顺序，而把所给问题恰当地划分为若干个相互联系又有区别的子问

3、题，称之为多段决策问题的阶段。一个阶段，就是需要作出一个决策的子问题，通常，阶段是按决策进行的时间或空间上先后顺序划分的用以描述阶段的变量叫作阶段变量，一般以k表示阶段变量阶段数等于多段决策过程从开始到结束所需作出决策的数目，图51所示的最短路问题就是一个四阶段决策过程6 2 2、动态规划的基本概念动态规划的基本概念（二）状态、状态变量和可能状态集（二）状态、状态变量和可能状态集 1、状态与状态变量用以描述事物(或系统)在某特定的时间与空间域中所处位置及运动特征的量，称为状态反映状态变化的量叫作状态变量。状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息按照过程进行的先后，每个阶段的状

4、态可分为初始状态和终止状态，或称输入状态和输出状态，阶段k的初始状态记作Sk，终止状态记为Sk+1。但为了清楚起见，通常定义阶段的状态即指其初始状态7 2 2、动态规划的基本概念动态规划的基本概念2可能状态集 一般状态变量的取值有一定的范围或允许集合，称为可能状态集，或可达状态集可能状态集实际上是关于状态的约束条件通常可能状态集用相应阶段状态sk的大写字母Sk表示，skSk，可能状态集可以是一离散取值的集合，也可以为一连续的取值区间，视具体问题而定在图51所示的最短路问题中，第一阶段状态为V1，状态变量s1的状态集合S1=V1；第二阶段则有三个状态：V2,V3,V4 ,状态变量s2的状态集合S

5、2=V2,V3,V4 ；第三阶段也有三个状态:V5,V6,V7 ，状态变量s3的状态集合S3=V5,V6,V7 ；第四阶段则有二个状态： V8,V9, 状态变量s4的状态集合S4=V8,V9 ；8 （三）决策、决策变量和允许决策集合三）决策、决策变量和允许决策集合 所谓决策就是确定系统过程发展的方案，决策的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的选择 用以描述决策变化的量称之决策变量，和状态变量一样，决策变量可以用一个数，一组数或一向量来描述也可以是状态变量的函数，记以uk= uk(sk)，表示于阶段k状态sk时的决策变量 决策变量的取值往往也有一定的允许范围，称之

6、允许决策集合决策变量uk(sk)的允许决策集用Uk(sk)表示, uk(sk) Uk(sk)允许决策集合实际是决策的约束条件 2 2、动态规划的基本概念动态规划的基本概念9 （四）、策略和允许策略集合（四）、策略和允许策略集合 策略(Policy)也叫决策序列策略有全过程策略和k部子策略之分，全过程策略是指具有n个阶段的全部过程，由依次进行的n个阶段决策构成的决策序列，简称策略，表示为p1,nu1,u2,un。从k阶段到第n阶段，依次进行的阶段决策构成的决策序列称为k部子策略,表示为pk,nuk,uk+1,un ，显然当k=1时的k部子策略就是全过程策略。 在实际问题中，由于在各个阶段可供选择

7、的决策有许多个，因此，它们的不同组合就构成了许多可供选择的决策序列(策略)，由它们组成的集合，称之允许策略集合，记作P1,n ，从允许策略集中，找出具有最优效果的策略称为最优策略。 2 2、动态规划的基本概念动态规划的基本概念10（五）状态转移方程（五）状态转移方程 系统在阶段k处于状态sk，执行决策uk(sk)的结果是系统状态的转移，即系统由阶段k的初始状态sk转移到终止状态sk+1 ，或者说，系统由k阶段的状态sk转移到了阶段k+1的状态sk+1 ，多阶段决策过程的发展就是用阶段状态的相继演变来描述的。 对于具有无后效性的多阶段决策过程,系统由阶段k到阶段k+1的状态转移完全由阶段k的状态

8、sk和决策uk(sk)所确定，与系统过去的状态s1,s2, sk-1及其决策u1(s1), u2(s2)uk-1(sk-1)无关系统状态的这种转移，用数学公式描述即有： 2 2、动态规划的基本概念动态规划的基本概念)(,(1kkkkksusTs(5-1)11 通常称式(5-1)为多阶段决策过程的状态转移方程。有些问题的状态转移方程不一定存在数学表达式，但是它们的状态转移，还是有一定规律可循的。 ( (六六) ) 指标函数指标函数 用来衡量策略或子策略或决策的效果的某种数量指标，就称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量函数。对不同问题，指标函数可以是诸如费用、成本、产值、利

9、润、产量、耗量、距离、时间、效用，等等。例如：图51的指标就是运费。 2 2、动态规划的基本概念动态规划的基本概念12 (1)阶段指标函数（也称阶段效应）。用gk(sk,uk)表示第k段处于sk状态且所作决策为uk(sk)时的指标，则它就是第k段指标函数，简记为gk 。图5-1的gk值就是从状态sk到状态sk+1的距离。譬如，gk(v2,v5)=3,即v2到v5的距离为3。 (2)过程指标函数（也称目标函数）。用Rk(sk,uk)表示第k子过程的指标函数。如图5-1的Rk(sk,uk)表示处于第k段sk状态且所作决策为uk时，从sk点到终点v10的距离。由此可见， Rk(sk,uk)不仅跟当前

10、状态sk有关，还跟该子过程策略pk(sk)有关，因此它是sk和pk(sk)的函数，严格说来，应表示为: 2 2、动态规划的基本概念动态规划的基本概念)(,(kkkkspsR13 不过实际应用中往往表示为Rk(sk,uk)或Rk(sk)。还跟第k子过程上各段指标函数有关，过程指标函数Rk(sk)通常是描述所实现的全过程或k后部子过程效果优劣的数量指标，它是由各阶段的阶段指标函数gk(sk,uk)累积形成的，适于用动态规划求解的问题的过程指标函数（即目标函数），必须具有关于阶段指标的可分离形式对于部子过程的指标函数可以表示为： 式中，表示某种运算，可以是加、减、乘、除、开方等 2 2、动态规划的基

11、本概念动态规划的基本概念),(),(),(),(11111,nnnkkkkkknnkkkknknkusgusgusgusususRR (5-2)14 多阶段决策问题中，常见的目标函数形式之一是取各阶段效应之和的形式，即: (5-3) 有些问题，如系统可靠性问题，其目标函数是取各阶段效应的连乘积形式，如： (5-4) 总之，具体问题的目标函数表达形式需要视具体问题而定。 2 2、动态规划的基本概念动态规划的基本概念nkiiiikusgR),(nkiiiikusgR),(15 ( (七七) ) 最优解最优解 用fk(sk)表示第k子过程指标函数 在状态sk下的最优值,即 称fk(sk)为第k子过程

12、上的最优指标函数；与它相应的子策略称为sk状态下的最优子策略，记为pk*(sk) ；而构成该子策赂的各段决策称为该过程上的最优决策，记为 ；有 简记为 2 2、动态规划的基本概念动态规划的基本概念)(,(kkkkspsRnkspsRoptsfkkkksPpkkkKk, 2 , 1),(,()()()(,),(),(11nnkkkksususunksusususpnnkkkkkk, 2 , 1),(,),(),()(11nkuuupnkkk, 2 , 1,116 特别当k=1且s1取值唯一时，f1(s1)就是问题的最优值，而p1*就是最优策略。如例5.1只有唯一始点v1即s1取值唯一,故f1(s

13、1)=18就是例5.1的最优值，而 就是例5.1的最优策略。 但若取值不唯一,则问题的最优值记为f0有 最优策略即为s1=s1*状态下的最优策略： 我们把最优策略和最优值统称为问题的最 优解。 2 2、动态规划的基本概念动态规划的基本概念,109731vvvvp)()(11111011ssfsfoptfSs,),()(211111nuusussp17 按上述定义，所谓最优决策，按上述定义，所谓最优决策， 是指它们在全过程上整体最优(即所构成的全过程策略为最优)，而不一定在各阶段上单独最优。 ( (八八) ) 多阶段决策问题的数学模型多阶段决策问题的数学模型 综上所述，适于应用动态规划方法求解的

14、一类多阶段决策问题，亦即具有无后效性的多阶段决策问题的数学模型呈以下形式: 2 2、动态规划的基本概念动态规划的基本概念), 2 , 1(nkuknkUuSsusTstsusususRRoptfkkkkkkkknnuun,2, 1),(.),(122111（5-5）18 式中“OPT”表示最优化，视具体问题取max或min. 上述数学模型说明了对于给定的多阶段决策过程，求取一个(或多个)最优策略或最优决策序列 ，使之既满足式(5-5)给出的全部约束条件，又使式(5-5)所示的目标函数取得极值，并且同时指出执行该最优策略时，过程状态演变序列即最优路线 2 2、动态规划的基本概念动态规划的基本概念

15、,21nuuu,121nnssss19 二、动态规划的最优化原理与基本方程二、动态规划的最优化原理与基本方程 1 1标号法标号法 标号法是借助网络图通过分段标号来求出最优路线的一种简便、直观的方法。通常标号法采取“逆序求解”的方法来寻找问题的最优解，即从最后阶段开始，逐次向阶段数小的方向推算，最终求得全局最优解。 2 2、动态规划的基本原理动态规划的基本原理20下面给出标号法的一般步骤：1.从最后一段标起，该段各状态(即各始点)到终点的距离用数字分别标在各点上方的方格内，并用粗箭线连接各点和终点。2.向前递推，给前一阶段的各个状态标号。每个状态上方方格内的数字表示该状态到终点的最短距离。即为该

16、状态到该阶段已标号的各终点的段长，再分别加上对应终点上方的数字而取其最小者。将刚标号的点沿着最短距离所对应的已标号的点用粗箭线连接起来，表示出各刚标号的点到终点的最短路线。 2 2、动态规划的基本原理动态规划的基本原理21 3.逐次向前递推，直到将第一阶段的状态(即起点)也标号，起点方格内的数字就是起点到终点的最短距离，从起点开始连接终点的粗箭线就是最短路线。 用标号法来求解下例 例例5.25.2：下列网络图52表示某城市的局部道路分布图。一货运汽车从S出发，最终到达目的地E。其中Ai(i1，2，3),Bj(j1，2)和Ck(k1，2)是可供汽车选择的途经站点，各点连线上的数字表示两个站点问的

17、距离。问，此汽车应走哪条路线，使所经过的路程距离最短? 2 2、动态规划的基本原理动态规划的基本原理22 2 2、动态规划的基本原理动态规划的基本原理图5-2 某城市的局部道路分布图23 第一步：先考虑第四阶段，即k=4，该阶段共有两个状态：C1、C2，设f4(C1)和f4(C2)分别表示C1、C2到E的最短距离，显然有f4(C1)=5和f4(C2)=8，边界条件f5(E)=0 。 第二步：即k=3,该阶段共有两个状态:B1 , B2 (1) 从B1出发有两种决策:B1C1，B1C2 。记d3(B1,C1)表示B1到C1的距离,即,这里的每一种决策的阶段指标函数就是距离，所以，B1C1的阶段指

18、标函数为d3(B1,C1)6，B1C2的阶段指标函数为d3(B1,C2)5。因此有,f3(B1)mind3(B1,C1)+f4(C1),d3(B1,C2)+ f4(C2)min(6十5，5十8)11。那么，从出发到E的最短路线是B1C1E，对应的决策u3(B1) = C1 。 2 2、动态规划的基本原理动态规划的基本原理24 (2)从B2出发也有两种决策:B2C1,B2C2同理, 有f3(B2)=mind3(B2,C1)+f4(C1),d3(B2,C2)+f4(C2)min(9+5，8+87)14，那么，从B2出发到E的最短路线是B2C1E，且u3(B2)=C1 。 第三步：即k2,该阶段共有

19、三个状态:Al,A2,A3 (1)从Al出发有两种决策：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出发也有两种决策: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、动态规划的基本原理动态规划的基本原理25(3)从A3出发也有两种决策: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，该阶段只有一个状态S,从S出发有三种决策: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、动态规划的基本原理动态规划的基本原理ECBAS11

21、1ECBAS113ECBAS12326 结果如图5-3所示。 每个状态上方的方格内的数字表示该状态到E的最短距离，首尾相连的粗箭线构成每一状态到E的最短路线。因此，标号法不但给出起点到终点的最短路线和最短距离，同时也给出每一状态到终点的最短路线及其最短距离。如,A1到E的最短路线是 ,最短矩离是17 图见下页 2 2、动态规划的基本原理动态规划的基本原理ECBA11127 2 2、动态规划的基本原理动态规划的基本原理图5-3某城市局部道路求最短路径的过程28 2最优化原理 （贝尔曼最优化原理） 作为一个全过程的最优策略具有这样的性 质：对于最优策略过程中的任意状态而言， 无论其过去的状态和决策

22、如何，余下的诸 决策必构成一个最优子策略。 该原理的具体解释是，若某一全过程最优 策略为： 2 2、动态规划的基本原理动态规划的基本原理)(),(,),(),()(221111nnkksususususp 则对上述策略中所隐含的任一状态而言， 第k子过程上对应于该状态的最优策略必然 包含在上述全过程最优策略p1*中，即为)(,),(),()(11nnkkkkkksusususp29 如第一节所述，基于上述原理，提出了一 种逆序递推法；这里可以指出，该法的关 键在于给出一种递推关系。一般把这种递 推关系称为动态规划的函数基本方程。 3.函数基本方程 在例5.2中，用标号法求解最短路线的计 算公式

23、可以概括写成：(5-6) 其中， 在这里表示从状态sk到 由决策uk(sk)所决定的状态sk+1之间的距离。 是边界条件，表示全过程到 第四阶段终点结束。 2 2、动态规划的基本原理动态规划的基本原理1 , 2 , 3 , 4),()(,(min)(0)(111)(55ksufsusgsfsfkkkkkkksUukkkkk)(,(kkkksusg0)(55sf30 一般地，对于n个阶段的决策过程，假设只考虑指标函数是“和”与“积”的形式，第k阶段和第k+1阶段间的递推公式可表示如下： (1)当过程指标函数为下列“和”的形式时， 相应的函数基本方程为 （5.7） 2 2、动态规划的基本原理动态规

24、划的基本原理)(,()()(kkkksPpkkspsRoptsfkKknkiiiiusg),(1 , 2 , 1,),()(,()(0)(11111nnksufsusgoptsfsfkkkkkkkUukknnkk31 (2) 当过程指标函数为下列“积”的形式时, 相应的函数基本方程为 （5.8） 可以看出，和、积函数的基本方程中边界 条件(即 的取值)是不同的。 2 2、动态规划的基本原理动态规划的基本原理)(,()()(kkkksPpkkspsRoptsfkKknkiiiiusg),(1 , 2 , 1,),()(,()(1)(11111nnksufsusgoptsfsfkkkkkkkUuk

25、knnkk)(11nnsf323 3、动态规划方法的基本步骤、动态规划方法的基本步骤 一动态规划的建模一动态规划的建模 标号法仅适用于求解象最短路线问题那样可以用网络图表示的多阶段决策问题。但不少多阶段决策问题不能用网络图表示。此时,应该用函数基本方程来递推求解.一般来说,要用函数基本方程逆推求解,首先要有效地建立动态规划模型,然后再递推求解,最后得出结论.然而,要把一个实际问题用动态规划方法来求解,还必须首先根据问题的要求。把它构造成动态规划模型,这是非常重要的一步。正确地建立一个动态规划模型,往往问题也就解决了一大半,而一个正确的动态规划模型,应该满足哪些条件呢?333 3、动态规划方法的

26、基本步骤、动态规划方法的基本步骤1应将实际问题恰当地分割成n个子问题(n个阶段)。通常是根据时间或空间而划分的，或者在经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数n，即k=n。2正确地定义状态变量sk，使它既能正确地描述过程的状态，又能满足无后效性动态规划中的状态与一般控制系统中和通常所说的状态的概念是有所不同的，动态规划中的状态变量必须具备以下三个特征：343 3、动态规划方法的基本步骤、动态规划方法的基本步骤(1)要能够正确地描述受控过程的变化特征(2)要满足无后效性即如果在某个阶段状态已经给定，那么在该阶段以后，过程的发展不受前面各段状态的影响，如果所选的变量不具

27、备无后效性，就不能作为状态变量来构造动态规划的模型。(3)要满足可知性即所规定的各段状态变量的值，可以直接或间接地测算得到一般在动态规划模型中，状态变量大都选取那种可以进行累计的量。此外，在与静态规划模型的对应关系上，通常根据经验，线性与非线性规划中约束条件的个数，相当于动态规划中状态变量sk的维数而前者约束条件所表示的内容，常就是状态变量sk所代表的内容。353 3、动态规划方法的基本步骤、动态规划方法的基本步骤3正确地定义决策变量及各阶段的允许决策集合Uk(sk)，根据经验，一般将问题中待求的量，选作动态规划模型中的决策变量。或者在把静态规划模型(如线性与非线性规划)转换为动态规划模型时，

28、常取前者的变量xj为后者的决策变量uk。4. 能够正确地写出状态转移方程，至少要能正确反映状态转移规律。如果给定第k阶段状态变量sk的值，则该段的决策变量uk一经确定，第k+1段的状态变量sk+1的值也就完全确定，即有sk+1=Tk(sk,uk)363 3、动态规划方法的基本步骤、动态规划方法的基本步骤5根据题意,正确地构造出目标与变量的函数关系目标函数，目标函数应满足下列性质：(1)可分性，即对于所有k后部子过程，其目标函数仅取决于状态sk及其以后的决策 uk,uk+1,un,就是说它是定义在全过程和所有后部子过程上的数量函数。(2)要满足递推关系，即(3)函数 对其变元Rk+1来说要严格单

29、调。nkkuuu,1),(,),(111111,nkkkkknkkkknkssRussususR),(,111nkkkkkssRus376写出动态规划函数基本方程例如常见的指标函数是取各段指标和的形式 其中 表示第i阶段的指标，它显然是满足上述三个性质的。所以上式可以写成 ：3 3、动态规划方法的基本步骤、动态规划方法的基本步骤nkiiiikkusgsR),()(),(iiiusg),(),(111nkkkkkkssRusgR38 二动态规划方法的基本步骤二动态规划方法的基本步骤 为进一步说明动态规划模型建立的基本方法及其求解过程,下面通过实际例子用上述方法具体给出求解动态规划方法的基本步骤：

30、 例例5.35.3 有某种机床,可以在高低两种不同的负荷下进行生产,在高负荷下生产时,产品的年产量为g,与年初投入生产的机床数量u1的关系为g=g(u1)=8u1,这时,年终机床完好台数将为au1,(a为机床完好率，0a1,设a=0.7).在低负荷下生产时,产品的年产量为h,和投入生产的机床数量u2的关系为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生生 产产 库库 存存 问问 题题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 生生 产产 库库 存存 问问 题题112根据题意 x1=2所以 D1(x1)=d1| 6d17由此 d1=7f1(x1)=-7d1-18x1+442 =-77182442 =357将以上结果总结成下表：k1234567ck11181317201015rk0853274xk2959974dk713-x2=4 14-x3=9 12-x4=3 9-x5=0 11-x6=40生生 产产 库库 存存 问问 题题113设设 备备 更更 新新 问问 题题114 一台设备的价格为P，运行寿命为n年，每年的维修费用是设备役龄的函数，记为C(t)，新设备的役龄为t=0。

33、旧设备出售的价格是设备役龄的函数，记为S(t)。在n年末，役龄为t的设备残值为R(t)。现有一台役龄为T的设备，在使用过程中，使用者每年都面临“继续使用”或“更新”的策略，设设 备备 更更 新新 问问 题题115阶段 k：运行年份；状态变量 xk：设备的役龄 t；决策变量 dk：dRplaceKK eepk(R e)()更 新继 续 使 用状态转移方程：xdRxdKkkkk111阶段指标：vP CS xdRC xdKP CS tdRC tdKkkkkkkk( )()()( )( )( )00116递推方程： fxPCS xfxdRC xfxdKPCS tfdRC tftdKkkkkkkkkkk

34、kkkk()min( )()()()()min( )( )( )( )()0011111111 终端条件： fn(t)=-R(t) 设设 备备 更更 新新 问问 题题117例设具体数据如下：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 更新 更新 继续 更新 继续 决策 2 更新 继续 更新 更新 继续 这两个决策是 设设 备备 更更 新新 问问 题题128第六章 排队论基本概念输入过程和服务时间分布泊松输入指数服务排队模型其他模型选介排队系统的优化目标与最优化问题本章内容重点129 排队论(Queuing Theory)，又称随 机 服

41、 务 系 统 理 论 ( R a n d o m Service System Theory),是一门研究拥挤现象(排队、等待)的科学。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。前前 言言130 排队是我们在日常生活和生产中经常遇到的现象。例如，上、下班搭乘公共汽车；顾客到商店购买物品；病员到医院看病；旅客到售票处购买车票；学生去食堂就餐等就常常出现排队和等待现象。除了上述有形的排队之外，还有大量的所谓“无形”排队现象，如几个顾客打电话到出租汽车站要求派车，如果出租汽车站无足够车辆、则部分顾客只得在各自的要车处等待，他们分散在不同地方，却形成

42、了一个无形队列在等待派车。排队的不一定是人，也可以是物：前前 言言131 例如，通讯卫星与地面若干待传递的信息；生产线上的原料、半成品等待加工；因故障停止运转的机器等待工人修理；码头的船只等待装卸货物；要降落的飞机因跑道不空而在空中盘旋等等。前前 言言132 显然，上述各种问题虽互不相同，但却都有要求得到某种服务的人或物和提供服务的人或机构。排队论里把要求服务的对象统称为“顾客”,而把提供服务的人或机构称为“服务台”或“服务员”。不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统，见图61至图65。

43、前前 言言133 类似地还可画出许多其它更复杂形式的排队系统，如串并混联的系统，网络排队系统等。尽管各种排队系统的具体形式不同，但都可由图66加以描述。图61 单服务台排队系统前前 言言134图62 单队列S个服务台并联的排队系统图6-3 S个队列S个服务台的并联排队系统前前 言言135图64 单队多个服务台的串联排队系统 图65 多队多服务台混联、网络系统前前 言言136图66 随机服务系统前前 言言137 通常称由图66表示的系统为一随机聚散服务系统，任排队系统都是一个随机聚散服务系统。这里，“聚”表示顾客的到达，“散”表示顾客的离去，所谓随机性则是排队系统的一个普遍特点，是指顾客的到达情

44、况(如相继到达时间间隔)与每个顾客接受服务的时间往往是事先无法确切知道的，或者说是随机的。一般来说，排队论所研究的排队系统中，顾客到来的时刻和服务台提供服务的时间长短都是随机的，因此这样的服务系统被称为随机服务系统。前前 言言138 面对拥挤现象，人们总是希望尽量设法减少排队，通常的做法是增加服务设施，但是增加的数量越多，人力、物力的支出就越大，甚至会出现空闲浪费，如果服务设施太少，顾客排队等待的时间就会很长，这样对顾客会带来不良影响。于是，顾客排队时间的长短与服务设施规模的大小，就构成了设计随机服务系统中的一对矛盾。如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排

45、队时间与服务设施费用大小这对矛盾，这就是随机服务系统理论排队论所要研究解决的问题。前前 言言139 排队论是1909年由丹麦工程师爱尔朗(A.KErlang)在研究电活系统时创立的，几十年来排队论的应用领域越来越广泛，理论也日渐完善。特别是自二十世纪60年代以来，由于计算机的飞速发展，更为排队论的应用开拓了宽阔的前景。前前 言言1401 1、基、基 本本 概概 念念 一 排队系统的描述 （一）、系统特征和基本排队过程 实际的排队系统虽然千差万别，但是它们有以下的共同特征： (1)有请求服务的人或物顾客； (2)有为顾客服务的人或物，即服务员或服务台； (3)顾客到达系统的时刻是随机的，为每一位

46、顾客提供服务的时间是随机的，因而整个排队系统的状态也是随机的。排队系统的这种随机性造成某个阶段顾客排队较长，而另外一些时候服务员(台)又空闲无事。141 任何一个排队问题的基本排队过程都可以用图6-6表示。从图6-6可知，每个顾客由顾客源按一定方式到达服务系统，首先加入队列排队等待接受服务，然后服务台按一定规则从队列中选择顾客进行服务，获得服务的顾客立即离开。1 1、基、基 本本 概概 念念142 （二）、排队系统的基本组成部分 通常，排队系统都有输入过程、服务规则和服务台等3个组成部分： 1输入过程这是指要求服务的顾客是按怎样的规律到达排队系统的过程，有时也把它称为顾客流一般可以从3个方面来

47、描述个输入过程。 (1)顾客总体数，又称顾客源、输入源。这是指顾客的来源。顾客源可以是有限的，也可以是无限的。例如，到售票处购票的顾客总数可以认为是无限的，而某个工厂因故障待修的机床则是有限的。1 1、基、基 本本 概概 念念143 (2)顾客到达方式。这是描述顾客是怎样来到系统的，他们是单个到达，还是成批到达。病人到医院看病是顾客单个到达的例子。在库存问题中如将生产器材进货或产品入库看作是顾客，那么这种顾客则是成批到达的。 (3)顾客流的概率分布，或称相继顾客到达的时间间隔的分布。这是求解排队系统有关运行指标问题时，首先需要确定的指标。这也可以理解为在一定的时间间隔内到达K个顾客(K=1、2

48、、)的概率是多大。顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若干种。1 1、基、基 本本 概概 念念144 2.服务规则这是指服务台从队列中选取顾客进行服务的顺序。一般可以分为损失制、等待制和混合制等3大类。 (1)损失制。这是指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来。典型例子是，如电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再打，就需重新拔号，这种服务规则即为损失制。1 1、基、基 本本 概概 念念145 (2)等待制。这是指当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。例如，排队等待售票

49、，故障设备等待维修等。等待制中，服务台在选择顾客进行服务时，常有如下四种规则： 先到先服务。按顾客到达的先后顺序对顾客进行服务，这是最普遍的情形； 后到先服务。仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况；1 1、基、基 本本 概概 念念146 随机服务。即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就是一例； 优先权服务。如老人、儿童先进车站；危重病员先就诊；遇到重要数据需要处理计算机立即中断其他数据的处理等，均属于此种服务规则。1 1、基、基 本本 概概 念念147 (3)混合制这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但

50、又不允许队列无限长下去。具体说来，大致有三种： 队长有限。当排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。例如最多只能容纳K个顾客在系统中，当新顾客到达时，若系统中的顾客数(又称为队长)小于K，则可进入系统排队或接受服务；否则，便离开系统，并不再回来。如水库的库容是有限的，旅馆的床位是有限的。1 1、基、基 本本 概概 念念148 等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来。如易损坏的电子元器件的库存问题，超过一定存储时间的元器件被自动认为失效。又如顾客到饭馆就餐，等了一定时间后

51、不愿再等而自动离去另找饭店用餐。 1 1、基、基 本本 概概 念念149 逗留时间(等待时间与服务时间之和)有限。例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为t时，若在这个时间内未被击落，也就不可能再被击落了。 不难注意到，损失制和等待制可看成是混合制的特殊情形，如记s为系统中服务台的个数，则当K=s时，混合制即成为损失制；当K=时，混合制即成为等待制.1 1、基、基 本本 概概 念念150 3服务台情况服务台可以从以下3方面来描述： (1) 服务台数量及构成形式。从数量上说，服务台有单服务台和多服务台之分。从构成形式上看，服务台有：a)单队单服务台式，b)单队多服务台并联式，c

52、)多队多服务台并联式，d)单队多服务台串联式，e)单队多服务台并串联混合式以及多队多服务台并串联混合式等等。见图6-1至图6-5所示。 1 1、基、基 本本 概概 念念151 (2) 服务方式。这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。如公共汽车一次就可装载一批乘客就属于成批服务。 (3) 服务时间的分布。一般来说，在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布、有定长分布、负指数分布、K级爱尔良分布、一般分布(所有顾客的服务时间都是独立同分布的)等等。1 1、基、基 本本 概概 念念152 （三）、排队系统的描述符号与分类 为了区别各种排队系统，根据输入过程

53、、排队规则和服务机制的变化对排队模型进行描述或分类，可给出很多排队模型。为了方便对众多模型的描述，肯道尔（DGKendall）提出了一种目前在排队论中被广泛采用的“Kendall记号”，完整的表达方式通常用到6个符号并取如下固定格式：/各符号的意义为：1 1、基、基 本本 概概 念念153表示顾客相继到达间隔时间分布，常用下列符号：M表示到达过程为泊松过程或负指数分布；D表示定长输入；Ek表示k阶爱尔朗分布；G表示一般相互独立的随机分布；表示服务时间分布，所用符号与表示顾客到达间隔时间分布相同。M表示服务过程为泊松过程或负指数分布；D表示定长分布；Ek 表示k阶爱尔朗分布；G表示一般相互独立的

54、随机分布；1 1、基、基 本本 概概 念念154表示服务台(员)个数：“1”则表示单个服务台，“s”。(s1)表示多个服务台。表示系统中顾客容量限额，或称等待空间容量；如系统有K个等待位子，则 0K0为一常数，表示单位时间内到达顾客的平均数，又称为顾客的平均到达率。 对于泊松流，不难证明其相继顾客到达时间间隔i，i=1,2,是相互独立同分布的，其分布函数为负指数分布： （6-6）!)()(KtetVKtk, 2 , 1 , 0K（6-5） 0, 00,1)(ttetFti), 2 , 1(i2 2、输入过程和服务时间分布、输入过程和服务时间分布1723.爱尔朗输入. 这是指相继顾客到达时间间隔

55、相互独立，具有相同的分布，其分布密度为 （6-7） 其中k为非负整数。 可以证明，在参数为的泊松输人中，对任意的j与k,设第j与第j+k个顾客之间的到达间隔为 。则随机变量Tk的分布必遵从参数为的爱尔朗分布，其分布密度为：0)!1()()(1teKttatK)(21kkkTT2 2、输入过程和服务时间分布、输入过程和服务时间分布173 例某排队系统有并联的k个服务台，顾 客流为泊松流，规定第i,K+i,2K+i,个顾客排入第i号台(i=1,2,K)，则第K台所获得的顾客流，即为爱尔朗输入流，其他各台，从它的第一个顾客到达以后开始所获得的流也为爱尔朗输入流。 此外，爱尔朗分布中，当K1时将化为负

56、指数分布。0)!1()()(1teKttatK2 2、输入过程和服务时间分布、输入过程和服务时间分布1744.一般独立输入，即相继顾客到达时间间隔相互独立、同分布，分布函数F(t)是任意分布，因此，上面所述的所有输入都是一般独立分布的特例。5.成批到达的输入这时指排队系统每次到达的顾客不一定是一个，而可能是一批，每批顾客的数目n是一个随机变量。其分布为： 到达时间间隔可能是上述几类输入中的一种。2 2、输入过程和服务时间分布、输入过程和服务时间分布（6-8）kaknP , 2 , 1 , 0K175 二、服务时间分布 1定长分布每一个顾客的服务时间 都是常数，此时服务时间t的分布函数 为： （

57、6-9） 2负指数分布即各个顾客的服务时间相互独立，具有相同的负指数分布： (6-10) 其中0为一常数，服务时间t的数学期望称为平均服务时间。显然，对于负指数分布2 2、输入过程和服务时间分布、输入过程和服务时间分布xxxtPxB01)()(0,00,1)(xxexBx176 3.爱尔朗分布. 即每个顾客的服务时间相互独立，具有相同的爱尔朗分布。其密度函数为 其中0为一常数，此种的平均服务时间为： K=1时爱尔朗分布化归为负指数分布当K时，得到长度为1/的定长服务。2 2、输入过程和服务时间分布、输入过程和服务时间分布001)()(dxxexxdBtEmx(6-11)(6-12)0,)!1(

58、)()(1xekxkkxbxkk01)()(dxxxbtE(6-13)177 4.一般服务分布所有顾客的服务时间都是相互独立具有相同分布的随机变量，其分布函数记B(X)，前面所述的各种服务分布都是一般服务分布的特例。 5.多个服务台的服务分布可以假定各个服务台的服务分布参数不同或分布类型不同。 6.服务时间依赖于队长的情况指服务员排队的人愈多，服务的速度也就愈快。2 2、输入过程和服务时间分布、输入过程和服务时间分布178 三、排队论研究的基本问题 排队论研究的首要问题是排队系统主要数量指标的概率规律，即研究系统的整体性质，然后进一步研究系统的优化问题。与这两个问题相关的还包括排队系统的统计推

59、断问题。(1)通过研究主要数量指标在瞬时或平稳状态下的概率分布及其数字特征，了解系统运行的基本特征。(2)统计推断问题，建立适当的排队模型是排队论研究的第一步，建立模型过程中经常会碰到如下问题：检验系统是否达到平稳状态；检验顾客相继到达时间间隔的相互独立性；确定服务时间的分布及有关参数等。2 2、输入过程和服务时间分布、输入过程和服务时间分布179(3)系统优化问题，又称为系统控制问题或系统运营问题，其基本目的是使系统处于最优或最合理的状态。系统优化问题包括最优设计问题和最优运营问题，其内容很多，有最少费用问题、服务率的控制问题、服务台的开关策略、顾客(或服务)根据优先权的最优排序等方面的问题

60、。 对于一般的排队系统运行情况的分析，通常是在给定输入与服务条件下，通过求解系统状态为n(有n个顾客)的概率Pn(t)，再进行计算其主要的运行指标:： 2 2、输入过程和服务时间分布、输入过程和服务时间分布180 (1)系统中顾客数(队长)的期望值L；(2)排队等待的顾客数(排队长)的期望值Lq；(3)顾客在系统中全部时间(逗留时间)的期望值W；(4)顾客排队等待时间的期望值Wq。 排队系统中，由于顾客到达分布和服务时间分布是多种多样的，加之服务台数。顾客源有限无限，排队容量有限无限等的不同组合，就会有不胜枚举的不同排队模型，若对所有排队模型都进行分析与计算，不但十分繁杂而且也没有必要。下面拟