案例10

1.2 线性规划应用举例

如何将一个复杂的实际问题转化为一个合理的线性规划模型既是一门科学，又是一门艺术。仅仅了解求解线性规划的数学原理是不够的，还需要在实践中学习将实际问题抽象为数学模型的技巧，不断总结和提高构造模型的技术，才能真正将线性规划技术应用到实际中。下面再列举几个比较典型的线性规划问题。

1.2.1 调和问题

调和问题是研究将若干种不同的原料按一定的技术要求调和成不同的产品，例如化工、塑料、冶炼、石油加工都会遇到调和问题。典型的调和问题包含了具有不同技术特性的原料和产品并有相应的成本和价格与之相关。调和问题的目标是在满足产品需求和调和指标的前提下使调和成本最小或生产收益最大。

例1.4 新星炼油厂生产三种牌号的汽油：70＃，80＃和85＃汽油。每种汽油有不同的辛烷值和含硫量的质量要求并由三种原料油调和而成。每种原料也有不同的质量指标。每种原料每日可用数量、质量指标和生产成本见表1.2，每种汽油的质量要求和销售价格见表1.3。问该炼油厂如何安排生产才能使其利润最大？假定在调和中辛烷值和含硫量指标都符合线性相加关系。

表1.2 汽油组分的质量和成本数据

序号i 1 2 3 原料 直馏汽油 催化汽油 重整汽油 辛烷值 62 78 90

1

含硫量％ 1.5 0.8 0.2 成本(元/吨) 600 900 1400 可用量(吨/日) 2000 1000 500 表1.3 汽油产品的质量和价格数据

序号i 1 2 3 产品 70＃汽油 80＃汽油 85＃汽油 辛烷值 ≥70 ≥80 ≥85 含硫量％ ≤1 ≤1 ≤0.6 销售价(元/吨) 900 1200 1500 这个问题要比前两个问题要复杂一些。首先决策变量的选择就不很直观。如果定义决策变量为各种汽油的产量，在写模型时会遇到不少麻烦。正确的方法是定义决策变量xij代表第i种原料调入第j种成品汽油的数量。令pj代表第

j种产品的销售价格，ci为第i种原料的生产成本，ei和ej分别为原料和产品的

辛烷值，hi和hj分别为原料和产品的含硫量，si为原料每日的可用量，则模型可写为：

max??(pj?ci)xij

i?1j?133s..t?(ei?ej)xij?0 j?1,2,3

i?133

?(h?h)x?ijiji?10 j? 1 ,2 ,3 （1.7）

?xj?13ij?s i i ?1, 2,3 xij?0

模型（1.7）目标函数的意义很清楚：调入j种产品的i种原料的产品售价与原料成本之差(pj?ci)即为调和组分xij对目标函数（利润）的贡献。前两个约束方程分别是辛烷值和含硫量的质量约束，每种产品都有两个质量约束。我们仅举70＃汽油的辛烷值含量为例来说明这些约束的写法。该约束写可为：

62x11?78x21?90x31?70(x11?x21?x31)

（1.8）

不等式（1.8）左边是调入70＃汽油不同组分油辛烷值含量的总和，右端则为

2

70＃汽油质量要求的最低标准，x11?x21?x31代表70＃汽油的实际产量，整理后可得：

(62?70)x11?(78?70)x21?(90?70)x31?0

（1.9）

式（1.9）与（1.7）的形式一样。最后一组约束表示所用原料不能超过原料可用量的限制。将数据代入并化简后的模型如下：

max 300x11?600x12?900x13?300x22 ?600x23?50x031?2x0302?1x 00s.. t?8x11?8x21?20x31?0 ?18x12?2x22?10x ?? 0.5x11?0.x2?21 0.5x12?0.x2?22 0.9x13?0.x2?2332? 00.x38?1 0.x38?2 0.x34?3

000 x11?x1?2000 2x?13 x21?x2?1000 2x?23 x31?x3?500 2x?33 xij?0 i ?1,2j,?3; 11.2.2 生产工艺优化问题

许多企业的生产过程是一个连续的生产过程，各道工序之间有紧密和稳定的联系，这些生产过程是可以用数学模型来描述的。应用数学模型，人们可以优化生产过程，提高设备利用效率，提高企业的经济效益。特别是线性规划可以求解规模较大的问题，因此在生产工艺优化方面大有用武之地。

例1.5 佳丽化工厂生产洗衣粉和洗涤剂。生产原料可以从市场上以每千克5元的价格买到。处理1千克原料可生产0.5千克普通洗衣粉和0.3千克普通洗

3

