第三章运输问题课件.ppt

《第三章运输问题课件.ppt》由会员分享，可在线阅读，更多相关《第三章运输问题课件.ppt（102页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运运 筹筹 学学“运筹学运筹学”课题组课题组本章内容重点本章内容重点 3.1 运输问题的数学模型运输问题的数学模型3.2 表上作业法表上作业法3.3 产销不平衡的运输问题及其求解方法产销不平衡的运输问题及其求解方法3.4 单纯形算法的进一步讨论单纯形算法的进一步讨论3.5 应用举例应用举例第三章第三章 运输问题运输问题第三章第三章 运输问题运输问题 前面讨论了一般线性规划问题的前面讨论了一般线性规划问题的数学模型的建立和求解的方法，但在数学模型的建立和求解的方法，但在实际工作中，往往碰到有些线性规划实际工作中，往往碰到有些线性规划问题，它们的约束条件的系数矩阵具问题，它们的约束条件的系数矩阵具

2、有特殊的结构，这就使我们有可能找有特殊的结构，这就使我们有可能找到比单纯形法更为简单的求解方法，到比单纯形法更为简单的求解方法，从而节约大量的计算时间和费用。本从而节约大量的计算时间和费用。本章所讨论的运输问题就是属于这样一章所讨论的运输问题就是属于这样一类特殊的线性规划问题，它在实践中类特殊的线性规划问题，它在实践中具有重要的作用，具有广泛的应用。具有重要的作用，具有广泛的应用。3.1、运输问题的数学模型、运输问题的数学模型 在经济建设中，经常会遇到大宗在经济建设中，经常会遇到大宗物资调拨中的运输问题。如煤炭、钢物资调拨中的运输问题。如煤炭、钢铁、木材、粮食等物资铁、木材、粮食等物资,在全国

3、有若在全国有若干生产基地，根据已有的交通网，应干生产基地，根据已有的交通网，应如何制定调运方案，将这些物资运到如何制定调运方案，将这些物资运到各消费地点，而使总运费最小。这类各消费地点，而使总运费最小。这类问题可用以下数学语言来描述：问题可用以下数学语言来描述：n运输问题：假设有运输问题：假设有m m个生产地点，可个生产地点，可以供应某种物资以供应某种物资(以后称为产地以后称为产地)，用用A Ai i表示，表示，i i=1,2,=1,2,m m；有；有n n个个销售地，用销售地，用B Bj j表示，表示，j j=1,2,=1,2,n n；产地的产量和销售地的销售量分；产地的产量和销售地的销售量

4、分别为别为a ai i,i i=1,2,=1,2,m m和和b bj j，j j=1,2,=1,2,n n，从，从A Ai i到到B Bj j运输单位运输单位物资的运价为物资的运价为c cijij，这些数据可汇总，这些数据可汇总于如表于如表3.13.1。表表3.13.1 销地销地产地产地B1B2Bn产量产量A1c11c12c1na1A2c21c22c2na2Amcm1cm2cmnam销量销量b1b2bn要求使总运费最小的调运方案。要求使总运费最小的调运方案。如果运输问题的总产量等于其总销量，如果运输问题的总产量等于其总销量，即即 则称该运输问题为产销平衡运输问则称该运输问题为产销平衡运输问题；

5、反之，称为产销不平衡运输问题。题；反之，称为产销不平衡运输问题。下面建立在产销平衡情况下的运输下面建立在产销平衡情况下的运输问题的数学模型。问题的数学模型。解解:假设假设 xij 表示从表示从Ai到到 Bj 的运量的运量,则所则所求的数学模型为求的数学模型为:在该模型中，目标函数表示运输总费用，在该模型中，目标函数表示运输总费用，要求其极小化；要求其极小化；第一个约束条件的意义是由各产地运往某第一个约束条件的意义是由各产地运往某一销地的物品数量之和等于该销地的销量；一销地的物品数量之和等于该销地的销量；第二个约束条件表示由某一产地运往销地第二个约束条件表示由某一产地运往销地的物品数量之和等于该

6、产地的产量；的物品数量之和等于该产地的产量；第三个约束条件表示变量的非负条件。第三个约束条件表示变量的非负条件。对于产销不平衡的情况，我们将对于产销不平衡的情况，我们将另行处理。另行处理。这就是运输问题的数学模型，它这就是运输问题的数学模型，它包含包含m m n n个变量，个变量，m+nm+n个约束条件，个约束条件，是一个线性规划问题。是一个线性规划问题。如果用单纯形法求解，首先应在每个约如果用单纯形法求解，首先应在每个约束条件上加入一个人工变量束条件上加入一个人工变量(以便求出初始以便求出初始基可行解基可行解)。因此，即使是因此，即使是m m=4=4，n n=5=5这样的简单这样的简单问题问

