运筹学实验指导书(第五版)

《运筹学实验指导书(第五版)》由会员分享，可在线阅读，更多相关《运筹学实验指导书(第五版)（20页珍藏版）》请在金锄头文库上搜索。

1、运筹学 实验指导书 江西理工大学应用科学学院机电工程系江西理工大学应用科学学院机电工程系 工业工程教研室工业工程教研室 20122012 年年 3 3 月月 目目 录录 运用运用 EXCEL 求解运筹学问题求解运筹学问题.1 一、实验性质和教学目的.1 二、实验软件.1 三、软件使用说明.1 四、实验内容.9 五、报告要求.12 运用运用 QSB 求解运筹学求解运筹学.13 一、实验软件.13 二、软件使用说明.13 三、实验内容.18 运筹学实验指导书 1 运用运用 EXCEL 求解运筹学问题求解运筹学问题 一、实验性质和教学目的一、实验性质和教学目的 本实验是管理及经济类本科生运筹学课程的

2、上机操作实验，实验的内容是本科生阶段运筹学 的所有内容，主要包括线性规划、整数规划、运输问题、目标规划、动态规划、图与网络、网络 计划等。实验目的在于使学生掌握应用计算机工具解决运筹学模型优化求解的方法步骤，熟悉各种 运筹学优化软件的使用，特别是 Excel 优化功能的使用，为今后在实际工作中解决大型的实际问题 优化模型奠定基础。同时，通过熟悉优化软件的操作激发同学的学习兴趣，提高本课程的教学效果。 二、实验软件二、实验软件 软件名称：MS-office Excel 电子表格软件 开 发 者：Microsoft 软件内容：Office Excel 规划求解软件包及相关挂接软件包 三、软件使用说

3、明三、软件使用说明 Excel 电子表格中的工具菜单中有一个“规划求解规划求解”选项，它可以通过简单的程序方法在一个 表格中求解线性规划等规划模型。 首先检查你的首先检查你的 Excel“Excel“工具工具”菜单中是否有菜单中是否有“规划求解规划求解”项，如果没有该项，则通过项，如果没有该项，则通过“工具工具” 菜单中的菜单中的“加载宏加载宏”选项添加。下面以例选项添加。下面以例 1 1 为例说明用为例说明用 ExcelExcel 求解规划模型的过程。求解规划模型的过程。 【例 1】利用原材料和设备资源生产甲乙产品的生产计划问题，原始数据如下表： 甲乙资源约束 设备 A128 设备 B401

4、6 设备 C0412 单件利润23 其规划模型如下： 1.1. 在在 ExcelExcel 电子表格中建立线性规划模型电子表格中建立线性规划模型 把线性规划模型转化为 Excel 电子表格文件形式。其表现形式可以多种多样，但应保持模型的 组织性、逻辑性、直观性、易操作性。为此，把制作表格的过程分成四个部分：数据、决策变量、数据、决策变量、 目标方程、约束。见图目标方程、约束。见图 3-13-1 1)数据部分：数据是模型处理的基础，原始数据通过计算而生成其他数据，为了便于数据的使 用，应尽可能将数据集中安排在一个便于组织的表格中；2)决策变量：决策变量通过名称等对元素 0, 124 164 82

5、 43max 21 2 1 21 21 xx x x xx xxz 运筹学实验指导书 2 加以区分，并将最优计算结果自动填入其中，为此，每一个单元格对应一个决策变量，并在决策变 量的上面或旁边设置说明文字来进行标记，以便于区别。 3)目标方程：该部分包括目标价值所必要的元素，目标方程中将含有数据部分的数据和未知的 决策变量值（相应的单元格为值）的方程式及运算结果。 4)约束方程：通常将每一个约束分成左端项 LHS、右端此项 RHS 和约束符号三部分分别放在三 个单元格中，任何常量和决策变量元素的结合均可加入到约束中，但对于每一个约束而言，LHS 和 RHS 都必须非空（至少有一个元素） ，包括

