《物流中心规划运输优化技术(ppt 81)13261.pptx》由会员分享，可在线阅读，更多相关《物流中心规划运输优化技术(ppt 81)13261.pptx（83页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、现代物流与物流中心规划 第三章 运输优化技术 Modern Logistics and Logistics centers Planning Modern Logistics and Logistics centers Planning 本章要点n n 运输的主体和客体n n 运输线路选择与优化n n 运输流量优化n n 车辆装载优化n n 运输的主体（实施运输的组织）：（从事运输的）企业（从事运输的）部门（从事运输的）人员n n 运输的客体（运输的对象）：为客户运输的产品运输的主体和客体运输线路的选择和优化 n n3.1.1 3.1.1 单一起迄点的运输线路优化问题单一起迄点的运输线路优化问
2、题n n3.1.2 3.1.2 运输问题运输问题n n3.1.1 3.1.1 单一起迄点的运输线路优化问题单一起迄点的运输线路优化问题在一个交通网络中，寻找由出发点到目的地的 在一个交通网络中，寻找由出发点到目的地的最短路线问题 最短路线问题。单行线交通网络，求 单行线交通网络，求V1 V1到 到V8 V8的最短路线 的最短路线这还用问？这还用问？最短路的求解方法？当然是：Dijkstra算法Dijkstra Dijkstra 算法轻松搞定 算法轻松搞定Dijkstra Dijkstra 算法轻松搞定 算法轻松搞定Dijkstra Dijkstra 算法轻松搞定 算法轻松搞定Dijkstra
3、Dijkstra 算法轻松搞定 算法轻松搞定Dijkstra Dijkstra 算法轻松搞定 算法轻松搞定Dijkstra Dijkstra 算法轻松搞定 算法轻松搞定Dijkstra Dijkstra 算法轻松搞定 算法轻松搞定Dijkstra Dijkstra 算法轻松搞定 算法轻松搞定Dijkstra Dijkstra 算法轻松搞定 算法轻松搞定Dijkstra Dijkstra 算法轻松搞定 算法轻松搞定Dijkstra Dijkstra 算法轻松搞定 算法轻松搞定Dijkstra Dijkstra 算法轻松搞定 算法轻松搞定Dijkstra Dijkstra 算法轻松搞定 算法轻松搞
4、定Dijkstra算法非常适合使用计算机进行求解。地球人都知道 地球人都知道 仅考虑最短距离，而不考虑运行时间？晕 晕!3.1.2 运输问题n n 平衡运输问题n n 不平衡运输问题3.1.2 3.1.2 运输问题平衡运输问题运输问题平衡运输问题算例：某玻璃制造厂与三个不同地点的纯碱供应商签订合同，由他们供货给三个分厂，条件是不超过合同所定的数量，但必须满足生产需要。该问题如表3-1所示。问题中所给费率是每个供应商到每个工厂之间最短路径的运输费率。求运输方案3.1.2 3.1.2 运输问题平衡运输问题运输问题平衡运输问题工厂工厂11工厂工厂22工厂工厂33供应量供应量供应商供应商11x11x1
5、1x12x12x13x13400400供应商供应商22x21x21x22x22x23x23700700供应商供应商33x31x31x32x32x33x33500500需求量需求量 6006005005005005003-13-1运输问题供需情况运输问题供需情况供销平衡供销平衡3.1.2 3.1.2 运输问题平衡运输问题运输问题平衡运输问题工厂工厂11工厂工厂22工厂工厂33供应商供应商11447766供应商供应商22331144供应商供应商339955883-13-1运输问题运输成本运输问题运输成本3.1.2 3.1.2 运输问题平衡运输问题运输问题平衡运输问题求解算法表上作业法3.1.2 3
6、.1.2 运输问题平衡运输问题运输问题平衡运输问题 表上作业法非常适合大脑中有两块 P4-CPU的人:(1):展示自己非凡的计算才能(2):体验当年的工作艰辛准备好笔、橡皮和纸吧 准备好笔、橡皮和纸吧准备开始讲求解算法？麻 烦！你确认你的 你确认你的CPU CPU是 是P4 P4的么 的么？求解算法数学软件包工欲善其事，必先利其器工欲善其事，必先利其器 LingoLINGO LINGO:L Linear inear IN INteractive teractive G General eneral O Optimizer ptimizerLingo给我们带来了什么？大家下课后认真思考 大家下课
7、后认真思考 采用Lingo求解运输问题需要准备什么？n n 构造好明确的数学模型n n 将数学模型按照指定的语法规范输入软件供销平衡情况供销平衡情况 就是这么简单 就是这么简单 3.1.2 3.1.2 运输问题不平衡运输问题运输问题不平衡运输问题n n 供大于需n n 需大于供 表上作业法需要设立虚拟库存，将该问题转化成为一个平衡运输问题求解 Lingo 软件法需要修改供需约束的不等号，再进行求解3.1.2 3.1.2 运输问题不平衡运输问题运输问题不平衡运输问题销地销地11销地销地22销地销地33销地销地44产量产量产地产地11x11x11x12x12x13x13x14x1466产地产地22
8、x21x21x22x22x23x23x24x2444产地产地33x31x31x32x32x33x33x34x3466销量销量 22223355不平衡不平衡 产量为 产量为6+4+6=16 6+4+6=16，销量为，销量为2+2+3+5=12 2+2+3+5=12。产。产量比销量多 量比销量多4 4。从供需平衡看，需要虚拟库存。从供需平衡看，需要虚拟库存 不平衡运输的例子：不平衡运输的例子：3.1.2 3.1.2 运输问题不平衡运输问题运输问题不平衡运输问题销地销地11销地销地22销地销地33销地销地44产地产地112210103344产地产地2288335577产地产地33668811223.
9、1.2 3.1.2 运输问题不平衡运输问题运输问题不平衡运输问题 表上作业法的思路：表上作业法的思路：转化成为一个平衡问题 转化成为一个平衡问题例如：例如：销地销地11销地销地22销地销地33销地销地44产量产量产地产地11x11x11x12x12x13x13x14x1455产地产地22x21x21x22x22x23x23x24x2433产地产地33x31x31x32x32x33x33x34x3444销量销量 22223355平衡平衡 产地 产地1 1 存储 存储1 1，产地，产地2 2 存储 存储1 1，产地，产地3 3 存储 存储2 2，此时平，此时平衡 衡3.1.2 3.1.2 运输问题
10、不平衡运输问题运输问题不平衡运输问题 Lingo Lingo 作业法的思路：作业法的思路：修改对应的供需约束条件 修改对应的供需约束条件例如：例如：3.1.2 3.1.2 运输问题不平衡运输问题运输问题不平衡运输问题强！运输问题搞定 运输问题搞定 3.1.2 3.1.2 运输问题不平衡运输问题运输问题不平衡运输问题如果用如果用LingoLingo求解最短路线问题如何？求解最短路线问题如何？（该部分仅做了解，不作为考试的考察内容）（该部分仅做了解，不作为考试的考察内容）当然可以！如果用如果用LingoLingo求解最短路线问题如何？求解最短路线问题如何？单行线交通网络，求 单行线交通网络，求V1
11、 V1到 到V8 V8的最短路线 的最短路线如果用如果用LingoLingo求解最短路线问题如何？求解最短路线问题如何？为了寻找网络的最短路线距离，我们将使用下面的为了寻找网络的最短路线距离，我们将使用下面的动态规划递归式：动态规划递归式：F(i)F(i)是从节点是从节点ii到终点的最短距离，到终点的最短距离，D(i,j)D(i,j)是从节是从节点点ii到节点到节点jj的距离。的距离。具体说：从节点具体说：从节点ii到终点的最短距离是从节点到终点的最短距离是从节点ii到临到临接点的距离加上邻接点的终点的最小距离之和的最接点的距离加上邻接点的终点的最小距离之和的最小值小值用用LingoLingo
12、求解最短路线问题的计算结果求解最短路线问题的计算结果从 从V1 V1到 到V8 V8的最短距离 的最短距离F(1)F(1)12 12，对应的路径可以对应找出，对应的路径可以对应找出LingoLingo求解最短路线问题求解最短路线问题很强！Lingo Lingo 能整的东西还挺多 能整的东西还挺多 运输流量优化 n n3.2.1 3.2.1 最大运输流量问题最大运输流量问题n n3.2.2 3.2.2 最小费用最大流问题最小费用最大流问题最大运输流量问题 如下图所示，连接煤产地 如下图所示，连接煤产地V1 V1（发点）到销地（发点）到销地V6 V6（收点）的交（收点）的交通网络，通网络，V2 V
13、2、V3 V3、V5 V5 表示交通网络的中间节点，每条运输线 表示交通网络的中间节点，每条运输线（弧）上的数字表示这条线的单位时间最大通过能力（称弧的（弧）上的数字表示这条线的单位时间最大通过能力（称弧的容量），现在要制订一个运输方案，使单位时间从发点 容量），现在要制订一个运输方案，使单位时间从发点V1 V1 到 到点 点V6 V6 煤的运输量最多？煤的运输量最多？可行流的网络 2：最大流 所谓最大流就是在有容量限制的网络中流量最大的可行流。所谓最大流就是在有容量限制的网络中流量最大的可行流。最大流问题 最大流问题 应用很广泛 应用很广泛：运输系统中的车辆流、物资流；运输系统中的车辆流、物
14、资流；通讯系统中的信息流；通讯系统中的信息流；供水系统中的水流；供水系统中的水流；供电系统中的电；供电系统中的电；金融系统中的资金流；金融系统中的资金流；供销系统中的商品流都有最大流问题的足迹。供销系统中的商品流都有最大流问题的足迹。涉猎广泛 涉猎广泛 求最大流的方法 n n标号法标号法n nLingoLingo软件求解法软件求解法还用 还用Lingo Lingo？标号法思路 第一个初始可行解如何给出？最简单的办法是每条弧上的流量都为零优点：简单缺点：可能会增加调整次数增广链及流的调整法前向弧、后向弧以及增广链的概念 用标号法找出网络中的最大流 给出初始可行流：给出初始可行流：第一次流量调整就
15、完成了第一次流量调整就完成了累！继续讲 继续讲 接下来，再在新的可行流基础上，从发点开始重新标号找增广链并对此调整，直至找不到增广链，即找到最大流为止第二次寻找增广链寻找过程第二次寻找增广链寻找过程第二次寻找增广链流量调整第二次寻找增广链流量调整第三次寻找增广链寻找过程第三次寻找增广链寻找过程第三次寻找增广链流量调整第三次寻找增广链流量调整第四次寻找增广链寻找过程第四次寻找增广链寻找过程终于完成了！看 看Lingo Lingo 轻松搞定 轻松搞定 Lingo的必须构造好明确的数学模型目标函数：路段上流量最大目标函数：路段上流量最大约束条件约束条件：（可行流的满足条件）：（可行流的满足条件）EA
16、SY！真能整 真能整 多个发点和收点的运输流量问题问题 问题：在运输流量问题中，可能同时存在多个发点可以供应某 在运输流量问题中，可能同时存在多个发点可以供应某种物资，也可能多个收点需要这种物资。种物资，也可能多个收点需要这种物资。多个发点和收点的运输流量问题解决方式 解决方式：将问题转化成为只有一个收点和一个发点的网络最大流 将问题转化成为只有一个收点和一个发点的网络最大流问题，运用相关方法求解 问题，运用相关方法求解最小费用最大流问题 问题的提出：在实际的物流运作过程中，不仅要考虑容量限制下的流量问题，而且还要求考虑费用问题。例如：某公司欲将产品从工厂运到仓库，虽然可以在许多运输线路中选择
17、，在不同的路线上，运费是不同的，而每条路线只能负担有限的货物运输量。如何找到运费最小的货物运输方式，并尽可能多地运输产品。这就构成了所谓的：最小费用，最大流问题。赋权图法对问题进行求解 求解最小费用流的算法很多，其中易于理解的一种流行算法是用最短路算法求最小费用的增广链。算法思路：（1）从零流开始，在始点到终点的所有可能增加流量的增广链中寻找总费用最小的的链，并对该链增加流量，得到第一次调整后的最小费用流。（2）再次寻找所有的增广链，找到此时费用最小的链，增加流量。（3）依此类推，直到网络中找不到增广链为止。此时的可行流就是最小费用流。赋权图法对问题进行求解（续）如何寻找总费用最小的的链？构造赋权图它的顶点还是原网络中各弧的顶点。而弧的构造则分成下面三种情况：赋权图法对问题进行求解（续）谢谢观看/欢迎下载BY FAITH I MEAN A VISION OF GOOD ONE CHERISHES AND THE ENTHUSIASM THAT PUSHES ONE TO SEEK ITS FULFILLMENT REGARDLESS OF OBSTACLES.BY FAITH I BY FAITH