dfbdshbfsdjnfdv5f4g8df4gbdf9

实实 验验 报报 告告 运筹学运筹学 A 二 二 学学 号 号 啊沙发沙发啊沙发沙发 姓姓 名 名 学学 院 院 交通运输工程学院交通运输工程学院 指导教师 指导教师 二 O 一一年五月 运筹学 上机实验指导书 1 课程中文名称 运筹学 课程英文名称 Operations Research 实验学时 4 适用专业 交通运输 工程管理 交通工程 先修课程 线性代数 概率论与数理统计 开课学院 交通运输学院 开课学期 4 一 课程简介 本实验是 运筹学 课程教学的课程实践的一部分 本实验是使用与教材配套的教学 软件和计算机通用软件进行运筹学建模求解的实践环节 上机实验以 WinQSB 为主 进行 问题描述 数据处理 模型建立与求解 通过实验使学生掌握使用相应软件辅助解决运筹 学问题的基本方法 巩固课程学习内容 为进一步学以致用打下基础 二 实验目的 1 熟练掌握运筹学软件的相关操作 2 学会使用软件求解运筹学中常见的数学模型 如求解最小树 最短路 最大流 排队论 存储论和对策论等问题 三 实验项目 根据课程教学安排分两次进行 包括 运筹学 一 和 运筹学 二 其中 运筹学 二 实验内容如下 图与网络分析 1 求解最小树问题 要求编题求解 2 求解最短路问题 运用网络图求解最短路问题 3 求解最大流问题 运用网络图求解最短路问题 4 网络计划时间参数的计算 排队论 模型 M M C 存储论 对策论 四 报告撰写格式 课程名称 实验名称 实验学时 2 实验日期 班级 学号 姓名 1 问题描述与分析 将上机题目 copy 至此处 简单分析问题模型 注 2 实验步骤或过程 描述操作过程 粘贴主要界面 3 实验结果分析 问题讨论或实验心得 五 附 上机题目 本内容不装订 六 附 上机指导手册 本内容不装订 附 上机题目 最小树问题 求下图的最小生成树和最大生成树 6 V1 V2 6 6 2 2 V6 7 V7 3 V3 8 3 4 3 V5 1 V4 最短路问题 如图所示网络 各线段上的数字代表相应两节点间的距离 请求出从节点 1 到节点 10 之间的最短距离 网络图 最大流问题 某单位招收懂俄 英 日 德 法文的翻译各一人 有 5 人应聘 已知乙懂俄文 甲 乙 丙 丁懂英文 甲 丙 丁懂日文 乙 戊懂德文 戊懂法文 问这 5 个人是否都能 得到聘书 最多几个得到招聘 招聘后每人从事哪一方面翻译任务 网络计划时间参数的计算 1 已知下表所列资料 工序代号正常时间最短时间紧前工序 正常完成的直 接费用 百元 费用斜率 百元 天 A43 205 B86 304 C64B153 D32A52 E53A184 F75A407 G43B D103 H32E F G156 合 计153 工程的间接费用5 百元 天 绘制网络图 计算各工序最早开工 最早完工 最迟开工 最迟完工时间及总时差 并指出关键工序 并求出该项工程总费用最低的最优工期 最低成本日程 排队论 模型 M M C 某运输公司有一个装卸队服务于卡车队 装卸每辆车所用时间服从平均时间为 20 分钟 的指数分布 卡车到达时间服从平均时间为 30 分钟的泊松分布 管理层想提高装卸队的效 率 把装卸队分成两队 每队装卸每辆车所用时间服从平均时间为 40 分钟的指数分布 请 问效率是否得到提高 存储论 某电子设备厂对一种元件的需求为 R 2000 件 年 订货提前期为零 每次订货费为 25 元 该元件每件成本为 50 元 年存储费为成本的 20 如发生缺货 可在下批货到达 时补上 但缺货损失费为每件每年 30 元 求 1 经济订货批量及全年的总费用 2 如不允许发生缺货 重新求经济订货批量 并同 1 的结果进行比较 对策论 设矩阵对策 G S1 S2 A 其中 S1 a1 a2 a3 a4 S2 b1 b2 b3 b4 赢得矩阵为 6 5 6 5 1 4 2 1 A 8 5 7 5 0 2 6 2 2 附 上机指导手册 四 图与网络分析上机程序 1 运行 Network Modeling 出现图 7 所示界面 2 运行 file 菜单下的 new problem 命令 出现图 14 所示界面 图 14 中各项目含义 Problem Type 问题类型 如下 Transportation Problem 运输问题 Assignment Problem 分配问题 Shortest Path Problem 最短路问题 Maximal Flow Problem 最大流问题 Minimal Spanning Tree 最小分布树 Traveling Salesman Problem 旅行商问题 Objective Criterion 选择目标为求最大或最小 Data Entry Format 选择数据输入是以矩阵或图形输入 Number of Nodes 共有几个节点数 3 如求一个最短路 P137 习题 6 8 b 则 选择Shortest Path Problem Objective Criterion 选最小化 Number of Nodes 后写上节点数 7 Problem Title 后给文件命名 OK 确定 则得矩阵形式输入如图 15 所示 图图 13 图图 14 1 根据P137 习题 6 8 b 图 按照从左到右 从上到下顺序给节点标上号 共有 1 7 个节点 填上节点间的直接距离 两点间如果没有直接连线 则空着不填 自己到自 己的节点也可空着不填 如果是无向图 即 i 节点到 j 节点距离与 j 到 i 相等 可只填上三 角矩阵 填好后则得图 16 运行 出现图 17 如下 选择求最短路的起始节点和最后节点 点 solve 运行 也可点 solve and Display Steps 看求解过程 最后得结果 如图 18 图图 17 图图 18 图 18 中表示 1 节点到 7 节点的最短路径为从 Node1 Node2 Node5 Node7 总距离 图图 15 图图 16 2 13 4 求解最小生成树问题 4 v4 5 43 3 v7 v8 v3 v5 v2 v1 v6 2 4 2 2 2 2 2 8 3 第第 1 步 生成表格步 生成表格 选择 程序 winQSB Network Modeling File New Program 弹出对话框 问题类型 Problem Type 最小部分树问题 Minimal Spanning Tree 优化条件 Objective Criterion 最小 Minimization 数据输入格式 Data Entry Format 电子表格形式 Spreadsheet Matrix Form 节点数 Number of Nodes 8 第第 2 步 输入数据步 输入数据 单击 OK 并输入数据 3 第第 3 步 求解步 求解 从系统菜单选择 Solve and Analyze Solve the Problem 生成如下运行结果 即 v4 v7 v8 v3 v5 v2 v1 v6 2 2 2 2 2 23 支撑树的权 15 5 求解网络最大流问题 1 v 2 v 3 v 4 v 5 v 5 6 v 7 v 9 4 5 10 9 13 6 4 4 5 5 第第 1 步 生成表格步 生成表格 v5 4 选择 程序 winQSB Network Modeling File New Program 弹出对话框 问题类型 Problem Type 网络最大流问题 Maximal Flow Problem 优化条件 Objective Criterion 最大 Maximization 数据输入格式 Data Entry Format 电子表格形式 Spreadsheet Matrix Form 节点数 Number of Nodes 7 第第 2 步 输入数据步 输入数据 单击 OK 并输入数据 第第 3 步 求解步 求解 从系统菜单选择 Solve and Analyze Solve the Problem 弹出对话框 5 选择左侧 发点 和右侧 收点 单击 求解 Solve 生成如下运行结果 即 1 v 2 v 3 v 4 v 5 v 5 4 6 v 7 v 9 9 4 4 5 5 10 7 9 9 13 11 6 4 4 0 4 2 5 5 5 4 从节点 1 到节点 7 的最大流 20 6 求解货郎担问题 从 1 出发 到城市 从城市 1234 1 2 3 0 8 5 6 0 8 7 9 0 9 7 8 6 46550 第第 1 步 生成表格步 生成表格 选择 程序 winQSB Network Modeling File New Program 弹出对话框 问题类型 Problem Type 货郎担问题 Traveling Salesman Problem 优化条件 Objective Criterion 最小 Minimization 数据输入格式 Data Entry Format 电子表格形式 Spreadsheet Matrix Form 节点数 Number of Nodes 4 第第 2 步 输入数据步 输入数据 单 OK 并输入数据 第第 3 步 求解步 求解 从系统菜单选择 Solve and Analyze Solve the Problem 弹出对话框 7 最近距离 Nearest Neighbor Heuristic 最小成本 Cheapest Insertion Heuristic 双向 交流式 Two way Exchange Improvement Heuristic 分枝定界法 Branch and Bound Method 四种方法选择其一 单击 Solve 生成如下运行结果 即 1 2 4 3 1 最小距离 23 五 计划评审方法和关键路径法上机程序 1 运行 PERT CPM 出现图 19 所示界面 图图 19 2 运行 file 菜单下 的new problem 命 令 出现图 20 所示 界面 8 图 20 中各项目含义 Problem Type 问题类型 如下 Deterministic CPM 确定型关键路线法 Probabilistic PERT 概率型网络计划技术 Data Entry Format 选择数据输入是以矩阵或图形输入 Select CPM Data Field Normal Time 正常时间 Crash Time 赶工时间 Normal Cost 正常费用 Crash Cost 赶工费用 3 如求一个PERT 问题 P143 例 1 则 Problem Title 后给文件命名 Number of Activities 后给出作业数 9 Time Unit 后给出时间单位 hour Problem Type 选择 Deterministic CPM Select CPM Data Field 选 Normal Time 输入界面如图 21 所示 OK 确定后出现 输入矩阵如图 22 所示 图图 20 9 图 22 中表格各项含义如下 Activity Number 作业编号 按 1 2 3 等依次对各项作业编号 Activity Name 作业名称 可自行取名填入 Immediate Predecessor 紧前工序 填入该项作业的紧前作业 可以填紧前作业的编号或 名称 若有多项紧前作业 每项之间用西文状态下的逗号 格开 Normal Time 作业时间 按 P143 例 1 填入后如图 23 所示 图图 21 图图 22 10 图图 23 按运行图标运行 得结果如图 24 所示 图图 24 图 24 中从左到右各列含义依次如下 1 作业编号 2 作业名称 3 该作业是否是关键路径上的关键作业 若是则为 Yes 若不是则 no 4 作业时间 5 作业最早可能开始时间 6 作业最早可能完成时间 7 作业最迟必须开始时间 8 作业最迟必须完成时间 9 作业总时差 图 24 中最后两行给出了项目完成时间 本题为 17 50 和关键路径的数量 本题为 1 4 求一个概率型 PERT 书 P150 例 3 1 按顺序给书 P140 表 7 4 中的 9 项作业编号为 1 9 2 选择 File 菜单下 New Problem 3 在出现的对话框中 Number of Activities 填入 9 Problem Type 选择 Problistic PERT 点击 OK 4 在出现的表格中填入书 P150 表 7 4 的数据后如图 25 所示 点击运行键运行 5 结果意义与上例同 其中 Activity Mean Time 和 Standard Deviation 给出了完成各项作 11 业的期望时间和标准差 图 25 六 动态规划 1 运行 Dynamic Programming 进入动态规划程序 菜单栏上选择 File New 进入图 26 所示对话框 对话框中列出了本程序可以求解的三种动态规 划问题 分别为 最短路径问题 背包问题 生产与存储计划问题 下面将 分别举例说明 2 最短路径问题 以 P155 例 1 为例 1 在图 26 的对话框中 点选第一项 并在 Number of Nodes 中填入节点个 数 例 1 中共有节点数 10 完成后点击 OK 2 在出现的界面中 按照各个节点间连接关系 完成距离矩阵 填完后的 矩阵如图 27 所示 按运行键运行 出现一个对话框如图 28 所示 在左边的列 表中选择路径的开始节点 在右边的列表中选择路径的结束节点 点 solve 求 图图 26 12 解问题 也可点 solve and Display Steps 看求解过程 最后得结果 如图 29 3 图 29 中给出了用 顺序法 分四个阶段求解的每个阶段的决策 及当阶段 指标值 Distance 及该阶段的最优指标值 Cumulative Distance 并在求得最 后一个阶段即第四阶段的最优指标值时即得到整个过程上的最短路径 11 图图 27 图图 28 图图 29 13 3 背包问题 以 P169 例 8 为例 1 运行 file 菜单下的 new problem 命令 在出现的对话框中 Problem Type 点选 Knapsack Problen Number of Items 根据例 8 填入 3 点击 ok 2 在出现的界面中 按照例 8 数据填入后如图 30 所示 其中从左到右各项 含义为 Item 背包中装载货物数目 也即为动态规划的阶段数 Item Identification 货物名称 可以改变其命名 Units Avaliable 可提供的该 货物的最大数量 因本例中未提及货物的数量限制 因此均为 M Unit Capacity Required 单位货物的体积或重量 本题为重量 Return Function 单位货物的价值 用函数式表示 如单位 Item1 货物价值为 50 则写为 50Item1 以此类推 在底行的 Knapsack Capacity 背包最大容量 填完 后运行得结果如图 31 3 图 31 结果中各项含义可参照上例最短路径的结果来理解 4 生产与存储计划问题 以 P171 习题 8 3 为例 1 运行 file 菜单下的 new problem 命令 在出现的对话框中 Problem Type 点选 Production and Inventory Scheduling Problem Number of Periods 根据例 8 填入 4 点击 ok 2 在出现的界面中 按照例 8 数据填入后如图 32 所示 其中从左到右各项 含义为 Period 生产与存储划分的时期 即动态规划的阶段数 本题为 4 阶段生产与存储问题 Period Identification 各时期的名称 可以改变其命名 Demand 各时期需求量 本题 4 个时期需求量分别为 2 3 2 4 Production Capacity 各时期生产能力 本题由 C 函数 x 大于 图图 30 图图 31 14 6 时 C 为无穷 分析为 6 Storage Capacity 各时期存储能力 本题无限制 取默认值 M Production Setup Cost 生产准备费用 本题由 C 函数 0 x 6 时 C 为 3 x 分析为 3 Variable Cost Function 费用函数 用变量 P H B 三个变量的函数式表示 P H B 分别表示本阶段末的产量 存储量 缺货量 本题中单位生产成本 3 单位存储费用 0 5 无缺货损失 因此费用函 数为 P 0 5H 填完后运行得结果如图 33 3 图 33 结果中给出了最优生产计划 每个时期初始存储量 Starting Inventory 相当于动态规划的状态变量分别为 0 3 0 4 每个时期的产量 Production Quantity 分别为 5 0 6 0 该策略对应的总变量成本 不包括 生产准备费用 为 14 50 总成本 加上生产准备费用 为 20 50 图 32 图 33 七 存储论 1 运行 Inventory Theory and System 菜单栏上选择 File New 进入图 34 所示对话框 对话框中列出了本程序可以求解的问题类型 根据所学内容 将应用两种类型 即 EOQ 经济订货批量 模型 单时期随机存储模型 下面 将分别举例说明 15 图 34 2 EOQ 经济订货批量 模型 以 P190 习题 1 为例 在图 34 中点选第一个 即 EOQ 模型 并填入 Problem Title Time Unit 后 点击 OK 进入图 35 界面 并依据习题 1 填入参数 需求量 10 000 订货费用 2000 单位存储费用 100 0 2 20 具体如图 35 所示 填入后运行 得到图 36 所示结果 结果显示最佳订货批量为 1414 总的订货费用为 14142 13 总存 储费用 14142 14 总的费用为 28284 27 图 35 图 36 3 单时期随机存储模型 以 P187 例 8 为例 在图 34 中点选第 3 个 即模型 Single period Stochastic Demand Newsboy Problem 点击 OK 依据例 8 填入参数 需求分布 Normal 正态分布 可 以双击 Normal 在弹出的对话框中改变随机分布类型 需求期望 300 需求方差 50 单位成本 Unit acquistion cost 0 3 单位售价 Unit Selling Price 0 5 单位处理价 Unit salvage value 0 2 具体如图 37 所示 填入 后运行 16 图 37 得到图 38 所示结果 结果显示最佳订货批量为 321 5373 期望的利润为 54 55 图 38 八 排队论 1 运行 Qeueing Analysis 菜单栏上选择 File New 进入图 39 所示对 话框 根据问题类型选择 Simple M M System 或 General Queuing System 17 图 39 2 M M S 排队模型 以 P209 例 5 为例 点选 Simple M M System OK 在图 40 中 依据例 5 填入参数 具体如图 40 所示 填入后运行 得到图 41 所示结果 图 40 图 41 图 41 结果显示 系统有效到达率 eff 19 3135 人 h 系统忙率为 92 5506 平均队 长 Ls 9 5563 平均排队长 Lq 5 8543 平均等待时间 Wq 0 3031h 等 九 二人零和对策问题 18 第第 1 步 生成表格步 生成表格 例 求下列支付矩阵的二人零和对策的最优策略 1 2 64546 5 12037 551 549 13308 04213 A 234 345 456 A 1 选择 程序 winQSB Decision Analysis File New Program 弹出对话框 问题类型 Problem Type 选择 二人零和对策 Two player Zero sum Game 局中人 1 的策略数 Number of Strategies for Player1 5 局中人 2 的策略数 Number of Strategies for Player2 5 第第 2 步 输入数据步 输入数据 单击 OK 并输入数据 第第 3 步 求解步 求解 从系统菜单选择 Solve and Analyze Solve the Problem 生成如下运行结果 19 最优纯策略 Th