6、非负条件在内。一个较好的处理方法就是将 LHS 作为一 列，而将 RHS 作为相邻的另一列，中间为符号说明列。 2.2. 在电子表格中优化线性规划模型在电子表格中优化线性规划模型 1)首先将基础数据、决策变量、目标方程、约束条件输入工作簿中。 2)在工具菜单中选择规划求解命令将出现规划求解参数窗口。在设置目标单元格的位置输入目 标单元格的代号；选定最大或最小；在可变单元格中输入决策变量单元格的代号；见图 3-2。 3)点击添加按钮出现添加约束对话框，在单元格引用位置输入约束的 LHS，选择约束符号类型， 在约束值位置输入相应的 RHS，如此重复添加各个约束条件；见图 3-3。 4)点击选项按钮

7、进入规划求解选项框，选定采用线性模型采用线性模型和假定非负假定非负选项框，然后点击确定； 见图 3-4。 5)点击求解按钮进入规划求解结果对话框，选定保存规划求解结果复选框，点击确定按钮则得 到求解的结果，见图 3-5。 此单元格代表 产品 I 的产量 需通过 此单元格代表产 品 II 的产量 此单元格代表目 标函数，格中输 入的是公式 这三个单元格分 别填入约束条件 左端公式 图 3-1 格式化规划模型到 Excel 中 基础数据 决策决策变变量量 约约束条件束条件 目目标标方程方程 图 3-2 规划求解参数窗口 运筹学实验指导书 3 3.3. 优化结果及灵敏度分析优化结果及灵敏度分析 在图

8、 3-5 所示规划求解结果窗口中，提示规划求解找到一解可以满足所有约束及最优状况，点 击确定按钮就会将优化的结果显示在 Excel 的界面中，决策变量及目标函数的位置就会出现相应的 图 3-3 添加约束窗口 图 3-4 规划求解选项窗口 图 3-5 规划求解结果窗口 运筹学实验指导书 4 优化结果值。优化的结果还可以以另一种形式出现，即在该窗口中选择运算结果报告项，点击确定 就会出现相应的结果报告如图 3-6。 在图 3-6 中有上中下三部分内容，其中上面是目标函数的优化结果值，中间是决策变量的优化 结果值，下面是约束条件在最优结果下的状态描述。 除了上述运算结果报告之外，在图 3-5 中还可

9、以选择敏感性报告选择项，点击确定后就会出现 相应的敏感性报告如图 3-7 所示。在此报告中分成上下两部分，上部分是对决策变量目标系数的灵 敏度分析，给出了目标系数的当前值和允许的增量和减量；下半部分是对各个约束条件右端常数项 的灵敏度分析，给出了约束左端的实际值、右端常数项的当前值以及允许的增量和允许的减量。 4.4. 其它规划模型的其它规划模型的 ExcelExcel 求解方法求解方法 4.1 运输问题用 EXCEL 求解 图 3-6 运算结果报告窗口 图 3-7 敏感性报告窗口 运筹学实验指导书 5 此处给出一个产销不平衡运输问题示例。图 38 是将运输问题规划到 EXCEL 表中，求解结

10、果 略。 图 38 4.2 整数规划及 0-1 规划模型的求解 在用 Excel 求解整数规划和一般 0-1 规划时，基本上与解线性规划相同，不同之处就是要把 决策变量的取整数要求或取 0-1 值的要求作为约束条件输入到模型中，通过添加约束窗口实现这一 要求，如图 3-9 所示。在此对话框中，左侧输入要求取整数决策变量的位置，在符号选择下拉列表 中选择 int(integer)项，则右侧自动出现整数二字，如果是 0-1 变量则在符号下拉列表中选择 bin(binary),右端就会自动出现二进制三个字。其它操作同线性规划。 匈牙利法的形式和运输问题类似，只需将变量变为 01，输入量和输出量分别变