涤剂。普通洗衣粉和普通洗涤剂可分别以每千克8元和12元的价格在市场上出售。工厂设备每天最多可处理4吨原料，每加工1千克原料的成本为1元。为生产浓缩洗衣粉和高级洗涤剂，工厂还可继续对普通洗衣粉和普通洗涤剂进行精加工。处理1千克普通洗衣粉可得0.5千克浓缩洗衣粉，处理1千克普通洗涤剂可得0.25千克高级洗涤剂。加工示意图见图1.2。浓缩洗衣粉的市场价格为每千克24元，高级洗涤剂的价格为每千克55元。每千克精加工产品的加工成本为3元。如果产品市场和原料供应没有限制，问该工厂如何生产能使其利润最大？

0.5y1千克洗衣粉 x1千克普通洗衣粉 x2千克浓缩洗衣粉 y1千克原材料 0.3y1千克洗涤剂 x3千克普通洗涤剂 x4千克秘级洗涤剂

图1.2 佳丽化工加工示意图

解：设x1为普通洗衣粉的产量，x2为浓缩洗衣粉的产量，x3为普通洗涤剂的产量，x4为高级洗涤剂的产量，y1为原材料的供应量。模型的目标函数可写为：

工厂利润＝8x1?12x3?24x2?55x4?3x2?3x4?(5?1)y1

目标函数的前四项是产品的销售收入，第五项、第六项是精加工成本，最后一项是原料的采购和加工成本。模型的约束主要是物流的平衡约束，例如对洗衣粉生产有如下的平衡关系：0.5y1?x1?x2/5，整理可得：0.5y1?x1?2x2?0；同理可得洗涤剂的平衡约束：0.3y1?x3?4x4?0。最后可得线性规划模型为：

4

max8x1?11x2?21x3?52x4?6y1

s.t 0.5y1?x1?2x2?0 0.3y1?x3?4x4?0

y1?4000 x1,x2,x3,x4,y1?1

1.2.3 多周期动态生产计划问题

线性规划还可以用来描述多周期的动态生产计划问题，在动态的生产计划问题中，管理者可以考虑在不同的生产周期中的生产平衡问题，并可在加班生产平衡和库存中进行权衡以降低总生产成本。下面是一个简单的多周期生产计划的例子。

例1.6 华津机器制造厂专为拖拉机厂配套生产柴油机。今年头四个月收到的订单数量分别为3000台，4500台，3500台，5000台柴油机。该厂正常生产每月可生产柴油机3000台，利用加班还可生产1500台。正常生产成本为每台5000元，加班生产还要追加1500元成本，库存成本为每台每月200元。华津厂如何组织生产才能使生产成本最低？

解：设xi为第i月正常生产的柴油机数，yi为第i月加班生产的柴油机数，

zi为第i月月初柴油机的库存数。如果令di为i月遥需求，第一个月期初的库存为零，则模型的目标函数为：

min?(5000xi?6500yi?200zi)

i?14约束的一般形式为：

xi?yi?zi?zi?1?di i?1,2,3,4

5

模型的详细形式如下：

min 5000(x1?x2?x3?x4)?6500(y1?y2?y3?y4)

?200(z2?z3?z4)

s.. tx1?y1?z2?3000 x2?y2?z2?z3?4500x3?y3?z3?z4?3500 x4?y4?z4?5000

0?xi?3000 i?1,2,3,4 0?yi?1500 i?1,2,3,4 xi?0 i?2,3,4

6

案例10 新英格兰饲料供应公司*

1996年4月14日，新英格兰饲料供应公司（New England Feed Supply Inc, NEFS）的配方分析师杰夫·史密斯（Jeff Smith）在估算波灵顿（Burlington）分厂生产的三种混合饲料下周的需求量。由于有一种原料——肉粉短缺，使NEFS很难完成手头上的合同。史密斯需要决定，是更改饲料配方，还是在自由市场上以高价购买肉粉。若更改配方，应如何更改。

公司简介

新英格兰饲料供应公司是一个生产动物混合饲料的公司。它有12个工厂，分布在新英格兰的主要中心。公司每月从农户、中间商采购主要原料，然后混合成标准的动物饲料，出售给饲料场农户和大的农场公司。NEFS按订单要求混合产品，不保持产品库存，由于原料在不同时间按不同价格购入，每种原料在仓库中的成本，按购买这种原料的总支出除以其在仓库中的吨数计算。

每种出售的混合产品必须要达到或超过国家研究协会（National Research Council, NRC）制订的营养成分含量标准的要求。原料成本占总产品成本的80%以上，因此，取得最低成本的配方就成为公司保持竞争优势和获利能力的关键。

