运筹学试卷及答霸诟.doc

运筹学期末考试试卷 一、某林业公司有6片林区，为便于树木的维护和砍伐运输，需要在林区之间修建公路，并保证任意两个林区都可以通过这些公路彼此连通。已知铺设公路的费用平均为850元/米，每两片林区之间的距离如下表所示。现要最小化总铺设成本。请回答以下问题： 1）这是一个最小支撑树问题，为什么？(5分) 2）该林业公司应该如何铺设公路？写出算法步骤。(10分) 3）最小成本是多少？(结果四舍五入保留两位小数) (5分) 解答：1)因为该问题满足最小支撑树问题的所有假设①给定了网络中可供选择的边及其成本(等价于边的长度即距离)；②要插入足够多的边使图连通；③目标是要使总成本最小。 2)用避圈法求解该问题最为简单。避圈法的求解步骤为：开始选一条最小权的边，以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已被选取的边不构成圈。选边的过程如下(每条边上标记的第一个数字为长度，小括号里的数字为第几次被选中)； (c)教材给定的启发式算法：第一步，选择成本最低的备选边；第二步，在一个已经有一条边连接的节点和另一个还没有边连接的节点之间选择成本最低的备选边；第三步，重复第二个步骤，直到所有的节点都有一条边(可能会有多于一条边)与其相连，此时就得到了一个最小支撑树(当有几条边同时是成本最低的边时，任意选择一条边)。 说明：只要算法步骤正确，得到了正确结果即可给分。 3)最为：+0.7+0.8+0.9+1.2)*850=3485(千元). 避圈法求解过程图 二、有一家钢铁公司收到一份500吨造船用钢的订单。此公司储存有4种不同的原材料，都可以用于制造这种钢。有关数据如下所示。假设各种不同原材料混合在一起的总重量等于所有原材料重量之和。公司的目标是确定各种原材料的用量以使总成本最低。请以代数形式建立该问题的线性规划模型，写清楚决策变量、目标函数和约束条件。(20分) 解答：决策变量为各种不同原材料的使用量，其中铁合金1为吨，铁合金2为吨，铜合金为吨，铝合金为吨。 约束条件包括：(1)钢的产量要求 (2)资源可用量的要求 (3)品质要求 (4)决策变量的非负要求 三、某炼油厂根据计划每季度需至少供应合同单位汽油15万吨、煤油12万吨、重油12万吨。该厂可从俄罗斯或中东地区购买原油进行提炼。俄罗斯的原油采购成本(含运费，下同)为200元/吨，中东地区的原油采购成本为310元/吨。由于油质的不同提炼出的成品油成分也不同。目标是最小化总采购成本。有关电子表格模型的求解结果及其敏感性分析报告如下。请回答下列问题(结果四舍五入保留2位小数)： 1）分别写出单元格F4、F5、F6和C13的公式；(8分) 2）俄罗斯和中东地区单位原油采购成本的最优域分别是什么？(4分) 3）由于市场变动，导致中东地区原油价格上涨为400元/吨，原油采购量和原油采购总成本将有什么变化趋势(不变，变大，变小)？(4分) 4）如果市场对煤油的需求量增加为15万吨，其影子价格会有什么变化？原油采购量和原油采购总成本将有什么变化趋势(不变，变大，变小)？(4分) 求解问题的电子表格模型和敏感性报告结果 解答：1）各单元格公式如下表所示 单元格 公式 F4 =SUMPRODUCT(yyOrderNum,C4:D4) F5 =SUMPRODUCT(yyOrderNum,C5:D5) F6 =SUMPRODUCT(yyOrderNum,C6:D6) C13 =SUMPRODUCT(yyOrderNum,yyUnitPrice) 注：X表示产品品种，P表示收益，S表示销售状态及其概率。 解答：1）按照乐观决策准则，每一个决策方案的最好情况如下 方案 A B C D 最好情况下的收益 14 22 18 20 其中收益最大的方案为B，因此乐观准则下应该开发B产品； 2）按照悲观决策准则，每一个决策方案的最坏情况如下 方案 A B C D 最坏情况下的收益 12 10 10 8 其中收益最大的方案为A，因此悲观准则下应该开发A产品； 3）按照最大可能性决策准则，销售状态最有可能是中，此情况下收益最大的方案为C，因此最大可能性决策准则下应该开发C产品； 4）按照贝叶斯决策准则，每一个决策方案的期望收益如下 E(A)=14*0.3+14*0.5+14*0.2=13.6 E(B)=22*0.3+14*0.5+10*0.2=15.6 E(C)=18*0.3+16*0.5+10*0.2=15.4 E(D)=20*0.3+12*0.5+8*0.2=13.60 其中E(B)最大，因此在贝叶斯决策准则下，该厂应该开发B产品。个M/M/1的 按照M/M/1排队 2）修理铺有2个顾客的概率 3）修理铺内顾客的平均数