《运筹学》知识点全总结

一、线性规划：基本概念1、下面的表格总结了两种产品A和B的关键信息以及生产所需的资源Q,R,S：资源每单位产品资源使用量可用资源产品A产品BQRS213123224利润/单位3000美元2000美元满足所有线性规划假设。（1）在电子表格上为这一问题建立线性规划模型；（2）用代数方法建立一个相同的模型；（3）用图解法求解这个模型。5、普里默（Primo）保险公司引入了两种新产品：特殊风险保险和抵押。每单位特殊风险保险的利润是5美元，每单位抵押是2美元。管理层希望确定新产品的销售量使得总期望利润最大。工作的要求如下：部门每单位工时可使用工时特殊风险抵押承保管理索赔30221024008001200（1）为这个问题在电子表格上建立一个线性规划模型并求解。（2）用代数形式建立相同的模型。8、拉尔夫·艾德蒙（RalphEdmund）喜欢吃牛排和土豆，因此他决定将这两种食品作为正餐的全部（加上一些饮料和补充维生素的食品）。拉尔夫意识到这不是最健康的膳食结构，因此他想要确定两种食品的食用量多少是合适的，以满足一些主要营养的需求。他获得了以下营养和成本的信息：成分每份各种成分的克数每天需要量（克）牛排土豆碳水化合物蛋白质脂肪520151552≥50≥40≤60每份成本4美元2美元拉尔夫想确定牛排和土豆所需要的份数（可能是小数），以最低的成本满足这些需求。（1）为这个问题在电子表格上建立一个线性规划模型并求解。（2）用代数形式建立相同的模型；（3）用图解法求解这个模型。二、线性规划的what-if分析1、G.A.T公司的产品之一是一种新式玩具，该产品的估计单位利润为3美元。因为该产品具有极大的需求，公司决定增加该产品原来每天1000件的生产量。但是从卖主那里可以购得的玩具配件（A,B）是有限的。每一玩具需要两个A类配件，而卖主只能将其供应量从现在的每天2000增加到3000。同时，每一玩具需要一个B类的配件，但卖主却无法增加目前每天1000的供应量。因为目前无法找到新的供货商，所以公司决定自己开发一条生产线，在公司内部生产玩具配件A和B。据估计，公司自己生产的成本将会比从卖主那里购买增加2.5美元每件（A,B）。管理层希望能够确定玩具以及两种配件的生产组合以取得最大的利润。将该问题视为资源分配问题，公司的一位管理者为该问题建立如下的参数表：资源每种活动的单位资源使用量可获得的资源总量生产玩具生产配件配件A配件B21-1-130001000单位利润3美元-2.5美元（1）为该问题建立电子表格模型并求解。（2）因为两类活动的单位利润是估计的，所以管理层希望能够知道，为了保持最优解不变，估计值允许的变动范围。针对第一个活动（生产玩具），运用电子表格，求出该活动单位利润从2美元增加到4美元每次增加50美分时问题的最优解和总利润。在最优解不变的前提下，单位利润可以偏离其初值3美元多少？（3）针对第二个活动（生产配件），重复（2）的分析，该活动的单位利润从-3.5美元增加到-1.5美元（第一种活动的单位利润固定在3美元）。（4）运用Excel灵敏度报告来找到每个活动单位利润的允许变动范围。（5）运用Excel灵敏度报告来描述在最优解不变的前提下，两个活动单位利润最多同时能改变多少。4、K&L公司为其冰激凌经营店供应三种口味的冰激凌：巧克力、香草和香蕉。因为天气炎热，对冰激凌的需求大增，而公司库存的原料已经不够了。计这些原料分别为：牛奶、糖和奶油。公司无法完成接收的订单，但是为了在资源有限的条件下使利润最大化，公司需要确定各种口味产品的最优组合。巧克力、香草和香蕉三种口味的冰激凌的销售利润分别为每加仑1.00美元、0.90美元和0.95美元。公司现在有200加仑牛奶、150磅糖和60加仑奶油的库存。这一问题代数形式的线性规划表示如下：假设：C=巧克力冰激凌的产量（加仑），V=香草冰激凌的产量（加仑），B=香蕉冰激凌的产量（加仑）最大化：利润=1.00C0.90V0.95V约束条件牛奶：0.45C0.50V0.40B≤200（加仑）糖：

0.50C0.40V0.40B≤50（加仑）奶油：0.10C0.15V0.20B≤60（加仑）且

