用解线性规划问题

子任务2.7　用Excel解线性规划问题

2.7.1　任务引入

【任务2-20】　P公司是一个生产高尔夫器材的小型公司，公司决定生产高、中价位的高尔夫袋，分销商对这种新产品十分感兴趣，并且同意买进公司未来3个月的全部产品。经过分析得知，高尔夫袋的生产分为4个工序：①切割并印染原材料；②缝合；③成型（插入支撑架、球棒分离装置等）；④检查和包装。生产一个标准袋的利润是10元，生产一个高级袋的利润是9元，有关生产消耗工时的数据如表2-21所示。要求为P公司建立数学模型，以决定高级袋和标准袋各应生产多少才能使公司获得最大利润？

表2-21　生产每个高尔夫袋所需要的时间及工时限制

【任务2-21】　某公司最优购买决策问题。某公司在生产过程中需要使用浓度为80%的磷酸100t，市场上各种浓度的磷酸及对应价格如表2-22所示。问应购买各种浓度的磷酸各多少吨，既能满足生产需要，又使得总成本最低？

表2-22　各种磷酸浓度及对应价格

【任务2-22】　某银行最优投资决策问题。某银行有100万元拟做投资用，其中一部分拟用做贷款（L），一部分拟投资证券（S）。贷款可以获取较高利率，证券利率虽然低一些但可以交易，在任何时候银行都可以将证券出售而获取迅速变现的能力。在下述条件下，试确定银行的最优投资决策。①年利率：贷款（L）10%，证券（S）5%；②变现能力S≥（L+S）×25%；③必须满足有信誉的老贷款客户的要求，L≥30。

2.7.2　任务分析

将P公司的问题表述为以下的线性规划模型：

下面介绍如何使用Excel 2002工作表解决P公司遇到的问题，我们在工作表的最上面输入P公司的有关数据，在工作表的底部写出数学线性规划模型。

使用Excel 2002建立数学公式的基本步骤如下：

第一步：在工作表的顶部输入数据；

第二步：确定每个决策变量所对应的单元格的位置；

第三步：选择单元格输入格式，找到目标函数的值；

第四步：选择一个单元格输入公式，计算每个约束条件左边的值；

第五步：选择一个单元格输入公式，计算每个约束条件右边的值。

2.7.3　知识构建

1）电子表格软件Excel简介

电子表格软件Excel 2002是微软公司应用软件系统Office 2002的重要组成部分，Excel 2002中文版是用于创建和维护电子表格的应用软件。电子表格实际上就是用于显示和管理数据，并能对数据进行各种复杂统计运算的表格，运用打印功能Excel 2002可以打印常用的各种统计报表和统计图。

运用Excel 2002的图表功能可以把数据信息用于二维和三维的统计图表，因此Excel 2002数据地图工具可以使数据信息和地理位置信息有机地组合起来，图表和数据地图完善了Excel 2002电子表格的应用功能。

Excel 2002工作簿是计算机存储数据的文件，每一个工作簿都可以包含多张工作表，因此可在单个文件中管理各种类型的相关信息，工作表是Excel 2002用来存储和处理数据的最主要的文档。Excel 2002还提供了被称为“数据透视表”的强大工具，使用它能够在短时间内对数据进行查阅和统计，让用户从各个角度查阅和分析财务数据。

使用Excel 2002电子表格不仅能完成日常的财务工作，在复杂的科学计算领域也得到了广泛应用。Excel 2002电子表格实际上就是一个数据库，对数据的各种操作同样适用于电子表格。在科学计算上，使用Excel 2002可以进行变量求解、假设分析、规划求解等；利用Excel 2002可以很容易地组织、计算和分析各种类型的数据，从而找到有价值的信息。

2）Excel 2002能以表格形式提供的功能

①强大（或万能）的表格计算功能；

②方便而漂亮的制表和图形制作功能；

③灵活的数据库管理功能；

④强大的科学计算功能；

⑤多方面的数据分析功能。

目前，我国对于Excel的应用，主要用于画表格或作简单的计算及图形制作，仅限于很初级的应用，其他方面的功能用得很少。

电子表格软件Excel与Lotus公司的Lotus 1-2-3有类似的结构：它们以工作簿为文件单位，一个工作簿可以包含若干（Excel 97最多256个，取决于内存的大小）工作表，一个工作表又可以包含很多的单元格。Excel 2002的单元格由列标题（由按字典排序的英文字母组成，如A，B，…，X，Y，Z；AA，AB，…，Ⅳ，共256列）和行号码（由阿拉伯数字1，2，…，65536，共65536行）相交而成。每个单元格就是一个变量，变量名就是其地址名，如A列与23行相交处的地址名或变量名就是A23，当然，地址或变量名也可以另外定义。每个变量可以存放各类数据，包括具有强大表格计算功能的公式和函数。

使用Excel 2002求解运筹学模型需要用到其中的“工具—规划求解”选项，此工具不是Excel 2002的标准安装部件，因此需要专门安装才能使用。

在系统中安装“规划求解”工具的方法如下：

