Excel求解线性规划问题实验教程要点.pdf

《Excel求解线性规划问题实验教程要点.pdf》由会员分享，可在线阅读，更多相关《Excel求解线性规划问题实验教程要点.pdf（27页珍藏版）》请在三一文库上搜索。

1、数学与信息科学学院 Excel 求解线性规划问题实 验 教 程 二零一三零八月 目录 1. 关于“规划求解” . . 1 2. 如何加载“规划求解” . . 2 3. “规划求解”各参数解释和设置. . 3 4. “规划求解”的步骤 . . 6 5.Excel 求解线性规划问题 8 6.Excel 求解运输问题 . 14 7.Excel 求解目标规划问题. 18 8.Excel 求解整数规划问题. 22 1 1. 关于“规划求解” “规划求解”是Excel 中的一个加载宏，借助“规划求解” ，可求得工作表 上某个单元格（被称为目标单元格）中公式（公式: 单元格中的一系列值、单元 格引用、名称或

2、运算符的组合，可生成新的值。公式总是以等号（=）开始）的 最优值。“规划求解”将对直接或间接目标单元格中公式相关联的一组单元格中 的数值进行调整，最终在目标单元格公式中求得期望的结果。“规划求解”通过 调整所指定的可更改的单元格（可变单元格）中的值，从目标单元格公式中求得 所需的结果。在创建模型过程中，可以对“规划求解”中的可变单元格数值应用 约束条件（约束条件： “规划求解”中设置的限制条件。可以将约束条件应用于 可变单元格、 目标单元格或其它与目标单元格直接或间接相关的单元格。而且约 束条件可以引用其它影响目标单元格公式的单元格。使用“规划求解”可通过更 改其它单元格来确定某个单元格的最大

3、值或最小值。） Microsoft Excel 的“规划求解”工具取自德克萨斯大学奥斯汀分校的Leon Lasdon 和克里夫兰州立大学的Allan Waren共同开发的 Generalized Reduced Gradient(GRG2) 非线性 最 优化 代码 。线 性和 整 数规 划问 题取自Frontline Systems 公司的 John Watson 和 Dan Fylstra提供的有界变量单纯形法和分支边 界法。 2 2. 如何加载“规划求解” 安装 office的时候，系统默认的安装方式不会安装宏程序，需要用户根据 自己的需求选择安装。 下面是加载“规划求解”宏的步骤： （1

4、）在“工具”菜单上，单击“加载宏” 。 （2）在弹出的对话框中的“可用加载宏”列表框中，选定待添加的加载宏 “规划求解”选项旁的复选框，然后单击“确定”。单击“确定”以后， “工具” 菜单下就会出现一项 “规划求解”命令。如果需要其他功能， 也可以用鼠标勾选。 注意: 加载的宏越多， Excel 启动的时候就会越慢，所以应工具需要选择。 （3）如果要卸载已经加载的宏，请在“可用加载宏”列表框中，选定待添加的 加载宏选项旁的复选框，然后单击“确定”。 3 3. “规划求解”各参数解释和设置 单击“规划求解”按钮，将会出现以下的规划求解参数的对话框。 设置目标单元格：一些单元格、具体数值、运算符号

5、的组合。注意：目 标单元格一定要是公式，即一定是以“=”开始。在应用Excel 的“规划求 解”命令求解线性规划问题时，目标函数对应的单元格就是目标单元格。 最大值、最小值：根据线性规划问题的目标函数是求最大（max ）还是求 最小(min) ，进行相应设置。如果需要指数值，可在右侧编辑框中输入数值。 可变单元格：在此指定可变单元格。其实可变单元格就是线性规划问题 在 Excel 中决策变量所在单元格。可变单元格必须直接或间接地与目标单元 格相关联。 推测：单击此按钮，自定推测“设置目标单元格”框中的公式所引用的 所有非公式单元格， 并在“可变单元格” 框中定为这些单元格的应用。 注意： 实际

6、进行计算时，这个命令几乎不用。 约束；在此列出规划求解得所有约束条件。 添加：显示“添加约束”对话框。 在该对话框中，设置线性规划问题中相应的约束条件。 更改：显示“更改约束”对话框。注意：单击此按钮的时候，要先选择 需要更改的约束。 4 删除：删除选定的约束条件。同样单击此按钮前，要先选择需要删除的 约束。 求解：对定义好的问题进行求解。 关闭：关闭对话框，不进行规划求解。但保留通过“选项”、“添加”、 “更改”或“删除”按钮所做的更改。也就是说，当你下次再次单击“规划 求解”按钮后，对话框显示上回所设置的参数。 选项：显示“规划求解选项”对话框。在其中可加载或保存规划求解模 型，并对求解过