7、题,变量个数就有变量个数就有2929个之多，利用单纯形个之多，利用单纯形法进行计算是非常复杂的。法进行计算是非常复杂的。因此，我们有必要针对运输问题的某些因此，我们有必要针对运输问题的某些特点，来寻求更为简单方便的求解方法。特点，来寻求更为简单方便的求解方法。3.23.2、表上作业法、表上作业法1 1、表上作业法的基本概念与重要结论：、表上作业法的基本概念与重要结论：针对运输问题的数学模型结构的特殊针对运输问题的数学模型结构的特殊性，它的约束方程组的系数矩阵具有如下特性，它的约束方程组的系数矩阵具有如下特点：点：（1 1）在该矩阵中，它的元素等于）在该矩阵中，它的元素等于0 0或或1 1（2

8、2）每列只有两个元素为）每列只有两个元素为1 1，其余都是，其余都是0 0；n（3 3）对应于每一个变量，在前）对应于每一个变量，在前m m个个约束方程中只出现一次，在后约束方程中只出现一次，在后n n个约个约束方程中也只出现一次。根据这个束方程中也只出现一次。根据这个特点，在单纯形法的基础上，下面特点，在单纯形法的基础上，下面设计出一种专门用来求解运输问题设计出一种专门用来求解运输问题的方法，这种方法我们称为的方法，这种方法我们称为表上作表上作业法。业法。根据运输问题的数学模型求出的运输问根据运输问题的数学模型求出的运输问题的解，它代表着一个运输方案，其中每一题的解，它代表着一个运输方案，其

9、中每一个变量个变量xij的值表示由的值表示由Ai调运数量为调运数量为xij的物品的物品给给Bj。由于运输问题也是一个线性规划问题，由于运输问题也是一个线性规划问题，当用单纯形法进行求解时，我们首先应当知当用单纯形法进行求解时，我们首先应当知道它的基变量的个数；道它的基变量的个数；其次，要知道这样一组基变量应当是由其次，要知道这样一组基变量应当是由哪些变量来组成。哪些变量来组成。n运输问题的解运输问题的解X X必须要满足模型中的所有必须要满足模型中的所有约束条件；约束条件；n基变量对应的约束方程组的系数列向量必基变量对应的约束方程组的系数列向量必须是线性无关的；须是线性无关的；n解中基变量应由解

10、中基变量应由 m+n-m+n-1 1个变量组成个变量组成(即基即基变量的个数变量的个数 =产地个数产地个数 +销售地个数销售地个数 1)1)，原因是在运输问题中虽然有，原因是在运输问题中虽然有m+nm+n个个约束条件，但由于总产量等于总销量，故约束条件，但由于总产量等于总销量，故只有只有m+n-m+n-1 1个约束条件是线性独立的。个约束条件是线性独立的。n进一步我们想知道，怎样的进一步我们想知道，怎样的 m+n-m+n-1 1个变量个变量会构成一组基变量？会构成一组基变量？为此我们需要引入一些基本概念，通过对这为此我们需要引入一些基本概念，通过对这些基本概念的分析和讨论，结合单纯形算法些基本

11、概念的分析和讨论，结合单纯形算法的基本结果，便可得出我们所需要的结论。的基本结果，便可得出我们所需要的结论。凡是能排成凡是能排成 互不相同，且互不相同，且 形成的变量的集合称之为一个闭回路。而把形成的变量的集合称之为一个闭回路。而把出现在闭回路中的变量称为这个闭回路的顶出现在闭回路中的变量称为这个闭回路的顶点。点。x11、x12、x32、x34、x24、x21 构成一个构成一个闭回路。这里有：闭回路。这里有：i1=1，i2=3，i3=2；j1=1，j2=2，j3=4。若把闭回路的顶点在表中画出，并且把相若把闭回路的顶点在表中画出，并且把相邻两个变量用一条直线相连（今后就称这些邻两个变量用一条直

12、线相连（今后就称这些直线为闭回路的边）。直线为闭回路的边）。例例3.1 设设 m=3，n=4，如表，如表3.2所示所示 销地销地产地产地B1B2B3B4A1x11x12A2x21x24A3x32x34n而表而表3.33.3，即顶点为，即顶点为 x x1212、x x3232、x x3434、x x1414 和表和表3.43.4，即顶点为，即顶点为 x x1111、x x1212、x x2222、x x2424、x x3434、x x3131 也分别构成两个闭回路。也分别构成两个闭回路。表表3.33.3 销地销地产地产地B1B2B3B4A1x12x14A2A3x32x34 销地销地产地产地B1B

