深圳大学期末考试试卷 开闭卷闭卷 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 分) 可行域
销路和利润增长额预测情况 S好(s 一般s 差(53) 25 045 生产(a1 15 不生产(a2) 解答:1)贝叶斯决策准则下各方案的期望收益为 E(a1)=15×0.25+1×0.3+(-6)×045=1.35 E(a2)=0 E(a1)>E(a2),因此应该生产该新产品。 2)贝叶斯决策过程的决策树如下所示: 0.25 好 生产 一般 差 1.35 0.25 不生产 一般 0.45 差 3)全情报价值为 EIPⅠ=EP(完全情报)-EP(无情报) (15×0.25+1×0.3+0×045)-1.35 27(万元) 因为EVPⅠ=27>06,所以值得请咨询公司进行市场调查。 五、某电话亭有一部电话,来打电话的顾客数服从泊松分布,相继两个人到达间隔时间的 平均值为10分钟,通话时间服从指数分布,平均数为3分钟。试计算 《运筹学》试卷卷第6页共9页
《运筹学》试卷 卷 第 6 页 共 9 页 销路和利润增长额预测情况 解答：1）贝叶斯决策准则下各方案的期望收益为 ( ) 0 ( ) 15 0.25 1 0.3 ( 6) 0.45 1.35 2 1 = = + + − = E a E a ( ) ( ) E a1 E a2 ，因此应该生产该新产品。 2）贝叶斯决策过程的决策树如下所示： 3）全情报价值为 2.7( ) (15 0.25 1 0.3 0 0.45) 1.35 ( ) ( ) 万元 完全情报 无情报 = = + + − EVPI = EP − EP 因为 EVPI=2.7>0.6，所以值得请咨询公司进行市场调查。 五、某电话亭有一部电话，来打电话的顾客数服从泊松分布，相继两个人到达间隔时间的 平均值为 10 分钟，通话时间服从指数分布，平均数为 3 分钟。试计算：
1)电话亭内至少有一个顾客的概率;(5分) 2)等待服务的顾客平均数;(5分) 3)平均等待服务时间:(5分) 4)在电话亭内消耗5分钟以上的概率。(5分) 解答:这个一个MM1的排队模型,其中的参数如下 =60/10=6(人/小时) =60/3=20(人/小时) p=4/=6/20=03 按照MM1排队模型的有关结论有: 1)电话亭内至少有一个顾客的概率 P{L≥1}=1-P{L=0} 1-(1-p) 0.3 2)等待服务的顾客平均数 0.3 ≈0.13(人) 3)平均等待服务时间 W 60(分钟) 3(分钟 4)在电话亭内消耗5分钟以上的概率 PW> 六、(附加题)有一家公司生产儿童自行车,明年上半年的销售量预测如表所示。公司具 有每月生产30千辆的能力。通过加班,每月的产量还可以提高50%,但是自行车的生产 成本也将从30元提高到40元。对于库存中的每辆自行车,在每个月底都需要支出5元的 存储费用。假设现在是1月1日。目标是要安排每月的生产和储存计划,在满足需求的同 时最小化总成本。请回答下列问题: 《运筹学》试卷卷第7页共9页
《运筹学》试卷 卷 第 7 页 共 9 页 1）电话亭内至少有一个顾客的概率；(5 分) 2）等待服务的顾客平均数；(5 分) 3）平均等待服务时间；(5 分) 4）在电话亭内消耗 5 分钟以上的概率。(5 分) 解答：这个一个 M/M/1 的排队模型，其中的参数如下 / 6 / 20 0.3 60 / 3 20( / ) 60 /10 6( / ) = = = = = = = 人 小时 人 小时 按照 M/M/1 排队模型的有关结论有： 1)电话亭内至少有一个顾客的概率 0.3 1 (1 ) { 1} 1 { 0} = = = − − = − = P L P L 2)等待服务的顾客平均数 0.13( ) 1 0.3 0.3 1 2 2 人 − = − = Lq 3)平均等待服务时间 1.3( ) 60( ) 20 (20 6) 6 ( ) 分钟 分钟 − = − = Wq 4)在电话亭内消耗 5 分钟以上的概率 0.19 } 60 5 { 60 5 20 (1 0.3) = = − − P W e 六、（附加题）有一家公司生产儿童自行车，明年上半年的销售量预测如表所示。公司具 有每月生产 30 千辆的能力。通过加班，每月的产量还可以提高 50%，但是自行车的生产 成本也将从 30 元提高到 40 元。对于库存中的每辆自行车，在每个月底都需要支出 5 元的 存储费用。假设现在是 1 月 1 日。目标是要安排每月的生产和储存计划，在满足需求的同 时最小化总成本。请回答下列问题：
1)以代数形式建立该问题的线性规划模型,写清楚决策变量、目标函数和约束条件。(15 2)草拟一张该问题的线性规划电子表格模型的草图,列岀数据单元格、可变单元格、输 出单元格、目标单元格及约束条件,并写出有关单元格的公式。(15分) 明年上半年的需求预测 月份 12 3 需求(千辆 解答:1)决策变量(单位:千辆 第个月使用第个月正常生产出来的产品的量 x2-第/个月使用第;个月加班生产出来的产品的量 目标函数(单位:千元) min C=∑[30+5(-)x+∑[40+5(-0 约束条件: 0,i> x=0,i>j x≤30 ∑x≤ (x2+x2) (x13+x 3) (x4+x14) ∑(x3+x)=33 +x16)=40 ≥0 x≥0 i,j∈{1,2,34,5,6} 2)如下图所示,浅蓝色为数据单元格,黄色为可变单元格,白色为输出单元格,橘红色 为目标单元格。 《运筹学》试卷卷第8页共9页
《运筹学》试卷 卷 第 8 页 共 9 页 1）以代数形式建立该问题的线性规划模型，写清楚决策变量、目标函数和约束条件。(15 分) 2）草拟一张该问题的线性规划电子表格模型的草图，列出数据单元格、可变单元格、输 出单元格、目标单元格及约束条件，并写出有关单元格的公式。(15 分) 解答：1）决策变量(单位：千辆)： 第 个月使用第 个月加班生产出来的产品的量 第 个月使用第 个月正常生产出来的产品的量； x j i x j i i j i j − − ' 目标函数(单位：千元)： = + − + + − ( , ) ' ( , ) min [30 5( )] [40 5( )] i j ij i j ij C j i x j i x 约束条件： + = + = + = + = + = + = = = = = = = = = = = , {1,2,3,4,5,6} 0 0 ( ) 40 ( ) 33 ( ) 25 ( ) 45 ( ) 35 ( ) 30 15 30 0 0 ' 6 1 ' 6 6 6 1 ' 5 5 6 1 ' 4 4 6 1 ' 3 3 6 1 ' 2 2 6 1 ' 1 1 6 1 ' 6 1 ' i j x x x x x x x x x x x x x x x x x i j x i j ij ij i i i i i i i i i i i i i i i i i i j ij j ij ij ij ， ， 2）如下图所示，浅蓝色为数据单元格，黄色为可变单元格，白色为输出单元格，橘红色 为目标单元格
D K L 每月使用的各月的量(千辆) 产量 能力 区域名称区域 1正常302E220 C4H15 1加班0 0 0005058 prodN I4115 各2正常0300 0 Capacity K4 K15 sedUm C16: H16 常3正常000 0 demandNum C18: H18 和3加班 015 0 dwCost C23H34 加 常0 12班物0000000<1 30 0 13量加班0 6正常0 000 16 6加L00 01010 使用量3035 253340 18 需求量3035452 21 每月使用各月产品的单位成本(元) 4各1加班 4530556065 月2正常030 35404550 正2加班04045505560 3正常 和3加班 29加4正常 000 3035 5055 3 的5常 00000000 00000 000000 3035 情5加班 6正常 6加班 37总成本[65 每月使用的各月的量(千辆) 正常 24841475398940 -SUM(C4.H4 =sUMC5HS 2正常 tUMc7H刀 常 3正常 3加班 4正常 的 0000500000 =SUM(C13: H13 SUM(C14: H14 6加班 9999999-suMc15H1 eHHE =SUM(C4C15=SUM(D4: D15=SUM(E4E15=SUM(F4:F15=SUM(G4G15=SUM(H4: HIS A B 总成本 《运筹学》试卷卷第9页共9页
《运筹学》试卷 卷 第 9 页 共 9 页