第八章数学方法在运输实务中的应用

第八章 数学方法在运输实务中的应用81 图上作业法 82 表上作业法83 运输解决方案案例81 图上作业法教学目的与要求1、 掌握图上作业法的概念、方法步骤。 2、 能够应用图上作业法作出物资调运方案。 内容和时间安排、教学方法1内容和时间安排：图上作业法的概念、步骤； 1课时。 应用案例； 1课时。 2教学方法：讲授，讨论分析，思考题。 教学重点和难点1重点：图上作业法的方法步骤。 2难点：应用图上作业法解决物资调运问题。 思考题粮食调运方案（问题内容课堂给出）一、图上作业法的基本概念这是一种借助于流向流量图而进行货流合理规划的简便线性规划方法，它能消除环状交通网上物资调运中的相向运输（包括隐蔽相向运输）和迂回运输，得出总吨公里最小的方案。这种方法由于对环状交通网上的货流规划行之有效，在苏联被称为圆周关系法。它虽在三十年代初已被人提出，但在中国得到广泛实际应用和数学证明，却是解放以后的事情。我国学者研究线性规划在管理中的应用,是从交通运输问题开始的。1950年,作为全国工业基地和抗美援朝后方基地的东北地区的交通运输已经极为繁忙,煤炭、粮食部门都深切地感到了合理调运,节约运力的迫切需要。当时东北计委会一个专营运输的小组,往往为比较两个运输方案,不分昼夜计算,终于发现了后来被称为“图上作业法”的一些方法。我国数学家和管理学家解决粮食运输问题时,再次提出了“图上作业法”(一种较为简单的图论方法),其基本前提是避免对流和弯路。实际上,“图上作业法”所处理的问题,国外在40年代已经有了模型及代数解法。而我国运输调拨工作者则给出了一种几何解法:先在图上标出“产地”与“销地”。若规定由A,终点为B,并在矢量旁边标出a 所谓“对流”,即在同一条线路的两侧均有箭头矢量。若路线地图上有一个环路,则环路内侧的箭头矢量的长度之和与环路外侧的箭头矢量的长度之和均不超过环路之长度的一半,则称为“迂回”。于是有下面的法则:当一个调拨方案,即箭头矢量图,画在地图上,若既无对流,对于任何环路又无迂回,则这一调拨方案就是最优的。反之亦然。从任一调拨方案出发,若有对流,则改变分配办法可以取消对流,若有迂回,则可用缩短外圈或内圈的箭头矢量长度来取消迂回,经逐步调整,即可获最佳调拨方案。二、图上作业法的基本步骤1绘制交通图 根据客户所需货物汇总情况、交通线路、配送点与客户点的布局，绘制出交通示意图。 2将初始调运方案反映在交通图上 任何一张交通图上的线路分布形态无非为成圈与不成圈两类。对于不成圈的运输，可按“就近调运”的原则即可，很容易得出调运方案。对于成圈的，可采用破圈法处理，即可得出初始调运方案。在绘制初始方案交通图时，凡是按顺时针方向调运的货物调运线路，其调运箭头线都画在圈外，称为外圈；否则，其调运箭头线都画在圈内，称为内圈，或者两种箭头相反方向标注也可。3检查与调整 面对交通图上的初始调运方案，首先分别计算线路的全圈长、内圈长和外圈长（圈长即指里程数），如果内圈长和外圈长都分别小于全圈长的一半，则该方案即为最优方案；否则，即为非最优方案，需要对其进行调整。三、图上作业法在运输问题中的应用举例，见课件。返回82 表上作业法教学目的与要求1、 掌握表上作业法的概念，方法步骤。2、 能应用表上作业法解决运输问题。 内容和时间安排、教学方法1内容和时间安排：表上作业法的概念、方法步骤； 1课时。 表上作业法案例分析； 1课时。2教学方法：讲授，讨论分析，思考题。 教学重点和难点1重点：表上作业法的方法步骤。2难点：应用表上作业法解决实际运输问题。 思考题用表上作业法如何解决物资调运问题。一、表上作业法的基本概念用列表的方法求解线性规划问题中运输模型的计算方法。是指线性规划一种求解方法。当某些线性规划问题采用图上作业法难以进行直观求解时，就可以将各元素列成相关表，作为初始方案，然后采用检验数来验证这个方案，否则就要采用闭回路法、位势法或矩形法等方法进行调整，直至得到满意的结果。这种列表求解方法就是表上作业法。运输问题是一类常见而且极其典型的LP问题。从理论上讲，运输问题可以用单纯型来求解。但由于运输问题数学模型具有特殊的结构，存在一种比单纯型法更简便的计算方法表上作业法。用表上作业法来求解运输问题比单纯型可节约计算时间与计算费用，但表上作业法实质上仍是单纯型法。二、表上作业法在运输问题中的应用例1 某部门有3个生产同类产品的工厂（产地）,生产的产品由4个销售点（销地）出售，各工厂的生产量、个销售点的销售量（假定单位均为t)以及各工厂到个销售点的单位云价（元/t)示于下表，试研究如何调运才能使总的运费最小？1、给出运输问题的初始可行解（初始调运方案）以下介绍三种常用的方法(1) 最小元素法(2)西北角法(3)沃格尔（Vogel）法2、解的最优性检验可以用闭回路法或位势法。返回83 运输解决方案案例教学目的与要求1、 掌握几种常见的运用数学方法解决运输问题做法。 2、 培养对所学方法应用的能力。 内容和时间安排、教学方法1内容和时间安排：案例分析 2课时。2教学方法：讲授，讨论分析，思考题。 教学重点和难点1重点：产销不平衡的运输问题。 2难点：应用能力的培养。 思考题谈谈对用数学方法解决实际运输问题的认识。运输问题的进一步讨论（产销不平衡问题）1、若总产量大于总销量，即我们从例子来说明如何求解例1 某市有三个造纸厂A1，A2和A3，其纸的产量分别为8，5和9个单位，有4个集中用户B1，B2，B3和B4，其销量及各造纸厂到用户的单位运价如表3-14所示，请确定总运费最少的调运方案。解：总产量是22，总销量是18。可增加一个假想的销地B5，构造新的产销平衡表3-15。由于实际上它并不存在，因此，由产地Ai（i=1，2，3）调运到这个销地的物品数量（i=1，2，3）（相当于松弛变量），实际上是存储在Ai的物品数量。就地存储的物品不经运输，故可令其单价=0（i=1，2，3），先用Vogel法求初始调运方案：至此，所有检验数0，当前解极为最优解。X=（4，0，0，4；0，3，0，0；0，0，5，2）T所对应的运费 z=43+44325125=49 2、销大于产例2 三个城市每年需分别供应电力320，250和350单位。由，电站提供，它们的最大可供电量分别为400，450单位。单位费用如表3-37所示。由于需求量大于可供量，决定城市1的供应量可减少030单位，城市2的供应量不变，城市3的供应量不少于270单位，试求总费用最低的分配方案（将可供电量用完）。城市电站123最大可供电量151822400212516450需求量320250350850920解：由于需求量供电量，我们虚拟一个电站，其供应量为70单位。该调运量实际上是不能提供电量的。故应取电费为0。但由于需求的特殊性，三个城市的需求应分两部分，一部分是必须提供的，另一部分可调整。于是设想把三个城市拆成5个城市，必须电量不能由城市电站1eq oac(,1)123eq oac(,3)3最大可供电量15151822224002121251616450M0MM07