第7章_物资调运问题的图上作业法

1、第第 7 章章 物资调运问题的物资调运问题的 图上作业法图上作业法刘群锋刘群锋 讲师讲师东莞理工学院东莞理工学院1 物资调运的交通图物资调运的交通图p交通图交通图n反映产地与销地的交通路线及其距离反映产地与销地的交通路线及其距离n产地用产地用“”表示，产量写在圆圈内表示，产量写在圆圈内n销地用销地用“”表示，销量写在方框内表示，销量写在方框内n距离写在弧的旁边距离写在弧的旁边1 物资调运的交通图物资调运的交通图p交通图举例交通图举例ACBGFDE10589793325241 物资调运的交通图物资调运的交通图p交通图举例交通图举例ABHECI500006000030000200003000050

2、000266239180393D80000F50000G500001151653172523491202 物资调运的流向图物资调运的流向图p流向图流向图n物资调运的方案可以用流向图表示物资调运的方案可以用流向图表示n例如例如ACBGFDE1058979(10)(8)(7)(7)(9)2 物资调运的流向图物资调运的流向图p关于流向图的一些规定关于流向图的一些规定n箭头必须表示物资运输的方向箭头必须表示物资运输的方向n流量写在箭头的旁边，流量写在箭头的旁边，加小括号加小括号。n流向不能直接跨越路线上的收点、发点、交流向不能直接跨越路线上的收点、发点、交叉点叉点n任何一段弧上最多只能显示一条流向！任

3、何一段弧上最多只能显示一条流向！即同即同一段弧上的多条流向必须合并。一段弧上的多条流向必须合并。n除端点外，任何点都可以流进和流出除端点外，任何点都可以流进和流出2 物资调运的流向图物资调运的流向图p含有圈的流向图含有圈的流向图ABHECI500006000030000200003000050000D80000F50000G50000(50000)(20000)(30000)(50000)(60000)(10000)(70000)(50000)2 物资调运的流向图物资调运的流向图p含有圈的流向图的补充规定含有圈的流向图的补充规定n顺时针方向的流向必须画在圈的内侧，称为顺时针方向的流向必须画在圈

4、的内侧，称为内圈流向内圈流向n逆时针方向的流向必须画在圈的外侧，称为逆时针方向的流向必须画在圈的外侧，称为外圈流向外圈流向2 物资调运的流向图物资调运的流向图p最优流向图最优流向图n总吨公里数最小总吨公里数最小的流向图的流向图l把每一条弧上的流量乘以相应的距离，再求和把每一条弧上的流量乘以相应的距离，再求和p怎样得到最优流向图？怎样得到最优流向图？n作出第一个流向图作出第一个流向图n检验其是否最优？检验其是否最优？l若是，结束；若是，结束；l否则，调整，直到最优。否则，调整，直到最优。3 第一个流向图的作法第一个流向图的作法p无圈的交通图无圈的交通图n供需归邻站法供需归邻站法p有圈的交通图有圈

5、的交通图n首先首先破圈破圈，变为无圈交通图，变为无圈交通图n再用再用“供需归邻站法供需归邻站法”3 第一个流向图的作法第一个流向图的作法p供需归邻站法举例供需归邻站法举例ACBGFDE10589793325243 第一个流向图的作法第一个流向图的作法(10)(8)(7)(7)(9)p供需归邻站法举例供需归邻站法举例ACBGFDE10589793 第一个流向图的作法第一个流向图的作法p含有圈的交通图含有圈的交通图ABHECI500006000030000200003000050000266239180393D80000F50000G500001151653172523491203 第一个流向图的

6、作法第一个流向图的作法ABHECI500006000030000200003000050000D80000F50000G50000(30000)(80000)(50000)(110000)(60000)(20000)(50000)p含有圈的交通图含有圈的交通图3 第一个流向图的作法第一个流向图的作法p含有圈的交通图含有圈的交通图3233332223334412621GABCFIHDE223 第一个流向图的作法第一个流向图的作法p含有圈的交通图含有圈的交通图334412621GABCFIHDE(3)(6)(3)(2)(4)(1)(7)(1)4 检验与调整检验与调整p图上作业法的基本定理图上作业法

7、的基本定理n用用“供需归邻站法供需归邻站法”得到的无圈流向图是最得到的无圈流向图是最优的！优的！n含圈流向图的每一个圈上的内圈流向和外圈含圈流向图的每一个圈上的内圈流向和外圈流向的总长度都不超过圈长的一半，该流向流向的总长度都不超过圈长的一半，该流向图就是最优的！图就是最优的！4 检验与调整检验与调整p怎样检验一个含圈流向图是否最优？怎样检验一个含圈流向图是否最优？n计算每一个圈的内圈长和外圈长计算每一个圈的内圈长和外圈长n检验它们是否超过圈长的一半检验它们是否超过圈长的一半l若是，则非最优；否则，最优若是，则非最优；否则，最优4 检验与调整检验与调整p检验含圈流向图是否最优检验含圈流向图是否

8、最优AC1050D3030(10)(30)2344(20)BAC1050D3030(10)(20)2344(30)B4 检验与调整检验与调整p检验含圈流向图是否最优检验含圈流向图是否最优ABHECI500006000030000200003000050000D80000F50000G50000(30000)(80000)(50000)(110000)(60000)(20000)(50000)2662391803931151653172523491204 检验与调整检验与调整p怎样调整流向图使之成为最优？怎样调整流向图使之成为最优？n当外圈流向的总长度超过圈长的一半时当外圈流向的总长度超过圈长的