7、程的高级属性进行控制。 最长运算时间：在此设定求解过程的时间。 可输入的最大值为 32767 （秒） ， 默认值 100（秒）可以满足大多数小型规划求解的要求。注意：我们在求解 线性规划问题时，该项一般不用改变。 迭代次数：在此设定求解过程中迭代运算的次数，限制求解过程的时间。 可输入的最大值为32767，默认值 100 次可满足大多数小型规划求解要求。 注意：我们在求解线性规划问题时，该项一般不用改变。 精度：在此输入用于控制求解精度的数字，以确定约束条件单元格中的 数值是否满足目标值或上下限。精度值必须表示为小数（0 到 1 之间），输 入数字的小数位数越多，精度越高。例如：0.0001

8、比 0.01 的精度高。注意： 我们在求解线性规划问题时，该项一般不用改变。 允许误差：在此输入满足整数约束条件并可被接受的目标单元格求解结 果与真实的最佳结果间的百分偏差。这个选项只应用于具有整数约束条件的 问题。设置的允许误差值越大，求解过程就越快。注意：我们在求解线性规 划问题时，该项一般不用改变。 5 收敛度：在此输入收敛度值，当最近五次迭代后目标单元格中数值的变 化小于“收敛度”框中设置的数值时，“规划求解”停止运行。收敛度只应 用于非线性规划求解问题，并且必须表示为（0 到 1 之间）。设置的数值越 小，收敛度就越高。例如，0.0001 表示比 0.01 更小的相对差别。收敛度越

9、小，“规划求解”得到结果所需的时间就越长。 采用线性模型 : 当模型中的所有关系都是线性的， 并且希望解决线性优化 问题时，选中此复选框可加速求解进程。 显示迭代结果：如果选中此复选框，每进行一次迭代后都将中断“规划 求解”，并显示当前的迭代结果。 自动按比例缩放： 如果选中此复选框， 当输入和输出值量级差别很大时， 可自动按比例缩放数值。例如，基于百万美元的投资将利润百分比最大化。 假定非负：如果选中此复选框，则对于在“添加约束”对话框的“约束 值”框中没有设置下限的所有可变单元格，假定其下限为0（零）。 估计：指定在每个一维搜索中用来得到基本变量初始估计值的逼近方案。 正切函数：使用正切向

10、量线性外推。 二次方程：用二次方程外推法，提高非线性规划问题的计算精度。 导数：指定用于估计目标函数和约束函数偏导数的差分方案。 向前差分：用于大多数约束条件数值变化相对缓慢的问题。 中心差分：用于约束条件变化迅速，特别是接近限定值的问题。虽然此 选项要求更多的计算，但在“规划求解”不能返回有效解时也许会有帮助。 搜索：指定每次的迭代算法，以确定搜索方向。 牛顿法：用准牛顿法迭代需要的内存比共轭法多。但所需的迭代次数少。 共轭法：比牛顿法需要的内存少，但要达到指定精度需要较多次的迭代 运算。当问题较大和内存有限，或迭代进程缓慢时，可用此选项。 装入模型 : 显示“装入模型”对话框，输入对所要加

11、载的模型的引用。 保存模型：显示“保存模型”对话框，在其中可指定保存模型的位置。 只有需要在工作表上保存多个模型时，才单击此命令。第一个模型会自动保 存。 6 4. “规划求解”的步骤 （1）首先在 Excel 表格上建立模型，然后单击 “规划求解”按钮， 出现“规 划求解参数”对话框； （2）在“设置目标单元格”对话框中，输入目标单元格的单元格引用（单 元格引用：用于表示单元格在工作表上所处位置的坐标集）。 （3）确定目标单元格中数值是最大还是最小，进行相应选择。如果要使目 标单元格中数值为确定值，单击“值为”，再在编辑框中键入数值。 （4）在“可变单元格”框中，输入每个可变单元格的名称或引

12、用，用逗号 分隔不相邻的引用。可变单元格必须直接或间接与目标单元格相联系。最多 可指定 200 个可变单元格。若要使“规划求解”基于目标单元格自动设定可 变单元格，可单击“推测”。 （5）在“规划求解参数”对话框的“约束”下，单击“添加”。 （6）在“单元格引用位置”框中，输入需要对其中数值进行约束的单元格 引用。其实是对应线性规划问题中约束条件的左端项（在Excel 中用单元格 表示）。 （7）单击希望在引用单元格和约束条件（约束条件：“规划求解”中设置 的限制条件。可以将约束条件应用于可变单元格、目标单元格或其它与目标 单元格直接或间接相关的单元格。）之间使用的关系 （“=”、 “Int

