1统筹方法.ppt

统筹方法 数学建模简明教程 第十一章统筹方法 一 统筹图的有关概念二 统筹图的要求及其检验方法三 统筹图的分析方法四 缩短工期问题 一 统筹图的有关概念一道工序以一条有向边来表示 有向边的权即为此工序的长度 表示完成该工序所需的时间 有向边的起点和终点分别表示该工序的开始和结束 称为事项 前接工序的完工事项即为后继工序的开工事项 统筹图的最重要功能 表示所要作的事情的先后次序关系 若工序A的终点是工序B的起点 如下图所示 则称工序A是工序B的紧前工序 工序B是工序A的紧后工序 统筹图的表示工序先后的次序关系的原则是 一个工序只有当它的所有紧前工序都完成后 才可以开工 或者说 对每一个事项来说 只有在指向该事项的所有工序都已完成的条件下 从该事项出发的工序才可以开始开工 注解1由 以茶待客 这个任务的完成过程来理解统筹图及工序 事项 初始 最终 事项 紧前 紧后 工序等相关概念 详见教材P134 由教材P134图11 1可以读出各个事情发生的先后次序 事件B一定要在事件A完成后才能做 事件D一定要在B C都完成的情况下才能开始 也就是说 放茶叶前一定要先洗好茶杯 冲茶前一定要先放好茶叶并且烧好开水 由此可见 对每一个事项来说 只有在指向该事项的所有工序都已完成的条件下 从该事项出发的工序才可以开始动手做 二 统筹图的要求及其检验方法 一 统筹图的要求要求整个统筹图只有一个初始事项和一个最终事项 正确的统筹图要求整个图内不含有 圈 所谓 圈 是图中从某个事项出发经过若干首尾相连的有向线段又回到起点的一个工序序列 注解2如果说要求 1 是一种 表达形式上 的要求 而且也易满足 那么 统筹图无圈 的要求则是 本质性 的 这是因为统筹图是一个有向图 有向图的圈与第八章中无向图的圈不同 统筹图中一旦出现圈 由于它表示工序上互为前提 故在实践中无法实现 二 通过例题理解如何画出正确的统筹图 例1 下表是某个机床要加工的5种零件的先后的次序关系 试根据表格画出相应的统筹图来 正确的统筹图如下 教材详细叙述了画出统筹图的过程 要注意虚工序的运用 统筹图中 有些地方一定要添加虚工序 虽然完成虚工序不要额外的时间 但却是不可省略的 例如上图中所添加的虚工序都不可省略 例2 自行车的装配 详见教材P136的例2 1 根据题目给出的必须遵循的装配顺序 列出各工序之间的关系 1 在安装并校正前后轮之前组装车架 B和C的紧前工序是A 2 车闸的安装于前后轮装好之后再做 G的紧前工序是B和C 3 连接飞轮和轮盘间的链条要在后轮和中轴装好之后再进行 C和D是E的紧前工序 4 先装中轴 再装脚蹬 D是F的紧前工序由关系 1 4 可得如关系表 2 根据这些关系画出相应的统筹图 由关系 1 得图 a 由关系 2 得图 d 返回图 h 由关系 3 得图 b 由关系 4 得图 c 下来要做的就是将这些分开的图合并成一个图 在此过程中就要适当的添加虚工序 合并图 a 和图 b 得图 e 而图 e 和图 c 就不能简单地合并成如图 f 因为C并不是F的紧前工序 所以这样合并使错误的 这里就要添加虚工序 如图 g 最后要做的是合并图 g 和图 d 我们很容易想到的是添加一个虚工序 合并成如图 h 但仔细观察一下 我们会发现这样合并是错误的 因为D并不是G的紧前工序 所以应再添加虚工序 合并成如图 i 为了适应每件事情总有 一个 开始和 一个 结束的思维习惯 我们可以将两个初始事项合并为一 三个最终事项也可并成一个 这样就形成如教材p138的图11 4即下图 三 如何检查统筹图有无圈 穷竭法 即 跟踪 每一个首尾相连的有向线段序列 看它是否回到起点 这种方法对简单的统筹图是有效的 但是当统筹图中包括有大量的工序时 这种做法很难确保检查了所有的有向线段序列而没有遗漏 有向线段删去法 这是检查统筹图有没有圈的普遍而简便的方法 有向线段删去法 具体步骤如下 1 从统筹图中找寻初始事项 2 删去该事项和从该事项出发的所有工序 3 在由此得到的新的统筹图中找寻新的初始 项 重复上述步骤 1 2 若能把图中的所有工序全部删去 则此统筹图没有圈 反之 则原图中包含圈 三 统筹图的分析方法 一 最短工期1 关键路线的概念对一张统筹图 所谓路线就是从初始事项到最终事项的一个首尾相连的工序序列 而路线中包含的工序的时间总和称为该路线的长 统筹图中最长的路线称为关键路线 2 关键路线的重要性 工程的最短工期等于统筹图中关键路线的长 即关键路线的长度等于最快完成所有的工序所需的时间 3 找统筹图中关键路线的方法 1 计算每个事项的最早出发时间和最迟到达时间 2 找出图中最早出发时间和最迟到达时间相同的所有事项 3 按时间由小到大连接这些事项的工序即组成关键路线 事项最早出发时间及其计算方法事项最早出发时间是指事项后面的工序最早什么时间可以开工 或者等价地 该事项前面的工序最早什么时间可以完工 因而统筹图中各事项的最早出发时间是由前向后推算的 由最早出发时间的含义可知 最终事项的最早时间也就是完成整个工程的最短时间 即工程的最短工期 事项最迟到达时间及其计算方法事项最迟到达时间是在规定事项后面各工序最迟完工时间的条件下 该事项前面的工序最迟什么时间必须完工 或等价地 该事项后面的工序最迟什么时候必须开工 因而统筹图中各事项的最迟到达时间是由后向前推算的 例1见教材 例3 对下图求关键路线 解 1 计算事项最早出发时间 用表示事项j的最早出发时间 事项1是初始事项 规定它的最早时间为0 即 则由前向后推算各事项的最早出发时间依次为 2 计算事项最迟到达时间用表示事项i的最迟到达时间 事项6是最终事项 规定它的最迟到达时间为该事项的最早出发时间80 即 则由后向前推算各事项的最迟到达时间依次为 3 找出最早出发时间和最迟到达时间相同的事项 1 3 4 6 4 将这些事项按时间由小到大连接它们的工序依次排列出来 就得到统筹图的关键路线 1 3 4 6或A C G 四 缩短工期问题工程的最短工期由关键路线长度决定 因此可以推出 要缩短工期必须想办法缩短关键路线上工序的时间 要注意两个问题 1 能否缩短某个工序的时间要从实际出发 2 缩短了关键路线上的工序后 新的统筹图的关键路线可能会改变 要对改变后的工程网络图进行检验