运筹学试卷及答案

运筹学 期末 超值

运筹学期末考试试卷

一、某林业公司有6片林区，为便于树木的维护和砍伐运输，需要在林区之间修建公路，并保证任意两个林区都可以通过这些公路彼此连通。已知铺设公路的费用平均为850元/米，每两片林区之间的距离如下表所示。现要最小化总铺设成本。请回答以下问题：

1）这是一个最小支撑树问题，为什么？(5分)

2）该林业公司应该如何铺设公路？写出算法步骤。(10分)

3）最小成本是多少？(结果四舍五入保留两位小数) (5分

)

解答：1)因为该问题满足最小支撑树问题的所有假设①给定了网络中可供选择的边及其成本(等价于边的长度即距离)；②要插入足够多的边使图连通；③目标是要使总成本最小。

2)(a)用避圈法求解该问题最为简单。避圈法的求解步骤为：开始选一条最小权的边，以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已被选取的边不构成圈(如果有两条或两条以上的边都是权最小的边，则从中任选一条)。选边的过程如下图所示(每条边上标记的第一个数字为长度，小括号里的数字为第几次被选中)；

(b)破圈法的求解步骤：任取一个圈，从圈中去掉权最大的边(如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条)。在余下的图中，重复这个步骤，一直到图中不含圈为止(去边的同时必须保证图的连通性)。

(c)教材给定的启发式算法：第一步，选择成本最低的备选边；第二步，在一个已经有一条边连接的节点和另一个还没有边连接的节点之间选择成本最低的备选边；第三步，重复第二个步骤，直到所有的节点都有一条边(可能会有多于一条边)与其相连，此时就得到了一个最小支撑树(当有几条边同时是成本最低的边时，任意选择一条边)。 说明：只要算法步骤正确，得到了正确结果即可给分。

3)最小成本为：(0.5+0.7+0.8+0.9+1.2)*850=3485(千元).

《运筹学》试卷 卷 第 1 页 共 8 页

运筹学 期末 超值

林区2

1.2(5)林区30.9(4)

林区1林区4

林区50.5(1)林区6

避圈法求解过程图

二、有一家钢铁公司收到一份500吨造船用钢的订单。此公司储存有4种不同的原材料，都可以用于制造这种钢。有关数据如下所示。假设各种不同原材料混合在一起的总重量等于所有原材料重量之和。公司的目标是确定各种原材料的用量以使总成本最低。请以代数形式建立该问题的线性规划模型，写清楚决策变量、目标函数和约束条件。(20分)

《运筹学》试卷 卷 第 2 页 共 8 页

运筹学 期末 超值

解答：决策变量为各种不同原材料的使用量，其中铁合金1为x1吨，铁合金2为x2吨，铜合金为x3吨，铝合金为x4吨。

目标函数是最小化总成本(单位：元)：minC?200x1?250x2?240x3?100x4

约束条件包括：(1)钢的产量要求

x1?x2?x3?x4?500

(2)资源可用量的要求

?x1?400?x?300?2 ?x?200?3

??x4?300

(3)品质要求

?x1?2.5%?x2?3%?x?x?x?x?2%

234?1

?x1?2.5%?x2?3%?x?x?x?x?3%

234?1

?x3?96%?x4?0.4%?0.4%??x1?x2?x3?x4 ??x3?96%?x4?0.4%?0.6%?x1?x2?x3?x4??x1?1.3%?x2?0.8%?x3?4%?x4?1.2%?1.2%?x1?x2?x3?x4??x1?1.3%?x2?0.8%?x3?4%?x4?1.2%?1.65%?x1?x2?x3?x4?

(4)决策变量的非负要求

?x1?0?x?0?2 ?x?0?3

??x4?0

三、某炼油厂根据计划每季度需至少供应合同单位汽油15万吨、煤油12万吨、重油12万吨。该厂可从俄罗斯或中东地区购买原油进行提炼。俄罗斯的原油采购成本(含运费，下同)为200元/吨，中东地区的原油采购成本为310元/吨。由于油质的不同提炼出的成品油成分也不同。目标是最小化总采购成本。有关电子表格模型的求解结果及其敏感性分析报告如下。请回答下列问题(结果四舍五入保留2位小数)：

《运筹学》试卷 卷 第 3 页 共 8 页

运筹学 期末 超值

1）分别写出单元格F4、F5、F6和C13的公式；(8分)

2）俄罗斯和中东地区单位原油采购成本的最优域分别是什么？(4分)

3）由于市场变动，导致中东地区原油价格上涨为400元/吨，原油采购量和原油采购总成本将有什么变化趋势(不变，变大，变小)？(4分)

4）如果市场对煤油的需求量增加为15万吨，其影子价格会有什么变化？原油采购量和原油采购总成本将有什么变化趋势(不变，变大，变小)？(4分)

求解问题的电子表格模型和敏感性报告结果

解答：1）各单元格公式如下表所示

F4

=SUMPRODUCT(yyOrderNum,C4:D4) 《运筹学》试卷 卷 第 4 页 共 8 页

运筹学 期末 超值

F5 F6 C13

=SUMPRODUCT(yyOrderNum,C5:D5) =SUMPRODUCT(yyOrderNum,C6:D6) =SUMPRODUCT(yyOrderNum,yyUnitPrice)

2）俄罗斯原油采购成本的最优域为[200-107,200+6.67]即[93,206.67]，中东地区原油采购成本的最优域为[310-10,310+356.67]即[300,666.67]；

3）中东地区的原油价格上涨到400元/吨，仍然在其最优域范围[300,666.67]之内，因此最优解不发生变化，即原油采购量不变。但是原油采购总成本将上升，上升量为(400-310)*21.8182=1963.64(万元)；

4）当煤油的需求量在[12-1.19,12+8]即[10.81,20]范围内时，其影子价格不会发生变化。而15在此范围内，因此其影子价格不会发生变化。由于需求量增加了，所以原油采购量和原油采购总成本都将上升。

四、某企业由于生产能力过剩，拟开发新产品，现有4个品种可供选择。市场销售有好、中、差三种情况，销售状态的概率和每一品种在不同状态下的收益如下表所示。按照以下不同的决策准则，该厂应该开发哪一种产品？ 1） 乐观准则；(5分) 2） 悲观准则；(5分) 3） 最大可能性准则；(5分) 4） 贝叶斯决策准则。(5分

)

注：X表示产品品种，P表示收益，S表示销售状态及其概率。 解答：1）按照乐观决策准则，每一个决策方案的最好情况如下

其中收益最大的方案为B，因此乐观准则下应该开发B产品； 2）按照悲观决策准则，每一个决策方案的最坏情况如下

《运筹学》试卷 卷 第 5 页 共 8 页