深圳大学期末考试试卷 开闭卷闭卷 AB卷B卷 2204030701 课程编号2204030702课程名称运筹学 学分3分 22040907 命题人(签字) 审题人(签字) 2007年11月_19日 题号 三四五|六七八九|十 基本题附加题 得分 :/评卷人 一、有一个大学希望将校园中6个不同建筑内的网络终端通过地下电缆连接起来,以使任 意两个终端之间都能通信,下表列出了各个终端之间的距离(单位:米)。已知连接两个终 ⌒密端的成本与它们之间的距离成正比,现要最小化总连接成本。请回答以下问题 她:1)这是一个最小支撑树问题,为什么?(5分) K2)写出算法步骤,给出终端之间的最优连接方案。(10分) 3)计算最优连接方案的总连接距离。(5分) 终端1终端2终端3终端4终端5终端6 终端1012092265149194 终端2120014117093 终 端392 141 218103116 终端42651702180110126 终端514993103110072 终端619416411612672 解答:1)因为该问題满足最小支撑树问题的所有假设①给定了网络中可供选择的边及其成 的本(等价于边的长度即距离):②要插入足够多的边使图连通;③目标是要使总成本最小。 2a)用避圈法求解该问题最为简单。避圈法的求解步骤为:开始选一条最小权的边,以后 每一步中,总从未被选取的边中选一条权最小的边,并使之与已被选取的边不构成圈(如 果有两条或两条以上的边都是权最小的边,则从中任选一条)。选边的过程如下图所示(每 条边上标记的第一个数字为长度,小括号里的数字为第几次被选中) (b)破圈法的求解步骤:任取一个圈,从圈中去掉权最大的边(如果有两条或两条以上的边 都是权最大的边,则任意去掉其中一条)。在余下的图中,重复这个步骤,一直到图中不 含圈为止(去边的同时必须保证图的连通性)。 (c)教材给定的启发式算法:第一步,选择成本最低的备选边:第二步,在一个已经有 《运筹学》试卷卷第1页共9页
《运筹学》试卷 卷 第 1 页 共 9 页 深圳大学期末考试试卷 开/闭卷 闭卷 A/B 卷 B 卷 课程编号 2204030701 2204030702 22040907 课程名称 运筹学 学分 3 分 命题人(签字) 审题人(签字) 2007 年 11 月 19 日 题号 一 二 三 四 五 六 七 八 九 十 基本题 总分 附加题 得分 评卷人 一、有一个大学希望将校园中 6 个不同建筑内的网络终端通过地下电缆连接起来，以使任 意两个终端之间都能通信，下表列出了各个终端之间的距离(单位：米)。已知连接两个终 端的成本与它们之间的距离成正比，现要最小化总连接成本。请回答以下问题： 1）这是一个最小支撑树问题，为什么？(5 分) 2）写出算法步骤，给出终端之间的最优连接方案。(10 分) 3）计算最优连接方案的总连接距离。(5 分) 解答：1)因为该问题满足最小支撑树问题的所有假设①给定了网络中可供选择的边及其成 本(等价于边的长度即距离)；②要插入足够多的边使图连通；③目标是要使总成本最小。 2)(a)用避圈法求解该问题最为简单。避圈法的求解步骤为：开始选一条最小权的边，以后 每一步中，总从未被选取的边中选一条权最小的边，并使之与已被选取的边不构成圈(如 果有两条或两条以上的边都是权最小的边，则从中任选一条)。选边的过程如下图所示(每 条边上标记的第一个数字为长度，小括号里的数字为第几次被选中)； (b)破圈法的求解步骤：任取一个圈，从圈中去掉权最大的边(如果有两条或两条以上的边 都是权最大的边，则任意去掉其中一条)。在余下的图中，重复这个步骤，一直到图中不 含圈为止(去边的同时必须保证图的连通性)。 (c)教材给定的启发式算法：第一步，选择成本最低的备选边；第二步，在一个已经有一 _____________ ________ … 学院 专业 姓名 学号 ( 密 封 线 内 不 答 题 ) … … … …… … …… … …… …… … …… … …… … 密… … …… … …… … …… … …… …… … …… 封 …… … … …… … …… … …… …… … 线… … …… … …… … …… … …… … 线………………………………………
条边连接的节点和另一个还没有边连接的节点之间选择成本最低的备选边;第三步,重复 第二个步骤,直到所有的节点都有一条边(可能会有多于一条边)与其相连,此时就得到了 个最小支撑树(当有几条边同时是成本最低的边时,任意选择一条边)。 说明:只要算法步骤正确,得到了正确结果即可给分。 3)最优连接方案的总连接距离为:72+92+93+103+110=470(米) 终端2 终端3 92(2) 终端1 终端 103(4) 110(5) 93(3) 终端52 72)(终端6 避圈法求解过程图 、某饲料公司生产两种类型的动物饲料:粉状饲料和颗粒饲料。生产这些饲料所需的原 料有:燕麦、玉米和糖渣。各种原料的营养成分、可用量和价格各不相同,每种饲料产品 都需要满足一定的营养成分要求。有关数据如下所示。公司每天需要9吨颗粒饲料和12 吨粉状饲料。公司想知道各种原材料应分别使用多少,并如何进行混合,才能按要求生产 出两种饲料产品,并使总成本最小。假定混合物的总重量等于各原料的重量之和。请以代 数形式建立该问题的线性规划模型,写清楚决策变量、目标函数和约束条件。(20分) 原料营养成分百分比(% 原村蛋白质脂肪纤维素 燕麦13671 玉米41 2.4 3.7 糖渣 原材料可用量与价格 原井可用量(千克)价格(元/千克 燕麦 11900 0.13 玉米 23500 糖渣 750 0.12 产成品的营养成分百分比要求(%) 《运筹学》试卷卷第2页共9页
《运筹学》试卷 卷 第 2 页 共 9 页 条边连接的节点和另一个还没有边连接的节点之间选择成本最低的备选边；第三步，重复 第二个步骤，直到所有的节点都有一条边(可能会有多于一条边)与其相连，此时就得到了 一个最小支撑树(当有几条边同时是成本最低的边时，任意选择一条边)。 说明：只要算法步骤正确，得到了正确结果即可给分。 3)最优连接方案的总连接距离为：72+92+93+103+110=470(米). 终端1 终端5 终端6 终端4 终端2 终端3 72(1) 92(2) 93(3) 103(4) 110(5) 避圈法求解过程图 二、某饲料公司生产两种类型的动物饲料：粉状饲料和颗粒饲料。生产这些饲料所需的原 料有：燕麦、玉米和糖渣。各种原料的营养成分、可用量和价格各不相同，每种饲料产品 都需要满足一定的营养成分要求。有关数据如下所示。公司每天需要 9 吨颗粒饲料和 12 吨粉状饲料。公司想知道各种原材料应分别使用多少，并如何进行混合，才能按要求生产 出两种饲料产品，并使总成本最小。假定混合物的总重量等于各原料的重量之和。请以代 数形式建立该问题的线性规划模型，写清楚决策变量、目标函数和约束条件。(20 分) 原料营养成分百分比(%) 原材料可用量与价格 产成品的营养成分百分比要求(%)
蛋白质 脂肪 纤维素 颗粒饲料不小于95等于2不大于6 粉状饲料等于8不大于1.5不小于5 解答:定义决策变量为不同产品使用的原材料的量(单位:吨),具体如下表所示 用量吨)、材料燕麦 玉米 糖渣 颗粒饲料 x21 X 粉状饲料x1x2x3 目标函数:使总成本最小(单位:千元) mnC=0.3×(x1+x12)+0.17×(x2+x2)+0.12×(x31+x32) 约束条件:(1)产成品的产量要求 12 (2)资源可用量的要求 +x2,≤0.75 (3)产成品营养成分百分比的要求 x1×136%+x21×4.1%+x1x5z95% x,+x+x x1×7% ≤6% x12×136%+x2×419%+x2×5% =8 xa+xa +x x12×7.1%+x22×2.4%+x32×0.3% ≤1.5% x1,×7%+x2,×3.7%+x32×25% ≥5% x12+x22+x (4)决策变量的非负要求 ≥0 ≥0 ≥0 0 ≥0 ≥0 《运筹学》试卷卷第3页共9页
《运筹学》试卷 卷 第 3 页 共 9 页 解答：定义决策变量为不同产品使用的原材料的量(单位：吨)，具体如下表所示 目标函数：使总成本最小(单位：千元) min 0.13 ( ) 0.17 ( ) 0.12 ( ) 11 12 21 22 31 32 C = x + x + x + x + x + x 约束条件：(1)产成品的产量要求 + + = + + = 12 9 12 22 32 11 21 31 x x x x x x (2)资源可用量的要求 + + + 0.75 23.5 11.9 31 32 21 22 11 12 x x x x x x (3)产成品营养成分百分比的要求 + + + + + + + + = + + + + + + + + = + + + + + + + + 5% 7% 3.7% 25% 1.5% 7.1% 2.4% 0.3% 8% 13.6% 4.1% 5% 6% 7% 3.7% 25% 2% 7.1% 2.4% 0.3% 9.5% 13.6% 4.1% 5% 12 22 32 12 22 32 12 22 32 12 22 32 12 22 32 12 22 32 11 21 31 11 21 31 11 21 31 11 21 31 11 21 31 11 21 31 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x (4)决策变量的非负要求 0 0 0 0 0 0 32 22 12 31 21 11 x x x x x x
、某炼油厂根据计划每季度需至少供应合同单位汽油15万吨、煤油12万吨、重油12 万吨。该厂可从俄罗斯或中东地区购买原油进行提炼。俄罗斯的原油采购成本(含运费, 下同)为200元吨,中东地区的原油采购成本为310元吨。由于油质的不同提炼出的成品 油成分也不同。有关数据如下所示。目标是最小化总采购成本。请用图解法求出最优采购 量和总采购成本,以及中东地区单位原油采购成本的最优域(结果四舍五入保留2位小数)。 (20分) 原油成分百分比(%) 俄罗斯中东地区 汽油含量15 煤油含量2030 重油含量5015 其他含量15 5 解答:设从俄罗斯采购的原油为x万吨,从中东地区采购的原油为x2万吨,则目标函数 如下(单位:万元): minC=200x1+310x 约束条件为 0.15x1+0.5x2≥15 0.2x1+0.3x2≥12 0.5x1+0.15x2≥12 x1≥0 画出如下图形 《运筹学》试卷卷第4页共9页
《运筹学》试卷 卷 第 4 页 共 9 页 三、某炼油厂根据计划每季度需至少供应合同单位汽油 15 万吨、煤油 12 万吨、重油 12 万吨。该厂可从俄罗斯或中东地区购买原油进行提炼。俄罗斯的原油采购成本(含运费， 下同)为 200 元/吨，中东地区的原油采购成本为 310 元/吨。由于油质的不同提炼出的成品 油成分也不同。有关数据如下所示。目标是最小化总采购成本。请用图解法求出最优采购 量和总采购成本，以及中东地区单位原油采购成本的最优域(结果四舍五入保留 2 位小数)。 (20 分) 解答：设从俄罗斯采购的原油为 1 x 万吨，从中东地区采购的原油为 2 x 万吨，则目标函数 如下(单位：万元)： min 200 1 310 2 C = x + x 约束条件为： + + + 0 0 0.5 0.15 12 0.2 0.3 12 0.15 0.5 15 2 1 1 2 1 2 1 2 x x x x x x x x 画出如下图形：
x2 80 (a)0.5x;+0.15x,=12 可行域 24 (b)0.2x1+0.3x2=12 (c)0.15x1+0.5x,=15 从图中可以看出,交点B是最优解,则求解下面方程组: 0.15x1+0.5x2≥15 0.2x1+0.3x2≥12 得出交点B(27.27,2182),即最优采购量为从俄罗斯采购原油2727万吨,从中东地区采 购原油2182万吨。最优采购成本为: C=200×27.27+310×2182=122182(万元) 从图中还可以看出,当目标函数线的斜率界于直线(b)和(c)的斜率之间时,最优解将保持 不变。求出(b)直线的斜率为-2/3,(c)直线的斜率为-3/10,假设中东地区单位原油采购成本 为P,则有 22003 ≤ 求得P的最优域为:[30066667] 四、某公司考虑生产一种新产品,决策者对市场销售状态进行预测的结果有三种情况:销 路好、一般、差,其概率及各种情况下增加的利润额(单位:万元)如下表所示(其中S为销 路,P为利润增长额,A为方案)。为了得到更加可靠的信息,公司可以花费06万元请咨 询公司代为进行市场调查,以确定市场的实际需求。请回答下列问题 1)采用贝叶斯决策准则,最优方案是什么?(5分) 2)画出贝叶斯决策过程的决策树。(10分) 3)计算全情报价值EⅤPI,并确定是否需要请咨询公司进行市场调查?(5分) 《运筹学》试卷卷第5页共9页
《运筹学》试卷 卷 第 5 页 共 9 页 30 100 (c)0.15x 1 +0.5x 2 =15 40 60 (b)0.2x 1 +0.3x 2 =12 24 80 (a)0.5x 1 +0.15x 2 =12 x 1 x 2 0 200x 1 +310x 2 =C A B C D 从图中可以看出，交点 B 是最优解，则求解下面方程组： + + 0.2 0.3 12 0.15 0.5 15 1 2 1 2 x x x x 得出交点 B(27.27,21.82)，即最优采购量为从俄罗斯采购原油 27.27 万吨，从中东地区采 购原油 21.82 万吨。最优采购成本为： C = 20027.27 +31021.82 =12218.2 (万元) 从图中还可以看出，当目标函数线的斜率界于直线(b)和(c)的斜率之间时，最优解将保持 不变。求出(b)直线的斜率为-2/3，(c)直线的斜率为-3/10，假设中东地区单位原油采购成本 为 P，则有 10 200 3 3 2 − − − P 求得 P 的最优域为：[300,666.67]。 四、某公司考虑生产一种新产品，决策者对市场销售状态进行预测的结果有三种情况：销 路好、一般、差，其概率及各种情况下增加的利润额(单位：万元)如下表所示(其中 S 为销 路，P 为利润增长额，A 为方案)。为了得到更加可靠的信息，公司可以花费 0.6 万元请咨 询公司代为进行市场调查，以确定市场的实际需求。请回答下列问题： 1）采用贝叶斯决策准则，最优方案是什么？(5 分) 2）画出贝叶斯决策过程的决策树。(10 分) 3）计算全情报价值 EVPI，并确定是否需要请咨询公司进行市场调查？(5 分) 可行域