下载掌阅APP，畅读海量书库
立即打开
按照同业公会公布的数字，布里斯烟草公司的成本要比主要的竞争对手高 20%,这事引起了公司董事长的注意。
该公司专门生产带有异国情调的香烟。那些对大公司的标准香烟不满的人正转向这类商品，因而虽然该公司目前的市场还小，却正在日渐扩大。公司的高成本有一部分是因为生产规模有限造成的，但董事长仍然认为，如果想增加市场份额，降低成本是可行而且是必要的措施。
董事长请工业工程部的负责人大卫解决成本管理问题。大卫马上指派他手下的首席分析员托尼以全部工作时间同他一起去做这件事。
大卫和托尼着手的第一步是详细分析香烟生产的费用，在这些费用中只有属于原材料消耗的与同行业其他公司的费用相当，而且看来也没有多大利润。最有可能降低成本的似乎是在制造和运输方面，而分析的结果也表明确实如此。譬如说，专为薄荷烟设计的工厂也一本正经地生产了许多种其他香烟，这样的混合生产谈不上效率，显然是轻率决策的结果。在此认识下，他们起草了一份呈交董事长批准的行动计划。
大卫和托尼都认为，必须把不同品种香烟的生产派给相宜的工厂，才能保证制造的效率。他们做过的初步调查还表明有可能获得必要的信息，去建立生产分派模型。因为模型只需在制订年度计划时使用，收集数据的时间相当充裕，使得用线性规划作为分派模型是可行的，所以他们就着手建立用线性规划作所需决策的模型。
布里斯公司下辖五家工厂，总共生产130 多种香烟。现在要做的资源分配决策是决定在各个工厂里分别生产哪几种香烟及其数量。
资源分配工作的目标是使扣除成本后的销售收入最大化。模型所受的约束则是工厂的生产能力、对各种产品的需求、关于烟草的限额。
董事长委托生产部副经理鲍勃来检查刚拟出大纲的正在构模的项目。鲍勃是个 40 刚出头的精明挑剔的管理者，他在一所著名学府取得管理学硕士学位，后来在布里斯公司里飞黄腾达。在读硕士时鲍勃就知道有线性规划，而令大卫和托尼烦恼的是鲍勃的经营学教授已使鲍勃有了线性规划难以应用于实际问题的先入为主之见。在他学习时，求解线性规划问题使用的是一板一眼的迭代步骤，这至今仍让他生厌，而且他还认为线性规划是严格的数值计算，无法兼顾定性因素。
鲍勃虽有所怀疑，但还是耐心地听取了介绍，然后发问：“模型里有多少变量？”这么详细的问题真是出人意料，好在大卫事先估计过模型的规模。
“一千个变量和三百来个约束。”大卫在回答时带着对模型规模的自豪，却没有想到副经理的反应大大不妙。
“你说什么！天呀，这可够你们算一辈子的了!”
“不，阁下，”托尼插嘴说：“新的计算机系统效率很高，要不了多少时间就可以计算出结果来。”
鲍勃没有被说服，他又问起数据：“你们想过收集数据要多少时间吗?”
“我们可以编一个生成数据库的程序。”托尼说。
“我是问多少时间？”副经理盯住不放。
“我们跟数据处理部门联系过，他们说我们可在半年内收集齐数据。”
“什么！”鲍勃叫起来。“董事长必须在下个月的董事会议前作出决策，你们知道吗?”
这可真的进退两难了，大卫踌躇了好几分钟。突然，他眼睛一亮，挂在副经理办公室墙上的一张意大利风景画让他有了一个主意。在运筹学文献里不是提到过一个意大利人吗，他叫什么名字来着？对,帕累托！他讲过一条普遍规律，今天就被称作ABC分类法。
大卫没头没脑地问了一句：“占我们公司销售总数 80%的产品有几种啊?”
“不多，这我可以断定。”鲍勃回答他。“让我查一下，据报告给我的数据，有 12 种产品的销售额占总数的 87%。”
“这样的话就有办法了，就只以这 12 个产品作为模型的对象。数据收集工作也可以用人力进行。”
“搞出模型要多长时间呢?”
“我想在三个星期内就可以给你一个结论了。”大卫说。
“那好，请记住，我们需要的是在短期内解决大问题，问题的重要性用不着多说。别搞那些只能供在象牙塔里的货色。”
最后一句话让人听了不怎么舒服，但大卫和托尼离开办公室时的心情是很复杂的。这是一个在重大决策上显身手的难得的机会，但也是弄不好就会把饭碗砸掉的挑战。
经过副经理鲍勃的督促，大卫和托尼开始将模型具体化，而且很快就完成了。因为有公司最高领导的关注，数据收集工作比正常情况下要顺利得多。在大卫的经验中，会计部门的合作如此尽力还属第一次。经过有限的调整，两位分析者就尝试着让模型运行。模型的结果看来是合情合理的，他们准备向鲍勃汇报。
向鲍勃介绍的结果总结如表 2 -15 所示。
表 2 -15 香烟生产的分派
单位：箱
(续上表)
注：香烟类型的代号略(所引文献译者)。
按照这一分派计划，费用约为 30 500 万美元，要比目前的实际费用少2 100万美元。大卫很受模型结果的鼓舞，满怀喜悦地盼望着与鲍勃的会面。
但是鲍勃的反应却不是那么回事，他说：“这个方案是荒唐的，大卫，你本应该知道得再多一些的，你知道公司有多少烘炉用于香烟生产？如果B城的烘炉坏了，会有什么结果？你只能停止三种香烟的生产。烘炉一修就要六个月，计划中只有B城生产的三种烟就完全脱销了。”
大卫因为未能事先在模型里考虑烘炉条件而难受，但他很快就指出，只要增加一类约束条件就能解决这个难题：某几种香烟在任何工厂里生产的百分比不能超过某个固定值。鲍勃欣赏大卫的这个主意，并把不能超过的百分数定为 60。再次运行模型后得到的结果汇总如表 2 -16 所示。
表 2 -16 修正过的香烟生产的分派
单位：箱
大卫有点遗憾地说：“与现在的情况比，我们省了 1 300 万美元，比我们的第一个方案则多花了 800 万美元。”
在提出正式报告之前，他们先把结果送给鲍勃。鲍勃再一次提出问题：“你们让P城的工厂每月生产 270 000 箱香烟，但我们可不能只为了这么点产量就维持一个厂啊!”
大卫他们商量后决定把P城的工厂排除在模型之外，并把由此获得的结论交给鲍勃。
“这个结论看来好多了，可以节省多少钱?”
“我要告诉你，在模型里为烘炉付 800 万美元保险费还是便宜的。我们去见董事长吧!”
董事长很高兴，但报告中有一点令他不安。他曾经担任过公司在P城工厂的厂长，因此很清楚关闭工厂对城市会有什么影响。在考虑一段时间之后，他决定采纳报告中的建议，但他又要求将P城的工厂改建为地区性仓库，以减少因工厂停产而造成的失业人数。
大卫母校的运筹学组织有一条规定：学生(校友）利用运筹学使所服务的单位获利(节约）超过 1 000 万美元的可获得一枚镶有钻石的奖章。该大学派人核实了由大卫负责的这次研究，并给大卫颁发了钻石奖章。
1.试描述模型必须做哪些变动。大卫和托尼是否应该自己先想到这些问题?
2.鲍勃关于花 800 万美元为烘炉保险的话正确吗?
3.一个分配模型对于像关掉P城工厂这样的定性决定应该持何态度?
4.用其他办法有可能得到相同的结论吗?
5.在什么情况下，隔多长时间，就应该重新评价这些结果？关闭P城的工厂是不是一个明智的决策?
1.某公司生产甲和乙两种产品，它们的单位利润分别是 300 元和 200 元。该公司有两个机械加工中心，它们每天工作的有效时间分别为 20 小时和 18 小时。每种产品都须经过两个中心加工，生产每单位产品甲在加工中心A需要 1 小时，在中心B需要 3 小时。生产每单位产品乙在中心A和B各需要 2 小时和 1 小时。根据市场调查得知产品甲每天的需求量不会超过 5 单位，而产品乙无论生产多少均能销售完。问公司应如何安排生产才能获利最大？试建立问题的线性规划模型，并用图解法求解。
2.用图解法解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解，还是无可行解?
(1)
(2)
(3)
(4)
3.某一企业家需要找人清理 5 间会议室、12 张桌子与 18 个货架。今有两个临时工A和B供该企业家雇用。 A一天可清理 1 间会议室、3 张桌子与 3 个货架; B一天可清理 1间会议室、2 张桌子与 6 个货架。 A的工资每天 25 元, B每天 22 元。为了使成本最低，应雇用A和B各多少天？(用线性规划图解法求解)
4.找出下列线性规划问题的两个基可行解，并写出约束方程组相应的典式。
5.将下列线性规划问题转化为标准型，并作出初始单纯形表。
(1)
(2)
6.用单纯形法求解习题 1 和习题 2 (4),并指出单纯形法迭代的每一步对应于可行域中的哪一个顶点。
7.讨论如何使用单纯形法求解下述线性规划问题。
8.解下列线性规划问题，并指出问题的解属于哪一类。若有多个最优解，请找出三个最优解。
(1)
(2)
(3)
(4)
(5)
9.设( SLP)有
k
个不同的最优解
X
(1)
,
X
(2)
,…,
X
(k
)。证明：对于任意
α
i
∈[0,1],满足
= 1,
X
=
也是最优解(这个结论表明最优解的凸组合也是最优解)。
10.表 2 -17 是某个求最大化的线性规划问题迭代到某一步的单纯形表。问各常数 H i ( i = 1,…,6)满足什么条件时，以下结论成立。
(1)当前解为唯一最优解。
(2)当前解为最优解，但存在无穷多最优解。
(3)该线性规划问题具有无界解。
(4)当前解为退化的基最优解。
(5)当前解非最优，但令 x 1 进基, x 2 出基后，目标函数能够改进。
表 2 -17
11.判断下列说法是否正确。
(1)在求最大化的线性规划模型中增加一个约束条件，目标函数的最优值将减少或不变；减少一个约束条件，目标函数的最优值将增加或不变(假定模型改变后仍存在最优解)。
(2)若线性规划的可行域无界，则它具有无界解。
(3)若(SLP)没有最优基可行解，则一定没有最优解。
(4)单纯形法计算中，若不按最小比值规则选取出基变量，则在下一个解中至少有一个基变量的值为负。
(5)(SLP)的每一个基解对应可行域的一个顶点。
(6)对一个有 n 个变量、 m 个约束方程的(SLP),其基可行解的正分量数目有可能大于 m 。
(7)对一个有
n
个变量、
m
个约束方程的(SLP),其基可行解的数目恰好为
个。
(8)一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。
(9)对自由变量
x
k
,通常令
x
k
=
-
,其中,
≥0,
≥0,在用单纯形法求得的最优解中不可能同时出现
> 0,
> 0。
12.某求极大化线性规划问题的最优单纯形表如表 2 -17 所示，已知该问题的所有约束为“≤”型, x 4 和 x 5 为松弛变量。
(1)求该线性规划问题的另外三个最优解。
(2)试求出表 2 -18 对应的最优基 B 和 B - 1 ,并写出原问题。
表 2 -18
13.在本章例 3 中，医院支付给护士的工资为:6:00 ~ 18:00 每小时 3 元,18:00 ~ 23:00 每小时 4 元,23:00 ~ 6:00 每小时 5 元。并要求 2:00 开始上班的人数不得超过 4 人。求最优安排方案。
14.某炼油厂使用三种原料油甲、乙、丙混合加工成A、 B、 C三类不同的汽油产品，有关数据如表 2 -19 所示。另外，由于市场原因, A的产量不得低于产品总量的 40%。问该厂应如何安排生产才能使其总利润最大?
表 2 -19
15.某公司从中心制造地点向四个分别位于城区北、东、南、西方向的分配点送材料。该公司有 26 辆卡车，用于从制造地点向分配点运料。其中有 9 辆是每辆能装 5 吨的大型卡车,12 辆是每辆能装 2 吨的中型卡车和 5 辆是每辆能装 1 吨的小型卡车。某天，北、东、南、西四个分配点分别需要材料 14 吨、10 吨、20 吨和 8 吨。每种卡车向各分配点送料一次的费用如表 2 -20 所示。若每辆卡车只送料一次，公司应如何安排才能使运料的总费用最小?
表 2 -20
单位：元
16.某厂要制订一个产品宣传计划，可利用的广告渠道有电视、广播、杂志三种。市场调查的结果如表 2 -21 所示。该厂计划用于广告费用不超过 16 万元。此外还要求:(1)受到广告影响的妇女至少要有 20 万人;(2)电视广告费用不超过 10 万元;(3)白昼电视至少要订 3 个广告，热门时间至少 2 个广告;(4)广播和杂志上的广告数都应在5 ~ 10之间。试问该厂如何制订一个广告计划，使受到影响的总人数最多?
表 2 -21
17.有A、 B两种产品，都须经过两个化学反应过程。每一单位产品A需要在前一工序中花去 2 小时和在后道工序中花去 3 小时；每一单位产品B需要在前一工序中花去 3 小时和在后道工序中花去 4 小时。可供利用的前一工序的时间为 200 小时，后道工序的时间为 240 小时。每生产 1 个单位的产品B同时也能得到 2 个单位的副产品C。出售产品A每单位能获利 5 元，产品B每单位能获利 10 元，副产品C每单位能获利 3 元。卖不出去的产品C必须销毁，单位产品销毁费用是 1 元。由市场预测知，最多售出 10 个单位的产品C。试问如何安排生产计划可使获得的利润最大。
18.某造纸厂生产宽度为 3 米的卷筒纸，再将这种大卷筒切成宽度分别为 1.6 米、1.1米和 0.7 米的小卷筒。市场对这三种小卷筒的需求分别是 100、200 和 400 个。问应以怎样的方法切割，可使耗用的大卷筒最少而又能满足市场的需求？最优切割方案是否唯一?
19.一家化工厂生产洗衣粉和洗涤剂。生产原料可以从市场上以每千克 5 元的价格买到。处理 1 千克原料可生产 0.55 千克普通洗衣粉和 0.35 千克普通洗涤剂。普通洗衣粉和普通洗涤剂可分别以每千克 8 元和 12 元的价格在市场上出售。市场对普通洗衣粉的最低需求是每天 1 000 千克。工厂设备每天最多可处理 10 吨原料，每加工 1 千克原料的成本为1.5 元。为生产浓缩洗衣粉和高级洗涤剂，工厂还可继续对普通洗衣粉和普通洗涤剂进行精加工。处理 1 千克普通洗衣粉可得 0.6 千克浓缩洗衣粉，处理 1 千克普通洗涤剂可得0.3 千克高级洗涤剂。浓缩洗衣粉和高级洗涤剂的市场价格分别为每千克 24 元和 55 元。每千克精加工产品的加工成本为 3 元。如果原料供应没有限制且各类产品畅销，问该工厂如何生产能使其利润最大?
20.某工厂生产三种产品Ⅰ、Ⅱ、Ⅲ,每种产品要经过A、 B两道工序加工。设该厂有两种规格的设备能完成A工序，它们以A 1 、 A 2 表示；有三种规格的设备能完成B工序，它们以B 1 、 B 2 、 B 3 表示。产品Ⅰ可在A、 B任何一种规格的设备上加工；产品Ⅱ可在任何规格的A设备上加工，但完成B工序时，只能在B 1 设备上加工；产品Ⅲ只能在A 2 与B 2 设备上加工。假定产品Ⅰ的销售量不超过1 500单位。已知三种产品在各设备上加工时，单位产品用的工时数(单位工时）、原材料费、产品销售价格、各种设备有效台时以及满负荷操作时设备的费用和人工费如表 2 -22 所示，要求安排最优的生产计划，使该厂利润最大。
表 2 -22
21.某公司在第一年有 100 万元资金。每年都有以下的投资方案可供考虑采纳：“假如今年投入一笔资金，明年又继续投入此资金的 50%,那么到后年就可收回今年年初投入资金的两倍金额。”试问该公司要如何决定最优投资策略才可使第六年拥有的资金最多?
22.某企业使用三种有限的资源生产两种产品A和B。这三种资源为成形时间、装配时间和油漆时间。生产一件产品A所需要的成形时间、装配时间和油漆时间分别为 8、6 和 4分钟；而产品B分别为 4、9 和 3 分钟。今年头四个月企业收到的订单数量，产品A都是每月 1 800 件，产品B分别为 2 500、2 000、3 000 和 1 000 件。
在第一和第二个月，产品A和B的单位利润分别为 17 元和 14 元。成形中心、装配中心和油漆中心每月可用的时间分别为 32 000、40 000 和 15 000 分钟。在第三和第四个月，产品A和B的单位利润分别变为 15 元和 16 元。油漆中心的扩建使得该中心每月可用的工作时间为 25 000 分钟，其余两个中心每月可用的时间不变。
假定第一个月开始时每种产品的库存有 1 000 件，要求第四个月月底每种产品的库存量必须不少于1 000 件，库存的费用为每月每件 1 元。另外，由于某种原因，在第三个月不能生产产品A,在第四个月不能生产产品B。问企业应如何安排生产才能使四个月的总利润最大？(提示：参看本章例12,并引入双下标变量，其中一个下标表示产品种类，另一个表示月份)
线性规划是运筹学中应用最为广泛的一个重要分支，在经济管理活动中，人们经常使用线性规划模型求解有限资源的最优配置问题。本章介绍了线性规划的数学模型、基本概念、图解法、线性规划的标准型及转化为标准型的方法。单纯形法是求解一般线性规划问题的有效方法，该方法的基本思路是每次迭代从某个基可行解(顶点）转移到另一个“更好”的基可行解(顶点），经过有限步骤可找到问题的最优解或发现问题具有无界解。本章还介绍了单纯形法的基本原理和计算步骤，包括寻找初始基可行解的人工变量方法，并探讨求多个最优解的问题。作为应用，章末给出了若干有代表性的例子和案例。
实际问题形成的线性规划模型都必须使用计算机求解，本章详细介绍了使用计算机软件求解线性规划的具体步骤和结果。