深圳大学期末考试试卷 开闭卷闭卷 AB卷A卷 2204030701 课程编号2204030702课程名称运筹学 学分3分 22040907 命题人(签字) 审题人(签字) 2007年11月_19日 题号 三四五|六七八九|十 基本题 总分/附加题 得分 :/评卷人 ε一、某林业公司有6片林区,为便于树木的维护和砍伐运输,需要在林区之间修建公路 :并保证任意两个林区都可以通过这些公路彼此连通。已知铺设公路的费用平均为850元/ 一密米,每两片林区之间的距离如下表所示。现要最小化总铺设成本。请回答以下问题 她:1)这是一个最小支撑树问题,为什么?(5分) ☆2)该林业公司应该如何铺设公路?写出算法步骤。(10分) 3)最小成本是多少?(结果四舍五入保留两位小数)(5分) w两片林区之间的距离(公里 120.9232.71.8 212 42 0.8 30.91.5 07142.5 423340.7 1.63.1 52.72 141.6 0.5 1.80.82.53.10.5 解答:1因为该问题满足最小支撑树问题的所有假设①给定了网络中可供选择的边及其成 本(等价于边的长度即距离):②要插入足够多的边使图连通;③目标是要使总成本最小 2a)用避圈法求解该问题最为简单。避圈法的求解步骤为:开始选一条最小权的边,以后 每一步中,总从未被选取的边中选一条权最小的边,并使之与已被选取的边不构成圈(如 果有两条或两条以上的边都是权最小的边,则从中任选一条)。选边的过程如下图所示(每 条边上标记的第一个数字为长度,小括号里的数字为第几次被选中) (b)破圈法的求解步骤:任取一个圈,从圈中去掉权最大的边(如果有两条或两条以上的边 都是权最大的边,则任意去掉其中一条)。在余下的图中,重复这个步骤,一直到图中不 含圈为止(去边的同时必须保证图的连通性) 《运筹学》试卷卷第1页共8页
《运筹学》试卷 卷 第 1 页 共 8 页 深圳大学期末考试试卷 开/闭卷 闭卷 A/B 卷 A 卷 课程编号 2204030701 2204030702 22040907 课程名称 运筹学 学分 3 分 命题人(签字) 审题人(签字) 2007 年 11 月 19 日 题号 一 二 三 四 五 六 七 八 九 十 基本题 总分 附加题 得分 评卷人 一、某林业公司有 6 片林区，为便于树木的维护和砍伐运输，需要在林区之间修建公路， 并保证任意两个林区都可以通过这些公路彼此连通。已知铺设公路的费用平均为 850 元/ 米，每两片林区之间的距离如下表所示。现要最小化总铺设成本。请回答以下问题： 1）这是一个最小支撑树问题，为什么？(5 分) 2）该林业公司应该如何铺设公路？写出算法步骤。(10 分) 3）最小成本是多少？(结果四舍五入保留两位小数) (5 分) 解答：1)因为该问题满足最小支撑树问题的所有假设①给定了网络中可供选择的边及其成 本(等价于边的长度即距离)；②要插入足够多的边使图连通；③目标是要使总成本最小。 2)(a)用避圈法求解该问题最为简单。避圈法的求解步骤为：开始选一条最小权的边，以后 每一步中，总从未被选取的边中选一条权最小的边，并使之与已被选取的边不构成圈(如 果有两条或两条以上的边都是权最小的边，则从中任选一条)。选边的过程如下图所示(每 条边上标记的第一个数字为长度，小括号里的数字为第几次被选中)； (b)破圈法的求解步骤：任取一个圈，从圈中去掉权最大的边(如果有两条或两条以上的边 都是权最大的边，则任意去掉其中一条)。在余下的图中，重复这个步骤，一直到图中不 含圈为止(去边的同时必须保证图的连通性)。 _____________ ________ … 学院 专业 姓名 学号 ( 密 封 线 内 不 答 题 ) … … … …… … …… … …… …… … …… … …… … 密… … …… … …… … …… … …… …… … …… 封 …… … … …… … …… … …… …… … 线… … …… … …… … …… … …… … 线………………………………………
(c)教材给定的启发式算法:第一步,选择成本最低的备选边;第二步,在一个已经有 条边连接的节点和另一个还没有边连接的节点之间选择成本最低的备选边;第三步,重复 第二个步骤,直到所有的节点都有一条边(可能会有多于一条边)与其相连,此时就得到了 个最小支撑树(当有几条边同时是成本最低的边时,任意选择一条边)。 说明:只要算法步骤正确,得到了正确结果即可给分。 3)最小成本为:(0.5+0.7+0.8+09+1.2)*850=3485(千元) 林区2 林区3 1.2(5) Q8(3)094)Q.7(2) 林区1 林区4 林区5 林区6 0.5(1) 避圈法求解过程图 二、有一家钢铁公司收到一份500吨造船用钢的订单。此公司储存有4种不同的原材料 都可以用于制造这种钢。有关数据如下所示。假设各种不同原材料混合在一起的总重量等 于所有原材料重量之和。公司的目标是确定各种原材料的用量以使总成本最低。请以代数 形式建立该问题的线性规划模型,写清楚决策变量、目标函数和约束条件。(20分) 造船钢的品质要求 化学元素最低含量最高含量 碳(%6)2 铜(Cu)0406 锰(Mn%6 1.65 原材料品质、可用库存量与价格 原材料C%Cu%Mn%可用库存量吨)单价(元吨) 铁合金12501.3 400 200 铁合金23008 250 铜合金0964 200 240 铝合金00412300 解答:决策变量为各种不同原材料的使用量,其中铁合金1为x1吨,铁合金2为x2吨, 铜合金为x3吨,铝合金为x4吨。 《运筹学》试卷卷第2页共8页
《运筹学》试卷 卷 第 2 页 共 8 页 (c)教材给定的启发式算法：第一步，选择成本最低的备选边；第二步，在一个已经有一 条边连接的节点和另一个还没有边连接的节点之间选择成本最低的备选边；第三步，重复 第二个步骤，直到所有的节点都有一条边(可能会有多于一条边)与其相连，此时就得到了 一个最小支撑树(当有几条边同时是成本最低的边时，任意选择一条边)。 说明：只要算法步骤正确，得到了正确结果即可给分。 3)最小成本为：(0.5+0.7+0.8+0.9+1.2)*850=3485(千元). 林区1 林区5 林区6 林区4 林区2 林区3 0.5(1) 0.7(2) 0.8(3) 0.9(4) 1.2(5) 避圈法求解过程图 二、有一家钢铁公司收到一份 500 吨造船用钢的订单。此公司储存有 4 种不同的原材料， 都可以用于制造这种钢。有关数据如下所示。假设各种不同原材料混合在一起的总重量等 于所有原材料重量之和。公司的目标是确定各种原材料的用量以使总成本最低。请以代数 形式建立该问题的线性规划模型，写清楚决策变量、目标函数和约束条件。(20 分) 解答：决策变量为各种不同原材料的使用量，其中铁合金 1 为 1 x 吨，铁合金 2 为 2 x 吨， 铜合金为 3 x 吨，铝合金为 4 x 吨
目标函数是最小化总成本(单位:元):mmC=200x1+250x2+240x3+100x4 约束条件包括:(1)钢的产量要求 x1+x,+x2+x (2)资源可用量的要求 x2≤300 200 ≤300 (3)品质要求 % x1+x2+x3+ 2.59 3% ≤3% x1+x2+x3+x4 x2×96%+x1×04% ≥04% x1+x,+x3+x x3×96%+x4×0.4% ≤0.6% x1+x2+x3+ x1×1.3%+x2×08%+x3×4%+x4×1.29z1.2% x1+x2+x3+x4 x×1.3%+x2×0.8%+x3×4%+x×1.2041.65% x1+x2+x3+x4 (4)决策变量的非负要求 x120 x2≥0 x4≥0 三、某炼油厂根据计划每季度需至少供应合同单位汽油15万吨、煤油12万吨、重油12 万吨。该厂可从俄罗斯或中东地区购买原油进行提炼。俄罗斯的原油采购成本(含运费, 下同)为200元吨,中东地区的原油采购成本为310元吨。由于油质的不同提炼出的成品 油成分也不同。目标是最小化总采购成本。有关电子表格模型的求解结果及其敏感性分析 报告如下。请回答下列问题(结果四舍五入保留2位小数 1)分别写出单元格F4、F5、F6和C13的公式;(8分) 2)俄罗斯和中东地区单位原油采购成本的最优域分别是什么?(4分) 3)由于市场变动,导致中东地区原油价格上涨为400元/吨,原油采购量和原油采购总成 本将有什么变化趋势(不变,变大,变小)?(4分) 《运筹学》试卷卷第3页共8页
《运筹学》试卷 卷 第 3 页 共 8 页 目标函数是最小化总成本(单位：元)：min 200 1 250 2 240 3 100 4 C = x + x + x + x 约束条件包括：(1)钢的产量要求 x1 + x2 + x3 + x4 = 500 (2)资源可用量的要求 300 200 300 400 4 3 2 1 x x x x (3)品质要求 + + + + + + + + + + + + + + + + + + + + + + + + + + + + 1.65% 1.3% 0.8% 4% 1.2% 1.2% 1.3% 0.8% 4% 1.2% 0.6% 96% 0.4% 0.4% 96% 0.4% 3% 2.5% 3% 2% 2.5% 3% 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 3 4 1 2 3 4 3 4 1 2 3 4 1 2 1 2 3 4 1 2 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 x x x x (4)决策变量的非负要求 0 0 0 0 4 3 2 1 x x x x 三、某炼油厂根据计划每季度需至少供应合同单位汽油 15 万吨、煤油 12 万吨、重油 12 万吨。该厂可从俄罗斯或中东地区购买原油进行提炼。俄罗斯的原油采购成本(含运费， 下同)为 200 元/吨，中东地区的原油采购成本为 310 元/吨。由于油质的不同提炼出的成品 油成分也不同。目标是最小化总采购成本。有关电子表格模型的求解结果及其敏感性分析 报告如下。请回答下列问题(结果四舍五入保留 2 位小数)： 1）分别写出单元格 F4、F5、F6 和 C13 的公式；(8 分) 2）俄罗斯和中东地区单位原油采购成本的最优域分别是什么？(4 分) 3）由于市场变动，导致中东地区原油价格上涨为 400 元/吨，原油采购量和原油采购总成 本将有什么变化趋势(不变，变大，变小)？(4 分)
4)如果市场对煤油的需求量增加为15万吨,其影子价格会有什么变化?原油采购量和原 油采购总成本将有什么变化趋势(不变,变大,变小)?(4分) 求解问题的电子表格模型和敏感性报告结果 A G 单位原油的成品油含量 23456789 俄罗斯 中东地区产出量(万吨 最小需求量(万吨) 汽油含量015 0.5 煤某油含量02 重油含量 16.90909091 12 其他含量015 0.5 原油价格(元吨)200 0.05 原油采购量万吨27272727272181818182 总成本(万元)□121818182 区战名称 区战 含义 Totalcost C13 原油采购总成本 yyOrderNum C11D11原油采购量 yyUnitPrice C9D9原油采购成本 pyoutNum F4F6成品油产出量 pyDemandNum H4H6成品油需求量 icrosoft Exce19.0敏感性报告 工作表[2007-11运筹学试题easy.xls]敏感性分析 报告的建立:2007-11-26下午11:59:01 可变单元格 终 递减目标式允许的允许的 单元格 名字 值 成本系数增量 3C11原油采购量(万吨)俄罗斯.27272727 2006.666666 107 D:11原油采购量(万吨)中东地区21.81818182 310356.6666667 约束 终 阴影 约束允许 的允许的 单元格 名字 值 价格限制值增量 1536.3636363615 2.25 F$5煤油含量 12972.7272727 81.186813187 虾6重油含量 16.90909091 124.909090909 1E+30 解答:1)各单元格公式如下表所示 单元格 公式 SUMPRODUCT(yyOrderNum, C4 D4) F5 =SUMPRODUCT(yyOrderNum, C5: D5) F6 =SUMPRODUCT(yyOrderNum, C6: D6) C13 =SUMPRODUCTyyOrderNum,yy Unit Price) 2)俄罗斯原油采购成本的最优域为[200-107,200+6.67]即[93,206.67],中东地区原油采 《运筹学》试卷卷第4页共8页
《运筹学》试卷 卷 第 4 页 共 8 页 4）如果市场对煤油的需求量增加为 15 万吨，其影子价格会有什么变化？原油采购量和原 油采购总成本将有什么变化趋势(不变，变大，变小)？(4 分) 求解问题的电子表格模型和敏感性报告结果 解答：1）各单元格公式如下表所示 单元格 公式 F4 =SUMPRODUCT(yyOrderNum,C4:D4) F5 =SUMPRODUCT(yyOrderNum,C5:D5) F6 =SUMPRODUCT(yyOrderNum,C6:D6) C13 =SUMPRODUCT(yyOrderNum,yyUnitPrice) 2）俄罗斯原油采购成本的最优域为[200-107,200+6.67]即[93,206.67]，中东地区原油采 0.05
购成本的最优域为[310-10,310+356.67]即[300,666.67]; 3)中东地区的原油价格上涨到400元/吨,仍然在其最优域范围[300,667]之内,因此 最优解不发生变化,即原油采购量不变。但是原油采购总成本将上升,上升量为 (400-310)*21.8182=1963.64(万元); 4)当煤油的需求量在[12-1.19,12+8]即[10.81,20范围内时,其影子价格不会发生变化。 而15在此范围内,因此其影子价格不会发生变化。由于需求量增加了,所以原油采购量 和原油采购总成本都将上升。 四、某企业由于生产能力过剩,拟开发新产品,现有4个品种可供选择。市场销售有好、 中、差三种情况,销售状态的概率和每一品种在不同状态下的收益如下表所示。按照以下 不同的决策准则,该厂应该开发哪一种产品? 1)乐观准则;(5分) 2)悲观准则:(5分) 3)最大可能性准则;(5分) 4)贝叶斯决策准则。(5分) S好 中 0.3 0.5 2 14 12 B 22 14 18 10 D 注:X表示产品品种,P表示收益,S表示销售状态及其概率 解答:1)按照乐观决策准则,每一个决策方案的最好情况如下 方案 A B C 最好情况下的收益14221820 其中收益最大的方案为B,因此乐观准则下应该开发B产品; 2)按照悲观决策准则,每一个决策方案的最坏情况如下 方案 ABCD 最坏情况下的收益1210108 其中收益最大的方案为A,因此悲观准则下应该开发A产品 3)按照最大可能性决策准则,销售状态最有可能是中,此情况下收益最大的方案为C, 因此最大可能性决策准则下应该开发C产品; 4)按照贝叶斯决策准则,每一个决策方案的期望收益如下 E(A)=14*0.3+14*0.5+14*0.2=13.6 《运筹学》试卷卷第5页共8页
《运筹学》试卷 卷 第 5 页 共 8 页 购成本的最优域为[310-10,310+356.67]即[300,666.67]； 3）中东地区的原油价格上涨到 400 元/吨，仍然在其最优域范围[300,666.67]之内，因此 最优解不发生变化，即原油采购量不变。但是原油采购总成本将上升，上升量为 (400-310)*21.8182=1963.64(万元)； 4）当煤油的需求量在[12-1.19,12+8]即[10.81,20]范围内时，其影子价格不会发生变化。 而 15 在此范围内，因此其影子价格不会发生变化。由于需求量增加了，所以原油采购量 和原油采购总成本都将上升。 四、某企业由于生产能力过剩，拟开发新产品，现有 4 个品种可供选择。市场销售有好、 中、差三种情况，销售状态的概率和每一品种在不同状态下的收益如下表所示。按照以下 不同的决策准则，该厂应该开发哪一种产品？ 1）乐观准则；(5 分) 2）悲观准则；(5 分) 3）最大可能性准则；(5 分) 4）贝叶斯决策准则。(5 分) 注：X 表示产品品种，P 表示收益，S 表示销售状态及其概率。 解答：1）按照乐观决策准则，每一个决策方案的最好情况如下 方案 A B C D 最好情况下的收益 14 22 18 20 其中收益最大的方案为 B，因此乐观准则下应该开发 B 产品； 2）按照悲观决策准则，每一个决策方案的最坏情况如下 方案 A B C D 最坏情况下的收益 12 10 10 8 其中收益最大的方案为 A，因此悲观准则下应该开发 A 产品； 3）按照最大可能性决策准则，销售状态最有可能是中，此情况下收益最大的方案为 C， 因此最大可能性决策准则下应该开发 C 产品； 4）按照贝叶斯决策准则，每一个决策方案的期望收益如下 E(A)=14*0.3+14*0.5+14*0.2=13.6
E(B产22*0.3+14*05+10*0.2=156 E(C=18*0.3+16*0.5+10*0.2=154 E(D20*0.3+12*0.5+8*0.2=1360 其中E(B)最大,因此在贝叶斯决策准则下,该厂应该开发B产品。 五、某自行车修理铺有师傅1人,来修理自行车的顾客按泊松分布到达,平均每小时3 人,自行车修理时间服从指数分布,平均需要15分钟。请计算: 1)修理铺空闲时间的概率;(5分) 2)修理铺有2个顾客的概率;(5分) 3)修理铺内顾客的平均数:(5分) 4)顾客在修理铺的平均逗留时间。(5分) 解答:这个一个MM1的排队模型,其中的参数如下 λ=3(人/小时) =60/15=4(人/小时) p=/=3/4=0.75 按照MM/1排队模型的有关结论有 1)修理铺空闲时间的概率 P{L=0}=1-p=1-0.75=0.25 2)修理铺有2个顾客的概率 P{L=2}=(1-p)2=(1-0.75)×0.752≈0.14 3)修理铺内顾客的平均数 0.75 3(人) 4)顾客在修理铺的平均逗留时间 4-3=(小时 六、(附加题)有一家公司生产玻璃纤维,产量以立方米为单位计算。这家公司希望对未 来6个星期的生产进行规划。产能有一定的上限,且在每个时期产能的上限都不同。规划 所覆盖的整个期间的每周需求量都已知。不同时期的生产和储存的费用也不同。有关数据 如下所示。公司考虑应该采取怎样的生产和储存方案,以使总成本最小。请回答下列问题 1)该问题可以看成运输问题吗?为什么?(5分) 《运筹学》试卷卷第6页共8页
《运筹学》试卷 卷 第 6 页 共 8 页 E(B)=22*0.3+14*0.5+10*0.2=15.6 E(C)=18*0.3+16*0.5+10*0.2=15.4 E(D)=20*0.3+12*0.5+8*0.2=13.60 其中 E(B)最大，因此在贝叶斯决策准则下，该厂应该开发 B 产品。 五、某自行车修理铺有师傅 1 人，来修理自行车的顾客按泊松分布到达，平均每小时 3 人，自行车修理时间服从指数分布，平均需要 15 分钟。请计算： 1）修理铺空闲时间的概率；(5 分) 2）修理铺有 2 个顾客的概率；(5 分) 3）修理铺内顾客的平均数；(5 分) 4）顾客在修理铺的平均逗留时间。(5 分) 解答：这个一个 M/M/1 的排队模型，其中的参数如下 / 3/ 4 0.75 60 /15 4( / ) 3( / ) = = = = = = 人 小时 人 小时 按照 M/M/1 排队模型的有关结论有： 1）修理铺空闲时间的概率 P{L = 0} = 1− = 1− 0.75 = 0.25 2）修理铺有 2 个顾客的概率 { 2} (1 ) (1 0.75) 0.75 0.14 2 2 P L = = − = − 3）修理铺内顾客的平均数 3( ) 1 0.75 0.75 1 = 人 − = − = L 4）顾客在修理铺的平均逗留时间 1( ) 4 3 1 1 = 小时 − = − = W 六、（附加题）有一家公司生产玻璃纤维，产量以立方米为单位计算。这家公司希望对未 来 6 个星期的生产进行规划。产能有一定的上限，且在每个时期产能的上限都不同。规划 所覆盖的整个期间的每周需求量都已知。不同时期的生产和储存的费用也不同。有关数据 如下所示。公司考虑应该采取怎样的生产和储存方案，以使总成本最小。请回答下列问题： 1）该问题可以看成运输问题吗？为什么？(5 分)
2)以代数形式建立该问题的线性规划模型,写清楚决策变量、目标函数和约束条件。(15 3)草拟一张该问题的线性规划电子表格模型的草图,列出数据单元格、可变单元格、输 出单元格、目标单元格及约束条件,并写出有关单元格的公式。(10分) 星期产能(立方米)需求(立方米)生产成本(元/立方米)储存成本(元/立方米) 0.2 100 1 586676 0.3 3 110 120 120 100 110 解答:1)该问题可以看成运输问题,因为它符合运输问题的特征:①有出发地(生产); ②有目的地(需求):③出发地有供应量(产能);④目的地有需求量;⑤存在单位供应成本 (生产成本+存储成本),总供应成本是单位供应成本的线性函数;⑥目标是使总供应成本 最小。 2)决策变量:x-第/周使用第周生产的产品的量(立方米),i和j属于{12,3465} 定义如下变量 星期产能值求值生产成本值儲存成本 值 140b1100 d 20 da3 110b3100 a4100b490 ccc 025 a 20 a6100b6110c 则目标函数为 minC=(c,+>dk)xu 约束条件为 x,=0, i>j x x x.≥0 i,∈{1,2,3,4,5,6} 3)如下图所示,浅蓝色为数据单元格,黄色为可变单元格,白色为输出单元格,橘红色 《运筹学》试卷卷第7页共8页
《运筹学》试卷 卷 第 7 页 共 8 页 2）以代数形式建立该问题的线性规划模型，写清楚决策变量、目标函数和约束条件。(15 分) 3）草拟一张该问题的线性规划电子表格模型的草图，列出数据单元格、可变单元格、输 出单元格、目标单元格及约束条件，并写出有关单元格的公式。(10 分) 解答：1）该问题可以看成运输问题，因为它符合运输问题的特征：①有出发地(生产)； ②有目的地(需求)；③出发地有供应量(产能)；④目的地有需求量；⑤存在单位供应成本 (生产成本+存储成本)，总供应成本是单位供应成本的线性函数；⑥目标是使总供应成本 最小。 2）决策变量： x 第j周使用第i周生产的产品的量(立方米) ij − ，i 和 j 属于{1,2,3,4,5,6}； 定义如下变量： 则目标函数为： ij j k i i k min C (c d )x 1 − = = + 约束条件为： = = = = , {1,2,3,4,5,6} 0 0 6 1 6 1 i j x x a x b x i j ij j ij i i ij j ij ， 3）如下图所示，浅蓝色为数据单元格，黄色为可变单元格，白色为输出单元格，橘红色
为目标单元格 ABCDEF HIKL 每周使用各周的产品的量 区域名称区域 产量 产能 weekUsed B4: G9 5 80 000000 0 80< weekProducedH4.H9 100<=100 B10G10 85 demand B12G12 6 totalcost 10使用量100 11 12需求量10012010 110 345678 每周单位产品的成本(生产+存储) 1 59562 3 85875 205 0 0 6000 73 21 0 0 600 0 6 23总成本[388 每周使用各周的产品的量 产量 0100 SUM(B6: G5) -SUM(B7:Gn 10000099903M18c SUM(9: G9) 0使用量sMB4B =SUM(C4: C9) =SUMD4 D9) = SUM(EA E9) =SUM(F4 F9)=SUMGG4: G9) A 23总成本 SUMPRODUCT(weekUsed unitCost 《运筹学》试卷卷第8页共8页
《运筹学》试卷 卷 第 8 页 共 8 页 为目标单元格
