物流中心规划运输优化技术(ppt 114)(3.82MB)

来自中国最大的资料库下载本章要点运输的主体和客体运输线路选择与优化运输流量优化车辆装载优化来自中国最大的资料库下载运输的主体（实施运输的组织）：•（从事运输的）企业•（从事运输的）部门•（从事运输的）人员运输的客体（运输的对象）：•为客户运输的产品运输的主体和客体来自中国最大的资料库下载运输线路的选择和优化3.1.1单一起迄点的运输线路优化问题3.1.2运输问题来自中国最大的资料库下载3.1.1单一起迄点的运输线路优化问题在一个交通网络中，寻找由出发点到目的地的最短路线问题。单行线交通网络，求V1到V8的最短路线6V1V2322V316110410236342V5V7V4V8V9来自中国最大的资料库下载这还用问？最短路的求解方法？当然是：Dijkstra算法来自算法－－－轻松搞定6V1V2322V316110410236342V5V6V7V4V8V9（1）从起点V1到其他各点的距离中，最小的为点V1到点V4，从而首先确定点V1到点V4的距离为1;来自算法－－－轻松搞定6V1V2322V316110410236342V5V6V7V4V8V9（2）修改点V1到点V6的路线为V1-V4-V6，距离为1＋10＝11来自算法－－－轻松搞定6V1V2322V316110410236342V5V6V7V4V8V9（3）确定点V1到点V3的路线为V1-V3，距离为3来自算法－－－轻松搞定6V1V2322V316110410236342V5V6V7V4V8V9（4）修改点V1到点V2的路线为V1-V3-V2，距离为3+2=5来自算法－－－轻松搞定6V1V2322V316110410236342V5V6V7V4V8V9（5）确定V1到点V2的路线为V1-V3-V2，距离为3+2=5来自算法－－－轻松搞定6V1V2322V316110410236342V5V6V7V4V8V9（6）修改点V1到点V5的路线为V1-V3-V2-V5，距离为3+2+1=6来自算法－－－轻松搞定6V1V2322V316110410236342V5V6V7V4V8V9（7）确定点V1到点V5的最短路线为V1-V3-V2-V5，距离为3+2+1=6来自算法－－－轻松搞定6V1V2322V316110410236342V5V6V7V4V8V9（8）修改点V1到点V6的路线为V1-V3-V2-V5-V6，距离为3+2+1+4=10修改点V1到点V7的路线为V1-V3-V2-V5-V7，距离为3+2+1+3=9修改点V1到点V8的路线为V1-V3-V2-V5-V8，距离为3+2+1+6=12来自算法－－－轻松搞定6V1V2322V316110410236342V5V6V7V4V8V9（9）确定点V1到点V7的最短路线为V1-V3-V2-V5-V7，距离为3+2+1+3=9来自算法－－－轻松搞定6V1V2322V316110410236342V5V6V7V4V8V9（10）点V1到其他各点的距离不变来自算法－－－轻松搞定6V1V2322V316110410236342V5V6V7V4V8V9（11）确定点V1到点V6的最短路线为V1-V3-V2-V5-V6，距离为10来自算法－－－轻松搞定6V1V2322V316110410236342V5V6V7V4V8V9（12）点V1到其他各点的距离不变来自算法－－－轻松搞定6V1V2322V316110410236342V5V6V7V4V8V9（13）确定点V1到V8的最短路线为V1-V3-V2-V5-V8,距离为3+2+1+3+3=12来自算法非常适合使用计算机进行求解。地球人都知道来自中国最大的资料库下载仅考虑最短距离，而不考虑运行时间？晕!来自运输问题平衡运输问题不平衡运输问题来自运输问题－平衡运输问题来自中国最大的资料库下载算例：某玻璃制造厂与三个不同地点的纯碱供应商签订合同，由他们供货给三个分厂，条件是不超过合同所定的数量，但必须满足生产需要。该问题如表3-1所示。问题中所给费率是每个供应商到每个工厂之间最短路径的运输费率。求运输方案供应商1供应商2供应商3工厂1工厂2工厂33.1.2运输问题－平衡运输问题来自运输问题－供需情况供销平衡3.1.2运输问题－平衡运输问题来自运输问题－运输成本3.1.2运输问题－平衡运输问题来自中国最大的资料库下载求解算法－－表上作业法实际问题列出产销平衡表及单位运价（用最小元素法）编制初始方案求校验数（闭合回路法或位势法）得到最优方案全部检验数=0从绝对值最大的负检验数入手，用闭合回路方法对方案进行调整，得到新方案否是3.1.2运输问题－平衡运输问题来自的人:(1):展示自己非凡的计算才能(2):体验当年的工作艰辛准备好笔、橡皮和纸吧来自中国最大的资料库下载准备开始讲求解算法？麻烦！你确认你的CPU是P4的么？来自中国最大的资料库下载求解算法－－数学软件包工欲善其事，必先利其器LingoLINGO:LinearINteractiveGeneralOptimizer来自给我们带来了什么？大家下课后认真思考来自求解运输问题需要准备什么？构造好明确的数学模型将数学模型按照指定的语法规范输入软件来自运输问题－不平衡运输问题供大于需需大于供表上作业法需要设立虚拟库存，将该问题转化成为一个平衡运输问题求解Lingo软件法需要修改供需约束的不等号，再进行求解来自运输问题－不平衡运输问题销地1销地2销地3销地4产量产地1x11x12x13x146产地2x21x22x23x244产地3x31x32x33x346销量2235不平衡产量为6+4+6=16，销量为2+2+3+5=12。产量比销量多4。从供需平衡看，需要虚拟库存不平衡运输的例子：来自运输问题－不平衡运输问题销地1销地2销地3销地4产地121034产地28357产地36812来自运输问题－不平衡运输问题表上作业法的思路：转化成为一个平衡问题例如：销地1销地2销地3销地4产量产地1x11x12x13x145产地2x21x22x23x243产地3x31x32x33x344销量2235平衡产地1存储1，产地2存储1，产地3存储2，此时平衡来自运输问题－不平衡运输问题Lingo作业法的思路：修改对应的供需约束条件例如：来自运输问题－不平衡运输问题来自中国最大的资料库下载强！运输问题搞定3.1.2运输问题－不平衡运输问题来自求解最短路线问题如何？（该部分仅做了解，不作为考试的考察内容）当然可以！来自求解最短路线问题如何？单行线交通网络，求V1到V8的最短路线6V1V2322V3161104106342V5V6V7V4V8来自求解最短路线问题如何？为了寻找网络的最短路线距离，我们将使用下面的动态规划递归式：)],(),([min)(jiFjiDiFjF(i)是从节点i到终点的最短距离，D(i,j)是从节点i到节点j的距离。具体说：从节点i到终点的最短距离是从节点i到临接点的距离加上邻接点的终点的最小距离之和的最小值V1V2V3V4V5F(V2)F(V3)D(V1,V2)D(V1,V3)来自(1)＝12，对应的路径可以对应找出来自求解最短路线问题很强！Lingo能整的东西还挺多来自中国最大的资料库下载运输流量优化3.2.1最大运输流量问题3.2.2最小费用最大流问题来自中国最大的资料库下载最大运输流量问题如下图所示，连接煤产地V1（发点）到销地V6（收点）的交通网络，V2、V3、V5表示交通网络的中间节点，每条运输线（弧）上的数字表示这条线的单位时间最大通过能力（称弧的容量），现在要制订一个运输方案，使单位时间从发点V1到点V6煤的运输量最多？V1V2V3V4V5V61048535361711来自来自：最大流所谓最大流就是在有容量限制的网络中流量最大的可行流。最大流问题应用很广泛：运输系统中的车辆流、物资流；通讯系统中的信息流；供水系统中的水流；供电系统中的电；金融系统中的资金流；供销系统中的商品流都有最大流问题的足迹。涉猎广泛来自中国最大的资料库下载求最大流的方法标号法Lingo软件求解法还用Lingo？来自(i)设法将f(i)改进称为另一个可行流f(i+1),使得f(i+1)f(i)计算结束否是f(i)是否最大流i=i+1来自中国最大的资料库下载第一个初始可行解如何给出？最简单的办法是每条弧