《物流运筹学第4章运输最优化ppt课件》由会员分享，可在线阅读，更多相关《物流运筹学第4章运输最优化ppt课件（26页珍藏版）》请在金锄头文库上搜索。
1、第四章第四章 运输最优化运输最优化.本章将讨论以下几个方面的内容：v线性规划与单纯形法简介v运输问题v指派问题v最短路问题v转运问题v中国邮递员问题.线性规划简介 v线性规划问题的标准型式 .v用矩阵描述时为 v b为资源向量；v c为价值向量；v x为决策变量的向量 .单纯形法简介 v单纯形法的基本思路:根据问题的标准,从可行域中某个基可行解(一个顶点)开场,转换到一个基可行解(顶点),并且使目标函数达到最大值时,问题就得到了最优解。 .v例如以下问题v经变换，得到一个基可行解v此时，目标函数的表达式v这说明若要用剩余资源 ，就必须支付附加费用。所以 时，即不再利用这些资源时，目标函数达到最
2、大值。所以 是最优解。 .运输问题 v已知有m个供应地点 。可供应某种物资，其供应量分别为 ，有n个销地 ，其需要量分别为 ，从 到 运输单位物资的运价单价为 ，这些数据可以汇总到产销平衡表和单位运价表中。若用 表示从 到 的运量，那么供需平衡的条件下，要求得总运费最小的调运方案，可求解以下数学模型： .表上作业法 v例题：某物流公司有三个仓库，每天向四个超市供应某种货物。已知三个仓库A1 、A2 和A3的此货物储藏量分别为7 箱、 4箱和 9箱。该物流公司把这些货物分别送往B1 、B2 、B3 和B4四个超市，各超市每日销量分别为3箱、 6箱、 5箱和6箱。试用表上作业法求解满足供需要求的最
3、佳调运方案，使总运费最少。.第一步，画出该问题的供销平衡表和单位运价表 超市仓库B1B2B3B4A1311310A21928A374105. 超市仓库B1B2B3B4储量A17A234A39销量3656v第二步，求初始解 v1、最小元素法 .计算过程表 超市仓库B1B2B3B4A1311310A21928A374105.v这方案的总运费为： v 元调运方案表 超市仓库B1B2B3B4储量A1437A2314A3639销量3656.v2、伏格尔法v首先，在分别计算出各行各列的最小运费和次小运费的差额，并填入该列表的最右列和最下行 计算过程表 超市仓库B1B2B3B4行差额A13113100A21
4、9281A3741051列差额2513.v这方案的总运费为 v 元计算过程表 超市仓库B1B2B3B4储量A1527A2314A3639销量3656.指派问题 v在物流活动中，经常会遇到这样的问题，有n项运输任务，恰好有n辆车可承担这些运输任务，由于车型，载重以及司机对道路的熟悉程度等不同，效率也不一样，于是产生了应指派那辆车去完成那项运输任务，使总效率最高或费用最小，或时间最短），这类问题称为指派问题。 .v问题要求极小化时数学模型是v .v例题：某物流公司现有四项运输任务A、B、C、D，现有甲、乙、丙、丁四辆车，他们完成任务所需时间如表所示。问应指派何人去完成何工作，使所需总时间最少？完成
5、任务所需时间表 任务人员ABCD甲215134乙1041415丙9141613丁78119.v第一步：使指派问题的系数矩阵经变换，在各行各列中都出现0元素。 .v第二步：进行试指派，以寻求最优解。v经第一步变换后，系数矩阵中每行每列都有了0元素；但需要找出n各独立的0元素。若能找出，就以这些独立0元素对应解矩阵 中的元素为1，其余为0，这就得到最优解。v最优解为 v这表示：指定甲去完成D项运输任务，乙去完成B项运输任务，丙去完成A项运输任务，丁去完成C项任务。 .最短路问题 v假定下图是一个由城市到城市的有向交通图，弧旁的数字表示各条路线的距离，那么最短路问题就是寻找一条从城市到城市的最短路径
6、。.求解最短路问题的基本思路 v狄克斯托(Dijkstra)标号法是求解最短路问题的有效算法之一。它的基本思路是逐点求最短路。例如图中，假如 是从 的最短路，那么由点 出发沿这条最短路到达中间的任一点，也是从 点到达该任意点的最短路。否则的话在这两点之间还存在其他最短路，那么 就不是从 到 的最短路，与原假设矛盾。因而，从起点开始逐点寻找到邻近点的最短路，直到将最短路延伸到指定的终点为止，就自然找到了从起点到终点的最短。 .中国邮递员问题 v一个邮递员送信，要走完他负责投递的全部街道，投完后回到邮局，应该怎样走，使所走的路程最短。 v这个问题是我国管梅谷同志1962年首先求出来的，因此在国际上
7、通称为中国邮递员问题。在物流活动中，经常会遇到这样的问题：汽车满载货物从配送中心出发，往各条街道的超市或小卖部送货，怎样走路程最短。 .v解决这样的问题，可以采用奇偶点图上作业法：如果在配送范围内，街道中没有奇点，那么他就可以从配送中心出发，走过每条街道一次，且仅一次，最后回到配送中心，这样他所走的路程也就是最短的路程。对于有奇点的街道图，就必须在每条街道上重复走一次或多次。.确定第一方案 v在任何一个连通图中，奇点个数必须为偶数，所以如果图中有奇点，就可以把它们配成对。又因为图是连通的，故每一对奇点之间必有一条链，把这条链的所有边作为重复边加到图中去，可见新图中比无奇点，这就给出了第一个可行方案。 .调整可行方案 v在最优方案中,图的每一边最多有一条重复边v在最优方案中,图中每个圈上的重复边的总权不大于该圈总权的一半 v .
