第五章 图
5.2 用DijKstra方法求图5-29中从v1到各点的最短路。
2 v1v2? v41 5 v5? v63 ? 4 ? 2 4 3 ? v8 ? 8 1 ? 7 v32 2 9 ? v7图5-29
注意事项：1、题目要求求出从v1到各点的最短路，最短路包括最短链及其长度两个方面。 5.5 在如图5-31所示的网络中，每弧旁的数字是cij,fij。
（1） 确定所有的截集； （2） 求最小截集的容量； （3） 证明指出的流是最大流。
?? （2，2） vs ? v1 ? （3，3） ?v t （4，3） （3，1） （1，0） ? v2 （2，2） ? （5，2）
常见问题：本题首先通过求最小截集的方法求出最大流，证明时犯了循环论证的错误，应使用增广链的方法证明。
5.7 如图5-33，发点s1,s2分别可供应10和15个单位，收点t1,t2可以接收10和25个单位，求最大流，弧上数为cij。
图5-31 3 s1v1 7 t? 2 2 ? 3 3 ? 6 s2 4 7 t? ? v2 7 图5-33
注意：求解时需增加一个始节点和终结点，本题答案有多个解，但最大流均为21。
5-10 绘 制表5-7所示的网络图，并用表上计算法计算工作的各项时间参数，确定关键路线。 表5-7 工作 A B C D E
在绘制网络图时，还要注意以下规则：
⑴网络图只能有一个总起点事项，一个总终点事项。 ⑵网络图不能有缺口和回路。 ⑶两节点i,j之间只能有一条弧。 ⑷正确表示工作之间的前行、后继关系。 如图5-16表示a,b两工序结束后，c,d两工序才开
2 图5-16 1 工时（d） 5 8 3 6 10 紧前工序 -- A，C A C B，C 工作 F G H I J 工时（d） 4 8 2 4 5 紧前工序 B，C C F，G E，H F，G a 3 c 4 d 5 b 始。a,b为
能开工，而
c,d的紧前工序，c,d为a,b的紧后工序。
⑸虚工序的应用。
如果a,b,c,d的工序关系是：c必须在a,b均完成后才
d只要在b完成后即可开工。也就是说，a,b是c的紧前工
1 a c 4 5 序，而只有④是一个虚
b是d的紧前工序。这样必须用图5-17来表示，其中③→
工序，只表示③、④两节点的衔接关系，不需要人力、物力间。
2 b 3 d 6 等资源和时
图5-17 虚工序还可以用于正确表示平行与交叉作业。一道工序分为几道工序同时进行，称为平行作业。如图5-18（a）中市场调研需12天，如增加人力分为3组同时进行，可以画为5-18（b）。
1 2 12 市场调研 3 4 1 2 3 3 6 5 6 5 4 （a） 图5-18 强调：
1、 一张网络图中只有一个始节点，一个终结点，其余的节点都是中间结点；
2、 两个结点之间职能有一条箭线，不允许同时有两条以上的箭线，如果遇到此情况可增加结点，用虚
箭线连接； 3、 不允许出现封闭的循环线路。 绘制方法和技巧：
顺推法（已知各工序的紧后工序，画始节点，确定始节点工序，根据紧后工序一步一步往后推）和逆推法（已知各工序的紧前工序，画终节点，确定终节点工序，根据紧前工序一步一步往前推）。 1 紧前工序完全相同的多个工序开始于同一结点； 2 紧后工序完全相同的多个工序结束于同一结点；
3 某工序的紧前工序包含另一工序的紧前工序，则引入虚工序，仅属于其中一工序的紧前工序置于该工序前，其他紧前工序则置于另一工序前，引入虚工序。
4某工序的紧后工序包含另一工序的紧后工序，则引入虚工序，仅属于其中一工序的紧后工序置于该工序后，其他紧后工序则置于另一工序后，引入虚工序。 例1： 工序 紧后工序 例2： 工序 紧后工序 例3：
a d,e b d,e,f c g d h e i f i g j h - i - j - a c,d b c,d,e c f d g e g f - g - （b）
工序 紧前工序
a - b - c a,b d a,b e b f c g c h d,e,f
第六章 排队论
6. 1 .3排队系统模型的分类
X/Y/Z/N/m
其中X指顾客相继到达间隔时间的分布，Y为服务时间的分布，Z为并列的服务台的数目。而N用以表示系统的容量限制，m则表示顾客源的数目。当N和m为无穷大，即系统容量和顾客源无限制时，可以把这两项略去。
6. 1. 4 衡量排队系统运行效率的工作指标 1. 平均队长Ls和平均排队长Lq 2. 平均逗留时间Ws和平均等待时间Wq
常用的数量指标。
（1）平均到达率?：指单位时间内到达服务系统的平均顾客数。
由?的定义可知， 1/?为相邻两个顾客到达系统的平均间隔时间，比如??2人/分钟为平均到达率。那么相邻两个顾客到达的平均间隔时间1/?=1/2分钟。
（2）平均服务率?：单位时间内被服务完毕后离开系统的平均顾客数。
同理，1/?表示每个顾客的平均服务时间。
（3）服务强度?：指每个服务台单位时间内的平均服务时间。
一般有?＝?，其中c为系统中并列服务台的数目。 c?（4）Pn＝P(N＝n)：指系统的状态N（即系统中的顾客数）为n的概率。 （5）有效到达率?e：指单位时间内进入服务系统的平均顾客数。
至今为止，研究较多且取得较好结果的排队系统是：顾客的输入过程服从泊松分布，而服务时间服从负指数分布的排队系统。
习题：
8， 某小型家电维修部声称对家电一般维修做到1小时内完成，并保证若顾客停留超过1小时，修理免费。已知每项修理收费10元，而修理成本为5.5元。如送达修理的家电服从泊松分布，平均每小时6件。修理每件的时间服从负指数分布，平均每件7.5分钟。该维修部有一名维修工，问：（1）该维修部能否做到盈利；（2）当维修时间不变，则维修家电送达率为何值时，该维修部的收支达到盈亏平衡。
解答：可以证明，在M/M/1情形下，顾客在系统中的逗留时间W服从参数为???的负指数分布。其分布函数
?1?e?(???)t t?0 FW(t)?P(W?t)??0 t <0?
注意：盈利的概率大于50%，并不一定代表能盈利。
9，某医生的私人诊所平均每20分钟有一位病人前来就诊。医生给每位病人诊断平均需要15分钟。现把它看作一个标准M/M/1排队模型，医生希望有足够的座位给来就诊的病人坐，具体地说，病人到达诊所时，没有座位的概率不能超过0.01，试问至少应为病人准备多少个座位？ 典型问题：对问题的理解存在偏差。
若为病人准备了n个座位，病人到达诊所时，没有座位的概率应为Pn+1+ Pn+2+…，而不是Pn
所以正确解法为：P1+ P2+…+Pn?0.99，解得n?16 就诊病人的座位算不算？
10，汽车按泊松分布到达某高速公路收费口，平均每小时90辆，每辆车通过收费口平均需时35秒，服从负指数分布。由于一些司机抱怨等待交费时间太长，管理部门拟采用自动收费装置使收费时间缩短到30秒。但条件是原收费口平均等待车辆超过6辆，且新装置的利用率不低于75%才采用。问在上述条件下，新装置应否被采用？
关键：求出平均排队长，及新装置的利用率。
13，某停车场有10的停车位置。汽车到达服从泊松分布，平均每小时10辆，每辆汽车停留时间服从负指数分布，平均10分钟，试求： 停车位置的平均空闲数； （E???10?n?P）
nn?010到达汽车能找到一个空位停车的概率； （
?Pn?09n?1?P10）
在该场地停车的汽车占总到达数的比例；
（当系统状态等于N时，新来的顾客会自动离去，因此，真正进入服务系统的顾客平均输入率是小于顾客平均到达率?的有效到达率?e。显然
?e??(1?PN) 。
在该场地停车的汽车占总到达数的比例应为?e/?）
每天（24小时）在该停车场找不到空闲位置停放的汽车的平均数。 （24???P10）
16，汽车按泊松分布到达一台专用于洗车的设备前，λ=5辆/小时，分别计算以下服务时间分布情况时，要洗车的车辆从到达到洗完离开总计需要的时间
Ws。（1）从5~10min的均匀分布；（2）正态分布N（9min，