1.3　牛奶加工的线性规划模型案例

一家奶制品加工厂用牛奶生产A1与A2两种奶制品。已知1桶牛奶可以在设备甲上用12小时加工成3千克A1，或者在设备乙上用8小时加工成4千克A2，根据市场需求，生产A1与A2全部能售出，且每千克A1获利24元，每千克A2获利16元。现在，加工厂每天能得到50桶牛奶的供应，每天工人总劳动时间为480小时，并且设备甲每天至多能加工100千克A1，设备乙的加工能力没有限制。请建立数学模型为该厂制订一个生产计划，使每天获利最大。

问题分析

这是一个标准的优化问题，其目标在于使得每天获利最大化，要做的决策为生产计划，即每天用多少桶牛奶生产A1，用多少桶牛奶生产A2（也可以选取每天生产多少千克A1，多少千克A2作为决策变量）；决策变量取值受到三个条件的限制：原料（牛奶）供应、劳动时间、设备甲的加工能力。通过对原题进行解读，可以得到如图1-1所示思路框架。按照题目所给条件将决策变量、目标函数和约束条件用数学符号及公式表示出来，就可以得到相应的数学模型。

模型假设

1.A1与A2两种奶制品每千克的获利是与它们各自产量无关的常数，每桶牛奶加工A1与A2的数量和所需的时间是与它们各自产量无关的常数。

2.A1与A2每千克的获利是与它们相互间产量无关的常数，每桶牛奶加工A1与A2的数量和所需的时间是与它们相互间产量无关的常数。

3.加工A1与A2的牛奶桶数可以是任意非负实数。

模型设计

按照优化模型的三要素（决策变量、目标函数、约束条件）建立本题的数学模型。设每天用x1桶牛奶生产A1，用x2桶牛奶生产A2。x1桶牛奶可生产3x1千克A1，获利24×3x1,x2桶牛奶可生产4x2千克A2，获利16×4x2。设每天获利为z元，故z=72x1+64x2。因此，优化模型的目标函数表达如下：

maxz=72x1+64x2

确立目标函数后，决策变量取值受到生产原料、加工时间、加工能力、决策变量属性的限制。

生产原料的限制：生产A1与A2的原料（牛奶）总量不得超过每天的供应总量，即x1+x2≤50；

加工时间的限制：生产A1与A2的总加工时间不得超过每天工人总劳动时间，即12x1+8x2≤480；

加工能力的限制：A1的产量不得超过设备甲每天的加工能力，即3x1≤100；

决策变量属性的限制：x1,x2均不能为负值，即x1≥0,x2≥0。

综上所述，所建立的牛奶生产加工优化模型如下：

分析上述模型特点可发现该优化模型符合比例性、可加性、连续性三个基础条件，是一个标准的线性规划模型。

模型求解

在中学阶段，老师曾介绍利用图形法求解双决策变量构成的线性规划模型。如图1-2所示，图中阴影部分为一个凸五边形，即由约束条件构成的优化模型可行解空间；求目标函数的最大化等价于求图中虚线（虚线方程为）与坐标轴截距的最大化。容易发现：当目标函数取到最大值时，虚线恰经过凸五边形的某个顶点。

虽然图形法简明易懂，但当线性规划模型涉及的决策变量较多时，图形法不再是一个合理、可行的求解方案。此时，采用软件求解线性规划模型显得更为高效。本节首先介绍如何利用LINGO软件求解牛奶加工问题中的线性规划模型。

在LINGO软件中输入如下代码：

观察上述代码发现，LINGO代码与所建立的线性规划模型高度相似。代码第二行表示优化模型的目标函数，代码第四行至第六行表示优化模型的3项约束条件。相较于MATLAB软件与Python软件，LINGO软件更为易学，更受到学生们的追捧。它使编程者更加注重模型表达的准确性，而非算法设计的高效性。初学者只需要掌握LINGO代码的基本特点以及相关注意事项，就可以快速编写程序求解线性规划模型。

LINGO代码具有如下特点：程序以“max=”或者“min=”开始，后面直接写出目标函数表达式，表示求解最大化问题或者最小化问题；每行后面加一个分号，表示目标函数或者约束条件结束；程序默认所有的变量都是非负变量，所以不必输入非负约束（如需在负数范围内寻找最优解，可以使用@free(x)函数解除变量非负限制）；书写相当灵活，不必对齐，也不区分字符的大小写；约束条件中的“<=”及“>=”可分别用“<”及“>”代替。

运行上述程序，将显示如图1-3所示求解状态。

