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

第八章 数学方法在运输实务中的应用 81? ?图上作业法 8—2?? 表上作业法 8—3?? 运输解决方案案例　 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)