四、实验仪器、设备
内存128Mb及以上，操作系统为Windows 2000及以上的电脑，并有安装好的完整Excel软件和lingo软件。
五、实验说明
1．整数线性规划问题和模型
在许多经济管理的实际问题中，决策变量只有非负整数才有实际意义。对求整数最优解的问题，称为整数规划(Integer Programming)(简记为IP)。又称约束条件和函数均为线性的IP为整数线性规划(Integer Linear Programming)(简记为ILP)。
ILP问题数学模型的一般形式为：求一组变量X1,X2,…,Xn，使
Max(orMin)Z??CjXj
j?1n?n??aijXj?bi(i?1,2,...,m)s.t.?j?1
?Xj?0,且皆为整数或部分整数?整数规划问题的求解应该在原来的规划模型中添加“决策变量为整数”的约束条件。
2．整数规划的一个重要特例是0-1型整数规划，它是指所有变量都必须为0或1的线性规划。如果在整数规划中，只要求部分变量必须为0或1，则称为0-1混合整数规划。
3．线性整数规划模型的求解
用Excel求解整数规划的基本步骤与求解一般线性规划问题相同，只是在约束条件中添加相应的“整数”约束。在Excel的规划求解参数对话框中，用“int”表示整数。因此，只要在该参数对话框中添加一个约束条件，在左边输入的是要求取整数的决策变量的单元格地址，然后选择“int”。见图2-1和图2-2。
图2-1 在规划求解对话框中添加整数约束
9
图2-2 在规划求解对话框中添加整数约束后
用Excel求解0-1型整数规划的基本步骤与求解一般线生规划问题相同，只是在约束条件中添加相应的“决策变量必须为0或1”的约束条件。在Excel的规划求解参数对话框中，用“bin”(binary)表示0和1两者取一。因此，只要在该参数对话框中添加一个约束条件，在左边输入的是要求取0或1的决策变量的单元格地址，然后选择“bin”。见图2-3和图2-4。
4．说明：现有的Excel虽然可以处理变量多达上千的一般线性规划问题，但它尚不能求解大规模整数规划问题。目前已有一些计算机软件具有较好的处理大规模整数规划的能力，如MPSX-MIP、OSL、CPLEX、LINDO等。不过对于一般规模不太大的整数规划，运用Excel可以解决。
5. 对于教材中例题和习题用Excel中“规划求解”功能求解和分析。 6. 尝试学习使用lingo求解。
图2-3 在规划求解对话框中添加0-1约束
六、实验题目
某服务部门各时段（每2h为一
个时段）需要的服务员人数如下表，按规定，服务员连续工作8h（4个时段）为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少。
时段 1 2 3 4 5 6 7 8 服务员最少人数 10 8 9 11 13 8 5 3
10
2-4 在图七、实验步骤
提示：设在第 j时段开始时上班的服务员人数为 xj。由于第 j时段开始时上班的服务员在第(j+3)时段结束时下班，故决策变量只需要考虑x1~x5。建立问题的数学模型为：
minz?x1?x2?x3?x4?x5
?x1?10
?x?x?8
?12
?x1?x2?x3?9
? x1?x2?x3?x4?11? ?s.t.?x2?x3?x4?x5?13
?x?x?x?8
345?
?x4?x5?5
?x?3
?5
??x1,x2,x3,x4,x5?0,且均取整数值
实验具体步骤：
（1）打开“实验二模板文件”；
（2）在B10中键入：=B8+C8+D8+E8+F8 （3）在B13中键入：=B8 在B14中键入：=B8+C8 在B15中键入：=B8+C8+D8 在B16中键入：=B8+C8+D8+E8 在B17中键入：=C8+D8+E8+F8
在B18中键入：=D8+E8+F8 在B19中键入：=E8+F8 在B20中键入：=F8 （4）在D13中键入：=B4 在D14中键入：=C4 在D15中键入：=D4 在D16中键入：=E4 在D17中键入：=F4
在D18中键入：=G4 在D19中键入：=H4 在D20中键入：=I4
（5）单击“工具\\规划求解”菜单
（6）在目标单元格一栏内，填入或选择表示目标函数值的单元格地址B10，并选择最小值选项；在可变单元格一栏内，填入或选择决策变量的单元格地址B8：F8。
（7）单击添加按钮，出现添加约束对话框，在单元格引用位置一栏内，填入或选择约束条件左边所在的单元格地址B13：B20；选择<=；在约束值一栏内，填入或选择约束
11
条件右端项的单元格地址D13：D20。添加约束，左边为决策变量的单元格地址B8：F8，选择“int”，即添加整数约束条件。单击确定。
（8）单击对话框架内的“选项”按钮，选择“采用线性模型”；选择“假定非负”；其它参数默认，单击确定；
（9）重新出现规划求解参数对话框，单击“求解”按钮，出现规划求解结果对话框，选择“保存规划求解结果”按钮。
本例结果：x1=10,x2=0,x3=8,x4=0,x5=5, 最小服务员总数：23人
八、实验练习
1．完成上述实验题目后，继续完成教材P146-147习题5.2、5.6。
实验三 图论与网络
一、实验目的
1.掌握图论与网络的概念和实际应用意义。 2.掌握图论与网络问题建模和计算机求解方法。 二、实验内容
1.对于教材中图论与网络中最大流问题例题和习题进行实验验证。
12
2.对于计算机求解结果进行分析和理解。 三、实验要求
1、学生在实验操作过程中自己动手独立完成，1人为1组。
2、完成实验报告：对计算机验证性求解结果的问题分析与结果报告。
四、实验仪器、设备
内存128Mb及以上，操作系统为Windows 2000及以上的电脑，并有安装好的完整Excel软件。
五、实验说明与步骤
（一）最大流问题模型及求解 1．供油网络问题
例3-1 如图3-1所示输油管道网，分别用节点1至节点6表示各输油管网站，边上的数表示该管道的最大输油能力，问应如何安排各管道输油量，才能使从节点1至节点6的总输油量最大？
2
2 3
4 1 2 4
3 2 6 1 4
3 4 3 2
5 图3-1 某供油网络系统
2．形成回路：添加一条从节点6至节点1的“虚边”（实际上不存在），目的是为了使网络中各节点的边形成回路，各节点的流出量与流入量的代数和（即净流出量）为零。 3．在Excel中构建该最大流问题模型，如表3-1所示。 表3-1 供油网络最大流量模型 B C D E F G H I J K A 1 例3-1 供油网络最大流模型 2 3 流量 4 至 节点1 节点2 节点3 节点4 节点5 节点6 总流出量 5 6 0 2 0 2 3 0 7 节点1 7 0 0 2 0 0 0 2 节点2 8 0 0 0 0 0 2 2 节点3 从 9 0 0 0 0 0 2 2 节点4 10 0 0 0 0 0 3 3 节点5 11 7 0 0 0 0 0 7 节点6 13