运筹学试卷&解答
一、某林业公司有6片林区,为便于树木的维护和砍伐运输,需要在林区之 间修建公路,并保证任意两个林区都可以通过这些公路彼此连通。已知铺设 公路的费用平均为850元/米,每两片林区之间的距离如下表所示。现要最小 化总铺设成本。请回答以下问题: 1)这是一个最小支撑树问题,为什么?(5分) 2)该林业公司应该如何铺设公路?写出算法步骤。(10分) 3)最小成本是多少?(结果四舍五入保留两位小数)(5分) ~~两片林区之间的距离(公里) 1 — 1.2 0.9 2.3 2.7 1.8 2 1.2 — 1.5 3.4 2.9 0.8 3 0.9 1.5 — 0.7 1.4 2.5 4 2.3 3.4 0.7 — 1.6 3.1 5 2.7 2.9 1.4 1.6 — 0.5 6 1.8 0.8 2.5 3.1 0.5 — 解答:1)因为该问题满足最小支撑树问题的所有假设①给定了网络中可供选 择的边及其成本(等价于边的长度即距离);②要插入足够多的边使图连通; ③目标是要使总成本最小。 2)(a)用避圈法求解该问题最为简单。避圈法的求解步骤为:开始选一条最小 权的边,以后每一步中,总从未被选取的边中选一条权最小的边,并使之与 已被选取的边不构成圈(如果有两条或两条以上的边都是权最小的边,则从中 任选一条)。选边的过程如下图所示(每条边上标记的第一个数字为长度,小 括号里的数字为第几次被选中); (b)破圈法的求解步骤:任取一个圈,从圈中去掉权最大的边(如果有两条或 两条以上的边都是权最大的边,则任意去掉其中一条)。在余下的图中,重复 这个步骤,一直到图中不含圈为止(去边的同时必须保证图的连通性)。 (c)教材给定的启发式算法:第一步,选择成本最低的备选边;第二步,在一 个已经有一条边连接的节点和另一个还没有边连接的节点之间选择成本最 低的备选边;第三步,重复第二个步骤,直到所有的节点都有一条边(可能 会有多于一条边)与其相连,此时就得到了一个最小支撑树(当有几条边同时 是成本最低的边时,任意选择一条边)。 说明:只要算法步骤正确,得到了正确结果即可给分。 3)最小成本为:(0.5+0.7+0.8+0.9+1.2)*850=3485(千元). 避圈法求解过程图 二、有一家钢铁公司收到一份500吨造船用钢的订单。此公司储存有4种不 同的原材料,都可以用于制造这种钢。有关数据如下所示。假设各种不同原 材料混合在一起的总重量等于所有原材料重量之和。公司的目标是确定各种 原材料的用量以使总成本最低。请以代数形式建立该问题的线性规划模型, 写清楚决策变量、目标函数和约束条件。(20分) 造船钢的品质要求 化学元素 最低含量 最高含量 碳(C%) 2 3 铜(Cu%) 0.4 0.6 锭(Mn%) 1.2 1.65 原材料品质、可用库存量与价格 原材料 C% Cu% Mn% 可用库存量(吨) 单价(元/吨) 铁合金1 2.5H 0 1.3 400 200 铁合金2 3 0 0.8 300 250 铜合金 0 96 4 200 240 铝合金 0 0.4 1.2 300 100 解答:决策变量为各种不同原材料的使用量,其中铁合金1为叫吨,铁合金 2为心吨,铜合金为吨,铝合金为q吨。 目标函数是最小化总成本(单位:兀):min C = 200了1 + 250心+ 240扬+100^4 约束条件包括:(1)钢的产量要求 易 + 工2 + %3 + %4 = 500 (2) 资源可用量的要求 X] 1.2% I] + %2 + %3 + X4 x. xl.3% + x2 x0.8% + x3 x4% + x4 xl.2% 0 x2 >0 2 0 X4 Z 0 三、某炼油厂根据计划每季度需至少供应合同单位汽油15万吨、煤油12万 吨、重油12万吨。该厂可从俄罗斯或中东地区购买原油进行提炼。俄罗斯 的原油采购成本(含运费,下同)为200元/吨,中东地区的原油采购成本为310 元/吨。由于油质的不同提炼出的成品油成分也不同。目标是最小化总采购成 本。有关电子表格模型的求解结果及其敏感性分析报告如下。请回答下列问 题(结果四舍五入保留2位小数): 1)分别写出单元格F4、F5、F6和C13的公式;(8分) 2)俄罗斯和中东地区单位原油采购成本的最优域分别是什么?(4分) 3)由于市场变动,导致中东地区原油价格上涨为400元/吨,原油采购量和 原油采购总成本将有什么变化趋势(不变,变大,变小)?(4分) 4)如果市场对煤油的需求量增加为15万吨,其影子价格会有什么变化?原 油采购量和原油采购总成本将有什么变化趋势(不变,变大,变小)?(4分) 求解问题的电子表格模型和敏感性报告结果 A B C D _ F G H 1 2 单位原油的成品油含量 3 俄罗斯 中东地区 产出量(万吨) 最小需求量(万吨) 4 汽油含量 0.15 0.5 15 >= 15 5 煤油含量 0.2 0.3 12 >= 12 6 重油含量 0.5 0.15 16.90909091 >= 12 7 其他含量 0.15 0-5 — 8 9 原油价格(元/吨) 200 310 、 10 (0.05 11 原油采购量(万吨) 27.27272727 21.81818182 12 13 总成本(万元) 12218.18182 区域富称 区域 含义 yyTotalCost C13 原油采购总成本 yyOrderNum C11:D11 原油采购量 yyUnitPrice C9:D9 原油采购成本 cpyOutNum F4:F6 成品油产出量 cpyDemandNum H4:H6 成品油需求量 licrosoft Excel 9. 0 敏感