运筹学与系统分析实验指导书余平祥 杨振刚 主编华南农业大学信息学院 管理科学与工程系
2014．9
目 录
实验一 线性规划及灵敏度分析 .......................... 1 实验二 整数规划...................................................... 8 实验三 实验四 实验五 实验六 实验七
图论与网络 ............................................... 12 表格计算法 ............................................... 16 分析与评价 .......................................... 18 层次分析法 ............................................... 21 综合性实验 ............................................ 25
问题 实验一 线性规划及灵敏度分析
一、实验目的
1.掌握线性规划问题建模的方法。 2.掌握线性规划问题求解的原理。 3.理解灵敏度分析的概念和意义。
4.掌握计算机求解线性规划问题的方法。 二、实验内容
1、对于教材中的线性规划建模习题，列出线性规划模型并求解。 2、对于教材中的灵敏度分析例题进行计算机求解验证性实验。 三、实验要求
1、学生在实验操作过程中自己动手独立完成，1人为1组。
2、完成实验报告：分析模型与结果的准确性报告和对灵敏度分析的概念和意义的理解报告。
四、实验仪器、设备
内存128Mb及以上，操作系统为Windows 2000及以上的电脑，并有安装好的完整Excel软件。 五、实验说明与步骤 （一）列线性规划模型
1．线性规划模型的特点
（1）每个问题都可用一组决策变量(x1,x2,…xn)表示某一方案，其具体的值就代表一个具体方案。通常可根据决策变量所代表的事物特点，可对变量的取值加以约束，如非负约束。
（2）存在一组线性等式或不等式的约束条件。
（3）都有一个用决策变量的线性函数作为决策目标（即目标函数），按问题的不同，要求目标函数实现最大化或最小化。
2. 例1-1：美佳公司计划制造I,II两种家电产品.已知各制造一件时分别占用的设备A、B的台时、调试时间、调试工序及每天可用于这两种家电的资源能力、各售出一件时的获利情况如表1-1所示。问该公司应制造两种家电各多少件，使获取的利润为最大？
表1-1 美佳公司单位产品资源使用和利润情况
1
设x1和x2美佳公司和II的数则该问题规划模型
项目 设备A(h) 设备B(h) 调试工序(h) Max Z?2x1?x2单位产品利润（元） 5x2?15??6x?2x?24?2s.t.?1x1?x2?5???x1?0,x2?0Ⅰ 0 6 1 2 Ⅱ 5 2 1 1 每天可用能力 15 24 5 分别表示
制造家电I量。
可用线性表示如下：
（二）用Excel中的“规划求解”功能求解线性规划问题
求解运筹学问题的软件很多，常见的有Lindo, Matlab, Speadsheet软件，自编程序等等，我们这里介绍最易得到的Excel中的“规划求解”功能来求解线性规划问题的使用。
一些常见的带有Speadsheet的软件，如Excel、Lotus1-2-3等，均有内置的线性规划求解功能。Excel的规划求解功能是一种通用的优化与资源配置工具。下面以上题为例，说明运用Excel的“规划求解”功能求解线性规划问题的步骤。
1．在Excel中进行问题描述与建模
首先，Excel描述问题与建立模型，见表1-2所示。
表1-2中上半部分是问题描述。问题描述是将已知的相关信息用简明的语言与数据表达出来，如美佳公司关于生产所需的设备A、设备B、调试工序的时间和利润等信息的描述。表1-2中下半部分是建模部分。建立模型是键入该问题的目标函数计算公司、确定决策变量、描述与计算约束条件的过程。其具体做法如下： （1）设单元格B14和C14分别表示决策变量x1与x2；
表1-2 用Excel对美佳公司家电生产问题建模与求解
2
（2）设单元
1 例1-1 美佳公司家电生产优化问题 格B16表示2 目标函数（总3 单位产品的资源需求 利润），它的4 项目 Ⅰ Ⅱ 每天可用能力 值=2x1+x2，
0 5 15 5 设备A(h) 因此，在单元
格B16中键6 2 24 6 设备B(h) 入： 1 1 5 7 调试工序(h) =B8*B14+C82 1 8 单位产品利润（元） *C14 9 上述公
10 模型 式等价于：
11 =sumpro
12 决 策 变 量 duct(B8：C8，
13 家电I 家电II B14：C14) 14 产量 上述公15 式中的命令16 总利润最大化 “= 17 sumproduct(B 18 约束 使用量（左边） 每天可用能力（右边） 8：C8，B14： C14)”表示将19 设备A(h) <= 15 B8：C8中的20 设备B(h) <= 24 元素（即单元21 调试工序(h) <= 5 格B8和C8）
与B14：C14中的相应元素（即单元格B14和C14）分别相乘后求和，它等于B8*B14+C8*C14的值。
（3）设单元格B19、B20和B21分别表示三个约束条件左边的值。其中，第一个约束条件左边是设备A的实际工时使用量0x1+5x2，所以在B19中键入：=B5*B14+C5*C14
或者：=sumproduct(B5：C5，B14：C14) 得到第一个约束条件左边的值；
同理，在单元格B20和B21中分别键入： =B6*B14+C6*C14 =B7*B14+C7*C14
分别得到第二个和第三个约束条件左边的值。
事实上，可将表示第一个约束条件左边的公式修改为： = B5*$B$14+C5*$C$14
然后通过拖拉得到下面两个单元格内容。
表1-3 美佳公司建模与求解中的公式
A B C D
3