运筹学-第七章-网络计划技术 PPT课件

运筹学方法与模型 II 主讲人 丁小xbsuda 考勤1 每节课抽点名 提问的形式 2 上课内容为考试内容 上课内容的子集 3 考试形式 平时占30 期末占70 不排除太差的会挂科 几乎每年都有 4 考题形式 选择题 填空 名词解释 计算题 简答题 本学期主要内容 第七章 网络计划技术 第八章 动态规划 第九章 排队论 第十章 存储论第十一章 博弈论 第十二章 决策分析 4 第七章网络计划技术 5 建造一座汽车库及引道的工程项目 从施工开始到全部结束需要多少时间 把整个工程分解成若干个环节 工序 估算出每个环节所需要的时间 工时 确定各个环节之间的相互联系 先做什么 后做什么 哪些可以同时施工 紧前 紧后 平行关系 汇总上述各点予以具体分析 计算 得总工期 将工序及所需要时间 各工序之间的关系整理成表 工序清单 这是应用网络技术的第一步 引例 6 7 网络计划图示例 第七章网络计划技术 1 网络图 网络图是由结点 弧 权所构成的有向图 即有向赋权图 2 关键路线 完成各个工序需要时间最长的路线 7 1基本概念 3 绘制网络图应遵循的原则 1 方向 时序与结点编号网络图是有向图 按照流程的顺序 规定工序从左至右排列 网络图中的各个结点都有个时间 一般按各个结点的时间顺序编号 2 紧前工序与紧后工序如果只有在a工序结束后 b工序才能开始 则a工序是b工序是紧前工序 a工序是b工序的紧后工序 3 虚工序为了用来表达相邻工序之间的衔接关系 实际上并不存在的工序 不消耗人力 物力等资源和时间 4 相邻两个结点只能出现一条弧 无平行边 5 不能有缺口和回路 4 主要网络计划技术概念 工程计划的网络图网络图的时间参数网络图的分析 工序工程的组成部分称为工序 工时完成工序所需要的持续时间 双代号法 箭杆式 或 i j 工序需要人力 物力投入 经过一定时间才能完成 实工序 需要时间的工序 可能不需要人力 物力 7 2网络计划 虚工序 工时为0的工序 不需要人力 物力 不存在 表明工序间的逻辑关系 2 事项工序都有两个事项 开工事项 完工事项 工序 i j 的开工事项 工序 i j 的完工事项 任一工序有且仅有两个事项 直接连结两个事项的箭杆只能有一根 虚工序 7 2网络计划 7 2网络计划 2 工序a有紧后工序c与d 工序d有紧前工序b与a 3 工序a有紧后工序b与c 工序d有紧前工序b与c 4 工序a有紧后工序b与d 工序c有紧后工序d与e 7 2网络计划 工序间的基本逻辑关系对工序 i j 紧前工序 紧后工序 平行工序 4 举例 7 2网络计划 利用公式 期望时间 5 工时确定 单一时间确定法 以前多次执行过的 有可靠的生产定额值的 可以一个确定的时间作为它的工时 三种时间确定法 初次执行 无资料可循 a 最乐观时间 b 最保守时间 m 最可能时间 估计 7 2网络计划 7 2网络计划 对承担的工程经过工序分解 工时确定 根据生产工艺 生产组织的制约确定出各工序间的逻辑关系后 可以用一张网络图把上述各点统一反映出来 借以形象地表达工程计划方案的编制 绘制网络图 前进法 后退法 任意法 草图 逐步调整 尽量消除箭杆的交叉 正确运用虚工序 排列整齐 完整准确反映工程计划编制的网络图 注意 1 总开工 总完工事项都是唯一的 2 编号 总开工事项1 各事项编号不重复 任一工序完工事项编号大于开工事项编号 总完工事项为n 7 3网络图的时间参数 1事项的参数 1 事项的最早 可能 开始时刻 E 事项i的最早 可能 开始时刻 在此之前 事项i不可能开始 从顶点1到顶点K的最长路径长度 总开工事项 最早可能开始时刻 0 即E1 0 计算 从总开工事项起 从左至右地对其余事项予以计算 22 18 15 8 0 事项时间 最早开始时间Te j 通常按箭头事项计算事项最早时间 它等于从始点事项起到本事项最长路线的时间长度 Te 1 0Te j max Te i T i j j 1 2 n 若有2条或2条以上路径 式中 Te j 和Te i 分别为箭头和箭尾事项的最早时间 最迟时间Tl i 即为箭头事项各工序的最迟必须结束时间 或箭尾事项各工序的最迟必须开始时间 即 Tl n Te n Tl i min Tl j T i j i n 1 n 2 2 1 式中 n为终点事项 Tl i 和Tl j 分别为箭头和箭尾事项的最迟时间 2 最迟 必须 结束时刻 L 事项j的最迟 必须 结束时刻 在此之后 事项j不结束 就会造成工程拖期 总完工事项 最迟 必须 结束时刻Ln En 总工期 7 3网络图的时间参数 7 3网络图的时间参数 计算各事项的最迟开始时间 重要结论和概念 最早开始时间 最晚开始时间的事项为项目的关键事项 关键工序 总时差为0的工序 关键路线 由关键工序组成的从总开工总完工事项的一条路线 非关键工序 总时差大于0的工序 1 关键工序与关键线路 例题1 例题2 例题3 已知下列资料 要求 1 绘制网络图 2 各事项的最早开始时间与最迟结束时间 3 确定关键路径 例题4 如下图所示网络图 求出各结点的最早与最晚开始时间 关键路径等参数 29 请画出前表网络图 7 2网络计划 注意紧前工序 紧后工序和虚工序的位置顺序 例题4 Te 1 0Te 2 8Te 3 4Te 4 8Te 5 11Te 6 12Te 7 15 Tl 7 15Tl 6 12Tl 5 12Tl 4 8Tl 3 5Tl 2 8Tl 1 0 32 7 4网络图优化分析 1 网络图优化的原则 1 向非关键工序要资源 2 向关键工序要时间 33 总工期 成本优化问题 1 直接成本 如人工 原材料 燃料和机械设备租用等直接与工序工作有关的费用 直接成本要分摊到每道工序上 2 间接成本 如管理人员工资 行政办公费 采购费 劳保福利等 间接成本不分摊到每道工序上而作为整个工程的成本 显然 整个TE短 间接成本就低 34 1 直接成本 如人工 原材料 燃料和机械设备租用等直接与工序工作有关的费用 直接成本要分摊到每道工序上 2 间接成本 如管理人员工资 行政办公费 采购费 劳保福利等 间接成本不分摊到每道工序上而作为整个工程的成本 显然 整个工程时间最短 间接成本就低 3 赶工成本增加了人力物力等资源以后 使工期得以缩短而需要的费用 2 直接成本 间接成本 赶工成本 35 3 基本概念 正常时间 赶工时间 正常成本 赶工成本 赶工成本斜率 36 赶工成本斜率 工序 I j 缩短一个单位时间所增加的直接成本称为该工序赶工成本斜率 记为 cij C 表示成本W 工作时间 37 5 优化分类 一 缩短工程进度优化二 时间成本优化三 资源优化 38 例5 1 例题5 1某工程的有关资料如下表所示 每天可以安排只有10人 要求工程在15天里完成 应如何安排工程进度可以在现有人力资源下按期完成任务 39 解题方法 1 绘制网络图看关键路线时间 人力资源是否满足要求 2 画出每天对人员的需要量的直方图3 计划调整 40 二 时间成本优化 工程总费用 直接费用 间接费用 赶工费用例5 5某工程由4项工作组成 其资料如表5 9 该工程的间接成本为每天4500元 试求最低成本日 41 解 画出网络图 标上时间参数工程直接费用 45000元总费用 45000 4500 12 0 99000求关键线路 42 另外 一条线路了1 2 4为时间富裕线 有2天机动时间 改进方案1 缩短关键工作时间 从成本斜率最低的关键工作着手 分析关键工作ACD 工作D的赶工成本斜率最低 所以对D赶工 但是赶工多少 对D赶工2天后 出现两条关键路线1 2 3 4 1 2 4 工期为10天 总费用为 45000 4500 10 2000 2 94000 改进方案2 进一步缩短工期 要缩短工期就需要考虑两条路线 43 工程可选择的赶工方案 44 由上表可以知道 方案3的赶工费用最低 所以选择B D各赶工1天 这样工期变为9天 总费用 45000 4500 9 2000 3 1000 1 92500改进方案三继续赶工 对A或者B C赶工 但是发现B C赶工费用为5000 大于工程每天的间接费 赶工已经不合算 所以对A赶工2天 总费用 45000 4500 7 2000 3 1000 1 4000 2 91500答 该工程总工期为7天 总费用为91500 课后作业 1 计算各结点的最早与最迟时间 各工序的最早开工 完工时间 2 计算各结点的最早与最迟时间 各工序的最早开工 完工时间 所有工序路线 1 2 7 10 11 181 2 5 6 7 10 11 191 2 5 6 9 10 11 161 2 4 5 6 7 10 11 181 2 4 5 6 9 10 11 161 2 4 8 9 10 11 171 3 4 5 6 7 10 11 20 关键路线 1 3 4 5 6 9 10 11 171 3 4 8 9 10 11 191 3 4 8 11 19 48 习题 1 绘制网络图 2 计算各结点的最早和最晚开始时间 3 求关键路线 49 肯定型网