汽车生产与原油采购的关联

在本章第一节和第二节的例题中研究的对象都是连续可分的，即决策变量是连续的，建立的模型是线性规划.然而，实际生活中还会遇到不同的情况，如下述所示.

一、汽车厂生产计划

一汽车厂生产小、中、大三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求、利润以及每月工厂钢材、劳动时间的现有量（见表5.3.1）.试制订月生产计划，以使工厂的利润最大.

进一步讨论：由于各种条件限制，如果生产某一类型汽车，则至少要生产80辆，那么最优的生产计划应做何改变？

表5.3.1　汽车厂的生产数据

【模型建立与求解】

设每月生产小、中、大型汽车的数量分别为x1，x2，x3，工厂的月利润为z，在题目所给参数均不随生产数量变化的假设下，立即可得线性规划模型：

其中N为非负整数集（自然数集）.这样的数学规划称为整数规划（Integer Programming，简记为IP）.IP可以用LINGO直接求解，输入文件：

注：最后一行中的“@gin”是将变量限定为整数的函数.求解得到输出（只列出需要的结果）：

IP的最优解x1=64，x2=168，x3=0，最优值z=632，即问题要求的月生产计划为生产小型车64辆、中型车168辆，不生产大型车.

讨论：对于问题中提出的“如果生产某一类型汽车，则至少要生产80辆”的限制，上面得到的IP的最优解不满足这个条件.这种类型的要求是实际生产中经常提出的.下面以本问题为例说明解决这类要求的办法.

对于原LP模型（5.3.1）～（5.3.4），需增加约束

下面是求解模型（5.3.1）～（5.3.5）的三种方法：

解法1　分解为多个LP子模型.

（5.3.5）式可分解为八种情况：

这里可以应用剪枝法，（8）显然不可能是问题的解.可以检查，（3）和（7）不满足约束条件（5.3.2），也不可能是问题的解.对其他五个LP子模型逐一求解，比较目标函数值，可知最优解在（5）情形得到：x1=80，x2=150，x3=0，最优值z=610.

注：可以不检查是否满足约束条件，解所有LP子模型，结果同上.

解法2　引入0-1变量

设y1只取0，1两个值，则“x1=0或≥80”等价于：

其中M为相当大的正数，本例可取1000（x1不可能超过1000）.类似地有：

于是（5.3.1）～（5.3.4），（1′）～（3′）构成一个特殊的整数规划模型（既有一般整数变量，又有0-1变量），用LINGO直接求解时，输入的最后要加上0-1变量的限定语句：

@bin(y1);@bin(y2);@bin(y3)；求解可得到与第一种方法同样的结果.

解法3　化为非线性规划.

条件（5.3.4），（5.3.5）可表示为：

式子左端是决策变量的非线性函数，（5.3.1）～（5.3.3），（1″）～（3″）构成非线性规划（Non-Linear Programming，简记作NP）.该模型可如下输入LINGO：

求解可得到与第二种方法同样的结果.

评注：像汽车这样的对象自然是整数变量，应该建立整数规划模型，但是求整数规划比线性规划要难得多（即使使用数学软件），所以当整数变量取值很大时，常作为连续变量用线性规划处理.

一般来说，非线性规划的求解比线性规划困难得多，特别是问题规模较大或者要求得到全局最优解时更是如此.为了考虑（5.3.5）式这样的条件，通常是引入0-1变量，而一般尽量不用非线性规划.

二、原油采购与加工

某公司用两种原油（A和B）混合加工成两种汽油（甲和乙）.甲、乙两种汽油含原油A的最低比例分别为50%和60%，售价分别为4800元/t和5600元/t.该公司现有原油A和B的库存量分别为500 t和1000 t，还可以从市场上买到不超过1500 t的原油A.原油A的市场价为：购买量不超过500 t时的单价为10000元/t；购买量超过500 t但不超过1000 t时，超过500t的部分8000元/t；购买量超过1000t时，超过1000t的部分6000元/t.该公司应如何安排原油的采购和加工[7]？

【问题分析】

安排原油采购、加工的目标只能是利润最大，题目中给出的是两种汽油的售价和原油A的采购价，利润为销售汽油的收入与购买原油A的支出之差.这里的难点在于原油A的采购价与购买量的关系比较复杂，是分段函数关系，能否及如何用线性规划、整数规划模型加以处理是关键所在.

【模型建立】

设原油A的购买量为x，根据题目所给数据，采购的支出c(x)可表为如下的分段线性函数（以下价格以千元/t为单位）：

