运输问题的计算机辅助求解算法*

刘海英

(福建广播电视大学 福建福州 350003)

线性规划方法在制定生产计划、交通运输、工农业生产等经济管理领域中有非常广泛的应用[1-2]。经济类和管理类的各专业都会开设《线性规划》这门课程，但目前大多数院校针对这门课程还是采用传统的教学方法[2]：以讲授理论为主，多采用手工求解。学生在学习过程中，对枯燥的算法、理论知识缺乏兴趣，在算法的理解和计算方面会遇到很大的困难。学生虽然勉强地学了很多理论，但是当面对实际问题时却不知从何下手，难以解决。这种教学方法已经很难适应大学要培养应用型人才的需要，必须进行改革。笔者认为应重视实践环节的教学，针对一些实际问题采用案例的形式进行教学，并利用计算机软件进行求解，使得学生计算的准确性和效率都有很大的提高。同时大大提高了学生解决实际问题的能力，真正地做到了理论指导实践。

1 运输问题

有生产某种产品的产地若干个，同时也有需要这种产品的销地若干个，要把这种产品从各产地运往各销地，调运方案有很多种，应如何组织调运，才能使总的运输费用最小，这就是运输问题[4-5]。

运输问题也是一种线性规划问题，只是其决策变量为双下标变量。假如问题具有m个产地和n个销地，第i个产地用Ai表示，其产量为ai(i=1,2,…,m)，第j个销地用Bj表示，其销量为bj(j=1,2,…,n)，从Ai运往Bj的运价为cij。上述数据通常用产销平衡表和单位运价表来表示，有时把两个表合在一起，称为产销平衡运价表，如表1所示。

表1 产销平衡运价表

如果用xij表示从第i个产地调运给第j个销地的物资数量，总的运输费用支出最小的问题可以用式(1)来表示：

(1)

2 运输问题的手工解法

2.1 单纯形法[3,5]

由于运输问题属于线性规划问题，理论上可用解线性规划问题的基本方法——单纯形法来解，限于篇幅此处不作介绍。

为便于手算求解，单纯形迭代也可以通过表格进行。对于包含有m个产地和n个销地的运输问题，要包括m×n个变量，因此运用单纯形法其运算量是非常大的，实际操作时要考虑其他方法。

2.2 表上作业法

由于运输问题数学模型自身构造的特殊性，可以找到比单纯形法更为简便、有效的方法——表上作业法，从而可以大量节约计算时间和费用,步骤如下：

(a)找出运价最小的供销业务，并以最大限度满足其供销量为原则确定调运方案。

(b)在余下未确定的供销业务中继续寻找运价最小的供销业务，同样以最大限度满足其供销量为原则确定调运方案。

(c)以同样的方法反复进行，直到确定了所有的供销业务，得到一个完整的调运方案即初始基本可行解为止。

最小元素法的基本思想是就近供应，即优先满足单位运价最小的供销业务，故称之为最小元素法。

(2)最优性检验。最小元素法给出的是一个运输问题的基本可行解，还需要通过最优性检验判别该解是否是最优解。如果不是，则应当进行调整使方案优化。在单纯形法中，为了检验一个基本可行解是不是最优解，需要求出所有非基变量的检验数。在运输问题中，每个空格对应一个非基变量。因此，判别的方法是计算空格处的检验数，当所有的检验数均非正时，基本可行解就是最优解。

常用的判别方法为位势法。给一个调运方案的每一列的元素赋予一个值，称之为列位势，记为v1,v2,…,vn。对于每行的元素也赋予一个值，称之为行位势，记为u1,u2,…,um。它们的值由下列方程组决定：ui+vj=cij，其中cij为所有基变量xij的系数。上述方程组包含m+n-1个方程，m+n个变量。可以证明，任意取定一个ui或vj的值，其他ui,vj的值都可以唯一确定。用这样的方法可以求得任意一个空格的检验数：σij=(ui+vj)-cij。对于求得的检验数，有以下几种情况：

(a)如果表中所有的检验数都小于或等于0，则说明当前方案已经是最优方案了；

(b)如果某空格处的检验数等于0，则说明该运输问题有多重最优解；

(c)如果出现正的检验数，则说明需要对方案进行改进；

(3)采用闭回路法对初始方案进行调整、改进，直到求得最优方案为止。

运输问题中的闭回路是指以调运方案中的一个空格为起点，用水平或垂直的直线向前划，当碰到一个数字格时转90°，然后继续前进，直到回到起始空格为止。改进解的具体步骤如下：

(a)以正检验数所在的空格xij为换入基变量，找出它在运输表中的闭回路。

(b)以空格(Ai,Bj)为第一个奇数顶点，沿闭回路顺(或逆)时针方向前进，对闭回路上的顶点依次编号。

(c)在闭回路上的所有偶数顶点中，找出运输量最小的顶点(格)，以该格中的变量为换出基变量。