13、”或“Bin”）。如果单击“Int ”，则“约束值”框中会显示“整数”； 如果单击“ Bin”, 则“约束值框”中会显示“二进制”，表示取0 或 1。 （8）在“约束值”框中，键入数字、单元格引用或名称，或键入公式（公 式：单元格中的一系列值、单元格引用、名称或运算符的组合，可生成新的 值。公式总是以等号（ =）开始。） （9）若要接受约束条件并要添加其他约束条件，请单击“添加”按钮。若 要接受约束条件并返回“规划求解参数”对话框，单击“确定”。 7 （10）注意：只能在可变单元格的约束条件中应用“Int ”和“ Bin”关系。 当“规划求解选项”对话框中的“采用线性模型”复选框被选中时，对约

14、束 条件的数量没有限制。对于非线性问题，每个可变单元格除了变量的范围和 整数限制外，还可以有多达100 个约束。 （11）更改或者删除约束。在“规划求解参数”对话框的“约束”下，单击 要更改或删除的约束条件（约束条件：“规划求解”中设置的限制条件。可 以将约束条件应用于可变单元格、目标单元格或其它与目标单元格直接或间 接相关的单元格）单击“更改”，并进行所需的更改，或单击“删除”。 （12）单击“求解”，再执行下列操作之一：若要在工作表中保存求解后的 数值，请在“规划求解结果”对话框中，单击“保存规划求解结果”；若要 恢复原始数据，请单击“恢复为原值”。注意：按Esc 可以终止求解过程， Ex

15、cel 将按最后找到的可变单元格的数值重新计算工作表。若求出解，请在 “报告”框中单击一种报表类型，再单击“确定”。报表保存在工作簿中新 生成的工作表上。 8 5.Excel 求解一般线性规划问题 例 5-1（唯一解） Excel 建立线性规划模型及其求解 实验目的：掌握在 Excel 中建立线性规划模型和求解方法；会查看唯一解得 情况 实验内容：求解下列线性规划模型（课本P28） 12 2 12 12 max2 515 6224 5 0(1,2) j zxx x xx st xx xj 实验步骤： 第一步：把线性规划模型反映在Excel 表格中。如下图所示： 图中，注意 F5,F6,F7 单

16、元格中的 0 分别表示约束条件的右端项表达式。即 单元格 F5中应用了公式：=sumproduct(B5:C5,B9:C9), 单元格 F6中应用了公式： =sumproduct(B6:C6,B9:C9), 单元格F7中应用了公式： =sumproduct(B7:C7,B9:C9) 。目标单元格 G2表示目标函数值， 在 G2中输入了公 式：=sumproduct(B2:C2,B9:C9) 。 事实上，单元格 B9，C9分别表示了决策变量 12 ,x x。 第二步：设置规划求解参数 打开求解规划参数对话框，进行相应的参数设置，如下图所示： 9 其中， “选项”中选取“假定非负”和“采用线性模型

17、”，其他采用默认项，如下 图所示： 第三步：求解 设置完毕后，点击“求解”按钮，出现如下图所示对话框： 该图中“报告”栏显示三类报告， 意味着该线性规划问题有唯一最优解，根 据需要选择相应的报告，单击“确定”按钮，完成运算，在Excel 中，相应的计 算结果也会显示出来，结果如下： 10 可以看出， 该线性规划模型的最优解为 12 3.5,1.5xx 见单元格（B9，C9 ）, 最优目标函数值为8.5 （见单元格 G2 ） 另外，根据“规划求解结果”对话框中在报告一项的选择情况，也可以看到 相关结果。 如果选择“运算结果报告”，可得如下图所示结果： 从这个报告中，可知，最优目标函数值为8.5

18、，可变单元格 B9,C9对应的值 为 3.5,1.5即是最优解；约束一项反映了在最优的情况下， 实际资源的使用情况， 对于条件 1，未到限制状态，型数值7.5 表示资源剩余 7.5 ；而条件 2，条件 3 的状态显示达到限制值，型数值都为0 表示资源全部用完。 备注：在用Excel 求解线性规划问题时，涉及到的数如果有分数，则转化 为小数，或是对模型适当变形，使相关系数全部为整数，避免出现分数。 11 例 5-2无穷多最优解情况的区分 实验目的：会区别报告中暗示的“无穷多最优解”情况； 实验内容：求解下列线性规划模型 12 2 12 12 max3 515 6224 5 0(1,2) j zx