图1-3显示：模型类型属于LP（线性规划模型），目标函数值的状态为Global Opt（全局最优解），目标函数最优值为3360，迭代次数为2次。模型运算的具体结果显示

在Solution Report如下：

模型运算结果显示：当x1=20,x2=30时，目标函数取得最大值为3360，即用20桶牛奶生产A1以及30桶牛奶生产A2可以获得最大收益。解决方案中除提示决策变量和目标函数的最优值外，还有许多对分析结果非常有用的信息，解释如下：

不妨将3个约束条件的右端看作3种“资源”，即原料、劳动时间、设备甲的加工能力。输出中“Slack or Surplus”提示这3种资源在最优状态时是否有剩余。可见，原料、劳动时间的剩余量均为零，设备甲尚余40千克加工能力。一般将“资源”剩余为零的约束称为紧约束（有效约束）。

不妨将目标函数看作“效益”。一旦增加紧约束的“资源”，“效益”必然跟着增长。输出中“Dual Prices”提示这3种资源在最优状态时，“资源”增长1个单位所引起的“效益”增量。如原料增加1个单位（1桶牛奶）时，利润增长48元；劳动时间增加1个单位（1小时）时，利润增长2元；而增加非紧约束（设备甲的加工能力）不会使得利润增长。这里，将“效益”的增量看作“资源”的潜在价值，经济学上称为影子价格，即1桶牛奶的影子价格为48元，1小时劳动的影子价格为2元，设备甲的影子价格为0元。读者可用直接求解的办法验证上述结论，即将输入文件中原料约束的右端参数50改为51，观察得到的最优值（利润）是否恰好增长48元。

此外，LINGO软件提供了模型灵敏性分析。首先，在软件菜单栏的“Option”中选择“General solver”页卡。然后，在页卡中“Dura Computations”选择“Price&anges”r即可。

除LINGO软件外，MATLAB软件的linprog函数也可用于求解线性规划模型。linprog函数调用方式如下[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub,x0)。其中，x表示决策变量的最优解向量，fval表示目标函数的最优值。函数参数意义如下：

其中，x0表示算法迭代的初始值。用户也可选择不指定迭代初始值，而由程序自行指定。

首先，将牛奶加工问题的线性规划模型写成矩阵形式如下：

其中，

然后，调用函数linprog求解线性规划模型。注意，函数linprog用于求解目标函数最小化的线性规划模型。因此，当求目标函数最大化时，可采用取相反数的方式将最大化问题转化为最小化问题。代码如下所示：

注意　与LINGO代码不同，采用MATLAB软件求解线性规划模型时，软件并不默认决策变量的非负属性。因此，在代码中需要添加决策变量的取值下限要求。

运行上述代码，具体结果显示如下：

模型运算的结果显示：当x1=20,x2=30时，目标函数取得最小值-3360，即原目标函数取得最大值3360，所得结果与LINGO软件结果相同！

此外，MATLAB软件提供了一种可视化求解优化模型的方法——Optimization Tool。首先，在软件“Command Window”中输入optimtool启动优化工具箱；然后，在页面Solver中选择线性函数求解器linprog，并输入优化模型的目标函数、约束条件如图1-4所示；最后，点击Strat按钮运行程序求解线性规划模型，并将模型结果显示在窗口内。

注意　除linprog函数外，MATLAB软件还有许多其他函数可以求解线性规划模型，如fmincon,fminimax,fminsearch等。感兴趣的读者可在MATLAB软件“Command Window”中输入help参看帮助文件，学习函数使用方式，如输入help fmincon可以查看fmincon命令的使用方法以及相关案例。

最后，Python也有类似的函数命令linprog求解线性规划模型。与MATLAB软件相似，Python软件函数linprog可用于求解目标函数最小化的线性规划模型。因此，当求目标函数最大化时，可采用取相反数的方式将最大化问题转化为最小化问题。linprog函数调用方式如下：res=linprog(c,A,b,Aeq,beq,bounds)。其中，res表示优化模型的求解结果。函数的参数意义如下：

其中，bounds表示决策变量的取值上下界。

求解牛奶加工问题的Python代码如下所示：

注意　Python软件与LINGO软件类似，程序默认决策变量的非负属性。运行上述程序，具体结果显示如下：

模型运算的结果显示：当x1=20,x2=30时，目标函数取得最小值-3360，即原目标函数取得最大值3360，用20桶牛奶生产A1,30桶牛奶生产A2时可以获得最大收益。所得结果与LINGO软件、MATLAB软件结果完全相同。

注意　除linprog函数，Python还有其他许多函数可以完成上述模型的求解，如cvxpy库等。因此，感兴趣的读者可以参看相关书籍学习。