13、2B3B4A1x11x12A2x22x24A3x31x34表表3.4n从上面的例子中不难看出，如果把一个闭从上面的例子中不难看出，如果把一个闭回路的所有顶点都在表中画出，并且把相回路的所有顶点都在表中画出，并且把相邻的顶点都用一条直线连接起来，就可以邻的顶点都用一条直线连接起来，就可以得到一条封闭的折线，折线的每一条边或得到一条封闭的折线，折线的每一条边或者是水平的，或者是垂直的。者是水平的，或者是垂直的。定理定理3.1：m+n-1个变量个变量 构成基变量的充分必要条件是它不包构成基变量的充分必要条件是它不包含有任何闭回路。含有任何闭回路。n 该定理给出了运输问题基的一个重要特征，该定理给出了

14、运输问题基的一个重要特征，这个结论是非常重要的，因为利用它可以这个结论是非常重要的，因为利用它可以判断判断 m+n-m+n-1 1个变量是否构成基变量，它比个变量是否构成基变量，它比直接判断这些变量所对应的系数列向量组直接判断这些变量所对应的系数列向量组是否线性无关要简单和直观。另外，在以是否线性无关要简单和直观。另外，在以后还将看到利用基的这个特征可以导出求后还将看到利用基的这个特征可以导出求运输问题的基本可行解的一种简便的方法。运输问题的基本可行解的一种简便的方法。2、表上作业法表上作业法 表上作业法是单纯形法在求解运输问题表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形