(d)以换出基变量的运输量为调整量，将该闭回路上奇数顶点处的运输量都增加这一数值，所有偶数顶点处的运输量都减去这一数值后，得到的新方案的总运费比原方案少。

(e)再对新得到的解进行最优性检验，如果不是最优解，就重复以上步骤继续进行调整，直到得出最优解为止。

方案调整时需要注意的是，有时对闭回路调整时，在需要减少运量的地方有两个以上相等的最小数，这样调整时原先空格处填上了这个最小数，则有两个以上最小数的地方成了空格。为了用表上作业法继续计算，就要把含最小数的格之一变为空格，其余均补添0，补添0的格当作数字格看待，使方案中有数字的格仍为m+n-1个。

综上所述，用表上作业法求解运输问题的步骤可用如图1所示的框图形式表示。

图1 表上作业法计算步骤框图

3 应用计算机软件Excel解运输问题

以上两种解题方法，其过程都相当繁琐，非常容易出错，在解决实际问题时，可以采用计算机软件Excel求解。Excel办公软件的普遍性优点使之更适合于促进科学决策的信息化水平。Excel中提供了规划求解工具，在解决线性规划问题时，只要掌握了基本模型的建立，就可以利用这个规划求解工具来求解，大大减少了计算量。即使不理解其数学原理和公式推导，只要学会上机操作，也可以轻而易举地求得结果。

3.1 工具的安装和使用

“规划求解”是Excel的一个加载项，它通常安装在“工具”菜单的“加载宏”中，显示为“规划求解选项”。在安装Excel后即可使用该程序。但是，在使用前必需要先进行加载。操作步骤如下：在Excel窗口中单击“工具”菜单，在弹出的下拉菜单(如图2)中单击“加载宏”命令，出现“加载宏”对话框如图3所示。

图2 Execel“工具栏”菜单栏

图3 Execel“宏”对话框

在“可用加载宏”列表框中选定“规划求解”复选框，则框前出现“√”表示该选项已被选中，单击“确定”按钮后，“规划求解…”命令将在“工具”菜单中显示出来如图2所示，和前一个工具菜单比较将会发现多出来一个“规划求解…”

应注意的是，如果在“加载宏”中找不到该选项，则需启动Office安装程序，经搜索已经安装的组件，列出4项维护程序，打开“添加/删除”项，选定“Excel”，单击“更改选项”按钮，再选择“加载宏”，找到“规划求解”，再单击“更改选项”，开始安装，安装完毕即可使用。

3.2 建立规划求解工作表

设置初始表格，建立目标单元格、可变单元格和约束条件之间的数量对应关系。

使用Excel求解线性规划问题时，电子表格是输入和输出的载体，因此设计良好的电子表格更加易于阅读。初始电子表中内容都是手动输入的数据。表中数据内容主要由3个基本部分组成：即决策变量单元格(一般设为可变单元格)、目标单元格和约束条件。

3.3 应用规划求解工具，定义各参数并求解

单击“工具”菜单下的“规划求解”，出现如图4所示的“规划求解参数”对话框，设置相应的参数。

(a)在此处分别“设置目标单元格”“等于”等选项。这是根据题意选择“最小值”“最大值”或是一个具体数值。

(b)“可变单元格”选项设置的决策变量的区域。

(c)然后单击“添加”按钮，出现如图5所示添加约束条件对话框。如在定义约束条件过程中，有需要修改的选中该公式单击“修改”按钮直接进行修改，有需要删除的，选中该公式单击“删除”按钮。所有约束条件定义完毕，此时单击图5中的“求解”按钮，出现如图5所示的对话框。

图4规划求解约束条件对话框

图5规划求解结果对话框

单击“保存规划求解结果”及“确定”按钮选项，得到解。如果在图7求解时单击选择右侧“报告”下面的“运算结果报告”“敏感性报告”“极限值报告”将分别给出3种报告。当实际问题中的目标函数和约束条件有所变动时，可以随时根据需要调整目标单元格和条件单元格的数值，然后重新求解，非常方便、快捷。

4 具体案例求解

运输问题案例：现有A1，A2和A33个产地分别生产某种物资7t，4t，9t，并销往B1，B2，B3，B44个地区，其中B1需要3t，B2需要6t，B3需要5t，B4需要6t，从各产地运往各销地的运价如表2所示。在完成运输任务的同时，满足总运费最小，试给出最优运输方案。

表2 各产地运往各销地的运价 (单位:万元/t)

销地运价产地B1B2B3B4 A1311310 A21928 A374105

这是一个非常典型的产量和销量相等的产销平衡的运输问题。

解:设产地A1销往B1，B2，B3，B44个地区分别为x11t，x12t，x13t，x14t，又知目标是要使总运费达到最小，即求目标函数的最小值。因此，该问题概括为用式(2)中的数学模型来表示：

minz=3x11+11x12+3x13+10x14+x21+9x22+2x23+8x24+7x31+4x32+10x33+5x34

(2)

