《运筹学》知识点全总结

《《运筹学》知识点全总结》由会员分享，可在线阅读，更多相关《《运筹学》知识点全总结（7页珍藏版）》请在金锄头文库上搜索。

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

2、排和土豆，因此他决定将这两种食品作为正餐的全部（加上一些饮料和补充维生素的食品） 。 拉尔夫意识到这不是最健康的膳食结构， 因此他想要确定两种食品的食用量多少是合适的，以满足一些主要营养的需求。他获得了以下营养和成本的信息：拉尔夫想确定牛排和土豆所需要的份数（可能是小数） ，以最低的成本满足这些需求。（ 1）为这个问题在电子表格上建立一个线性规划模型并求解。（ 2）用代数形式建立相同的模型；（ 3）用图解法求解这个模型。二、线性规划的 what-if 分析1、 G.A.T 公司的产品之一是一种新式玩具，该产品的估计单位利润为 3 美元。因为该产品具有极大的需求，公司决定增加该产品原来每天 10

3、00 件的生产量。但是从卖主那里可以购得的玩具配件（ A,B ）是有限的。每一玩具需要两个 A 类配件，而卖主只能将其供应量从现在的每天 2000 增加到 3000。同时，每一玩具需要一个 B 类资源每单位产品资源使用量可用资源产品 A 产品 B Q R S 2 1 3 1 2 3 2 2 4 利润 /单位 3000 美元 2000 美元部门每单位工时可使用工时特殊风险 抵押承保管理索赔3 0 2 2 1 0 2400 800 1200 成分每份各种成分的克数 每天需要量（克）牛排 土豆碳水化合物蛋白质脂肪5 20 15 15 5 2 50 40 60 每份成本 4 美元 2 美元的配件，但卖

4、主却无法增加目前每天 1000 的供应量。因为目前无法找到新的供货商，所以公司决定自己开发一条生产线，在公司内部生产玩具配件 A 和 B。据估计，公司自己生产的成本将会比从卖主那里购买增加 2.5 美元每件（ A,B ） 。管理层希望能够确定玩具以及两种配件的生产组合以取得最大的利润。将该问题视为资源分配问题，公司的一位管理者为该问题建立如下的参数表：（ 1）为该问题建立电子表格模型并求解。（ 2） 因为两类活动的单位利润是估计的， 所以管理层希望能够知道， 为了保持最优解不变， 估计值允许的变动范围。 针对第一个活动 （生产玩具） ， 运用电子表格， 求出该活动单位利润从 2 美元增加到 4

5、 美元每次增加50 美分时问题的最优解和总利润。在最优解不变的前提下，单位利润可以偏离其初值 3 美元多少？（ 3）针对第二个活动（生产配件） ，重复（ 2）的分析，该活动的单位利润从 -3.5 美元增加到 -1.5 美元（第一种活动的单位利润固定在 3 美元） 。（ 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.40B 200（加仑）糖： 0.50C+0.40V+0.40B

7、 50 （加仑）奶油： 0.10C+0.15V+0.20B 60 （加仑）且 C 0， V 0， B 0 使用 Excel 求解，求解后的电子表格和灵敏度报告如下图所示（注意，因为在（ 6）中将会讨论牛奶约束，所以该部分在下面的图中隐去了） 。不用 Excel 重新求解，尽可能详尽地回答下列问题，注意，各个部分是互不干扰、相互独立的。A B C D E F G 1 巧克力 香草 香蕉2 单位利润 1.00 0.90 0.95 3 4 原料 每加仑冰激凌所用原料 所需原料 可用原料5 牛奶 0.45 0.5 0.4 180 200 6 糖 0.5 0.4 0.4 150 150 7 奶油 0.1

8、 0.15 0.2 60 60 8 9 巧克力 香草 香蕉 总利润10 每加仑 0 300 75 341.25 资源每种活动的单位资源使用量 可获得的资源总量生产玩具 生产配件配件 A 配件 B 2 1 -1 -1 3000 1000 单位利润 3 美元 -2.5 美元可调单元格单元格名称 最终价值 成本削减 目标系数 增加上限 降低下限$C$10 每加仑巧克力用量0 -0.0375 1 0.0375 1E+30 $D$10 每加仑香草用量 300 0 0.9 0.05 0.0125 $E$10 每加仑香蕉用量 75 0 0.95 0.0214 0.05 约束单元格 名称 最终价值 影子价格

9、右端值 增加上限 降低下限$F$5 所用牛奶量$F$6 所用糖量 150 1.875 150 10 30 $F$7 所用奶油量 60 1 60 15 3.75 （ 1）最优解和总利润是多少？（ 2）假设香蕉冰激凌每加仑的利润变为 1.00 美元，最优解是否改变，对总利润又会产生怎样的影响？（ 3）假设香蕉冰激凌每加仑的利润变为 92 美分，最优解是否改变，对总利润又会产生怎样的影响？（ 4） 公司发现有 3 加仑的库存奶油已经变质， 只能扔掉， 最优解是否改变， 对总利润又会产生怎样的影响？（ 5）假设公司有机会购得 15 磅糖，总成本 15 美元，公司是否应该购买这批糖，为什么？（ 6）在灵