9、一半时l找出调整量，每个外圈流量减去调整量，每个内找出调整量，每个外圈流量减去调整量，每个内圈流量加上调整量圈流量加上调整量l无流量的弧添上内圈流向，流量为调整量无流量的弧添上内圈流向，流量为调整量n当内圈流向的总长度超过圈长的一半时当内圈流向的总长度超过圈长的一半时l找出调整量，每个内圈流量减去调整量，每个外找出调整量，每个内圈流量减去调整量，每个外圈流量加上调整量圈流量加上调整量l无流量的弧添上外圈流向，流量为调整量无流量的弧添上外圈流向，流量为调整量4 检验与调整检验与调整p调整流向图使成为最优调整流向图使成为最优AC1050D3030(10)(30)2344(20)BAC1050D30

10、30(10)(20)2344(30)B5 基本流向图与改进图上作业法基本流向图与改进图上作业法p检验与调整下面的流向图检验与调整下面的流向图3233332223334412621GABCFIHDE(3)(6)(3)(2)(4)(1)(7)(1)225 基本流向图与改进图上作业法基本流向图与改进图上作业法p改进图上作业法改进图上作业法n作出第一个流向图，使之成为基本流向图作出第一个流向图，使之成为基本流向图n检验其是否最优？检验其是否最优？l若是，结束；若是，结束；l否则，调整，直到最优。否则，调整，直到最优。5 基本流向图与改进图上作业法基本流向图与改进图上作业法p基本流向图基本流向图n投影图

11、投影图连通且不含圈连通且不含圈的流向图的流向图p流向图的投影图流向图的投影图n流向图中有流向的弧留下流向图中有流向的弧留下n流向图中无流向的弧去掉流向图中无流向的弧去掉5 基本流向图与改进图上作业法基本流向图与改进图上作业法p画出投影图、判断是否基本流向图画出投影图、判断是否基本流向图50103030(10)(30)2344(20)501030305 基本流向图与改进图上作业法基本流向图与改进图上作业法p画出投影图、判断是否基本流向图画出投影图、判断是否基本流向图5030305050303050(30)(50)23445 基本流向图与改进图上作业法基本流向图与改进图上作业法p画出投影图、判断是

12、否基本流向图画出投影图、判断是否基本流向图ABHECI500006000030000200003000050000D80000F50000G50000(30000)(80000)(50000)(110000)(60000)(20000)(50000)2662391803931151653172523491205 基本流向图与改进图上作业法基本流向图与改进图上作业法5 基本流向图与改进图上作业法基本流向图与改进图上作业法p怎样把非基本流向图化成基本流向图？怎样把非基本流向图化成基本流向图？n在流向图中添加虚流向，让投影图连通在流向图中添加虚流向，让投影图连通5 基本流向图与改进图上作业法基本流向

13、图与改进图上作业法p将流向图化成基本流向图将流向图化成基本流向图5030305050303050(30)(50)23445 基本流向图与改进图上作业法基本流向图与改进图上作业法p将流向图化成基本流向图将流向图化成基本流向图ABHECI500006000030000200003000050000D80000F50000G50000(30000)(80000)(50000)(110000)(60000)(20000)(50000)2662391803931151653172523491205 基本流向图与改进图上作业法基本流向图与改进图上作业法5 基本流向图与改进图上作业法基本流向图与改进图上作业

14、法p基本流向图的作用基本流向图的作用n最优流向图一定是基本流向图！最优流向图一定是基本流向图！n所有所有“要检查的圈要检查的圈”都合格的基本流向图必都合格的基本流向图必定是最优流向图！定是最优流向图！p基本流向图的基本流向图的“要检查的圈要检查的圈”n要检查的圈的个数要检查的圈的个数=小圈的个数小圈的个数n每次对投影图每次对投影图(在变化中在变化中) 加上一条无流向加上一条无流向的弧得到的圈的弧得到的圈5 基本流向图与改进图上作业法基本流向图与改进图上作业法p改进图上作业法举例改进图上作业法举例n已知交通图如下，求最优流向图已知交通图如下，求最优流向图3233332223334412621GA

15、BCFIHDE225 基本流向图与改进图上作业法基本流向图与改进图上作业法n第一个流向图如下，它是不是基本流向图第一个流向图如下，它是不是基本流向图334412621GACFIHDE(3)(6)(3)(2)(4)(1)(7)(1)5 基本流向图与改进图上作业法基本流向图与改进图上作业法n检查并调整所有检查并调整所有“要检查的圈要检查的圈”直到合格直到合格3233332223334412621GABCFIHDE(3)(6)(3)(2)(4)(1)(7)(1)225 基本流向图与改进图上作业法基本流向图与改进图上作业法n最优流向图为最优流向图为3233332223334412621GABCFIHDE(3)(4)(0)(1)(1)22(3)(3)(0)7 车辆调度问题车辆调度问题p某运输公司接受了一项货运业务如下表，收、某运输公司接受了一项货运业务如下表，收、发点的位置如下图。求车辆的最优调度方案。发点的位置如下图。求车辆的最优调度方案。货名货名发货点发货点收货点收货点运量运量距离距离水泥水泥B1A2803石灰石灰B2A1505砖砖B3A3805341322B3