深圳大学期末考试试卷 开闭卷闭卷 AB卷B卷 课程编号2204030702课程名称运筹学 学分3分 22040907 命题人(签字) 审题人(签字) 2007年11月_19日 题号 三四五|六七八九|十 基本题 附加题 得分 评卷人 一、有一个大学希望将校园中6个不同建筑内的网络终端通过地下电缆连接起来,以使任 意两个终端之间都能通信,下表列出了各个终端之间的距离(单位:米)。已知连接两个终 ⌒密端的成本与它们之间的距离成正比,现要最小化总连接成本。请回答以下问题 她:1)这是一个最小支撑树问题,为什么?(5分) K2)写出算法步骤,给出终端之间的最优连接方案。(10分) 3)计算最优连接方案的总连接距离。(5分) 终端1终端2终端3终端4终端5终端6 终端1012092265149194 终端2120014117093 终端 218 终端42651702180110126 终端514993 0 终端619 116126 《运筹学》试卷卷第1页共12页
《运筹学》试卷 卷 第 1 页 共 12 页 深圳大学期末考试试卷 开/闭卷 闭卷 A/B 卷 B 卷 课程编号 2204030701 2204030702 22040907 课程名称 运筹学 学分 3 分 命题人(签字) 审题人(签字) 2007 年 11 月 19 日 题号 一 二 三 四 五 六 七 八 九 十 基本题 总分 附加题 得分 评卷人 一、有一个大学希望将校园中 6 个不同建筑内的网络终端通过地下电缆连接起来，以使任 意两个终端之间都能通信，下表列出了各个终端之间的距离(单位：米)。已知连接两个终 端的成本与它们之间的距离成正比，现要最小化总连接成本。请回答以下问题： 1）这是一个最小支撑树问题，为什么？(5 分) 2）写出算法步骤，给出终端之间的最优连接方案。(10 分) 3）计算最优连接方案的总连接距离。(5 分) _____________ ________ … 学院 专业 姓名 学号 ( 密 封 线 内 不 答 题 ) … … … …… … …… … …… …… … …… … …… … 密… … …… … …… … …… … …… …… … …… 封 …… … … …… … …… … …… …… … 线… … …… … …… … …… … …… … 线………………………………………
《运筹学》试卷卷第2页共12页
《运筹学》试卷 卷 第 2 页 共 12 页
某饲料公司生产两种类型的动物饲料:粉状饲料和颗粒饲料。生产这些饲料所需的原 料有:燕麦、玉米和糖渣。各种原料的菅养成分、可用量和价格各不相同,每种饲料产品 都需要满足一定的营养成分要求。有关数据如下所示。公司每天需要9吨颗粒饲料和12 吨粉状饲料。公司想知道各种原材料应分别使用多少,并如何进行混合,才能按要求生产 出两种饲料产品,并使总成本最小。假定混合物的总重量等于各原料的重量之和。请以代 数形式建立该问题的线性规划模型,写清楚决策变量、目标函数和约束条件。(20分) 原料营养成分百分比(%) 原料蛋白质脂肪纤维素 燕麦13671 玉米41 2.4 糖渣 原材料可用量与价格 原籽可用量(千克)价格(元/千克) 燕麦 11900 0.13 玉米23500017 糖渣 750 产成品的营养成分百分比要求(% 产品。蝥白质脂肪纤维恚一 颗粒饲料不小于95等于2不大于6 粉状饲料「等于8不大于15不小于5 《运筹学》试卷卷第3页共12页
《运筹学》试卷 卷 第 3 页 共 12 页 二、某饲料公司生产两种类型的动物饲料：粉状饲料和颗粒饲料。生产这些饲料所需的原 料有：燕麦、玉米和糖渣。各种原料的营养成分、可用量和价格各不相同，每种饲料产品 都需要满足一定的营养成分要求。有关数据如下所示。公司每天需要 9 吨颗粒饲料和 12 吨粉状饲料。公司想知道各种原材料应分别使用多少，并如何进行混合，才能按要求生产 出两种饲料产品，并使总成本最小。假定混合物的总重量等于各原料的重量之和。请以代 数形式建立该问题的线性规划模型，写清楚决策变量、目标函数和约束条件。(20 分) 原料营养成分百分比(%) 原材料可用量与价格 产成品的营养成分百分比要求(%)
《运筹学》试卷卷第4页共12页
《运筹学》试卷 卷 第 4 页 共 12 页
三、某炼油厂根据计划每季度需至少供应合同单位汽油15万吨、煤油12万吨、重油12 万吨。该厂可从俄罗斯或中东地区购买原油进行提炼。俄罗斯的原油采购成本(含运费, 下同)为200元吨,中东地区的原油采购成本为310元吨。由于油质的不同提炼出的成品 油成分也不同。有关数据如下所示。目标是最小化总采购成本。请用图解法求出最优采购 量和总采购成本,以及中东地区单位原油采购成本的最优域(结果四舍五入保留2位小数) (20分) 原油成分百分比%) 俄罗斯中东地区 汽油含量155 煤油含量2030 重油含量50 其他含量15 《运筹学》试卷卷第5页共12页
《运筹学》试卷 卷 第 5 页 共 12 页 三、某炼油厂根据计划每季度需至少供应合同单位汽油 15 万吨、煤油 12 万吨、重油 12 万吨。该厂可从俄罗斯或中东地区购买原油进行提炼。俄罗斯的原油采购成本(含运费， 下同)为 200 元/吨，中东地区的原油采购成本为 310 元/吨。由于油质的不同提炼出的成品 油成分也不同。有关数据如下所示。目标是最小化总采购成本。请用图解法求出最优采购 量和总采购成本，以及中东地区单位原油采购成本的最优域(结果四舍五入保留 2 位小数)。 (20 分)