整数规划模型Excel求解的简化方法

[摘 要] 整数规划是一类典型的线性规划问题。对于这类问题，运筹学中已有解决的方法，但比较繁琐。本文利用Excel软件的“规划求解”工具，对整数规划问题求解的模型建立和求解作了较详尽的论述。

[关键词] 整数规划问题 Excel 规划求解

整数规划是线性规划中的一类典型问题，应用于解决生产实际的许多问题，有着广泛的应用前景。对于这类问题，运筹学中已有解决方法，如分枝定界法、穷举法等，但很繁琐。也有借助于Matlab、Mathematics和 Lingo等软件求解,但专业性太强。相比之下,Excel功能强大，汉化水平高，菜单操作方便，拥有大量的函数、公式等，不需专门购买和安装。为解决整数规划问题提供了一种很好的工具。本文结合实例说明利用在Excel软件中“规划求解”工具，建立数学模型并求解整数规划问题。

1 “规划求解”工具

Microsoft Excel的“规划求解”工具取自于Leon Lasdon和Allan Waren共同开发的非线性最优化代码。“规划求解”是Execl中的一个加载宏。

1.1 安装 “规划求解”

加载宏是Excel的一个可选安装模块，在安装Microsoft Excel时，系统默认的安装方式不会安装宏程序，只有在选择“完全／定制安装”时才可选择安装这个模块。如果采用“典型安装”，则“规划求解”工具没有安装 ，就必须重新启动Office安装程序并且选择Excel选项，在加载宏区段中选择 “规划求解”，然后进行安装。

1.2 加载“规划求解”

安装了“规划求解”之后，在“工具”菜单下可能仍然找不到“规划求解”，此时您可以选择“工具/加载宏”，在打开的“加载宏”对话框中选中 “规划求解”复选框，确定后，就可以将“规划求解”命令添加到“工具”菜单栏中了。

2 整数规划的一般模型

整数规划是线性规划的特殊情形，它的变量x仅取整数，其数学表达式有标准式、缩简形式、向量式、矩阵式等多种表现形式。本文只讨论标准形式，具体表达式如图1。

3 实例及求解过程

例1：某工厂有资金13万元用于购置新机器，可在两种机器中任意选购，已知机器A每台购置费2万元，机器B每台购置费4万元。该厂维修能力只能维修7台机器B；若维修机器A，1台折算2台机器B。购置1台A可增加年产值6万元，1台B可增加年产值4万元，问应购置A和B各多少台才能使年产值增加最多？

第一步，建立数学模型（如图2）。第二步，建立整数规划问题的电子表格模型（如图3）。

第三步，选定可变单元格和目标单元格，输入目标函数和约束条件。选定可变单元格，用它来记录最终的最优解。将单元格B6和C6作为可变单元格(分别代表x1，x2)。在其中输入任意初值，不妨都输入0。确定目标单元格，用它来记录目标函数值。当问题求解结束时，它将显示最优的目标函数值。选定D5作为目标单元格(代表变量Z)，其中输入目标函数公式为D5=SUMPRODUCT(B5:C5,B6:C6)，含义是D5=B5×B6+C5×C6。输入约束条件。选定单元格D3和D4，依次输入约束条件。利用SUMPRODUCT函数，分别输入D3=SUMPRODUCT(B2:C2,B6:C6)，D4=SUMPRODUCT(B3:C3,B6:C6)，见图3。

第五步，设置规划求解参数。单击菜单栏“工具”中的“规划求解”命令，弹出“规划求解参数”的对话框后，在设置的目标单元格中输入“$D$5”，可变单元格中输入“$B$6:$C$6”。设置约束条件，单击“添加”按钮，出现“添加约束”对话框，在单元格引用中输入“$D$3:$D$4”约束值输入“$F$3:$F$4”。对于变量的整数值限制，需要再次输入$B$6：$C$6，约束值为“int整数”。如下图4、图5所示：

第六步，计算得出规划求解结果。完成了参数的设置后，单击“选项”按钮，弹出“规划求解选项”，见图6，勾选“假定非负”和“采用线性模型”，单击“确定”退出。单击“求解”按键，就可得到相应的结果，见图7。图中的单元格B6和C6里的数据就是得到的最优解。D5中的数据是Z最大的值，即Z=22万元。

特别地，如果是“0-1”型整数规划，只须对于变量的整数值限制，约束值为“bin两进制”即可。

参 考 文 献

[1]赵鹏等.管理运筹学教程.北京:清华大学出版社,北京交通大学出版社,2008.3.

[2]田啸等.Excel2000中文版操作详解与实例.华中理工大学出版社,1999.9.