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

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