运筹学知识点全总结汇总

《运筹学知识点全总结汇总》由会员分享，可在线阅读，更多相关《运筹学知识点全总结汇总（14页珍藏版）》请在装配图网上搜索。

1、一、线性规划：基本概念1、下面的表格总结了两种产品A 和 B 的关键信息以及生产所需的资源Q, R, S ：每单位产可用资资源品资源源使用量产品A产品BQ212R122S334利润 /单位3000美元2000美元满足所有线性规划假设。（ 1）在电子表格上为这一问题建立线性规划模型；（ 2）用代数方法建立一个相同的模型；（ 3）用图解法求解这个模型。5、普里默（ Primo ）保险公司引入了两种新产品：特殊风险保险和抵押。每单位特殊风险保险的利润是 5 美元，每单位抵押是 2 美元。管理层希望确定新产品的销售量使得总期望利润最大。工作的要求如下：可使用部门单位工工时时特殊风抵押险承保322400

2、管理01800索赔201200（ 1）为这个问题在电子表格上建立一个线性规划模型并求解。（ 2）用代数形式建立相同的模型。8、拉尔夫 艾德蒙（ Ralph Edmund ）喜欢吃牛排和土豆，因此他决定将这两种食品作为正餐的全部（加上一些饮料和补充维生素的食品）。拉尔夫意识到这不是最健康的膳食结构，因此他想要确定两种食品的食用量多少是合适的，以满足一些主要营养的需求。他获得了以下营养和成本的信息：每每天需份各种成分要量成分的（克）克数牛排土豆碳水化51550合物54020蛋白质26015脂肪每份成4美元 2 美元本拉尔夫想确定牛排和土豆所需要的份数（可能是小数），以最低的成本满足这些需求。（ 1

3、）为这个问题在电子表格上建立一个线性规划模型并求解。（ 2）用代数形式建立相同的模型；（ 3）用图解法求解这个模型。二、线性规划的what-if分析1、G.A.T 公司的产品之一是一种新式玩具，该产品的估计单位利润为3 美元。因为该产品具有极大的需求，公司决定增加该产品原来每天1000 件的生产量。但是从卖主那里可以购得的玩具配件（ A,B）是有限的。每一玩具需要两个A 类配件，而卖主只能将其供应量从现在的每天 2000 增加到 3000。同时，每一玩具需要一个B 类的配件，但卖主却无法增加目前每天1000 的供应量。因为目前无法找到新的供货商，所以公司决定自己开发一条生产线，在公司内部生产玩

4、具配件 A 和 B。据估计，公司自己生产的成本将会比从卖主那里购买增加 2.5 美元每件（ A,B ）。管理层希望能够确定玩具以及两种配件的生产组合以取得最大的利润。将该问题视为资源分配问题，公司的一位管理者为该问题建立如下的参数表：每种活动可获得资源的单位的资源资源使总量用量生产玩生产配具件配件 A2-13000配件 B1-11000单位利3 美元-2.5 美润元（ 1）为该问题建立电子表格模型并求解。（ 2）因为两类活动的单位利润是估计的，所以管理层希望能够知道，为了保持最优解不变，估计值允许的变动范围。针对第一个活动（生产玩具），运用电子表格，求出该活动单位利润从 2 美元增加到 4 美

5、元每次增加 50 美分时问题的最优解和总利润。在最优解不变的前提下，单位利润可以偏离其初值3 美元多少？（3）针对第二个活动（生产配件），重复（加到 -1.5 美元（第一种活动的单位利润固定在2）的分析，该活动的单位利润从3 美元）。-3.5 美元增（ 4）运用 Excel 灵敏度报告来找到每个活动单位利润的允许变动范围。（ 5）运用 Excel 灵敏度报告来描述在最优解不变的前提下，两个活动单位利润最多同时能改变多少。4、 K&L 公司为其冰激凌经营店供应三种口味的冰激凌：巧克力、香草和香蕉。因为天气炎热，对冰激凌的需求大增，而公司库存的原料已经不够了。计这些原料分别为：牛奶、糖和奶油。公司