19、x x xx st xx xj 通过图解法可知该线性规划问题的解为无穷多最优解，如下图所示： 线段 AB上的点都是最优解，该线性规划问题有无穷多最优解。 应用 Excel 求解如下： 第一、二步与例 1 类似设置，但在第三步求解时， 规划求解对话框如下所示： 这个“规划求解结果”对话框情况与例1 的“唯一最优解”情况一样。在 Excel 表格中，计算结果显示如下： 12 通过上图可知，在线性规划问题具有无穷多最优解情况下，Excel 只能计算 出其中的一个最优解。 通过例 1 与例 2 的 Excel 应用可知， Excel 对线性规划问题具有无穷多最优 解与唯一最优解的情况不能区分。 例 5

20、-3无界解情况的区分 实验目的：会区别报告中暗示的“无界解”情况； 实验内容：求解下列线性规划模型 12 12 12 max300500 4 ,0 zxx xx st x x 图解法：通过图解法可知，该线性规划问题的可行域无界，最优解无界。如 下图所示： 可以看出， 目标函数直线往右上方平移，可以一直平移下去，而对应的目标 函数值会一直增大下去，可知该线性规划问题具有无界解。 Excel 求解： 13 第一、二步与例 1 类似设置，但在第三步求解时， 规划求解对话框如下所示： 从这个“规划求解结果”参数对话框的“报告”栏，可看出运算结果报告、 敏感性报告、极值报告都不可用， 同时从对话框中“设

21、置目标单元格的值未收敛， 知该线性规划问题具有无界解。 例 5-4无解情况的区分 实验目的：会区别报告中暗示的“无解”情况； 实验内容：求解下列线性规划模型 12 12 12 12 max2 2 226 ,0 zxx xx stxx x x 对于该线性规划问题，很容易知道它无可行解。 Excel 求解： 第一、二步与例 1 类似设置，但在第三步求解时， 规划求解对话框如下所示： 从该对话框的“ 规划求解好不到有用的解”可知，该线性规划问题无解。 14 6. Excel求解运输问题 实验目的：掌握Excel 求解运输问题方法； 实验内容：求解下列产销平衡的运输问题 销售点 加工厂 1 B 2 B

22、 3 B 4 B 产量 （吨） 1 A 3 11 3 10 7 2 A 1 9 2 8 4 3 A 7 4 10 5 9 销量（吨）3 6 5 6 20 在满足各销售点需求量的前提下，使总运费最小？ 解：设 ij x表示加工厂(1,2,3) i A i运往销售点(1,2,3, 4) j Bj的运输量，考虑到产 量与销量相等，可建立产销平衡模型如下： 111213142122232431323334 11121314 21222324 31323334 112131 122232 132333 142434 min31131092874105 7 4 9 3 . 6 5 6 0(1,2,3;1,

23、2,3,4) ij zxxxxxxxxxxxx xxxx xxxx xxxx xxx st xxx xxx xxx xij 运输问题是一种特殊的线性规划问题，理论上一般采用“表上作业法”求解 运输问题，但 Excel 的“规划求解”还是采用“单纯形法”来求解。 Excel 求解过程如下： 第一步：根据运输问题特点，建立电子表格模型，如下图所示： 15 在上图中，黄色框内表示初始运输方案，可全部记为0。实际销量一行，事 实上是由各产地到某销地的实际运输量相加得到，实际产量一列由相应的产地到 各销地的实际运输量相加得到。 总 费 用对 应的 单元 格 J3 为 目标 单元 格，该 单元 格中 输

24、入 了 公 式： =sumproduct(b3:e5,b9:e11),事实上，它是由图中青绿色单元格与黄色单元格对 应位置相乘再相加得到的。 第二步 : 利用“规划求解”命令求解。 首先打开求解规划参数对话框，进行相应的参数设置，如下图所示： 其次，打开“选项”按钮进行设置，设置结果如下图所示： 16 点击“确定”后回到“规划求解参数”对话框。 最后，点击“求解”命令，进入“规划求解结果”对话框，如下图所示： 可以看出，该运输问题存在最优解，在“报告”一栏，可以选择显示的3 个 报告，也可以不选择，直接点击“确定”按钮，可在第一步建立的电子表格模型 中显示最优解。 第三步，确定最优解。如下图所

