运筹学试卷及答案.doc

运筹学期末考试试卷一、某林业公司有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(千元).避圈法求解过程图二、有一家钢铁公司收到一份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分)求解问题的电子表格模型和敏感性报告结果0.05解答：1）各单元格公式如下表所示单元格公式F4=SUMPRODUCT(yyOrderNum,C4:D4)F5=SUMPRODUCT(yyOrderNum,C5:D5)F6=SUMPRODUCT(yyOrderNum,C6:D6)C13=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）按照乐观决策准则，每一个决策方案的最好情况如下方案ABCD最好情况下的收益14221820其中收益最大的方案为B，因此乐观准则下应该开发B产品；2）按照悲观决策准则，每一个决策方案的最坏情况如下方案ABCD最坏情况下的收益1210108其中收益最大的方案为A，因此悲观准则下应该开发A产品；3）按照最大可能性决策准则，销售状态最有可能是中，此情况下收益最大的方案为C，因此最大可能性决策准则下应该开发C产品；4）按照贝叶斯决策准则，每一个决策方案的期望收益如下E(A)=14*0.3+14*0.5+14*0.2=13.6E(B)=22*0.3+14*0.5+10*0.2=15.6E(C)=18*0.3+16*0.5+10*0.2=15.4E(D)=20*0.3+12*0.5+8*0.2=13.60其中E(B)最大，因此在贝叶斯决策准则下，该厂应该开发B产品。五、某自行车修理铺有师傅1人，来修理自行车的顾客按泊松分布到达，平均每小时3人，自行车修理时间服从指数分布，平均需要15分钟。请计算：1） 修理铺空闲时间的概率；(5分)2） 修理铺有2个顾客的概率；(5分)3） 修理铺内顾客的平均数；(5分)4） 顾客在修理铺的平均逗留时间。(5分)解答：这个一个M/M/1的排队模型，其中的参数如下按照M/M/1排队模型的有关结论有：1）修理铺空闲时间的概率2）修理铺有2个顾客的概率3）修理铺内顾客的平均数4）顾客在修理铺的平均逗留时间六、（附加题）有一家公司生产玻璃纤维，产量以立方米为单位计算。这家公司希望对未来6个星期的生产进行规划。产能有一定的上限，且在每个时期产能的上限都不同。规划所覆盖的整个期间的每周需求量都已知。不同时期的生产和储存的费用也不同。有关数据如下所示。公司考虑应该采取怎样的生产和储存方案，以使总成本最小。请回答下列问题：1）该问题可以看成运输问题吗？为什么？(5分)2）以代数形式建立该问题的线性规划模型，写清楚决策变量、目标函数和约束条件。(15分)3）草拟一张该问题的线性规划电子表格模型的草图，列出数据单元格、可变单元格、输出单元格、目标单元格及约束条件，并写出有关单元格的公式。(10分)解答：1）该问题可以看成运输问题，因为它符合运输问题的特征：有出发地(生产)；有目的地(需求)；出发地有供应量(产能)；目的地有需求量；存在单位供应成本(生产成本+存储成本)，总供应成本是单位供应成本的线性函数；目标是使总供应成本最小。2）决策变量：，i和j属于1,2,3,4,5,6；定义如下变量：则目标函数为：约束条件为：3）如下图所示，浅蓝色为数据单元格，黄色为可变单元格，白色为输出单元格，橘红色为目标单元格。运筹学试卷 卷 第 8 页 共 8 页