配方

生产工厂直接取得不同类型动物饲料的客户订单。设在总部办公室的配方部门负责向每个工厂发出相应的饲料配方。根据配方部提供的标准饲料配方，每个工厂可确定下一周的原料需求量，并且在星期三上午之前，将这一需求报告总部办公室。由于订购饲料的按时交货对客户的牲畜饲料至关重要，公司的策略是：接下了一个订单就必须完成，不允许缺货（也不允许退还订单）。

*

Drew Parker和钟彼德教授编写。

7

NEFS的每种产品都具有相对稳定的可预测的需求。实际上，每个工厂提供150－200种不同的产品混合物。工厂日常作业是按标准混合配方混料，即使在市场价格或原料成本有少量波动时，仍坚持这一原则。但是，偶尔原料短缺，就不得不要求配方部门重新计算配方，或者想办法从现货市场上以显著高于正常的价格购买短缺的原料。

波灵顿工厂

设立在波灵顿的工厂，混合并销售三种要以肉粉作原料的产品，包括：15%猪饲料、40%猪补充饲料和17%蛋鸡饲料（其中％表示产品中蛋白质的含量）。在准备这些产品生产时，公司必须保证产品能够达到NRC规定的最低营养成分标准。NRC的产品规定标准如表10－1所示。例如1吨15%猪饲料需用0单位的禽类营养素，3000单位的猪营养素，15单位的蛋白质等。表10－1同时还列出了工厂下周各原料的需求量（按吨计）。

表10－1 各种产品需求和需要的营养成分——波灵顿工厂 产品 下周需求（吨） 每吨营养成分需要量 家禽营养素 猪营养素 蛋白质 钙 磷酸盐 赖氨酸 蛋氨酸 甲基胱氨酸 色氨酸

15%猪饲料

400 0 3000 15 0.75 0.60 0.61 0.20 0.30 0.10

40%猪饲料

120 0 2500 40 5.50 2.50 2.00 0.45 0.80 0.25

17%笼养蛋鸡饲料

600 2675 0 17 3.80 0.70 0.68 0.28 0.48 0.15

将各相应数量的原料混合到一起，达到配方所要求的营养成分要求，就可

8

生产出三种产品。所用的原料包括谷物、大麦、豆粉、肉粉、石灰和过磷酸钙。每吨原料中包含有不同的营养成分，如表10－2所示。如每吨谷物中含有3500单位的禽类营养素，表10－2中同时还列出每种原料当前的成本。

表10－2 原料的营养成分和成本

原料 每吨成本（美元） 营养成分含量 营养单位/吨原料 家禽营养素 猪营养素 蛋白质 钙 磷氨酸 赖氨酸 蛋氨酸 甲基胱氨酸 色氨酸

谷物 127 3500 3325 8.70 0.02 0.28 0.20 0.20 0.33 0.09

大麦 145 2865 2870 10.00 0.06 0.33 0.35 0.15 0.32 0.12

豆粉 314 2530 3485 48.4 0.30 0.69 3.20 0.70 1.44 0.63

肉粉 319 1984 2540 50.9 9.70 4.02 2.82 0.62 1.24 0.31

石灰 25 － － － 39 － － － － －

过磷酸钙 405 － － － 16.5 21.0 － － － －

史密斯所面临的基本饲料配方问题，是确定原料的配比以满足每种产品的营养需求，并使成本最低的问题。

为确定每种最终产品的混合比率，史密斯先生需要确保，所选择的用以组成1吨产品的各原料组合重量不超过1吨。如果组合原料重量小于1吨，短缺部分可用加入非营养物填充，基本上不增加成本。

特夫·史密斯（Teff Smith）的问题

公司总部办公室接到通知，波灵顿工厂接到下周要用168吨肉粉的一个订单，这是工厂按照标准饲料配方完成它的订单所需用的肉粉量。当时仓库中仅有80吨肉粉、缺货问题已通知史密斯。

在分析波灵顿工厂生产和出售的三种混合产品的配方时，史密斯注意到每

9

种产品都需要肉粉。他清楚地了解，肉粉的可用量由每月的采购合同所确定，订购的肉粉平均成本为339美元/吨。超过合同规定的需求量需要在现货市场上采购，现货市场由独立的商人控制，他们能根据采购要求及时供货，但是价格要比合同价高得多。

在重新计算配方或考虑到现货市场采购时，肉粉最大可用量约束可定为80吨，如果决定第二天到现货市场上采购，面临的问题是立即确定一个合适的买价。或者是根据有限的肉粉量确定新的混合配方。上述活动的结果，要在星期五上午反馈至工厂。

