下载掌阅APP，畅读海量书库
立即打开
在线性规划的应用中，最重要的是如何将一个复杂的实际问题转化为一个合理的线性规划模型。人们常说，建模工作既是一门科学，又是一门艺术。作为教材，本书通过几个不同类型的简化例子，讲解建立线性规划模型的基本思路和一些技巧。
例 11 一维下料问题。
某厂有一批长度为 7.4 m的钢管原材料(数量充分多），今为制造零件要将它们截成长度分别为 2.9 m、 2.1 m和 1.5 m的管料，需要量都是 200 根。问应如何下料，使用的原材料最省?
解：最简单的做法是，在每根原材料上截取 2.9 m、 2.1 m和 1.5 m的管料各一根，每根剩下残料 0.9 m。这样要使用原材料 200 根，总残料 180 m。若改为混合使用各种下料方法，就可以节约原材料。表 2 -12 给出了各种下料方案。设 x j 为按方案 j 下料的原材料根数, j = 1,…,8。
表 2 -12
单位：根
我们的目标是使用的原材料最省，因此可最小化总残料，即min
z
=0
x
1
+0.1
x
2
+0.2
x
3
+0.3
x
4
+0.8
x
5
+0.9
x
6
+ 1.1
x
7
+ 1.4
x
8
;也可以最小化总的下料根数，即min
z
=
由表2 -12的数据就可列出以下数学模型:
这是要求变量取整数值的线性规划问题(称为整数线性规划问题，将在第 6 章讨论）。对于整数规划，求解方法要复杂得多。在这里我们使用单纯形法解没有变量取整数值要求的线性规划，如果刚好得到整数最优解，问题便解决了。
上机使用QM软件求得的最优下料方案是：按方案 1 下料 60 根；方案 2 下料 20 根；方案 4 下料 100 根，即需 180 根原材料就可以完成下料任务，总残料为 32 m。
由QM软件输出的最优单纯形表，我们发现问题有多个最优解。经过旋转变换可求得另一个最优下料方案：按方案 2 下料 80 根；方案 3 下料 60 根；方案 4 下料 40 根(详见 2.3.2的内容)。
进一步思考:
(1)用总残料最少和用总根数最少作目标函数有何区别?
(2)什么是二维下料问题和三维下料问题，以及各种情况下的应用场景?
(3)当原材料更长时，如何进行方案的筛选?
(4)当下料方案很多，超出了软件求解的变量范围时，如何处理?
例 12 混合配方问题。
一家化工厂要将四种原料A、 B、 C、 D混合调配出三种产品，表 2 -13 是制造各种产品的数据。三种产品的销售价格分别是每千克 9 元、8.5 元和 8 元，各种原料A、 B、 C和D的供应量分别是 1 000、1 000、750 和 800 千克；单价分别是每千克 5 元、6 元、4 元和4.5 元。该厂应如何安排生产才能获得最大利润?
表 2 -13
解：首先确定决策变量。如果我们定义决策变量为各种产品的产量，就不可能建立问题的线性规划模型。正确的方法是定义决策变量为产品中所含原料数量。具体令 x ij 表示第 j 种产品中 i 种原料的数量(千克), i = A, B, C, D; j = 1,2,3。由于产品 3 不含有C,故 x C3 = 0,因此一共只有 11 个变量。
这样，各种产品的产量分别是: x A1 + x B1 + x C1 + x D1 , x A2 + x B2 + x C2 + x D2 和 x A3 + x B3 + x D3 ,由表 2 -13 的规格要求有:
化简后可得:
另外还有以下两组约束条件。
原材料供应量的限制:
需求量的限制:
我们的目标是使利润最大，也就是总销售收入与原料的总成本之差为最大。
销售收入:
原料成本:
于是目标函数为:
该问题的LP模型可归纳如下:
上机求解的结果是
即每天用 475 千克原料A, 725 千克原料B, 500 千克原料C, 800 千克原料D来生产2 500 千克产品 1;以及用 525 千克原料A, 275 千克原料B, 250 千克原料C来生产 1 050千克产品 2,可获得最大利润为 13 825 元。
进一步思考的问题:
(1)如果原料之间配伍存在相斥性问题，模型如何拓展?
(2)配方问题的应用场景有哪些?
(3)对于双下标的变量, Excel求解是否方便?
例 13 多阶段投资问题。
某公司有 100 万元用于投资，可选择的投资项目如下:
项目A:从第一年到第四年每年年初都可投资，并于次年年末回收本利 110%,规定每年的最低投资额为 10 万元。
项目B:第二年年初可以投资，到第五年年末能收回本利 135%,规定投资额不超过20 万元。
项目C:第三年年初可以投资，到第五年年末回收本利 125%,规定最低投资额为 20万元，最高投资额为 40 万元。
项目D:五年内每年年初都可投资，年末回收本利 104%。
问该公司应如何确定给这些项目每年的投资额，使到第五年年末回收资金的本利总额最大?
解：设 x ij 表示第 i 年年初给项目 j 的投资额(单位：万元），由题意知一共有 11 个变量: x 1A , x 1D , x 2A , x 2B , x 2D , x 3A , x 3C , x 3D , x 4A , x 4D 和 x 5D 。
不难看出，第五年年末回收资金的本利总额 z = 1.1 x 4A + 1.35 x 2B + 1.25 x 3C + 1.04 x 5D 。
下面建立约束条件。由于项目D每年都可以投资，并且当年年末就能回收本利。因此，每年都应把手中资金全部投出去，即每年年初的投资额应等于当年年初可用的资金额。具体如下:
第一年年初: x 1A + x 1D = 100
第二年年初：公司可用的资金额仅为项目D在第一年年末回收的本利 1.04 x 1D ,于是有:
第三年年初：可用的资金额是从项目A第一年年初投资及项目D第二年年初投资中回收的本利总和 1.1 x 1A +1.04 x 2D ,从而有:
同理有第四年年初: x 4A + x 4D = 1.1 x 2A + 1.04 x 3D
第五年年初: x 5D = 1.1 x 3A + 1.04 x 4D
此外，还有投资额限制及变量非负的约束，最后得到如下的线性规划模型(该模型假定项目A、 C都要选择):
上机求解可得结果:
第一年年初: x 1A = 45.454 5 (万元), x 1D = 54.545 5 (万元)
第二年年初: x 2A = 36.727 3 (万元), x 2B = 20 (万元), x 2D = 0
第三年年初: x 3A = 10 (万元), x 3C = 40 (万元), x 3D = 0
第四年年初: x 4A = 40.4 (万元), x 4D = 0
第五年年初: x 5D = 11 (万元)
到第五年年末该公司回收资金的本利总额为 132.88 万元，即赢利 32.88%。
可以求出本例的另一个最优解(单位：万元）为:
注：我们可在模型中引入若干 0 -1 变量以解决项目A和C的选择或不选择问题(详见第 6 章)。
进一步思考:
(1)在本例中有项目D和没有项目D对规划的约束有何影响?
(2)如果进一步考虑项目存在不同的投资风险，模型应该如何拓展?
例 14 多周期动态生产计划问题。
一家工厂要对某种产品制订今后 n 个周期(一个周期可以是一周或一个月等）的生产计划。已知第 j 周期的产品需求量为 d j ,该厂第 j 周期的正常生产能力是 a j ,加班生产能力为 b j ,正常生产的单位成本为 c j 元，加班生产的单位成本要增加 e j 元。
工厂库存能力为 I ,第 j 周期库存单位成本为 h j 元。假定在第一周期初和第 n 周期末的库存量都为零。问该厂应如何安排各个周期的生产与库存，才能在满足市场需要的条件下，使总成本最小？试建立这个问题的线性规划模型。
解：先定义决策变量。设 x j 为第 j 周期正常生产的产品数, y j 为第 j 周期加班生产的产品数, z j 为第 j 周期末库存的产品数。
使用下列一般关系式:
本期产量+上期末库存量-本期末库存量=本期需求量
不难得到如下的线性规划模型:
例 15 配套生产问题。
某工厂有 m 个车间，生产一种由 n 种不同部件组成的产品，每个车间均可生产这 n 种部件。已知车间 i 的工时限制为 b i (小时），生产第 j 种部件的生产率为 c ij (件/小时）。问各车间应如何分配工时，才能使产品的件数最多？试建立这个问题的优化模型。
解：设
x
ij
为车间
i
分配给第
j
种部件的工时数,
y
为产品的产量，则生产第
j
种部件的数量为
,因此有:
上式虽然是非线性的，但我们可建立下述等价的线性优化模型。
例 16 餐巾供应问题。
某饭店筵席部预计一周每天接待的客人数如表 2 -14 所示。
表 2 -14
规定每位客人每天用餐巾一条。所用餐巾中可购买新的，每条成本 6 元，或用已经洗净的餐巾。附近有两家洗衣店：甲店洗净一条餐巾收费 3 元，隔一天后送还；乙店洗净一条收费 2 元，隔两天后送还。假定第 7 天后餐巾应换新的，且每周开始时没有旧餐巾。问饭店后勤部应如何安排各天餐巾的供应，以使总成本最低?
解：根据题意，确定决策变量如下:
x i 为星期 i 购买的新餐巾数( i = 1,2,…,7)
y j 为星期 j 送往甲店清洗的餐巾数( j = 1,2,…,5)
z k 为星期 k 送往乙店清洗的餐巾数( k = 1,2,3,4)
u l 为星期 l 未送去清洗的脏餐巾数( l = 1,2,…,7)
目标函数是极小化总费用:
有三类约束条件:
(1)满足每天餐巾需要量的约束条件:
从而有:
(2)处理脏餐巾的约束条件:
即
于是有:
(3)所有变量取非负整数的约束条件。
上机使用线性规划的求解程序可得最优解为:
最小总费用 z = 1 970 (元)。
注 1:本题有多重解，下面是另一个最优基可行解:
注 2:餐巾供应问题起源于美国空军的后勤供应研究。空军某航空队需要某种飞机零件(餐巾），以适应军事上预计的需要(每天顾客人数）。当时有以下的供应选择：买新的零件(买新餐巾）；快速修理零件(洗衣店甲）；一般速度修理零件(洗衣店乙）。快速修理费用较大，一般速度修理费用较小，新买当然费用更高。
因为不少实际问题具有这类特点，所以餐巾供应问题有一定的应用价值。