1.1线性规划及其数学模型

1.1.1 案例

例1.1 某厂拟生产甲、乙两种适销产品，每件利润分别是3（百元）和5（百元）。甲、乙产品的部件各自在A、B两个车间分别生产，每件甲、乙产品的部件分别需要A、B车间的生产能力1工时和2工时；两种产品的部件最后都要在C车间装配，装配每件甲、乙产品分别需要3工时和4工时。A、B、C三个车间每天可用于生产这两种产品的工时分别是8、12、36。应如何安排生产这两种产品才能获利最大？

解 设x1、x 2分别是甲产品和乙产品的日产量，z为这两种产品每天总的利润。首先列出该问题的数据，如表1.1所示。

根据题意，建立模型如下：

其中，max是英文maximize（最大化）的缩写。

例1.2 有A、B、C三个工地，每天A工地需要水泥17百袋，B工地需要用水泥18百袋，C工地需要水泥15百袋。为此，甲、乙两个水泥厂每天生产23百袋水泥和27百袋水泥专门供应三个工地。两个水泥厂至工地的单位运价如表1.2所示。问：如何组织调运使总运费最省？

解 设xij为甲、乙两个水泥厂分别运到A、B、C三个水泥厂的水泥袋数，则可以做出如表1.3所示的数据表。

由题意容易得到如下数学模型：

其中，min是minimize（最小化）的缩写。

例1.3 光明厂生产中需要某种混合料，它应包含甲、乙、丙三种成分。这些成分可由市场购买的A、B、C三种原料混合后得到。已知各种原料的单价、成分含量及各种成分每月的最低需求量如表1.4所示。

问：该厂每月应购买各种原料多少吨，才能使在满足需求的基础上，用于购买原材料所耗费的资金为最少？

解 现设x1、x2、x3分别为原料A、B、C的购买数量，显然有 x1、x2、x3≥0，又设z为总的耗费资金，则z=6x1+3x2+2x3，由题意容易得到如下数学模型：

例1.4 一家昼夜服务的宾馆，一天24小时分成6个时段，每个时段需要的在岗服务员人数如表1.5所示。

每个服务员每天连续工作8小时，且在每个时段开始时上班。问：最少需要多少名服务员？试建立该问题的线性规划数学模型。

解 现设xj为第j时段开始上班工作的服务员人数（j=1,2,3,4,5,6），又设z为需要的服务员总的人数，z=x1+x2+x3+x4+x5+x6。由题意得到如下数学模型：

从前面4个例子中不难发现它们的共同点：它们的限制条件（或称为约束条件）都是线性方程组，或者是线性不等式组；它们都是求一组满足约束条件的非负的解，使得一个线性函数（目标函数）取得极大值（或极小值），因此，这些问题都是线性规划问题。

1.1.2 线性规划的一般模型

线性规划模型的目标是企业利润的最大化。在不考虑产品销售情况的理想状态下，将资源尽可能地配置到利润率更高的产品上去，并尽可能减少资源的浪费，是实现线性规划模型总目标的关键所在。

一般线性规划模型可以表示如下：

建立一个实用的线性规划模型必须明确以下4个组成部分的含义。

第一，决策变量。决策变量是模型中的可控而未知的因素，经常使用带不同下标的英文字母表示不同的变量，如式（1-5）、式（1-6）中的xj。

第二，目标函数。线性规划模型的目标是求系统目标的极值，可以是求极大值，如企业的利润和效率等，也可以是求极小值，如成本和费用等。式（1-5）即为最优化目标函数，简称目标函数。式中opt即optimize（最优化）的缩写，根据问题要求不同，可以表示为max（最大化）或min（最小化）。

第三，约束条件。约束条件是指实现系统目标的限制性因素，通常表现为生产力约束、原材料约束、能源约束、库存约束等资源性约束，也有可能表现为指标约束和需求约束，如式（1-6）中的前m个式子。

第四，非负限制。由于在生产实际问题中，资源总是代表一些可以计量的实物或人力，因而一般不能是负数，如式（1-6）中的最后一个。

由式（1-5）和式（1-6）组成的线性规划模型还可以用下列的矩阵式表示，即

其中，为系数矩阵；C=[c1,…,c n]；

X=[x1,…,xn]T；B=[b1, …,bm]T；O=[0, …,0]T表示0矩阵。