第11章网络计划
11.1 已知下列资料(表11-1)。
表11-1
要求：（1）绘制网络图；
（2）用图上计算法计算各项时间参数(除外)；
（3）确定关键路线。
解：（1）由题意绘制网络图如图11-1所示。
（
2）
事项最早时间见图11-1中“□”中的数字，事项最迟时间见图11-1中“△”中的数字。
图11-1
（3）总时差为零的工序为关键工序，所以关键路线为①→③→④→⑤→⑥→⑦→⑩→?，对应的工序为。
11.2 已知下列资料，如表11-2所示。
r
H B G A F K
→→→→→
要求：（1）绘制网络图；
（2）计算各项时间参数；
（3）确定关键路线。
表11-2
解：（1）由题意绘制网络图如图11-2所示。
（2）事项最早时间见图11-2“□”中的数字，事项最迟时间见图11-2中“△”中的数字。
图11-2
（3）总时差为零的工序为关键工序，所以关键路线为，如图11-2所示。
11.3 已知下列资料，如表11-3所示：
表11-3
求出这项工程的最低成本日程。
解：由表11-3中的已知条件和数据，绘制如图11-3所示的网络图。
图11-3
各事项的最早时间为：
各事项最迟时间为：
()()()()()()()
{} 6max44,6,33,6,55,6
E E E E
T T T T T T T
=+++
{}
max84,45,11012
=+++=
()()()()()
{}{} 7max22,7,66,7max86,12315 E E E
T T T T T
=++=++=
将各事项的最早时间与最迟时间分别记入该事项右下角的“□”和“△”内，如图11-4所示。
图11-4
总时差为零的工序为关键工序，从图11-4可以看出关键路线为
又已知工程项目每天的间接费用为500元，按图11-4及表11-3中的已知资料，若按图11-4安排，易知工程总工期为l5天，工程的直接费用(各工序直接费用之和)为
（20+30+15+5+18+40+10+15）×100=15300元 工程间接费用15×500=7500元 工程总费用为15300+7500=22800元
如果要缩短工期，应该首先缩短关键线路上赶一天进度所需费用最小的工序的作业时间。工序B ，G ，H 中，G 赶一天进度所需费用最小，为300元，且小于一天的工程间接费用
()715L T =()()()676,715312L L T T T =?=?=()()()464,61248L L T T T =?=?=()()()()(){}{}2min 72,7,42,4min 156,808L L L T T T T T =??=??=()()()565,612012L L T T T =?=?=()()()()()()(){}3min 43,4,63,6,53,55L L L L T T T T T T T =???=()()()()(){}{}1min
21,2,31,3min 88,540L L L T T T T T =??=??=
500元。缩短G工序1天，此时总费用为22800+(300-500)=22600元。此时，关键路线有三条，分别为B，G，H；B，C和A，D，G，H。此时，如果再缩短工程工期，赶进度所需费用将超过因缩短工期而节约的间接费用，从而导致工程总费用的增加。
所以，最低成本日程为14天，此时工程总费用为22600元。
第二节 最大流和最小割 一、割 若S 为V 的一个子集，S y S V S S x ∈-=∈,,，记),(S S K =为起点在S 中，终点在S 中的全体有向边的集合，即 {} S v S u v u K ∈∈=,),( （11-4） 我们称边集),(S S K =为网络G 的一个割，称∑∈K e e C )(为K 的容量，记为 Cap K 。 例5 给运输网络如图11-8所示，试 求与给定的j S （j =1，2，3）相对应的 Cap j K 。 解取{}11,v x S =， {}),(),,(),,(221311v x v v v v K =， Cap 1K =10+6+9=25。 图11-8 取 {}4212,,,v v v x S =， {}),(),,(),,(5254312v v v v v v K =， Cap 2K =10+6+13=29。 取 {}54213,,,,v v v v x S =， {}),(),,(5313y v v v K =， Cap 3K =10+10=20。 可见，若把割K 的边全从G 中移去，G －K 不一定分离成两部份（如例5中，3K G -仍为一个连通图），但是它一定把G 的全部自源x 到汇y 的路断开，也就是说此时流不能在G 上发生。故从直观上不难理解，G 的任一流f 的流值Val f 不能超过任一割的容量。 二、最大流与最小割 若?f 为满足下列条件的流： Val ?f ={}的一个流 为G f Valf max ， （11-5）
则称?f 为G 的最大流。 若?K 为满足下列条件的割。 Cap ?K ={}的一个割 为G K K Cap min ， （11-6） 则称?K 为G 的最小割。 例1 这个运输问题，就是一个在图11-6中求x 至y 的最大流问题。对此，我们不难建立线性规划模型来求出最优解。但由于网络模型结构的特殊性，我们可以建立有效的求最大流的算法，且求出的最优解是一个整数解。 定理1 对于G 中任一流f 和任一割),(S S K =，有 Val )()(s f S f f -+-= 其中，∑∈+= ),()()(S S e e f S f ，∑∈-=),()()(S S e e f S f 例如，在图11-7中，取{}11,,v x x S =，则 {}),(),,(),,(),,(),,(),(221412121x x x x v v v v v x S S = {}),(),(12v x S S = 4815510315)(=++++=+S f 8)(=-S f 可见，Val )()(40S f S f f -+-== 定理1说明，通过G 的任一横截面的净流值都为Val f ，亦即Val f 为任一横截面的输出量与输入量的代数和。 若f 为G 上一个流，对任E e ∈，若)()(e C e f =，称边e 为f 饱和边；若)(e f ＜)(e C ，称边e 为f 不饱和边；若)(e f ＞0，称边e 为f 正边；若)(e f =0，称e 为f 零边。 定理2 对于G 上任一流f 和任一割),(S S K =，有 1．Val f ≤Cap K ； 2．Val f =Cap K 的充要条件为：任),(S S e ∈，边e 为f 饱和边；任),(S S e ∈，边e 为f 零边。 证 1．∑∈+= ),()()(S S e e f S f ≤∑∈=K e CapK e C )( 又 )(S f -≥0，
第11章网络计划 11.1 已知下列资料(表11-1)。 表11-1 要求：（1）绘制网络图； （2）用图上计算法计算各项时间参数(除外)； （3）确定关键路线。 解：（1）由题意绘制网络图如图11-1所示。 （ 2） 事项最早时间见图11-1中“□”中的数字，事项最迟时间见图11-1中“△”中的数字。 图11-1 （3）总时差为零的工序为关键工序，所以关键路线为①→③→④→⑤→⑥→⑦→⑩→?，对应的工序为。 11.2 已知下列资料，如表11-2所示。 r H B G A F K →→→→→
要求：（1）绘制网络图； （2）计算各项时间参数； （3）确定关键路线。 表11-2 解：（1）由题意绘制网络图如图11-2所示。 （2）事项最早时间见图11-2“□”中的数字，事项最迟时间见图11-2中“△”中的数字。 图11-2 （3）总时差为零的工序为关键工序，所以关键路线为，如图11-2所示。 11.3 已知下列资料，如表11-3所示： 表11-3
求出这项工程的最低成本日程。 解：由表11-3中的已知条件和数据，绘制如图11-3所示的网络图。 图11-3 各事项的最早时间为： 各事项最迟时间为： ()()()()()()() {} 6max44,6,33,6,55,6 E E E E T T T T T T T =+++ {} max84,45,11012 =+++= ()()()()() {}{} 7max22,7,66,7max86,12315 E E E T T T T T =++=++=
将各事项的最早时间与最迟时间分别记入该事项右下角的“□”和“△”内，如图11-4所示。 图11-4 总时差为零的工序为关键工序，从图11-4可以看出关键路线为 又已知工程项目每天的间接费用为500元，按图11-4及表11-3中的已知资料，若按图11-4安排，易知工程总工期为l5天，工程的直接费用(各工序直接费用之和)为 （20+30+15+5+18+40+10+15）×100=15300元 工程间接费用15×500=7500元 工程总费用为15300+7500=22800元 如果要缩短工期，应该首先缩短关键线路上赶一天进度所需费用最小的工序的作业时间。工序B ，G ，H 中，G 赶一天进度所需费用最小，为300元，且小于一天的工程间接费用 ()715L T =()()()676,715312L L T T T =?=?=()()()464,61248L L T T T =?=?=()()()()(){}{}2min 72,7,42,4min 156,808L L L T T T T T =??=??=()()()565,612012L L T T T =?=?=()()()()()()(){}3min 43,4,63,6,53,55L L L L T T T T T T T =???=()()()()(){}{}1min 21,2,31,3min 88,540L L L T T T T T =??=??=
运筹学模型（一） 本章重点： 线性规划基础模型、目标规划模型、运输模型及其应用、图论模型、最小树问题、最短路问题 复习要求： 1.进一步理解基本建模过程，掌握类比法、图示法以及问题分析、合理假设的内涵. 2.进一步理解数学模型的作用与特点. 本章复习重点是线性规划基础模型、运输问题模型和目标规划模型.具体说来，要求大家会建立简单的线性规划模型，把实际问题转化为线性规划模型的方法要掌握，当然比较简单.运输问题模型主要要求善于将非线性规划模型转化为运输规化模型，这种转化后求解相当简单.你至少把一个很实际的问题转化为用表格形式写出的模型，至于求解是另外一回事，一般不要求.目标模型一般是比较简单的线性规模模型在提出新的要求之后转化为目标规划模型.另外，关于图论模型的问题涉及到最短路问题，具体说来用双标号法来求解一个最短路模型.这之前恐怕要善于将一个实际问题转化为图论模型.还有一个最小数的问题，该如何把一个网络中的最小数找到.另外在个别场合可能会涉及一笔划问题. 1.营养配餐问题的数学模型 n n x C x C x C Z ++=211m i n ????? ?? ??=≥≥+++≥+++≥+++??) ,,2,1(0, ,, 22112222212111212111n j x b x a x a x a b x a x a x a b x a x a x a t s j m n mn m m n n n n 或更简洁地表为 ∑== n j j j x C Z 1 m i n ??? ??? ?==≥≥??∑=),,2,1,,2,1(01 n j m i x b x a t s j n j i j ij 其中的常数C j 表示第j 种食品的市场价格，a ij 表示第j 种食品含第i 种营养的数量，b i 表示人或动物对第i 种营养的最低需求量. 2.合理配料问题的数学模型 有m 种资源B 1，B 2，…，B m ，可用于生产n 种代号为A 1，A 2，…，A n 的产品.单位产品A j 需用资源B i 的数量为a ij ，获利为C j 单位，第i 种资源可供给总量为b i 个单位.问如何安排生产，使总利润达到最大？ 设生产第j 种产品x j 个单位（j =1，2，…，n ），则有 n n x C x C x C Z +++= 2211m a x
《运筹学基础》名词解释 运筹学：缩写OR，是利用计划方法和有关多学科的要求。把复杂功能关系。表示成数学模型，其目的是通过定量分析为决策和揭露新问题提供数量根据。 定性决策：基本上根据决策人员的主观经验或感受到的感觉或只是而制定的决策。 定量决策：借助于某些正规的计量方法而作出的决策。 混合性决策：必须运用定性和定量两种方法才能制定的决策。 预测：是对未来的不确定的事物进行估计或判断。 专家小组法：是在介绍咨询的专家之间组成一个小组，面对面的进行讨论与磋商，最后对需要预测的课题得出比较一致的意见 指数平滑预测法：是定量与定性方法相结合的一种预测方法 决策：从狭义方面来说，决策可以解释为对一些可供选择的方案作出抉择。广义的决策过程包括4个程序：明确决策项目的目的，寻求可行的方案，在诸可行方案中进行抉择，对选定的决策方案经过实施后的结果进行总结评价 常规性决策：它是例行的，重复性的决策。做这类决策的个人或组织。又要需要他们决策的问题不是新问题，一般来说已经有管理和经验作参考。因而进行决策是就比较容易。 特殊性决策：是对特殊的，先例可循的新问题的决策。做这类决策的个人或组织只有认真履行决策过程的四个阶段，才能作出满意的决策。 计划性决策：有些类似法治系统中的立法工作。国家或组织的方针政策以及较长期的计划等都可视为计划性较长的对象。 最大最大决策标准：可称为乐观主义者的决策标准，采用这种决策标准，决策者比较谨慎小心。总是从未来的销售情况可能较差的状态考虑。然后在选择最优的可行方案、 最小最小遗憾值决策标准：也叫最小最大后悔值决策标准。它运用计算遗憾值的逻辑原则，求得在不同的销售状态下选用不同的方案所能造成的遗憾值，然后在根据最小最大以后标准进行决策。选取最优方案。 现实主义决策标准：也称折衷主义决策标准。所谓现实主义或折衷主义，就是说既不是从最乐观的角度。也不说从最保守的角度来估计未来可能出现才自然状态 存货台套：它的英文原名为stockkeepinggunit，在某些企业中可以译成存货储备单元，简称存货单元ABC分析法是按各种存货台套或存货单元的年度需用价值，将它们分成A，B，C三类。订货费用：主要是企业自己拥有存货或 保管存货所有承担的费用。主要包括投 入储存货方面的资金利息。由于存货陈 旧或样式过时而折损的费用，储存场地 方面发生的费用。存业务费用，税金， 保险费和盗窃损失等款项。 经济订货量：(EOQ）是使总的存货费用 达到最低的为某个存货台套货某个存 货单元确定的最佳的订货量 再顶点：一是时间上的含义。即什么时 间为某项存货再订货，另一种是存货水 平上的含义。即某项存货达到怎样的存 量水平时，就应再订货。上述的“某项 存货再订货时的时间”和“再订货时的 某项存货的存量水平”都可称为再订货 点。 前置时间内的需求量：可称为订货提前 期内的需求量。前置时间内某项存货台 套货存货单元的使用量就是前置时间 内的需求量 缺货指仓库中已没有某项存货可以满 足生产需要或销售需要时的状况 安全库存量：又称为保险库存量。它是 为了预防可能出现的缺货现象而保持 的额外库存量。 单纯形法：解线性规划问题的一种比较 简单的方法，是由美国数学家丹齐格教 授在1947年首先发展去来的的。它是 通过一种数学的迭代过程，逐步求得最 优解的方法。 改进路线：指从某一个空格开始，所寻 求的那一条企图改变原来的运输方案 的路线。 改进指数：就是指循着改进路线，当货 物的运输量做一个单位的变动时，会引 起总运输费用的改变量。 阶石法：我们把数学格中的数字用圆圈 圈上，再用虚线从上到下，从左到右把 各个圆圈联系起来：由圆圈和虚线所组 成的图形很像一个台阶。 网络计划技术（统筹法）它是综合运用 计划平核术和关键路线法的一种比较 先进的计划管理方法。 计划评核术：是对计划项目进行核算、 评价，然后选定最优计划方案的一种技 术。 关键路线法：在计划项目的各项错综复 杂的工作中，抓住其中的关键路线进行 计划安排的一种方法。 网络图（箭头图，统筹图），它是计划 项目的各个组成部分内在逻辑关系的 综合反映，是进行计划和计算的基础。 箭线式网络图以箭线代表活动，以结点 代表活动的开始或完成。结点式网络图 从结点代表活动，以箭线表示各活动之 间的先后承接关系。活动用箭线表示， 箭线的方向表示活动前进的方向，从箭 尾的箭头表示一项活动的开始到终结 的过程。 结点：是箭线之间的交接点，用圆圈表 示，结点指明某一项活动的开始或完 成。 线路：指从网络的始点开始，顺着箭线 的方向，中间经过互相连接的节点和箭 线，到网络终点为止的一条联线。 作业时间：在一定的生产技术条件下， 完成一项活动或一道工所需要的时间。 单一时间估计法：就是在估计各项活动 的作业时间时，只确定一个时间值。估 计时，应参照过去从事同类活动的统计 资料，务求确定的作业时间既符合实际 情况，又具有先进性。三种时间估计法 就是在估计各项活动的作业时间时，先 估计出三个时间值，然后再求出完成该 活动的作业时间。 线段：两个关键结点之间的一个活动或 两个关键结点之间的几个活动连续相 接的连线。 时间优化：就是在人力、材料、设备、 资金等资源基本上有保证的条件下，寻 求最短的工程周期。 时间与资源优化：就是在合理利用资源 的条件下，寻求最短的工程周期。 树：一个图第一是连通的：第二是不含 圈的。这样的图很象一棵树，我们就形 象地称之为“树”。 最小枝杈树问题：是关于在一个网络 中，从一个起点出发到所有接点，找出 一条或几条路线，以使在这样一些路线 中所采用的全部支线的总长度是最小 的。 马尔柯夫过程：对于由一种情况转换为 另外一种情况的过程，且该过程具有转 换概率，此种转换概率又能够依据其紧 邻的前项情况推算出来，由于马尔柯夫 对此作了系统深入的研究，因而在以后 的学术研究中把这种过程称为马尔柯 夫过程。 马尔柯夫分析：对于马尔柯夫过程或马 尔柯夫锁链可能产生之演变加以分析， 以观察和预测该过程或该锁链未来变 动的趋向，则这种分析、观察和预测的 工作即为马尔柯夫分析。 概率向量：任意一个向量 u=(u,u2，······，un),如果它内部的各 个元素为非负数，且总和等于1，则此 向量称为概率向量。 概率矩阵：一方阵P=（PIJ）中，如果 其各行都是概率向量，则此方阵称为概 率矩阵或概率方阵。 盈亏平衡分析：是一种管理决策工具， 它用来说明在一定销售量水平上总销 售量与总成本因素之间的关系。 盈亏平衡点：是企业经营达到这一点 时，总销售额和总成本完全相等。 计划成本：是管理部门认为要达到预期 目标所必须的费用。 预付成本：是由所提供的生产能力决定 的。例如线性折旧、税款、租金、工厂 和设备保险金等,这些费用是过去发生 的行为的结果,不受短期管理控制的支 配。 边际收益：又称为边际贡献，指产品的 价格减去可变成本的净值。 模拟：又称仿真，是一种定量的过程， 它先为过程设计一个模型，然后再组织 一系列的反复试验，以预测该过程全部 时间里所发生的情况。 随机变量：这些变量在某个范围内都是 随机变化的，我们称为随机变量。
《运筹学》习题答案 一、单选题 1.用动态规划求解工程线路问题时，什么样的网络问题可以转化为定步数问题求解（ ）B A.任意网络 B.无回路有向网络 C.混合网络 D.容量网络 2.通过什么方法或者技巧可以把工程线路问题转化为动态规划问题？（ ）B A.非线性问题的线性化技巧 B.静态问题的动态处理 C.引入虚拟产地或者销地 D.引入人工变量 3.静态问题的动态处理最常用的方法是？B A.非线性问题的线性化技巧 B.人为的引入时段 C.引入虚拟产地或者销地 D.网络建模 4.串联系统可靠性问题动态规划模型的特点是（ ）D A.状态变量的选取 B.决策变量的选取 C.有虚拟产地或者销地 D.目标函数取乘积形式 5.在网络计划技术中，进行时间与成本优化时，一般地说，随着施工周期的缩短，直接费用是( )。C A.降低的 B .不增不减的 C .增加的 D .难以估计的 6.最小枝权树算法是从已接接点出发，把( )的接点连接上C A.最远 B.较远 C.最近 D.较近 7.在箭线式网络固中，( )的说法是错误的。D A.结点不占用时间也不消耗资源 B.结点表示前接活动的完成和后续活动的开始 C.箭线代表活动 D.结点的最早出现时间和最迟出现时间是同一个时间 8.如图所示，在锅炉房与各车间之间铺设暖气管最小的管道总长度是( )。C A.1200 B.1400 C.1300 D.1700 9.在求最短路线问题中，已知起点到A ，B ，C 三相邻结点的距离分别为15km ，20km,25km ，则（ ）。D A.最短路线—定通过A 点 B.最短路线一定通过B 点 C.最短路线一定通过C 点 D.不能判断最短路线通过哪一点 10.在一棵树中，如果在某两点间加上条边，则图一定( )A A.存在一个圈 B.存在两个圈 C .存在三个圈 D .不含圈 11.网络图关键线路的长度( )工程完工期。C A.大于 B.小于 C.等于 D.不一定等于 600 700 300 500 400 锅炉房 1 2 3
10.1已知下表所列资料 工序紧前工序工序时间（天数）工序紧前工序工序时间（天数） a － 3 f c 8 b a 4 g c 4 c a 5 h d,e 2 d b,c 7 i g 3 e b,c 7 j j,h,i 2 要求：（1）绘制网络图；（2）计算各结点的最早时间与最迟时间；（3）计算各工序的最早开工、最早完工、最迟开工及最迟完工时间；（4）计算各工序的总时差（总机动时间）；（5）确定关键路线。 10.2 已知建设一个汽车库及引道的作业明细表如下表所示。要求： （1）计算该项工程从施工开始到全部结束的最短周期； （2）若工序l拖期10天，对整个工程进度有何影响； （3）若工序j的时间由12天缩短到8天，对整个工程进度有何影响； （4）为保证整个工程进度在最短周期内完成，工序i最迟必须在哪天开工； （5）若要求整个工程在75天完工，要不要采取措施？若要的话，应从哪些方面采取措施？ 工序代号工序名称工序时间（天）紧前工序 a 清理场地开工10 － b 备料8 － c 车库地面施工 6 a,b d 预制墙及房顶16 b e 车库地面保养24 c f 立墙架 4 d,e g 立房顶架 4 f h 装窗及边墙10 f i 装门 4 f j 装天花板12 g k 油漆16 h,i,j l 引道施工8 c m 引道保养24 l n 交工验收 4 k,m ２５０
求出该项工程总费用最低的最优工期（最低成本日程）。 10.4 已知某工程的网络图如下图所示，设该项工程开工时间为零，合同规定该项工程的完工时间为25天。 要求：（1）确定各工序的平均工序时间和均方差；（2）画出网络图并按平均工序时间照常网络图中的关键路线；（3）求该项工程按合同规定的日期完工的概率。 (1)绘制网络图；求出每道工序的期望时间和方差；求出计划项目的期望工 期和方差；求出工期不迟于50天完成的概率和比期望工期提前4天完成 的概率。 ２５１