运筹学课程设计指导书

中中 国国 计计 量量 学学 院院 20092009 20102010 学年学年 第第 2 2 学期学期 运筹学课程设计 指导书 二二级级学学院院 部部 中中心心 经经济济与与管管理理学学院院 学学 科科 专专 业业 管理科学与工程管理科学与工程 课课 程程 名名 称称 运筹学课程设计运筹学课程设计 授授 课课 对对 象象 0808 市场营销市场营销 1 1 1 1 教教 材材 名名 称称 无无 20102010 年年 6 6 月月 2828 日日 一 课程设计的地位与任务一 课程设计的地位与任务 运筹学是财务管理专业的专业基础课程 为提高学生应用运筹学方法与计算机软件的 独立工作能力 运筹学课程设计本着 突出建模 结合软件 加强应用 的指导思想 以 学生自己动手为主 利用 运筹学 课程所学过的基础理论和基本方法 对一些实际题目 进行建模 再运用计算机软件进行求解 对解进行检验和评价 写出课程设计报告 从而 巩固学生的理论知识和提高学生运用知识的能力 二 课程设计的内容和基本要求二 课程设计的内容和基本要求 一 一 选题建模选题建模 学生选取指导教师提供需要解决的众多实际问题中相应问题 进行分析建模 二 二 程序设计 运用 程序设计 运用 在建模的基础上 要求学生编写或选取适当的工具解决问题 三 三 报告答辩报告答辩 根据要求编写课程设计报告 三 教学安排与教学方法三 教学安排与教学方法 本课程设计要求学生根据提供的实际问题中抽取相应的题目 通过具体的计算机语言 编写程序 求解问题 然后利用熟悉常用的运筹学软件 如 WINQSB LINDO 管理运筹 学软件等 对问题进行验证 本课程设计分三个阶段 选题建模 程序设计 运用 报告 答辩 具体进度安排如下 教学时间教学时间教学内容教学内容学学 时时教学方式教学方式 第一天 上 软件操作介绍 4 课堂教学 第一天 下 上机实践上机辅导 第二天 上 选题建模课堂教学 第二天 下 上机实践上机辅导 第三天 上 上机实践上机辅导 第三天 下 上机实践 10 上机辅导 第四天 上 上机实践上机辅导 第四天 下 上机实践上机辅导 第五天 报告答辩 2 课堂教学 总 计 16 四 课程设计内容四 课程设计内容 课程设计案例课程设计案例软件模块软件模块设计小组设计小组 案例 C 1 生产计划问题线性规划与整数规划 线性规划 2 3 组 案例 C 2 配料问题 线性规划与整数规划 灵敏度分析 2 3 组 案例 C 3 证券网点分配 线性规划与整数规划 整数规划 2 3 组 案例 C 4 工程建设问题 目标规划2 3 组 案例 C 6 购车问题网络模型2 3 组 案例 C 6 购车问题动态规划2 3 组 案例 C 7 房屋拆迁还建问题 运输问题 指派问题 2 3 组 五 考核方式与成绩评定标准五 考核方式与成绩评定标准 考核方式考核方式 编写课程设计报告 设计报告的主要内容设计报告的主要内容 封面 课程设计题目 课程设计内容 学生姓名 班级学号 专业 指导姓名 日期 问题描述 建模分析 程序设计 结果分析 设计报告编写的基本要求设计报告编写的基本要求 一律按照学校统一标准编写 成绩评定成绩评定 平时成绩占 30 程序设计 运用 报告占 50 报告答辩 20 评定成 绩为优 良 中 及格与不及格五个等级 六 推荐教材与主要参考书六 推荐教材与主要参考书 推荐教材 熊伟主编 运筹学 机械工业出版社 2005 1 运筹学 教材编写组 运筹学 清华大学出版社 1990 1 主要参考书 1 韩伯棠主编 管理运筹学 高等教育出版社 2005 6 2 胡运权主编 运筹学教程 第二版 清华大学出版社 2003 3 朱求长主编 运筹学及其应用 武汉大学出版社 2003 1 4 赵可培主编 运筹学 上海财经大学出版社 2002 7 5 罗明安主编 运筹学 经济管理出版社 1999 1 6 薛秀谦 范宝谦 李永淇主编 运筹学 系统模型 原理 方法 中国矿业大 学出版社 1998 6 附录附录 案例案例 1 某厂排气管车间生产计划的优化分析某厂排气管车间生产计划的优化分析 1 问题的提出 问题的提出 排气管作为发动机的重要部件之一 极大地影响发动机的性能 某发动机厂排气管车 间长期以来 只生产一种四缸及一种六缸发动机的排气管 由于其产量一直徘徊不前 致 使投资较大的排气管生产线 一直处于吃不饱状态 造成资源的大量浪费 全车间设备开 动率不足 50 为了充分发挥车间的潜力 该车间在厂部的大力协助下主动出击 一方面争取到了工 厂自行开发的特殊机型排气管生产权 另一方面瞄准国际市场以较低的价格和较高的质量 赢得了世界两大著名汽车公司 CUMMINS 和 FORD 的信任 成为其 8 种型号排气管最具 竞争实力的潜在供应商 如果这 8 种排气管首批出口进入国际市场畅销的话 后续订单将 会成倍增长 而且两大公司有可能逐步减少其它公司的订单 将其它型号排气管全部转移 到该车间生产 针对这种状况 该车间组织工程技术人员对 8 种排气管的产品图纸进行了评审 进行 了工艺设计和开发 编排工艺流程图 进行 PFMEA 分析和编制控制计划 进行样品试制 同时对现生产能力和成本进行了认真细致的核算和预测工作 如何调整当前的生产计划 是否增加设备或改造生产线 其它类型新产品需要多长时间才能投入生产等一系列问题尚 缺乏科学的 定量的依据 而目前厂部和车间最关心的资源问题 主要是加工设备的生产 能力 一位工商管理硕士 MBA 毕业的厂部管理人员马上想到 这是一个合理利用有限 资源 如何制定生产计划使产出最大的优化问题 理论上可以用线性规划方法解决 2 生产概况及有关资料 生产概况及有关资料 1 车间概况 该车间按两班制生产 每班 8 小时 标准工作日为 22 天 车间现有员工 30 名 其中 生产工人 27 人 每月安排职工政治学习及业务培训时间为 4 小时 进行文明生产等非生产 性工作每月平均 2 小时 人 月 排气管工废按产量的 1 计算 料废按 2 计算 车间生产 工人工作时间按 44 小时 人 周 每月 4 周 进行考核 2 生产状况 该车间排气管生产为 10 道工序 分别在不同的 10 类机床上进行加工 每种排气管所 占用的设备时间如表 C 1 所示 各种排气管的成本构成如表 C 2 所示 目前 由于市场不景气 排气管生产的上工序即铸造厂产能富裕 只要资金到位该厂可 准时 足量供货 而且品种可以保证 而出口排气管外商的的资金可以及时到位 并且许 诺如果需要可预付 50 以上的预付款 只不过对某些产品提出了特殊要求 即第一种 第 七种排气管月产量均不能低于 10000 第三种不能低于 5000 月 第六种排气管产量不高于 60000 月 第二和第四种排气管配对使用 但由于第二种排气管使用中易损 故每月必须 多生产 3000 根 因此原材料来源和资金不足是增加生产的制约因素 制约该车间排气管产 量的主要是设备计划外停工及基本生产工人工时 即设备与人力资源 根据以往经验 各 设备加工能力见表 C 3 表表 C 1 8 种排气管设备消耗时间 单位 台时种排气管设备消耗时间 单位 台时 1000 件 件 产品 时间 设备 12345678 1 平面铣床44 54 85 85 24 04 65 6 2 卧铣床3 94 54 35 04 94 45 14 8 3 组合钻5 95 85 76 36 56 06 66 4 4 单面铣床3 53 03 74 03 83 04 13 4 5 攻丝床5 86 25 76 46 36 06 56 2 6 精铣床5 55 74 76 05 95 26 25 6 7 扩孔钻床3 93 84 04 13 73 54 13 6 8 摇臂钻床4 14 04 04 34 23 84 34 3 9 去毛刺机2 52 92 73 03 02 53 12 8 10 清洗机2 82 92 13 23 02 53 23 0 总计41 943 341 748 146 540 947 845 7 表表 C 2 8 种排气管成本构成表 单位 元种排气管成本构成表 单位 元 根 根 产品 项目 12345678 毛坯价格981049411210697104102 辅料消耗22222222 动能消耗1010101010101010 工具等消耗10131214158911 管理费用1 4551 0991 211 441 1881 22651 3081 56 税收151614 81716 514 515 615 5 售价150160 1149172166145 6157 8155 8 利润 元 13 54514 00114 9915 5615 31212 873515 89213 74 注 表中售价为含税价 表表 C 3 设备加工能力一览表设备加工能力一览表 设备 台数 台 标准工作 日 日 月 标准工作 日长度 时 日 台均维修 保养时间 时 月 月可利用工 时 实际工时 99 1 平面铣床42216413921378 2 卧铣床42216214001386 3 组合钻床62216520822061 4 单面铣床222162700693 5 攻丝床62216420882067 6 精铣床42216313961382 7 扩孔钻床42216813761362 8 摇臂钻床42216613841370 9 去毛刺机222162700693 10 清洗机222162700693 根据以上资料 请你完成下列 3 和 4 两项工作 3 制定利润最大的生产计划 制定利润最大的生产计划 1 建立线性规划数学模型 2 用 WinQSB 软件求解 3 写出各种产品月生产量及月总利润 4 结果分析 结果分析 1 分析各种资源的利用情况 根据线性规划得到的结果 如何重新调整资源 2 利用影子价格分析各资源对利润的边际贡献 分析哪些是影响增加利润的关键设备 3 如果企业现有一订单 各种排气管的需要量是 15000 5000 5000 3000 15000 60000 10000 60000 根 正常时间内 1 个月能否完成 任务 如果不能完成 哪些资源需要加班多少时间 假定加班不额外增加成本 4 对现有资源和生产能力进行分析 提出你对排气管车间整个计划的看法和建议 案例案例 2 配料问题配料问题 某饲料公司生产肉用种鸡配合饲料 每千克饲料所需营养质量要求如表 C 4 所示 表表C 4 营养成分肉用种鸡国家标准肉用种鸡公司标准产蛋鸡标准 代谢能2 7 2 8Mcal kg 2 7Mcal kg 2 65Mcal kg 粗蛋白135 145g kg135 145g kg 151g kg 粗纤维 50g kg 45g kg 20g kg 赖氨酸 5 6g kg 5 6g kg 6 8g kg 蛋氨酸 2 5g kg 2 6g kg 6g kg 钙23 40g kg 30g kg 33g kg 有效磷4 6 6 5g kg 5g kg 3g kg 食盐3 7g kg3 7g kg3g kg 公司计划使用的原料有玉米 小麦 麦麸 米糠 豆饼 菜子饼 鱼粉 槐叶粉 DL 蛋 氨酸 骨粉 碳酸钙和食盐等 12 种原料 各原料的营养成分含量及价格见表 C 5 表表C 5 变量原料 单 价 元 kg 代谢 能 Mcal kg 粗 蛋 白 g kg 粗 纤 维 g kg 赖 氨 酸 g kg 蛋 氨 酸 g kg 钙 g kg 有 效 磷 g kg 食盐 g kg x1玉米0 683 3578162 31 20 70 3 x2小麦0 723 08114223 41 70 60 34 x3麦麸0 231 78142956 02 30 310 0 x4米糠0 222 10117726 52 71 013 0 x5豆饼0 372 404024924 15 13 25 0 x6菜饼0 321 623601138 17 15 38 4 x7鱼粉1 542 80450029 111 86327 x8槐叶粉0 381 6117010810 62 24 04 0 x9DL met23 0980 x10骨粉0 56300140 x11碳酸钙1 12400 x12食盐0 421000 公司根据原料来源 还要求 1 吨配合饲料中原料的含量为 玉米不低于 400 kg 小麦 不低于 100 kg 麦麸不低于 100 kg 米糠不超过 150 kg 豆饼不超过 100 kg 菜子饼不低于 30 kg 鱼粉不低于 50 kg 槐叶粉不低于 30 kg DL 蛋氨酸 骨粉 碳酸钙适量 1 按照肉用种鸡公司标准 求 1 千克配合饲料中每种原料各配多少成本最低 建立数学 模型并求解 2 按照肉用种鸡国家标准 求 1 千克配合饲料中每种原料各配多少成本最低 3 公司采购了一批花生饼 单价是 0 6 元 kg 代谢能到有机磷的含量分别为 2 4 38 120 0 0 92 0 15 0 17 求肉用种鸡成本最低的配料方案 4 求产蛋鸡的最优饲料配方方案 5 公司考虑到未来鱼粉 骨粉和碳酸钙将要涨价 米糠将要降价 价格变化率都是原价 的 r 试对两种产品配方方案进行分析 说明 以上 5 个问题独立求解和分析 如在问题 3 中只加花生饼 其它方案则不加 花生饼 案例案例 3 证券营业网点设置问题证券营业网点设置问题 证券公司提出下一年发展目标是 在全国范围内建立不超过 12 家营业网点 1 公司为此拨出专款 2 2 亿元人民币用于网点建设 2 为使网点布局更为科学合理 公司决定 一类地区网点不少于 3 家 二类地区网点不少 于 4 家 三类地区网点暂不多于 5 家 3 网点的建设不仅要考虑布局的合理性 而且应该有利于提升公司的市场份额 为此 公 司提出 待 12 家网点均投入运营后 其市场份额应不低于 10 4 为保证网点筹建的顺利进行 公司审慎地从现有各部门中抽调出业务骨干 40 人用于筹 建 分配方案为 一类地区每家网点 4 人 二类地区每家网点 3 人 三类地区每家网点 2 人 5 依据证券行业管理部门提供的有关数据 结合公司的市场调研 在全国选取 20 个主要 城市并进行分类 每个网点的平均投资额 bj 年平均利润 cj 及交易量占全国市场平 均份额 rj 如表 C 6 所示 试根据以上条件进行分析 公司下一年应选择哪些城市进行网点建设 使年度利润总 额最大 表表C 6 地区 类别 拟入选城市名称编 号 投资额 万元 bj 利润额 万元 cj 市场平均份额 rj 上海125008001 25 深圳224007001 22 北京323007001 20 一 类 地 区 广州422006501 00 大连520004500 96 天津620005000 98 重庆718003800 92 武汉818004000 92 杭州917503300 90 成都1017003000 92 南京1117003200 88 沈阳1216002200 82 二 类 地 区 西安1316002000 84 福州1415002200 86 济南1514002000 82 哈尔滨1614001700 75 三 类 地 区 长沙1713501800 78 海口1813001500 75 石家庄1913001300 72 郑州2012001200 70 案例案例 4 工程建设与财政平衡决策问题工程建设与财政平衡决策问题 阅读下列案例 完成计算和分析 某市政府为改善其基础设施 在近 3 年内要着手如下 5 项工程的建设 按重要性排序 的工程建设项目名称及造价如表 C 7 所示 表表 C 7 项目项目名称造价 万元 1公路 1b1 2大桥b2 3公路 2b3 4水厂b4 5供水管道b5 该市政府的财政收入主要来自国家财政拨款 地方税收和公共事业收费 3 年内该三 项总收入分别估计为 e1 e2和 e3 除此之外就靠向银行贷款和发行债券 3 年中可贷款的 上限为 U11 U12和 U13 年利率为 g 可发行债券的上限为 U21 U22和 U23 年利率为 f 银行还贷款期限为 1 年 假定贷款在年初付出 债券则由下年起每年按一定比例 r 归还部 分债主的本金 市政府应如何作出 3 年的投资决策 设 x1t t 1 2 3 为第 t 年向银行贷款数 x2t t 1 2 3 为第 t 年发行债券数 yit i 1 2 5 t 1 2 3 为项目 i 在第 t 年的完工率 投资比例 见表 C 8 表 C 8 名称第一年第二年第三年 银行贷款 万元 发行债券 万元 x11 x21 x12 x22 x13 x23 工程项目 1 总完工率y11y12y13 工程项目 2 总完工率y21y22y23 工程项目 3 总完工率y31y32y33 工程项目 4 总完工率y41y42y43 工程项目 5 总完工率y51y52y53 除上述变量外 为了写出平衡式 引进第 1 年的起始财政平衡变量 z0和每年末的财 政平衡变量 z1 z2和 z3 1 决策变量 为了列出目标规划决策模型 决策变量如表 C 8 所示 2 约束和目标 注意问题中有的目标 例如历年财政平衡 实际上是硬约束 其中不含 偏差变量 因此引入松弛变量 si i 1 2 7 作等式的平衡 3 财政平衡约束条件 变量的上限限制和财政平衡目标 变量包括决策变量 财政平衡变量和保证财政平衡的 人工变量 表 C 8 所列变量都有上界限制的 把这些有上界约束的变量写成目标形式 其中只须引进负偏差变量 njt 对平衡变量应使 z0为零 使 zl z2 z3为正值 故除 z0外其 它平衡变量都引进了正偏差变量 而且把使 z0为零和使其它平衡变量为正作 硬约束 的 规定 因此有 3 1 04 45 1 21 2 3 11 2 51 2 3 11 2 5 01 0 1 2 33 jtjtjt itit iti t kkk xnUjt ydit ydi zs zsdk 贷款 债券平衡约束 各项目每年完工率平衡约束 完工率平衡约束 第年初财政平衡约束 年财政平衡约束 式中 为正偏差变量 s4 k是松弛变量 等价于负偏差变量 z0是第 1 年年初的可用资 5 k d 金 假设 z0 0 则约束 z0 s4 0 可以去掉 zk是第 k 年年末剩余 k 1 年年初可用 资 金 所有变量非负 根据财政平衡的意义 可列出 3 年中每年的财政平衡约束条件 即 该年银行贷款 该年发行债券 该年财政收入 该年各项工程拨款 该年银行还 款 该年债券还款 该年银行贷款付息 该年债券付息 起始平衡 最终平衡 0 则有 第一年 0 11021 5 1 112111 szzfxybexx i ii 第二年 0 1 221222121 1121111 5 1 222212 szzfxrxxff gxrxxyybexx i i ii 第三年 0 1 2 1 3322322222121 2 1222122 5 1 332313 szzfxrxxffrxxff gxrxxyybexx i i ii 4 目标函数 对问题目标函数的要求有如下几点 硬约束为 1 级目标 以首先保证各年财政平衡 这可使这些约束条件的相应松弛变量 的和为最小 力图尽量获得银行贷款和发行债券 以解决工程建设的资金问题 保证头两项工程的优先完成 按重点顺序加权 按重点顺序加权 抓紧后三项工程的建设 争取每个项目在 3 年内都完工 使各年最终财政平衡变量为最小 因此 目标函数可列出 73333 1212312 11111 33353 4345565 11111 min 2 32 ktttt ktttt tttik tttik pspnnpdd pdddpdpd 整理得到目标规划数学模型 73333 1212312 11111 33353 4345565 11111 min 2 32 ktttt ktttt tttik tttik pspnnpdd pdddpdpd 3 1 35 1 21 2 3 11 2 51 2 3 11 2 5 0 1 2 3 jtjtjt itit iti t kkk xnUjt ydit ydi zsdk 5 11121111 1 55 121112 11 21221222 55 2 23121321 11 2223233 1 1 1 1 1 1 1 2 1 1 1 1 ii i iiii ii iiii ii b yxf xzse b yb yg xx rr ffxf xzzse b yb yg xxrr ffx rr ffxf xzzs 3 e 所有变量非负 要求 1 给定具体数据 b1 700 b2 500 b3 800 b4 400 b5 680 e1 700 e2 900 e3 1200 U11 300 U12 400 U13 450 U21 300 U22 350 U23 350 f 0 055 g 0 05 r 0 2 用软 件求满意解 2 对结果进行分析 列出 3 年详细的项目投资计划 资金分配表和平衡表 资金是 否有缺口 写出分析报告 案例案例 5 综合生产计划编制综合生产计划编制 汽车制造厂现有一个 6 个月的产品生产任务 产品需要在车加工车间生产 每件产品 需要 5 小时加工 有关资料如下 1 车间现有 200 名工人 每天正常工作 8 小时 每小时的工资 8 元 2 如果正常时间不能完成任务可以加班生产 每小时的工资 10 元 每位工人每月加班 时间不得超过 60 小时 3 工厂可以提供原材料外协加工 每月最多 1000 件 每件产品的加工费第 1 2 个月为 85 元 第 3 6 月份为 80 元 4 可以延期交货 但 6 个月的总生产任务必须完成 每件产品延期一个月必须支付延期 费用 8 元 5 已知第 1 月月初有 300 件库存产品 为了预防产品需求量的波动 工厂决定每月月末 最少要库存一定数量的产品 安全库存量 每月最大库存量不超过 800 件 每件产品一个 月的储存费为 1 2 元 6 如果当月工人不够可以雇佣新工人 对雇佣工人除了支付工资外还要额外支付技术培 训费 800 元 如果当月工人有剩余 工厂必须支付每