运输问题综述.doc

运输问题摘要：本文讨论一类特殊的线性规划问题——运输问题，并将详细地介绍运输问题的模型、具体的求解方法，包括表上作业法、最小费用流方法，并举例说明具体应用关键词：运输问题；表上作业；最小费用流0 引言运输问题是社会经济生活和军事活动中经常出现的优化问题在经济建设和国防建设中经常遇到煤炭、钢铁、木材、粮食、武器装备等物资的调运问题[1]如何制定调运方案，将物资运往指定地点，而且实现运输成本最小，记为运输问题具体来说，这类问题要解决的就是把某种产品从若干个产地调运到若干个销地在每个产地的供应量和每个销地的需求量为已知的前提下，如何在多种可行的方案中，确定一个使总运输费用或运量最少的方案运输问题又称为希奇柯克问题或康脱洛维奇问题，与一般线性规划问题不同，它的约束方程组的系数矩阵具有特殊的结构，根据它的特点可以找到比单纯形法更为简洁的解法下文将具体介绍运输问题的模型、算法、应用1 运输问题的模型运输问题：设某种物资有个产地供应量分别为个单位联合供应个销地需求量分别为个单位又假设从产地 向销地运输一个单位的费用，即单位运价（或计价距离）是已知的，应怎样调运物资才能使运输费用最少？模型建立：设从产地到销地的运输量为个单位。

先考虑这个问题的数学模型的约束条件，由调出的物资总量等于的供应量所以应满足同样，运到的物资总量应等于的需求量所以应满足总的运费应该为因此，所要解决的问题的数学模型为 （4.1）该模型包含个变量，个约束方程，其系数矩阵为显然，上述物资调运问题是一个特殊的线性规划问题另外还有许多问题如生产规划问题都可以归结为上述形式故把凡是具有形如式（4.1）的线性规划问题都叫做运输问题，把产地（供应地）等统称为发点或源，而销地（需求地）统称为收点或汇其中，当满足条件：时，称该运输问题是平衡的，否则称该运输问题是不平衡的2表上作业法表上作业法是一种迭代算法[2]：先按照某种规则找出一个初始解；再对初始解作最优性判别；若该解不是最优解，就在运输表上对它进行调整改进，从而得出一个新解，再进行判断改进，直到迭代出运输问题的最优解为止简而言之，表上作业法一般分为两个阶段：第一阶段制定初始调运方案；第二阶段从初始调运方案出发，调整调运方案，逐步获得最优解在进行表上作业时，首先要了解产销运输表对于一般的运输问题的数学模型，将各种参数以及变量排列在一张表上，即为产销运输表，如表1：表1 产销运输表2.1制定初始调运方案在运输问题约束方程组的系数矩阵中，如果含有单位矩阵，就很容易找到初始基本可行解；否则就要引入人工变量，用大法或两阶段法求初始基本可行解。

但由于运输问题数学模型的特殊性，可以不必引入人工变量而是利用一些特殊的方法直接求出运输问题的基本可行方案下面介绍三种常用的求运输问题初始基本可行解的方法2.1.1产销平衡问题1.左上角法（西北角法）通过例题来讲解左上角法及其计算过程例1 设有三个产地的产品需要运往四个销地，各产地的产量、各销地的销量及各销地的单位运费如表2所示，问如何调运使总的运费最省？由表2可知即产销平衡问题，采用左上角法进行求解，步骤如下：表2 产销运输表第1步：作产销空格表，将空格对应的产销地运费填在空格的右上角第2步：在表中首先对左上角的格进行分配，将它所对应的产地产量与销地销量进行比较：（1）如果产大于销，则在这个方格中填上销量，并在表中划去这一列或在该列的空格处打 ；（2）如果销大于产，则在这个方格中填上产量，并在表中划去这一行或在该行的空格处打 ；（3）如果产销相等，则在这个方格中填上产量（销量），并在表中划去相应的行（或列），但不能行列都划去第3步：在剩下的表中，反复进行第2步，直至每个方格都被划过或全部方格都赋值为止，这里要注意被划过的表中产量与销量的变化下面给出具体计算过程先对左上角进行分配，即划去第1列，此时产地的产量改为。