4.1 表上作业法求解

此题存在3×4=12个变量，用手工解法的第一种单纯形迭代相当麻烦。可以采用表上作业法。

(1)编制初始调运方案。这个问题的初始运价表如表3所示。

表3 初始运价表

销地产地B1B2B3B4产量 A13113107 A219284 A3741059 销量3656

采用最小元素法求初始调运方案。从表3中找出最小运价为1的供销业务(有两个最小运价时任选其一)，最大限度满足其供销量为原则，再从剩下的元素中继续找到最小的运价这样一步步进行下去，直到表上所有的元素都划去为止，这时在产销平衡表上就得到一个调运方案，如表4所示，这个调运方案的总运费为z=4×3+3×10+3×1+2×1+6×4+3×5=86元。

表4 产销平衡表

销地产地B1B2B3B4产量 A1437 A2314 A3639 销量3656

(2)最优性检验——位势法[6]。采用前面所述位势法进行，可以求得各空格处的检验数如表5所示。

表5 位势法检验表

销地产地B1B2B3B4 A1-1-2 A2-11 A3-10-12

(3)用闭回路调整法对初始方案改进。如果检验数表中的所有数字都小于等于0，则表明对调运方案做出任何改变都不会使运费减少，即给定的方案已经是最优方案，但在表5中，(A2，B4)单元格的检验数为正，这就说明方案需要进一步改进。改进的方法是针对空格x24对应的闭回路，调整此闭回路上其他顶点的运输量，使x24尽量增大，以得到一个更好的基可行解。

改进解的具体步骤按上文所述闭回路调整法，这样调整后就得到一个新的调运方案，如表6所示，这个新方案的运费是85元。

表6 新的调运方案表

销地产地B1B2B3B4产量 A1527 A2314 A3639 销量3656

为了检验表6的方案是否为最优，继续对这个方案中的每一个空格求检验数，得检验数表如表7所示。

表7 位势法检验表

销地产地B1B2B3B4 A10-2 A2-2-1 A3-9-12

由于表7中的所有检验数都小于等于0，所以表6给出的方案是最优方案。检验数表7中，(A1，B1)处的检验数为0，这说明有多重最优解，可以求得表8所示的结果也是最优解。

表8 最优解表

销地产地B1B2B3B4产量A1257A2134A3639销量3656

4.2 用Excel软件中的“规划求解”工具求解运输问题。

(1)建立规划求解工作表。建立目标单元格、可变单元格和约束条件之间的数量对应关系，如图6所示，其中目标单元格“F5”的公式定义为：=3*B2+11*C2+3*D2+10*E2+1*B3+9*C3+2*D3+8*E3+7*B4+4*C4+10*D4+5*E4。

图6 规划求解工作表

(2)定义各项参数。完成以上操作后，单击“工具”菜单中的“规划求解”选项，并按Enter键进入“规划求解参数”对话框，设置对话框如图7所示，其中目标单元格为F5，等于最小值，可变单元格为“B2:E4”，约束条件分别添加为B2:E4>=0，B5=3，C5=6，D5=5，E5=6，F2=7，F3=4，F4=9。

图7 “规划求解参数”对话框的设置

(3)求解。单击“求解”按钮，系统开始运算。运算结束后即给出“规划结果”对话框，并且弹出提示“规划求解找到一解，可满足所有约束及最优状况”，并在表中显示所得结果，如图8所示。

图8 运算结果

如果在求解时单击选择右侧“报告”下面的“运算结果报告”“敏感性报告”“极限值报告”将分别给出3种报告，由于篇幅所限，此处略去。

在上例中，可以随时根据需要调整各目标单元格和条件单元格的数值，然后重新求解，十分方便、快捷。

为检验学生解决问题的能力是否有所提高，针对同一实际问题将120名学生平均分为3组进行对比实验。对比实验表明利用Lindo和Excel软件的求解速度要比手工求解速度高70-80%，而且准确率也大大提高。当把条件细微改动后(此处是修改两个运价)，用软件求解的优势更加明显。3种方法两次求解运输问题效率如表9所示。

表9 3种方法两次求解运输问题效率分析

5结论

线性规划这门课程与实践应用领域紧密相联，生产生活中的实际问题涉及的数据都比较多，如文中案例。当学生理解了算法之后，如果还是通过手算求解，运算量是非常庞大。随着计算机技术的发展和普及，教授学生会用计算机软件解决相关问题。通过对比也不难发现，运用计算机软件解决线性规划问题的优势。当学生在实际工作中遇到问题时，只要会利用软件，不用复杂的计算过程，就可以解决问题。即使在资源发生变化后，只需要改变某些变量的取值就可以快速得到最优值，大大提高解题的效率和准确率。学生们通过亲自动手操作，不仅能熟练运用线性规划模型和方法解决实际问题的流程，而且学会了分析问题和解决问题的方法，深刻体会到用科学知识解决实际问题的妙处，真正做到学以致用。