15、算法。时的一种简化方法，其实质是单纯形算法。只是具体计算和术语有所不同，可归纳为：只是具体计算和术语有所不同，可归纳为：（1 1）找出初始基可行解，即在）找出初始基可行解，即在 (m m n n)产产销平衡表上给出销平衡表上给出m+n-m+n-1 1个有数字的格，这些个有数字的格，这些有数字的格不能构成闭回路，且行和等于产有数字的格不能构成闭回路，且行和等于产量，列和等于销售量；量，列和等于销售量；n(2 2）求各非基变量的检验数，即在表上求）求各非基变量的检验数，即在表上求出空格的检验数，判别是否达到最优解。出空格的检验数，判别是否达到最优解。如果达到最优解，则停止计算，否则转入如果达到最优

16、解，则停止计算，否则转入下一步；下一步；（3 3）确定换入变量和换出变量，找出新的）确定换入变量和换出变量，找出新的基可行解，在表上用闭回路法进行调整。基可行解，在表上用闭回路法进行调整。（4 4）重复（）重复（2 2）、（）、（3 3）步，直到求（得最）步，直到求（得最优解为止。以下我们就具体给出求解运输优解为止。以下我们就具体给出求解运输问题表上作业法的计算步骤。问题表上作业法的计算步骤。（1 1）、）、确定初始基可行解确定初始基可行解确定初始基可行解即首先给出初始的调运方确定初始基可行解即首先给出初始的调运方案，方法很多，我们只介绍其中的两种方法：案，方法很多，我们只介绍其中的两种方法：

17、方法一：最小元素法：方法一：最小元素法：最小元素法的基本思想就是就近供应。即从最小元素法的基本思想就是就近供应。即从单位运价表中最小的运价开始确定产销关系，单位运价表中最小的运价开始确定产销关系，依次类推，直到给出初始方案为止。下面由依次类推，直到给出初始方案为止。下面由例题来说明最小元素法确定初始基可行解的例题来说明最小元素法确定初始基可行解的具体步骤。具体步骤。n例例3.23.2：某公司有：某公司有3 3个生产同类产品的工个生产同类产品的工厂，生产的产品由厂，生产的产品由4 4个销售点销售，各个销售点销售，各工厂的生产量、各销售点的销售量以及工厂的生产量、各销售点的销售量以及各工厂到各销售

18、点的单位产品运价如表各工厂到各销售点的单位产品运价如表3.53.5所示。问该公司应如何调运产品，所示。问该公司应如何调运产品，在满足各销售点的需要量的前提下，使在满足各销售点的需要量的前提下，使总的运费为最小。总的运费为最小。表表3.53.5 销地销地产地产地B1B2B3B4产量产量A13113107A219284A3741059销量销量3656解：解：第一步：第一步：从单位运价表中找出最小运价从单位运价表中找出最小运价为为1 1，这表示先将，这表示先将 A A2 2 的产品供应给的产品供应给 B B1 1 。由于由于A A2 2 每天生产每天生产4 4吨，吨，B B1 1 每天只需要每天只需

19、要 3 3吨，吨，即即 A A2 2 除每日能满足除每日能满足B B1 1 的需要外还余的需要外还余1 1吨。吨。n因此在产销平衡表因此在产销平衡表 (A A2 2,B B1 1)交叉处填上交叉处填上3 3，表示，表示 A A2 2 调运调运3 3吨给吨给B B1 1，再在单位运价，再在单位运价表中将表中将B B1 1 这一列运价划去，表示这一列运价划去，表示 B B1 1 的需的需求已满足，不需要继续调运求已满足，不需要继续调运 (即即x x21 21=3=min(=3=min(a a2,2,b b1)=min(4,3)1)=min(4,3)。n第二步第二步:从上述未划去的单位运价表的元从上

20、述未划去的单位运价表的元素中找出最小的运价素中找出最小的运价2 2，即，即A A2 2 把剩余的把剩余的产品供应给产品供应给B B3 3 ；B B3 3 每天需要每天需要5 5 吨，吨，A A2 2 只只剩余剩余 1 1 吨，因此在上述产销平衡表的吨，因此在上述产销平衡表的 (A A2 2,B B3 3)交叉处填上交叉处填上 1 1，划去上述运价，划去上述运价表中表中A A2 2 这一行运价，表示这一行运价，表示 A A2 2的产品已分的产品已分配完毕。配完毕。销地销地产地产地B1B2B3B4产量产量A13113107A219284A3741059销量销量3656表表3.63.6n第三步第三步

21、:从上述第二步所得的单位运价表从上述第二步所得的单位运价表未划去的元素中找出最小元素为未划去的元素中找出最小元素为 3 3。这表。这表示将示将 A A1 1 的产品供应的产品供应 B B3 3 ，A A1 1 每天生产每天生产7 7 吨，吨，B B3 3 尚缺尚缺 4 4 吨，因此在产销平衡表的吨，因此在产销平衡表的(A A1 1,B B3 3)交叉处填上交叉处填上 4 4，由于，由于B B3 3 的需求的需求已满足，将单位运价表中的已满足，将单位运价表中的 B B3 3 这一列运这一列运价划去。价划去。销地销地产地产地B1B2B3B4产量产量A1437A2314A3639销量销量3656n如

22、此，一步步进行下去，直到单位运价表如此，一步步进行下去，直到单位运价表中所有元素都划去为止，最终在产销平衡中所有元素都划去为止，最终在产销平衡表上就可以得到一个初始调运方案。这个表上就可以得到一个初始调运方案。这个方案的总运费为方案的总运费为 86 86 元，如表元，如表3.73.7所示。所示。表表3.73.7 应当注意的是，在用最小元素法确定初应当注意的是，在用最小元素法确定初始基可行解的时候，有可能出现以下的两种始基可行解的时候，有可能出现以下的两种特殊情况：特殊情况：一是当在中间步骤的未划去的单位运价一是当在中间步骤的未划去的单位运价表中寻找最小元素时，有多个元素同时达到表中寻找最小元素

23、时，有多个元素同时达到最小，这时从这些最小元素中任意选择一个最小，这时从这些最小元素中任意选择一个作为基变量；作为基变量；二是当在中间步骤的未划去的单位运价二是当在中间步骤的未划去的单位运价表中寻找最小元素时，发现该元素所在行的表中寻找最小元素时，发现该元素所在行的剩余产量等于该元素所在列的剩余销售量。剩余产量等于该元素所在列的剩余销售量。n这时在产销平衡表相应的位置填上一个数，这时在产销平衡表相应的位置填上一个数，而在单位运价表中就要同时划去一行和一而在单位运价表中就要同时划去一行和一列。为了使调运方案中有数字的格仍为列。为了使调运方案中有数字的格仍为（m+n m+n 1 1）个，需要在同时

24、划去的行）个，需要在同时划去的行或列的任一空格位置添上一个或列的任一空格位置添上一个“0 0”，这，这个个“0 0”表示该变量是基变量，只不过它表示该变量是基变量，只不过它取值为取值为0 0，即此时的调运方案是一个退化，即此时的调运方案是一个退化的基可行解。的基可行解。例例3.33.3n 某公司有某公司有3 3个生产同类产品的工厂，生个生产同类产品的工厂，生产的产品由产的产品由4 4个销售点销售，各工厂的生个销售点销售，各工厂的生产量、各销售点的销售量以及各工厂到各产量、各销售点的销售量以及各工厂到各销售点的单位产品运价如表销售点的单位产品运价如表3.83.8所示。利所示。利用最小元素法，求该

25、公司的初始调运方案。用最小元素法，求该公司的初始调运方案。表表3.83.8 销地销地产地产地B1B2B3B4产量产量A1531049A216964A32010577销量销量3584解：解：第一步：第一步：从单位运价表中找出最小运价从单位运价表中找出最小运价为为1 1，这表示先将，这表示先将 A A2 2 的产品供应的产品供应 B B1 1 。由。由于于A A2 2 每天生产每天生产4 4吨，吨，B B1 1 每天只需要每天只需要 3 3吨，吨，因此在产销平衡表因此在产销平衡表 (A A2,2,B B1 1)交叉处填上交叉处填上3 3，同时将单位运价表中的，同时将单位运价表中的B B1 1 这一

26、列运价划这一列运价划去。去。n第二步第二步:从上述未划去的单位运价表的元从上述未划去的单位运价表的元素中找出最小的运价素中找出最小的运价3 3，即，即A A1 1的产品供应的产品供应供应给供应给B B2 2；B B2 2 每天需要每天需要5 5 吨，由于吨，由于A A1 1每每天生产天生产9 9吨，因此在上述产销平衡表的吨，因此在上述产销平衡表的 (A A1,1,B B2)2)交叉处填上交叉处填上 5 5，划去上述运价，划去上述运价表中表中B B2 2这一列运价。这一列运价。n第三步第三步:从上述第二步所得的单位运价表从上述第二步所得的单位运价表未划去的元素中找出最小元素为未划去的元素中找出最

27、小元素为 4 4。这表。这表示将示将 A A1 1 把剩余的产品供应给把剩余的产品供应给B B4 4；B B4 4 每每天需要天需要4 4吨，吨，A A1 1 正好剩余正好剩余 4 4 吨，因此在吨，因此在上述产销平衡表的上述产销平衡表的 (A A1,1,B B4)4)交叉处填上交叉处填上 4 4，这时，这时A A1 1的产品已分配完毕，同时的产品已分配完毕，同时B B4 4 的的需求已满足，因此划去上述运价表中需求已满足，因此划去上述运价表中A A1 1 这一行和这一行和B B4 4 这一列运价。这一列运价。n为了使有数字的格不减少，为了使有数字的格不减少，(有数字的格有数字的格的总数应为的

28、总数应为m+n m+n 1 1个个 )可以在空格可以在空格(A A1,1,B B1)1)、(A A1,1,B B3)3)、(A A2,2,B B4)4)、(A A3,3,B B4)4)中任选一个格添加一个中任选一个格添加一个 “0 0”；同样，这个添加的；同样，这个添加的“0 0”格当作基格当作基变量，取值为变量，取值为0 0。这里我们在。这里我们在 (A A1,1,B B3)3)处填处填0 0（即初始调运方案是一个退化的基（即初始调运方案是一个退化的基可行解），表示为基变量。可行解），表示为基变量。n如此，进行下去，直到单位运价表中所有如此，进行下去，直到单位运价表中所有元素都划去为止，最终

