Excel平台下运筹学模型的求解分析

冯英华

（潍坊科技学院，山东 寿光 262700）

0 引 言

在运筹学教材中详细介绍了规划问题的分类及其解法，针对每种类型的问题都有不同的解决方法，但这些方法在实际计算过程中并不实用。一是手工计算篇幅会过长，二是计算占用时间太多。我们的目的是学会分析问题、建立模型和求解模型的方法，至于具体的求解过程可以交给计算机去处理。但现在学生对于 MATLAB，LINDO和LINGO等编程还没有接触，在这种情况下有一种简单而实用的运算工具就是Excel。Excel是平时用的比较多的一个软件，其中有一个工具“规划求解”，专门求解运筹学中的系列问题［1－2］，下面根据相应案例来分析一下Excel的各种使用方法。

在运用Excel求解之前先检查一下本机的Excel中是否安装了相关模块。方法是打开Excel，一般在2007版本中的工具栏下都带有规划求解选项，而2003版本中不带。现在用的最多的还是2003版本，如何实现2003版本下的求解运算呢？我们可以通过加载宏对本工具进行加载。

1 Excel在线性规划中的应用

对于线性规划问题的求解，课本上的方法是先将规划模型化为标准形，然后再利用单纯形法去进行求解，有时根据模型的需要还要添加人工变量来构造人工基［3－4］。而单纯形法中一次次的迭代加大了运算量，手工计算非常繁琐。在Excel中不需对原模型进行任何的变换，只需要将模型的各项数据全部录入即可。下面以一个具有一般性的线性规划模型为例来进行分析。

线性规划模型：

打开Excel，将上述问题按图1形式将相应数据依次输入。

图1 线性规划Excel图

“变量取值”取初始值为0，软件会自动进行迭代。在E栏中输入约束条件算式时应注意对变量取值实行绝对引用，以防在向下拖动选定区域时变量单元格发生改变。如E3格内应输入“＝B3＊＄B＄2＋C3＊＄C＄2＋D3＊＄D＄2”，然后向下拖动选定区域，扩展至E4，E5，在目标函数“B7”中输入“＝B6＊B2＋C6＊C2＋D6＊D2”，这样已知数据准备完毕，下面开始对问题进行分析。

选中目标函数单元格B7，点击“工具”一栏中的“规划求解”，如图2所示。

图2 规划求解参数图

2 Excel在运输问题中的应用

在运输问题中条件会相对较复杂，里面的数据通常涉及到产销平衡表和单位运价表，课本上的表上作业法运算量相对庞大。那么，怎样运用Excel轻松解决运输问题？在Excel中建立好单位运价表和产销平衡表两个表格，产销平衡表中初始数据填0，将其余相关数据列入表中。而该问题中的总运费支出最小又应如何表示呢？引入SUMPRODUCT函数对两表相应元素对应相乘并求和，即为总的运费支出。如“SUMPRODUCT（B2：E4，B7：E9）”表示对矩阵B2：E4与矩阵B7：E9的对应元素的乘积求和。

在目标单元格中输入目标函数，然后点击规划求解，根据要求将各个参数与约束条件在弹出的页面中依次填好即可。这里强调一下，选中“可变单元格”后，在Excel表格中点击运量表中变量的左上角单元格，再输入冒号，然后再点击运量表中变量的右下角单元格，这就代表了运量表的这个矩形框内的所有变量。在约束条件参数中使“各厂的产量＝已知产量”、“各地的销量＝已经销量”，同时在约束条件中要求所有变量非负。如果需要变量取整数，则只需在约束条件中约束好即可。点击求解后得到所求结果。

利用Excel建立好问题模型，它的特点是使用简单、便捷、利于调整。如果各厂的生产量或是各地的销售量有所变化，只需要在已经建好的Excel模型中更改一下有关数据就可以得出新的计算结果，使用非常方便，能够更好地服务于实际需求。

3 Excel在整数规划中的应用

整数规划只是对变量的要求有所变化，它是要求全部或部分变量的取值必须是整数。所以和线性规划问题在Excel中的求解一样，只需要在“规划求解参数”约束条件中添加变量取整数（int）的条件就可以，不再单独举例说明。

在该规划中还有一类“指派问题”，它的解法和第二类运输问题的解法类似，需在Excel中建立效率矩阵和分配矩阵两个表格，利用SUMPRODUCT函数对效率矩阵和分配矩阵两表相应元素对应相乘并求和。只是其中的变量取值只能取0或1，所以要在“规划求解参数”中对变量输入约束条件bin（二进制），也可以用“≥0”，“≤1”同时加取整数的条件来进行约束［6］。

4 Excel在目标规划中的应用