6、无法完成接收的订单，但是为了在资源有限的条件下使利润最大化，公司需要确定各种口味产品的最优组合。巧克力、香草和香蕉三种口味的冰激凌的销售利润分别为每加仑1.00 美元、 0.90 美元和0.95 美元。公司现在有 200 加仑牛奶、 150 磅糖和 60 加仑奶油的库存。这一问题代数形式的线性规划表示如下：假设： C=巧克力冰激凌的产量（加仑）， V= 香草冰激凌的产量（加仑）， B= 香蕉冰激凌的产量（加仑）最大化：利润 =1.00C+0.90V+0.95V约束条件牛奶： 0.45C+0.50V+0.40B200（加仑）糖： 0.50C+0.40V+0.40B50 （加仑）奶油： 0.10C

7、+0.15V+0.20B60 （加仑）且 C0， V0， B0使用 Excel 求解，求解后的电子表格和灵敏度报告如下图所示（注意，因为在（6）中将会讨论牛奶约束，所以该部分在下面的图中隐去了）。不用 Excel 重新求解，尽可能详尽地回答下列问题，注意，各个部分是互不干扰、相互独立的。ABCDEFG1巧克力香草香蕉2单位利润1.000.900.9534每加仑冰激所需原料可用原料原料凌所用原料5牛奶0.450.50.41802006糖0.50.40.41507奶油0.10.150.26089巧克力香草香蕉10每加仑030075可调单元格单元格名称最终价成本削目标系增加上值减数限$C$10每加仑

8、巧克0-10.0375力用量0.0375$D$10每加仑香草30000.90.05用量$E$10每加仑香蕉7500.95 0.0214用量15060总利润341.25降低下限1E+300.01250.05约束单元格名称最终价 影子价 右端值 增加上降低下限值格限$F$5所用牛奶量$F$6所用糖量1501.8751501030$F$7 所用奶油量60160153.75（ 1）最优解和总利润是多少？（ 2）假设香蕉冰激凌每加仑的利润变为 1.00 美元，最优解是否改变，对总利润又会产生怎样的影响？（ 3）假设香蕉冰激凌每加仑的利润变为 92 美分，最优解是否改变，对总利润又会产生怎样的影响？（ 4

9、）公司发现有 3 加仑的库存奶油已经变质，只能扔掉，最优解是否改变，对总利润又会产生怎样的影响？（ 5）假设公司有机会购得 15 磅糖，总成本 15 美元，公司是否应该购买这批糖，为什么？（ 6）在灵敏度报告中加入牛奶的约束，并解释如何减少各种产品的产量？5、大卫、莱蒂娜和莉迪亚是一家生产钟表的公司业主以及员工，大卫、莱蒂娜每周最多工作40 个小时，而莉迪亚每周最多能工作20 个小时。该公司生产两种不同的钟表：落地摆钟和墙钟。大卫是机械工程师，负责装配钟表内部的机械部件；而莱蒂娜是木工，负责木质外壳的手工加工；莉迪亚负责接收订单和送货。每一项工作所需时间如下表所示：所需任务时间（小时）落地摆钟

10、墙钟组装机械配64件84雕刻木质外33壳运输每生产并销售一个落地摆钟产生的利润是300 美元，每个墙钟为200 美元。现在，三个业主希望能够得到各种产品产量的最优组合，以使得利润最大化。将会讨论牛奶约束，所以该部分在下面的图中隐去了）。（ 1）为该问题建立线性规划模型。（ 2）如果落地摆钟的单位利润从300 美元增加到 375 美元，而模型的其他不变，最优解是否会改变。然后用该模型检验如果墙钟的单位利润也从否会改变。200 美元变动到175 美元，最优解是（ 3）在电子表格上建立和求解该问题的原始模型。（ 4）运用 Excel 分析，如果落地摆钟的单位利润在 150 美元到 450 美元之间每

