管理运筹学复习题及部分参考答案(5页).docx

-第 1 页管理运筹学复习题及部分参考答案-第 2 页一、名词解释 1.模型 2.线性规划 3.树 4.网络 5.风险型决策 二、简答题 1.简述运筹学的工作步骤。2.运筹学中模型有哪些基本形式 3.简述线性规划问题隐含的假设。4.线性规划模型的特征。5.如何用最优单纯形表判断线性规划解的唯一性或求出它的另一些最优解 6.简述对偶理论的基本内容。7.简述对偶问题的基本性质。8.什么是影子价格?同相应的市场价格之间有何区别,以及研究影子价格的意义。9.简述运输问题的求解方法。10.树图的性质。11.简述最小支撑树的求法。12.绘制网络图应遵循什么规则。三、书 收据模型与决策 2.13 14.有如下的直线方程:2x 1+x 2=4 a.当 x 2=0 时确定 x 1 的值。当 x 1=0时确定 x 2 的值。b.以 x 1 为横轴 x 2 为纵轴建立一个两维图。使用 a 的结果画出这条直线。c.确定直线的斜率。d.找出斜截式直线方程。然后使用这个形式确定直线的斜率和直线在纵轴上的截距。答案:14.a.如果 x 2=0,则 x 1=2。如果 x 1=0,则 x 2=4。c.斜率=-2 d.x 2=-2 x 1+4 2.40 你的老板要求你使用管理科学知识确定两种活动(和)的水平,使得满足在约束的前提下总 成本最小。模型的代数形式如下所示。Maximize 成本=15 x 1+20 x 2 约束条件 约束 1:x 1+2x 210 约束 2:2x 13x 26 约束3:x 1+x 26 和 x 10,x 20 a.用图解法求解这个模型。b.为这个问题建立一个电子表格模型。c.使用 Excel Solver 求解这个模型。答案:a.最优解:(x 1,x 2)=(2,4),C=110 bc.活动获利 1 2 总计水平 A B C 1 2 23 1 1 101086 66 单位成本方案 15 20 2 4$110.00 3.2 考虑具有如下所示参数表的资源分配问题:资源 每一活动的单位资源使用量 可获得的 资源数量 1 2 1 2 3 2 3 2 1 3 4 10 2020 单位贡献$20$30 单位贡献=单位活动的利润 b.将该问题在电子表格上建模。c.用电子表格检验下面的解(x 1,x 2)=(2,2),(3,3),(2,4),(4,2),(3,4),(4,3),哪些是可行 解,可行解中哪一个能使得目标函数的值最优 d.用 Solver 来求解最优解。e.写出该模型的代数形式。f.用作图法求解该问题。答案:ac.每单位数量的活动使用的资源量资源 活动 1 活动 2 总计 可用资源 1 2 1 1010 2 3 3 3 2 4 2020 2020 单位利润方案 20 20 3.333 3.333$166.67 3.5 Omega 公司停止了生产一些已经不再获利的产品,这样就产生了相当地剩余生产力。管理层 考虑将这些剩余的生产力用于一种或几表所示。机器?类型 每周可获得的机器小时 铣床 车床 磨床 500 350 150 各种产品每生产一个单位需要的机器小时如下表所示:生产系数(每单位的机器小时)机器类型 产品 1 产品 2 产品 3 铣床 车床 磨床 9 5 3 3 4 0 5 02 销售部门表示产品 1 与产品 2 的预计销售将超过最大的生产量,而产品 3 的每周平均销售 20 单位。三种产品的单位利润分别为$50,$20,和$25。目标是要确定每种产品的产量使得公司 的利润最大化。a.判别问题的各种活动以及分配给这些活动的有限的资源,从而说明该问题为什么是资源分 配问题。b.为该资源分配问题建立参数表。c.描述该问题要作出的决策,决策的限制条件以及决策的总绩效测度。d.将上面对于决策与绩效测度的描述以数据和决?量的定量的方式来表达。e.为该问题建立电子表格模型,确定数据单元格,可变单元格,目标单元格以及其他的输出 单元格,并且将输出单元格中使用 SUMPRODUCT函数的等式表示出。f.用 Solver 来求解问题。g.将该模型以代数形式总结。答案:c.所需要进行的决策是每一种产品应当生产多少。决策的约束条件是碾磨机、车床和磨工的 可用时数以及产品 3 的潜在销量。总的绩效测度是利润,利润必须最大化。d.碾磨机:9(#1 的单位数)+3(#2 的单位数)+5(#3 的单位数)500 机床:5(#1 的单位数)+4(#2 的单位数)350 磨工:3(#1 的单位数)+2(#3 的单位数)150销售量:(#3 的单位数)20 非负条件:(#1 的单位数)0,(#2 的单位数)0,(#3 的单位数)0 利润=$50(#1 的单位数)+$20(#2 的单位数)+$25(#3 的单?数)ef.A B C D E F G 1 资源 每单位数量的活动使用的资源量总计 可用资源 2 产品 1 产品 2 产品 3 3 第一部分 第二部分资金 工作时数 9 3 5 5 4 03 0 2 0 0 1 500500 0350 0150 020 4 5 6 7 单位利润方案 50 20 25 0 166.667 0$3,333.338 4.6 K&L 公司为其冰激凌经营店供应三种口味的冰激凌:巧克力、香草和香蕉。因为天气炎热,对冰激凌?需求大增,而公司库存的原料已经不够了。这些原料分别为:牛奶、糖和奶油。公司无法完成接收的订单,但是,为了在资源有限的条件下,使利润最大化,公司需要确定 各种口味产品的最优组合。巧克力、香草和香蕉三种口味的冰激凌的销售利润分别为每加仑$1.00、$0.90 和$0.95。公司现在有 200 加仑牛奶、150磅糖和 60 加仑奶油的存货。这一问题代数形式的线性规划表 示如下:假设 C=巧克力冰激凌的产量(加仑)V=香草冰激凌的产量(加仑)B=香蕉冰激凌的产量(加仑)最大化 利润=1.00C+0.90V+0.95B 结束条件牛奶:0.45C+0.50V+0.40B200(加仑)糖:0.50C+0.40V+0.40B150(加仑)奶-第 3 页油:0.10C+0.15V+0.20B60(加仑)且 C0 V0 B0 使用 Excel Solver 求解,求解后的电子表格和灵敏度报告?下所示。(注意,因为在 f 中将会讨论牛奶约束,所以该部分在下面的省去了。)不用 Excel Solver 重新求解,尽可能详尽的回答下列问题,注意,各个部分是互不干扰,相互独立的。a.最优解和总利润是多少 b.假设香蕉冰激凌每加仑的利润变为$1.00,最优解是否改变,对总利润又会产生怎样 的影响 c.假设香蕉冰激凌每加仑的利润变为 92 美分,最优解是否改变,对总利润又会产生怎 样的影响 d.公司发现有三加仑的库存奶油已经变质,只能扔掉,最优解是否改变,对总利润又 会产生怎样的影响 e.假设公司有机会购得 15磅糖,总成本$15,公司是否应该购买这批糖,为什么 f.在灵敏度报告中加入牛奶的约束,并解释如何减少各种产品的产量 A B C D E F G 1 2 Resource Usage per Unit of Each Activity Resource 3 Resource ChocolateVanilla Banana Totals Available 4 Milk 0.45 0.5 0.4 180200 5 Sugar 0.5 0.4 0.4 150150 6 Cream 0.10.15 0.2 6060 7 1 0.9 0.95$341.25 8 Solution 0 300 75 变动单元格 单元格名最终值 减少的 目标函数 允许 允许 成本 系数 增加值 减少值$B$8 巧克力的解 00.0375 1 0.0375 1E+30$C$8 香草的解300 0 0.9 0.05 0.0125$D$8 香蕉的解 75 0 0.95 0.021428571 0.05 约束条件 单元格名最终值 影子 右端值 允许 允许 价格 增加值 减少值$E$4 牛奶总计$E$5 糖总计 150 1.875 150 10 30$E$6 奶油总计 60 1 60 15 3.75 4.7 大卫、莱蒂娜和莉迪亚是一家生产钟表的公司业主以及员工,大卫、莱蒂娜每周最多工作 40 个小时,而莉迪亚每周最多只能工作 20 个小时。该公司生产两种不同的钟表:落地摆钟和墙钟。大卫是机械工程师,负责装配钟表内部 的机械部件,而莉迪亚是木工,负责木质外壳的手工加工,莉迪亚负责接收订单和运货。每 一项工作所需时间如下表所示:任务 所需时间(小时)落地摆钟 墙钟?装机械配件雕刻木盖 运输 6 8 3 4 4 3 每生产并销售一个落地摆钟产生的利润是$300,每个墙钟为$200。现在,三个业主希望能够得到各种产品产量的最优组合,以使得利润最大化。a.为该问题建立线性规划模型。b.使用图形法求解。c.将模型显示在电子表格上。d.使用 Excel Solver 求解最优解并生成灵敏度报告。e.如果落地摆钟的单位利润从$300 增加到$375,而模型的其他不变,运用灵敏度报告 确定最优解是否会改变 f.除了 e 中老式表的单位利润变动之外,再加上将墙钟的单位利润从$200 降到$175,重复 e 的问题。g.用图表分析证明 e 和 f 的答案。h.为了增加总利润,三个业主同意增加他们三人中的一个人的工作时间,增加该人的 工作时间必须能够最大限度的增加总利润。运用灵敏度报?,确定应该选择哪一个 人。(假设模型的其他部分没有任何的变动。)i.解释为什么有一个人的影子价格为 0。j.如果莉迪亚将工作时间从每周的 20 小时增加到 25 小时,是否可以用影子价格分析 该变动对结果的影响如果影子价格有效,总利润将增加多少 k.在将 j 中加入另一变动,即大卫的工作时间从每周 40 小时减少到 35,重新分析。l.使用图形证明 k 中的结论。4.11 考虑具有如下参数表的资源分配问题:资源 每种活动的单位资源使用量 1 2 可获得资源数量 1 2 单位利润 1 1$1 3 1$2 8 4 该问题的目标是确定各种活动的单位数量使得总利润最大。a.使用作图法求解该模型。b.增加一个单位的可获得的资源数量,用作图法再次求解,从而确定各种资源的影子价格。c.对 a 和 b 部分用电子表格建模并求解。d.运用 Solver 的灵敏度报告求得影子价格。e.描述一下为什么在管理层有权改变可获得的资源量时,影子价格是很有用的。5.5 汤姆想要在今天买三品脱的家酿酒,明天买另外的四品脱。迪克想要销售 5 品脱的家酿酒,今天的价钱为每品脱 3.00 美元,而明天的价钱为每品脱 2.70 美元。哈里想要销售 4 品脱的家 酿酒,今天的价钱为每品脱 2.90 美元,而明天的价钱为每品脱 2.80 美元。汤姆想要知道他要如何进行购买才能在满足他的口渴需要的基础之上,使他的购买成本 达到最小值。为这个问题建立电子表格模型并解决它。5.8 承包商苏珊美格想要向三个建筑工地运送沙土。她可以在城市北面的沙土矿中购买 18 吨的 沙土,在城市南面的沙土矿中购买 14 吨的沙土。建筑工地 1、2、3 需要的沙土量分别为 10 吨、5 吨和 10 吨。在每个沙土矿购买一吨沙土的成本以及每一吨的运输成本如下所示。矿到每一个工地的运输成本(美元)每吨 价钱 1 2 3 南面 北面 30 60 60 30 5040 100 120 苏珊想要确定应该从每一个沙土矿运输多少沙土到每一个工地,才能使购买和运输成本达到最低。对这个问题进行描述并求解。5.18 考虑拥有如下所示成本表的指派问题(单位:美元)工作 1 2 3 人员 A B C 5 3 2 7 6 3 4 5 4 最优解是 A-3,B-1,C-2,总的成本是 10 美元。a.画出这个问题的网络表示图。b.在电子表格上对这个问题进行描述。c.使用 Excel Solver 得到最优解。答案:bc.单位成本($)任务(工作)1 2 3 供应量 被指派者 A(人)B C 5 7 4 3 6 5 2 3 4 1 1 1 需求量 1 1 1 单位成本($)任务(工作)-第 4 页1 2 3 总计 供应量 被指派者 A(人)B C 0 0 1 1 0 0 0 1 0 1=1 1=1 1=1 总计 需求量 1 1 1=1 11 总成本=$10 5.19 考虑拥有如下所示的成本表的指派问题(单位:美元)工作 1 2 3 4 被指派者 A B C D8 6 7 6 6 5 8 7 5 3 4 5 7 4 6 6 a.画出这个问题的网络表示图。b.在电子表格上对这个问题进行描述。c.使用 Excel Solver 得到最优解。5.20 四艘货船要从一个码头向其他的四个码头运货(分别标记为 1、2、3、4)。每一艘船都能够 运送到任何一个码头。但是,由于货船和货物的不同,装船、运输和卸货成本都有些不同。如同下表所示:(单位:美元)码头 1 2 3 4 货船 A B C D 500 600 700 500 400 600 500 400 600 700700 600 700 500 600 600 目标是要把这四个不同的码头指派给四艘货船,使总运输成本最小。a.请解释为什么这个问题符合指派问题模型。b.在电子表格中描述这个问题并求解。6.8 为下图给出的最大流问题建立一个电子表格模型并用其求解。图中,节点 A 是源,节点 F 是收点,弧的容量如弧旁边方括号里的数字所示。6.9 右方的图描述了产生于三条河(节点 R1、R2 和 R3)而终结于一个主要城市(节点 T)的人 工水道系统。图中其他的节点是系统中的连接点。以千立方英尺为单位,下表显示了每天每条人工水道可以通过的最大水量。到从 A B C 到从 D E F 到从 T R1 R2 75 40 65 50-60 A B 60 70 45 55-45 D E 120 190B D C E A F 7 2 9 7 4 6 3 6 9 B D C E A F 7 2 9 7 4 6 3 6 9 R 2 R 1 A D T E B C F R 3 R 2 R 1 A D T E B C F R 3 R3-80 70 C-70 90 F 130 城市水利管理者需要确定一个流量方案,使得到达这个城市的水流量最大。a.把这个问题看作是最大流问题,确定源点、收点和转运点,然后画出标有每条弧容量 的完整网络。b.为该问题建立电子表格模型并求解。答案:6.8从到 运量 容量 A A B B C C D D E B C D E D E E F F 8 7 7 1 2 5 3 6 99 7 7 24 6 3 6 9 节点 净流量 供应量/需求量 A B C D E F 15 0 0 0 0?15=0 0 0 0 最大流量=15 6.12你将驾驶着小汽车进行一次旅行,到达一个你以前从未到过的城市。所以你需要研究地图,从而为到达这一目的地选择一条最短的路线。无论你所选择的是哪一条路线,一路上你将会 经过五个城市(我们将其称为A,B,C,D,E)。地图上标明了连接两个城市市之间公路的 长度。它们之间不再有其他城市。这些数据概括在下表中,-表示若不经过其他城市,两 个城市之间没有道路直接相连。城市 相邻城市间的距离 A B C D E目标地源 A B C D E 40 60 10 50-20-70 55-40 50 10-60 80 a.画出网络模型,并根据这个?题的网络模型求出最短路径。其节点代表这个城市,连 线代表路程,数据代表这些路程有多少英里。b.作出这个问题的电子表格模型并求解。c.利用 b 部分来确认你的最短路径。d.如果表格中的数据代表你驾车从一个城市到另一个城市的成本(以美元为单位),c 部分所得出的答案是否就是你的最低成本路径 e.如果表格中的数据代表你驾车从一个城市到另一个城市的时间(以分钟为单位),c 部分所得出的答案是否就是你的最短时间路径 6.13 在一个不断扩建的小型飞机场里,一家本地的航空公司购买了一辆新的牵引车作为拖车,在 飞机场之间搬运行李。因为机场在三年后将安装一个新的机械化行李搬运系统,所以到那时 牵引车将被淘汰。然而,由于高负荷工作,其使用与维护成本会随着年份急剧增加。因此使 用一两年后进行重置可能更加经济。下面的表格(0 表示现在)给出了第 i 年末购买的拖车在 第 j 年末卖出的总净折现成本(购买价格减去交易抵偿,加上使用与维护费用)。j(美元)1 2 3 i 0 1 2 8,000 18,000 10,000 31,000 21,00012,000 为了使得三年内拖车的总成本最低,管理层希望确定何时(如何可能的话)进行拖车置 换是最合理的。a.将这个问题作为最短路问题,建立一个网络模型。b.为这个问题建立电子表格模型并求解。6.14 速达(Speedy)航空公司中有一架班机将从西雅图直飞伦敦。由于天气因素的影响,在明确 选择线路时存有一定的灵活性。下面的网络模型提供了所能考虑到的一些可能航线。节点 SE 与 LN 分别代表了西雅图与伦敦。其他的节点分别代表了不同的途经地点。风力对于飞行的时间(以及燃油的耗用)是有很大影响的。根据最新的气象报道,各条 航线飞行时间(以小时计算)标注在弧线上。因为燃油十分昂贵,速达航空公司的管理层需 要制定一套方案,选择飞行时间最短的航线。a.在将此问题作为最短路问题时,什么代表了路程 b.为这一问题建立电子表格模型并求解。6.16 A D B E C F S E L N 3.5 3.4 3.6 3.2 4.7 4.6 3.4 3.3 4.2 3.8 3.4 3.5 A D B E C F S E L N 3.5 3.4 3.6 3.2 4.7 4.6 3.4 3.3 4.2 3.8 3.4 3.5 运用在 6.5 节中介绍的贪婪算法,找出由下面的节点和供选择的边组成的网络的最小支撑树。每两个节点间的虚线代表备选边,虚线旁边的数字代表把这条边插入到网络中的成本(单位:千美元)。6.17 运用 6.5 节中介绍的贪婪算法,找出由下面的节点和供选择的边组成的网络的最小支撑树。每两个节点间的虚线代表-第 5 页备选边,虚线旁边的数字代表把这条边插入到网络中的成本(单位:百万美元)。8.19 艾尔伯特弗兰克公司(Albert Franko Co.)的管理层已经为其公司的两种新产品制定了各自 的市场目标,具体的说,产品 1 必须占据 15%的市场份额,而产品 2 必须有 10%的市场份额。为了获得市场,准备开展三次广告活动,其中两个广告是分别针对产品 1 和产品 2 的,而广 告 3 是为了提高整个公司及其产品的声誉。以 x 1,x 2,x 3 分别表示分配在三个广告上的资金(以 百万美元为单位),相应的两种产品取得的市场份额估计值(以百分比表示)为 产品 1 的市场份额=0.5x 1+0.2x 3 产品 2 的市场份额=0.3x 1+0.2x 3 广告总预算为$5500 万,其中必须有至少$1000 万投资在第三个广告上。如果两个产品 的市场份额目标不能同时实现,管理层认为两种产品上目标偏离的严重性是同等的。在上述 条件下,管理层希望得到最有效的资金分配方法。a.根据题中给出的各目标以及总目标的数量表达式,说明为什么该问题是一个目标规划 问题。b.在电子表格上建立该问题的线性规划模型并求解。c.以管理层能够管理的语言解释你所求得的最优解。8.20 易迈克斯(Emax)公司的研发部开发出了三种新产品,现在就要决策该如何生产各种产品。管理层主要考虑三个因素,分别为:总利润,员工的稳定性以及公司明年的收入比今年的$75,000,000 有所增加。使用表中规定的单位,该问题的目标可表示为:B C D A G E F 4 7 1 6 5 2 4 5 5 1 6 8 B C D A G E F B C D A G E F 4 7 1 6 5 2 4 55 1 6 8 B E H A D G I K C F J 3 4 7 8 2 2 2 2 5 4 6 2 5 2 3 4 5 6 4 5 3 1 B E H A D G I K C F J 3 4 7 8 2 22 2 5 4 6 2 5 2 3 4 5 6 4 5 3 1 最大化 M=P-6C-3D 其中 M=综合三个因素的总绩效测度 P=新产品在整个生命周期产生的总利润 C=员工水平的变动量(增加或减少)D=第二年收入与今年相比的减少量 收入的任何增加都不输入 M,因为管理层所要求的只是收入上的些许的增加以取悦股东。(这里面还包含着矛盾的心情,如果明年收入增加过多,今后几年就很难保持并超越。)各产 品每一单位对三个因素的影响如下表所示:因素 单位产品的贡献 目标(单位)1 2 3 总利润 员工水平 下一年的收入 20 6 8 15 4 7 25 5 5 最大化=5075(百万美元)(百名员工)(百万美元)a.为该问题建立电子表格模型并求解。b.以管理层能够理解的语言解释你所求得的最优解。答案:b.易迈克斯(Emax)应该生产 15 个单位的产品 3。虽然这样使就业水平提高 25,但是并没有 减少收入并且使得新产品在整个生命周期中的利润达到最大。任何产品组合在这三点上都 有缺陷,但是根据管理层的绩效测度这个产品组合是最令人满意的。8.22 蒙特哥是一个有着 15,000,000 亩共用耕地的发展中国家。目前,政府正计划将这些土地分配 给三种基本的农作物。生产的农产品一部分出口以换取紧缺的外币,剩下的是居民的食粮。种植这些农作物也为国家相当一部分人提供了就业。因此,在分配土地时要考虑的主要因素 为:(1)能获得的外币,(2)可供养的居民数,(3)种植农作物需要的劳动力。