11、为 1 既可。 4.2 目标规划模型的 Excel 求解 目标规划是解决多目标规划问题的较好的方法，由于规划目标的多样性以及规划目标的优先等 级的不可逾越性，在用 Excel 求解目标规划时通常采用逐级优化法。逐级优化法是基于各个目标的 优先等级逐次优化，首先优化优先等级最高的目标，这时以该等级目标方程中的偏差变量作为目标 函数进行优化，然后再优化次一级的目标，这时要把上一级及更高级的优化结果作为约束加入到本 等级的优化过程中，依此类推直至最后一级目标优化完毕为止，最后一级的优化结果就是整个目标 规划优化的结果。下面用例题说明。 【例 2】 用 EXCEL 求解多目标规划问题 解：（1）第一步

12、优化 首先将基础数据、目标函数和约束条件格式化到 EXCEL 表中，见图 310。实线单元格中为 3 , 2 , 1 , 0 , 12 5635 4 10 )32(min 21 4421 3321 221 1121 4321231 iddxxx ddxx ddxx ddx ddxx dPddPdPz iis 图 3-9 限定决策变量取整 运筹学实验指导书 6 已知数据，虚线单元格中为决策变量，细线单元格中为正负偏差变量，双线单元格中为第一次优化 目标函数，实际值为各个目标约束中的目标实现值，合计值为各个目标约束的左端项。 利用规划求解功能进行第一步优化，规划求解参数框设置见图 311。注意：可

13、变单元格应该可变单元格应该 包括决策变量和正负偏差变量；通过选项选择包括决策变量和正负偏差变量；通过选项选择“采用线性模型采用线性模型”和和“假定非负假定非负” 。求解之后的结果 见图 312。 （2）第二步优化 第二步优化与第一步优化的差别在于，在规划求解的过程中，目标单元格设定为目标单元格设定为 D12，增加一 个约束条件$F$60，见图 313。求解出来的结果见图 314。 （3）第三步优化 在第二步优化的基础上，在规划求解过程中，将目标单元格设定为将目标单元格设定为 D13，再增加两个约束条件 $E$46 和$E$50，见图 315。求解出来的结果与第二步优化结果相同。 图 310 图

14、 311 运筹学实验指导书 7 图 312 图 313 图 314 运筹学实验指导书 8 C 1 A B DE 6 3 25 46 图 316 6 10 11 F 54 8 G 图 315 4.3最大流问题、最短路问题和网络计划问题的 Excel 优化求解 以上三种问题的求解思路非常相似，此处仅举网络计划问 题为例，其他两中方法见课本。 【例 3】寻找网络图 316 的关键路线 求解思路见图 317，图中阴影部分为求解 之后的结果，公式、名称定义和求解思路在下部。 图 317 运筹学实验指导书 9 关键路线为：1256，或者说：ABG，路线长为 25 四、实验内容四、实验内容 （一）（一） 线

15、性规划问题线性规划问题: 用 EXCEL 表求解下面各题，并从求解结果中读出下面要求的各项，明确写 出结果。例如：原问题最优解为 X*=（4，2）T 1、 原问题的最优解（包括决策变量和松弛变量） 、最优值； 对偶问题的最优解； 目标函数价值系数的变化范围； 右端常数的变化范围。 2、 0, 42010132 4008510 3001028 9 . 223max 321 321 321 321 321 xxx xxx xxx xxx xxxz （1）求解： 原问题的最优解（包括决策变量和松弛变量） 、最优值； 对偶问题的最优解； 目标函数价值系数的变化范围； 右端常数的变化范围。 （2）对产品 I 进行改进，改进后系数列向量为（9，12，4）T，价值系数为 4.5 原问题的最优解（包括决策变量和松弛变量） 、最优值； 对偶问题的最优解； 目标函数价值系数的变化范围； 右端常数的变化范围； 对原问题的最优解有什么影响。 （二）整数规划：（二）整数规划：写出下面问题的最优解和最优值 （1）