模块三 物资调运问题的图上作业法.pptVIP

模块三 物资调运问题的图上作业法;问题引入：求下列问题的最优调运方案;3.1 物资调运问题的图上作业法 ;1、交通路线图： （也称为网络图）是反映产地与销地的交通路线及其距离的图。;A;▼一是有发点（产地）和收点（销地） ； ▼二是有发点的发量及收点的收量； ▼产地（发点）用“○”表示，产量写在圆圈内 ▼销地（收点）用“□”表示，销量写在方框内 ▼三是有连接收点、发点的交通线路以及与之相对应的线路长度或运价； ▼距离或运价写在弧的旁边;交通路线图的绘制： 第一步是先标出产地（发点）和销地（收点），产地“○” 内填上该产地的产量（发量)；销地“□” 内填上该销地的销量(收量)。 第二步画出连接这些点的交通路线，在每段路线旁注明该路线的长度或运价。;●2 、物资调运的流向图（流向图）;§物资调运流向图的一些规定：;图3-1 图3-2 ;⑩;3.2 利用流向图求解物资调运问题;3.2 利用流向图求解物资调运问题;;◆流向图中对流现象： 所谓对流就是在一段线路上有同一种物资出现相对运输现象（往返运输）（同一段线路上，两个方向都有流向），如下图所示：;;【例3.1】求不成圈问题的最优调运方案;案例分析;第二步：在交通图上找调运方案;第三步：检验是否为最优;第四步：得到最优调运方案1;第三步：得到最优调运方案2;说明： 交通路线不成圈问题的图上作业法求得的最优调运方案不一定是唯一的！不同的最佳调运方案的总成本一定都是相同的。 因为上例中没考虑各地之间运输距离。;练一练;答案;▼一是有发点（产地）和收点（销地） ； ▼二是有发点的发量及收点的收量； ▼产地（发点）用“○”表示，产量写在圆圈内 ▼销地（收点）用“□”表示，销量写在方框内 ▼三是有连接收点、发点的交通线路以及与之相对应的线路长度或运价； ▼距离或运价写在弧的旁边;§物资调运流向图的一些规定：;根据交通图成圈与否，图上作业法分为： 3.2.1 不成圈问题的图上作业法求物资调运问题 3.2.2 成圈问题的图上作业法求物资调运问题;;试求下列交通图的最优调运方案;分析;思考：对下面交通图求最优调运方案？;;流向图中不合理的现象：迂回;;3.3.1 成圈问题图上作业法的求解步骤： 第一步：丢边破圈。 方法：“丢边破圈”。即从流向图中任取一圈，丢掉一条边，破去一个圈。再从剩下的图中取圈，丢边破圈，直到图中无圈为止。 注意1：丢边时，是丢掉圈中长度最大的边。 第二步：在无圈的交通图上作流向图。 原则：按“供需归邻站”，先端点后中间点做流向图。当某条边无流向时，必须填上运输量为零的虚流向。 第三步：补上丢掉的边，对逐个圈检查有无迂回。 第四步：若有迂回，调整有迂回的圈使之最优。 ;例3.2 设某集团公司有3个配送中心，要为该公司所属的5个超市补充库存，各配送中心和超市的位置如下图，图中的数字表示相应点之间的里程，各配送中心供应量和各超市的需求量也在图中标出. 试确定最佳调运方案.;解： 第一步：变有圈为无圈。 方法：“丢边破圈”。在流向图中任取一圈，丢掉一条边，破去一个圈。再从剩下的图中取圈，丢边破圈，直到图中无圈。 注意：丢边时，往往是丢掉圈中长度最大的边。如图所示;第二步：在无圈的交通图上作流向图。 原则：按“供需归邻站”，先端点后中间点，要求每个边都有流向。当某条边无流向时，必须填上运输量为零的虚流向。 ;第三步：补上丢掉的边，在无流向的边上填上运输量为零的虚流向，对逐个圈检查有无迂回。 圈B5B4B3A2的圈长=4+4+5+8=21, 内圈长= 4+4+5=1321/2，有迂回！ 所以流向图不是最优流向图。需要调整。;（1）外调整法：;第四步：对方案进行调整。 方法：由于圈B5B4B3A2的内圈长=4+4+5=1321/2。故采用“外调整法”：找出有迂回圈的内圈流量最小值（2），每个内圈流量都减少2，外圈流量都增加2，并在无流量的边B5A2上增加外圈流向和流量2，得到新的交通流向图。;第五步：对新方案进行检验。 圈B5B4B3A2的圈长=4+4+5+8=21,内圈长= 4+5=921/2，外圈长= 821/2.内圈、外圈的长度均不超过圈长的一半，所以圈B5B4B3A2不存在迂回。 圈A3B1B2A1B3B4的圈长=7+2+3+6+4+3=25,内圈长= 2+3+6+3=1425/2，有迂回，所以流向图不是最优流向图。故需要调整。;4;故本物资调运问题的最优方案为： ;指导我们作流向图和检查流向图的方法是以下口诀： “流向画右边，对流不应当 里圈和外圈，不过半圈长”;本节小结;