现代物流与物流中心规划 （ppt 66）.pptx

现代物流与物流中心规划 第三章第三章 运输优化技术运输优化技术 Modern Logistics and Logistics centers PlanningModern Logistics and Logistics centers Planning 本章要点n n运输的主体和客体运输的主体和客体n n运输线路选择与优化运输线路选择与优化n n运输流量优化运输流量优化n n车辆装载优化车辆装载优化n n运输的主体（实施运输的组织）：（从事运输的）企业（从事运输的）部门（从事运输的）人员n n运输的客体（运输的对象）：为客户运输的产品运输的主体和客体运输线路的选择和优化 n n3.1.1 3.1.1 单一起迄点的运输线路优化问题单一起迄点的运输线路优化问题n n3.1.2 3.1.2 运输问题运输问题n n3.1.1 3.1.1 单一起迄点的运输线路优化问题单一起迄点的运输线路优化问题单一起迄点的运输线路优化问题单一起迄点的运输线路优化问题在一个交通网络中，寻找由出发点到目的地的在一个交通网络中，寻找由出发点到目的地的在一个交通网络中，寻找由出发点到目的地的在一个交通网络中，寻找由出发点到目的地的最短路线问题最短路线问题最短路线问题最短路线问题。单行线交通网络，求单行线交通网络，求单行线交通网络，求单行线交通网络，求V1V1到到到到V8V8的最短路线的最短路线的最短路线的最短路线DijkstraDijkstraDijkstraDijkstra算法轻松搞定算法轻松搞定算法轻松搞定算法轻松搞定DijkstraDijkstraDijkstraDijkstra算法轻松搞定算法轻松搞定算法轻松搞定算法轻松搞定DijkstraDijkstraDijkstraDijkstra算法轻松搞定算法轻松搞定算法轻松搞定算法轻松搞定DijkstraDijkstraDijkstraDijkstra算法轻松搞定算法轻松搞定算法轻松搞定算法轻松搞定DijkstraDijkstraDijkstraDijkstra算法轻松搞定算法轻松搞定算法轻松搞定算法轻松搞定DijkstraDijkstraDijkstraDijkstra算法轻松搞定算法轻松搞定算法轻松搞定算法轻松搞定DijkstraDijkstraDijkstraDijkstra算法轻松搞定算法轻松搞定算法轻松搞定算法轻松搞定DijkstraDijkstraDijkstraDijkstra算法轻松搞定算法轻松搞定算法轻松搞定算法轻松搞定DijkstraDijkstraDijkstraDijkstra算法轻松搞定算法轻松搞定算法轻松搞定算法轻松搞定DijkstraDijkstraDijkstraDijkstra算法轻松搞定算法轻松搞定算法轻松搞定算法轻松搞定DijkstraDijkstraDijkstraDijkstra算法轻松搞定算法轻松搞定算法轻松搞定算法轻松搞定DijkstraDijkstraDijkstraDijkstra算法轻松搞定算法轻松搞定算法轻松搞定算法轻松搞定DijkstraDijkstraDijkstraDijkstra算法轻松搞定算法轻松搞定算法轻松搞定算法轻松搞定Dijkstra算法非常适合使用计算算法非常适合使用计算机进行求解。机进行求解。地球人都知道地球人都知道地球人都知道地球人都知道 仅考虑最短距离，仅考虑最短距离，而而不考虑运行时间不考虑运行时间？晕晕晕晕!3.1.2 运输问题n n平衡运输问题平衡运输问题n n不平衡运输问题不平衡运输问题3.1.2 3.1.2 运输问题平衡运输问题运输问题平衡运输问题运输问题平衡运输问题运输问题平衡运输问题算例：某玻璃制造厂与三个不同地点的纯碱算例：某玻璃制造厂与三个不同地点的纯碱供应商签订合同，由他们供货给三个分厂，供应商签订合同，由他们供货给三个分厂，条件是不超过合同所定的数量，但必须满足条件是不超过合同所定的数量，但必须满足生产需要。该问题如表生产需要。该问题如表3-1所示。问题中所所示。问题中所给费率是每个供应商到每个工厂之间最短路给费率是每个供应商到每个工厂之间最短路径的运输费率。径的运输费率。求运输方案求运输方案3.1.2 3.1.2 运输问题平衡运输问题运输问题平衡运输问题运输问题平衡运输问题运输问题平衡运输问题工厂工厂工厂工厂1 1工厂工厂工厂工厂2 2工厂工厂工厂工厂3 3供应量供应量供应量供应量供应商供应商供应商供应商1 1x11x11x12x12x13x13400400供应商供应商供应商供应商2 2x21x21x22x22x23x23700700供应商供应商供应商供应商3 3x31x31x32x32x33x33500500需求量需求量需求量需求量6006005005005005003-13-1运输问题供需情况运输问题供需情况供销平衡供销平衡3.1.2 3.1.2 运输问题平衡运输问题运输问题平衡运输问题运输问题平衡运输问题运输问题平衡运输问题工厂工厂工厂工厂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 运输问题平衡运输问题运输问题平衡运输问题运输问题平衡运输问题运输问题平衡运输问题求解算法求解算法数学软件包数学软件包工欲善其事，必先利其器工欲善其事，必先利其器 LingoLINGOLINGO:L Linearinear IN INteractive teractive GGeneral eneral OOptimizerptimizerLingo给我们带来了什么？给我们带来了什么？大家下课后认真思考大家下课后认真思考 采用采用Lingo求解运输问题需要准求解运输问题需要准备什么？备什么？n n构造好明确的数学模型构造好明确的数学模型n n将数学模型按照指定的语法规范输入软件将数学模型按照指定的语法规范输入软件供销平衡情况供销平衡情况 就是这么简单就是这么简单 3.1.2 3.1.2 运输问题不平衡运输问题运输问题不平衡运输问题运输问题不平衡运输问题运输问题不平衡运输问题n n供大于需供大于需n n需大于供需大于供 表上作业法需要设立虚拟库存，将该问题转化成为一个平衡运输问题求解 Lingo软件法需要修改供需约束的不等号，再进行求解3.1.2 3.1.2 运输问题不平衡运输问题运输问题不平衡运输问题运输问题不平衡运输问题运输问题不平衡运输问题销地销地1 1销地销地2 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 运输问题不平衡运输问题运输问题不平衡运输问题运输问题不平衡运输问题运输问题不平衡运输问题销地销地1 1销地销地2 2销地销地3 3销地销地4 4产地产地1 12 210103 34 4产地产地2 28 83 35 57 7产地产地3 36 68 81 12 23.1.2 3.1.2 运输问题不平衡运输问题运输问题不平衡运输问题运输问题不平衡运输问题运输问题不平衡运输问题 表上作业法的思路：表上作业法的思路：转化成为一个平衡问题转化成为一个平衡问题例如：例如：销地销地1 1销地销地2 2销地销地3 3销地销地4 4产量产量产地产地1 1x11x11x12x12x13x13x14x145 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作业法的思路：作业法的思路：修改对应的供需约束条件修改对应的供需约束条件例如：例如：3.1.2 3.1.2 运输问题不平衡运输问题运输问题不平衡运输问题运输问题不平衡运输问题运输问题不平衡运输问题如果用如果用如果用如果用LingoLingo求解最短路线问题如何？求解最短路线问题如何？求解最短路线问题如何？求解最短路线问题如何？单行线交通网络，求单行线交通网络，求单行线交通网络，求单行线交通网络，求V1V1到到到到V8V8的最短路线的最短路线的最短路线的最短路线如果用如果用如果用如果用LingoLingo求解最短路线问题如何？求解最短路线问题如何？求解最短路线问题如何？求解最短路线问题如何？为了寻找网络的最短路线距离，我们将使用下面的为了寻找网络的最短路线距离，我们将使用下面的动态规划递归式：动态规划递归式：F(i)F(i)F(i)F(i)是从节点是从节点是从节点是从节点i i i i到终点的最短距离，到终点的最短距离，到终点的最短距离，到终点的最短距离，D(i,j)D(i,j)D(i,j)D(i,j)是从节是从节是从节是从节点点点点i i i i到节点到节点到节点到节点j j j j的距离。的距离。的距离。的距离。具体说：从节点具体说：从节点具体说：从节点具体说：从节点i i i i到终点的最短距离是从节点到终点的最短距离是从节点到终点的最短距离是从节点到终点的最短距离是从节点i i i i到临到临到临到临接点的距离加上邻接点的终点的最小距离之和的最接点的距离加上邻接点的终点的最小距离之和的最接点的距离加上邻接点的终点的最小距离之和的最接点的距离加上邻接点的终点的最小距离之和的最小值小值小值小值用用用用LingoLingo求解最短路线问题的计算结果求解最短路线问题的计算结果求解最短路线问题的计算结果求解最短路线问题的计算结果从从从从V1V1到到到到V8V8的最短距离的最短距离的最短距离的最短距离F(1)F(1)1212，对应的路径可以对应找出，对应的路径可以对应找出，对应的路径可以对应找出，对应的路径可以对应找出运输流量优化 n n3.2.1 3.2.1 最大运输流量问题最大运输流量问题n n3.2.2 3.2.2 最小费用最大流问题最小费用最大流问题最大运输流量问题 如下图所示，连接煤产地如下图所示，连接煤产地V1V1（发点）到销地（发点）到销地V6V6（收点）的交（收点）的交通网络，通网络，V2V2、V3V3、V5V5表示交通网络的中间节点，每条运输线表示交通网络的中间节点，每条运输线（弧）上的数字表示这条线的单位时间最大通过能力（称弧的（弧）上的数字表示这条线的单位时间最大通过能力（称弧的容量），现在要制订一个运输方案，使单位时间从发点容量），现在要制订一个运输方案，使单位时间从发点V1V1到到点点V6V6煤的运输量最多？煤的运输量最多？可行流的网络 2：最大流 所谓最大流就是在有容量限制的网络中流量最大的可行流。所谓最大流就是在有容量限制的网络中流量最大的可行流。最大流问题最大流问题应用很广泛应用很广泛：运输系统中的车辆流、物资流；运输系统中的车辆流、物资流；通讯系统中的信息流；通讯系统中的信息流；供水系统中的水流；供水系统中的水流；供电系统中的电；供电系统中的电；金融系统中的资金流；金融系统中的资金流；供销系统中的商品流都有最大流问题的足迹。供销系统中的商品流都有最大流问题的足迹。涉猎广泛涉猎广泛 求最大流的方法 n n标号法标号法n nLingoLingo软件求解法软件求解法还用还用LingoLingo？标号法思路 第一个初始可行解如何给出？第一个初始可行解如何给出？最简单的办法是每条弧上的流量都最简单的办法是每条弧上的流量都为零为零优点：简单优点：简单缺点：可能会增加调整次数缺点：可能会增加调整次数增广链及流的调整法前向弧、后向弧以及增广链的概念 用标号法找出网络中的最大流 给出初始可行流：给出初始可行流：给出初始可行流：给出初始可行流：接下来，再在新的可行流接下来，再在新的可行流基础上，从发点开始基础上，从发点开始重新标重新标号找增广链并对此调整号找增广链并对此调整，直，直至找不到增广链，即找到最至找不到增广链，即找到最大流为止大流为止第二次寻找增广链寻找过程第二次寻找增广链寻找过程第二次寻找增广链寻找过程第二次寻找增广链寻找过程第二次寻找增广链流量调整第二次寻找增广链流量调整第二次寻找增广链流量调整第二次寻找增广链流量调整第三次寻找增广链寻找过程第三次寻找增广链寻找过程第三次寻找增广链寻找过程第三次寻找增广链寻找过程第三次寻找增广链流量调整第三次寻找增广链流量调整第三次寻找增广链流量调整第三次寻找增广链流量调整第四次寻找增广链寻找过程第四次寻找增广链寻找过程第四次寻找增广链寻找过程第四次寻找增广链寻找过程Lingo的必须构造好明确的数学模型的必须构造好明确的数学模型目标函数：路段上流量最大目标函数：路段上流量最大目标函数：路段上流量最大目标函数：路段上流量最大约束条件约束条件约束条件约束条件：（可行流的满足条件）：（可行流的满足条件）：（可行流的满足条件）：（可行流的满足条件）