再对进行分配，，划去第1行，此时的产量改为依次类推，具体结果如表3所示，表中的箭头是指填写数字的顺序表3 初始调运方案上表给出了该问题的初始调运方案，基本可行解为 其初始调运方案的运费为 2.最小元素法通过例题来讲解最小元素法和计算过程例2 用最小元素法求解例1问题的运费最少的调度方案，其产销运输表如表二所示解：用最小元素法确定初始调运方案的具体步骤如下第1步：作产销空格表，将空格对应的产销地运费填在空格的右上角第2步：在表中找出运价最小的一格，将它所对应的产地产量与销地销量进行比较：（1）如果产大于销，则在这个方格中填上销量，并在表中划去这一列；（2）如果销大于产，则在这个方格中填上产量，并在表中划去这一行；（3）如果产销相等，则在这个方格中填上产量（销量），并在表中划去相应的行（或列），但不能行列都划去第3步：在剩下的表中，反复进行第2步，直至每个方格都被划过，这里要注意被划过的表中产量与销量的变化下面给出具体计算过程在表二中可以看到，运价最小，的需求为3个单位，的产量为4个单位产大于销，在处填上销量3，再划去这一列再检查运价，其中最小，需求为5个单位，而只剩1个单位，所以此处填上1。

又因为销大于产，故划去这一行继续检查，找出最小运费运费最小为 共需5个单位，而已提供1个单位，故还需4个单位产量为7个单位，产大于销，则填上4后划去这一列依次类推，具体结果如表4所示表4 用最小元素法求出的初始调运方案表4给出的就是一种调运方案，即初始基本可行解为 其总运费为 3.差额法（VAM法）元素差额法是在最小元素法的基础上改进的一种求初始方案的方法，在分配运量确定产销关系时，不从最小元素格开始，而是通过运输表中各行各列的最小元素和次小元素之差额来确定产销关系用元素差额法确定初始调运方案具体步骤如下第1步：作产销空格表，将空格对应的产销地运费填在空格的右上角第2步：产销空格表增加一列和一行作为差额行和差额列，在差额行和差额列的每格上填上对应行和对应列的最小元素和次小元素之差额第3步：在差额行和差额列的所有元素中，选取差额最大的一行或一列进行分配，并对该行（或列）的最小元素的格填数，填数规则同最小元素法若有几个相同的最大差额的行和列，则可任取一行或一列进行分配第4步：重新计算差额并进行分配具体步骤同第2步和第3步，直到每一个格都被填上数或画为止在重新计算差额时，要注意一下两个问题：（1）已分配完的行或列不再重新计算差额；（2）在重新计算时，不再考虑已分配的位置和画位置的运费，在剩下的格中计算差额。

例3 用元素差额法求解例1的初始调运方案，具体计算过程如下由表的第一行可以看出，最小元素为3，次小元素为10，故差额为7，在行的右边填上差额7又从表的第1列看出，最小元素与次小元素的差额为3-1=2，在列的下边填上差额2用同样的方法可以求出其他各行和各列的差额，如表5所示表5 用元素差额法确定初始调运方案在表中的差额（7,1,1），（2,5,1,3）中，最大者是7，它出现在行，所以先分配给行在这一行中，最小运费是3它坐在的列是第1列，根据最小元素法知，并在第1列打然后类似步骤依次往下计算，直到每个格都被赋值或打，所得结果如表五由表给出该问题的最优解其最优值为 上文对例1利用了三种方法计算，比较而知，不同的方法得到不同的初始调运方案，且元素差额法所得的方案较优，那么这个方案是否是最优呢？一般情况下不一定，需要经过判断，才能确定是否为最优2.1.2产销不平衡问题以上讲的是产销平衡问题，而且假定了每个产地到每个销地都有路可行，即任何产地的产品都可以运往任何一个销地将表上作业法做一些推广，使之能够处理不满足这些条件的问题在已给出运输问题的模型中，当时，该问题称为产销不平衡问题产销不平衡问题有产量大于销量和销量大于产量两种情况，下面分别进行讨论。