25、示： 从上述表格可以很容易看出最优运输方案（黄色框内）和对应的最小总费用（见 单元格 J3）。 17 当然，也可以根据建立的数学模型，应用线性规划模型求解方式求解，但没有 上述这种方式方便。 18 7. Excel求解目标规划问题 实验目的：掌握Excel 求解目标规划问题方法； 实验内容：求解下列目标规划问题 112233 12 1211 1221 1233 12 min, 51060 20 4436 6848 ,0 (1,2,3) ii PdP dP d xx xxdd stxxdd xxdd x xddi 实验过程： 第一步：首先保证 1 P级目标的实现，这时不考虑其他次级目标。 此时模

26、型变为： 11 12 1211 1221 1233 12 min 51060 20 4436 6848 ,0 (1,2,3) ii zd xx xxdd stxxdd xxdd x xddi 首先，根据这个模型建立电子表格模型（与线性规划模型类似）如下图所示： 注意: 图中，单元格B6 中输入公式： =d2；左端表达式一列分别是用B4:I4 一行与黄色方框内各行相乘再相加得到。 其次，应用“规划求解”命令，打开“规划求解参数”对话框，进行相关设 置，设置情况如下图所示： 19 同时打开“选项”按钮进行设置，主要是考虑非负和线性情况。 最后，点击“求解”命令，可得结果如下： 可以看出，目标函数为

27、0，即 1 P级目标对应的 1 0d。 第二步，在保证 1 P级目标实现的基础上考虑 2 P级目标。 此时，把 10d加入第一步的模型中，目标函数变为2P级对应的目标，此时 的模型为： 22 12 1211 1221 1233 1 12 min 51060 20 4436 6848 0 ,0 (1,2,3) ii zd xx xxdd xxdd st xxdd d x xddi 仿照第一步的做法，对该模型建立电子表格，并应用规划求解命令，同时进 行相关设置，可得结果如下： 20 注意：在该图中，单元格B6中输入了公式： =g4；从图中也可以看出，对于 第二级目标也能实现，即有 20d。 第三步

28、，在保证 1 P级目标和 2 P级目标的基础上，考虑 3 P级目标。 此时，在第二步模型基础上，添加约束条件 2 0d, 目标函数变为 3 P级对应 的目标，所得模型如下： 33 12 1211 1221 1233 1 2 12 min 51060 20 4436 6848 0 0 ,0 (1,2,3) ii zd xx xxdd xxdd stxxdd d d x xddi 可在第二步建立的电子表格基础上，添加约束条件 2 0d，并更改目标 函数，按照第一步类似做法，应用“规划求解”命令，可得计算结果如下： 21 该步得到的结果即是整个目标规划问题的满意解。可以发现， 第三级目标也 能够实现

29、。 特别说明：目标规划的求解， 是在分步骤的情况下进行的， 即是在求出第一 级目标的情况下，再求第二级目标，依次类推，但要注意是在满足上级目标的 情况下，再求下级目标，且别忘记上级目标的目标值要作为约束条件放入下一 级目标规划中。 22 8.Excel 求解整数规划问题 例 8-1 应用 Excel 求解纯整数规划问题 实验目的：掌握Excel 求解纯整数规划问题方法； 实验内容：求解下列纯整数规划问题 12 12 12 12 12 12 max3 523 5410 325 ,0 , zxx xx xx stxx x x x x为整数 实验步骤： 第一步：把模型反映在Excel 表格中，建立电

30、子表格模型，如下所示： 第二步，应用“规划求解”命令，打开规划求解对话框，设置如下所示： 23 注意一点是，考虑到决策变量取整数，在约束中把代表决策变量的可变单元格 B4：C4要求为整数，添加约束时，进行了如下设置： 其他方面的设置与一般的线性规划求解类似。 第三步，点击“求解”按钮，结果如下： 可看出，最优解为 12 1,2xx，最优目标函数值为1。 例 8-2 应用 Excel 求解 0-1 型整数规划问题 实验目的：掌握 Excel 求解 0-1 型整数规划问题方法； 实验内容：求解下列0-1 型整数规划问题 1234 1234 1234 124 1234 min37 21 648 3 535 ,01 zxxxx xxxx xxxx st xxx xxxx 或 实验步骤： 第一步：把模型反映在Excel 表格中，建立电子表格模型，如下所示： 24 第二步：应用“规划求解”命令求解，其他设置与一般线性规划问题求解类似， 要注意的是关于决策变量的设置，在添加约束时，可按下图所示进行： 该设置中的 $B$4:$E$4代表决策变量， bin 表示二进制，即决策变量取值为0 或 1。 第三步：求解结果如下所示： 可看出，最优解为： 1234 1,0,1,1xxxx，最优目标函数值为：3（绿色 单元格 B7显示） 。