运输问题的数学模型详细讲解,有案例+多种方法.ppt

运输问题的数学模型 一、 运输问题及其数学模型 二、 图上作业法 三、 表上作业法 一、 运输问题及其数学模型 在经济建设中，经常碰到物资调拨中的运输问题。 例如 煤、钢材、粮食、木材等物资，在全国都有若干生产基地，分别将这些物资调到各消费基地去，应如何制定调运方案，使总的运输费用最少？ 运输问题的一般提法是：设某种物资有m个产地和n个销地。产地Ai的产量为 ；销地Bj的销量 。从第i个产地向第j个销地运输每单位物资的运价为Cij。 这就是由多个产地供应多个销地的单品种物资运输问题。问如何调运这些物资才能使总运费达到最小。 单位运价表 （1） 。即运输问题的总产量等于其总 销量，这样的运输问题称为产销平衡的运输问题。 （2） 。即运输问题的总产量不等于总 销量，这样的运输问题称为产销不平衡的运输问题。 若用xij表示从Ai到Bj的运量，那么在产销平衡的条件下，要求得总运费最小的调运方案，数学模型为： 二、图上作业法 在运输中，若使用同一种运输工具，则运费的计算往往仅与运送物资的多少及里程有关。因此，在求最佳的运输方案时，用吨公里作为度量的标准比用运费作为度量标准更加方便、实用。 在求解最佳运输方案时，用吨公里作为度量单位，还可以在已经画出的交通图上进行，操作起来较为简单、方便、直观、快捷。 在铁路、公路等交通部门经常使用这种方法决策最优运输问题，这种方法被称为图上作业法。 （一）编制交通图和流向图 交通图 反映发点（产地）与收地（销地）及交通线路及其距离组成的图形。 发点用“○”表示，发出货物的数量记在“○”之内（单位：吨） 收地（销地）用“□”表示，收取货物的数量记在“□”之内（单位：吨） 两点之间的线路长度记在交通线路的旁边。 1、交通图 1、交通图 2、流向图 流向图: 在交通图上表示物资流向的图被称为流向图。在图中每个发点吨数全部运完，每个收点所需吨数均已满足。 2、流向图 2、流向图 关于流向图的一些规定 箭头必须表示物资运输的方向 流量写在箭头的旁边，加小括号。 流向不能直接跨越路线上的收点、发点、交叉点 任何一段弧上最多只能显示一条流向！即同一段弧上的多条流向必须合并。 除端点外，任何点都可以流进和流出 2、流向图 2、流向图 含有圈的流向图的补充规定 顺时针方向的流向必须画在圈的内侧，称为内圈流向 逆时针方向的流向必须画在圈的外侧，称为外圈流向 内圈流向、外圈流向举例 （二）对流向图的检验 在物资运输中，把某种物资从各发点调到各收点的调运方案是很多的，但我们的目的是找出吨—公里数是最小的调运方案。这就要注意在调运中不要发生对物流运输和迂回运输，因此，我们在制定流向图时，就要避免它的出现。 （1）不合理的现象1：对流 （1）对流：所谓对流就是在一段线路上有同一种物资出现相对运输现象（往返运输）（同一段线路上，两各方向都有流向），如图4-4。 甲乙两地是一种对流现象。如果把流向图改成图4-5，就可以避免对流现象，从而可以节约运输量20×10=200(吨公里)。 （2）不合理的现象2：迂回 （2）迂回：当收点与发点之间的运输线路有两条或两条以上时（即交通图成圈），如果运送的货物不是走最短线路，则称这种运输为迂回运输。 注：当交通图成圈时，如果流向图中内圈流向的总长（简称内圈长）或外圈流向的总长（简称外圈长）超过整个圈长的一半就称为迂回运输。例如某物资流向图如图4-6、4-7所示。 迂回运输的判断 （3）、正规（最优）流向图 正规（最优）流向图：一个最优的调运方案，它的流向图必是无对流、无迂回的流向图，称这种流向图为正规流向图。 物资调运的图上作业法就是寻找一个无对流、无迂回的正规流向图。 步骤如下： 作出一个无对流的初始可行方案； 检验有无迂回 若无，结束； ??否则，调整，直到最优。 三、图上作业法的求解过程 1、无圈的交通图 2、有圈的交通图 方法：供需归邻站 1、交通图无圈情形 【例1】求最优调运方案 案例分析 口诀：抓各端，各端供需归邻站 即：先满足端点的要求，逐步向中间逼近，直至收点与发点得到全部满足为止。 练一练 答案 2、交通图有圈情形 【例2】求最优调运方案 解题步骤： 第一步：变有圈为无圈。 方法：“丢边破圈”。即丢掉一条边，破去一个圈。 注意：丢边时，往往是丢掉圈中长度最大的边。如图所示 第一步： “丢边破圈” 第二步：在无圈的交通图上作流向图。 原则：先外后内，先端点后中间点，要求每个边都有流向。当某条边无流向时，必须填上运输量为零的虚流向。 第二步：作流向图 第三