10、敏度报告中加入牛奶的约束，并解释如何减少各种产品的产量？5、 大卫、莱蒂娜和莉迪亚是一家生产钟表的公司业主以及员工，大卫、莱蒂娜每周最多工作 40 个小时，而莉迪亚每周最多能工作 20 个小时。该公司生产两种不同的钟表：落地摆钟和墙钟。大卫是机械工程师，负责装配钟表内部的机械部件；而莱蒂娜是木工，负责木质外壳的手工加工；莉迪亚负责接收订单和送货。每一项工作所需时间如下表所示：每生产并销售一个落地摆钟产生的利润是 300 美元，每个墙钟为 200 美元。现在，三个业主希望能够得到各种产品产量的最优组合，以使得利润最大化。将会讨论牛奶约束，所以该部分在下面的图中隐去了） 。（ 1）为该问题建立线性

11、规划模型。（ 2） 如果落地摆钟的单位利润从 300 美元增加到 375 美元， 而模型的其他不变， 最优解是否会改变。 然后用该模型检验如果墙钟的单位利润也从 200 美元变动到 175 美元，最优解是否会改变。（ 3）在电子表格上建立和求解该问题的原始模型。（ 4）运用 Excel 分析，如果落地摆钟的单位利润在 150 美元到 450 美元之间每增加 20 美元给最优解和总利润带来的影响（墙钟单位利润不变） 。然后同样分析，当墙钟的单位利润在 50 美元岛 50 美元之间每增加 20美元给最优解和总利润带来的影响 （落地摆钟单位利润不变） 。 而模型的其他不变， 运用灵敏度报告确定最优解

12、是否会改变？用这些信息来估计每种钟单位利润允许取值范围。（ 5）象（ 4）中一样，只是每增加 20 美元变为每增加 50 美元，给最优解带来的影响。（ 6）依次对每个业主用 Excel 分析，如果他们决定将自己的最大可用工时增加 5 小时每周，那么给最优解和总利润带来的影响。（ 7）运用 Excel 分析，如果只是大卫将最大可用工时变为 35、 37、 39、 41、 43、 45 时最优解和总利润的变化。 然后同样分析， 莱蒂娜将可用工时进行上述改变时的情况。 最后分析， 当莉迪亚将最大可用工时变为 15、17、 19、 21、 23、 25 时最优解和总利润的变化。（ 8）生成 Excel

13、 灵敏度报告，用它来决定每种钟的单位利润和每个业主的最大可用工时的允许变化范围。任务所需时间（小时）落地摆钟 墙钟组装机械配件雕刻木质外壳运输6 8 3 4 4 3 （ 9） 为了增加总利润， 三个业主同意增加他们三个人中的一个人的工作时间， 增加该人的工作时间必须能够最大限度地增加总利润。运用灵敏度报告，确定应该选择哪一个人（假设模型的其他部分没有任何变动） 。（ 10）解释为什么有一个人的影子价格是 0。（ 11）如果莉迪亚将工作时间从每周的 20 小时增加到 25 小时，是否可以用影子价格分析该变动对结果的影响？如果影子价格有效，总利润将增加多少？（ 12）在（ 1）中加入另一变动，即大

14、卫的工作时间从每周 40 小时减少到 35 小时，重新分析。三、运输问题和指派问题1、 研究分析一下拥有如下所示参数表的运输问题：单位成本（美元）供应1 2 3 1 2 39 7 6 6 12 7 8 10 6 4 3 2 需求 4 2 3 （ 1）画出这个问题的网络表示图。（ 2）用电子表格描述这个问题，然后使用 Excel 得到最优解决方案。2、 考虑拥有如下所示参数表的运输问题：（ 1）画出这个问题的网络表示图。（ 2）用电子表格描述这个问题，然后使用 Excel 得到最优解决方案。3、 考斯雷司（ Cost-Less）公司从它的工厂向它的四个零售点供应货物，从每一个工厂到每一个零售点供

15、应货物，从每一个工厂到每一个零售点的运输成本如下所示：工厂 1、 2、 3、 4 每个月的生产量为 10、 20、 20、 10 个运输单位。零售点 1、 2、 3、 4 每个月所需货物量为20、 10、 10、 20 个运输单位。配送经理兰迪史密斯现在需要确定每个月从每一个工厂制中药运送多少给相应零售点的最佳方案。兰迪的目标就是要使总的运输成本最小。（ 1）把这个问题描述为一个运输问题并写出相应的出发地、供应量、目的地、需求量和单位成本。（ 2）用电子表格描述这个问题，然后使用 Excel 得到最优解决方案。目的地出发地单位成本（美元）供应1 2 3 4 1 2 33 2 4 7 4 3 6

16、 3 8 4 2 5 5 2 3 需求 3 3 2 2 零售点工厂单位成本（美元）1 2 3 4 1 2 3 4500 200 300 200 600 900 400 100 400 100 200 300 200 300 100 200 销地产地4、 恰德费尔（ Childfair ）公司拥有三个生产折叠婴儿车的工厂，并运往四个配送中心。工厂 1、 2 和 3 枚月产量为 12、 17、 11 个运输单位。同时配送中心每月需要 10 个运输单位的货物。从每一个工厂到每一个配送中心的路程如下表所示：每一个运输单位的运输成本为每英里 100.5 美元。（ 1）把这个问题描述为一个运输问题并写出相应的出发地、供应量、目的地、需求量和单位成本。（ 2）用电子表格描述这个问题，然后使用 Excel 得到最优解决方案。5、 汤姆想要在今天买 3 品脱的家酿酒，明天买另外的 4 品脱。迪克想要销售 5 品脱的家酿酒，今天的价钱为每品脱 3.00 美元， 而明天的价钱是每品脱 2.70 美元。 哈里想要销售 4