C≥0，V≥0，B≥0使用Excel求解，求解后的电子表格和灵敏度报告如下图所示（注意，因为在（6）中将会讨论牛奶约束，所以该部分在下面的图中隐去了）。不用Excel重新求解，尽可能详尽地回答下列问题，注意，各个部分是互不干扰、相互独立的。ABCDEFG1巧克力香草香蕉2单位利润1.000.900.9534原料每加仑冰激凌所用原料所需原料可用原料5牛奶0.450.50.4180≤2006糖0.50.40.4150≤1507奶油0.10.150.260≤6089巧克力香草香蕉总利润10每加仑030075341.25可调单元格单元格名称最终价值成本削减目标系数增加上限降低下限$C$10每加仑巧克力用量0-0.037510.03751E30$D$10每加仑香草用量30000.90.050.0125$E$10每加仑香蕉用量7500.950.02140.05约束单元格名称最终价值影子价格右端值增加上限降低下限$F$5所用牛奶量$F$6所用糖量1501.8751501030$F$7所用奶油量60160153.75（1）最优解和总利润是多少？（2）假设香蕉冰激凌每加仑的利润变为1.00美元，最优解是否改变，对总利润又会产生怎样的影响？（3）假设香蕉冰激凌每加仑的利润变为92美分，最优解是否改变，对总利润又会产生怎样的影响？（4）公司发现有3加仑的库存奶油已经变质，只能扔掉，最优解是否改变，对总利润又会产生怎样的影响？（5）假设公司有机会购得15磅糖，总成本15美元，公司是否应该购买这批糖，为什么？（6）在灵敏度报告中加入牛奶的约束，并解释如何减少各种产品的产量？5、大卫、莱蒂娜和莉迪亚是一家生产钟表的公司业主以及员工，大卫、莱蒂娜每周最多工作40个小时，而莉迪亚每周最多能工作20个小时。该公司生产两种不同的钟表：落地摆钟和墙钟。大卫是机械工程师，负责装配钟表内部的机械部件；而莱蒂娜是木工，负责木质外壳的手工加工；莉迪亚负责接收订单和送货。每一项工作所需时间如下表所示：任务所需时间（小时）落地摆钟墙钟组装机械配件雕刻木质外壳运输683443每生产并销售一个落地摆钟产生的利润是300美元，每个墙钟为200美元。现在，三个业主希望能够得到各种产品产量的最优组合，以使得利润最大化。将会讨论牛奶约束，所以该部分在下面的图中隐去了）。（1）为该问题建立线性规划模型。（2）如果落地摆钟的单位利润从300美元增加到375美元，而模型的其他不变，最优解是否会改变。然后用该模型检验如果墙钟的单位利润也从200美元变动到175美元，最优解是否会改变。（3）在电子表格上建立和求解该问题的原始模型。（4）运用Excel分析，如果落地摆钟的单位利润在150美元到450美元之间每增加20美元给最优解和总利润带来的影响（墙钟单位利润不变）。然后同样分析，当墙钟的单位利润在50美元岛50美元之间每增加20美元给最优解和总利润带来的影响（落地摆钟单位利润不变）。而模型的其他不变，运用灵敏度报告确定最优解是否会改变？用这些信息来估计每种钟单位利润允许取值范围。（5）象（4）中一样，只是每增加20美元变为每增加50美元，给最优解带来的影响。（6）依次对每个业主用Excel分析，如果他们决定将自己的最大可用工时增加5小时每周，那么给最优解和总利润带来的影响。（7）运用Excel分析，如果只是大卫将最大可用工时变为35、37、39、41、43、45时最优解和总利润的变化。然后同样分析，莱蒂娜将可用工时进行上述改变时的情况。最后分析，当莉迪亚将最大可用工时变为15、17、19、21、23、25时最优解和总利润的变化。（8）生成Excel灵敏度报告，用它来决定每种钟的单位利润和每个业主的最大可用工时的允许变化范围。（9）为了增加总利润，三个业主同意增加他们三个人中的一个人的工作时间，增加该人的工作时间必须能够最大限度地增加总利润。运用灵敏度报告，确定应该选择哪一个人（假设模型的其他部分没有任何变动）。（10）解释为什么有一个人的影子价格是0。（11）如果莉迪亚将工作时间从每周的20小时增加到25小时，是否可以用影子价格分析该变动对结果的影响？如果影子价格有效，总利润将增加多少？（12）在（1）中加入另一变动，即大卫的工作时间从每周40小时减少到35小时，重新分析。三、运输问题和指派问题1、研究分析一下拥有如下所示参数表的运输问题：单位成本（美元）供应12312397661278106432需求423（1）画出这个问题的网络表示图。（2）用电子表格描述这个问题，然后使用Excel得到最优解决方案。2、考虑拥有如下所示参数表的运输问题：目的地出发地单位成本（美元）供应1234123324743638425523需求3322（1）画出这个问题的网络表示图。（2）用电子表格描述这个问题，然后使用Excel得到最优解决方案。3、考斯雷司（Cost-Less）公司从它的工厂向它的四个零售点供应货物，从每一个工厂到每一个零售点供应货物，从每一个工厂到每一个零售点的运输成本如下所示：零售点工厂单位成本（美元）12341234500200300200600900400100400100200300200300100200工厂1、2、3、4每个月的生产量为10、20、20、10个运输单位。零售点1、2、3、4每个月所需货物量为20、10、10、20个运输单位。配送经理兰迪·史密斯现在需要确定每个月从每一个工厂制中药运送多少给相应零售点的最佳方案。兰迪的目标就是要使总的运输成本最小。（1）把这个问题描述为一个运输问题并写出相应的出发地、供应量、目的地、需求量和单位成本。（2）用电子表格描述这个问题，然后使用Excel得到最优解决方案。4、恰德费尔（Childfair）公司拥有三个生产折叠婴儿车的工厂，并运往四个配送中心。工厂1、2和3枚月产量为12、17、11个运输单位。同时配送中心每月需要10个运输单位的货物。从每一个工厂到每一个配送中心的路程如下表所示：零售点工厂到配送中心的距离（英里）123412380011006001300140012004006008007001000900每一个运输单位的运输成本为每英里100.5美元。（1）把这个问题描述为一个运输问题并写出相应的出发地、供应量、目的地、需求量和单位成本。（2）用电子表格描述这个问题，然后使用Excel得到最优解决方案。5、汤姆想要在今天买3品脱的家酿酒，明天买另外的4品脱。迪克想要销售5品脱的家酿酒，今天的价钱为每品脱3.00美元，而明天的价钱是每品脱2.70美元。哈里想要销售4品脱的家酿酒，今天的价钱为每品脱2.90美元，而明天的价钱为每品脱2.80美元。汤姆想要知道他要如何进行购买才能在满足他的口渴需求的基础之上，使他的购买成本达到最小值。为这个问题建立电子表格模型并解决它。9、万诺特（Onenote）公司为四个顾客在三个工厂生产一种产品。在未来一周内这三个工厂的产量为60、80、40单位。公司决定向顾客1供应40个单位，向顾客2供应60个单位，向顾客3至少要供应20个单位。顾客3和4都想要尽可能多地购买剩下的产品。从工厂i运送单位数量的产品给顾客j的净利润如下表所示（单位：美元）：顾客工厂到每一个顾客的单位净利润（美元）1234123800500600700200400500100300200300500管理层希望知道为了使利润最大，应当向顾客3和4提供多少单位的产品以及应当从每一个工厂向每一个顾客运送多少单位的产品。用电子表格描述这个问题并求解。14、考虑拥有如下所示成本表的指派问题（单位：美元）：工作人员相关成本（美元）123ABC532763454最优解是A-3，B-1，C-2，总的成本是10美元。（1）画出这个问题的网络表示图。（2）在电子表格上对这个问题进行描述，并使用Excel得到最优解。15、考虑拥有如下所示的成本表的指派问题（单位：美元）：工作被指派者到每一个顾客的单位净利润（美元）1234ABCD8676658753457466（1）画出这个问题的网络表示图。（2）在电子表格上对这个问题进行描述，并使用Excel得到最优解。16、四艘货船要从一个码头向其他的四个码头运货（分别积为1、2、3、4）。每一艘船都能够运送到任何一个码头。但是，由于货船和货物的不同，装船、运输和卸货成本都有些不同。如下表所示（单位：美元）：码头货船相关成本（美元）1234ABCD500600700500400600500400600700700600700500600600目标是要把这四个不同的码头指派给四艘货船，使总运输成本最小。（1）请解释为什么这个问题符合指派问题模型。（2）在电子表格中描述这个问题并求解。语文数学物理化学张王李赵926885768291776383907