运筹学--第十章 网络计划方法

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天完成

的概率。

２５１

数学建模 运筹学模型(一)

运筹学模型（一） 本章重点： 线性规划基础模型、目标规划模型、运输模型及其应用、图论模型、最小树问题、最短路问题 复习要求： 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

运筹学教材编写组《运筹学》课后习题-网络计划(圣才出品)

第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 =??=??=

运筹学名词解释

《运筹学基础》名词解释 运筹学：缩写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

数学建模 运筹学模型

运筹学模型（一） 本章重点： 线性规划基础模型、目标规划模型、运输模型及其应用、图论模型、最小树问题、最短路问题 复习要求： 1.进一步理解基本建模过程，掌握类比法、图示法以及问题分析、合理假设的内涵. 2.进一步理解数学模型的作用与特点. 本章复习重点是线性规划基础模型、运输问题模型和目标规划模型.具体说来，要求大家会建立简单的线性规划模型，把实际问题转化为线性规划模型的方法要掌握，当然比较简单.运输问题模型主要要求善于将非线性规划模型转化为运输规化模型，这种转化后求解相当简单.你至少把一个很实际的问题转化为用表格形式写出的模型，至于求解是另外一回事，一般不要求.目标模型一般是比较简单的线性规模模型在提出新的要求之后转化为目标规划模型.另外，关于图论模型的问题涉及到最短路问题，具体说来用双标号法来求解一个最短路模型.这之前恐怕要善于将一个实际问题转化为图论模型.还有一个最小数的问题，该如何把一个网络中的最小数找到.另外在个别场合可能会涉及一笔划问题. 1.营养配餐问题的数学模型 或更简洁地表为 其中的常数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 ），则有 或更简单地写为 3.运输问题模型 运输问题也是一种线性规划问题，只是决策变量设置为双下标变量.假如问题具有m 个产地和n 个销地，第i 个产地用A i 表示，其产量为a i （i =1，2，…，m ），第j 个销地用B j 表示，其销量为b j （j =1，2，…，n ），从A i 运往B j 的运价为c ij ， 而∑∑===m i n j j i b a 11表示产销平衡.那么产销平衡运输问题的一般模型可以写成为 4.目标规划模型 某工厂生产代号为Ⅰ、Ⅱ的两种产品，这两种产品都要经甲、乙两个车间加工，并经检验与销售两部门处理.已知甲、乙两车间每月可用生产工时分别为120小时和150小时，每小时费用分别为80元和20元，其它数据如下表 表4-1 工厂领导希望给出一个可行性生产方案，使生产销售及检验等方面都能达标. 问题分析与模型假设 经与工厂总经理交谈，确定下列几条： p 1： 检验和销售费每月不超过4600元； p 2： 每月售出产品I 不少于50件；

运筹学模型与数学建模竞赛

运筹学模型与数学建模竞赛 一、引言 一般来说，大学生数学建模竞赛所涉及到的运筹学模型包括数学规划（线性规划和非线性规划），网络优化（含网络计划技术），排队模型，动态规划等，请看下表 下面重点介绍运筹学模型的数学规划。 二、数学规划的一般形式 ))(max ()(min x f or x f ?? ? ??≤≤=≤==ub x lb m j x g l i x h t s j i ,,2,1, 0)(,,2,1,0)(. . 线性规划： 整数规划： 非线性规划： 三、数学规划问题举例 1 下料问题 现要用100×50厘米的板料裁剪出规格分别为40×40 厘米与50×20厘米的零件，前者需要25件，后者需要30件。问如何裁剪，才能最省料？

解：先设计几个裁剪方案 记 A---------40×40；B-----------50×20 注：还有别的方案吗？ 显然，若只用其中一个方案，都不是最省料的方法。最佳方法应是三个方案的优化组合。设方案i 使用原材料x i 件(i =1,2,3)。共用原材料f 件。则根据题意，可用如下数学式子表示： ??? ??=≥≥++≥+++=)3,2,1(0305325 2. .min 321213 21j x x x x x x t s x x x f j ，整数 这是一个整数线性规划模型。 2 运输问题 现要从两个仓库（发点）运送库存原棉来满足三个纺织厂（收点）的需要，数据如下表，试问在保证各纺织厂的需求都得到满足的条件下应采取哪个运输方案，才能使总运费达到最小？（运价（元/吨）如下表） 方案1 方案2 方案3

解：题意即要确定从i 号仓库运到j 号工厂的原棉数量。故设ij x 表示从i 号仓运到j 号工厂的原棉数量（吨）f 表示总运费.则运输模型为： ?????? ????? ??==≥? ?? ??=+=+=+??? ≤++≤+++++++=运输量非负约束；需求量约束运出量受存量约束),,j ,i (x x x x x x x x x x x x x .t .s x x x x x x f m in ij 32121025154030504223223 1322122111232221131211232221131211 一般地，对于有m 个发点和n 个收点的运输模型为 ????? ??????==≥===≤=∑∑∑∑====),...2,1;,...2,1(0)...2,1(),...3,2,1(..min 1 1 11 n j m i x n j b x m i a x t s x c f ij m i j ij n j i ij m i n j ij ij 其中a i 为i 号发点的运出量，b j 为j 号收点的需求量，c ij 为从i 号发点到j 号收点的单位运价。 特别当 ∑∑===m i n j j i b a 1 1 时，存货必须全部运走，故上述约束条件中的 ∑=≤n j i ij a x 1 可改为等式： ),...2,1(1 m i a x i n j ij ==∑= 3 选址问题 某地区有m 座煤矿，i # 矿每年产量为a i 吨，现有火力发电厂一个，每年需用煤b 0吨，每年运行的固定费用（包括折旧费，但不包括煤的运费）为h 0元。现规划新建一个发电厂，m 座煤矿每年开采的原煤将全部供给这两个电厂发电用。现有n 个备选的厂址。若在j #备选厂址建电厂，每年运行的固定费用为h j 元，每吨原煤从i # 矿运送到j #备选厂址的运费为c ij 元(i =1,2,…m , j =1,2…n )。每吨原煤从i # 矿运送到原有电厂的运费为c i0 (i =1,2,…m )。试问： [1] 应把新电厂厂址选在何处？ [2] m 座煤矿开采的原煤应如何分配给两个电厂？ 才能使每年的总费用（电厂运行的固定费用与原煤运费之和）为最小？

运筹学--第十章 网络计划方法

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天完成 的概率。 ２５１