①启动Excel 2002。打开“工具”菜单，如果没有“规划求解”选项，单击“加载宏”如图2-9所示。

图2-9　安装“规划求解”选项的“加载宏”窗口

弹出以下窗口，如图2-10所示。

图2-10　选中“规划求解”加载宏

②安装“规划求解”工具。在“当前加载宏”的复选框中选中“规划求解”，单击“确定”按钮后返回Excel，这时在“工具”菜单中就出现了“规划求解”选项，如图2-11所示，关闭“工具”菜单。

图2-11　安装后在工具菜单中出现“规划求解”选项

2.7.4　任务实施

下面按照以上所述5个步骤为P公司的问题建立公式工作表。工作表分为两个部分：数据部分和模型部分，模型的4个组成部分已经展示在图2-12上，为决策变量准备的单元格都已经用边框框起来了。如图2-12所示就是公式工作表，因为它展示了所有已输入的公式，而不是由公式得到的值。应用Excel工具解决该问题的具体步骤如下所示。

步骤一　在工作表的顶部输入问题的数据

单元格B5：C8显示的是每件产品的工作时间要求；单元格B9：C9显示这两种产品的单件利润；单元格D5：D8显示的是每个部门的可利用时间。

步骤二　确定每个决策变量所对应的单元格的位置

单元格B16是标准袋的产量，单元格C16是高级袋的产量。

步骤三　选择一个单元格输入用来计算目标函数值的公式

在单元格B18中输入=B9*B16+C9*C16。

图2-12　P公司优化问题数据输入和公式建立

步骤四　选择单元格输入公式，计算每个约束条件左边的值

在单元格B21中输入=B5*B16+C5*C16；

在单元格B22中输入=B6*B16+C6*C16；

在单元格B23中输入=B7*B16+C7*C16；

在单元格B24中输入=B8*B16+C8*C16。

步骤五　选择一个单元格输入公式，计算每个约束条件右边的值

对于此模型中的4个条件，选择相应的单元格输入其条件，即

在单元格D21中输入=D5；

在单元格D22中输入=D6；

在单元格D23中输入=D7；

在单元格D24中输入=D8。

为了便于理解，可为工作表添加标签，这将使我们能够很容易地理解每一部分的意思。例如，在第15行和第16行中分别写上“标准袋、高级袋”和“产量”，我们就很容易理解第15行和第16行的意思；此外，在单元格A18中写入“最大总利润”，用来说明单元格B18表示的是最大利润值；在约束条件明确时，增加了约束条件的名称“＜=”，用来表示约束条件左右两边的关系，这些标签对解题来说不是必要的，但它们可以帮助使用者理解模型，并对最优解做出说明。

步骤六　使用Excel求解

由Microsoft公司开发的Excel 2002，可以用来解决本课程中所有的线性规划问题。下面将详细说明如何利用Excel 2002来解决P公司所遇到的优化问题。

第一步：选择“工具”下拉菜单。

第二步：选择“规划求解”选项。

第三步：当出现“规划求解参数”对话框（如图2-13所示）时，在“设置目标单元格”栏输入B18，“等于”后选择“最大值”项，在“可变单元格”栏输入B16：C16，然后单击“添加”按钮。

第四步：当弹出的“添加约束”对话框出现时，在“单元格引用位置”框中输入B21：B24，选择＜=，在“约束值”框中输入D21：D24，然后单击“确定”按钮。

第五步：当“规划求解参数”对话框出现时，选择“选项”。

第六步：当“规划求解选项”对话框出现时，选择“假定非负”，单击“确定”按钮。

第七步：当“规划求解参数”对话框出现时，选择“求解”选项。

第八步：当“规划求解结果”对话框出现时，选择“保存规划求解结果”，单击“确定”按钮。

图2-13　P公司问题的“规划求解参数”对话框

图2-13表示的是整个规划求解参数对话框，图2-14表示的是“规划求解选项”对话框，图2-15表示的是Excel 2002工作表中求出的最优解。最优解是生产标准袋540个，高级袋252个，此时可获得的最大总利润为7668.0元。实际上，利用Excel不但能得到图形输出外，还提供了敏感度分析选项，有兴趣的读者不妨一试。

图2-14　第六步“规划求解选项”对话框

图2-15　Excel对P公司的问题的求解结果

需要说明的是，第六步时的对话框“规划求解选项”中选择了“假定非负”（如图2-13所示），这样做就不必输入非负性约束了。一般说来，如果要解决的线性规划问题是非负的，都应该选择该条件。此外，在第四步中，我们在“添加约束”对话框中的“单元格引用位置”中输入B21：B24，这样就将全部约束条件一次性地输入计算机中去了。当然，也可以一次输入一个约束条件。

对于“规划求解选项”对话框中有一些参数，通过设置这些参数的取值，可以控制规划求解过程。下面给出具体说明：

①最长运算时间。此选项默认值为100s。如果要改变设置，可先删去默认值，然后根据问题规模的大小和复杂程度、可变单元格和约束条件的多少以及所选其他选项的数目输入适当的运算时间，最长可达32767s。

