运筹学-6(图与网络分析).ppt

运筹学基础教程6 黄桐城主编赵弘志改编主讲 第六章图与网络分析 主要内容 我们的教材p 116 图论的基本概念 最短路问题 不重要内容 最大流问题 不重要内容 网络计划 6 1图论的基本概念 6 1 1引论哥尼斯堡七桥问题 A B D C A B C D 简捷表示事物之间的本质联系 归纳事物之间的一般规律 引论图的用处 A B C D E某公司的五支球队进行循环赛组织机构设置图 A B C D E 总公司 分公司 工厂或办事处 6 1 2图的基本概念 图是由点和线构成的 点的集合V表示 V vi 不带箭头的连线叫做边 edge 边的集合记为E ej 一条边可以用两点 vi vj 表示 ej vi vj 带箭头的连线叫做弧 arc 弧的集合记为A A ak 一条弧也是用两点表示 ak vi vj 弧有方向 vi为始点 vj为终点 图的基本概念 续 由点和边组成的图叫做无向图 记为G V E 由点和弧组成的图叫做有向图 记为D V A 例1 v1 v2 v3 v4 v1 v2 v3 v4 v5 v6 v7 e1 e2 e3 e4 e5 e6 e7 a1 a2 a8 a4 a3 a5 a6 a9 a7 a10 a11 无向图 点集 边集 有向图 点集 弧集 图的基本概念 续 以点u为端点的边的条数 叫做点u的次次为1的点叫做悬挂点 次为0的点叫做孤立点 次为奇数则称奇点 次为偶数则称偶点 点弧交替序列称为链 闭合的链称为圈首尾相接的链称为路 闭合的路称回路任意两点之间都有边相连 称为连通图 节点与 有向 边每一条边和两个节点关联 一条边可以用两个节点的标号表示 i j 路径 Path 前后相继并且方向相同的边序列P 1 2 2 3 3 4 4 2 3 1 4 2 3 1 网络由节点和边组成 图的基本概念 续 回路 Circuit 起点和终点重合的路径称为回路 1 2 2 4 4 1 回路中各条边方向相同 4 2 3 1 链 Chain 前后相继并且方向不一定相同的边序列称为链C 1 2 3 2 3 4 4 2 3 1 连通图任意两个节点之间至少有一条链的图称为连通图 2 4 3 5 1 圈 Cycle 起点和终点重合的链称为圈 1 2 2 4 3 4 1 3 圈中各条边方向不一定相同 4 2 3 1 树 Tree 无圈的连通图称为树树中只与一条边关联的节点称为悬挂节点 图上作业法 已知如图所示 三个工厂向四个市场配送 请确定最佳配送路线 先去掉两个圈内路线最长的线 得到下列流量图 验证 第一圈内总长 3 4 5 4 7 23第一圈逆时针内配送路长 3 4 5 12 11 5 则不是最优方案第二圈内配送路长 4 2 3 4 13第二圈逆时针内配送路长 2 6 5 则是最优方案 第二圈顺时针内配送路长 3 6 5 则是最优方案 修正第一圈内方案 取逆时针方向最小值1 然后逆时针方向配送路线减去1 顺时针方向配送及未走路线加上1 则得到第一圈内配送路长 5 总长一半 则是最优方案 如图所示 验证 第一圈顺时针内配送路长 7 4 11 11 5 则是最优方案 第一圈逆时针内配送路长 5 11 5 则是最优方案 第二圈顺时针内配送路长 3 6 5 则是最优方案 第二圈逆时针内配送路长 4 2 6 6 5 则是最优方案 计算运费 1 7 2 5 1 4 2 3 1 2 29 案例 通俗思路解题 起点和终点不同的单一路线选择例1 如图5 5所示 A是一煤矿所在地 I是煤炭需求地 B C D E F G H I是由A到J的可经过的城镇 每两节点之间的距离已经标出 现在要找出从A到J之间的最短路线 这就是一个最短路问题 6 2网络计划 6 2 1基本概念 p130 网络计划是用网络分析的方法编制的计划 杜邦公司 关键路线法CPM 美国海军武器局 计划评审技术PERT 网络图 有向赋权图 的构成 结点 也称事项 一道工序的开始或结束 工序 弧 相对独立的活动 消耗资源 虚工序 只表示衔接关系 不消耗资源 工序时间 权 完成工序的时间消耗 6 2 2网络图的绘制原则 只能有一个始点事项和一个终点事项不允许出现编号相同的箭线不允许出现循环线路作业要始于结点终于结点 网络规则 2 1 避免循环 不留缺口2 一一对应 一道工序用两个事项表示3 从左向右依次展开例 A 4 B 6 C 6 D 7 E 5 G 7 F 9 H 4 I 8 网络图的绘制 任务的分析与分解判定作业之间的逻辑关系依逻辑关系绘制网络图 6 2 3关键路线法 CPM 一 时间参数运算什么是关键路线 1 作业时间t i j 经验数据 统计数据2 事项最早时间TE j max TE i t i j 到齐上课 最后到者决定最早开课时间3 事项最迟时间TL i min TL j t i j 保证12点吃饭 路最远者决定最迟下课时间4 工序最早可能开工时间TES i j TE i max TES h i t h i 5 工序最早可能完工时间TEF i j TES i j t i j h i j 6 工序最迟必须开工时间TLS i j TL j t i j min TLs j k t i j 7 工序最迟必须完工时间TLF i j TL j TLS i j t i j 8 工序总时差 在不影响其紧后工序最迟必须开工时间的前提下 本工序可以推迟的时间R i j TLS i j TES i j TLF i j TEF i j min TLS j k TEF i j 9 工序单时差 在不影响其紧后工序最早可能开工时间的前提下 本工序可以推迟的时间r i j min TES j k TEF i j k k 6 2 4时间参数图解 解上例 计算事项 时间参数 TES TLS TEF TLF TES TLS TEF TLS r i j R i j A4 B6 C6 G7 D7 E5 F9 H4 I8 0 0 4 7 6 13 22 20 28 28 20 24 13 6 关键路线 由总时差为零的工序构成BDGI t i j t j k 解上例计算工序时间参数 6 2 5计划评审技术 PERT PERT的产生关键路线法中 工序时间是确定值 而对研究性的工序来说 t i j 是随机的 1958年美国海军武器局研制北极星导弹时提出 重点在于计划的评审 PERT的时间估计采用三种时间估计法a 最乐观时间 b 最悲观时间 m 最可能时间 则工序期望时间te 方差 e2 2 a 4m b 6 b a 6 时间优化 网络图 PERT技术的优化 分多种 有时间优化 时间 费用优化和时间 费用 资源利用优化等 我们在这里简单介绍时间优化和时间 费用优化 时间优化主要是在以下两方面进行工作 向关键线路要时间 尽可能节省时间 向非关键线路要资源 在非关键线路调整人员 资金 物资等 集中到关键线路 使得关键线路有所突破 时间 费用优化 时间和费用双目标优化 一般来讲二者是矛盾的 通过仔细分析 寻找既省时又省钱的方案 即最低成本日程 费用 直接费用和间接费用直接费用 建造工程本身所需材料 人工间接费用 工程所需管理费用 设备租金 c t 间接费用 总费用 直接费用 赶工 直接费用增加 间接费用减少 间接费用是常量直接费用简化为常量处理 则 赶工直接费用率 费用差 时间差 课后作业 请同学们根据网络关键路线法求出下面网络计划图的关键路线 0 4 2 8 10 15 15 11 10 4 8 0 0 3 0 3 6 0 6 关键线路 时差为零的作业连接而成的线路 答案 1 建立层次结构模型该结构图包括目标层 准则层 方案层 层次分析法的基本步骤归纳如下 3 计算单排序权向量并做一致性检验 2 构造成对比较矩阵 从第二层开始用成对比较矩阵和1 9尺度 对每个成对比较矩阵计算最大特征值及其对应的特征向量 利用一致性指标 随机一致性指标和一致性比率做一致性检验 若检验通过 特征向量 归一化后 即为权向量 若不通过 需要重新构造成对比较矩阵 目标层 选一领导干部 准则层 方案层 建立层次结构模型 A的最大特征值 相应的特征向量为 构造成对比较矩阵及层次单排序 一致性指标 随机一致性指标RI 1 24 查表 一致性比率CR 0 07 1 24 0 0565 0 1 通过一致性检验 假设3人关于6个标准的判断矩阵为 健康情况 业务知识 写作能力 口才 政策水平 工作作风 由此可求得各属性的最大特征值和相应的特征向量 各属性的最大特征值 均通过一致性检验 从而有 即在3人中应选择A担任领导职务 层次总排序及一致性检验 怎么样选择对象 项目 期望值 1 A1 2 A2 3 A3 4 A4 5 A5 6 A6 7 A7 8 A8 期望值 1 A1 2 A2 3 A3 4 A4 5 A5 6 A6 7 A7 8 A8 课堂复习与练习 1 现在某皮鞋公司准备引进国外先进设备 现在通过专家评价 得到下面这个表格 请问 1 你认为这个表缺不缺内容 2 你认为某皮鞋公司应该这样决策 2 某学校每年一度的职称评定开始了 今年上级给这个学校高级职称的的指标仅有3人 但是有5位同志有资格可以参加评定 于是该学校进行了一系列的测评 下面这个表格是系列测评的一张表格 请问 1 你能告诉我们 这是一张什么样的表格 2 根据这表格 你认为哪三位在这个测评中在前面 3 左边是一个单位分了五个小组对五位先进工作者进行的小组集体打分排出的名次的结果 1 你认为ABC