29、在产销平衡表上就元素都划去为止，最终在产销平衡表上就可以得到一个初始调运方案。如表可以得到一个初始调运方案。如表3.93.9、表表3.103.10所示。所示。销地销地产地产地B1B2B3B4产量产量A1531049A216964A32010577销量销量3584表表3.9表表3.93.9表表3.10 销地销地产地产地B1B2B3B4产量产量A15049A2314A377销量销量3584 方法二、伏格尔法：方法二、伏格尔法：最小元素法的缺点是，为了节省一处的最小元素法的缺点是，为了节省一处的费用，有时造成在其它地方要花多几倍的运费用，有时造成在其它地方要花多几倍的运费。伏格尔法考虑到，一产地的产

30、品，假如费。伏格尔法考虑到，一产地的产品，假如不能按最小运费就近供应，就考虑次小运费。不能按最小运费就近供应，就考虑次小运费。这就有一个差额，差额越大，说明不能按最这就有一个差额，差额越大，说明不能按最小运费调运时，运费增加就越多。小运费调运时，运费增加就越多。因此，对于差额最大处，就优先采用最因此，对于差额最大处，就优先采用最小运费调运。小运费调运。我们还是用例我们还是用例3.2 3.2 来说明伏格尔法的具来说明伏格尔法的具体实施过程，步骤如下：体实施过程，步骤如下：n第一步：第一步：在单位运价表中增加一行和一列，在单位运价表中增加一行和一列，列的格位置相应填入该行的次小运费与最列的格位置相

31、应填入该行的次小运费与最小运费之差，我们称之为行差额。行的格小运费之差，我们称之为行差额。行的格位置相应填入该列的次小运费与最小运费位置相应填入该列的次小运费与最小运费之差，我们称之为列差额。如此可得表之差，我们称之为列差额。如此可得表3.113.11：表表3.11 销地销地产地产地B1B2B3B4行差额行差额A13113100A219281A3741051列差额列差额2513第二步：第二步：从行差额和列差额中选出最大者，从行差额和列差额中选出最大者，选择它所在的行或列中的最小元素。比较该选择它所在的行或列中的最小元素。比较该元素所在的行和列的产量，取它们最小者填元素所在的行和列的产量，取它们

