运筹学第三版胡运权郭耀煌黄⾊封⽪第九and⼗章排队论习题答案9.1 有A，B，C，D，E，F 6项⼯作，关系分别如图9-38(a)，(b)，试画出⽹络图。
9.2 试画出下列各题的⽹络图(见表9-8，表9-9，表9-10)，并为事项编号。
9.3 设有如图9-39，图9-40⽹络图，⽤图上计算法计算时间参数，并求出关键路线。
9.4 绘制表9-11，表9-12所⽰的⽹络图，并⽤表上计算法计算⼯作的各项时间参数、确定关键路线。
9.5 某⼯程资料如表9-13所⽰。
要求：(1)画出⽹络图。
(2)求出每件⼯作⼯时的期望值和⽅差。
(3)求出⼯程完⼯期的期望值和⽅差。
(4)计算⼯程期望完⼯期提前3天的概率和推迟5天的概率。
解：每件⼯作的期望⼯时和⽅差见表9-13的左部。
⼯程完⼯期的期望值为32个⽉，⽅差为5（1+1+1+1+1）。
⼯程期望完⼯期提前3天的概率为0.09，推迟5天的概率为0.987。
9.6 对图9-41所⽰⽹络，各项⼯作旁边的3个数分别为⼯作的最乐观时间、最可能时间和最悲观时间，确定其关键路线和最早完⼯时间的概率。
根据关键线路，再考虑到其他线路上的时差很多，可知最早完⼯时间应该等于关键线路上各个⼯作最早完⼯时间之和:4+2+6+2+3=2=19 。
概率为0.005 。
9.7 某项⼯程各道⼯序时间及每天需要的⼈⼒资源如图9-42所⽰。
图中，箭线上的英⽂字母表⽰⼯序代号，括号内数值是该⼯序总时差，箭线下左边数为⼯序⼯时，括号内为该⼯序每天需要的⼈⼒数。
若⼈⼒资源限制每天只有15⼈，求此条件下⼯期最短的施⼯⽅案。
解:最短⼯期还是15天。
各个⼯作的开始时间如下图所⽰：9.8 已知下列⽹络图有关数据如表9-14，设间接费⽤为15元／天，求最低成本⽇程。
解：将①→②缩短两天，总⼯期为25天，直接费⽤7420元，间接费⽤375元，最⼩总费⽤为7795元。
⽹络图和关键线路如下：9.9 ⼀项⼩修计划包括的⼯作如表9-15所⽰。
运筹学复习重点第1章线性规划与单纯形法（1）化线形规划标准形的手法（2）线性规划解的概念、解的情形、解的判定（3）单纯形法的计算过程、迭代逻辑。
（4）熟练运用单纯形表求解问题；若给出单纯形表，要会解读，会基于单纯形法基本原理反推出表中一些参数。
（5）两阶段法、大M法第2章对偶理论和灵敏度分析（1）会写对偶问题，掌握对偶性质，原问题与对偶问题之间的关系。
（2）互补松弛定理的应用：知道一个问题的最优解，求另一个问题的最优解。
（3）对偶单纯形法（4）当目标函数系数和右端项变化时灵敏度分析的简便方法第4章整数规划（1）分支定界法：如何构造分支子问题，如何更新目标函数最优值上下界，何时终止。
（2）割平面法：如何写对源约束方程；如何拆分、组装割平面方程；如何利用对偶单纯形法继续求解。
第5章无约束优化（1）凸函数与凸规划的定义与判别（2）一维搜索的0.618法基本原理和迭代过程（3）无约束优化的最速下降法的基本原理、迭代过程第6章约束极值优化（1）可行下降方向的含义、满足什么代数条件、几何意义（2）正确写出Kuhn-Tucker条件，理解K-T条件与最优解的关系（3）利用Kuhn-Tucker条件，求出K-T点和最优解。
（4）外点法和内点法的基本原理、无约束优化目标函数的一般构造手法第7章动态规划（1）动态规划的基本原理和基本方程（2）动态规划的逆推解法（3）动态规划求静态规划问题的套路第8章图与网络优化（1）图的基本概念、树的基本性质、最小支撑树的求法（2）求最短路的Dijkstra算法（3）增广链的概念、用途，求网络最大流的标号法第10章排队论（1）排队系统基本性能指标的含义、关系（2）泊松流与负指数分布的关系，排队系统中基本参数λ和μ含义的多维解读。
（3）系统状态概率Pn的含义、它在推导系统基本性能指标中的基础地位，推导它自身所依据的状态转移图。
（4）M/M/1模型、M/M/c模型的状态转移图，概率平衡方程，以及了解系统状态概率、基本性能指标的计算过程。
第八章 排队论排队是日常生活和经济管理经常遇到的问题，如医院等待看病的病人、加油站等待加油的汽车、工厂等待维修的机器、港口等待停泊的船只等。
在排队论中把服务系统中这些服务的客体称为顾客。
由于系统中顾客的到来以及顾客在系统中接受服务的时间等均是随机的，因此排队现象是不可避免的。
对于随机服务系统，若扩大系统设备，会提高服务质量，但会增加系统费用。
若减少系统设备，能节约系统费用，但可能使顾客在系统中等待的时间加长，从而降低了服务质量，甚至会失去顾客而增加机会成本。
因此，对于管理人员来说，解决排队系统中的问题是：在服务质量的提高和成本的降低之间取得平衡，找到最适当的解。
排队论是优化理论的重要分支。
排队论是1909年由丹麦工程师爱尔郎（A.K.Erlang ）在研究电话系统时首先提出，之后被广泛应用于各种随机服务系统。
第一节 排队论的基本概念及所研究的问题一、基本概念（一）排队系统的组成一般的排队系统有三个基本组成部分：顾客的到达（输入过程）、排队规则和服务机构，如图8—1所示。
1．输入过程输入过程指顾客按什么样的规律到达。
包括如下三个方面的内容：（1）顾客总体（顾客源） 指可能到达服务机构的顾客总数。
顾客总体数可能是有限的，也可能是无限。
如工厂内出现故障而等待修理的机器数是有限的，而到达某储蓄所的顾客源相当多，可近似看成是无限的。
（2）顾客到达的类型 指顾客的到达是单个的还是成批的；（3）顾客相继到达的时间间隔分布 即该时间间隔分布是确定的（定期运行的班车、航班等）还是随机的，若是随机的，顾客相继到达的时间间隔服从什么分布（一般为负指数分布）；2．排队规则排队规则指顾客接受服务的规则（先后次序），有以下几种情况。
（1）即时制（损失制） 当顾客来到时，服务台全被占用，顾客随即离去，不排队等候。
这种排队规则会损失许多顾客，因此又称为损失制。
（2）等待制 当顾客来到时，若服务台全被占用，则顾客排队等候服务。
在等待制中，又可按顾客顾客达到排队系统 图8—1服务的先后次序的规则分为：先到先服务（FCFS，如自由卖票窗口等待卖票的顾客）、先到后服务（FCLS，如仓库存放物品）、随机服务（SIRO，电话交换台服务对话务的接通处理）和优先权服务（PR，如加急信件的处理）。
