发布时间 : 星期日 文章运筹学与系统分析实验指导书(含实验56) - 图文更新完毕开始阅读76bd67c5d1f34693daef3ec7
七、实验步骤
提示：设在第 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
12 总流入量 13 总流出量 14 净流出量 15 17 19 20 21 22 23 24 25 26 27 节点1 节点2 节点3 节点4 节点5 节点6 16 给定的净流出量 18 边的容量 7 7 0 = 0 2 2 0 = 0 2 2 0 = 0 2 2 0 = 0 至 3 3 0 = 0 7 7 0 = 0 7 最大流量 节点1 节点2 节点3 节点4 节点5 节点6 从 11 4 2 3 1 2 2 4 3 4 2 3 (1)输入部分
首先输入已知数据。在单元格C21：H26中输入各节点间的边容量。凡是节点间没有管道相连接的边，令其容量为零。从节点6至节点1的边为“虚”边，可设它的容量等于从源点（节点1）出发的所有边的容量之和，即：4+3+4=11。此外，当网络中总流入量与总流出量达到平衡时，应满足以下条件：所有节点的净流出量均应等于零。在单元格C16：H16中输入各节点净流出量应取的值，它们均为零。 （2）决策变量
本问题的决策变量用C6：H11中的单元格表示，它们是从各节点到其他节点的实际安排的流量。 （3）目标函数
本问题的目标函数是流入节点6的总流入量（要求最大，即供油网络流量最大），或者从节点6流向节点1的流出量最大。在单元格J17中输入目标函数：=C11 （4）约束条件
本问题的约束条件有三个，第一个是网络中边的容量约束；第二个是各节点的总流入量与总流出量的平衡约束；第三个是决策变量非负约束。
第一个约束是网络中边的容量约束。容量约束是指各节点间的边上的流量不得超过该边的容量。因此有：
单元格C6：H11中的数值（边流量）≤单元格C21：H26中的数值（边容量）
第二个约束是节点总流入量与总流出量的平衡约束。其计算过程如下： ①计算各节点的总流入量
节点的总流入量等于所有流入该节点的流量之和。用单元格C12表示节点1的总流入量，在C12中输入：=sum(C6：C11)，将公式复制到单元格D12：H12，得到其他节点的总流入量。 ②计算各节点的总流出量
节点的总流出量等于从该节点的所有流出量之和。用单元格I6表示节点1的总流出量，在I6中输入：=sum(C6:H6)，将上述公式复制到单元格I7：I11，得到其他节点的总流出量。 ③计算各节点的净流出量
14