32、最小者填入产销平衡表相应的位置。入产销平衡表相应的位置。同时在单位运价表中划去一行或一列。同时在单位运价表中划去一行或一列。由于由于B B2 2 的列差额最大。的列差额最大。B B2 2 列中最小元素为列中最小元素为 4 4（即（即 A A3 3 行），可确定行），可确定 A A3 3 产品优先供应产品优先供应 B B2 2。比较它们的产量和销量，可知在单位。比较它们的产量和销量，可知在单位运价表中划去运价表中划去 B B2 2 列。在产销平衡表的列。在产销平衡表的(A A3 3,B B2)2)空格处填入空格处填入 6 6。n第三步：第三步：对上述未划去的元素再比较出各对上述未划去的元素再比较

33、出各行、各列的差额。重复第一、二步的工作，行、各列的差额。重复第一、二步的工作，直到给出初始解为止。直到给出初始解为止。n本问题利用伏格尔方法给出的初始调运方本问题利用伏格尔方法给出的初始调运方案如下表案如下表3.113.11所示。所示。表表3.11 销地销地产地产地B1B2B3B4产量产量A1527A2314A3639销量销量3656n 由以上可见：伏格尔方法同最小元素由以上可见：伏格尔方法同最小元素法除在确定供求关系的原则上不同外，其法除在确定供求关系的原则上不同外，其余步骤相同，因而给出的初始调运方案也余步骤相同，因而给出的初始调运方案也是基可行解。是基可行解。n 且一般来说，用伏格尔方

34、法比用最小且一般来说，用伏格尔方法比用最小元素法所求出的初始解更接近于最优解。元素法所求出的初始解更接近于最优解。本例用伏格尔方法给出的初始解的总运费本例用伏格尔方法给出的初始解的总运费为为 8585元。元。（2 2）最优解的判别）最优解的判别 得到运输问题的初始基可行解后就要判得到运输问题的初始基可行解后就要判别这个解是否为最优解，判别的方法是计算别这个解是否为最优解，判别的方法是计算非基变量即空格的检验数。因运输问题的目非基变量即空格的检验数。因运输问题的目标函数是要求实现最小化，所以当所有的非标函数是要求实现最小化，所以当所有的非基变量检验数全都大于等于基变量检验数全都大于等于 0 0

35、时为最优解。时为最优解。下面介绍两种求空格检验数的方法。下面介绍两种求空格检验数的方法。、方法一：闭回路法、方法一：闭回路法n在给出调运方案的计算表上，如表在给出调运方案的计算表上，如表3.73.7，从每一空格出发，找一条闭回路。它是以从每一空格出发，找一条闭回路。它是以空格为起点，用水平线或垂直线向前划，空格为起点，用水平线或垂直线向前划，每碰到一数字格就转每碰到一数字格就转 90 90 度后继续前进。度后继续前进。直到回到起始空格处为止。直到回到起始空格处为止。n可以证明，每个空格都存在唯一的闭回路。可以证明，每个空格都存在唯一的闭回路。(A A1,1,B B1)1)空格与空格与(A A1

36、,1,B B4)4)、(A A2,2,B B4)4)和和 (A A2,2,B B1)1)三个有数字的格构成三个有数字的格构成一闭回路，如此等等。一闭回路，如此等等。闭回路计算检验数的经济解释为：闭回路计算检验数的经济解释为：在已给出初始解的表在已给出初始解的表3.73.7中，可以从任中，可以从任一空格出发，如从一空格出发，如从 (A A1,1,B B1)1)出发，若让出发，若让 A A1 1 的产品调的产品调 1 1 吨给吨给B B1 1，为了保持产销平衡，为了保持产销平衡，就要依次作调整：在就要依次作调整：在 (A A1,1,B B3)3)处减少处减少 1 1 吨，吨，(A A2,2,B B

37、3)3)处增加处增加 1 1 吨，吨，(A A2,2,B B1)1)处减少处减少 1 1 吨，即构成了以吨，即构成了以(A A1,1,B B1)1)空格为空格为起点，其它为有数字的格的闭回路。如表起点，其它为有数字的格的闭回路。如表3.123.12中的直线所示。中的直线所示。n各顶点所在格的右上角的数字是单各顶点所在格的右上角的数字是单位运价。位运价。n可见这一调整方案使运费增加了：可见这一调整方案使运费增加了：n(+1)(+1)3+(-1)3+(-1)3+(+1)3+(+1)2+2+(-1)(-1)1=1(1=1(元元)n这表明若这样调整运输方式将增加这表明若这样调整运输方式将增加运费。将运

38、费。将“1 1”这个数填入这个数填入(A A1,1,B B1)1)格，这就是检验数。格，这就是检验数。表表3.12 1 销地销地产地产地B1B2B3B4产量产量A1 3（1）34（1）37A2 13（1）21（1）4A3639销量销量3656按以上所述，就可以找出按以上所述，就可以找出 所有空格的检验所有空格的检验数，见如下表数，见如下表3.133.13。空空 格格闭闭 回回 路路检验数检验数(A1,B1)(1,1)(1,3)(2,3)(2,1)(1,1)1(A1,B2)(1,2)(1,4)(3,4)(3,2)(1,2)2(A2,B2)(2,2)(2,3)(1,3)(1,4)(3,4)(3,2

39、)(2,2)1(A2,B4)(2,4)(2,3)(3,3)(1,4)(2,4)-1(A3,B1)(3,1)(3,4)(1,4)(1,3)(2,3)(2,1)(3,1)10(A3,B3)(3,3)(3,4)(1,4)(1,3)(3,3)12表表3.133.13n这时检验数还存在负数，因为这时检验数还存在负数，因为(A A2,2,B B4)4)空格的检验数为空格的检验数为 1 1，这说明表，这说明表3.73.7给出给出的方案还不是最优解，还需要进一步改进，的方案还不是最优解，还需要进一步改进，改进方法见本节后面的基可行解的改进方改进方法见本节后面的基可行解的改进方法。法。、方法二：位势法方法二：位

