运输问题的求解及其应用【毕业论文】.doc

1、 本科 毕业 论文 （ 20 届） 运输问题的求解及其应用 所在学院 专业班级 数学与应用数学 学生姓名 学号 指导教师 职称 完成日期 年 月 摘要 ： 本课题主要探讨了如何判别一个运输问题的调运方案是最优，对通常采用的两种闭回路法或位势法做综述整理，同时探讨更好的一次性算法，既避免了闭回路法中对所有非基变量检验数的一一计算 ,又回避了位势法中需要多次求解线性方程组以计算位势的过程。本课题 主要 利用 了 已有或已得到的算法对实际问题进行分析研究。 关键词 ： 运输问题；最优方案；一次性算法；闭回路法；位势法 Transportation problem solving and its ap

2、plication Abstract: My subject mainly discusses how to distinguish the transportation problem with optimal solution scheme, then synthetically induces about closed loop method or potentials method which we always use. At the same time, we explore a better method to one-timely get the result. It not

3、only avoids calculating one by one all the basic variable inspection number with closed loop method, but also avoids the process of solving the linear equations many times to calculat potentials with potentials method. In short, the goal of my topic is analyzing and studying practical problems with

4、exsited or achieved methods. Key words: Transportation problem; The optimal solution; One-time algorithm; Closed loop method;Potentials method 目录 1 运输问题简介 . 1 2 运输问题模型 . 2 3 几种常用检验法的缺陷 . 3 3.1 闭回路法的缺陷 . 4 3.2 位势法的缺陷 . 8 3.3 改进的闭回路法的缺陷 . 12 3.4 动态规划法的缺陷 . 12 4 一种新的检验方法 . 12 5 应用举例 . 13 6 运输问题在消防中的应用

5、. 15 7 结束语 . 17 致谢 . 错误 !未定义书签。 参考文献 . 17 1 1 运输问题简介 运输问题是 一类具有特殊结构的 线性规划 问题。由于运输问题约束方程组的系数矩阵是完全么模的，即所有的子 行列式 为 0 或 1 ，存在着比 单纯形法 更简单的特殊解法。对于规模不太大的运输问题可用图上作业法或表上作业法求解。这类问题的典型提法是，为了把某种产品从若干个产地调运到若干个销地，已知每个产地的供应量和每个销地的需求量，如何在许多可行的调运方案中，确定一个总运输费或总 运输量 最少的方案。 具有上述特点的线性规划问题通常被称为运输型问题。现已发现的运输型问题有以下6 类 : 一般

6、运输问题 ,又称希契科克运输问题，简称 H 问题。 网络运输问题，又称图上运输问题 ,简称 T 问题。 最大流量问题 ,简称 F 问题。 最短路径问题 ,简称 S 问题。 任务分配问题，又称指派问题 ,简称 A 问题。 生产计划 问题，又称 日程计划 问题 ,简称 CPS 问题。其中一般运输问题、任务分配问题和生产计划问题通常都可以用表上作业法求解，而网络运输问题、最大流量问题和最短路径问题一般可用图上作业法或 网络技术 求解 （参见文献 1）。 当使用 表上作业法求解运输问题 时 。初始基本可行解的求法有三种： 左 上角法。它的基本思想是给运输表中左上角的变量分配运输量以确定产销关系。 最

7、小元素法，或最小成本法。它的基本思想是就近供应，即从运输表中运价最小的格子开始分配运输量以确定产销关系。 元素差额法 ,又称沃格尔近似法，简称 VAM 法。它是从运输表中各行和各列的最小元素和次小元素的差额来确定产销关系。改进初始基本可行解的方法有两种： 闭回路法。这种方法需要对每一个空格寻找一条闭回路，并根据闭回路求出每个空格的检验数。当运输问题中 m 和 n 较大时，计算检验数的工作量很大。 位势法，或 乘数 法。先对初始调运方案求出位势，然后求各空格的检验数。当所有的检验数均为非负时，就得到最优方案。如果出现负的检验数，则从检验数为负的空格出发，作闭回路，重新计算检验数，作进一步调整。用

8、位势法求检验数就是对偶问题的表上作业法 （参见文献 2）。 但是我们发现对于实际的运输问题，上述优化方法很难将运输过程中所发生的费用都考虑进去，因此，如果教条地采用上述优化方法直接进行优化，则很难保证此方案是真正的最佳方案。实际 的运输问题中上述方法没考虑到的因素有： （ 1）对运输问题中的中转再分拨，其中转的装卸搬运费用，无论是求最小费用最大流的优化方法还是表上作业法求具有中转站的运输问题最佳方案时，都没有考虑此因素，但装卸搬运费用及时间在物流费用中占有一定的比重。 （ 2）多种运输方式的联合运输问题，当物资通过运输网络从出发地运往目的地时，由于各线路的不同特点，可能需要采用不同的运输方式，

9、不同的运输方式所产生的费用是不同2 的，但上述的优化方法没有考虑此因素。虽然，人们对多式联运的优化方法也进行了一定的研究，但其方法也是有某些前提条件。 （ 3）对于物流系统中的配送问题，由于实际的配送问题，其配送方式有多种，按照物流据点的不同，可分为配送中心配送、仓库配送、就站配送、就港配送、就厂配送等；按照配送货物的品种和数量，可分为单一品种大批量配送、多品种小批量配送、配套成套配送等；按照配送时间和数量，可分为定时配送、定量配送、定时定量配送、不定时（及时）配送等；按照配送时间和路线，可分为定时定路线配送、不定时定路线配送、定路线巡回配送等；按照配送用户的范围，可分为企业配送、行业配送、地

