2012年运筹学期末考试复习题(含答案)

2012 年 01 学期运筹学期末考试复习题 第 1 页 第一章第一章 线性规划问题及单纯形法线性规划问题及单纯形法 书 书 11 面 例面 例 1 美佳公司计划制造美佳公司计划制造 两种家电产品 已知各制造一件时分别占用的设备两种家电产品 已知各制造一件时分别占用的设备 A B 的的 台时 调试工序及每天可用于这两种家电的能力 各售出一件时的获利情况 如下表 问该公司应制造两种台时 调试工序及每天可用于这两种家电的能力 各售出一件时的获利情况 如下表 问该公司应制造两种 家电各多少件 使获取的利润为最大 家电各多少件 使获取的利润为最大 项目项目 每天可用能力每天可用能力 设备设备 A0515 设备设备 B6224 调试工序调试工序115 利润利润21 问题问题 1 用变量用变量 x1 和和 x2 分别表示美佳公司制造家电分别表示美佳公司制造家电 和和 的数量 的数量 书 书 11 面 例面 例 2 捷运公司在下一年度的捷运公司在下一年度的 1 4 月的月的 4 个月内拟租用仓库堆放物资 已知各月份所需仓个月内拟租用仓库堆放物资 已知各月份所需仓 库面积列于下表 仓库租借费用随合同期而定 期限越长 折扣越大 具体数字见表 租界仓库的合同每月库面积列于下表 仓库租借费用随合同期而定 期限越长 折扣越大 具体数字见表 租界仓库的合同每月 初都可以办理 每份合同具体规定租用面积和期限 因此该厂课根据需要 在任何一个月初办理租借合同 初都可以办理 每份合同具体规定租用面积和期限 因此该厂课根据需要 在任何一个月初办理租借合同 每次办理时可签一份合同 也可签若干份租用面积和租借期限不同的合同 试确定该公司签订租借合同的最每次办理时可签一份合同 也可签若干份租用面积和租借期限不同的合同 试确定该公司签订租借合同的最 优决策 目的是使所付租借费用最小 优决策 目的是使所付租借费用最小 单位 单位 100m2 月份月份1234 所需仓库面积所需仓库面积15102012 合同租借期限合同租借期限1 个月个月2 个月个月3 个月个月4 个月个月 合同期内的租费合同期内的租费2800450060007300 问题问题 2 用变量用变量 xij 分别表示捷运公司在第分别表示捷运公司在第 i 个月初签订的租借期为个月初签订的租借期为 j 个月的仓库面积的合同个月的仓库面积的合同 2012 年 01 学期运筹学期末考试复习题 第 2 页 例例 3 工厂工厂 A1 和和 A2 生产某种物资 由于该种物资供不应求 故需要再建一家工厂 相应的建厂方案有生产某种物资 由于该种物资供不应求 故需要再建一家工厂 相应的建厂方案有 A3 和和 A4 两个 这种物资的需求地有两个 这种物资的需求地有 B1 B2 B3 和和 B4 四个 各工厂年生产能力 各地年需求量 各厂至四个 各工厂年生产能力 各地年需求量 各厂至 各地的单位物资运费各地的单位物资运费 cij 见下表 见下表 工厂工厂 A3 或或 A4 开工后 每年的生产费用估计分别为开工后 每年的生产费用估计分别为 1200 万元或万元或 1500 万元 现要决定应该建设工厂万元 现要决定应该建设工厂 A3 还还 是是 A4 才能使今后每年的总费用最少 才能使今后每年的总费用最少 B1B2B3B4生产能力生产能力 A12934400 A28357600 A37612200 A44525200 需求量需求量350400300150 书 书 15 面 例面 例 4 例例 5 例例 6 2012 年 01 学期运筹学期末考试复习题 第 3 页 例例 7 固定费用问题固定费用问题 有三种资源被用于生产三种产品 资源量 产品单件可变费用及售价 资源单耗量及组织三种产品生产有三种资源被用于生产三种产品 资源量 产品单件可变费用及售价 资源单耗量及组织三种产品生产 的固定费用见表 要求制定一个生产计划 使得总收益最大 的固定费用见表 要求制定一个生产计划 使得总收益最大 资源量资源量 A 2 4 8 500 B 2 3 4 300 C 1 2 3 100 单件可变费用单件可变费用 4 5 6 固定费用固定费用 100 150 200 单件售价单件售价 8 10 12 松弛问题 max z x1 x2 x1 x2 x3 1 s t 3x1 x2 x4 4 x1 x2 x3 x4 0 XB X1 X2 X3 X4 b X1 1 0 1 4 1 4 3 4 X2 0 1 3 4 1 4 7 4 r 0 0 1 2 1 2 例例 8 max z 3x1 2x2 5x3 X1 X2 X3 Z a b c d x1 2x2 x3 2 0 0 0 0 0 x1 4x2 x3 4 0 1 0 2 s t x1 x2 3 0 1 1 3 4x2 x3 6 0 0 1 5 5 x1 x2 x3 0 或或 1 1 0 0 3 1 1 0 1 1 1 1 6 1 0 1 8 8 X1 1 X2 0 X3 1 Z 8 例例 9 min z 3 x1 7x2 x3 x4 2x1 x2 x3 x4 1 x1 x2 6x3 4x4 8 s t 5x1 3x2 x4 5 x1 x2 x3 x4 0 或或 1 割平面割平面 3 4X 3 4X3 3 1 4x 1 4x4 4 3 4 3 4 2012 年 01 学期运筹学期末考试复习题 第 4 页 例例 10 一笔画问题一笔画问题 FGHFEHIDCBEDBAF 例例 11 哪些是欧拉图哪些是欧拉图 例例 12 求最小生成树求最小生成树 例例 13 狄克斯特拉算法狄克斯特拉算法 2012 年 01 学期运筹学期末考试复习题 第 5 页 例例 14 求最短路径求最短路径 V1 V4 V5 V7 25 V1 V4 V5 21 V1 V3 V6 20 V1 V