《物流中心规划及运输行业知识》由会员分享,可在线阅读,更多相关《物流中心规划及运输行业知识(114页珍藏版)》请在金锄头文库上搜索。
1、来自 中国最大的资料库下载,现代物流与物流中心规划,第三章 运输优化技术,Modern Logistics and Logistics centers Planning,来自 中国最大的资料库下载,本章要点,运输的主体和客体 运输线路选择与优化 运输流量优化 车辆装载优化,来自 中国最大的资料库下载,运输的主体(实施运输的组织): (从事运输的)企业 (从事运输的)部门 (从事运输的)人员 运输的客体(运输的对象): 为客户运输的产品,运输的主体和客体,来自 中国最大的资料库下载,运输线路的选择和优化,3.1.1 单一起迄点的运输线路优化问题 3.1.2 运输问题,来自 中国最大的资料库下载,
2、3.1.1 单一起迄点的运输线路优化问题,在一个交通网络中,寻找由出发点到目的地的最短路线问题。,单行线交通网络,求V1到V8的最短路线,来自 中国最大的资料库下载,这还用问?,最短路的求解方法? 当然是:Dijkstra算法,来自 中国最大的资料库下载,Dijkstra算法轻松搞定,来自 中国最大的资料库下载,Dijkstra算法轻松搞定,来自 中国最大的资料库下载,Dijkstra算法轻松搞定,来自 中国最大的资料库下载,Dijkstra算法轻松搞定,来自 中国最大的资料库下载,Dijkstra算法轻松搞定,来自 中国最大的资料库下载,Dijkstra算法轻松搞定,来自 中国最大的资料库下
3、载,Dijkstra算法轻松搞定,来自 中国最大的资料库下载,Dijkstra算法轻松搞定,来自 中国最大的资料库下载,Dijkstra算法轻松搞定,来自 中国最大的资料库下载,Dijkstra算法轻松搞定,来自 中国最大的资料库下载,Dijkstra算法轻松搞定,来自 中国最大的资料库下载,Dijkstra算法轻松搞定,来自 中国最大的资料库下载,Dijkstra算法轻松搞定,来自 中国最大的资料库下载,Dijkstra算法非常适合使用计算机进行求解。,地球人都知道,来自 中国最大的资料库下载,仅考虑最短距离, 而不考虑运行时间?,晕!,来自 中国最大的资料库下载,3.1.2 运输问题,平衡
4、运输问题 不平衡运输问题,来自 中国最大的资料库下载,3.1.2 运输问题平衡运输问题,来自 中国最大的资料库下载,算例:某玻璃制造厂与三个不同地点的纯碱供应商签订合同,由他们供货给三个分厂,条件是不超过合同所定的数量,但必须满足生产需要。该问题如表3-1所示。问题中所给费率是每个供应商到每个工厂之间最短路径的运输费率。求运输方案,3.1.2 运输问题平衡运输问题,来自 中国最大的资料库下载,3-1运输问题供需情况,供销平衡,3.1.2 运输问题平衡运输问题,来自 中国最大的资料库下载,3-1运输问题运输成本,3.1.2 运输问题平衡运输问题,来自 中国最大的资料库下载,求解算法表上作业法,3
5、.1.2 运输问题平衡运输问题,来自 中国最大的资料库下载,表上作业法非常适合大脑中有两块 P4-CPU的人: (1):展示自己非凡的计算才能 (2):体验当年的工作艰辛,准备好笔、橡皮和纸吧,来自 中国最大的资料库下载,准备开始讲求解算法? 麻 烦!,你确认你的CPU是P4的么?,来自 中国最大的资料库下载,求解算法数学软件包,工欲善其事,必先利其器,Lingo,LINGO: Linear INteractive General Optimizer,来自 中国最大的资料库下载,Lingo 给我们带来了什么?,大家下课后认真思考,来自 中国最大的资料库下载,采用Lingo求解运输问题需要准备什
6、么?,构造好明确的数学模型 将数学模型按照指定的语法规范输入软件,来自 中国最大的资料库下载,供销平衡情况,来自 中国最大的资料库下载,就是这么简单,来自 中国最大的资料库下载,3.1.2 运输问题不平衡运输问题,供大于需 需大于供,表上作业法需要设立虚拟库存,将该问题转化成为一个平衡运输问题求解 Lingo软件法需要修改供需约束的不等号,再进行求解,来自 中国最大的资料库下载,3.1.2 运输问题不平衡运输问题,产量为6+4+6=16,销量为2+2+3+5=12。产量比销量多4。从供需平衡看,需要虚拟库存,不平衡运输的例子:,来自 中国最大的资料库下载,3.1.2 运输问题不平衡运输问题,来
7、自 中国最大的资料库下载,3.1.2 运输问题不平衡运输问题,表上作业法的思路:转化成为一个平衡问题 例如:,产地1存储1,产地2存储1,产地3存储2,此时平衡,来自 中国最大的资料库下载,3.1.2 运输问题不平衡运输问题,Lingo作业法的思路:修改对应的供需约束条件 例如:,来自 中国最大的资料库下载,3.1.2 运输问题不平衡运输问题,来自 中国最大的资料库下载,强!,运输问题搞定,3.1.2 运输问题不平衡运输问题,来自 中国最大的资料库下载,如果用Lingo求解最短路线问题如何?,(该部分仅做了解,不作为考试的考察内容),当然可以!,来自 中国最大的资料库下载,如果用Lingo求解
8、最短路线问题如何?,单行线交通网络,求V1到V8的最短路线,来自 中国最大的资料库下载,如果用Lingo求解最短路线问题如何?,为了寻找网络的最短路线距离,我们将使用下面的动态规划递归式:,F(i)是从节点i到终点的最短距离,D(i,j)是从节点i到节点j的距离。 具体说:从节点i到终点的最短距离是从节点i到临接点的距离加上邻接点的终点的最小距离之和的最小值,来自 中国最大的资料库下载,用Lingo求解最短路线问题的计算结果,从V1到V8的最短距离F(1)12,对应的路径可以对应找出,来自 中国最大的资料库下载,Lingo求解最短路线问题,很强!,Lingo能整的东西还挺多,来自 中国最大的资
9、料库下载,运输流量优化,3.2.1 最大运输流量问题 3.2.2 最小费用最大流问题,来自 中国最大的资料库下载,最大运输流量问题,如下图所示,连接煤产地V1(发点)到销地V6(收点)的交通网络,V2、V3、V5表示交通网络的中间节点,每条运输线(弧)上的数字表示这条线的单位时间最大通过能力(称弧的容量),现在要制订一个运输方案,使单位时间从发点V1到点V6煤的运输量最多?,来自 中国最大的资料库下载,来自 中国最大的资料库下载,可行流的网络,来自 中国最大的资料库下载,2:最大流 所谓最大流就是在有容量限制的网络中流量最大的可行流。 最大流问题应用很广泛: 运输系统中的车辆流、物资流; 通讯
10、系统中的信息流; 供水系统中的水流; 供电系统中的电; 金融系统中的资金流; 供销系统中的商品流都有最大流问题的足迹。,涉猎广泛,来自 中国最大的资料库下载,求最大流的方法,标号法 Lingo软件求解法,还用Lingo?,来自 中国最大的资料库下载,标号法思路,来自 中国最大的资料库下载,第一个初始可行解如何给出?,最简单的办法是每条弧上的流量都为零 优点:简单 缺点:可能会增加调整次数,来自 中国最大的资料库下载,增广链及流的调整法,来自 中国最大的资料库下载,前向弧、后向弧以及增广链的概念,来自 中国最大的资料库下载,来自 中国最大的资料库下载,来自 中国最大的资料库下载,来自 中国最大的
11、资料库下载,用标号法找出网络中的最大流,给出初始可行流:,来自 中国最大的资料库下载,来自 中国最大的资料库下载,来自 中国最大的资料库下载,来自 中国最大的资料库下载,来自 中国最大的资料库下载,第一次流量调整就完成了,累!,继续讲,来自 中国最大的资料库下载,接下来,再在新的可行流基础上,从发点开始重新标号找增广链并对此调整,直至找不到增广链,即找到最大流为止,来自 中国最大的资料库下载,第二次寻找增广链寻找过程,来自 中国最大的资料库下载,第二次寻找增广链流量调整,来自 中国最大的资料库下载,第三次寻找增广链寻找过程,来自 中国最大的资料库下载,第三次寻找增广链流量调整,来自 中国最大的
12、资料库下载,第四次寻找增广链寻找过程,来自 中国最大的资料库下载,终于完成了!,看Lingo轻松搞定,来自 中国最大的资料库下载,Lingo的必须构造好明确的数学模型,目标函数:路段上流量最大 约束条件:(可行流的满足条件),来自 中国最大的资料库下载,来自 中国最大的资料库下载,EASY!,真能整,来自 中国最大的资料库下载,多个发点和收点的运输流量问题,问题: 在运输流量问题中,可能同时存在多个发点可以供应某种物资,也可能多个收点需要这种物资。,来自 中国最大的资料库下载,多个发点和收点的运输流量问题,解决方式: 将问题转化成为只有一个收点和一个发点的网络最大流问题,运用相关方法求解,来自
13、 中国最大的资料库下载,最小费用最大流问题,问题的提出: 在实际的物流运作过程中,不仅要考虑容量限制下的流量问题,而且还要求考虑费用问题。 例如:某公司欲将产品从工厂运到仓库,虽然可以在许多运输线路中选择,在不同的路线上,运费是不同的,而每条路线只能负担有限的货物运输量。如何找到运费最小的货物运输方式,并尽可能多地运输产品。 这就构成了所谓的:最小费用,最大流问题。,来自 中国最大的资料库下载,赋权图法对问题进行求解,求解最小费用流的算法很多,其中易于理解的一种流行算法是用最短路算法求最小费用的增广链。 算法思路: (1)从零流开始,在始点到终点的所有可能增加流量的增广链中寻找总费用最小的的链
14、,并对该链增加流量,得到第一次调整后的最小费用流。 (2)再次寻找所有的增广链,找到此时费用最小的链,增加流量。 (3)依此类推,直到网络中找不到增广链为止。此时的可行流就是最小费用流。,来自 中国最大的资料库下载,赋权图法对问题进行求解(续),如何寻找总费用最小的的链?构造赋权图 它的顶点还是原网络中各弧的顶点。而弧的构造则分成下面三种情况:,来自 中国最大的资料库下载,括号内数字依此为流量、容量、费用,来自 中国最大的资料库下载,赋权图法对问题进行求解(续),来自 中国最大的资料库下载,赋权图法的算例,大家开始手工构造一个赋权图,来自 中国最大的资料库下载,赋权图法的算例,是这样的么?咱们
15、开始找最短路,来自 中国最大的资料库下载,赋权图法的算例,最短路的费用为1+2+1=4 对了吧,咱们继续!要开始调整流量了,来自 中国最大的资料库下载,第一次流量调整的结果,继续,构造第二次流量调整所需的赋权图,来自 中国最大的资料库下载,赋权图法的算例,是这样的么?咱们开始找最短路,来自 中国最大的资料库下载,赋权图法的算例,最短路的费用为1+3+2=6,来自 中国最大的资料库下载,第二次流量调整的结果,来自 中国最大的资料库下载,赋权图法的算例,是这样的么?咱们开始找最短路,来自 中国最大的资料库下载,赋权图法的算例,最短路的费用为4-2+3+2=7,来自 中国最大的资料库下载,第三次流量
16、调整的结果,来自 中国最大的资料库下载,赋权图法的算例,咱们开始找最短路,谁先找到请举手!,来自 中国最大的资料库下载,赋权图法的算例,咱们开始找最短路,谁先找到请举手!,不存在从Vs到Vt的通路。因此不存在增广链,算法终止!,来自 中国最大的资料库下载,最终的最大费用最小流,来自 中国最大的资料库下载,最终的最大费用最小流,图上作业法的确很适合人工运算,如果采用Lingo你有好办法么?,感兴趣的同学可以回去用Lingo实验一下,来自 中国最大的资料库下载,车辆配载优化装货问题,车辆配载问题一般解决思路:可以化为多阶段问题,运用动态规划的方法求解。 问题描述:,来自 中国最大的资料库下载,如此明显的模型表达式,不使用Lingo 还等什么?,造个例子开始用Lingo,车辆配载优化装货问题,来自 中国最大的资料库下载,重量为8t的载重卡车,运输4种货物。它们重量分别为3,3,4,5t(如下表所示),问如