图上作业法.ppt

图上作业法 本节课的主要内容 编制交通图和流向图对流向图的检验图上作业法的求解过程 重点 一 图上作业法 在运输中 若使用同一种运输工具 则运费的计算往往仅与运送物资的多少及里程有关 因此 在求最佳的运输方案时 用吨公里作为度量的标准比用运费作为度量标准更加方便 实用 在求解最佳运输方案时 用吨公里作为度量单位 还可以在已经画出的交通图上进行 操作起来较为简单 方便 直观 快捷 在铁路 公路等交通部门经常使用这种方法决策最优运输问题 这种方法被称为图上作业法 二 编制交通图和流向图 交通图反映发点 产地 与收地 销地 及交通线路及其距离组成的图形 发点用 表示 发出货物的数量记在 之内 单位 吨 收地 销地 用 表示 收取货物的数量记在 之内 单位 吨 两点之间的线路长度记在交通线路的旁边 1 交通图 1 交通图 2 流向图 流向图 在交通图上表示物资流向的图被称为流向图 在图中每个发点吨数全部运完 每个收点所需吨数均已满足 流向用箭头画在两点连线的右方 即 站在发点 看向收点 右手所在的一侧或从发点到收点 顺时针方向的一侧 2 流向图 2 流向图 关于流向图的一些规定箭头必须表示物资运输的方向流量写在箭头的旁边 加小括号 流向不能直接跨越路线上的收点 发点 交叉点任何一段弧上最多只能显示一条流向 即同一段弧上的多条流向必须合并 除端点外 任何点都可以流进和流出 2 流向图 2 流向图 含有圈的流向图的补充规定顺时针方向的流向必须画在圈的内侧 称为内圈流向逆时针方向的流向必须画在圈的外侧 称为外圈流向 内圈流向 外圈流向举例 二 对流向图的检验 在物资运输中 把某种物资从各发点调到各收点的调运方案是很多的 但我们的目的是找出吨 公里数是最小的调运方案 这就要注意在调运中不要发生对物流运输和迂回运输 因此 我们在制定流向图时 就要避免它的出现 1 不合理的现象1 对流 1 对流 所谓对流就是在一段线路上有同一种物资出现相对运输现象 往返运输 同一段线路上 两各方向都有流向 如左图 甲乙两地是一种对流现象 如果把流向图改成右图 就可以避免对流现象 从而可以节约运输量20 10 200 吨公里 2 不合理的现象2 迂回 2 迂回 当收点与发点之间的运输线路有两条或两条以上时 即交通图成圈 如果运送的货物不是走最短线路 则称这种运输为迂回运输 注 当交通图成圈时 如果流向图中内圈流向的总长 简称内圈长 或外圈流向的总长 简称外圈长 超过整个圈长的一半就称为迂回运输 例如某物资流向图如图所示 迂回运输的判断 显然 左图为迂回运输 3 正规 最优 流向图 正规 最优 流向图 一个最优的调运方案 它的流向图必是无对流 无迂回的流向图 称这种流向图为正规流向图 物资调运的图上作业法就是寻找一个无对流 无迂回的正规流向图 步骤如下 作出一个无对流的初始可行方案 检验有无迂回若无 结束 否则 调整 直到最优 三 图上作业法的求解过程 1 无圈 线状 的交通图2 有圈的交通图方法 供需归邻站 1 交通图无圈 现状 情形 例 求最优调运方案 案例分析 口诀 抓各端 各端供需归邻站即 先满足端点的要求 逐步向中间逼近 直至收点与发点得到全部满足为止 3 4 2 3 4 7 3 10 练一练 答案 2 交通图有圈情形 例 求最优调运方案 它的原则可归纳为 流向划右方 对流不应当 里圈 外圈分别算 要求不过半圈长 如若超过半圈长 应甩运量最小段 反复求算最优方案 解题步骤 第一步 变有圈为无圈 方法 丢边破圈 即丢掉一条边 破去一个圈 注意 丢边时 往往是丢掉圈中长度最大的边 如图所示 第一步 丢边破圈 第二步 在无圈的交通图上作流向图 原则 先外后内 先端点后中间点 要求每个边都有流向 当某条边无流向时 必须填上运输量为零的虚流向 第二步 作流向图 4 8 1 5 3 2 8 第三步 检查有无迂回 圈B5B4B3A2的圈长 4 4 5 8 21 内圈长 4 4 5 13 21 2 有迂回 所以流向图不是最优流向图 需要调整 第四步 对方案进行调整 方法 找出有迂回圈的流量最小的边 去掉的边除外 改此边为丢掉的边 边B5B4 并补上原来丢掉的边 边B5A2 得到新的交通图 在此交通图上做新的流向图 第四步 调整方案 4 5 4 7 8 6 4 5 4 A1 A2 B1 B3 B2 B5 A3 8 B4 2 2 7 3 4 6 3 4 8 1 5 1 2 6 第五步 对新方案进行检验 圈B5B4B3A2的圈长 4 4 5 8 21 内圈长 4 5 925 2 有迂回 所以流向图不是最优流向图 需要调整 第六步 对方案进行调整 方法 找出有迂回圈的流量最小的边 去掉的边除外 改此边为丢掉的边 边A1B3 并补上原来丢掉的边 边B1A3 得到新的交通图 在此交通图上做新的流向图 直到所有圈的内圈长小于二分之一圈长 外圈长小于二分之一圈长 得到最优方案 第六步 调整方案