运输线路决策

选择运输线路•起止点不同的单一问题：最短路径法•多起点问题：•表上作业法•图上作业法•节约里程法•最短路径法AFEDCB50409080405030•表上作业法是单纯形法在求解运输问题的一种简化方法，寻求运费最少的调运方案。•解题思路是：•首先依据已知问题列出货物的供需平衡表及运价表；然后使用左上角法或者最小元素法或伏格尔法确定初始的调运方案；最后根据一个判定法则判断初始方案是不是最优方案，如果不是最优方案，要借助调出变量调整调配方案，再判断，直到判定为最优方案为止。•初始方案容易找•利用左上角法寻找初始方案，基本思路•从运价表元素中左上角的元素开始，集中供应，依次安排调运量，直到得到一个可行方案。•利用最小元素法寻找初始方案，基本思路•就近运输，也就是从运价表中找到最小的运价，优先满足运价最小的调运，然后在剩下的供需状态中，寻找次小的运价，满足此供需路径，再重复寻找剩下的最小的运价给与满足，直到给出初始方案为止。这种方法找到的方案，虽然每次都找的是运价最低的路径优先调运，但为了节省一个节点的费用，有时会造成其他节点费用的大幅增加，所以进行判定最优解时，会比较麻烦。•伏格尔法，一个调运地如果不能按最小运费就近供应，就考虑次小运费，这就有了一个差额，差额越大，说明不按最小运费供应，越不合理，运费增加越多，所以应优先采用最小运费调运。•例3-1某公司有3个仓库，分别是A、B、C，供应量分别是7吨、4吨、9吨，每天向4个配送中心送货，分别是甲、乙、丙、丁，需求量分别是10吨，3吨、2吨和5吨。单位运价表如图7-2所示，请确定初始可行方案。单位运价表单位：元/吨销地产地甲乙丙丁A2376B1326C3548•解：•第一步建立货物的供需平衡表及运价表如表所示。•平衡表销地产地甲乙丙丁供应量（吨）A23767B13264C35489需求量（吨）1032520•第二步，利用最小元素法寻找初始方案最小元素法确定的初始方案表销地产地甲乙丙丁供应量（吨）A617B44C2259需求量（吨）1032520•第三步判定最优方案•位势法•首先在初始方案中找到运量分配最多的行或列，确定其所在行或列的位势为零，•然后根据有调运量的格所对应的运价等于行位势加上列位势之和，依次求出各行和列的位势，•再根据下列公式求空格所对应的检验数。Aij＝Cij—（Ui+Vj）公式中的Aij表示空格所对应的检验数，Cij表示空格所对应的运价，Ui表示行位势，Vj表示列位势，i表示运价表的行数，j表示运价表的列数。最小元素法确定的初始方案表销地产地甲乙丙丁供应量（吨）A617B44C2259需求量（吨）1032520最小元素法确定的初始方案的检验数销地产地甲乙丙丁供应量（吨）A6（0）1（0）（5）（0）7B4（0）（1）（1）（1）4C（-1）2（0）2（0）5（0）9需求量（吨）1032520•最后判断，如果所有的检验数均大于等于零，则判断的方案最优。当检验数有至少一个负数时，说明该方案不是最优的方案，运输成本还有调整的空间，对负数检验数绝对值最大的所在的闭回路进行调整。•Aij=0，初始方案最优；有一个Aij0，则不是最优，需要调整负数中|Aij|值最大的所在闭合回路。•闭合回路•基本思路是从任意一个空格（没有安排调运量的格）出发，沿着行或列寻找的一条除此空格之外其余顶点均为有数字格（安排有调运量的格）的闭合回路。•找出某一空格的闭合回路；从该空格开始在闭合回路上给各个顶点进行“+”、“-”间隔标号；•对负数检验数绝对值最大的所在的闭回路进行调整:标有负号顶点中对应的最小运量作为调入运量，标有“+”的顶点所对应的运量加上调入运量，标有“—”的顶点所对应的运量减去调入运量；•形成新的调运方案，再判断和调整直到得到最优方案为止。•例7-2某公司有3个仓库，分别是A、B、C，供应量分别是7吨、4吨、9吨，每天向4个配送中心送货，分别是甲、乙、丙、丁，需求量分别是10吨，3吨、2吨和5吨。单位运价表如图所示，请确定最优方案。单位运价表单位：元/吨产地销地甲乙丙丁A2376B1326C3548销地产地甲乙丙丁供应量（吨）A（1）3（5）47B2（0）2（0）4C8（0）（0）19需求量（吨）1032520Aij≥0，得到最优解x13=5,x14=2,x21=3,x24=1,x32=6,x34=3,其余xij=0;最优值：f*=3×5+10×2+1×3+8×1+4×6+5×3=85例•某地区有3个煤矿，所产煤炭全部销往两座火力发电厂。各矿产量、电厂需求量及单位运价表如表所示，问如何安排运输可使总运费最省？运价电厂煤矿B1B2煤产量A1355000A24211000A3698000需求量1000014000•练习题:某商品产地：A、B、C、D销地：a、b、c、d、e供应量分别为：100、300、600、800，需求量分别为：250、300、350、400、500，请确定最优方案。•单位运价表abcde•A•B•C•D3020305030303010304070804020205040707080供需不平衡的物资调运问题•1、供应量大于需求量•2、需求量大于供应量处理：引入一个虚设的需求点，令其的需求量等于实际问题中供应量与需求量之差。实际中，相当于在某个供应点的仓库里将多余部分储存起来了。因此，可视其相应运价为。零处理：引入一个虚设的供应点，令其的供应量等于实际问题中需求量与供应量之差。实际中，相当于在某个需求点内设立一个仓库，将不足部分另找出路供应好，预先储存起来了。相应运价为零。例:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解：增加一个虚设的销地运输费用为0例:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解：增加一个虚设的产地运输费用为0•图上作业法•图上作业法：•利用商品产地和销地的地理分布和交通路线示意图，采用科学规划的方法，制定出商品合理的运输方案，来求得商品运输最小吨公里的方法。•它适用于交通线路为线状、圈状，而且对产销地点的数量没有严格限制的情况。•如果没有对流和迂回，就是一个运输力最省的最优方案。•图上作业法交通图画法1、交通图的符号：发点用“”表示，并将发货量记在里面，收点用“”表示，并将收货量记在里面。两点间交通线的长度记在交通线旁边。2、调运物资的流向图：物资调运的方向（流向）用“”表示，并把“”按调运方向画在交通线的右边，把调运物资的数量记在“”的右边并加上括号。•例1：调运线路呈线状。•依据“就近调空”原则，只要不出现对流情况，即是最优方案。•设产地A、D、F，产量为10、3、9，销地B、C、E、G，需求为2、5、11、4，试求合理的运输方案。•第一步，编制商品产销平衡表需供BCEG产量A10D3F9销量2511422•第二步，绘制交通线路示意图A10B-2-5C3DE-11F9G-4•第三步，按交通路线示意图进行图上作业。就近调空，首先从各端开始就近调运，在进行调整。A10B-2-5C3DE-11F9G-4•第四步，将结果填入商品调运平衡表。需供BCEG产量A22610D33F549销量2511422例•有某物资17万吨，由A1，A2，A3，A4发出，发量分别为5，2，3，7（单位：万吨），运往B1，B2，B3，B4，收量分别为8，1，3，5，收发量是平衡的，它的交通路线如图所示，问应如何调运，才能使运输吨·千米最小。52378135A1A2B1A3B2B3A4B4•例2：调运线路呈圈状。设有产地，销地,其距离及供需量见书，求最优运输线路。•它的原则可归纳为：流向划右方，对流不应当；里圈、外圈分别算，要求不过半圈长；如若超过半圈长，应甩运量最小段；反复求算最优方案。•第一步，在每个圈中，去掉一段距离最长的线路，用虚线表示，变成线状，再根据线路不含圈的情况作出初始调运方案。•第二步，检查有无迂回现象。•第三步，调整流向。•第四步将结果填入平衡表。［例］调运线路成圈状例。设有某商品发运点A、B、C、D等四处，接收点a、b、c、d位于圈状，其距离及供需量如表所示，试求最优运输路线。解：具体作业步骤如下：A．首先假定里程最长的一段没有货流通过，使圈状线路变成非圈线状，其B应甩去。B．进行合理运输，即从B运150吨到a，再从a运20吨到A，A运100吨到d。另一方面，从D运10吨到d。此外，从D运90吨到e，C地运70吨到e，同时运100吨到b地。C．根据图中虚线简示．将内外圈货流里程汇总．检查是否超过全圈长的一半一般来说，利用图上作业法寻求商品最优运输方案，可以按运输吨公里最小原则，也可以从运送时间最短或运费最省等角度来分别计算，只要商品在图上没有对流，内外圈长都不大于半圈长，该运输方案就是最优运输方案。练习3131132A1A2B1A3B2B3B475344432•在实际运输活动中，各流向上的物资是不平衡的，如进多出少或进少出多，就会出现有时车辆卸货后空载，如何调运才能使空车行驶里程最少。货名发货点收货点里程运量XXGB1669XXGH571XXIH13210XXJH759XXAD16710XXAB785XXKB749XXFD416XXEB1449XXCD5713节约法确定路径的基本原理•车辆运行计划法(VSP，VehiclesSchedulingProgram)又称里程节约法（VSP方法）。适用于实际工作中为求得较优解或最优的近似解时采用。它的基本原理是三角形的一边之长必定小于另外两边之和。如图所示。ABPL3L1L2Q1Q2122()TLLL123TLLLL121231232()()TLLLLLLLLL为实现所节约里程。可根据用户要求、道路条件等设计几种巡回方案，再计算节约里程，以其中节约里程最大者为优选的方案。VSP方法可对所有需求地点计算其节约里程，按节约量的大小顺序，优选确定路线。ABPL3L1L2Q1Q2•如图所示交通网络图。由起始点P向A、B、C、D、E等五个用户送物品。图中连线上的数字表示公路里程（km）。图中靠近各用户括号里的数字，表示对货物的需求量（t）。起始点备有2t和4t载质量的汽车，且汽车一次巡回行驶里程不能超过30km。求解满意的送货方案。E（2）D（1）695741348A（1.5）B（3）9C（0.5）10387PPABCDEP-831087A-817159B-91110C-713D-6E--ABCDEA-3116B-400C-114D-9E-序号路程节约数额1C-D112D-E93A-E64B-C45C-E46A-B37A-C18A-D1节约里程数额排序表节约里程表最短距离表E（2）D（1）695741348A（1.5）B（3）9C（0.5）10387P•从图中可以看出，依次确定的3条路径均符合约束条件。最后选择的方案是：使用2辆4t车，1辆2t车，行驶里程共52km。其中：•路径1：4t车，载货量3.5t，行驶里程30km；•路径2：2t车，载货量1.5t，行驶里程16km；•路径3：4t车，载货量3t，行驶里程6km。•在环形的线路起点，可以通过计算实载率的思路确定。总之，这一方法用计算机计算将变得非常简单。E（2）D（1）67A（1.5）B（3）C（0.5）10378路路1路路2路路3P•练习：有一配送中心（Q）要向10个用户配送，配送距离（公里）和需用量（吨）。采用最大载重量2t、4t、8t三种汽车，并限定车辆一次运行距离50km。•第一步，从配送网络图中列出配送中心至用户及用户相互间的最短距离。•第二步：从最短距离中，计算用户相互间的节约里程。•第三步：将节约里程按大小顺序排列分类。•第四步：按节约里程大小顺序，组成配送路线第一步：做出最短距离例如：C-d之间的节约里程为：ΔS=s1＋s2-s3=7＋8—5=10km第二步