②迭代次数。此选项默认值为100次。如果要改变设置，可先删去默认值，输入更多的迭代次数，最多可达32767次。增加迭代次数有可能使规划求解得到更满意的结果，但运算时间也将相应延长。

以上两项在运算过程中如果尚未找到结果就已达到设定的运算时间和迭代次数，将会弹出“显示中间结果”对话框，在对话框中选择“继续运行”后，可设置更多的运算时间和迭代次数，继续求解；选择“停止”，可在未完成求解过程的情况下显示“规划求解结果”。

③精度。此选项默认值为0.0000001。如果要达到更高的求解精度，可在此框中输入所要求的数值，使约束条件的数值能够满足目标值或其上、下限。精度必须用小数表示，小数位数越多，达到的精度越高，但求解的时间也越长。

④允许误差。此选项只适用于有整数约束条件的整数规划问题。所谓“允许误差”是指满足整数约束条件的目标单元格求解结果与最佳结果之间可以允许的偏差，默认值为5%。如果要改变默认值，可根据需要输入适当的百分数，设置的允许误差越大，求解过程也就越快。

⑤收敛度。此选项只适用于非线性规划。收敛度是指在最近5次迭代中，如果目标单元格数值的变化小于设置的数值，规划求解即停止运行，默认值为0.001，可根据需要改变设置。设置的值越小，则收敛度越高，即求解过程所需要的时间越长。

在以上5个选项下面还有4个复选框，可根据需要选用。

①采用线性模型。当目标函数为线性函数，约束条件为线性等式或不等式且要求解决现行优化问题或进行线性逼近时，可选择此复选框，以加速求解过程。

②自动按比例缩放。当输入和输出的数值相差很大时，如求投资百万美元的赢利百分数时，可选择此复选框，以放大求解结果（即增加小数位数）。

③假定非负。在“添加约束”对话框的“约束值”框中输入设置下限的可变单元格时，可选择此复选框，假定其下限为0。

④显示迭代结果。选择此复选框后计算机将单步执行规划求解，即每进行一次迭代后都将求解的数值记入工作表，并弹出“显示中间结果”对话框。如要继续求解过程并显示下次求解结果，可单击“继续执行”按钮，如要结束求解过程并显示“规划求解结果”对话框，可单击“停止”按钮。

另外，“估计”“导数”“搜索”单选框为规划求解所用方法选项。

①“估计”单选框指定在每个一维搜索中用以得到基本变量初始估计值的逼近方案，下设“正切函数”和“二次方程”两个选项。“正切函数”指定使用正切向量线性外推法；“二次方程”指定使用二次函数外推法，可以提高非线性规划问题的计算精度。

②“导数”单选框指定用于估计目标函数和约束条件偏导数的差分方案，下设“向前差分”和“中心差分”两个选项。“向前差分”多用于多数约束条件数值变化比较缓慢的问题；“中心差分”用于约束条件数值变化迅速，特别是接近限定值的问题。此选项需要较多计算，但有助于规划求解得到有效结果。

③“搜索”单选框指定每次迭代算法已确定的搜索方向，下设“牛顿法”和“共轭法”两个选项。“牛顿法”采用准牛顿法进行迭代，占用内存较多，但所需要的迭代次数较少；“共轭法”占用的内存较少，但要达到指定的精度需要迭代的次数较多。当问题规模较大或计算机内存有限，或单步迭代进程缓慢时，应使用“共轭法”。

同理实施任务2-22。

下面介绍求解操作步骤：

第一步：在Excel界面上的布局与P公司的布局相同，分为数据区城和模型区域。

第二步：选择“工具”—“规划求解”选项，弹出“规划求解参数”对话框，在“设置目标单元格”内填入＄B＄14，选择“最小值”选项，单击“选项”按钮，在“规划求解选项”对话框中选中“采用线性模型”和“假定非负”，单击“确定”按钮后返回到“规划求解参数”对话框。

第三步：在“规划求解参数”对话框内设置“可变单元格”为“＄B＄10：＄F＄10”，单击“添加”按钮，在“约束”框内输入约束条件＄B＄17：＄B＄18=＄D＄17：＄d＄18。

第四步：单击“规划求解参数”对话框中的“求解”按钮，即可解出如图2-16所示的答案。目标函数（最小总成本）最优值为169167元，见图2-16中的单元格B14，决策变量最优解如表2-23所示。

图2-16　使用Excel对某公司最优购买决策问题进行求解

表2-23　最优购买决策问题优化结果

同理实施任务2-23。

如图2-17所示，运用Excel工具求解结果为：L= 75万元，S= 25万元，最大获利总额为9万元。

图2-17　使用Excel对某银行投资决策问题进行求解

需要注意的是：为了使求解过程变得简单，在建立模型后进行求解时将约束条件做了变换，即图2-17中单元格B21=100-B16-C16，B22=C16-0.25*（B16+C16），B23=B16-30；其中L=B16，S=C16。这样，在“约束”文本框中就可以非常简单地写入＄B＄21=0，＄B＄22：＄B＄23＞=0，如图2-18所示，从而使求解过程简化。

图2-18　“规划求解参数”对话框