11、增加 20 美元给最优解和总利润带来的影响（墙钟单位利润不变）。然后同样分析，当墙钟的单位利润在 50 美元岛 50 美元之间每增加 20 美元给最优解和总利润带来的影响（落地摆钟单位利润不变）。而模型的其他不变，运用灵敏度报告确定最优解是否会改变？用这些信息来估计每种钟单位利润允许取值范围。（ 5）象（4）中一样，只是每增加20 美元变为每增加50 美元，给最优解带来的影响。（ 6）依次对每个业主用 Excel 分析，如果他们决定将自己的最大可用工时增加周，那么给最优解和总利润带来的影响。5 小时每（ 7）运用 Excel 分析，如果只是大卫将最大可用工时变为35、 37、 39、 41、4

12、3、 45 时最优解和总利润的变化。然后同样分析，莱蒂娜将可用工时进行上述改变时的情况。最后分析，当莉迪亚将最大可用工时变为15、 17、 19、21、 23、 25 时最优解和总利润的变化。（ 8）生成 Excel 灵敏度报告，用它来决定每种钟的单位利润和每个业主的最大可用工时的允许变化范围。（ 9）为了增加总利润，三个业主同意增加他们三个人中的一个人的工作时间，增加该人的工作时间必须能够最大限度地增加总利润。运用灵敏度报告，确定应该选择哪一个人（假设模型的其他部分没有任何变动）。（ 10）解释为什么有一个人的影子价格是0。（ 11）如果莉迪亚将工作时间从每周的 20 小时增加到 25 小时

13、，是否可以用影子价格分析该变动对结果的影响？如果影子价格有效，总利润将增加多少？（12）在（1）中加入另一变动，即大卫的工作时间从每周40 小时减少到35 小时，重新分析。三、运输问题和指派问题1、研究分析一下拥有如下所示参数表的运输问题：销单位成本（美元）供应地产地12319684271210336762需求423（1）画出这个问题的网络表示图。（2）用电子表格描述这个问题，然后使用Excel 得到最优解决方案。2、考虑拥有如下所示参数表的运输问题：目的地单位成本（美元）供应出发地1234137645224322343853需求3322（1）画出这个问题的网络表示图。（2）用电子表格描述这个

14、问题，然后使用Excel 得到最优解决方案。3、考斯雷司（ Cost-Less）公司从它的工厂向它的四个零售点供应货物，从每一个工厂到每一个零售点供应货物，从每一个工厂到每一个零售点的运输成本如下所示：零售点单位成本（美元）工厂12341500600400200220090010030033004002001004200100300200工厂 1、 2、 3、 4 每个月的生产量为 10、 20、 20、 10 个运输单位。零售点 1、 2、 3、 4 每个月所需货物量为 20、 10、 10、 20 个运输单位。配送经理兰迪史密斯现在需要确定每个月从每一个工厂制中药运送多少给相应零售点的最佳

15、方案。兰迪的目标就是要使总的运输成本最小。（ 1）把这个问题描述为一个运输问题并写出相应的出发地、供应量、目的地、需求量和单位成本。（ 2）用电子表格描述这个问题，然后使用Excel 得到最优解决方案。4、恰德费尔（ Childfair）公司拥有三个生产折叠婴儿车的工厂，并运往四个配送中心。工厂1、 2 和 3 枚月产量为12、 17、 11 个运输单位。同时配送中心每月需要10 个运输单位的货物。从每一个工厂到每一个配送中心的路程如下表所示：零售点到配送中心的距离工厂（英里）123418001340070021100006001000143600008009001200每一个运输单位的运输成

