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