物流优化技术课件第4章运输问题.ppt

第四章 运输最优化运输问题 v已知有m个供应地点 可供应某种物资，其供应量分别为 ，有n个销地 ，其需要量分别为 ，从 到 运输单位物资的运价（单价）为 ，这些数据可以汇总到产销平衡表和单位运价表中若用 表示从 到 的运量，那么供需平衡的条件下，要求得总运费最小的调运方案，可求解以下数学模型： 表上作业法 v例题：某物流公司有三个仓库，每天向四个超市供应某种货物已知三个仓库A1 、A2 和A3的此货物储藏量分别为7 箱、 4箱和 9箱该物流公司把这些货物分别送往B1 、B2 、B3 和B4四个超市，各超市每日销量分别为3箱、 6箱、 5箱和6箱试用表上作业法求解满足供需要求的最佳调运方案，使总运费最少第一步，画出该问题的供销平衡表和单位运价表 超市仓库B1B2B3B4A1311310A21928A374105 超市仓库B1B2B3B4储量A17A234A39销量3656v第二步，求初始解 v1、最小元素法 计算过程表 超市仓库B1B2B3B4A1311310A21928A374105v这方案的总运费为： v 元调运方案表 超市仓库B1B2B3B4储量A1437A2314A3639销量3656v2、伏格尔法v首先，在分别计算出各行各列的最小运费和次小运费的差额，并填入该列表的最右列和最下行 计算过程表 超市仓库B1B2B3B4行差额A13113100A219281A3741051列差额2513v这方案的总运费为 v 元计算过程表 超市仓库B1B2B3B4储量A1527A2314A3639销量3656三、车辆调度的方法v不平衡问题需求地区化肥厂产量(万吨)ABC1614191313202219231715_506050最低需求(万吨)最高需求(万吨)3050707003010不限不平衡问题销地产地ABCD161419M1614190131320M22192301715MM1715M0不平衡问题销地产地产量ABCD3020502003010302050605050销量3020703010502、图上作业法v 任何一张交通图上的线路分布形态无非为成圈与不成圈两类。

对于不成圈的运输，可采用“就近调运”的原则2、图上作业法v对于成圈的可采用破圈法处理凡是按顺时针方向调运的货物调运线路（如A3至B1、B1至B4、A2至B3），其调运箭头线都画在圈外，称为外圈；否则，其调运箭头线（A3至B3）都画在圈内，称为内圈 10首先分别计算线路的全圈长、内圈长和外圈长（圈长即指里程数），如果内圈长和外圈长都分别小于全圈长的一半，则该方案即为最优方案；否则，即为非最优方案，需要对其进行调整 指派问题 v在物流活动中，经常会遇到这样的问题，有n项运输任务，恰好有n辆车可承担这些运输任务，由于车型，载重以及司机对道路的熟悉程度等不同，效率也不一样，于是产生了应指派那辆车去完成那项运输任务，使总效率最高（或费用最小，或时间最短），这类问题称为指派问题 v问题要求极小化时数学模型是v v例题：某物流公司现有四项运输任务A、B、C、D，现有甲、乙、丙、丁四辆车，他们完成任务所需时间如表所示问应指派何人去完成何工作，使所需总时间最少？完成任务所需时间表 任务人员ABCD甲215134乙1041415丙9141613丁78119v第一步：使指派问题的系数矩阵经变换，在各行各列中都出现0元素。

v第二步：进行试指派，以寻求最优解v经第一步变换后，系数矩阵中每行每列都有了0元素；但需要找出n个独立的0元素若能找出，就以这些独立0元素对应解矩阵 中的元素为1，其余为0，这就得到最优解v最优解为 v这表示：指定甲去完成D项运输任务，乙去完成B项运输任务，丙去完成A项运输任务，丁去完成C项任务 加工任务分配方法-匈牙利方法v案例2v有4项流通加工任务分给4个小组去完成，各小组完成不同任务需用不同的加工时间v 各小组完成不同加工任务的工时表任务（1）任务（2）任务（3）任务（4）A31067B144138C13141210D415139v（1）列出矩阵v（2）逐行缩减矩阵v（3）再逐列缩减矩阵v（4）检查是否可以分配v（5）为增加“0”元素进行变换v（6）重新检查覆盖线v（7）确定最优方案v 0 7 3 4v 10 0 9 4v 3 4 2 0 v 0 11 9 5v（0） 7 1 4 v 10（0）7 4v 3 4 （0）0 v 0 11 7 5 v v 0 6 (0) 3v 11 (0) 6 3 v 4 4 0 (0) v (0) 10 6 4v最优分配方案是:A(3) B(2) C(4) D(1)v此方案所需总工时:6+4+10+4=24(h)最短路问题 v假定下图是一个由城市到城市的有向交通图，弧旁的数字表示各条路线的距离，那么最短路问题就是寻找一条从城市到城市的最短路径。

求解最短路问题的基本思路 v狄克斯托(Dijkstra)标号法是求解最短路问题的有效算法之一它的基本思路是逐点求最短路例如图中，如果 是从 的最短路，那么由点 出发沿这条最短路到达中间的任一点，也是从 点到达该任意点的最短路否则的话在这两点之间还存在其他最短路，那么 就不是从 到 的最短路，与原假设矛盾因此，从起点开始逐点寻找到邻近点的最短路，直到将最短路延伸到指定的终点为止，就自然找到了从起点到终点的最短 2、最短路径的选择中国邮递员问题 v一个邮递员送信，要走完他负责投递的全部街道，投完后回到邮局，应该怎样走，使所走的路程最短 v这个问题是我国管梅谷同志1962年首先求出来的，因此在国际上通称为中国邮递员问题在物流活动中，经常会遇到这样的问题：汽车满载货物从配送中心出发，往各条街道的超市（或小卖部）送货，怎样走路程最短 哥尼斯堡七桥问题 中国邮递员问题（欧拉定律）。