第8页 中华学生百科全书

  20-2．4×4＝10．4（度）

  那么如果我们把每天的煤、电全部用来生产甲产品，结果又会是怎样呢？

  从煤的角度，每天可以生产甲产品

  12÷2＝6（吨）

  从电的角度，每天可以生产甲产品

  20÷6＝3．33（吨）

  综合考虑，每天能生产 3．33 吨甲产品，净收入为：

  3．33×4＝13．32（千元）

  这时每天会有剩余的煤

  12-3．33×2＝5．34（吨）

  工厂对上述两种安排都不满意，因为这两种方案煤和电力资源都没有充

  分利用。有人认为，如果每天只生产 2 吨乙产品，则消耗煤 10 吨、电 8 度，

  收入 12000 元。省下了 2 吨煤，可生产 1 吨甲产品（同时耗电 6 度），可再

  增加收入 4000 元。这两种产品一起可收入 16000 元，比前面只安排一种产品

  生产的两个方案的赢利都多。除此之外，其实还可以试探其他方案，但试探

  的方法过于繁琐。

  实际上，用线性规划模型可以解决这一类各因素成比例关系的生产安排

  问题。对于上述只生产两种产品，消耗两种资源的问题，因为因素少，可以

  用简单的作图法来解决；对于涉及因素众多的线性规划问题，要用所谓的“单

  纯形法”来求最优解；对于大型工厂、地区、部门，相关因素可能成百上千，

  这时就要借助于电子计算机来求解了。通过图形法或单纯形法解决上述工厂

  的问题时，可以得出：每天安排生产甲产品 2．36 吨，乙产品 1．45 吨，可得

  到最大收入 18180 元。

  还有一类问题也可以用线性规划模型来解决。例如有甲、乙、丙、丁 4

  个糖果厂，生产同一种水果糖供给 A、B、C、D4 个商店零售。若已知 4 个工

  厂的产量，4 个商店的需要量，而且还知道每个工厂运给每个商店 1 吨水果

  糖的运费是多少，又叫运输问题，是实际工作中会经常遇到的问题。这些问

  题，都可以用线性规划模型来解决。

  如何才能赚最多的钱

  ——整数规划模型

  一个汽车队，有甲、乙两种汽车。甲汽车每辆可装体积为 1 立方米的货

  物，载重量为 5 吨，可收入 500 元。乙种汽车每辆每次可装体积为 1 立方米

  的货物，载重量为 9 吨，可收入 800 元。由于值班司机人数、汽油燃料等条

  件的限制，每次车队派车运货体积总计不能超过 6 立方米，载重量不能超过

  45 吨。问题是每次安排甲、乙车各多少辆，才能既满足限制条件，又取得最

  多的收入？

  我们想一想这个问题，会发现两种汽车装载货物的体积、重量与汽车的

  数量是成比例关系的，而车队的收入也是与车辆数目成比例关系的。因此，

  用线性规划模型可以解决这一问题。应用图解法或单纯形法，可以计算出结

  果，每次应派甲种车 2．25 辆，乙种车 3．75 辆，总收入为：

  5×2．25＋8×3．75＝41．25（百元）

  现在新的问题又来了，这种安排是不可能实行的。2．25 辆甲种车怎么

  派？要么是 2 辆、要么是 3 辆，谁也不可能派出不是整数的车。乙种车也是

  同样要派出整数。像这种要求得到整数结果的线性规划模型通常被称做整数

  规划模型。

  可不可以集零为整？如果把小数点后面的第一位数四舍五入，即甲种车

  派 2 辆，乙种车派 4 辆，这是不是上面整数规划模型的最优结果呢？通过计

  算会发现该结果超过了限制条件：2 辆甲车装载 10 吨，4 辆乙车可装载 36

  吨，合计可装载 46 吨，但规定不能超过 45 吨。如果把小数点后的数字舍掉，

  就不会超出限制条件了，但这样的结果是不是符合最优要求呢？再来计算一

  下，每次甲种车派 2 辆，乙种车派 3 辆，总收入为：

  500×2＋800×3＝3400（元）

  这种情况下，每次派车运货的体积总量为：

  1×2＋1×3＝5（立方米）

  每次派车运货的载重量总计为：

  5×2＋9×3＝37（吨）

  可以看出还有 1 立方米体积和 8 吨载重量没有利用，还可再增加一辆甲

  种车，即 3 辆甲种车，这时收益为：

  500×3＋800×3＝3900（元）

  从而我们知道，四舍五入和去掉小数点后面的尾数化零为整的方法都不

  能求出整数规划模型的最优结果。

  有人建议将条件允许的派车方案都列举出来，一一进行计算、比较，就

  可以找到最优结果。

  对于上面汽车队的派车的问题，要计算 25 种方案。如果因素增加，解决

  整数规划模型的方案就可能成百上千，不仅计算复杂，光列举这些方案就会

  令人头晕眼花。

  那该怎么办呢？现在，科学家已找到了一种解决整数规划问题的方法，

  叫做“分支定界法”。这种方法首先是找到相对应的线性规划问题的最优结

  果，这个结果是整数规划的界限（例如上述汽车队派车问题，相对应的线性

  规划的最大收入是 4125 元，整数规划的结果一定不会超过 4125 元）。然后

  作出判断并进行计算，如果线性规划求出的结果恰恰是整数，这时可以认为

  已找到答案。如果线性规划求出的因素中有非整数结果，如 2．25 辆车，就要

  设法分别在限制条件内把各非整数因素化整，求出结果，进行比较，最后找

  到整数规划的最优结果。对于上面派车问题，可以找到的结果是，不派甲种

  车，派乙种车 5 辆，可以得到最高收入：

  5×0＋8×5＝40（百元）

  在实际系统中，存在许多因素，它们一定要用整数值来表示，如机器台

  数、人数、火车车厢数目、集装箱数、工厂个数、商店家数以及在某地是不

  是建工厂，建不建商店、学校、车站等等，这些数值都不能有分数（如建，

  可用 1 表示；若不建，用 0 表示）。涉及这些因素的线性规划模型，都要用

  整数规划来解决，用分支定界法等方法求出最优结果。

  分派问题也是另一类广泛应用的整数规划问题。例如学校周末劳动，有

  四项工作（给树木花草浇水、打扫教室、修理桌椅、出黑板报）要分配 4 位

  同学去完成。这 4 位同学中，不同的人对不同的工作所用时间不一样。有人

  力气大，浇水快；有人写字娴熟，出黑板报花的时间少。安排得好，4 位同

  学总计花费的时间就会最少。还有分派不同的工人到不同的车间去工作，不

  同的轮船按不同的航线航行，不同的飞机去不同的城市等，都是属于分派问

  题。

  系统工程的妙用

  植树问题

  某班长带领 60 位同学上山去值树，主要的工作有 3 项：挖坑、运树苗、

  挑水浇树。根据情况得知：用 20 或 20 以上的人挖坑，需要 20 分钟；用 20

  或 20 以上的人运树苗，需要 15 分钟；用 20 或 20 以上的人挑水浇树，需 30

  分钟。这样，便会有 5 种安排：