运筹学课程设计报告

长长 春春 工工 业业 大大 学学 课课 程程 设设 计计 报报 告告 课程设计名称课程设计名称 运筹课程设计运筹课程设计 专专 业业 信息管理与信息系统信息管理与信息系统 班班 级级 学学 生生 姓姓 名名 指指 导导 教教 师师 20112011 年年 7 7 月月 1212 日日 1 课课 程程 设设 计计 任任 务务 书书 课程设计题目 课程设计题目 第十六题第十六题 起止日期 起止日期 20112011 6 6 2929 20112011 7 7 1212设计地点 设计地点 教室 电子商务中心教室 电子商务中心 设计任务及日程安排 设计任务及日程安排 1 1 设计任务 设计任务 1 11 1 通过课程设计可以增强学生解决实际运筹学问题的能力 1 21 2 通过课程设计可以使学生巩固 拓展和深化所学的基础理论 专业理论和知 识 1 31 3 通过课程设计可以使学生初步掌握用运筹学方法解决实际问题的过程和技巧 树立理论联系实际的工作作风 1 41 4 通过课程设计可以使学生初步建立正确的设计思想和方法 进一步提高运算 计算机应用技能和综合分析 解决问题的能力 2 2 设计进度安排 设计进度安排 本课程设计时间分为两周 本课程设计时间分为两周 第一周 第一周 20112011 年年 6 6 月月 2727 日日 2011 2011 年年 7 7 月月 1 1 日 建模阶段 此阶段各小组日 建模阶段 此阶段各小组 根据给出的题目完成模型的建立 主要环节包括根据给出的题目完成模型的建立 主要环节包括 1 11 1 6 月 29 日上午 发指导书 按组布置设计题目 说明进度安排 1 21 2 6 月 29 日下午至 7 月 1 日 各小组审题 查阅资料 进行建模前的必要准 备 包括求解程序的编写与查找 1 31 3 7 月 4 日至 7 月 5 日 各个小组进行建模 并根据题目及设计要求拟定设计 提纲 指导教师审阅 同时阅读 理解求解程序 为上机求解做好准备 第二周 第二周 20112011 年年 7 7 月月 4 4 日日 7 7 月月 8 8 日 上机求解 结果分析及答辩 主要环日 上机求解 结果分析及答辩 主要环 节包括节包括 1 11 1 7 月 6 日至 7 月 7 日 上机调试程序 1 21 2 7 月 8 日 完成计算机求解与结果分析 1 31 3 7 月 11 日 撰写设计报告 1 41 4 7 月 12 日 设计答辩及成绩评定 答辩时间 7 月 12 日上午 8 30 12 00 下午 2 00 5 00 2 运筹学课程设计报告运筹学课程设计报告 组组 别别 第十八组 设计设计人员人员 设计时间设计时间 2011年6月27日 2011年7月12日 1 1 设计进度设计进度 本课程设计时间分为两周 第一周 2011 年 6 月 29 日 2011 年 7 月 5 日 建模阶段 此阶段各小组根据给出的题目完成模型的建立 主要环节包括 1 11 1 6 月 29 日上午 发指导书 按组布置设计题目 说明进度安排 1 21 2 6 月 29 日下午至 7 月 1 日 各小组审题 查阅资料 进行建模前的必要准 备 包括求解程序的编写与查找 1 31 3 7 月 4 日至 5 日 各个小组进行建模 并根据题目及设计要求拟定设计提纲 指导教师审阅 同时阅读 理解求解程序 为上机求解做好准备 第二周 2011 年 7 月 6 日 7 月 12 日 上机求解 结果分析及答辩 主要环节包括 1 41 4 7 月 6 日至 7 月 7 日 上机调试程序 1 51 5 7 月 8 日 完成计算机求解与结果分析 1 61 6 7 月 11 日 撰写设计报告 1 71 7 7 月 12 日 设计答辩及成绩评定 2 2 设计题目设计题目 第十六题 某城市自来水的水源地为A B C三个水库 分别由地下管道把水送 往该市所辖甲 乙 丙 丁四个区 唯一的例外是C水库与丁区没有地下管道 由于 地理位置的差别 各水库通往各区的输水管道经过的涵洞 桥梁 加压站和净水站 等设备各不相同 因此该公司对各区的引水管理费 元 千吨 各不相同 见下表 但是对各区自来水的其他管理费均为45元 千吨 而且对各区用户都按统一标准计费 单价为90元 千吨 目前水库将临枯水期 该公司决策机构正考虑如何分配现有供水 量的问题 首先 必须保证居民生活用水和某些重要机关 企业 事业单位用水的 基本需求 各区的这部分用水量由下表的 最低需求 行表示 但是拥有一个独立 水源的丙区这部分水量可自给自足 无须公司供给 其次 除乙区外 其他三个区 都已向公司申请额外再分给如下水量 千吨 天 甲区 20 丙区 30 丁区要求 3 越多越好 无上限 这部分水量包含于 最高需求 行中 该公司应如何分配供水量 才能在保障各区最低需求的基础上获利最多 并按要求 分别完成下列分析 1 水库B供应甲区的引水管理费 元 千吨 在何范围内变化时最优分配方案不变 2 水库A的供水量在何范围内变化时最优基不变 3 乙区的日供水量为80千吨时的最优分配方案 引水管理费 千 吨 甲乙丙丁供水量 元 千吨 A1613221750 B1413191560 C192023 50 最低需求 千吨 天 3070010 最高需求 千吨 天 507030不限 3 3 建模过程建模过程 3 13 1 设定变量设定变量 设 Xij表示从第 i 个水库输水到第 j 个区的供水量 其中 i 1 2 3 1 2 3 分 别代表 A B C 三个水库 j 1 2 3 4 1 2 3 4 分别表示甲 乙 丙 丁四 个区 设 Z 为总的饮水管理费 设 Y 表示公司的获利 3 2 根据题意推理 A水库到甲区的饮水管理费为 16X11 A水库到乙区的饮水管理费为 13X12 A水库到丙区的饮水管理费为 22X13 A水库到丁区的饮水管理费为 17X14 B水库到甲区的饮水管理费为 14X21 区 水 库 4 B水库到乙区的饮水管理费为 13X22 B水库到丙区的饮水管理费为 19X23 B水库到丁区的饮水管理费为 15X24 C水库到甲区的饮水管理费为 19X31 C水库到乙区的饮水管理费为 20X32 C水库到丙区的饮水管理费为 23X33 A水库的供水量为 X11 X12 X13 X14 50 B水库的供水量为 X21 X22 X23 X24 60 C水库的供水量为 X31 X32 X33 50 甲区的最低需求为 X11 X21 X31 30 乙区的最低需求为 X12 X22 X32 70 丁区的最低需求为 X14 X24 10 甲区的最高需求为 X11 X21 X31 50 乙区的最高需求为 X12 X22 X32 70 丙区的最高需求为 X13 X23 X33 30 则得该问题的LP问题为 MinZ 16 X11 13X12 22X13 17X14 14X21 13X22 19X23 15X24 19X31 20X32 23X33 X11 X12 X13 X14 50 X21 X22 X23 X24 60 X31 X32 X33 50 X11 X21 X31 30 X12 X22 X32 70 X14 X24 10 X11 X21 X31 50 X13 X23 X33 30 Xij 0 i 1 2 3 4 j 1 2 3 4 3 33 3 计算机求解前的手工数据准备计算机求解前的手工数据准备 3 3 1数学模型数据准备 将原问题第一 二 三 四 六 七 八个约束条件添加松弛变量X1 X2 X3 X4 X5 X6 X7 5 将原问题第四 五 六个约束条件添加人工变量X8 X9 X10 将问题化为标准形式 MaxZ 16X11 13X12 22X13 17X14 14X21 13X22 19X23 15X24 19X31 20X32 23X33 X11 X12 X13 X14 X1 50 A水库的供水量 X21 X22 X23 X24 X2 60 B水库的供水量 X31 X32 X33 X3 50 C水库的供水量 X11 X21 X31 X4 X8 30 甲区的最低需求 X12 X22 X32 X9 70 乙区的最低需求 X14 X24 X5 X10 10 丁区的最低需求 X11 X21 X31 X6 50 甲区的最高需求 X13 X23 X33 X7 30 丙区的最高需求 Xij 0 Xr 0 i 1 2 3 4 j 1 2 3 4 r 1 2 3 4 5 6 7 8 3 3 2 Lindo 6 1数据准备 在模型编译框内输入原模型的程序规范模式如下 Min 16X11 13X12 22X13 17X14 14X21 13X22 19X23 15X24 19X31 20X32 23X33 SUBJECT TO X11 X12 X13 X14 50 X21 X22 X23 X24 60 X31 X32 X33 30 X12 X22 X32 70 X14 X24 10 X11 X21 X31 50 X13 X23 X330 选择主元素行 r min bi0 bis 换元后计算各行新的系数 1 brj brj brs 2 bij bij brs brj 选择主元素列 s 用非基变量的线性组合来表示基变量 读取第一阶段计算结果 A 和 b 的值 开始 存在 cj0 b min bi ir ir 0 确定b的变化范围 如果b的变化在该范围之内最优基不变最优解变化 最优解由公式XB B 1b求得 如果b的变化超出该范围最优基最优解均发生变化 重新计算CBB 1b B 1b代入 最优表中重新迭代 5 25 2问题分析问题分析 通过对题目的正确理解和分析 依据题意可以得到在保证各区最低供水量的基 础上运费最低 也就是获利最大的模型 以这个模型为基础 可以得到公司分配供 水量的最优决策方案 然后通过灵敏度分析 1 水库B供应甲区的引水管理费 元 千吨 在何范围内变化时最优分配方案不变 2 水库A的供水量在何范围内变化时 最优基不变 3 乙区的日供水量为80千吨时的最优分配方案 5 35 3 计算机的求解结果及分析计算机的求解结果及分析 5 3 1 数据录入 输入变量个数以及变量系数和约束条件个数 依次输入约束 条件中变量的系数 以及右端常数项的值 输入确定并回车后可得最优解和最优值 如图 7 图 7 由图可知 最优分配供水量方案为 X12 50 X21 30 X22 20 X24 10 其余 13 变量的值为 0 即 A 水库输水到乙区 50 千吨 B 水库输入到甲区 30 千吨 到乙区 20 千吨 到丁区 10 千吨 此时 Min Z 1480 即最低总的饮水管理费为 1480 元 则最大获利为 Y 90 45 50 30 20 10 1480 3470 元 5 45 4 灵敏度分析灵敏度分析 5 4 1 根据结果分析当目标函数的变量系数在什么变化范围内时 最优基不变 VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X11 16 000000 INFINITY 2 000000 X12 13 000000 0 000000 INFINITY X13 22 000000 INFINITY 22 000000 X14 17 000000 INFINITY 2 000000 X21 14 000000 2 000000 14 000000 X22 13 000000 7 000000 0 000000 X23 19 000000 INFINITY 19 000000 X24 15 000000 2 000000 15 000000 X31 19 000000 INFINITY 5 000000 X32 20 000000 INFINITY 7 000000 X33 23 000000 INFINITY 23 000000 其中各列表头释义为 CURRENT COEF 初始目标函数系数 ALLOWABLE INCREASE 允许变量系数增加的范围 ALLOWABLE DECREASE 允许变量系 数减少的范围 则当目标函数的系数 C 在 初始目标函数的系数 允许变量系数减少 的范围 初始目函数的系数 允许变量系数增加的范围 内变化时 最优基不变 最 优解也不变 由于目标函数的系数发生改变了 所以最优值有可能改变 5 4 2 根据结果分析约束条件右端项在什么范围内变化时 最优基不变 ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50 000000 20 000000 0 000000 3 60 000000 INFINITY 0 000000 4 50 000000 INFINITY 50 000000 5 30 000000 0 000000 30 000000 6 70 000000 0 000000 20 000000 7 10 000000 0 000000 10 000000 8 50 000000 INFINITY 20 000000 9 30 000000 INFINITY 30 000000 其中各列表头释义为 CURRENT RHS 初始约束条件右端项的值 ALLOWABLE INCREASE 允许 b 值增加的范围 ALLOWABLE DECREASE 允许 b 值减少的范围当约束条件右端项的值在 初始约束条件右端项的值 允许 b 值 14 减少的范围 初始约束条件右端项的值 允许 b 值增加的范围 内变化时最优基不变 最优解不变 5 55 5 原问题分析原问题分析 5 5 1 水库B供应甲区的引水管理费 元 千吨 在何变化范围时最优分配方案不变 解 因为水库 B 供应甲区的饮水管理费为 C21 由上列计算结果可得允许变量系 数增加的范围为 0 2 允许变量系数减少的范围 0 14 所以水库 B 供应甲区的饮 水管理费在 0 16 范围内变化时最优基不变 5 5 2 水库A的供水量在何范围内变化时最优基不变 解 因为水库A的供水量年是第1个约束条件的右端项 即该问题求的是b1的变化 范围 由上列计算结果可得b1变化范围为 0 20 所以水库A的供水量在 50 70 范围 内变化时最优基不变 5 5 3 乙区的日供水量为80千吨时的最优分配方案 解 因为乙区的日供水量是第 5 个约束条件的右端项 将 b5 改为 80 然后用 Lindo 6 1 进行求解得最小总的饮水管理费用 m