线性规划在运输问题中的应用

1、线性规划在运输问题中的应用【摘要】 用运筹学的思想探讨运筹学课程的教学方法。运筹学中的指派问题、最短路问题，最小费用流问题可转化为运输问题或转运问题，从而可以统筹安排这些教学内容，为提高教学效果，减少教学时间找出更优的教学方法。【关键词】 运输问题；转运问题； 运筹学；线性规划；教学方法引言：随着我国国民经济的不断开展，企业之间的交易活动更加频繁,同地区、不同地区、甚至跨国的交易活动也不断发生，运输那么成为交易的活动重点了。交通运输作为国民经济的一个重要部门，作为人类进步、社会开展的一个重要推动力，其开展模式正在对环境产生越来越重要的影响。传统的运输方式已经不能满足环境保护、经济开展以及交通运

2、输本身开展的需求，探寻与环境、资源条件相适应的运输是非常重要的一个问题。人们在运输方面趋利避害建立更好的运输方法，让交通运输的方法到达一个更高的水平。1线性规划简介线性规划法是解决多变量最优决策的方法，是在各种 相互关联的多变量约束条件下，解决或规划一个对象的线性目标函数最优的问题，即给与一定数量的人力、物力和资源，如何应用而能得到最大经济效益。当资源限制或约束条件表现为线性等式或不等式，目标函数表示为线性函数时，可运用线性规划法进行决策。线性规划法就是在线性等式或不等式的约束条件下，求解线性目标函数的最大值或最小值的方法。其中目标函数是决策者要求到达目标的数学表达式，用一个极大&#

3、160;或极小值表示。约束条件是指实现目标的能力资源和内 部条件的限制因素，用一组等式或不等式来表示。线性规划是决策系统的静态最优化数学规划方法之一。它作为经营管理决策中的数学手段，在现代决策中的应用是非常广泛的，它可以用来解决科学研究、工程设计、生产安排、军事指挥、经济规划；经营管理等各方面提出的大量问题。 最近几年，我国物流产业快速开展，形成了物流热。在物流作业的管理活动中，有着大量的规划问题，物资的合理调运就是其中一个比拟重要的问题。求物资调运的最优调运方案，就是要在满足各种资源限制的条件下，找到使运输总费用最小的调运方案。 2.线性规划在运输中的应用在现实

4、的生产经营、商品销售、经济建设和物资管理过程中，常常会遇到各类物资的分配和调运问题，即将各种生产资料或生活资料消耗品从供给基地调运到需求基地，这里就需要如何根据现有条件科学、合理的安排调运方案，提高运输经济效益。这就是属于线性规划中网络配送的以最小的本钱完成货物的运输问题。运输问题就是讨论有关物资调运的问题，即将数量和单位运价都给定的某种物资从供给站运送到消费站，要求在供给和需求平衡的同时，制定出流量与流向，使总运输本钱最低。运输问题是特殊的线性规划问题，根据问题的要求，建立数学模型，用表上作业法或线性规划软件求解，即可得出最正确的调运方案，取得了较好的经济效益。在运输问题中，确定的需求限制占

5、据着重要的地位，即必须确定需求以及相应地确定需求的约束条件。  3.运输问题的特征 运输问题关心的是以最低的总配送本钱把供给中心出发地的任何产品运送到每一个接收中心目的地。每一个出发地都有一定供给量配送到目的地，每一个目的地都需要一定的需求量。运输问题在供给量和需求量两方面都做出了如下的假设：需求假设。每一个出发地都有一个固定的供给量，所有的供给量都必须配送到目的地。与之类似，每一个目的地都有一个固定的需求量，整个需求量都必须由出发地满足本钱假设。从任何一个出发地到任何一个目的地的货物配送本钱和所配送的数量成线性比例关系。因此，这个本钱就等于配送的单位本钱乘以所配送的数量。

6、运输问题所需要的数据仅仅是供给量、需求量和单位本钱，这些就是模型参数。如果一个问题可以完全描述成如下表所示的参数表形式，明确出发地、供给量、需求量和单位本钱，并且符合需求假设和本钱假设，那么这个问题不管其中是否涉及到运输都适用于运输问题模型，最终目的都是要使配送的总本钱最小。 4.运输问题的数学模型 设某种物品有 m 个产地 ， ， ，各产地的产量分别是 ，；有 n 个销地 ，各销地的销量分别为 ，假定从 产地 i=1，2，m 向销地 j=1，2，n 运输单位物品的运价为 ，假设用表示从到的运输量，那么在产销平衡条件下，总费用最低的数学模型为  运输问题通常用表上

7、作业法求解，表上作业法是单纯形法求解运输问题时的一种简化方法，其实质是单纯形法。表上作业法首先需要经过次加法运算求出初始基可行解。在初始基可行解根底上用闭回路法或位势法计算所有空格非基变量的检验数 ，如用位势法，需要经过解次一元一次方程计算位势和计算个检验数，共需要计算 次。 当所有检验数时，得最优解，否那么需要在表上用闭回路法进行调整，确定换入变量和换出变量，找出新 的基可行解，直到得出最优解为止。假设需要调整 k 次，那么 中间环节需要计算次。故全部过程一共需要经过次运算，当 m，n 很大时，表上作业的计算量庞大且繁杂。本文提出的用线性规划法求解 运

