物流运筹学第4章 运输最优化ppt课件

1、第四章第四章 运输最优化运输最优化本章将讨论以下几个方面的内容：v线性规划与单纯形法简介v运输问题v指派问题v最短路问题v转运问题v中国邮递员问题线性规划简介 v线性规划问题的标准型式 nnxcxcxcz2211max0,)(21221122222121112121111nnnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxaMv用矩阵描述时为 v b为资源向量；v c为价值向量；v x为决策变量的向量 CXz maxbAX 0X0X),(212111211nmnmmnpppaaaaaaA单纯形法简介 v单纯形法的基本思路:根据问题的标准,从可行域中某个基可行解(一个顶点)开场,

2、转换到一个基可行解(顶点),并且使目标函数达到最大值时,问题就得到了最优解。 v例如以下问题v经变换，得到一个基可行解v此时，目标函数的表达式v这说明若要用剩余资源 ，就必须支付附加费用。所以 时，即不再利用这些资源时，目标函数达到最大值。所以 是最优解。 5432100032maxxxxxxz124164825241321xxxxxxx5 , 2 , 1, 0jxjTX)4 , 0 , 0 , 2 , 4()3(43125. 05 . 114xxz43,xx043 xx)3(X运输问题 v已知有m个供应地点 。可供应某种物资，其供应量分别为 ，有n个销地 ，其需要量分别为 ，从 到 运输单位

3、物资的运价单价为 ，这些数据可以汇总到产销平衡表和单位运价表中。若用 表示从 到 的运量，那么供需平衡的条件下，要求得总运费最小的调运方案，可求解以下数学模型： miAi,2, 1,miai, 2 , 1,njBj, 2 , 1,njbj, 2 , 1,iAjBijcijxiAjBijminjijxcz11minnjbxjmiij, 2 , 1,1miaxinjij, 2 , 1,10ijx表上作业法 v例题：某物流公司有三个仓库，每天向四个超市供应某种货物。已知三个仓库A1 、A2 和A3的此货物储藏量分别为7 箱、 4箱和 9箱。该物流公司把这些货物分别送往B1 、B2 、B3 和B4四个

4、超市，各超市每日销量分别为3箱、 6箱、 5箱和6箱。试用表上作业法求解满足供需要求的最佳调运方案，使总运费最少。第一步，画出该问题的供销平衡表和单位运价表 超市仓库B1B2B3B4A1311310A21928A374105 超市仓库B1B2B3B4储量A17A234A39销量3656v第二步，求初始解 v1、最小元素法 计算过程表 超市仓库B1B2B3B4A1311310A21928A374105v这方案的总运费为： v 元调运方案表 超市仓库B1B2B3B4储量A1437A2314A3639销量3656865310321344613v2、伏格尔法v首先，在分别计算出各行各列的最小运费和次小

5、运费的差额，并填入该列表的最右列和最下行 计算过程表 超市仓库B1B2B3B4行差额A13113100A219281A3741051列差额2513v这方案的总运费为 v 元计算过程表 超市仓库B1B2B3B4储量A1527A2314A3639销量3656825381102354613指派问题 v在物流活动中，经常会遇到这样的问题，有n项运输任务，恰好有n辆车可承担这些运输任务，由于车型，载重以及司机对道路的熟悉程度等不同，效率也不一样，于是产生了应指派那辆车去完成那项运输任务，使总效率最高或费用最小，或时间最短），这类问题称为指派问题。 v问题要求极小化时数学模型是v ijijijxczMin

6、 njxiij2 , 1, 1nixjij2 , 1, 101或ijxv例题：某物流公司现有四项运输任务A、B、C、D，现有甲、乙、丙、丁四辆车，他们完成任务所需时间如表所示。问应指派何人去完成何工作，使所需总时间最少？完成任务所需时间表 任务人员ABCD甲215134乙1041415丙9141613丁78119v第一步：使指派问题的系数矩阵经变换，在各行各列中都出现0元素。 9118713161491514410413152)(ijc794224104750111006211130minmin24)(00102350960607130ijbv第二步：进行试指派，以寻求最优解。v经第一步变换后

7、，系数矩阵中每行每列都有了0元素；但需要找出n各独立的0元素。若能找出，就以这些独立0元素对应解矩阵 中的元素为1，其余为0，这就得到最优解。v最优解为 v这表示：指定甲去完成D项运输任务，乙去完成B项运输任务，丙去完成A项运输任务，丁去完成C项任务。 )(ijx0100000100101000)(ijx最短路问题 v假定下图是一个由城市到城市的有向交通图，弧旁的数字表示各条路线的距离，那么最短路问题就是寻找一条从城市到城市的最短路径。求解最短路问题的基本思路 v狄克斯托(Dijkstra)标号法是求解最短路问题的有效算法之一。它的基本思路是逐点求最短路。例如图中，假如 是从 的最短路，那么由

8、点 出发沿这条最短路到达中间的任一点，也是从 点到达该任意点的最短路。否则的话在这两点之间还存在其他最短路，那么 就不是从 到 的最短路，与原假设矛盾。因而，从起点开始逐点寻找到邻近点的最短路，直到将最短路延伸到指定的终点为止，就自然找到了从起点到终点的最短。 75641vvvvv71vv 1v1v75641vvvvv1v7v中国邮递员问题 v一个邮递员送信，要走完他负责投递的全部街道，投完后回到邮局，应该怎样走，使所走的路程最短。 v这个问题是我国管梅谷同志1962年首先求出来的，因此在国际上通称为中国邮递员问题。在物流活动中，经常会遇到这样的问题：汽车满载货物从配送中心出发，往各条街道的超市或小卖部送货，怎样走路程最短。 v解决这样的问题，可以采用奇偶点图上作业法：如果在配送范围内，街道中没有奇点，那么他就可以从配送中心出发，走过每条街道一次，且仅一次，最后回到配送中心，这样他所走的路程也就是最短的路程。对于有奇点的街道图，就必须在每条街道上重复走一次或多次。确定第一方案 v在任何一个连通图中，奇点个数必须为偶数，所以如果图中有奇点，就可