《物流中心规划运输优化技术(ppt 81).PPT》由会员分享，可在线阅读，更多相关《物流中心规划运输优化技术(ppt 81).PPT（82页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、现代物流与物流中心规划 第三章第三章 运输优化技术运输优化技术 Modern Logistics and Logistics centers PlanningModern Logistics and Logistics centers Planning 来自来自 中国最大的中国最大的资料库下载资料库下载本章要点n n运输的主体和客体运输的主体和客体n n运输线路选择与优化运输线路选择与优化n n运输流量优化运输流量优化n n车辆装载优化车辆装载优化来自来自 中国最大的中国最大的资料库下载资料库下载n n运输的主体（实施运输的组织）：（从事运输的）企业（从事运输的）部门（从事运输的）人员n n运
2、输的客体（运输的对象）：为客户运输的产品运输的主体和客体来自来自 中国最大的中国最大的资料库下载资料库下载运输线路的选择和优化 n n3.1.1 3.1.1 单一起迄点的运输线路优化问题单一起迄点的运输线路优化问题n n3.1.2 3.1.2 运输问题运输问题来自来自 中国最大的中国最大的资料库下载资料库下载n n3.1.1 3.1.1 单一起迄点的运输线路优化问题单一起迄点的运输线路优化问题单一起迄点的运输线路优化问题单一起迄点的运输线路优化问题在一个交通网络中，寻找由出发点到目的地的在一个交通网络中，寻找由出发点到目的地的在一个交通网络中，寻找由出发点到目的地的在一个交通网络中，寻找由出发
3、点到目的地的最短路线问题最短路线问题最短路线问题最短路线问题。单行线交通网络，求单行线交通网络，求单行线交通网络，求单行线交通网络，求V1V1到到到到V8V8的最短路线的最短路线的最短路线的最短路线来自来自 中国最大的中国最大的资料库下载资料库下载这还用问？这还用问？最短路的求解方法？最短路的求解方法？当然是：当然是：Dijkstra算法算法来自来自 中国最大的中国最大的资料库下载资料库下载DijkstraDijkstraDijkstraDijkstra算法轻松搞定算法轻松搞定算法轻松搞定算法轻松搞定来自来自 中国最大的中国最大的资料库下载资料库下载DijkstraDijkstraDijkst
4、raDijkstra算法轻松搞定算法轻松搞定算法轻松搞定算法轻松搞定来自来自 中国最大的中国最大的资料库下载资料库下载DijkstraDijkstraDijkstraDijkstra算法轻松搞定算法轻松搞定算法轻松搞定算法轻松搞定来自来自 中国最大的中国最大的资料库下载资料库下载DijkstraDijkstraDijkstraDijkstra算法轻松搞定算法轻松搞定算法轻松搞定算法轻松搞定来自来自 中国最大的中国最大的资料库下载资料库下载DijkstraDijkstraDijkstraDijkstra算法轻松搞定算法轻松搞定算法轻松搞定算法轻松搞定来自来自 中国最大的中国最大的资料库下载资料库
5、下载DijkstraDijkstraDijkstraDijkstra算法轻松搞定算法轻松搞定算法轻松搞定算法轻松搞定来自来自 中国最大的中国最大的资料库下载资料库下载DijkstraDijkstraDijkstraDijkstra算法轻松搞定算法轻松搞定算法轻松搞定算法轻松搞定来自来自 中国最大的中国最大的资料库下载资料库下载DijkstraDijkstraDijkstraDijkstra算法轻松搞定算法轻松搞定算法轻松搞定算法轻松搞定来自来自 中国最大的中国最大的资料库下载资料库下载DijkstraDijkstraDijkstraDijkstra算法轻松搞定算法轻松搞定算法轻松搞定算法轻松搞
6、定来自来自 中国最大的中国最大的资料库下载资料库下载DijkstraDijkstraDijkstraDijkstra算法轻松搞定算法轻松搞定算法轻松搞定算法轻松搞定来自来自 中国最大的中国最大的资料库下载资料库下载DijkstraDijkstraDijkstraDijkstra算法轻松搞定算法轻松搞定算法轻松搞定算法轻松搞定来自来自 中国最大的中国最大的资料库下载资料库下载DijkstraDijkstraDijkstraDijkstra算法轻松搞定算法轻松搞定算法轻松搞定算法轻松搞定来自来自 中国最大的中国最大的资料库下载资料库下载DijkstraDijkstraDijkstraDijkstr
7、a算法轻松搞定算法轻松搞定算法轻松搞定算法轻松搞定来自来自 中国最大的中国最大的资料库下载资料库下载Dijkstra算法非常适合使用计算算法非常适合使用计算机进行求解。机进行求解。地球人都知道地球人都知道地球人都知道地球人都知道来自来自 中国最大的中国最大的资料库下载资料库下载 仅考虑最短距离，仅考虑最短距离，而而不考虑运行时间不考虑运行时间？晕晕晕晕!来自来自 中国最大的中国最大的资料库下载资料库下载3.1.2 运输问题n n平衡运输问题平衡运输问题n n不平衡运输问题不平衡运输问题来自来自 中国最大的中国最大的资料库下载资料库下载3.1.2 3.1.2 运输问题平衡运输问题运输问题平衡运输
8、问题运输问题平衡运输问题运输问题平衡运输问题来自来自 中国最大的中国最大的资料库下载资料库下载算例：某玻璃制造厂与三个不同地点的纯碱算例：某玻璃制造厂与三个不同地点的纯碱供应商签订合同，由他们供货给三个分厂，供应商签订合同，由他们供货给三个分厂，条件是不超过合同所定的数量，但必须满足条件是不超过合同所定的数量，但必须满足生产需要。该问题如表生产需要。该问题如表3-1所示。问题中所所示。问题中所给费率是每个供应商到每个工厂之间最短路给费率是每个供应商到每个工厂之间最短路径的运输费率。径的运输费率。求运输方案求运输方案3.1.2 3.1.2 运输问题平衡运输问题运输问题平衡运输问题运输问题平衡运输
9、问题运输问题平衡运输问题来自来自 中国最大的中国最大的资料库下载资料库下载工厂工厂工厂工厂1 1工厂工厂工厂工厂2 2工厂工厂工厂工厂3 3供应量供应量供应量供应量供应商供应商供应商供应商1 1x11x11x12x12x13x13400400供应商供应商供应商供应商2 2x21x21x22x22x23x23700700供应商供应商供应商供应商3 3x31x31x32x32x33x33500500需求量需求量需求量需求量6006005005005005003-13-1运输问题供需情况运输问题供需情况供销平衡供销平衡3.1.2 3.1.2 运输问题平衡运输问题运输问题平衡运输问题运输问题平衡运输问
10、题运输问题平衡运输问题来自来自 中国最大的中国最大的资料库下载资料库下载工厂工厂工厂工厂1 1工厂工厂工厂工厂2 2工厂工厂工厂工厂3 3供应商供应商供应商供应商1 14 47 76 6供应商供应商供应商供应商2 23 31 14 4供应商供应商供应商供应商3 39 95 58 83-13-1运输问题运输成本运输问题运输成本3.1.2 3.1.2 运输问题平衡运输问题运输问题平衡运输问题运输问题平衡运输问题运输问题平衡运输问题来自来自 中国最大的中国最大的资料库下载资料库下载求解算法求解算法表上作业法表上作业法3.1.2 3.1.2 运输问题平衡运输问题运输问题平衡运输问题运输问题平衡运输问题
11、运输问题平衡运输问题来自来自 中国最大的中国最大的资料库下载资料库下载 表上作业法表上作业法非常适合大脑中有两非常适合大脑中有两块块 P4-CPU的人的人:(1):展示自己非凡的计算才能展示自己非凡的计算才能 (2):体验当年的工作艰辛体验当年的工作艰辛准备好笔、橡皮和纸吧准备好笔、橡皮和纸吧来自来自 中国最大的中国最大的资料库下载资料库下载准备开始讲准备开始讲求解算法求解算法？麻麻 烦！烦！你确认你的你确认你的CPUCPU是是P4P4的么的么？来自来自 中国最大的中国最大的资料库下载资料库下载求解算法求解算法数学软件包数学软件包工欲善其事，必先利其器工欲善其事，必先利其器 LingoLING
12、OLINGO:L Linearinear ININteractiveteractive GGeneral eneral OOptimizerptimizer来自来自 中国最大的中国最大的资料库下载资料库下载Lingo给我们带来了什么？给我们带来了什么？大家下课后认真思考大家下课后认真思考来自来自 中国最大的中国最大的资料库下载资料库下载 采用采用Lingo求解运输问题需要准求解运输问题需要准备什么？备什么？n n构造好明确的数学模型构造好明确的数学模型n n将数学模型按照指定的语法规范输入软件将数学模型按照指定的语法规范输入软件来自来自 中国最大的中国最大的资料库下载资料库下载供销平衡情况供销
13、平衡情况 来自来自 中国最大的中国最大的资料库下载资料库下载就是这么简单就是这么简单 来自来自 中国最大的中国最大的资料库下载资料库下载3.1.2 3.1.2 运输问题不平衡运输问题运输问题不平衡运输问题运输问题不平衡运输问题运输问题不平衡运输问题n n供大于需供大于需n n需大于供需大于供 表上作业法需要设立虚拟库存，将该问题转化成为一个平衡运输问题求解 Lingo软件法需要修改供需约束的不等号，再进行求解来自来自 中国最大的中国最大的资料库下载资料库下载3.1.2 3.1.2 运输问题不平衡运输问题运输问题不平衡运输问题运输问题不平衡运输问题运输问题不平衡运输问题销地销地1 1销地销地2
14、2销地销地3 3销地销地4 4产量产量产地产地1 1x11x11x12x12x13x13x14x146 6产地产地2 2x21x21x22x22x23x23x24x244 4产地产地3 3x31x31x32x32x33x33x34x346 6销量销量2 22 23 35 5不平衡不平衡不平衡不平衡 产量为产量为6+4+6=166+4+6=16，销量为，销量为2+2+3+5=122+2+3+5=12。产。产量比销量多量比销量多4 4。从供需平衡看，需要虚拟库存。从供需平衡看，需要虚拟库存 不平衡运输的例子：不平衡运输的例子：来自来自 中国最大的中国最大的资料库下载资料库下载3.1.2 3.1.2
15、 运输问题不平衡运输问题运输问题不平衡运输问题运输问题不平衡运输问题运输问题不平衡运输问题销地销地1 1销地销地2 2销地销地3 3销地销地4 4产地产地1 12 210103 34 4产地产地2 28 83 35 57 7产地产地3 36 68 81 12 2来自来自 中国最大的中国最大的资料库下载资料库下载3.1.2 3.1.2 运输问题不平衡运输问题运输问题不平衡运输问题运输问题不平衡运输问题运输问题不平衡运输问题 表上作业法的思路：表上作业法的思路：转化成为一个平衡问题转化成为一个平衡问题例如：例如：销地销地1 1销地销地2 2销地销地3 3销地销地4 4产量产量产地产地1 1x11x
16、11x12x12x13x13x14x145 5产地产地2 2x21x21x22x22x23x23x24x243 3产地产地3 3x31x31x32x32x33x33x34x344 4销量销量2 22 23 35 5平衡平衡平衡平衡 产地产地1 1存储存储1 1，产地，产地2 2存储存储1 1，产地，产地3 3存储存储2 2，此时平，此时平衡衡来自来自 中国最大的中国最大的资料库下载资料库下载3.1.2 3.1.2 运输问题不平衡运输问题运输问题不平衡运输问题运输问题不平衡运输问题运输问题不平衡运输问题 LingoLingo作业法的思路：作业法的思路：修改对应的供需约束条件修改对应的供需约束条件
17、例如：例如：来自来自 中国最大的中国最大的资料库下载资料库下载3.1.2 3.1.2 运输问题不平衡运输问题运输问题不平衡运输问题运输问题不平衡运输问题运输问题不平衡运输问题来自来自 中国最大的中国最大的资料库下载资料库下载强强！运输问题搞定运输问题搞定 3.1.2 3.1.2 运输问题不平衡运输问题运输问题不平衡运输问题运输问题不平衡运输问题运输问题不平衡运输问题来自来自 中国最大的中国最大的资料库下载资料库下载如果用如果用如果用如果用LingoLingo求解最短路线问题如何？求解最短路线问题如何？求解最短路线问题如何？求解最短路线问题如何？（该部分仅做了解，不作为考试的考察内容）（该部分仅
18、做了解，不作为考试的考察内容）当然当然可以可以！来自来自 中国最大的中国最大的资料库下载资料库下载如果用如果用如果用如果用LingoLingo求解最短路线问题如何？求解最短路线问题如何？求解最短路线问题如何？求解最短路线问题如何？单行线交通网络，求单行线交通网络，求单行线交通网络，求单行线交通网络，求V1V1到到到到V8V8的最短路线的最短路线的最短路线的最短路线来自来自 中国最大的中国最大的资料库下载资料库下载如果用如果用如果用如果用LingoLingo求解最短路线问题如何？求解最短路线问题如何？求解最短路线问题如何？求解最短路线问题如何？为了寻找网络的最短路线距离，我们将使用下面的为了寻找
19、网络的最短路线距离，我们将使用下面的动态规划递归式：动态规划递归式：F(iF(iF(iF(i)是从节点是从节点是从节点是从节点i i i i到终点的最短距离，到终点的最短距离，到终点的最短距离，到终点的最短距离，D(i,jD(i,jD(i,jD(i,j)是从节是从节是从节是从节点点点点i i i i到节点到节点到节点到节点j j j j的距离。的距离。的距离。的距离。具体说：从节点具体说：从节点具体说：从节点具体说：从节点i i i i到终点的最短距离是从节点到终点的最短距离是从节点到终点的最短距离是从节点到终点的最短距离是从节点i i i i到临到临到临到临接点的距离加上邻接点的终点的最小距
20、离之和的最接点的距离加上邻接点的终点的最小距离之和的最接点的距离加上邻接点的终点的最小距离之和的最接点的距离加上邻接点的终点的最小距离之和的最小值小值小值小值来自来自 中国最大的中国最大的资料库下载资料库下载用用用用LingoLingo求解最短路线问题的计算结果求解最短路线问题的计算结果求解最短路线问题的计算结果求解最短路线问题的计算结果从从从从V1V1到到到到V8V8的最短距离的最短距离的最短距离的最短距离F(1)F(1)1212，对应的路径可以对应找出，对应的路径可以对应找出，对应的路径可以对应找出，对应的路径可以对应找出来自来自 中国最大的中国最大的资料库下载资料库下载LingoLing
21、o求解最短路线问题求解最短路线问题求解最短路线问题求解最短路线问题很很强强！LingoLingo能整的东西还挺多能整的东西还挺多 来自来自 中国最大的中国最大的资料库下载资料库下载运输流量优化 n n3.2.1 3.2.1 最大运输流量问题最大运输流量问题n n3.2.2 3.2.2 最小费用最大流问题最小费用最大流问题来自来自 中国最大的中国最大的资料库下载资料库下载最大运输流量问题 如下图所示，连接煤产地如下图所示，连接煤产地V1V1（发点）到销地（发点）到销地V6V6（收点）的交（收点）的交通网络，通网络，V2V2、V3V3、V5V5表示交通网络的中间节点，每条运输线表示交通网络的中间节
22、点，每条运输线（弧）上的数字表示这条线的单位时间最大通过能力（称弧的（弧）上的数字表示这条线的单位时间最大通过能力（称弧的容量），现在要制订一个运输方案，使单位时间从发点容量），现在要制订一个运输方案，使单位时间从发点V1V1到到点点V6V6煤的运输量最多？煤的运输量最多？来自来自 中国最大的中国最大的资料库下载资料库下载来自来自 中国最大的中国最大的资料库下载资料库下载可行流的网络来自来自 中国最大的中国最大的资料库下载资料库下载 2：最大流 所谓最大流就是在有容量限制的网络中流量最大的可行流。所谓最大流就是在有容量限制的网络中流量最大的可行流。最大流问题最大流问题应用很广泛应用很广泛：运输
23、系统中的车辆流、物资流；运输系统中的车辆流、物资流；通讯系统中的信息流；通讯系统中的信息流；供水系统中的水流；供水系统中的水流；供电系统中的电；供电系统中的电；金融系统中的资金流；金融系统中的资金流；供销系统中的商品流都有最大流问题的足迹。供销系统中的商品流都有最大流问题的足迹。涉猎广泛涉猎广泛 来自来自 中国最大的中国最大的资料库下载资料库下载求最大流的方法 n n标号法标号法n nLingoLingo软件求解法软件求解法还用还用LingoLingo？来自来自 中国最大的中国最大的资料库下载资料库下载标号法思路 来自来自 中国最大的中国最大的资料库下载资料库下载第一个初始可行解如何给出？第一
24、个初始可行解如何给出？最简单的办法是每条弧上的流量都最简单的办法是每条弧上的流量都为零为零优点：简单优点：简单缺点：可能会增加调整次数缺点：可能会增加调整次数来自来自 中国最大的中国最大的资料库下载资料库下载增广链及流的调整法来自来自 中国最大的中国最大的资料库下载资料库下载前向弧、后向弧以及增广链的概念 来自来自 中国最大的中国最大的资料库下载资料库下载来自来自 中国最大的中国最大的资料库下载资料库下载来自来自 中国最大的中国最大的资料库下载资料库下载来自来自 中国最大的中国最大的资料库下载资料库下载用标号法找出网络中的最大流 给出初始可行流：给出初始可行流：给出初始可行流：给出初始可行流：
25、来自来自 中国最大的中国最大的资料库下载资料库下载来自来自 中国最大的中国最大的资料库下载资料库下载来自来自 中国最大的中国最大的资料库下载资料库下载来自来自 中国最大的中国最大的资料库下载资料库下载来自来自 中国最大的中国最大的资料库下载资料库下载第一次流量调整就完成了第一次流量调整就完成了第一次流量调整就完成了第一次流量调整就完成了累累！继续讲继续讲 来自来自 中国最大的中国最大的资料库下载资料库下载 接下来，再在新的可行流接下来，再在新的可行流基础上，从发点开始基础上，从发点开始重新标重新标号找增广链并对此调整号找增广链并对此调整，直，直至找不到增广链，即找到最至找不到增广链，即找到最大
26、流为止大流为止来自来自 中国最大的中国最大的资料库下载资料库下载第二次寻找增广链寻找过程第二次寻找增广链寻找过程第二次寻找增广链寻找过程第二次寻找增广链寻找过程来自来自 中国最大的中国最大的资料库下载资料库下载第二次寻找增广链流量调整第二次寻找增广链流量调整第二次寻找增广链流量调整第二次寻找增广链流量调整来自来自 中国最大的中国最大的资料库下载资料库下载第三次寻找增广链寻找过程第三次寻找增广链寻找过程第三次寻找增广链寻找过程第三次寻找增广链寻找过程来自来自 中国最大的中国最大的资料库下载资料库下载第三次寻找增广链流量调整第三次寻找增广链流量调整第三次寻找增广链流量调整第三次寻找增广链流量调整来
27、自来自 中国最大的中国最大的资料库下载资料库下载第四次寻找增广链寻找过程第四次寻找增广链寻找过程第四次寻找增广链寻找过程第四次寻找增广链寻找过程来自来自 中国最大的中国最大的资料库下载资料库下载终于完成了终于完成了！看看LingoLingo轻松搞定轻松搞定 来自来自 中国最大的中国最大的资料库下载资料库下载Lingo的必须构造好明确的数学模型的必须构造好明确的数学模型目标函数：路段上流量最大目标函数：路段上流量最大目标函数：路段上流量最大目标函数：路段上流量最大约束条件约束条件约束条件约束条件：（可行流的满足条件）：（可行流的满足条件）：（可行流的满足条件）：（可行流的满足条件）来自来自 中国
28、最大的中国最大的资料库下载资料库下载来自来自 中国最大的中国最大的资料库下载资料库下载EASY！真能整真能整 来自来自 中国最大的中国最大的资料库下载资料库下载多个发点和收点的运输流量问题多个发点和收点的运输流量问题问题问题：在运输流量问题中，可能同时存在多个发点可以供应某在运输流量问题中，可能同时存在多个发点可以供应某种物资，也可能多个收点需要这种物资。种物资，也可能多个收点需要这种物资。来自来自 中国最大的中国最大的资料库下载资料库下载多个发点和收点的运输流量问题多个发点和收点的运输流量问题解决方式解决方式解决方式解决方式：将问题转化成为只有一个收点和一个发点的网络最大流将问题转化成为只有
29、一个收点和一个发点的网络最大流将问题转化成为只有一个收点和一个发点的网络最大流将问题转化成为只有一个收点和一个发点的网络最大流问题，运用相关方法求解问题，运用相关方法求解问题，运用相关方法求解问题，运用相关方法求解来自来自 中国最大的中国最大的资料库下载资料库下载最小费用最大流问题 问题的提出：问题的提出：在实际的物流运作过程中，不仅要考虑容在实际的物流运作过程中，不仅要考虑容量限制下的流量问题，而且还要求量限制下的流量问题，而且还要求考虑费用问考虑费用问题题。例如例如：某公司欲将产品从工厂运到仓库，虽然：某公司欲将产品从工厂运到仓库，虽然可以在许多运输线路中选择，在不同的路线上，可以在许多运
30、输线路中选择，在不同的路线上，运费是不同的，而每条路线只能负担有限的货运费是不同的，而每条路线只能负担有限的货物运输量。如何找到运费最小的货物运输方式，物运输量。如何找到运费最小的货物运输方式，并尽可能多地运输产品。并尽可能多地运输产品。这就构成了所谓的：最小费用，最大流问题。这就构成了所谓的：最小费用，最大流问题。来自来自 中国最大的中国最大的资料库下载资料库下载赋权图法对问题进行求解 求解最小费用流的算法很多，其中易于理解的求解最小费用流的算法很多，其中易于理解的一种流行算法是用一种流行算法是用最短路算法最短路算法求最小费用的增求最小费用的增广链。广链。算法思路算法思路：（1）从零流开始，
31、在始点到终点的所有可能增）从零流开始，在始点到终点的所有可能增加流量的增广链中寻找总费用最小的的链，并加流量的增广链中寻找总费用最小的的链，并对该链增加流量，得到第一次调整后的最小费对该链增加流量，得到第一次调整后的最小费用流。用流。（2）再次寻找所有的增广链，找到此时费用最）再次寻找所有的增广链，找到此时费用最小的链，增加流量。小的链，增加流量。（3）依此类推，直到网络中找不到增广链为止。）依此类推，直到网络中找不到增广链为止。此时的可行流就是最小费用流。此时的可行流就是最小费用流。来自来自 中国最大的中国最大的资料库下载资料库下载赋权图法对问题进行求解（续）如何寻找总费用最小的的链？如何寻找总费用最小的的链？构造赋权图构造赋权图它的顶点还是原网络中各弧的顶点。而弧的构它的顶点还是原网络中各弧的顶点。而弧的构造则分成下面三种情况：造则分成下面三种情况：来自来自 中国最大的中国最大的资料库下载资料库下载赋权图法对问题进行求解（续）来自来自 中国最大的中国最大的资料库下载资料库下载来自来自 中国最大的中国最大的资料库下载资料库下载