8、输问题将大大提高最优解的求解速度，大大提高了效率。 5.实例 现在物流业面临的新问题是： 认定所给问题确实是一个线性规划问题； 把它建立起线性数学模型； 并能够完成具体实务的全部工作。第一个问题实质上是具体实务究竟满足什么条件才能应用线性规划的方法。一般地说，必须有：一定要满足将目标表为最小化或最大化的要求；一定要有到达目标的不同方法，且必须要有选择的可能性；要求的目标是有限制条件的；必须将约束条件用数学表示为线性等式或线性不等式，并将目标函数化为线性函数。5.1物资调运最优问题： 例 1：苹果的运价及产销量如表 1，求总运费最省的运输方案。运价销地产量

9、B1 B2 B3产地A174109产地A231137销量656表1解：找线性关系：设表示产地供给销地的物资数量，产地A1 产量只有9个单位，可供销地B1、B2、B3， 其和为9，B1、B2、B3 的量有多种选择。而B1 只需6个单位，可选A 1、A2 的产量，其和小于6。因为总销量大于总产量。故约束为： 又从A1 运1 个单位的苹果到B1 需运价7 个单位，假设个单位那么运价，因此满足约束的得总运价的目标函数为：此约束方程组不是标准型。将约束条件方程组2标准化为：用单纯形法的程序在计算机上可得最优调运矩阵为，最省的运费为。特别地，当产量大于销量时，如常数9 改为12，约束条

10、件前两个方程改为，后面三个用等式。当产销平衡时，约束方程组是等式方程组，方程组的个数为个。5.2车辆调度问题物流部门承接的运输千万种，并往往是几十种物资同时调运。为此，只有一种物资的数学模型求最优调运方案方法，在多种物质运输情况下就不能直接使用。原因是：在调度汽车去完成运输任务时，免不了要出现空驶现象。例如某车队有一天要完成如表2 所示的运输任务，各地间的距离如表3，问应怎样安排汽车去完成这些任务才能做到最省？ 分析：满车路线和方向显然是固定的，但空车的路程、方向却没有固定。如把木材从火车站运到建筑工地卸下后，空车即可去火车站装煤，也可去文具公司装纸张。空车的走法不同，空驶的t

11、83;km 数当然也不同，这就产生了车辆调度问题。车辆调度问题主要解决的是：怎样安排车辆去完成所有的运输任务并使空驶的t·km数最小。物资调运问题是“怎样才能使物资运输的t·km 数最小；这就是说把空车看成是一批货物卸几吨货物就看成是几吨空车，那么把车辆调度问题转化为物资调运问题。把空车看成是货物，其发、收产、销点及发、收产、销量按如下的方法决定： 1假设某点的缷货总量大于装货总量，那么该点是空车的发点，其发量等于卸货总量与装货总量之差。如学校的卸货总量为4，装货为0，故学校是发点，发量为4。2假设某点装货总量大于卸货总量，那么该点是空车的收点，其收量也是二者之差

12、。3如果某点的卸货总量等于装货总量，如此点不存在空车那么不予考虑。为此，车辆调度问题可作为物资调运问题来处理。即空车的流向应怎样才能使车辆调度合理？其主要步骤如下：确定空车的收发点和收发量，并列表；确定空车调运的数学模型，并求解；根据所得解并结合具体情况合理调派车辆。解：收点：火车站、文具公司、粮店；发点：建筑工地、钢厂、学校。约束条件为：用单纯形法的程序在计算机上可得：钢厂、学校分别向火车站发2t 空车，建筑工地向文具公司和粮店发2t 空车。空车吨公里数最小是：6.结论通过上例分析，我们可以很清楚地了解线性规划企业运输决策的整个运作过程具有很大的实践意义。利用线性规划进行运输决策，可以制定出

13、最正确运输方案，往哪里运，运多少，而且可以同时对线性规划的进一步运用、剖析运输决策中各环节、各部门之间的内在联系，使人力、物力和财力能够得到充分利用，从而实现最优化的货物流通，使企业的利润进一步追加，最终得到最正确运输方案，提高企业经济效益。然而在实际应用中，往往要综合考虑各个方面的影响因素，仅仅从货物分配方面考虑并不能单纯的解决运输费用的最小控制，所以，对于该问题的研究还有待于更深一步的探讨。7.心得与体会在教学中，将看似不同的问题归纳转化为同一问题，非常重要。首先，这涉及到教学内容的结构问题，原来看似不同的问题可能在教材的不同章节，转化为同一问题后可并入同一章节。第二，对提高教学效果有一定

14、的帮助。对老师而言，可减少教学时间，原先要花较多时间讲解不同的问题，现在只需讲解一个问题，然后作为同一问题举一反三，不仅可将原问题讲授得更清楚，也解决了新问题。对学生而言，原先要记多种问题的解法，现在只需记一种解法就可以了，减轻了学习负担。第三，更重要的是，启发学生对问题有更深入的理解，抓住事物的本质，而不是停留在外表，这对培养学生抽象思维、综合归纳能力是大有裨益的。当然，要做到这一点，对老师的要求显然更高，必须要花更多的时间和精力研究问题，吃透教材，理解精髓，融会贯穿，非一般的应付教学所能解决的。最后，在用计算机求解方面，可用同一程序处理这些类似的问题。因此，将看似不同的问题归纳转化为同一问题，可以统筹安排教学内容，在现有的教学条件下，能帮助我们提高教学效果，减少教学时间。这正是运筹学的精髓，对各种有限资源进行统筹安排，找出最优方案。所以本文与其说是教学体会，还不如说是运筹学方法的运用，用运筹学方法探讨运筹学的教学问题，为运筹学教学找到一种更好的方法。8.参考文献1 徐辉,张延飞.管理运