运输问题中表上作业法的算法及应用数学毕业论文.doc

洛阳师范学院毕业论文2013届 本科毕业论文运输问题中表上作业法的算法及应用院（系）名称数学科学学院专 业 名 称数学与应用数学学生姓名 学号指导教师 完 成 时 间2013.5运输问题中表上作业法的算法及应用摘要:表上作业法是运输问题的经典算法，本文详细讨论了产销平衡运输问题的表上作业法以及把产销不平衡问题化为产销平衡运输问题的方法，再此基础上结合实际生产建立了在有物资储存情况下的运输问题模型，并研究了集体比赛项目中参赛队员的出场次序问题.关键词：运输问题；表上作业法；位势法；出场次序引言 所谓运输问题,就是指从若干个产地往若干个销地运输某种物资,根据各产地的产量、各销地的销量和现有的交通网络,如何安排运输使总运费最少的问题 运输问题是特殊的线性规划，在运筹学中占有重要地位，运输问题不仅代表了物资合理调运、车辆合理调度等问题，有些其他类型的问题经过适当变换后也可以归结为运输问题，如指派问题、最短路问题、最小费用流问题可转化为运输问题或转运问题，对实际生产具有很大的指导意义.求解运输问题的基本方法是以单纯形法为基础的表上作业法,在本文中我们从运输问题的基本模型入手，介绍了用表上作业法解产销平衡和产销不平衡情况下运输问题的方法，并进一步论述了表上作业法的实际应用以及在不同情况下的改进与优化.1 运输问题的典型问题及经典模型 运输问题的一般描述是：已知有m个生产地可供应某种物资,它们的供应量为; 有n个销地需要这些物资, 需求量为；从到的单位物资的运价，即代表从第i个产地到第j个产地的单位物资运价.问如何安排运输, 可使总运费最小？上面这些数据通常用产销平衡表（见表1-1）和单位运价表（见表1-2） 产地地 地产地 销地12n产量12m销量表1-1产销平衡表表1-2单位运价表产地产地销地12.n 12m 1.1 产销平衡的运输问题 这是多个产地供应多个销地的单一物品运输问题,我们用表示从到的运量, 如果总产量等于总销量,即，则该运输问题为产销平衡运输问题，产销平衡问题一般模型如下所示： （模型一）其中约束条件右端常数和满足.1.2 产销不平衡的运输问题模型在实际生活中鉴于各种问题的复杂性和决策过程的不确定性,在实际生产和生活中,各销售地的需求量和各销售地的销售量往都是不平衡的，我们分两种情况来论述：1.2.1在产大于销即时，运输问题的数学模型可成: （模型二） 1.2.2在销大于产即时，运输问题模型可写成： （模型三） 在计算过程中产销不平衡模式可以转换成产销平衡模式进行解决，在实际生产过程中运输问题往往也复杂的多，具体解决方案以下详述.2 表上作业法求解运输问题分析实际问题列出产销平衡表及单位运价表确定初始方案（最小元素法）或（Vogel法）求检验数（闭回路法或位势法）所有检验数为非负得到最优方案找出绝对值最大的负检验数用闭回路调整，得出新方案2.1表上作业法的步骤如图 是 否2.1.1初始可行解的确定 常用的初始可行解的确定方法有3种:西北角法、最小元素法和Vogel法（最大差额法）通常情况下，用Vogel法确定的初始解质量最好，最接近最优解，最小元素法次之，西北角法最差常用Vogel法来确定初始可行解，步骤如下: (1)计算运输表中每一行和每一列次小单位运价和最小单位运价之间的差值，圈出其中的最大的差值; (2)若同时出现两个以上的最大差值，则圈出其所在行或所在列的最小运价为最小者的最大差值; (3)根据最大差值的位置在运输表中的适当格中填入一个尽可能大的运输量，并划去相应的一行或一列; (4)当运输问题某部分的产量和销量相等时，在运输表中相应空格处填入运量，需同时划去运输表的一行和一列，这时最终运输表上的数字格就会小于，规定只能划去一行(或一列)，在未被划去的一行或一列的某个空格中填入数字0； (5)重复以上步骤，从而得到一个初始可行解具体运算过程如下： 例1 有3 个产地、, 4 个销地、的产销平衡运输问题,见表2-1和表2-2.试用表上作业法求最优调运方案.表2-1单位运价表产地销地 311310192874105表2-2产销平衡表运价表产地销地产量（) 311310719284741059销量()3656 解 用法.从表2-1中每行与每列最小两个元素之差，分别列于表的右端和下端，见表2-4中两元素之差中标志的行和列.从表中可以看出列的差值最大，从该列找出最小元素为4，即生产的首先满足的需要，在表2-3中的交叉格填6.由于的需要已经得到满足，从单位运价表中划去这列数字，重复上述步骤，一直到产地的产量分配完、销地销量得到满足为止.表2-3 产地销地产量 527314639销量3656 表2-4 产地 销地 两最小元素之差 3 11 10 9 2 8 7 10 0 0 0 7 1 1 1 6 1 2两最小元素之差 2 5 1 3 2 1 3 2 1 2 1 2 2.2解的最优性检验 对初始可行解的最优性检验可仿照单纯形法，调运方案的检验通过检验数来完成,求可行解的各非基变量的检验数可以判断一个方案是否为最优方案.若有某空格的检验数为负（即），说明将作为基变量会使总运费减少，故当前解不是最优解，需要调整.若所有空格的检验数全部非负，该可行解就是最优解，所对应的调运方案为最优方案. 求检验数的常用方法有两种:位势法和闭回路法.其中利用位势法求检验数相对来说运算量比较小.根据线性规划的对偶规划矩阵描述，运输问题的检验数分别为，、分别为所在空格的单位运价及空格所在行的行位势（即第行位势）和所在列的列位势（即第列位势）.对于运输问题的y一个初始可行解，其基变量是、，得方程组 因为,此方程组有解，但由于对偶变量数比方程数多一个，解、（）不能唯一确定，为简化计算，可以任意指定某一位势等于一个较小的整数或零（注：的值无论先确定或，哪一个值都是一样的.） 若，则应该对方案进行调整和改善.我们依然用例1来说明.下表2-5是我用最小元素法确定的最初调运方案：表2-5产地销地产量 437314639销量3656下面我们用位势法来求检验数：第一步仿照2-5做一个表，不过将该表有数字的地方换上表2-1对应格的运价，如表2-6(下）所示：表2-6产地销地 3101245第二步是在表2-6的下面和右面增加一行和一列，并填上这样一些数字使表2-6中的各个数刚好等于它所在行和列的这些新填写的数字之和，见表2-7，通常用（）和（）来代表这些新填的数字，和分别称为第行和第列的位势.由于这些和是相互联系的，所以填写时可以先决定其中一个，然后推导其他的，如表2-7，先令,可得和如下表2-7：表2-7产地销地 3101120451829现在再看空格的检验数，令代表空格的检验数，是空格单位运价表的运价，由闭回路计算可知： 同理可算出任一空格的检验数见表2-8表2-8产地销地 1211012 在上表2-8中，的检验数为负，说明方案需要进一步改进，具体改进方案及方法在以下详述.2.3解的调整和改进 若经过最优性检验，可行解不是最优解，则需要进一步改进与调整.改进的方法主要是运用闭回路法，即在运输表中做出最小负检验数对应空格的闭回路，在满足约束条件的前提下，使尽可能增大并相应调整闭回路上其他顶点处的运量，得到一个更好的可行解.解调整改进的步骤如下： (1) 在运输表中做出最小负检验数对应空格的闭回路; (2)以空格 为初始点，沿顺时针方向依次对闭回路上的顶点进行编号;(3)在闭回路上的所有偶数顶点格子中所填写的运量里，找出最小运量； (4)以为调整量，将闭回路上所有奇数顶点处的运量增加，所有偶数顶点处的运量减去，从而得到一个新的可行解; (5)对得到的新可行解进行最优性检验，如不是最优解，重复以上步骤进行调整和改进,直到得出最优解为止.我们依然用上面的例子，表2-5为最初调运方案，在上面我们得到了检验数如表2-8所示，其改进方法是从出发，做一条除该空格外其余顶点均为由数字格组成的闭回路，在这条闭回路上按照上述方法进行最大可能的调整，从表2-9中可以看出为了把产品调运给，就要相应减少调运给的量和运给的量，才能得到平衡.在这个表格中最小运量为一，因此至多只能调运1给,由此得到一个新的调运方案，见表2-10，这个新方案运费是85元.表2-9产地销地产量 4（+1） 3（）73 1（） （+1）4639销量3656表2-10产地销地产量 527314639销量3656接下来按照上述方法重复直到检验数全大于0为止.3 产销不平衡运输问题的算法在运输生产及管理过程中，有各种不可估计的变量，故对其中的不平衡运输问题改建成平衡运输问题数学模型的可行性以及表上作业法的普遍适用性进行探讨，具有一定的实际意义.我们分产大于销和销大于产两种情况来分别进行向产销平衡模式的转化：3.1 产大于销时，其模型如模型2（见第4页)所示： 下面将此不平衡问题改建成平衡的数学模型. 由于总的产量大于销量，就要考虑多余的物资在那个产地就地库存的问题.我们假想一个销地，把多余的物资贮存在该地，则其“需求”为： 设从“运往”的运量设为，则有： 故模型2中不等式的约束条件可以改为： 增加一个方程，即第个方程为：3.1.1 不考虑就地储存费用.从各个产地到到假想销地（实际上是库存）的运输单价为：，多余的物资就地贮存故运费为0. 从而模型2可优化为： s.t. ，其中； （模型4） 因此，此模型中，这样就把模型2转化成了平衡模式如模型4所示.3.1.2 当考虑物资就地储存费用时，我们分两种情况考虑：(1)各个产地单位物资存贮费用相同为常数 建立目标是总运输费与存贮费之和最少的数学模型，即： 其中；（模型5） 其中（即),是第个产地就地储存的物资数量.此模型为平衡模型的数学问题，可以用表上作业法求解.（2）各个产地单位物资贮费不同设第个产地的单位物资贮费为，总运费与贮存费用之和的数学模型为：s.t. 其中；（模型6） 其中（即），是第个产地的贮存物资数量.模型6也为平衡问题的数学模型，用表上作业法求解即可 3.2销大于产时 类似的，就可以在产销平衡表里增加一个假想的产地，该地产量为，在单位运价表上令从该假想的产地到各销地的运价，同样可以转化成一个产销平衡的运输问题，然后用表上作业法求解，此处不再赘述. 4 运输问题的应用 运输问题并不仅仅限于物品的空间转移，凡是其数学模型符合运输问题特点的运筹学问题，都可以采用运输问题特有方法加以解决.在实际生产过程中许多问题都可以转化为运输问题来解决.4.1 集体比赛项目中的应用（指派问题）在体育比赛中, 经常出现一些集体项目的比赛, 集体项目的比赛有两种比赛规则。其一由举办者利用抽签来确定各队参赛队员的比赛次序; 其二由参赛队己来确定参赛队员的比赛次序。对于其一, 显然没有研究的必要, 而对其二我们利用运筹学中的表上作业法进行科学排序, 从而使参赛队取得最优成绩。集体比赛项目的标准形式: 设有n 个队员参加有次序同一种比赛(如接力赛跑等), 要求每一次序只能由一个队员参加比赛, 每个队员只允许参加一次比赛。第个队员参加第次序比赛所需时间为，其时间矩阵为 ，再设决策变量： 我们可建立模型为 s.t. 显然，这说明约束方程组的系数矩阵的秩与增广矩阵的秩相等, 都为.满足运输问题产销平衡模型，可以用表上作业法求解.4.2.1 实例求解 例 2 设有甲、乙、丙、丁四个队员参加接力赛跑，根据四位运动员的综合素质（心理、体力、技术、场地等),所跑不同棒次所用时间（单位为）如下表4-1所示,请给出各队员所跑棒次的科学排序.不同棒次时间表4-1队员棒次1234人数甲1010.0110.01101乙10.0110.0110.0110.011丙10.0110.0110.0110.021丁1010.0110.0110.011棒数1111 显然，每一次序只能由一个队员参加比赛, 每个队员只允许参加一次比赛.我们在表4-1上列出棒数与人数两项，这就构成了一个棒数与人数的平衡表如表4-1所示.(1） 用法给出初始方案如表4-2表4-2队员棒次1234甲01乙 1 丙1丁1000（2） 用位势法求出其检验数如表4-3所示表4-3队员棒次1234甲000乙0.1 00.010丙000.020丁01010.0110.0110 表中检验数全为非负数，故该方案即为最优方案.即最科学的安排方式为:队员甲：第4棒；队员乙：第2棒；队员丙:第3棒；队员丁：第1棒；最少时间（） 注 从上述实例可以看出运筹学为教练员合理安排队员比赛次序提供了科学的决策方法.生活中类似的分配指派问题都可以转化为运输问题解决.4.2生产与储存问题(最小费用流问题) 例 3 某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机.已知该厂各季度的生产能力及生产每台柴油机的成本如下表4-4.如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元.试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案.表4-4季度 生产生产能力(台)单位成本（万元） 一季度2510.8二季度3511.1三季度3011.0四季度1011.3 问题分析：由于一二三季度的生产能力分别大于需要提供的柴油机台数，所以第一二三季度剩余的柴油机可提供给下一季度.如果设为第季度生产的在第季度交货的柴油机台数，分析题目内容可知应满足以下条件：1、 在交货时应满足的条件为: 2、 在生产时应满足的条件为: 模型建立：分析可知该条件满足产大于销的模型条件把第季度生产的柴油机数目看作第 个生产厂的产量；把第季度交货的柴油机数目看作第个销售点的销量；设表示第季度生产的用于第季度交货的每台柴油机的实际成本，其值如下表：产量销量表4-5 1234110.810.9511.1011.25211.1011.2511.4031111.15411.30 显然，这是一个产大于销的运输问题，注意到这个问题中当时，所以令对应的，再加上一个假想的需求地，就可以把这个问题转化成产销平衡的运输问题，因此可构造下列产销平衡问题： 目标函数： 产销平衡表4-4季度IIIIIIIV产量I10.8010.9511.1011.20025II11.1011.2511.40035III11.0011.15030IV11.30010销量1015252030用表上作业法求解，可得多个最优方案，表4-5中列出最优方案之一.即第I季度生产25台，10台当季交货，15台II季度交货；II季度生产5台，用于III季度交货；III季度生产30台，其中20台于当季交货，10台于IV季度交货.IV季度生产10台，于当季交货.按此方案生产，该厂总的生产(包括储存、维护)的费用为773万元.表4-5季度IIIIIIIV产量I1015025II 51035III201030IV1010销量1015252030注：运输问题在生活中的应用非常广泛.如土地分配，产品调配，运输路线、转运问题等，此处不再赘述.结束语运输问题是运筹学的经典问题,已经有60多年的历史, 作为其重要算法的表上作业法被广为使用，对于产大于销运输问题或销大于产的问题既考虑运输费用, 又考虑剩余物资就地存贮费,目标是总运费与总剩余物资就地存贮费用二者之和最小,可以建立与模型、模型类似的模型，当然也可以用表上作业法求解.在实际生产过程中的运输问题往往比我们分析到的要复杂的多，有多种不确定性，这就需要我们仔细分析各种变量，建立最合理的的运输问题模型，然后与其他方法配合解决.参考文献 1胡运全等.运筹学基础及应用第五版第三章运输问题.北京-高等教育出版社：83-105.2张永良，卢厚清. 运输问题模型与解法J. 指挥技术学院学报，1999，（5）：99- 100.3谢凡荣. 产销平衡运输问题的表上作业法解法的一个注J记. 运筹与管理, 2005, 14(4): 44-46.4陈宝林, 何坚勇. 运输问题的表上作业法的一个解释J. 清华大学学报: 自然科学版 , 1998, 38 (12): 40-43.5何莉敏,李玉,于涛,等.法求解最大值问题J郑州大学学报: 理学版， 2011,43(1):43( 1) :