定量-工具：运输优化技术(LINGO计算).pdf

该【定量-工具：运输优化技术(LINGO计算) 】是由【小屁孩】上传分享，文档一共【19】页，该文档可以免费在线阅读，需要了解更多关于【定量-工具：运输优化技术(LINGO计算) 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..本章要点运输的主体和客体运输优化技术运输线路选择与优化运输流量优化车辆装载优化运输的主体和客体运输的主体和客体运输线路的选择和优化运输线路的选择和优化运输的主体(实施运输的组织):运输的主体(实施运输的组织):(从事运输的)企业(从事运输的)企业(从事运输的)部门(从事运输的)(从事运输的)人员(从事运输的)人员运输的客体运输的客体(运输的对象):(运输的对象):,寻找由出发点到目的地的在一个交通网络中,寻找由出发点到目的地的最短路线问题最短路线问题。。V21V52V9最短路的求解方法?最短路的求解方法?62633V363当然是:当然是:DijkstraDijkstraDijkstraDijkstraDijkstraDijkstraDijkstraDijkstraDijkstra算法算法V1410V8241210V7V4这还用问?这还用问?单行线交通网络,求单行线交通网络,求V1V1V1V1V1V1到到V8V8V8V8V8V8的最短路线的最短路线1:..DijkstraDijkstraDijkstraDijkstraDijkstraDijkstraDijkstraDijkstraDijkstra算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定DijkstraDijkstraDijkstraDijkstraDijkstraDijkstraDijkstraDijkstraDijkstra算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定V21V52V9V21V52V9626362633V363V13V363410V824V14104V812210V71210V7V4V6(1)从起点V1到其他各点的距离中,最小的为点V1到点V4,从而V4V6首先确定点V1到点V4的距离为1;(2)修改点V1到点V6的路线为V1-V4-V6,距离为1+10=11DijkstraDijkstraDijkstraDijkstraDijkstraDijkstra算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定DijkstraDijkstraDijkstraDijkstraDijkstraDijkstra算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定V21V52V9V21V52V9662632633V363363V3V1410V14104V84V822121210V710V7V4V6V4V6(3)确定点V1到点V3的路线为V1-V3,距离为3(4)修改点V1到点V2的路线为V1-V3-V2,距离为3+2=5DijkstraDijkstraDijkstraDijkstraDijkstraDijkstra算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定DijkstraDijkstraDijkstraDijkstraDijkstraDijkstra算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定V21V52V9V21V52V9662632633633V363V3V1410V14104V84V822121210V710V7V4V6V4V6(5)确定V1到点V2的路线为V1-V3-V2,距离为3+2=5(6)修改点V1到点V5的路线为V1-V3-V2-V5,距离为3+2+1=62:..DijkstraDijkstraDijkstraDijkstraDijkstraDijkstraDijkstraDijkstraDijkstra算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定DijkstraDijkstraDijkstraDijkstraDijkstraDijkstraDijkstraDijkstraDijkstra算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定V2V5V9V21V52V9**********V3633V363V1410V8V1410244V82121210V710V7V4V6V4(8)修改点V1到点V6的路线为V1-V3-V2-V5-V6,距离为3+2+1+4=10V6修改点V1到点V7的路线为V1-V3-V2-V5-V7,距离为3+2+1+3=9(7)确定点V1到点V5的最短路线为V1-V3-V2-V5,距离为3+2+1=6修改点V1到点V8的路线为V1-V3-V2-V5-V8,距离为3+2+1+6=12DijkstraDijkstraDijkstraDijkstraDijkstraDijkstra算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定DijkstraDijkstraDijkstraDijkstraDijkstraDijkstra算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定V21V52V9V2V512V9662632633V3633V363V1410V84V141024V8122V71210V710V4V6V4V6(9)确定点V1到点V7的最短路线为V1-V3-V2-V5-V7,距离为3+2+1+3=9(10)点V1到其他各点的距离不变DijkstraDijkstraDijkstraDijkstraDijkstraDijkstra算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定DijkstraDijkstraDijkstraDijkstraDijkstraDijkstra算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定V21V52V9V21V52V966263263363363V3V3V1410V8V141044V822121210V710V7V4V6V4V6(11)确定点V1到点V6的最短路线为V1-V3-V2-V5-V6,距离为10(12)点V1到其他各点的距离不变3:..DijkstraDijkstraDijkstraDijkstraDijkstraDijkstraDijkstraDijkstraDijkstra算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定算法---轻松搞定V21V52V96DijkstraDijkstraDijkstraDijkstraDijkstraDijkstraDijkstraDijkstraDijkstra算法非常适合使用计算机算法非常适合使用计算机263进行求解。进行求解。363V3V14104V821210V7V4V6(13)确定点V1到V8的最短路线为V1-V3-V2-V5-V8,距离为3+2+1+3+3=,仅考虑最短距离,而而不考虑运行时间不考虑运行时间??不平衡运输问题不平衡运输问题晕晕!!!!!!!!-平衡运输问题运输问题-平衡运输问题运输问题-平衡运输问题运输问题-平衡运输问题运输问题-平衡运输问题运输问题--平衡运输问题运输问题-平衡运输问题算例:某玻璃制造厂与三个不同地点的纯碱算例:某玻璃制造厂与三个不同地点的纯碱供应商签订合同,由他们供货给三个分厂,供应商签订合同,由他们供货给三个分厂,条件是不超过合同所定的数量,但必须满足条件是不超过合同所定的数量,但必须满足生产需要。该问题如表生产需要。该问题如表3-13-13-13-13-13-1所示。问题中所所示。问题中所给费率是每个供应商到每个工厂之间最短路给费率是每个供应商到每个工厂之间最短路径的运输费率。径的运输费率。求运输方案求运输方案供应商111111供应商222222供应商333333工厂1111工厂2222工厂33334:..-平衡运输问题运输问题--平衡运输问题运输问题-平衡运输问题3-13-1运输问题-供需情况运输问题-供需情况3-13-1运输问题-运输成本运输问题-运输成本工厂1111工厂2222工厂3333供应量工厂1111工厂2222工厂3333供应商1111x11x11x11x12x12x12x13x13x**********-平衡运输问题运输问题-平衡运输问题表上作业法表上作业法非常适合大脑中有两非常适合大脑中有两求解算法--求解算法--表上作业法表上作业法列出产销平衡表及单位运列出产销平衡表及单位运列出产销平衡表及单位运块块P4-CPUP4-CPUP4-CPUP4-CPUP4-CPUP4-CPUP4-CPUP4-CPUP4-CPU的人的人::::::::::实际问题实际问题实际问题价价价价(1):(1):(1):(1):(1):(1):(1):(1):(1):展示自己非凡的计算才能展示自己非凡的计算才能((((用最小元素法用最小元素法用最小元素法))))编制初编制初编制初始方案始方案始方案(2):(2):(2):(2):(2):(2):(2):体验当年的工作艰辛体验当年的工作艰辛求校验数求校验数求校验数求校验数求校验数求校验数((((闭合回路法或位势法闭合回路法或位势法闭合回路法或位势法))))全部检验数全部检验数全部检验数>>>>====0000是否得到最优方案得到最优方案得到最优方案从绝对值最大的负检验数入手从绝对值最大的负检验数入手从绝对值最大的负检验数入手,,,,用闭合用闭合用闭合回路方法对方案进行调整回路方法对方案进行调整回路方法对方案进行调整,,,,得到新方案得到新方案得到新方案准备好笔、橡皮和纸吧准备好笔、橡皮和纸吧准备开始讲准备开始讲求解算法求解算法??求解算法--求解算法--数学软件包数学软件包LingoLingoLingoLingoLingoLingoLingoLingoLingoLingoLingoLingo麻麻烦!烦!工欲善其事,必先利其器你确认你的你确认你的CPUCPU是是P4P4的么的么??LINGOLINGO::LLinearinearININteractiveteractiveGGeneraleneralOOptimizerptimizer5:..采用采用LingoLingoLingoLingoLingoLingoLingoLingoLingo求解运输问题需要准备求解运输问题需要准备什么?什么?LingoLingoLingoLingoLingoLingoLingoLingoLingoLingoLingoLingo构造好明确的数学模型构造好明确的数学模型给我们带来了什么?给我们带来了什么?-不平衡运输问题运输问题--不平衡运输问题运输问题-不平衡运输问题供大于需供大于需不平衡运输的例子:需大于供需大于供销地1销地2销地3销地4产量表上作业法需要设立虚拟库存,将该产地1x11x12x13x146问题转化成为一个平衡运输问题求解产地2x21x22x23x244产地3x31x32x33x346Lingo软件法需要修改供需约束的不等号,再进行求解销量2235不平衡产量为6+4+6=16,销量为2+2+3+5=12。产量比销量多4。从供需平衡看,需要虚拟库存6:..-不平衡运输问题运输问题--不平衡运输问题运输问题-不平衡运输问题表上作业法的思路:转化成为一个平衡问题销地1销地2销地3销地4例如:产地121034销地1销地2销地3销地4产量产地28357产地1x11x12x13x145产地36812产地2x21x22x23x243产地3x31x32x33x344销量2235平衡产地1存储1,产地2存储1,产地3存储2,-不平衡运输问题运输问题--不平衡运输问题运输问题-不平衡运输问题Lingo作业法的思路:修改对应的供需约束条件例如:-不平衡运输问题运输问题-不平衡运输问题如果用如果用LingoLingoLingoLingoLingoLingo求解最短路线问题如何?求解最短路线问题如何?强强!!当然当然当然当然当然当然当然当然当然当然当然当然可以可以可以可以可以可以可以可以可以可以可以可以!!!!!!!!!!!!运输问题搞定(该部分仅做了解,不作为考试的考察内容)7:..如果用如果用LingoLingoLingoLingoLingoLingo求解最短路线问题如何?求解最短路线问题如何?如果用如果用LingoLingoLingoLingoLingoLingo求解最短路线问题如何?求解最短路线问题如何?V2V5为了寻找网络的最短路线距离,我们将使用下面的1动态规划递归式:6F(i)=min[D(i,j)+F(i,j)]26j363F(i)是从节点i到终点的最短距离,D(i,j)是从节V3V1410V8点i到节点j的距离。24具体说:从节点i到终点的最短距离是从节点i到临12接点的距离加上邻接点的终点的最小距离之和的最10V7小值V2D(V1,V2)F(V2)V4V6V1V4V5单行线交通网络,求单行线交通网络,求V1V1V1V1V1V1到到V8V8V8V8V8V8的最短路线的最短路线D(V1,V3)V3F(V3)用用LingoLingoLingoLingoLingoLingo求解最短路线问题的计算结果求解最短路线问题的计算结果LingoLingoLingoLingoLingoLingo求解最短路线问题求解最短路线问题很很强强!!从从V1V1V1V1V1V1到到V8V8V8V8V8V8的最短距离的最短距离F(1)F(1)F(1)F(1)F(1)F(1)==121212121212,对应的路径可以对应找出,对应的路径可以对应找出Lingo能整的东西还挺多最大运输流量问题最大运输流量问题运输流量优化运输流量优化如下图所示,连接煤产地V1(发点)到销地V6(收点)的交通网络,V2、V3、V5表示交通网络的中间节点,每条运输线(弧)上的数字表示这条线的单位时间最大通过能力(),现在要制订一个运输方案,使单位时间从发点V1到点V6煤的运输量最多?:..可行流的网络可行流的网络V2V45,010,311,53,34,03,3V1V65,28,86,617,6V3V5求最大流的方法求最大流的方法2:最大流所谓最大流就是在有容量限制的网络中流量最大的可行流。标号法标号法最大流问题应用很广泛:运输系统中的车辆流、物资流;通讯系统中的信息流;LingoLingo软件求解法软件求解法供水系统中的水流;供电系统中的电;金融系统中的资金流;供销系统中的商品流都有最大流问题的足迹。涉猎广泛还用Lingo?标号法思路标号法思路第一个初始可行解如何给出?第一个初始可行解如何给出?先求出一个可行先求出一个可行先求出一个可行流流流流ffff((((iiii))))最简单的办法是每条弧上的流量都最简单的办法是每条弧上的流量都ffff((((iiii))))是否最大流是否最大流是否最大流是计算结束计算结束计算结束为零为零否设法将设法将设法将ffff((((iiii))))改进称为另一改进称为另一改进称为另一优点:简单优点:简单个可行流个可行流个可行流个可行流个可行流个可行流ffffff((((((iiiiii++++++111111)))))),,,,,,使得使得使得使得使得使得缺点:可能会增加调整次数缺点:可能会增加调整次数ffffff((((((iiiiii++++++111111))))))>>>>>>ffffff((((((iiiiii))))))iiiiii======iiiiii++++++1111119:..增广链及流的调整法增广链及流的调整法前向弧、后向弧以及增广链的概念前向弧、后向弧以及增广链的概念(1,+)(2,+)V25,0V410,311,5(0,+)3,34,03,3V15,2V68,86,617,6V3V5用标号法找出网络中的最大流用标号法找出网络中的最大流给出初始可行流:给出初始可行流:V25,0V410,311,53,34,03,3V1V65,28,86,617,6V3V510:..(1,+)(2,+)V25,0V4(1,+)11,5V25,0V410,33,3(0,+)10,311,54,0(0,+)3,3V13,35,2V64,03,38,8V15,2V66,617,68,86,617,6V3V5V3V5(1,+)(2,+)V2V4V25,0V45,511,511,1010,33,310,83,3(0,+)(4,+)4,03,34,03,3V15,2V6V1V65,28,88,86,617,66,617,6V3V5V3V5第一次流量调整就完成了第一次流量调整就完成了接下来,再在新的可行流接下来,再在新的可行流基础上,从发点开始基础上,从发点开始重新标重新标累累!!号找增广链并对此调整号找增广链并对此调整,直,直至找不到增广链,即找到最至找不到增广链,即找到最大流为止大流为止继续讲11:..第二次寻找增广链--寻找过程第二次寻找增广链--寻找过程第二次寻找增广链--流量调整第二次寻找增广链--流量调整(1,+)(3,+)V2V4V25,5V45,511,1011,1110,810,93,33,3(0,+)4,03,3(4,+)4,13,3V15,2V6V15,3V68,86,68,817,66,617,6V3V5V3V5(2,+)第三次寻找增广链--寻找过程第三次寻找增广链--寻找过程第三次寻找增广链--流量调整第三次寻找增广链--流量调整V2(1,+)5,5V4(3,+)V2V45,510,911,1111,113,310,103,3(0,+)(5,+)4,13,3V1V64,23,25,3V1V68,85,46,617,68,86,617,7V3(2,+)V5(4,-)V3V5第四次寻找增广链--寻找过程第四次寻找增广链--寻找过程V25,5V410,1011,113,34,23,2V15,4V68,8终于完成了终于完成了!!6,617,7V3V5看Lingo轻松搞定12:..LingoLingoLingoLingoLingoLingoLingoLingoLingo的必须--构造好明确的数学模型的必须--构造好明确的数学模型目标函数:路段上流量最大目标函数:路段上流量最大约束条件约束条件:(可行流的满足条件):(可行流的满足条件)多个发点和收点的运输流量问题多个发点和收点的运输流量问题问题:在运输流量问题中,可能同时存在多个发点可以供应某种物资,也可能多个收点需要这种物资。EASYEASYV110V7EASYEASYEASYEASYEASYEASYEASYEASY!!20V410501030V250V620202015V530V3V8真能整多个发点和收点的运输流量问题多个发点和收点的运输流量问题最小费用最大流问题最小费用最大流问题解决方式:将问题转化成为只有一个收点和一个发点的网络最大流问题的提出:问题的提出:问题,运用相关方法求解在实际的物流运作过程中,不仅要考虑容在实际的物流运作过程中,不仅要考虑容V1V7量限制下的流量问题,而且还要求量限制下的流量问题,而且还要求考虑费用问考虑费用问考虑费用问考虑费用问考虑费用问考虑费用问考虑费用问考虑费用问考虑费用问2010题题题题题题题题题题。。V4例如例如例如例如例如例如:某公司欲将产品从工厂运到仓库,虽然:某公司欲将产品从工厂运到仓库,虽然2010506010可以在许多运输线路中选择,在不同的路线可以在许多运输线路中选择,在不同的路线8030上,运费是不同的,而每条路线只能负担有限上,运费是不同的,而每条路线只能负担有限V250V6Vt的货物运输量。如何找到运费最小的货物运输的货物运输量。如何找到运费最小的货物运输Vs2020方式,并尽可能多地运输产品。方式,并尽可能多地运输产品。15205015V530这就构成了所谓的:最小费用,最大流问题。这就构成了所谓的:最小费用,最大流问题。V3V813:..赋权图法对问题进行求解赋权图法对问题进行求解赋权图法对问题进行求解(续)赋权图法对问题进行求解(续)求解最小费用流的算法很多,其中易于理解的求解最小费用流的算法很多,其中易于理解的如何寻找总费用最小的的链?如何寻找总费用最小的的链?构造赋权图构造赋权图构造赋权图构造赋权图构造赋权图构造赋权图构造赋权图构造赋权图构造赋权图一种流行算法是用一种流行算法是用最短路算法最短路算法最短路算法最短路算法最短路算法最短路算法最短路算法最短路算法最短路算法求最小费用的增求最小费用的增广链。广链。算法思路算法思路算法思路算法思路算法思路算法思路算法思路算法思路算法思路::它的顶点还是原网络中各弧的顶点。而弧的构它的顶点还是原网络中各弧的顶点。而弧的构((1111111111)从零流开始,在始点到终点的所有可能增)从零流开始,在始点到终点的所有可能增造则分成下面三种情况:造则分成下面三种情况:加流量的增广链中寻找总费用最小的的链,并加流量的增广链中寻找总费用最小的的链,并对该链增加流量,得到第一次调整后的最小费对该链增加流量,得到第一次调整后的最小费用流。用流。((22222222)再次寻找所有的增广链,找到此时费用最)再次寻找所有的增广链,找到此时费用最小的链,增加流量。小的链,增加流量。((3333333333)依此类推,直到网络中找不到增广链为止。)依此类推,直到网络中找不到增广链为止。此时的可行流就是最小费用流。此时的可行流就是最小费用流。赋权图法对问题进行求解(续)赋权图法对问题进行求解(续)V1(7,7,1)VsV1Vs(2,10,4)-1-4(0,2,6)4Vs(5,5,2)(0,4,2)-262Vs(5,8,1)1V2(0,10,3)V3-13V2V3括号内数字依此为流量、容量、费用括号内数字依此为流量、容量、费用赋权图法的算例赋权图法的算例赋权图法的算例赋权图法的算例VtV1(0,5,1)VtV11(0,10,4))42,2,(0,2,6)5,5,(0,4,2)6Vs0(0(22Vs(0,8,1)(0,10,3)13V2V3V2V3大家开始手工构造一个赋权图是这样的么?咱们开始找最短路14:..赋权图法的算例赋权图法的算例第一次流量调整的结果第一次流量调整的结果VtV11VtV1(5,5,1)4(0,10,4)6)2)22,(0,2,6)25,5,(0,4,2)VsVs5(5(13(5,8,1)(0,10,3)V2V3V2V3最短路的费用为1+2+1=4对了吧,咱们继续!要开始调整流量了继续,构造第二次流量调整所需的赋权图赋权图法的算例赋权图法的算例赋权图法的算例赋权图法的算例VtVtV1-1V1-1446622-2-2VsVs1133-1-1V2V3V2V3是这样的么?咱们开始找最短路最短路的费用为1+3+2=6第二次流量调整的结果第二次流量调整的结果赋权图法的算例赋权图法的算例VtV1-1VtV1(5,5,1)4(0,10,4)62)2-2--22,2,(0,2,6)Vs5,5,(3,4,2)Vs5(5(-13(8,8,1)(3,10,3)V2V3V2V3-3是这样的么?咱们开始找最短路15:..赋权图法的算例赋权图法的算例第三次流量调整的结果第三次流量调整的结果VtVtV1V1(5,5,1)-14(1,10,4))2)26,(0,2,6)22-25(4,4,2)-,4,4VsVs(-13(8,8,1)(4,10,3)V2V3V2V3-3最短路的费用为4-2+3+2=7赋权图法的算例赋权图法的算例Vt赋权图法的算例赋权图法的算例V1-1-44不存在从Vs到Vt的通6-222路。因此不存在增广-Vs链,算法终止!-13V2V3-3咱们开始找最短路,谁先找到请举手!咱们开始找最短路,谁先找到请举手!最终的最大费用最小流最终的最大费用最小流最终的最大费用最小流最终的最大费用最小流VtV1(5,5,1)图上作业法的确很适(1,10,4)合人工运算,如果采)2)2,(0,2,6)5,5,(4,4,2)用Lingo你有好办法Vs4(4(么?(8,8,1)(4,10,3)V2V3感兴趣的同学可以回去用Lingo实验一下16:..车辆配载优化--装货问题车辆配载优化--装货问题车辆配载优化--装货问题车辆配载优化--装货问题车辆配载问题一般解决思路一般解决思路一般解决思路:可以化为多阶段问题,运用动态规划的方法求解。问题描述问题描述问题描述:如此明显的模型表达式,不使用Lingo还