APP下载

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

2014-10-10冯英华

长春工业大学学报 2014年4期
关键词:运筹学约束条件单元格

冯英华

(潍坊科技学院,山东 寿光 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.

猜你喜欢

运筹学约束条件单元格
基于一种改进AZSVPWM的满调制度死区约束条件分析
流水账分类统计巧实现
玩转方格
玩转方格
浅谈Excel中常见统计个数函数的用法
运筹学课程教学改革问题研究
浅谈对运筹学专业教育的一些看法
基于半约束条件下不透水面的遥感提取方法
占卜·庙算·军事运筹——谈军事运筹学的历史发展
谈企管干部学习运筹学