运筹学全套课件

第八章标准服务系统

M/M/n系统鱼与熊掌兼得？28.1M/M/n损失制

8.1.1M/M/n损失制，无限源

(M/M/n:/n/FIFO)令从顾客源来的顾客到达率为

，每台的服务率为

则有

j=

,j=0,1,...,n–1;

n=0，

j=j,j=1,...,n将

j,

j

代入生灭方程，得式中

=

/

称为业务量(traffic)，是无量纲量；表示单位时间内要求系统提供的服务时间；

和

的单位必须一致；由于纪念Erlang，用爱尔兰作单位(Erl)3

系统的服务质量系统的质量用顾客的损失率来度量，有两种度量方法按时间计算的损失率pn，即单位时间内服务台全被占用的时间按顾客计算的损失率B，即单位时间内损失的顾客数与到达顾客数之比在本系统中有B=pn=En(

)，称为爱尔兰损失公式不是所有系统都有B=pn

的性质工程上经常是已知

，给定B，求所需最少的服务台n求n

一般有三种方法：迭代计算，查图，查表4

求所需服务台的方法1、查图，如书上262页2、迭代计算无法由En(

)给出n

的逆函数，因此采用逐次试算的方法注意，En(

)有较简单的递推公式3、工程上经常采用查表的方法爱尔兰表最左边一列为服务台数n，最上面一行为服务质量的不同等级，即B爱尔兰表中元素的值为

，表示服务台数为n，服务质量为B时，系统最大所能承担的业务量；工程上经常用A表示

，A

是加入话务量5爱尔兰损失表n=3,B=0.01,查表得

=0.455已知n

和

如何求B，线性内插法；例：n=3，

=2.5，由表可知B

落在0.2~0.3之间，若假设在这区间所承担的业务量与B

成线性关系，则有线性内插公式B2.5=0.2+(0.3-0.2)(2.5-1.930)/(2.633-1.930)=0.2816例1M/M/n损失制无限源系统，已知n=3，

=5人/小时，平均服务时长30分钟/人，试求：(1)系统中没有顾客的概率；(2)只有一个服务台被占用的概率；(3)系统的损失率解：由题意可知

=60/30=2人/小时，所以

=

/

=2.5Erl(1)p0=(1+2.5+2.52/2+2.53/3!)1=0.108(2)p1=

p0=2.50.108=0.27(3)B=E3(2.5)=p0

3/3!=0.1082.604=0.28例2

两市话局间的忙时平均呼叫次数为240，每次通话平均时长为5分钟，规定两局间中继线的服务等级为B

0.01,问：(1)应配备多少条中继线？(2)中继线群的利用率为多少？解：中继线群上的加入话务量为

=2405/60=20Erl，

(1)查262页图，n=30条；

(2)查爱尔兰表可知：n=30，B=0.01时可承担A=20.337，B=0.005时可承担A=19.034，因此，E30(20)=0.005+0.005(2019.034)/(20.33719.034)=0.008707

中继线群利用率

=

(1B)/n=20(1-0.008707)/30=0.6608627

服务台利用率与服务台数量的关系

n

图当给定n

和B

后，系统所能承担的业务量

可以通过爱尔兰公式求出，从而可计算出服务台利用率

；若保持B

不变，不断增加服务台数n，

也会发生变化，就可以得到

n

图如下；通过观察，有几点结论：1、B不变时，

随

n增加；说明大电路群效率高2、n不变时，

随

B增加；说明效率与质量是矛盾的；(高效路由)3、

具有边际递减规律4、

越大，系统抗过负荷能力越差8

系统过负荷特性

B

图过负荷是指系统加入的业务量A,超过给定服务质量所能承担的业务量A过负荷用过载业务量与标准应承担的业务量的比值来表示，即

=(A

A)/A=A/A

En(A)=B,En(A)=B

由图可见，在同样标准的服务质量和同样的过负荷率下，大系统的质量劣化严重；说明效率与可靠性是矛盾的9例3

某服务部门把顾客分为两组，分别组成两个单独的服务系统。各系统的到达率分别为

1=4人/小时，

2=8人/小时，每人的平均占用时长都为6分钟；给定损失率为B

0.01，试求：(1)分组服务时每组应配备的服务台数；(2)合并为一个服务系统时，各种条件不变，应配备的服务台数；(3)比较两种组织方式的服务台利用率。解：(1)分组时：

1=40.1=0.4Erl,

2=80.1=0.8Erl

查爱尔兰表，得n1=3台，n2=4台，共需7台。

B1=0.005+0.005(0.40.349)/(0.4550.349)=0.0074

B2=0.005+0.005(0.80.701)/(0.8690.701)=0.00795

=[

1(1B1)+

2(1B2)]/(n1+n2)=0.17(2)合组时：

=120.1=1.2Erl,

查爱尔兰表，得n

=5台，节省了2台。

B

=0.005+0.005(1.21.132)/(1.3611.132)=0.006485

=(1B)/n=0.238108.2.1M/M/n损失制，有限源

(M/M/n:N/n/FIFO)例交换机内部有n

条绳路，N条入中继线，N>n；每条入中继线上的呼叫到达强度为

，且为波松分布，通话时长为负指数分布(参数为m)，问入中继线上呼叫的损失率为多少？上述例子就是一个M/M/n损失制，有限源系统。当已经接受绳路服务的中继线在通话中，该中继线上就不会有新的呼叫。因此，整个系统的呼叫到达率是与系统中被服务的中继线数相关的。这就是有限源系统的特点显然，系统在各状态下的到达率和离去率分别为

j=(N–j)

,j=0,1,...,n–1,

n=0，

j=j,j=1,...,n将

j,

j

代入生灭方程，得11

当j=n

时，pn表示按时间计算的损失率下面分析按顾客计算的损失率BB=单位时间平均损失顾客数/单位时间平均到达顾客数在有限源系统中，顾客到达率随系统状态变化，因此有平均顾客到达率

，又称为有效到达率

12可见，在有限源情况下，系统按时间计算的损失率pn

和按顾客计算的损失率B是不相等的；其原因就是输入过程随系统状态而变从一个极端情况看，若N=n，则B=0，但pn

