搜索
管理运筹学11、物流系统规划之运输线路选择（1）问题提出运输问题确定了物资调运的方向、具体实施涉及运输路线选择。运输路线的确定会直接影响到运输效果的好坏，关系着物资能否及时运到指定地点。当运输费用是以吨-千米来计算时，运输路线的长短就直接关系着运输费用的多少。因此运输路线的选择也是物资调运规划的一个重要内容。在物资调运中，把某项物资从各发点调到各收点，调运方案很多，如何找出使用运输力量最小的方案？管理运筹学2（2）问题描述某项物资从m个产地或仓库(统称为发点)，调运到n个需要地(称为收点)，在指定调运方案时，要先画一个示意的交通图，表明收发点的大致位置、收发量、交通路线长度(不必与实际长度成比例)。在交通图上，发点用“○”表示，并将发货量记在里面，收点用“口’’表示，并将收货量记在里面。两点间交通线的长度记在交通线旁边。然后作调运物资的流向图。物资调运的方向(流向)用→表示，并把→按调运方向画在交通线的右边，把调运物资的数量记在→的右边，并加上括号，以表示和交通线长度区别，这样就构成下图的物资调运流量图。管理运筹学3管理运筹学43）相关概念a)对流即同一物资在同一线路上的往返运输，如图1。将某物资l0吨，从A1运到B2，而又有同样的物资10吨，在同一期间从A2运到B1，于是间就出现了对流现象。管理运筹学5图1出现对流的调运流量图管理运筹学6如果把调运流量图改成如图2所示，即将A1的l0吨运到B1,而将A2的10吨运到B2就消灭了对流，可以节省运输力量2×10×40=800吨·千米。图2消灭了对流的调运流量图管理运筹学7b)迂回在交通图成圈的时候，由于表示调运方向的箭头，要按调运方向，画在交通线的右边，因此，流向图中，有些流向就在圈外，称为外圈流向。如图3；有些流向就在圈内，称为内圈流向，如图4。如果流向图中，内圈流向的总长(简称内流长)或外圈流向的总长(简称外流长)超过整个圈长的一半，就称为迂回运输。管理运筹学8图3迂回运输图图4无迂回运输图管理运筹学9如果改成图4，就消灭了迂回，可以节省运输力量（5×6）-（5×4）=l0吨·千米。管理运筹学10迂回流向图示例图5迂回运输内流长7大于全圈长13的一半，是迂回运输。管理运筹学11调整：如果调整内圈长(在内圈各流量中减去内圈的最小流量10)。在外圈各流量中增加内圈的最小流量10，同时在没有流量的线段上新添上外圈流量10(即内圈的最小流量)，便得出新的流向圈，如图6。图6无迂回运输管理运筹学124）运输线路选择图上作业法物资调运问题的图上作业法，就是为了消灭运输中对流和迂回，节省运输力量。一般步骤：先找出一个没有对流的方案，再检查有没有迂回？如果没有迂回，这方案已是最优方案。如果有迂回，则调整这一方案，直至消灭迂回为止。管理运筹学13在物资调运中，运输路线可分为两种情况：一是交通路线不成圈，一是交通路线成圈。下面分别介绍这两种情况物资调运的方法。a)交通路线不成圈例3物资17万吨，由A1，A2，A3，A4发出，发量分别为5，2，3，7(单位：万吨)，运往B1，B2，B3，B4，收量分别为8，1，3，5(单位：万吨)，收发量是平衡的，它的交通路线如图7所示，问应如何调运，才使运输吨·千米最小。管理运筹学14图7交通路线图管理运筹学15解：作一个没有对流的流向图。作法：由各端点开始，由外向里，逐步进行各收发点之间的收发平衡。把A1的5万吨给A2，A2成为有发量7万吨的发点。由A3调1万吨给B2，A3剩2万吨，由A4调5万吨给B4，A4剩2万吨。将A2的7万吨全部调给B1，将A3剩余的2万吨，先调1万吨给B1，余下的1万吨调给B1，剩余的2万吨全部调给B3，调运流向图如图8。管理运筹学16图8调运流向图根据上面流向图的作法，所得的没有对流现象的流向图是惟一的，再根据对流现象是不合理的运输，所以这惟一没有对流的流向图就是惟一的最优方案的流向图。有时同一流向图，可以编制各种不同的调运方案。例中，B3需要的3万吨，除A4供给的2万吨外，其余1万吨可以由给A3，也可以由给A2，也可以由A2，A3，共同给。这些方案所用的运输力是一样的，调运时可以结合其他条件，选择其中一个。管理运筹学17b)交通路线成圈例：有某物资7万吨，由发点A1，A2，A3发出，发量分别为3，3，1(万吨)，运往收点B1，B2，B3，B4，收量分别为2，3，1，1(万吨)，收发量平衡，交通图如图9所示，问应如何调运，才使吨·千米最小。管理运筹学18图9交通路线图管理运筹学19解：1)作一个没有对流的流向图，用“去线破圈”的方法：去一线破一圈，有几个圈去掉几条线，把有圈的交通图，化为不成圈的交通图。一般是先去掉长度最长的交通线，比如，去掉A1-B4(7千米)，破A1-B1-B2-A3-B4圈，再去掉线A3-B3(4千米)，破圈B2-A2-B3-A2。这样，原来有圈的交通图，变成了不成圈的交通图．如图9所示。然后先从各个端点开始，在图9上作一个没有对流的流向图。管理运筹学20图9调运流量图破圈管理运筹学212)检查有无迂回。方法是对流向图中的各圈进行检查，看看有无迂回。如果没有迂回，这个初始方案就是最优方案，如果其中某一圈有迂回，这个方案就不是最优方案，需要改进。管理运筹学22在图9中，圈A1-B1-B2-A3-B4的总长为23千米，外流长为5+4+3=12千米，大于圈长的一半，因而需要调整。再看圈B2-A2-B3-A3，其总长为13千米，圈中内流长为3千米，外流长为2千米，都小于圈长的一半，因此，此圈不必调整。管理运筹学233）调整对圈的调整方法是：在外圈的各流量中，减去外圈的最小流量1万吨；然后在内圈的各流量中加上1万吨；另外，再在无流量的线段上，新添上内圈流量1万吨，这样得出新的流量图，如图10所示。管理运筹学24图10调整后的流量图管理运筹学254）分析新的流量图中，在A1-B1-B2-A3-B4圈内，内流长为：4+7=11千米，外流长为：5千米，都不超过全圈长(23千米)的一半；在B2-A2-B3-A3圈内，内流长为3千米，外流长为4+2=6千米，也都没有超过全圈长(13千米)的一半，因此，这个流向图没有迂回现象，是本问题的最优调运方案。5）总运输力为：1×7+2×5+1×4+2×3+2×1=29吨·千米。管理运筹学26物流系统规划之最短路（1）最短路线描述例：某家运输公司签定了一项运输合同，要把A市的一批货物运送到B市。该公司根据这两个城市之间可选择的行车路线的地图，绘制了图11的公路网络。图中，圆圈也称结点，代表起点、目的地和与行车路线相交的其他城市。箭矢或称为分支，代表两个结点之间的公路，每一条公路上都标明运输里程。管理运筹学27图11公路网络管理运筹学28可以看出，从A市出发到达B市，可以有很多条路线可供选择。但是如何选择运输路线，才能使总路程的长度最短呢?该公司的目的就是要找出从A市到B市的最短路线。这就是运输规划中的最短路问题。管理运筹学29解：最短路线的计算方法为：1)从终点开始逐步逆向推算，与终点10联接的有两个结点，即9和8，B市先从9开始计算。9到10只有一条路线，因此没有选择的余地，9-10就是最短的路线，它的里程为100，记为(9-10)100。同样8-10也只有一条路线，最短路线为8-10，里程为150，也按相同方式记为(8-10)150。管理运筹学302)再看结点6，与6联接的只有一个结点9，因此最短路线为6-9，6至9的里程为200。而9至终点10的最短里程为100，因此6至终点的最短里程为200+100=300。记入方式同上：(6-9-10)300。3)再看结点5，与5联接的结点有9、8两个，5至9再至终点的最短里程为400+100=500，5至8再至终点的最短里程为250+155=400。400500，所以5至终点的最短里程为400，记为(5-8-10)400。结点7至终点的最短里程为125+150=275，记入方式同上：(7-8-10)275。管理运筹学314)再看结点4，与4联接的结点有5、6、7三个。4至6再到终点的最短里程为200+300=500，4至5再到终点的最短里程为175+400=575，4至7再到终点的最短里程为275+275=550。三个里程中以500为最小，所以结点4至10的最短里程记为(4-6-10)500。5）用同样的方法，算出结点2到终点的最短里程为600。结点3到终点的最短里程也为600。记入的方式同上：(2-6-9-10)600；(3-5-8-10)600管理运筹学326)最后看结点1。与结点1联接的路线有3条：1至2再到终点的最短里程100+600=700，路径为1-2-6-9-10；1至4再到终点的最短里程150+500=650，路径为l-4-6-9-10。1至3再到终点的最短里程175+600=775，路径为1-3-5-8-10。三个里程中以650为最小，这就是从A市到B市的最短里程，而对应的最短路线为1-4-6-9-10。管理运筹学33•作业：P144,第6题管理运筹学34物流系统规划之最大流1、问题提出当我们要把货物运输到指定的地点时，有时会希望找到一条交通量最大的路线，以使货物能在最短时间内到达。这就要在有一个起点和个终点的网络中，找出在一定时期内，能在起点进入，并通过这个网络，在终点输出的最大流量问题。管理运筹学352、例题美国北卡罗来纳州杜哈姆市周围从北到南的交通，平时是利用85号公路通行的。后来，有两个星期因为85号公路要进行路面维修，车辆不能行驶，因而北卡罗来纳州公路委员会的工程技术人员需要查明，穿过杜哈姆市区的几条路线，是不是有把握让每小时6000辆汽车穿过，这些汽车在正常情况下，是利用85号公路南驶的。问题：要求出从①点到⑥点的公路网络所能通过的最大流量。管理运筹学36图12标出了穿过该市从北往南的几条路线。结点旁边的数字指明以每小时千辆汽车为单位的该行车道的流量能力。如1-2支线(行车道)上的6字表明这条行车道通往结点2的流量能力为每小时6千辆。3-5支线上的5字表示每小时可以有5千辆汽车从3向5开去。管理运筹学37图12交通路线图管理运筹学38解：(1)任意选择一条从起点①到终点⑥的路线，例如，我们选择路线l-2-5-6。首先找出这条路线上流量能力最小的支线，即5-6支线，其流量能力为2。这就表明，沿1-2-5-6支线南驶的汽车，其每小时的最大流量只能是2干辆，因为5-6支线限制了全线的车流量。管理运筹学39（2）其次把这条路线上每条支线的流量能力减去2，差数则表示该支线剩余的流量能力，将其写在原来的流量能力的旁边，并把原来的流量划掉。把减数2写在每条支线的终点，在减数2的右下角注上(1)，如2(1)，表示第一条路线的流量能力为2千辆。标注方式如图13所示。管理运筹学40图13最大流量计算图管理运筹学41(3)另选一条从起点到终点的路线，如1-4-6，以该路线上最小的流量能力3为减数，来减各条支线上的流量能力，其差数、减数的记入方法同上。在差数3的右下角注上(2)，表示第二条路线的流量能力为3千辆。管理运筹学42(4)再选一条从起点到终点的路线，如1-3-4-6，以该路线上最小的流量能力3为减数来减各条支线上的流量能力，其差数、减数的记入方式同上。但4-6支线的流量能力已经只剩下4，再减去3，差数为1，接续写在4的旁边，表示4-6支线的流量能力只剩余1千辆，同时划掉4，再记入本路线的差数3(3)，表示第三条路线的流量能力为3千辆。管理运筹学43（5）结论：已经求得了这个网络的最大流量，即第一条路线上的2千辆，第二条路线上的3千辆，第三条路线上的3千辆，共为8千辆。计算结果表明，穿过杜哈姆市区的几条路线，要让每小时6千辆汽车通过，是绰绰有余的。管理运筹学44（6）分析：从起点到终点，已找不到这样一条路线，在这条路线上，所有各条支线的流量能力全为正数。如1-2-3-5-6路线，其中1-2、2-3、3-5支线，都还有流量能力4千辆、7千辆、5千辆，但5-6支线已经没有剩余的流量能力，因而成为整线路的瓶颈，限制了全线