除肉粉外，其他原料已在夏季备有存货，即使在配方有些变化的情况下，也能保证充分供应。

10

案例11 西北新闻纸公司*

近期新闻纸价格的稳定对于西北新闻纸公司来说，是一条好消息。约翰·史密特（John Smithers）正渴望着对现有市场最充分地加以开发。西北新闻纸公司是一家新闻纸的主要生产商，其纸厂分布于太平洋西北沿岸和加拿大，分别供应着北美的不同市场。

史密特是西北公司核心业务部（纸业）的助理审计员。他承认，由于市场状况发生了极大的变化，西北公司也形成了一些运输模式。细心观察一下各工厂供应各市场的情况，就会发现许多节约成本的机会。起初，史密特计划直接针对新闻纸配送难题开发和使用一套模型，以便找出这样的机会。但后来他希望这套模型也能用于解决一些长期的“战略性”问题。

西北新闻纸公司的经营

在20世纪80年代早期，华盛顿州达伽玛（Tacoma）的西北森林产品公司（Northwest Forest Products Company），购买了大不列颠哥伦比亚的科拉克新闻纸公司（Clark Newsprint Ltd）大部分的股权。到20世纪80年代中期，前者持有后者的股权几乎达到100％，并且在1988年，将公司更名为西北克拉克公司（Northwest Clack, Inc.）。

购并之后，西北克拉克公司成了世界最大的新闻纸生产商之一，并位列世界最大的森林产品企业的前五位，其车间和工厂散布于加拿大和美国各地。此外，公司还经营着大片的森林。到1994年，西北公司的销售收入达到了20亿美元。

公司的销售收入来自于六大产品系列：新闻纸、墙纸、优质纸、建筑产品、以及木材（见表11－1）。以前，西北克拉克公司只不过是一个纸浆和纸品的生

*

钟彼德和霍兰德教授编写。

11

产商，然而，自从购并时开始，公司销售收入逐渐增加。这几大产品系列的成长主要与木材和建筑产品有关，而且与美国住房产业的兴衰息息相关，而新闻纸曾经是并将继续是公司最大的产品系列，它占用了公司75％的纸浆和纸的生产能力。正是由于认识到新闻纸的重要性，在1986年，西北克拉克公司建立了西北新闻纸公司，并将其作为独立的子公司，全权负责西北克拉克公司所有的纸浆和纸的经营。

表11－1 按产品分布的净销售收入

产品 (1)新闻纸 (2)地材木特质纸 (3)优质纸 (4)工艺产品 总计(纸浆＋纸) (5)建筑产品 (6)木材 总计（(5)&(6)） 总销售额 1992年 千美元 724 356 195 804 415 372 51 883 $1 387 415 164 432 108 333 $272 765 $1 660 180 ％ 43.6 11.8 25.0 3.1 83.6 9.9 6.5 16.4 100.0 1993年 千美元 808 591 208 918 371 901 57 948 $1 446 548 128 008 59 706 $187 714 $1 634 262 ％ 49.5 12.8 22.7 3.5 88.5 7.8 3.7 11.5 100.0 ①

1994年 千美元 908 376 194 039 402 350 66 512 $1 571 277 115 361 76 747 $192 108 $1 763 385 ％ 51.5 11.0 22.8 3.8 89.1 6.5 4.4 10.9 100.0 ①净销售数据包括汇率波动的调整，但这些数据是在其他期间和产品成本之前计算的。

到1990年，纸浆和纸的经营利用了公司有约85％的有效生产能力，生产效率利用上的数字细分，（见表11－2），表明某些产品比另一些产品更有效地利用了生产设施。在资本密集且充分竞争的产业内，如果要保持稳定的利润率水平，那么对生产能力的有效利用就极其重要。西北公司达到的85％的利用率标准几乎成了行业标准，低于这一效率的公司将努力找出差距原因。

12

表11－2 初级产量——纸浆和纸的生产

1994年的有效生产能力/千吨 ①新闻纸 1 937 74.4 1 575 81.3% 地材木特质纸 333 12.8 321 96.4% 优质纸 127 4.9 101 74.5% 工艺产品 207 7.9 173 83.6% 占1994年总有效生产 能力的百分比/％ 1994年实际产量 1994年生产能力利用率 ①有效生产能力由每台机器每天的新闻纸产量与该机器的可用天数算出（允许有计划安排的停机时间），然后汇总每台机器的有效生产能力。

新闻纸

