信息系统项目管理师计算题考点：运输问题

考点分析：并不常考，虽然第4版官方教材上介绍的是最小元素法，但考试时，我们都是用伏格尔(Vogel)法进行计算，主要也是考察伏格尔法，所以大家需要重点理解下伏格尔法的求解方法，其他的内容了解即可。而且这部分内容只看文字说明是很难理解的，建议大家看视频教程讲解，然后结合试题演练加深理解。

运输问题是一类特殊的线性规划问题，将单纯型法的思想用到运输问题的求解里，便得到了运输问题的表上作业法。首先确定初始方案，可选用西北角法、最小元素法或伏格尔法;其次进行解的最优性检验，有闭回路法和位势法两种基本方法;最后进行解的调整优化，直至求得最优解。

表上作业法求解步骤：

一、在已知运输表的基础上寻找初始基可行解，通常采用下列3种方法:

1.西北角法(简便，但求解效率低，现已不常使用);

2.最小元素法(整体效率适中，在某些问题中有着因追求最小运费而使得其他供销地运费陡然增加的弊端);

3.伏格尔(Vogel)法(效率最高，但求解过程繁琐，应用更加广泛)。

二、通过计算初始基可行解的检验数来判断当前解的最优性。若已为最优解，则直接输出当前解;若非最优解，则转入下一步。判断最优性的方法主要有2种:

1.闭回路法;

3.位势法(对偶变量法)

三、最后对当前解进行调整，直到达到最优解，调整时通常采用闭回路法。

各方法介绍：

●西北角法：从单位运价表未被直线覆盖的西北角位置开始标识基变量，依次进行，直到找到m+n+1个变量位置。(此方法已不常用，所以大家知道有这么个东西就行了，不需要过多了解)

●最小元素法：从单位运价表未被直线覆盖的最小运价位置开始标识基变量，依次进行，直到找到m+n+1个变量位置。(大家可以看下官方教材的讲解，不过只看文字内容可能还是看不懂，需要大家去看看视频教程)

●伏格尔(Vogel)法(考试重点)：

沃格尔(Vogel)法又称差值法，该方法考虑到，最初按某一最小单位运价优先安排物品调运时，在后续调运过程中却可能不得不采用运费很高的其他供销点，从而使整个运输费用增加。沃格尔法的基本思想是在运价表中分别计算出各行各列的最小单位运价和次小单位运价之差，并称这两个单位运价之差为该销售地或供应地的罚数，然后按照最小单位运价对罚数最大处安排运输。因为若罚数的值很大，说明不按最小运价组织运输就会造成很大的运费损失。

算法步骤：

1、首先计算运输表中每一行和每一列的次小单位运价和最小单位运价之间的差值，分别称为行罚数和列罚数。

2、选取这些罚数中最大者(若存在最大罚数相同的情况，则任选其中一个)所在的行或列的最小单位运价所在的格子，在格子中给其分配尽可能大的运量，划去该行/该列。

3、在尚未划去的各行或各列中，重复以上步骤，直到最后一个格子也被分配上运量，得到所求运输问题的初始基可行解。

●位势法(对偶变量法)：在得到运输问题的初始基可行解后，应对该解做最优性判别。位势法就是用来判断解的最优性的一种方法，其实质是在求解单纯形表中非基变量的检验数。该方法适用于产地和销地较少的运输问题。

●闭回路法：找到运输问题的一个初始基可行解之后，判定此解是否是最优解的一种方法。在运输方案表中，任何一个非变量都能和若干个基变量构成一个唯一的闭回路。

使用规则：遇到数字才能改变方向，但也可以不换;偶数次转弯格上的运价标负号，奇数标正号。

结果分析：如果最终检验数均为非正数，则说明为最优解，否则不是。

以下用一个例题为大家进行讲解，但还是建议大家看视频教程!

【例题讲解】

某公司有东部、中部、西部三个生产基地，生产的产品需要运送带甲、乙、丙、丁四个市场，从生产基地到各个市场的单位运价及产量和需求量如表所示，完成该运输任务所需的最小运费为()。

A.242

B.244

C.289

D.302

【答案】B

【解析】采用伏格尔法。

第一步：计算每行每列的最小元素和次小元素差额

第二步：找到差额最大的行/列的最小运价位置作为基变量，从上表可知，最大的差额为5，也就是乙那一列，乙这一列最小运价位置为5，即西部那一行，所以，我们先考虑西部到乙的情况。

西部的产量为22，乙需求量为14，所以可以满足其最大需求，也就是最多可以运输的量为14。运输完成后，西部还剩余22-14=8，乙已经满足需求量，可以将这一列划掉。

第三步：跟第一步一样，重新计算除去已经划掉部分（即乙已经满足，划掉了）每行每列的最小元素和次小元素差额，然后找到最大差额的行/列的最小运价位置作为基变量，从下表可知，最大的差额为3，也就是丁那一列，丁这一列最小运价位置为6，即西部那一行，所以，我们先考虑西部到丁的情况。

西部的产量已经只剩下8，丁需求量为14，所以无法满足其最大需求，也就是最多可以运输的量为8。运输完成后，西部还剩余8-8=0，乙需求量还要14-8=6，西部已经用完，可以将这一列划掉。

第四步：这样一直重复以上步骤，直到得出完整的运输方案表，如下：

最后，对比价位表，可以算出：根据价位表，可以算出：12*4+4*11+8*2+2*9+14*5+8*6=244。所以答案选B。

【真题演练】