1.产量大于销量的不平衡问题对于产量大于销量的运输问题有处理方法与前面大体相同，只不过在制定初始调运方案时，应首先考虑需求，最后哪一个产地还有多余部分，就在哪一个产地库存具体做法是：在表上加进一列“库存”，库存量就是产量与销量的差额部分，它的运费为0，然后如前面一样处理但需注意在制定初始调运方案时，最小的单位运价应以实际最小价格为准，最后再考虑库存这一列例4 水泥调运的产销不平衡情况及运价如表6所示，求最佳的调运方案表6 产销运输表解：这个问题的发量总数为19，而收量总数为15，故此问题是产量大于销量的情况因此增加库存这一列，其相应的运价为0，则初始调运方案制定如表7所示表7 初始调运方案在制定初始方案时，库存一列零运价暂不考虑，在原来给定的运价上逐次选取最小运价，分配完后再考虑库存由上表7可得出初始的调运方案2. 销量大于产量的不平衡问题与产量大于销量的解题思路相同，只不过是假设有一个虚产地，产量就是差额部分，从虚产地到各个销地的运费为0，在制定初始调运方案时，应首先由真实产地按最小单位运价调往销地，最后的差额部分再由虚产地供给，步骤如前面一样3．没有线路的情况有时某产地到销地没有运输路线，这时可认为该产地到这个销地非常大，只要在表中将这个运费取得充分大，就能保证在求出的最优方案中这两地的运量为0，其余步骤如前所示。

2.2 最优调运方案的判断方法 判断一个方案是否最优，实质是判断一个基本可行解是否为最优解在单纯形法中是根据对应于非基变量的检验数来判断的表上作业法也是类似的判断初始调运方案表的空格表示调运量为0，它对应于非基变量，因此要判定这个调运方案是否最优，就必须求出各个空格的检验数主要介绍两种方法：闭回路法和位势法1.闭回路法由一个空格开始，沿水平方向或垂直方向前进，遇到一个适当的有数字的格子时，则按与前进方向垂直的方向转向前进，这样会再遇到一个适当的有数字的空格，再转向前进依次进行，直到回到原来出发的空格，形成闭回路填有数字并使方向前进改变的格子称为拐角例5 求表4的一个闭回路从空格出发，向前进，这里有数字6，再沿水平方向前进，依次进行，具体结果如表8表8 为起点和终点的闭回路检验数的求法：从空格开始沿闭回路前进，将空格相应的单位运费去正号，第一个转角格的单位运费取负号，第二个又取正号，依次正负相间的做下去，然后将这些运费加起来即为空格的检验数如上例，的检验数为9-4+5-10+3-2=1，同样方法可求出其它空格的检验数，但此方法比较麻烦2.位势法第一步：先建一张表，在这张表中的数字就是初始调运方案相应的单位运价和运量，如表9。

表9 求出位势值的初始调运方案第二步：在表中增加一行和一列，使表中各基变量的单位运价正好等于它所在的列和行的与之和第三步：计算各空格的检验数，求任一空格检验数的公式为 先把的值求出来放在每个格的左下角，把求得的检验数填在每个格的左上角结果如上表9求出检验数后，就可以判断这个调运方案是否为最优了由于这里所求的目标函数是极小化问题，且由运输问题的模型可知其对偶模型为 故有即所有的检验数都为非负时，这个调运方案就是最优的调运方案由此知，本例中的检验数有负数-1，故它不是最优的调运方案，需要调整2.3 调整已有的调运方案调整已有的调运方案，就是根据一个初始方案求出另一个较好的方案实质上就是根据一个基本可行解找出另一个基本可行解，使目标函数值下降其思想是，选出具有最小负值的检验数的空格。