40、势法用闭回路法求检验数时，需要给每一空用闭回路法求检验数时，需要给每一空格找一条闭回路。当产销点很多时，空格的格找一条闭回路。当产销点很多时，空格的数量很大，计算检验数将十分费时。下面介数量很大，计算检验数将十分费时。下面介绍一种较为简便的方法绍一种较为简便的方法位势法。位势法。现在引进现在引进m+nm+n 个未知量个未知量 u u1 1,u um m,v v1 1,v vn n，由上述基本可行解可，由上述基本可行解可构造如下一个方程组：构造如下一个方程组：是一组基可行解，是一组基可行解，其中其中c cijij为单位运价。方程组（为单位运价。方程组（3.13.1）共有）共有m+n m+n 个未

41、知数和个未知数和m+n-m+n-1 1个方程。个方程。(3.1)(3.1)的解存的解存在且恰有一个自由变量。称在且恰有一个自由变量。称u u1 1,u um m为行位势，为行位势，v v1 1,v vn n为列位势。为列位势。定理定理3.2 3.2 设已给了一组基本可行解，设已给了一组基本可行解，则对每一个非基变量则对每一个非基变量x xijij 来说，它所对应的来说，它所对应的检验数为：检验数为：ijij=c=cijij (u ui i+v+vj j)下面下面,我们就以例子来说明这种方法的我们就以例子来说明这种方法的具体实施过程。具体实施过程。仍以例仍以例3.23.2所给出的初始基可行解表所

42、给出的初始基可行解表3.73.7为例：第一步：在对应表为例：第一步：在对应表3.73.7的数字格处的数字格处填入单位运价如表填入单位运价如表3.143.14所示：所示：55 4 A3 22 11A2 1010 33 A1B4B3B2B1销地销地产地产地 表表3.143.14第二步：第二步：在表在表3.143.14上增加一行和一列，上增加一行和一列，列中填入行位势列中填入行位势 u ui i ，行中填入列位势，行中填入列位势 v vj j 得表得表3.153.15。先令先令u u1 1=0=0（行和列中基变量多的令为（行和列中基变量多的令为0 0），然后按），然后按ui+vj=cij ui+vj

43、=cij(i,j i,j)基基变量指标集变量指标集 ，相继确定，相继确定uiui、vj vj。由表由表3.153.15可见，可见，u u1 1=0=0 时，由时，由u u1 1+v+v3 3=c=c13=313=3可得可得v v3 3 =3=3，由，由u u1 1+v+v4 4=c=c14=1014=10，可得，可得v v4 4 =10=10；在；在v v4 4 =10=10时，由时，由u u3 3+v+v4 4=c=c34=534=5可得可得u u3=-53=-5。以此。以此类推可确定所有的类推可确定所有的uiui、vjvj的值。的值。10392列位势列位势vj-5-110行位势行位势ui

