文档介绍：学院专业姓名学号
( 密封线内不答题)
……………………………………………………密………………………………………………封………………………………………线……………………………………线………………………………………
_____________ ________
…
深圳大学期末考试试卷
开/闭卷
闭卷
A/B卷
A卷
课程编号
2204030701
2204030702
22040907
课程名称
运筹学
学分
3分
命题人(签字) 审题人(签字) 2007 年 11 月 19 日
题号
一
二
三
四
五
六
七
八
九
十
基本题总分
附加题
得分
评卷人
一、某林业公司有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)决策变量的非负要求
三、某炼油厂根据计划每季度需至少供应合