设原油A用于生产甲、乙两种汽油的数量分别为x11和x12，原油B用于生产甲、乙两种汽油的数量分别为x21和x22，则总的收入为4.8(x11+x21)+5.6(x12+x22).于是本例的目标函数——利润为

约束条件包括加工两种汽油用的原油A、原油B库存量的限制，和原油A购买量的限制，以及两种汽油含原油A的比例限制，分别表示为：(www.xing528.com)

由于（5.3.6）式中的c(x)不是线性函数，（5.3.6）～（5.3.13）给出的是一个非线性规划，而且，对于这样用分段函数定义的c(x)，一般的非线性规划软件也难以输入和求解，那么能不能想办法将该模型化简，从而用现成的软件求解呢？

【模型求解】

下面介绍三种解法.

解法1　一个自然的想法是将原油A的采购量x分解为三个量，即用x1，x2，x3分别表示以价格10千元/t、8千元/t、6千元/t采购的原油A的数量，总支出为c(x)=10x1+8x2+6x3，且

这时目标函数（5.3.7）变为线性函数：

应该注意到，只有当以10千元/t的价格购买x1=500t时，才能以8千元/t的价格购买x2(x2＞0)，这个条件可以表示为

同理，只有当以8千元/t的价格购买x2=500t时，才能以6千元/t的价格购买x3(x3＞0)，于是

此外，x1，x2，x3的取值范围是

由于有非线性约束（5.3.16）和（5.3.17），（5.3.8）～（5.3.18）构成非线性规划模型.将该模型输入LINGO软件如下：

注：因为（5.3.14）式和（5.3.18）式保证了（5.3.10）式，所以上面输入中不需要（5.3.10）式.将文件存储并命名后，选择菜单“LINGO|Solve”，运行该程序得到：

最优解是用库存的500 t原油A、500 t原油B生产1000 t汽油甲，不购买新的原油A，利润为4800000元.

但是LINGO得到的结果只是一个局部最优解（local optimal solution），还能得到更好的解吗？除线性规划外，LINGO在缺省设置下一般只给出局部最优解，但可以通过修改LINGO选项要求计算全局最优解.具体做法是：选择“LINGO|Options”菜单，在弹出的选项卡中选择“General Solver”，然后找到选项“Use Global Solver”将其选中，并应用或保存设置.重新运行“LINGO|Solve”，可得到如下输出：

全局最优解是购买1000 t原油A，与库存的500 t原油A和1000 t原油B一起，共生产2500 t汽油乙，利润为5000000元，高于局部最优解对应的利润.

解法2　引入0-1变量将（5.3.16）和（5.3.17）转化为线性约束.

令y1=1，y2=1，y3=1，分别表示以10千元/t、8千元/t、6千元/t的价格采购原油A，则约束（5.3.16）和（5.3.17）可以替换为：

（5.3.8）～（5.3.15），（5.3.18）～（5.3.22）构成整数（线性）规划模型，将它输入LINGO软件如下：

运行该程序得到的最优解与第一种解法得到的结果（全局最优解）相同.

解法3　直接处理分段线性函数c(x).（5.3.6）式表示的c(x)如图5.3.1所示.

图5.3.1　分段线性函数c(x)图形

记x轴上的分点为b1=0，b2=500，b3=1000，b4=1500.当x在第一个小区间[b1，b2]时，记

x=z1b1+z2b2，z1+z2=1，z1，z2≥0，

因为c(x)在[b1，b2]是线性的，所以c(x)=z1c(b1)+z2c(b2).同样，当x在第二个小区间[b2，b3]时，

x=z2b2+z3b3，z2+z3=1，z2，z3≥0，c(x)=z2c(b2)+z3c(b3).

当x在第三个小区间[b3，b4]时，

x=z3b3+z4b4，z3+z4=1，z3，z4≥0，c(x)=z3c(b3)+z4c(b4).

为了表示x在哪个小区间，引入0-1变量yk(k=1，2，3)，当x在第k个小区间时，yk=1，否则，yk=0.这样，z1，z2，z3，z4，y1，y2，y3应满足：

此时x和c(x)可以统一地表示为

（5.3.7）～（5.3.13），（5.3.23）～（5.3.27）也构成一个整数规划模型，将它输入LINGO软件求解，得到的结果与第二种解法相同.

评注：这个问题的关键是处理分段线性函数，我们推荐化为整数规划模型的第二、第三种解法，第三种解法更具一般性，其做法如下：

设一个n段线性函数f(x)的分点为b1≤…≤bn≤bn+1，引入zk，将x和f(x)表示为：

zk和0-1变量yk满足：