图上作业法专题.ppt

图上作业法专题 一 图上作业法 在运输中 若使用同一种运输工具 则运费的计算往往仅与运送物资的多少及里程有关 因此 在求最佳的运输方案时 用吨公里作为度量的标准比用运费作为度量标准更加方便 实用 在求解最佳运输方案时 用吨公里作为度量单位 还可以在已经画出的交通图上进行 操作起来较为简单 方便 直观 快捷 在铁路 公路等交通部门经常使用这种方法决策最优运输问题 这种方法被称为图上作业法 二 编制交通图和流向图 交通图反映发点 产地 与收地 销地 及交通线路及其距离组成的图形 发点用 表示 发出货物的数量记在 之内 单位 吨 收地 销地 用 表示 收取货物的数量记在 之内 单位 吨 两点之间的线路长度记在交通线路的旁边 1 交通图 1 交通图 2 流向图 流向图 在交通图上表示物资流向的图被称为流向图 在图中每个发点吨数全部运完 每个收点所需吨数均已满足 2 流向图 2 流向图 关于流向图的一些规定箭头必须表示物资运输的方向流量写在箭头的旁边 加小括号 流向不能直接跨越路线上的收点 发点 交叉点任何一段弧上最多只能显示一条流向 即同一段弧上的多条流向必须合并 除端点外 任何点都可以流进和流出 2 流向图 2 流向图 含有圈的流向图的补充规定顺时针方向的流向必须画在圈的内侧 称为内圈流向逆时针方向的流向必须画在圈的外侧 称为外圈流向 内圈流向 外圈流向举例 二 对流向图的检验 在物资运输中 把某种物资从各发点调到各收点的调运方案是很多的 但我们的目的是找出吨 公里数是最小的调运方案 这就要注意在调运中不要发生对物流运输和迂回运输 因此 我们在制定流向图时 就要避免它的出现 1 不合理的现象1 对流 1 对流 所谓对流就是在一段线路上有同一种物资出现相对运输现象 往返运输 同一段线路上 两各方向都有流向 如图4 4 甲乙两地是一种对流现象 如果把流向图改成图4 5 就可以避免对流现象 从而可以节约运输量20 10 200 吨公里 2 不合理的现象2 迂回 2 迂回 当收点与发点之间的运输线路有两条或两条以上时 即交通图成圈 如果运送的货物不是走最短线路 则称这种运输为迂回运输 注 当交通图成圈时 如果流向图中内圈流向的总长 简称内圈长 或外圈流向的总长 简称外圈长 超过整个圈长的一半就称为迂回运输 例如某物资流向图如图4 6 4 7所示 迂回运输的判断 显然 图4 6为迂回运输 3 正规 最优 流向图 正规 最优 流向图 一个最优的调运方案 它的流向图必是无对流 无迂回的流向图 称这种流向图为正规流向图 物资调运的图上作业法就是寻找一个无对流 无迂回的正规流向图 步骤如下 作出一个无对流的初始可行方案 检验有无迂回若无 结束 否则 调整 直到最优 三 图上作业法的求解过程 1 无圈的交通图2 有圈的交通图方法 供需归邻站 1 交通图无圈情形 例1 求最优调运方案 案例分析 口诀 抓各端 各端供需归邻站即 先满足端点的要求 逐步向中间逼近 直至收点与发点得到全部满足为止 3 4 2 3 4 7 3 10 图4 8 练一练 答案 2 交通图有圈情形 例2 求最优调运方案 图4 9 解题步骤 第一步 变有圈为无圈 方法 丢边破圈 即丢掉一条边 破去一个圈 注意 丢边时 往往是丢掉圈中长度最大的边 如图所示 第一步 丢边破圈 第二步 在无圈的交通图上作流向图 原则 先外后内 先端点后中间点 要求每个边都有流向 当某条边无流向时 必须填上运输量为零的虚流向 第二步 作流向图 4 8 1 5 3 2 8 图4 10 第三步 补上丢掉的边 检查有无迂回 圈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 图4 11 第五步 对新方案进行检验 圈B5B4B3A2的圈长 4 4 5 8 21 内圈长 4 5 925 2 有迂回 所以流向图不是最优流向图 需要调整 第六步 对方案进行调整 方法 找出有迂回圈的流量最小的边 去掉的边除外 改此边为丢掉的边 边A1B3 并补上原来丢掉的边 边B1A3 得到新的交通图 在此交通图上做新的流向图 第六步 调整方案 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 3 7 1 4 2 2 6 图4 12 可验证 此方案中无迂回现象 即为最优方案 练一练 答案 图上作业法 有某物资7t 由发出点A1 A2 A3发出 发量分别为3 3 1 t 运往收点B1 B2 B3 B4 收量分别为2 3 1 1 t 收发量平衡 交通图如下图 问应如何调动 才使t km最小 例1 38 2 图上作业法 例3 有某物资7t 由A1 A2 A3发出 发量分别为3 3 1 t 运往收点B1 B2 B3 B4 收量分别为2 3 1 1 t 收发量平衡 交通图如图4 1所示 问应如何调运 才使t km最小 4 39 3 1 破圈求初始解 检查有无迂回 方法水对流想图中的各圈进行检查 侃侃有无迂回 如果没有迂回 即该圈总长的一半均大于内流长和外流长 这个初始方案就是最优方案 如果其中某一圈有迂回 这个方案就不是最优方案 需要改进 在图中 圈A1B1B2A3B4的总长为23km 外流长为5 4 3 12km 大于圈长的一半 因而需要调整 在看圈B2A2B3A3其总长为13km 圈中内流长为3km 外流长为2km 都小于圈长的一半 因此此圈不必调整 40 对圈A1B1B2A3B4的调整方法是 在外圈的个流量中 减去外圈的最小流量1t 然后在内圈的个流量中加上1t 在此圈中 因无内流量 所以无处可加 另外 在无流量的线段上 新添上内圈流量1t 这样得出新的流量图 方案调整 3 41 2 在圈B2A2B3A3中外圈长为4 3 7大于圈长的一半 调整为内圈加 1 外圈减 1 此时两个圈都没有迂回是最优方案总的TKM为 7 1 2 5 1 4 3 2 27 方案调整 42 8 3 4 6 6 5 7 5 7 代表仓库 代表需求 43 最短路问题 2 分析还没有P标号的各点 比较T j 和P 1 l1j l1j为V1到Vj的弧长 将Vj的新标号取较小者 即T j min T j P 1 l1j 如果 P 1 l1j T j 则用P 1 l1j代替T j 作为Vj点的新的T标号 T B min T B P A l12 min 0 3 3T C min T C P A l13 min 0 4 4点V2的T标号的数最小 令P 2 16 1 将A标上P标号0 即P 1 0 表示从A到A的距离为0 给其他点 B F 标上T标号 即T j j 2 3 4 5 6 F 5 44 3 以点B 刚得到标号的点 作为比较基础 重复上述过程 即比较T j 与 P 2 l2j j 3 4 5 6取较小的数作为Vj的新的T标号 T D 3 5 8T C 4T E 3 7 10比较T D T E T C 其中T C 为最小 将点C的T标号改为P标号 P C 4 5 45 同理T D 4 4 8比较T D T E 其中T D 最小 令P D 8 5 46 T E 3 8 11T F 8 4 12T E 3 7 10其中T E 10最小令P E 10 5 47 T F 10 5 15T F 12其中T F 12最小 则令P F 12最短路为12A B D FA C D F 5 3 1 3 1 2 1 3 A1 B2 A2 B3 A3 B4 B1 7 4 4 3 2 4 3 5 在上图的基础上做一个无对流的流向图 注意 与表上作业法类似 表上作业法要求有调运量的格子数应该是收点数 发点数 1 图上作业法要求在流向图上的箭头数 有调运量的边数 也应为收点数 发点数 1 这一要求也可以等价地表述为 在去线破圈后得到的不成圈的交通图上 要求每边都应该有流向 3 1 3 1 2 1 3 A1 B2 A2 B3 A3 B4 B1 4 4 3 2 3 5 3 1 2 1 1 因此 某一边无流向时 必须在这一边上添上调运量为0的虚流向 和其它流向同样对待 按照这一要求 应在A3边上添上虚流向 于是 再补上去掉的边 得下图 3 1 3 1 2 1 3 A1 B2 A2 B3 A3 B4 B1 4 4 3 2 3 5 3 1 2 1 1 0 2 检查有无迂回方法 对流向图中只有一边没有流向的各圈进行检查 如果没有迂回 即已到最优调运方案 如果有迂回 则需要进行调整 首先分别计算线路的全圈长 内圈长和外圈长 圈长即指里程数 如果内圈长和外圈长都分别小于全圈长的一半 则该方案即为最优方案 否则 即为非最优方案 需要对其进行调整A1B1B2A3B4外圈长5 4 3 12 大于全圈长23的1 2 3 调整方案 方法 在有迂回的外圈各流量中减去一个最小调运量 在内圈 含无调运量的边 各流量上加上这一最小调运量 圈A1B1B2A3B4中的最小流量为 在外圈上减去该最小调运量后 有两条边同时为 需在任意一边上记上0运