10、区配送、城市配送等；按照配送经营形式的不同，可分为销售配送、供应 配送、销售 供应一体化配送、代理配送等；按照企业之间的关系，可分为共同配送、集团配送、单独配送等。寻找能综合解决满足所有条件的最佳配送方案的方法正是人们所期望的。 （ 4）对于新的运输网络，只知道从各产地运往各销地及可经过的线路，这进修求最佳方案，需要求多个指标的最优方案。如各地之间的单位物资的费用（即单位运价）、最大流量、最优路线等（参见文献 3）。 因此 对于复杂的运输问题的优化，要根据具体情况，综合应用各种优化技术求其最优的调运方案。 2 运输问题模型 设某种物资有 m个产地，有 n个销地， ia 为第 i个产地的产量，

11、jb 为第 j个销地的销量，ijc 为从产地 i到销地 j的单位运价， 这些数据可汇总于产销平衡表和单位运价表中，见下表。 销地 产地 1, 2 , , n 产量 1 2 m A 1 A2 Am 销量 B1 B2 Bn 3 销地 产地 1， 2， .n 1， 2， . . . . m nccc 11211 .,., nccc 22221 .,., . . . mnmm ccc .,., 21 若用 ijx 为从产地 i到销地 j的调运数量， oxij ，其中 i=1， 2.， m； j=1,2, .n。问如何调运才能使得总运费最省 ? 在产销平衡的条件 nj jmi iba11下，其数学模型为

12、 injijminjijijaxtsxcZ 11 1.m in（ oxij ； i=1， 2.， m； j=1,2, .n） jmi ij bx 1由于产销不平衡运输问题可以通过添加虚拟的产地或销地而化为产销平衡运输问题，因此在这里仅研究平衡运输问题即可。 3 几种常用检验法的缺陷 近两年，物流已成为当今中国经济最热门名词之一 。 运输在整个物流中占有很重要的地位， 总成本占物流总成本的 35 -50左右，占商品价格的 4 -10。运输对物流总成本的节约具有举足轻重的作用。会计学上将物流成本分为显性成本和隐性成本 （参见文献4）。 在我国现行的物流运输方式中无论是自营物流，合营物流还是第三方物

13、流，隐性成本占据了很重要的地位，这些隐性成本在物流运输过程中主要包括以下几个方面：返程或起程空驶：空车无货载行驶，是不合理运输的最严重形式。在实际运输组织中，必须调运空车。4 但是，因调运不当货源计划不周，形成的空驶，是不合理运输的表现。造成空驶的不合理运输主要有以下几种原因：依靠自 备车送货提货，单程空驶的不合理运输。由于工作失误或计划不周，造成货源不实，由于车辆过分专用，无法搭运回程货物。 对流运输：在同一线路上或平行线路上作相对方向的运送，而与对方运程的部分发生重叠交错的运输称对流运输。 迂回运输：舍近取远的一种运输。不选取短距离进行运输，却选择路程较长路线进行运输的一种不合理形式。重复

14、运输：直接将货物运到目的地，在未达目的地之处，或目的地之外的其它场所将货卸下，再重复装运送达目的地，这是重复运输。另一种形式是，同品种货物在同一地点一面运进，同时又向外运出。过远运输： 是指调运物资舍近求远，近处有资源不调而从远处调，这就造成可采取近程运输而未采取，拉长了货物运距的浪费现象。 运力选择不当：在于火车及大型船舶起运及到达目的地的准备、装卸时间长，且机动灵活性不足，在过近距离中利用，发挥不了运速快的优势，延长运输时间。 因此，如何判别一个运输问题的调运方案是否最优至关重要。目前，通常采用闭回路法或位势法来判别，但这两种方法的计算量都非常大，而且都有其局限性。 3.1 闭回路法的缺陷

15、 所谓闭回路法，就是对于代表非基变量的空格（其调运量为零），把它的调运量调整为 1，由于产销平衡的要求 ,我们必须对这个空格的闭回路的顶点的调运量加上或减少 1。最后我们计算出由这些变化给整个运输方案的总运输费带来的变化。如果所有代表非基变量的空格的检验数也即非基变量的检验数都大于等于零，则已求得最优解，否则继续迭代找出最优解。 例如 在给出调运方案的计算表上，如下表，从每一空格出发找一条闭回路。它是以某空格为起点。用水平或垂直线向前划，当碰到一数字格时可以转 90后，继续前进，直到回到起始空格为止（参见文献 5）。 5 销地 加工厂 B1 B2 B3 B4 产量 A1 4 3 7 A2 3

16、1 4 A3 6 3 9 销量 3 6 5 6 任意空格（非基变量）对应的系数列向量可用其闭回路上所有角点出数字格（基变量）的系数列向量线性表示。如 ijP , i,j N可表示为： jmiij eeP jmuusmsmllkmkmi eeeeeeeeee )()()()()( jmusmusmlkmlkmi eeeeeeeeee ujuslslkik PPPPP 其中 BPPPPP ujusisikik , 。这些向量构成了闭回路。 闭回路法计算检验数的经济解释为：在已给出初始解的表中，可从任一空格出发，如( 1A ， 1B )。若让 1A 的产品调运 1吨给 1B 。为了保持产销平衡，就要依次作调整： 6 在 ( 1A ， 3B )处减少 1吨， ( 2A ， 3B )处增加 1吨， ( 2A ， 1B )处减少 1吨，即构成了以( 1A ， 1B )空格为起点，其他为数字格的闭回路。如表中的虚线所示。 销地 加工厂 B1 B2 B3 B4 产量 A1 4 3 7 A2 3 1 4 A3 6 3 9 销量 3 6 5 6 结合运价，可见这调整的方案使运费增加： (+1) 3+(1) 3+(+1) 2+(1)=1(元 ) 空格 闭回路 检验数