文档介绍：一、某林业公司有6片林区,为便于树木的维护和砍伐运输,需要在林区之间修建公路,并保证任意两个林区都可以通过这些公路彼此连通。已知铺设公路的费用平均为850元/米,每两片林区之间的距离如下表所示。现要最小化总铺设成本。请回答以下问题:1)这是一个最小支撑树问题,为什么?(5分)2)该林业公司应该如何铺设公路?写出算法步骤。(10分)3)最小成本是多少?(结果四舍五入保留两位小数)(5分)解答:1)因为该问题满足最小支撑树问题的所有假设①给定了网络中可供选择的边及其成本(等价于边的长度即距离);②要插入足够多的边使图连通;③目标是要使总成本最小。2)(a)用避圈法求解该问题最为简单。避圈法的求解步骤为:开始选一条最小权的边,以后每一步中,总从未被选取的边中选一条权最小的边,并使之与已被选取的边不构成圈(如果有两条或两条以上的边都是权最小的边,则从中任选一条)。选边的过程如下图所示(每条边上标记的第一个数字为长度,小括号里的数字为第几次被选中);(b)破圈法的求解步骤:任取一个圈,从圈中去掉权最大的边(如果有两条或两条以上的边都是权最大的边,则任意去掉其中一条)。在余下的图中,重复这个步骤,一直到图中不含圈为止(去边的同时必须保证图的连通性)。(c)教材给定的启发式算法:第一步,选择成本最低的备选边;第二步,在一个已经有一条边连接的节点和另一个还没有边连接的节点之间选择成本最低的备选边;第三步,重复第二个步骤,直到所有的节点都有一条边(可能会有多于一条边)与其相连,此时就得到了一个最小支撑树(当有几条边同时是成本最低的边时,任意选择一条边)。说明:只要算法步骤正确,得到了正确结果即可给分。3)最小成本为:(++++)*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万吨,其影子价格会有什么变化?原油采购量和原油采购总成本将有什么变化趋势(不变,变大,变小)