目标规划是一种处理多目标优化问题的工具，应用非常广泛，其模型与线性规划模型基本相同，所以可以用单纯形法进行求解［7－8］。但因不同目标重要程度相差悬殊，对目标函数的优化是按优先级顺序逐级进行的，所以人工运算量是非常大的，而Excel节省时间，能够快速地给出运算结果报告。

如多目标规划模型：

将上面模型中的相关数据与前面介绍的方法一样有条、有序的录入到Excel表格中。在这里需要说明3点：

3）目标函数为优先因子pi分别乘上对应的子目标之和，其中的优先因子可以根据实际需要来定义它的取值，这里取p1＝10 000，p2＝100，p3＝1，以满足pk≫pk＋1。

明确这3点，并将规划求解参数设置好后，进行求解输出结果报告。

5 Excel在图论问题中的应用（最短路径和最大流问题）

在很多实际问题中，经常会从图中求出任意两点间的最短距离以及其经过的路径，如选址、管道铺设、投资、设备更新等都可归结为最短路问题［3］。针对此问题一般有求从其中一点到另外其它各点之间的Dijkstra算法和求图上任意两个点之间的矩阵算法，但当涉及到的点比较多时，人工算法就不方便了。所以需要寻找一种既简单又方便的方法。

该问题一样可以利用Excel平台来进行求解，其原理是：令边的变量（决策变量）为0或1，1表示最短路经过该边，0表示不经过该边，起点进出权和为1，终点进出权和为－1，除此外各点处的进出权和为0，目标函数可借助SUMPRODUCT函数，设定为各边的变量和权之积的和的最小值［9］。

求从v1～v7的最短路，如图3所示。

图3 最短路网络图

以此为例在Excel表格中进行问题分析，将相关数据列出，如图4所示。

图4 最短路Excel图

图4中边的变量初始值设为0，单元格F列中录入每个顶点的进出权和，如：F2中录入“＝D2＋D3”，…，F8中录入“＝0－D10－D13”。本例中有两个特殊点v5，v6，以v5点为例，v6－v5是进边，v5－v6是出边，F6中录入“＝D10＋D11－D5－D8－D12”。在B14一格中输入“SUMPRODUCT（C2：C13，D2：D13）”。在弹出的求解参数表中输入“＄D＄2：＄D＄13＝二进制、＄F＄2＝1，＄F＄8＝－1，＄F＄3：＄F＄7＝0”的约束，点击“求解”后边的变量值为1的即为所通过的边。

6 结 语

运筹学是在解决实际问题的过程中发展起来的，而其手工的运算在实际问题中也不太切合实际，特别是问题比较复杂、运算量比较大的模型。因此，需要我们借助于更好的工具去运算，这样既大量节省时间，又增强了学生对计算机应用的进一步认识。Excel功能强大，它在运筹学中的应用不仅限于上述几个方面，存贮论、排除论等问题也可在Excel中建立模型进行直接求解，另外，还可运用“treeplan”宏建立决策树求解风险型决策问题，运用“teachdp”宏求解动态规划问题，通过VB编程进行随机模拟实验（如掷币游戏）等［9－10］。

Excel操作简单，其中的“规划求解”易于学习掌握，对初学者而言是一个非常不错的运算工具。

［1］吕剑亮，朱坤.运筹学线性规划模型求解的计算机应用［J］.长春工程学院学报：自然科学版，2001，2（3）：59－62.

［2］刘建知.利用Excel求解线性规划问题［J］.湖南农业大学学报：自然科学版，2005，31（5）：562－564.

［3］胡运权.运筹学基础及应用［M］.5版.北京：高等教育出版社，2008.

［4］马振华.现代应用数学手册（运筹学与最优化理论卷）［M］.北京：清华大学出版社，1998.

［5］陈士成，李桥兴，何丽红.运筹学网络优化模型的Excel求解的减化方法［J］.兰州大学学报：自然科学版，2010，46（9）：179－182.

［6］雷真，缪昇，屈俊童.整数规划法在防火预案制定中的应用［J］.云南大学学报：自然科学版，2009，31（S1）：289－293.

［7］李如兵，宗凤喜.运筹学教学中Excel的应用研究［J］.绵阳师范学院学报，2012，31（8）：148－152.

［8］杨波，罗领俊，张仰福.运筹学在实践教学中存在的问题与改进措施［J］.山西建筑，2012，38（3）：271－272.

［9］张美玉.求解线性网络最优化问题的新型进行算法［J］.广西师范大学学报：自然科学版，2006（4）：74－77.

［10］徐海霞，任红松，袁继勇，等.用Excel及其“规划求解”功能拟合曲线方程［J］.农业网络信息，2004（2）：37－39.