16、本为每英里100.5 美元。（ 1）把这个问题描述为一个运输问题并写出相应的出发地、供应量、目的地、需求量和单位成本。（ 2）用电子表格描述这个问题，然后使用Excel得到最优解决方案。5、汤姆想要在今天买3 品脱的家酿酒，明天买另外的4 品脱。迪克想要销售5 品脱的家酿酒，今天的价钱为每品脱3.00 美元，而明天的价钱是每品脱2.70 美元。哈里想要销售4 品脱的家酿酒，今天的价钱为每品脱2.90 美元，而明天的价钱为每品脱2.80 美元。汤姆想要知道他要如何进行购买才能在满足他的口渴需求的基础之上，使他的购买成本达到最小值。为这个问题建立电子表格模型并解决它。9、万诺特（ Onenote）

17、公司为四个顾客在三个工厂生产一种产品。在未来一周内这三个工厂的产量为60、80、 40 单位。公司决定向顾客1 供应 40 个单位，向顾客2 供应 60 个单位，向顾客 3 至少要供应20 个单位。顾客3 和 4 都想要尽可能多地购买剩下的产品。从工厂i 运送单位数量的产品给顾客j 的净利润如下表所示（单位：美元）：顾客工厂到每一个顾客的单位净利润（美元）1234180705002001002003502030030000604050000管理层希望知道为了使利润最大，应当向顾客 3 和 4 提供多少单位的产品以及应当从每一个工厂向每一个顾客运送多少单位的产品。用电子表格描述这个问题并求解。1

18、4、考虑拥有如下所示成本表的指派问题（单位：美元）：工作相关成本（美元）人员123A574B365C234最优解是A-3 ，B-1 ， C-2，总的成本是10 美元。（1）画出这个问题的网络表示图。（2）在电子表格上对这个问题进行描述，并使用Excel 得到最优解。15、考虑拥有如下所示的成本表的指派问题（单位：美元）：工作到每一个顾客被指派者的单位净利润（美元）1234A8657B6534C7846D6756（1）画出这个问题的网络表示图。（2）在电子表格上对这个问题进行描述，并使用Excel 得到最优解。16、四艘货船要从一个码头向其他的四个码头运货（分别积为 1、 2、3、 4）。每一艘

19、船都能够运送到任何一个码头。但是，由于货船和货物的不同，装船、运输和卸货成本都有些不同。如下表所示（单位：美元）：码头相关成本（美货船元）1234A500400600700B600600700500C700500700600D500400600600目标是要把这四个不同的码头指派给四艘货船，使总运输成本最小。（ 1）请解释为什么这个问题符合指派问题模型。（ 2）在电子表格中描述这个问题并求解。语文 数学物理化学张92 68 85 76王82 91 77 63李83 90 74 65赵93 61 83 7517、张、王、李、赵 4 位教师被分配教语文、数学、物理、化学 4 门课程，每位老师教一门

20、课程，一门课程由一位老师教。根据这四位老师以往教课的情况，他们分别教这四门课程的平均成绩如下表：四位教师每人只能教一门课，每一门课只能由一个教师来教，要确定哪一位教师上哪一门课，使四门课的平均成绩之和为最高。用Excel Solver求此指派问题的最优解。四、网络最优化问题4、过纽约 ALBANY 的北 南高速公路，路况通过能力如下图所示，图中弧上数字单位：千辆/ 小时，问该路段能否承受 10000 辆/小时的北 南向流量压力？5、在一个不断扩建的小型飞机场里，一家本地的航空公司购买了一辆新的牵引车作为拖车，在飞机之间搬运行李。因为机场在三年后将安装一个新的机械化行李搬运系统，所以到那时牵引车将被淘汰。然而，由于高负荷工作，其使用与维护成本会随着年份急剧增加。因此使用一两年后进行重置可能更加经济。下面的表格（ 0 表示现在）给出了第 i 粘膜买的拖车在第 j 年末卖出的总净折现成本（美元，购买价格减去交易抵偿，加上使用与维护费用）。到 j（美元）从 i12308000180003100011000021000212000为了使得三年内拖车的总成本最低，管理层希望确定何时（如果可能的话）进行拖车置换是最合理的。（ 1）将这个问题作为最短路问题，建立一个网络模型。（ 2）为这个问题建立电子表格模型并求解