44、销地销地产地产地 B4B3B2B1A3A2A1 55 33 11 2244 1010表表3.15第三步：按第三步：按 ijij=cij =cij (ui+ui+vj vj),(),(i,j i,j)非基变量指标集，非基变量指标集，计算所有的空格检验数。如：计算所有的空格检验数。如：1111=c=c1111 (u u1 1+v v1 1 )=3)=3 (0+2)=1(0+2)=1 1212=c=c1212 (u u1 1+v v2 2 )=11-(0+9)=2)=11-(0+9)=2这些计算可直接在表这些计算可直接在表3.153.15上进行。上进行。为了方便，特设计计算表，如表为了方便，特设计计

45、算表，如表3.163.16。右上角框内的数为单位运价。右上角框内的数为单位运价。在表在表3.163.16中还有负的检验数，说中还有负的检验数，说明还未得到最优解，还得进一步进行明还未得到最优解，还得进一步进行改进。改进。10392列位势列位势vj-5-10行位势行位势ui 销地销地产地产地 B4B3B2B1A3A2A1 50 30 10 2004 100表表3.16 31 112 91 8-1 710 1012、基可行解改进的方法基可行解改进的方法闭回路调整闭回路调整法法当计算所有的空格检验数时，出现了负当计算所有的空格检验数时，出现了负检验数，这表明还未得到最优解。若有两个检验数，这表明还未

46、得到最优解。若有两个或两个以上的检验数为负时，一般选择其中或两个以上的检验数为负时，一般选择其中最小的负检验数，以它对应的空格为调入格。最小的负检验数，以它对应的空格为调入格。即以它对应的非基变量为换入变量。由表即以它对应的非基变量为换入变量。由表3.163.16可知可知 (A2,B4)(A2,B4)为调入格（即以它对应为调入格（即以它对应的变量的变量 x24 x24 为换入变量）。以此格为出发为换入变量）。以此格为出发点，作一闭回路，如表点，作一闭回路，如表3.173.17所示。所示。销销地地产产地地B1B2B3B4产产量量A14(+1)3(-1)7A231(-1)(+1)4A3639销销量

47、量3656表表3.17n (A2,B4)(A2,B4)格的调入量格的调入量 q q 是选择闭是选择闭回路上具有（回路上具有（-1-1）的数字格中的最小者。）的数字格中的最小者。即即 q=min1,3=1(q=min1,3=1(其原理与单纯形其原理与单纯形法中按法中按q q 规则来确定的换出变量是相同规则来确定的换出变量是相同)，然后按闭回路上的正、负号，加入和减，然后按闭回路上的正、负号，加入和减去此值，得到调整方案如表去此值，得到调整方案如表3.183.18所示。所示。销销地地产产地地B1B2B3B4产产量量A1257A2134A3639销销量量3656 表表3.18 解的解的调调整表整表n

48、对表对表3.183.18给出的解，再用闭回路法或位势给出的解，再用闭回路法或位势法求各空格的检验数，见表法求各空格的检验数，见表3.193.19，这时表，这时表中的所有检验数全都大于等于中的所有检验数全都大于等于 0 0，所以，所以表表3.193.19所给出的解为最优解。这时得到的所给出的解为最优解。这时得到的总运费的最小值是总运费的最小值是 85 85 元。元。B1B2B3B4A102A1A221A2A3912A3检验数都大于等于检验数都大于等于0 0，因此所得方案为最优，因此所得方案为最优方案。方案。表表3.19 检验检验数表数表 应当指出的是，产销平衡的运输应当指出的是，产销平衡的运输问

49、题必定存在最优解。问题必定存在最优解。那么有唯一最优解还是无穷多个那么有唯一最优解还是无穷多个最优解？最优解？依据仍然是看非基变量（即空格处）的依据仍然是看非基变量（即空格处）的检验数是否有为检验数是否有为0 0的。的。若有，则存在无穷多个最优解；否则，若有，则存在无穷多个最优解；否则，只有唯一最优解。只有唯一最优解。由于表由于表3.183.18可知，空格可知，空格 (A A1,1,B B1)1)处的检处的检验数为验数为0 0，表明例，表明例3.23.2有无穷多个最优解。可有无穷多个最优解。可在表在表3.183.18中以中以(A A1,1,B B1)1)为调入格为调入格,作闭回作闭回(A A1

50、,1,B B1)+1)+(A A1,1,B B4)4)-(A A2,2,B B4)+4)+(A A2,2,B B1)1)-(A A1,1,B B1)+1)+。n确定确定 =min2,3=2min2,3=2，经调整后得到另经调整后得到另一个最优解，见表一个最优解，见表3.203.20。销销地地产产地地B1B2B3B4产产量量A1257A2134A3639销销量量3656表3.20n当然，我们的调入量可以是当然，我们的调入量可以是：0 0 2 ji j 时，时，x xijij=0 0，所，所以应该令对应的以应该令对应的 c cijij=M M，M M 是充分大的正是充分大的正数，再加上一个假想的需