新闻纸，仅有一种用途，它专用于印刷报纸。因此，新闻纸的全球需求量高度依赖于对报纸的需求量，而报纸的需求量又进一步依赖于世界的经济状况，因为经济状况的好坏直接影响着对报纸和报纸广告的需求。

加拿大、美国和日本是世界上最大的新闻纸生产者，而美国也是世界上最大的消费者，它消费了世界新闻纸供应总量的40％多。日本、英国和原西德是除美国之外的主要新闻纸消费者。事实上，由于美国和日本几乎完全消费了其自身的产量，加拿大反而成了世界上最大的新闻纸出口国。因为西北公司的新闻纸厂设在加拿大，纸价因汇率的波动（特别是美元汇率的波动）而受到一定的影响。

自1993年中期以来，新闻纸价格基本上在410美元/吨～500美元/吨的范围内波动。但从1994年开始，由于需求量在近期的增加已导致价格急剧上涨。目前的价格是750美元/吨，在过去的12个月中，上涨了47％。但价格的继续上涨似乎不大可能，晨报建议生产商考虑每吨降价58美元。

13

配送问题

西北新闻纸公司在美国和加拿大共经营着10家新闻纸厂，其中多数座落于太平洋西北沿岸，三家分布在加拿大。由于公司85％以上的新闻纸需求都来自于美国，加拿大的工厂则不得不把它们大多数的产品从北运到南。公司在美国的七家工厂产品被指派给具体的顾客，这些顾客构成了它们全部的新闻纸产品的有效需求。这种安排看起来大体上是符合逻辑的。与大的需求中心位置较近的工厂自然就给那个中心供货，换句话说，与各个主要的需求中心距离都很远的工厂，则把它们的大多数产品出口到日本或环太平洋的其他地方。尽管这些安排未免有点武断，但公司对它们的经营结果还是满意的。

当史密特检查1995年的生产计划时，他注意到，新闻纸从加拿大的三个工厂配送给北美的顾客，若重新进行安排，可能会出现一些削减成本的机会。三家工厂——斯伯路斯（Spruce）、垴密（Naomee）、杜彻斯（Duchesne）在1995年的计划产量是703 737吨，三家的各自计划见表11－3。

表11－3 1995年（计划）产量

工厂 斯伯路斯 垴密 杜彻斯 总产量

每日/吨 462.0 756.5 737.7 －

每年/吨 166 320 272 340 265 077 703 737

①

①每日数据（新闻纸的吨数是按一天24小时生产计算）乘以360得到年计划产量。这种做法使得每年有五天的时间没有列入计划。

西北新闻纸公司的3000个用户，都从九个主要的中心之一获得供应，这九个中心是：华盛顿州的西雅图；伊利诺斯州的芝加哥；科罗拉多州的丹佛；得克萨斯州的达拉斯；路易斯安那州的新奥尔良；加利弗尼亚州的洛杉矶和圣弗朗西斯科；大不列颠哥伦比亚的温哥华以及克尔格米、阿尔贝特。对于这些中心的1995年度需求计划如表11－4所列。

14

表11-4 1995年预测需求

分销中心 西雅图 芝加哥 达拉斯 新奥尔良 丹佛 洛杉矶 圣弗朗西斯科 温哥华 克尔格米 总需求

年需求/吨 40 727 55 608 92 680 92 680 23 832 211 841 52 960 32 581 8 145 611 054

在购并之际，西北公司和克拉克公司达成协议：生产能力在各纸厂之间平均利用。也就是，当一家纸厂因没有任务而闲置时，另一家纸厂要想达到100%的生产能力利用率是不可能的。按照现在的解释，它意味着每一家纸厂在七天中至少有六天在生产。

西北新闻纸公司期望来年的新闻纸价格保持稳定，仍以750美元/吨的售价销给美国的顾客，以700美元/吨的售价销给加拿大的顾客（所有的货币价值均按0.75美元兑换1加元的价格换算成了美元）。

新闻纸的生产是一个资本相对密集的处理过程，但是每吨新闻纸的生产仍然涉及到一些重要的可变成本。这些成本包括原材料（木材、辅助材料、化学产品）、直接人工、以及燃料，但是不包括固定成本，诸如薪金、保险、税收、管理费用、折旧以及服务部门的费用。通过采用直接成本法核算，西北公司估计新闻纸的生产成本如下：斯伯路斯为390美元/吨，垴密和杜彻斯为415美元/吨。

成品新闻纸从各纸厂到各分销中心的运输费用很高。运输成本（按1995年的估计）见表11-5。（表中仅引用了部分数据。在某些情况下，找不到可靠的运输方法。）

15

本文来源：https://www.bwwdw.com/article/on3v.html