0虽然爱尔兰损失公式和恩格谢特损失公式都是在负指数服务时长假设下推导出来的，但已证明服务时间是其它一般平稳分布，结论仍是正确的服务台利用率：13例4

有一电话查询服务处集中答复三个查询点的所有查询事项。查询服务处与查询点之间用电话联系。查询服务处只有一名值班员答复所有的查询。已知每个查询点平均每小时有两次查询，每次平均通话12分钟，问：(1)值班员空闲的概率；(2)值班员打电话的概率；(3)查询时值班员忙的概率；(4)服务处查询电话的平均到达率；(5)值班员的工时利用率。解：系统是有限源

M/M/1损失制。q=

/

=(2/60)12=0.4Erl (1)p0=1/(1+Nq)=0.4545148.2M/M/n等待制，无限源，无限容量

(M/M/n://FIFO)

8.2.1系统稳态概率及等待概率令从顾客源来的顾客到达率为

，每台的服务率为

则有

j=

,j0;

j=j,j<n；

j=n,j

n将

j,

j

代入生灭方程，得15当

n

时，则p0

中第二项不收敛，系统中队长将趋于无穷当

<n

时，系统有稳态，处于动态平衡；无限容量等待制，每个顾客早晚都会得到服务，因此系统完成的业务量也是

顾客进入系统必须排队等待的概率为D

爱尔兰等待公式排队等待的概率是等待制系统的重要指标之一n=1时，D=

公式

D的记忆法168.2.2系统的各种指标等待制系统的指标有：平均逗留队长；平均等待队长；平均逗留时长；平均等待时长和服务台利用率等n=1时，D=

，Ld=

/(1

)，Lq=

2/(1

)，Wq=

/(

)例5

书上273页178.2.3等待时间的概率分布前面只推导了要等待的概率D=P{W>0}，但在很多情况下我们希望知道等待时长的分布，即P{W>t}系统中有j

个顾客，j

n

时，新来顾客要排队等待，采用FIFO规则；令新顾客到达时为0时刻，显然，只有服务台上离去j

n个顾客时，新顾客才排到队首当n

个服务台连续服务时，顾客离去率为n，因此服务台空出的过程是波松流，在(0,t)内空出i

次的概率为18

等待时长分布的推导19例6

某储蓄所内，已知忙时顾客到达率

=40人/小时，窗口营业员服务率为

=16人/小时，要求：(1)工时利用率不低于60%；(2)顾客平均等待时间不超过5分钟；问：设几个窗口适当。解：系统是无限源

M/M/n

等待制。

=

/

=40/16=2.5Erl (1)

=

/n0.6，解出n4.17，故n

可取值3，4(2)n=3时，p0=(1++2/2!

+(

3/3!)(3/(3-2.5))1=0.04520例7

兴建一座港口码头，只有一个装卸泊位，要求设计泊位的生产能力，能力用日装卸船只数表示。已知单位装卸能力日平均生产费用为a=2000元；船只到港后若不能及时装卸，逗留一日要损失运输费b=1500元；预计船只的平均到达率为

=3只/日。设船只到达的间隔时间和装卸时间都服从负指数分布，问港口生产能力设计为多大时，每天总费用最小？解：系统是无限源

M/M/1等待制，生产能力用

(只/日)表示 目标函数：minC=a+bLd21例8M/M/1等待制系统,无限队长,顾客到达与队长有关该系统仍为无限源，但考虑到顾客对排队的心理，假设顾客到达率与队长成反比关系即

j=

0

/(1+j)，

0为队长为0时的顾客到达率从而系统的

j

和

j

为将

j

和

j

代入生灭方程，得第二章

线性规划的对偶理论及其应用窗含西岭千秋雪，门泊东吴万里船对偶是一种普遍现象232.1线性规划的对偶理论

2.1.1线性规划原问题与对偶问题的表达形式任何线性规划问题都有其对偶问题对偶问题有其明显的经济含义

假设有商人要向厂方购买资源A和B，问他们谈判原料价格的模型是怎样的？24

例2.1.1设A、B资源的出售价格分别为y1

和

y2显然商人希望总的收购价越小越好工厂希望出售资源后所得不应比生产产品所得少目标函数ming(y)=25y1+15y2252.1.1线性规划原问题与对偶问题的表达形式262.1.1线性规划原问题与对偶问题的表达形式272.1.2标准(max,)型的对偶变换目标函数由max型变为min型对应原问题每个约束行有一个对偶变量yi，i=1,2,…,m对偶问题约束为型，有n

行原问题的价值系数C变换为对偶问题的右端项原问题的右端项

b变换为对偶问题的价值系数原问题的技术系数矩阵A转置后成为对偶问题的技术系数矩阵原问题与对偶问题互为对偶对偶问题可能比原问题容易求解对偶问题还有很多理论和实际应用的意义2.1.3非标准型的对偶变换29

表2.1.1对偶变换的规则约束条件的类型与非负条件对偶非标准的约束条件类型对应非正常的非负条件对偶变换是一一对应的302.2线性规划的对偶定理

2.2.1弱对偶定理定理对偶问题(min)的任何可行解Y0，其目标函数值总是不小于原问题(max)任何可行解X0的目标函数值

为了便于讨论，下面不妨总是假设31

弱对偶定理推论max问题的任何可行解目标函数值是其对偶min问题目标函数值的下限；min问题的任何可行解目标函数值是其对偶max问题目标函数值的上限如果原max(min)问题为无界解，则其对偶min(max)问题无可行解如果原max(min)问题有可行解，其对偶min(max)问题无可行解，则原问题为无界解注：有可能存在原问题和对偶问题同时无可行解的情况322.2.2最优解判别定理定理若原问题的某个可行解X0的目标函数值与对偶问题某个可行解Y0的目标函数值相等，则X0,Y0分别是相应问题的最优解证：由弱对偶定理推论1，结论是显然的。即CX0

=Y0b

CX,Y0b=CX0

Yb

。证毕。

2.2.3主对偶定理定理如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解的目标函数值相等。证：由弱对偶定理推论1可知，原问题和对偶问题的目标函数有界，故一定存在最优解。现证明定理的后一句话。

33

主对偶定理的证明

证：现证明定理的后一句话。设X0为原问题的最优解，它所对应的基矩阵是B，X0=B

1

b，则其检验数满足C

CBB

1A0

令Y0=

CBB

1，则有Y0

A

C；而对原问题松弛变量的检验数有0

CBB

1I0，即Y0

0

。

显然Y0为对偶问题的可行解。因此有对偶问题目标函数值，g(Y0)=Y0b=CBB

1

b

而原问题最优解的目标函数值为

f(X0)=CX0=CBB

1

b故由最优解判别定理可知Y0为对偶问题的最优解。证毕。该定理的证明告诉我们一个非常重要的概念：对偶变量的最优解等于原问题松弛变量的机会成本即对偶变量的最优解是原问题资源的影子价格342.2.4互补松弛定理定理设X0,Y0分别是原问题和对偶问题的可行解，U0为原问题的松弛变量的值、V0为对偶问题剩余变量的值。X0,Y0分别是原问题和对偶问题最优解的充分必要条件是Y0

U0+

V0X0=0证：由定理所设，可知有

AX0+U0=bX0,U0

0(1)Y0A

V0

=CY0,V0

0(2)分别以Y0左乘(1)式，以X0右乘(2)式后，两式相减，得

Y0U0+V0X0

=Y0b

CX0若Y0U0+V0X0

=0，根据最优解判别定理，X0,Y0分别是原问题和对偶问题最优解。反之亦然。证毕。352.2.4互补松弛定理Y0

U0+

V0X0=0有什么应用若(Y0

)i>0，则(U0

)i=0，意味着原问题第i

约束行必须为=约束；对(X0

)i>0亦如此可用来简化问题的求解线性规划的高级算法：利用互补松弛定理，原问题与对偶问题同时解原问题为基础可行解，对偶问题为非可行解，但满足互补松弛条件；则当对偶问题为可行解时，取得最优解362.2.5原问题检验数与对偶问题的解在主对偶定理的证明中我们有：对偶(min型)变量的最优解等于原问题松弛变量的机会成本，或者说原问题松弛变量检验数的绝对值容易证明，对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值由于原问题和对偶问题是相互对偶的，因此对偶问题的检验数与原问题的解也有类似上述关系。更一般地讲，不管原问题是否标准，在最优解的单纯型表中，都有原问题虚变量(松弛或剩余)的机会成本对应其对偶问题实变量

(对偶变量)的最优解，原问题实变量(决策变量)的检验数对应其对偶问题虚变量

(松弛或剩余变量)的最优解。因此，原问题或对偶问题只需求解其中之一就可以了。37

例2.2.3原问题检验数与对偶问题的解3839402.3对偶单纯型算法

2.3.1基本思路原单纯型迭代要求每步都是基础可行解达到最优解时，检验数cj–zj

0(max)或cj–zj

0(min)但对于(min,)型所加的剩余变量无法构成初始基础可行解，因此通过加人工变量来解决大M法和二阶段法较繁能否从剩余变量构成的初始基础非可行解出发迭代，但保证检验数满足最优条件，cj–zj

0(max)或cj–zj

0(min)每步迭代保持检验数满足最优条件，但减少非可行度如何判断达到最优解如何保证初始基础解满足最优条件为什么叫对偶单纯型法b=B

1b

0412.3.2迭代步骤确定出变量找非可行解中最小者，即min{bi|bi<0}，设第i*行的最负，则i*行称为主行，该行对应的基变量为出变量，xi*确定入变量最大比例原则

设j*

列满足(2.3.1)式，j*

列称为主列，xj*

为出变量

以主元ai*j*

为中心迭代

检查当前基础解是否为可行解

若是，则当前解即为最优解否则，返回步骤142最大比例原则令V=C-CBB-1A

为检验数向量对min问题，V0称为正则，即满足最优判定条件可以证明，V

的迭代也满足四角运算法则令xr

为出变量，在第i*行；若选非基变量xj*为入变量必须满足什么条件才能保证迭代后的解仍为正则的？因此只需考虑非基变量xj

观察出变量xr

对应的检验数变化，因为有ai*r

=1，故

由于vj*

0，故必有ai*j*<0，即主元必须为负值

若xj

仍为基变量，则可知ai*j

=0

,43最大比例原则若xj

为非基变量，则当ai*j>

0时，显然有

结合上述的几个条件，则得到最大比例原则

若ai*j

<

0

时，则要求vj-vj*ai*j

/ai*j*

0,可解出注：这里的aij

都表示当前单纯性表中的技术系数44

例2.3.1对偶单纯型解法解：化原问题为适合对偶解法的标准型45

表2.3.1对偶单纯型法的单纯型表(min)答：最优解为x1=14,x3=8,x2=x4=0,OBJ=14第九章特殊随机服务系统秩序影响服务质量9.1

M/G/1

等待制，无限源，无限容量G表示一般独立分布，没有具体的分布函数，但知道该分布的数学期望

1/

和方差

2设到达率为

，平均服务时长为h=1/

，则系统业务量为

=h；同样，系统有稳态的条件是

<1

9.1.1系统中逗留顾客的平均数由于服务时长不具有马氏性，不能套用生灭方程求稳态pj以第n

个顾客离去瞬间系统内顾客数表示系统状态，如图Ln

为第n个顾客离开系统瞬间的系统排队队长Yn+1

为第n+1个顾客服务时间内到达的顾客数47E[Yn+1]代表一个服务时长内到达系统的平均顾客数E[U(Ln)]代表系统中有顾客逗留的概率，也即服务台被占用的概率；服务台被占用的概率就是

，所以有48Ld，Lq

不但与

有关，而且与

2有关(5),(6)式以俄国数学家朴拉切克—欣钦命名49顾客等待的概率为D=E[U(Ln)]=

，不需等待的概率为1

9.1.2平均剩余服务时间对于负指数服务时间分布，众所周知剩余服务时间仍服从原来的分布，即h=1/

但在M/G/1中，平均剩余服务时间Tr

需要研究，它与顾客排队等待的时间Wq

有关；显然，Wq分为两部分：(1)等待服务台空出的平均时间，(2)排在队中所有顾客的服务时间50对于定长分布，

=1，Tr=h/2对于负指数分布，

=2，Tr=h对于k

阶爱尔兰分布，

=？，Tr=？519.2优先权服务系统

9.2.1M/G/1非强占优先系统设有m

级顾客，1级顾客为最高优先权，每级内采用FIFO各级顾客到达率为

i，波松流，各级顾客的平均服务时长都为hi，方差为

i2；系统总业务量

=

i

hi，

<1利用上节推导出的等待服务台空出的时间T1，可知W1=T1/(1

1)，递推得第k

级顾客的平均等待时间Wk52

k

级顾客的平均等待时间与比之高级顾客的业务量有关平均服务时间短的顾客有高优先权，可以减少总的排队时间优先权级别不宜太多，插队现象就是增加等级，使总等待时间增加例1

在M/G/1服务系统中，有两类顾客，都是波松到达过程。第一类顾客

1=2个/秒，定长服务h1=0.1秒/个；第二类顾客

2=0.5个/秒，负指数服务h2=1.2秒/个，试求：(1)不分优先权时的顾客平均等待时间；(2)非强占优先权，第一类顾客或第二类顾客优先时，各类顾客的平均等待时间。解：

1=2，h1=0.1，

1=0.2Erl，

12=0；

2=0.5，h2=1.2，

2=0.6Erl，

22=h22=1.22=1.44 (1)不分优先权，属纯M/G/1系统，由T1

公式，得

T1=(2/2)(0+0.12)+(0.5/2)(1.22+1.22)=0.73秒

Wq=T1/(1

)=0.73/(10.20.6)=3.65秒

(2)非强占优先，第一类顾客优先

W1=T1/(1

1)=0.73/(10.2)=0.9125秒

W2=T1/(1

1)(1

1

2)=0.73/(10.2)(10.8)=4.563秒 非强占优先，第二类顾客优先

W2=T1/(1

2)=0.73/(10.6)=1.825秒

W1=T1/(1

2)(1

1

2)=0.73/(10.6)(10.8)=9.125秒539.2.3M/M/n

服务系统，非强占优先权与M/G/1非强占优先权系统的基本假设大多数一样，但有n

个独立并联服务台，各级顾客的平均服务时间都是h各级顾客到达率为

i，系统总到达率

=

i，总业务量

=

i

h，

<n上节(10)式仍成立，有54令Wq

为全体顾客的平均等待时间，Lq

为平均队长，则9.3溢流通路计算9.3.1部分利用度的概念当服务台可以为所有进入系统的顾客服务时，称为全利用度系统(Fullyprovided)当服务台部分分组使用，部分公用，则称为部分利用度系统，如图所示55全利用度系统利用率最高，但不易组织分组专用效率低，但容易组织部分利用度系统综合两者的优点9.3.2溢流通路的概念在电信网的组织中，由于经济的原因，并不是任两个交换机之间都有直达的中继线群在话务量适当的点间开高效直达路由是经济的。所谓高效路由是指呼损率大的中继线群(如B>0.02)，但当该中继线忙时，允许通过迂回路由接通呼叫；在高效路由上呼损而转移到迂回路由上的话务流量称为溢流，如图所示溢流具有突发性，不再是波松流，目前仍不清楚其分布具有溢流的系统是一个部分利用度系统569.3.3溢流通路的计算已知A23和给定的B23，可以用爱尔兰损失公式直接求n23如何求溢流通路(2,1)的容量n21，因为其上除直达业务量A21，还有(2,3)的溢出流量Ao23

，而Ao23

不是波松流，不能简单迭加，因而也不能直接用爱尔兰损失公式求n21威尔金森(R.IWilkinson,1956)提出了“等效随机流法”的近似计算方法就是给出一种溢出流的迭加方法，然后求一个等效波松流A

和一个等效电路群n，使A

通过n

后的溢流等于原溢出流的迭加，如图所示57等效随机流的计算方法与步骤1、计算(2,3)的溢流均值和方差由于n23

是A23

的专用通路，给定B23，有58威尔金森给出求溢流方差的公式2、计算各通路上的溢流总和的均值和方差注意，波松流自身的方差等于均值，即A21=

2213、计算等效随机流A和等效通路数n波松流A

经过通路n

都会有公式(1),(2)给出的溢流如何根据已知溢流(Ao,

o2)反解A

和n

拉普(Y.Rapp,1964)给出了反解公式等效随机流的计算方法与步骤594、计算溢流通路的电路数N等效于将A

加载到n+N

的通路上，给定呼损B，有5、计算各通路的呼损将最终呼损AoN按各通路的溢流分摊拉普公式例1求溢流通路(A,D)的电路数NAD，要求B0.011、计算(D,B)(D,C)的溢流Ao1,

2o1

查表，并利用线性内插，得602、计算(A,D)的总溢流Ao,

2o3、计算等效流

A

和等效电路n例1求溢流通路(A,D)的电路数NAD，要求B0.014、计算溢流通路(A,D)所需通路数N615、计算(A,D),(D,B)(D,C)的呼损有不合理现象，低等级点间的呼损小于骨干上点间呼损例2网路优化问题1、各点间每条直达电路的成本不一样2、汇接局的交换机每个路端的成本比非汇接局(端局)要高很多3、因此，网路优化是线路成本和交换成本的平衡4、有三种基本结构：纯汇接(星型)、独立直达和高效直达5、高效直达中还可以进一步优化62第六章图与网路分析图是最直观的模型64BACD图论

GraphTheory哥尼斯堡七桥问题(KönigsbergBridgeProblem)LeonhardEuler(1707-1783)在1736年发表第一篇图论方面的论文，奠基了图论中的一些基本定理很多问题都可以用点和线来表示，一般点表示实体，线表示实体间的关联656.1图与网路的基本概念

6.1.1图与网路节点

(Vertex)物理实体、事物、概念一般用vi

表示边

(Edge)节点间的连线，表示有关联一般用eij

表示图

(Graph)节点和边的集合一般用G(V,E)表示点集V={v1,v2,…,vn}边集E={eij}网路

(Network)边上具有表示连接强度的权值，如wij又称加权图(Weightedgraph)666.1.2无向图与有向图所有边都没有方向的图称为无向图，如图6.1在无向图中eij=eji，或(vi,vj)=(vj,vi)当所有边都有方向时，称为有向图，用G(V,A)表示在有向图中，有向边又称为弧，用aij表示，i,j的顺序是不能颠倒的，图中弧的方向用箭头标识图中既有边又有弧，称为混合图

6.1.3端点，关联边，相邻，次图中可以只有点，而没有边；而有边必有点若节点vi,vj

之间有一条边eij，则称vi,vj

是eij的端点(endvertex)，而eij

是节点vi,vj的关联边(incidentedge)同一条边的两个端点称为相邻(adjacent)节点，具有共同端点的边称为相邻边一条边的两个端点相同，称为自环(self-loop)；具有两个共同端点的两条边称为平行边(paralleledges)既没有自环也没有平行边的图称为简单图(simplegraph)在无向图中，与节点相关联边的数目，称为该节点的“次”(degree)，记为d

；次数为奇数的点称为奇点(odd),次数为偶数的点称为偶点(even)；图中都是偶点的图称为偶图(evengraph)68

6.1.3端点，关联边，相邻，次有向图中，由节点向外指的弧的数目称为正次数，记为d+，指向该节点的弧的数目称为负次数，记为d–次数为0的点称为孤立点(isolatedvertex)

，次数为1的点称为悬挂点(pendantvertex)定理1：图中奇点的个数总是偶数个

6.1.4链，圈，路径，回路，欧拉回路相邻节点的序列

{v1

,v2

,…,vn

}构成一条链(link)，又称为行走(walk)；首尾相连的链称为圈(loop)，或闭行走在无向图中，节点不重复出现的链称为路径(path)；在有向图中，节点不重复出现且链中所有弧的方向一致，则称为有向路径(directedpath)首尾相连的路径称为回路(circuit)；69

走过图中所有边且每条边仅走一次的闭行走称为欧拉回路定理2：偶图一定存在欧拉回路(一笔画定理)

6.1.5连通图，子图，成分设有两个图G1(V1,E1),G2(V2,E2),若V2

V1,E2

E1，则G2是G1的子图无向图中，若任意两点间至少存在一条路径，则称为连通图(connectedgraph)，否则为非连通图(discon-nectedgraph)；非连通图中的每个连通子图称为成分

(component)链，圈，路径(简称路)，回路都是原图的子图平面图(planargraph)，若在平面上可以画出该图而没有任何边相交706.2树图与最小生成树一般研究无向图树图：倒置的树，根(root)在上，树叶(leaf)在下多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图716.2.1树的定义及其性质任两点之间有且只有一条路径的图称为树(tree)，记为T

树的性质：最少边的连通子图，树中必不存在回路任何树必存在次数为1的点具有n

个节点的树T的边恰好为

n

1条，反之，任何有n

个节点，n

1条边的连通图必是一棵树

6.2.2图的生成树树T是连通图G的生成树(spanningtree)，若T是G的子图且包含图G的所有的节点；包含图G中部分指定节点的树称为steinertree每个节点有唯一标号的图称为标记图，标记图的生成树称为标记树(labeledtree)Caylay定理：n(

2)个节点，有nn

2个不同的标记树72

6.2.2

图的生成树如何找到一棵生成树深探法(depthfirstsearch)：任选一点标记为0点开始搜索，选一条未标记的边走到下一点，该点标记为1，将走过的边标记；假设已标记到i

点，总是从最新标记的点向下搜索，若从i

点无法向下标记，即与i

点相关联的边都已标记或相邻节点都已标记，则退回到

i

1点继续搜索，直到所有点都被标记广探法(breadthfirstsearch)：是一种有层级结构的搜索，一般得到的是树形图736.2.3

最小生成树有n个乡村，各村间道路的长度是已知的，如何敷设光缆线路使n个乡村连通且总长度最短显然，这要求在已知边长度的网路图中找最小生成树

最小生成树的算法：Kruskal

算法：将图中所有边按权值从小到大排列，依次选所剩最小的边加入边集T，只要不和前面加入的边构成回路，直到T中有n

1条边，则T是最小生成树Kruskal

算法基于下述定理定理3

指定图中任一点vi，如果vj

是距vi最近的相邻节点，则关联边eij必在某个最小生成树中。推论将网路中的节点划分为两个不相交的集合V1和V2，V2=V

V1，则V1和V2间权值最小的边必定在某个最小生成树中。746.2.3

最小生成树最小生成树不一定唯一定理3推论是一个构造性定理，它指示了找最小生成树的有效算法Prim

算法：不需要对边权排序，即可以直接在网路图上操作，也可以在边权矩阵上操作，后者适合计算机运算

边权矩阵上的Prim算法：1、根据网路写出边权矩阵，两点间若没有边，则用表示；2、从v1

开始标记，在第一行打，划去第一列；3、从所有打的行中找出尚未划掉的最小元素，对该元素画圈，划掉该元素所在列，与该列数对应的行打；4、若所有列都划掉，则已找到最小生成树(所有画圈元素所对应的边)；否则，返回第3步。该算法中，打行对应的节点在V1中，未划去的列在V2中756.2.3

最小生成树Prim算法是多项式算法Prim算法可以求最大生成树网路的边权可以有多种解释，如效率次数受限的最小生成树—尚无有效算法最小Steiner树—尚无有效算法

766.3

最短路问题

6.3.1狄克斯特拉算法(Dijkstraalgorithm,1959)计算两节点之间或一个节点到所有节点之间的最短路令

dij

表示

vi

到vj

的直接距离(两点之间有边)，若两点之间没有边，则令dij

=

，若两点之间是有向边，则dji

=

；令dii

=0，s

表示始点，t

表示终点0、令始点Ts=0，并用框住，所有其它节点临时标记Tj=

；1、从vs

出发，对其相邻节点vj1

进行临时标记，有Tj1=ds,j1

；2、在所有临时标记中找出最小者，并用框住，设其为vr

。若此时全部节点都永久标记，算法结束；否则到下一步；3、从新的永久标记节点vr

出发，对其相邻的临时标记节点进行再标记，设vj2

为其相邻节点，则Tj2=min{Tj2,Tr+dr,j2}，返回第2步。77例1狄克斯特拉算法0

81510121511311378

Dijkstra最短路算法的特点和适应范围一种隐阶段的动态规划方法，而且是正向递推每次迭代只有一个节点获得永久标记，若有两个或两个以上节点的临时标记同时最小，可任选一个永久标记；总是从一个新的永久标记开始新一轮的临时标记，是一种深探法被框住的永久标记Tj

表示vs

到vj

的最短路，因此要求dij0，第k次迭代得到的永久标记，其最短路中最多有

k

条边，因此最多有n1

次迭代可以应用于简单有向图和混合图，在临时标记时，所谓相邻必须是箭头指向的节点；若第n1

次迭代后仍有节点的标记为，则表明vs

到该节点无有向路径如果只求vs

到vt

的最短路，则当vt

得到永久标记算法就结束了；但算法复杂度是一样的应用Dijkstra算法n1

次，可以求所有点间的最短路vs

到所有点的最短路也是一棵生成树，但不是最小生成树796.3.2Warshall-Floyd算法(1962)Warshall-Floyd算法可以解决有负权值边(弧)的最短路问题该算法是一种整体算法，一次求出所有点间的最短路该算法不允许有负权值回路，但可以发现负权值回路该算法基于基本的三角运算定义对给定的点间初始距离矩阵{dij}，令dii=

，

i。对一个固定点j，运算dik=min{dik,dij+djk},

i,k

j,称为三角运算。(注意，这里允许i=k)定理依次对j=1,2,…,n执行三角运算，则dik

最终等于i

到k

间最短路的长度。806.3.2Floyd-Warshall算法(1962)fori=1tondodii=;foralleij=0;forj=1tondofori=1tondoifi

jthenfork=1tondoifk

jthenbegin

dik=min{dik,dij+djk};

ifdik>dij+djktheneik=j

end;若网路中存在负回路，则计算中，某些dii会小于0，此时应中断算法显然，Floyd算法要进行n(n-1)2次加法和比较如何回溯找出任两点之间的最短路？在Floyd算法中设一伴随矩阵E={eik}，eik

记录了i

到

k

最短路中最后一个中间节点81小结最短路有广泛的应用(6.3.4节市话局扩容方案)最短路的多种形式：无向图，有向图无循环圈，有向图，混合图，无负边权，有负边权，有负回路，k-最短路等当存在负权值边时，Floyd算法比Dijkstra算法效率高，且程序极简单。但Dijkstra算法灵活若图是前向的，则Dijkstra算法也可以求两点间最长路一般情况下，两点间最长路是NP-complete，但最短路是P算法两点间k-最短路：分为边不相交的和边相交的

求边不相交的k-最短路非常容易：先求最短路，将该最短路中的边从网路删去，再用Dijkstra算法可求次最短路，以此类推826.3.4最短路应用举例——市话扩容(实装率=0.8)83最短路应用举例—市话扩容846.4网路的最大流和最小截

6.4.1网路的最大流的概念网路流一般在有向图上讨论定义网路上支路的容量为其最大通过能力，记为cij，支路上的实际流量记为fij图中规定一个发点s，一个收点t节点没有容量限制，流在节点不会存储容量限制条件：0

fij

cij平衡条件：

满足上述条件的网路流称为可行流，总存在最大可行流当支路上fij=cij

，称为饱和弧最大流问题也是一个线性规划问题viA(vi)B(vi)856.4.2截集与截集容量定义：把网路分割为两个成分的弧的最小集合，其中一个成分包含s

点，另一个包含t

点。一般包含s

点的成分中的节点集合用V表示，包含t

点的成分中的节点集合用V表示截集容量是指截集中正向弧的容量之和

福特-富克森定理：网路的最大流等于最小截集容量866.4.3确定网路最大流的标号法从任一个初始可行流出发，如0流基本算法：找一条从s

到t

点的增广链(augmentingpath)若在当前可行流下找不到增广链，则已得到最大流增广链中与s

到t方向一致的弧称为前向弧，反之后向弧

增广过程：前向弧f

ij=fij+q,后向弧f

ij=fij

q

增广后仍是可行流

87

最大流最小截的标号法步骤第一步：标号过程，找一条增广链1、给源点s

标号[s+,q(s)=]，表示从s点有无限流出潜力2、找出与已标号节点i

相邻的所有未标号节点j，若(1)(i,j)是前向弧且饱和，则节点

j

不标号；(2)(i,j)是前向弧且未饱和，则节点

j

标号为[i+,q(j)]，表示从节点i

正向流出，可增广q(j)=min[q(i),cij

fij]；(3)(j,i)是后向弧，若fji=0，则节点j

不标号；(4)(j,i)是后向弧，若fji>0，则节点j

标号为[i

,q(j)]，表示从节点j

流向

i，可增广q(j)=min[q(i),fji]；3、重复步骤2，可能出现两种情况：(1)节点t

尚未标号，但无法继续标记，说明网路中已不存在增广链，当前流v(f)就是最大流；所有获标号的节点在V

中，未获标号节点在V

中，V与V

间的弧即为最小截集；算法结束(2)节点t

获得标号，找到一条增广链，由节点t

标号回溯可找出该增广链；到第二步88

最大流最小截的标号法步骤第二步：增广过程1、对增广链中的前向弧，令f=f+q(t)，q(t)为节点t

的标记值2、对增广链中的后向弧，令f=f

q(t)3、非增广链上的所有支路流量保持不变第三步：抹除图上所有标号，回到第一步以上算法是按广探法描述的，但在实际图上作业时，按深探法进行更快捷一次只找一条增广链，增广一次换一张图最后一次用广探法，以便找出最小截集89最大流最小截集的标号法举例(s+,)(s+,6)(2

,6)(3+,1)(4+,1)(s+,)(s+,5)(2+,2)(5

,2)(4+,2)90最大流最小截集的标号法举例(s+,)(s+,3)(2

,3)最小截集91

最大流标号法的复杂度讨论找一条增广链的计算量是容易估计的，不会超过O(n2)但是最多迭代多少次(即增广的次数)就很难估计，在最坏情况下，与边的容量有关；如上图：先增广suvt,然后增广svut，每次只能增广1个单位，故要增广4000次才能结束克服这种缺点的经验方法：尽量先用段数少的增广链尽量不重复前面出现过的增广链926.4.4多端网路问题936.4.5

最小费用最大流双权网路：每条弧不但有容量，还有单位流量的通过费用两种解法：一种基于最小费用路径算法；一种基于可行弧集的最大流算法基于最小费用路径算法：总是在当前找到的最小费用的路径上增广流；缺点是每次增广后要改变弧的费用，且出现负权值费用的弧基于可行弧集的最大流算法：从0费用弧集开始应用最大流算法，然后根据计算信息提高费用的限界P，使可行弧集增大，再应用最大流算法，直至所有弧都进入可行弧集。这种算法是一种主-对偶规划的解法。使用这种方法的还有运输问题、匹配问题946.4.5

以最短路为基础汇总网路上的流在电路网中每两点之间都有中继电路群需求，但并不是任两点都有物理传输链路根据两点间最短传输路径将该两点间的电路需求量加载到这条传输路径上去：设a25=10是节点2和5之间的电路需求，节点2和5之间的最短传输路径为2

1

3

5，则加载过程为:T21=T21+10,T13=T13+10,T35=T35+10；Tij

是传输链路i

j

上加载的电路数；当所有点间电路都加载完则算法结束956.5欧拉回路和中国邮递员问题中国邮递员问题(ChinesePostmanProblem,CPP)是由我国管梅谷教授于1962年首先提出并发表的问题是从邮局出发，走遍邮区的所有街道至少一次再回到邮局，走什么路由才能使总的路程最短？如果街区图是一个偶图，根据定理3，一定有欧拉回路，CPP问题也就迎刃而解了若街区图不是偶图，则必然有一些街道要被重复走过才能回到原出发点显然要在奇次点间加重复边如何使所加的边长度最少归结为求奇次点间的最小匹配(minimumweightedmatch)—由Edmons给出多项式算法(1965)96

解中国邮递员问题的步骤0、将图中的所有悬挂点依次摘去1、求所有奇次点间的最短距离和最短路径2、根据奇次点间的最短距离求最小完全匹配3、根据最小完全匹配和最短路径添加重复边4、将悬挂点逐一恢复，并加重复边5、根据得到的偶图，给出欧拉回路的若干种走法97

解中国邮递员问题的步骤986.6哈密尔顿回路及旅行推销员问题

6.6.1哈密尔顿回路(Hamiltoniancircuit)连通图G(V,E)中的回路称为哈密尔顿回路，若该回路包括图中所有的点。显然哈密尔顿回路有且只有n

条边，若|V|=n连通图具有哈密尔顿回路的充分必要条件是什么？这个问题是由爱尔兰数学家哈密尔顿1859年提出的，但至今仍未解决欧拉回路是对边进行访问的问题，哈密尔顿回路是对点进行访问的问题搜索哈密尔顿回路的难度是NP-complete任两点间都有边的图称为完全图(或全连接图)完全图中有多少个不同的哈密尔顿回路？完全图中有多少个边不相交的哈密尔顿回路？最小哈密尔顿回路问题

(NP-complete)哈密尔顿路径：包含图中所有点的路径为什么说找两点间的最长路是非常困难的问题？(n

1)!/2(n

1)/2996.6.2旅行推销员问题(TravelingSalesman

Problem)旅行推销员问题(TSP)：设v1,v2,...,vn

为n

个已知城市，城市之间的旅程也是已知的，要求推销员从v1出发，走遍所有城市一次且仅一次又回到出发点，并使总旅程最短这种不允许点重复的旅行推销员问题就是最小哈密尔顿回路问题一般旅行推销员问题(GTSP)：允许点重复的TSP当网路边权满足三角不等式时，一般旅行推销员问题就等价于最小哈密尔顿回路问题当网路边权不满足三角不等式时，只要用两点间最短路的距离代替原来的边权，就可以满足三角不等式，在此基础上求最小哈密尔顿回路

典型的应用：乡邮员的投递路线邮递员开邮箱取信的路线问题邮车到各支局的转趟问题100

TSP的启发式算法(Heuristicalgorithm)穷举法：指数算法分支定界法：隐枚举法二交换法(two-option,Lin’salgorithm)哈密尔顿回路可以用点的序列表示从任一个哈密尔顿回路(即任何一个序列)出发按照一定顺序试图交换相邻两个点的顺序，若路程减少则完成交换，继续下一个交换；若没有改善，则不进行本次交换，尝试下一个交换；若所有的相临交换都试过而不能改善，则算法结束，得到一个局部最优点模拟退火(SimulatedAnnealing)随机地采用二交换法当交换后没有使目标函数改善，也可能以玻尔兹曼分布概率被接受，但这种概率是随模拟的温度下降而减少的发挥了计算机的优点，尽量减少陷入局部极值点模拟物理机制101

二交换法举例初始解：1-2-3-4-5

1-3-2-4-51-3-2-4-5

1-3-4-2-51-3-4-2-5

1-3-4-5-2

5-3-4-2-13-1-4-2-5102

算法复杂度Prim算法i=1n

1次比较，最多n

1次赋值i=22(n

2)次比较，最多2(n

2)次赋值i=k

k(n

k)次比较，最多k(n

k)次赋值Dijkstra算法i=1n

1次临时标记，永久标记n

1次比较和赋值i=2n

2次临时标记，永久标记n

2次比较和赋值i=k

n

k

次临时标记，永久标记n

k

次比较和赋值103Prim算法的改进增加一个辅助记录型数组，用以记录当前V

中各节点到V

的最小边，minedge[i].cost记录该边的权值，minedge[i].vex记录该边V

中的顶点。若minedge[i].cost<0则表明i

点进入集合Vfori:=2tondobeginminedge[i].vex:=1;minedge[i].cost:=w[1,i]end;fori:=1ton

1dobeginmi:=maxint;forj:=2tondoif(minedge[j].cost>0)and(minedge[j].cost<mi)thenbegink:=j;mi:=minedge[j].costend;minedge[k].cost:=

minedge[k].cost;{找到k，将k

加入集合V}forj:=2tondoif(w[k,j]<minedge[j].cost)thenbeginminedge[j].cost:=w[k,j];minedge[j].vex:=k;end;end;{该算法复杂度约为5n(n-1)}104

匹配问题(MatchingProblem)定义：图中一组边的集合，当图中的每个节点最多只与该集合中的一条边相关联，则该边集就成为匹配。1、两部图的匹配问题图中的节点可分为两个集合，X,Y，X与Y

之间有边相连，但X

内部和Y

内部无关联边，称为两部图运输问题实际上是两部图的最小费用最大流问题任务分配问题实际上是两部图的最小完全匹配问题2、非两部图的匹配问题(1)最大基数匹配(maximumcardinalitymatching)(2)最大权匹配(maximumweightmatching)(3)最小完全匹配(minimumweightperfectmatching)(4)最优分数匹配(optimalfractionalmatching)105两部图的最小完全匹配匈亚利算法任务分配问题的抽象就是两部图的最小完全匹配问题匈亚利算法(Hungarianmethod)由Kuhn教授提出，它实际上是主对偶算法的先驱匈亚利算法借助于效率矩阵和两部图来完成运算任务分配问题的效率矩阵对应的是两部图的边权{cij}，对偶问题的解对应的是每条边的两个端点{ai,bj}；对偶约束为ai,＋bj

cij匈亚利算法的实质是通过构造对偶问题的可行解，得到一个等值边子图，即所有ai,＋bj＝cij

的边构成的图；然后在等值边子图上求最大基数匹配；当得到原问题的完全匹配，则算法结束对偶问题的可行解

等值边子图满足互补松弛定理求原问题的解(部分可行解)检验扩充等值边子图

106最大基数匹配最大基数匹配是基于交错树的算法敞露点、根、交错链、外点、内点、增广链尚未匹配的节点称为敞露点以敞露点为根，由非匹配边和匹配边交替构成的链称为交错链交错链的根为外点，其后内点与外点交替；外点是交错链的生长点以内点结束的交错链称为增广链，因为反转该链上各边的匹配状态可使匹配的边数增加一条107匈亚利算法步骤令所有ai＝0在效率矩阵中找每列最小值qj，令bj＝qj

，故i,j，满足ai＋bj

cij在满足ai＋bj＝cij

的边构成的等值子图中求最大基数匹配；若达到完全匹配则结束，否则到下一步对敞露点求每列的最小松弛量sj＝mini*{ci*j－ai*－bj}求最大增广量S＝0.5

minj{sj}增广等值子图，

j，bj＝bj＋S

i*(敞露点)，aj＝aj＋S

；

i(非敞露点)，aj＝aj－S返回到第3

步108匈亚利算法举例**109匈亚利算法举例*110匈亚利算法举例111

任务分配问题、匹配问题和TSP的关系三个问题都有一个n

n

正权值的边权矩阵三个问题的解都可以用代数置换(permutation)表示i1,i2,i3,i4,i5是1,2,3,4,5的任一排列，表示元素位置的交换轮换，全轮换，对换TSP的解必须是一个全轮换任务分配问题的解可以是任一个置换匹配的解必须是n/2个对换任务分配问题是匹配问题的松弛问题112

6.7

选址问题使所选地址到最远的服务对象距离尽可能小——中心点使所选地址到各服务对象的总距离最小——中位点有时间限制的多用中心点，如乡邮局总资源约束的多用中位点，如电话交换局

6.7.1各点之间的距离节点到节点间的最短距离，称为节点—节点距离边上某点到节点的最短距离，称为点—节点距离节点到某边上最远一点的距离，称为节点—边距离边上一点到另一边上最远点的距离，称为点—边距离1131、边上某点到节点的最短距离dij

代表vi

与vj

间的最短距离，ars

代表边(r,s)的边长，令h

为边(r,s)上一点的百分位，0

h1边上对应h

的一点到vj

的最短距离为

d[h(r,s),j]=min[h

ars+drj,(1

h)

ars+dsj]2、节点到某边上最远一点的距离指定节点j，它到边(r,s)上对应h百分位点有两条路，最远点必使两条路一样长，故有

d[j,(r,s)]=0.5[djr+djs+ars]3、边上指定一点到其他边上最远点的距离h

是边(r,s)上指定的百分位点，另一边为(u,t)d[h(r,s),(u,t)]=min[h

ars+d[r,(u,t)],(1

h)

ars+d[s,(u,t)]]114

6.7.2

中心的选择中心：以节点—节点距离为基础，大中取小(maxmin)一般中心：以节点—边距离为基础，大中取小绝对中心：以点—节点距离为基础，大中取小一般绝对中心：以点—边距离为基础，大中取小左图的中心是v1；而三个节点都是一般中心类似也有四种中位点：中位点一般中位点绝对中位点一般绝对中位点115

例6.7.1~6.7.2中心一般中心中位点一般中位点第七章随机服务理论概述确定型只是随机现象的特例7.1随机服务系统系统的输入与输出是随机变量A.k.Erlang于1909~1920年发表了一系列根据话务量计算电话机键配置的方法，为随机服务理论奠定了基础又称为排队论(QueuingTheory)或拥塞理论(CongestionTheory)117

与服务系统性能相关的特性服务系统存在来自两个矛盾方面的要求顾客希望服务质量好，如排队等待时间短，损失率低系统运营方希望设备利用率高给用户一个经济上能够承受的满意的质量哪些系统特性会影响系统的性能？服务机构的组织方式与服务方式顾客的输入过程和服务时间分布系统采用的服务规则

7.1.1服务机构的组织方式与服务方式单台制和多台制并联服务串联服务串并联服务、网络服务全利用度、部分利用度118

与服务系统性能相关的特性7.1.2输入过程和服务时间顾客单个到达或成批到达顾客到达时间间隔的分布和服务时间的分布顾客源是有限的还是无限