1.2 线性规划及其数学模型

在生产管理和经营活动中经常提出一类问题，即如何合理有效地利用有限的人、财、物等资源，才能得到最佳的经济效果。下面我们来讨论一个经典的线性规划问题引例。

1.2.1 线性规划问题引例

【例1-1】（线性规划问题引例）某公司生产甲、乙两种产品，均需在A、B、C三种不同的设备上加工，产品加工所需工时单耗、产品销售后能获得的利润及设备可用工时数如表1-1所示。问：如何安排生产计划，才能使该公司获得的总利润最大？

解：这是一个典型的线性规划问题，下面建立该问题的线性规划数学模型。

① 设甲、乙产品产量分别为x1千克、x2千克——决策变量，简称变量

② 设总利润为Z，则

Max Z = 70x1+30x2 ——目标函数

③ 设备可用工时数限制——约束条件

3x1+ 9x2≤ 540 A设备可用工时约束

5x1+ 5x2≤ 450 B设备可用工时约束

9x1+ 3x2≤ 720 C设备可用工时约束

x1, x2≥0非负约束

因此原问题的数学模型为（其中s.t．是subject to的简写，意为约束条件）：

这就是该线性规划问题引例的数学模型，因此数学模型就是对一个实际问题以适当的数学公式来表达它的内在关系。

1.2.2 数学模型的经济含义

当我们把一个实际问题表达成LP数学模型时，一定要注意和理解数学模型中的经济含义。

1．数学模型的三要素

（1）有一组待确定的决策变量。如【例1-1】中（x1, x2）为一个具体行动方案。

一般来说，构成线性规划的问题都有很多具体方案可供选择，但是最优的方案往往只有一个，要从很多的可行方案中去求得这个最优方案，使得资源得到充分利用，避免因任意选取其他方案而造成资源的浪费，这样就能够达到最优的经济效果。

（2）有一个明确的目标要求（Max或Min）。如【例1-1】中要求利润Z最大。

显然，任取一种计划产量x1和x2值的可行方案（即满足全部约束条件），都会得到一定数量的利润，但不一定是最大，因此目标要求与待定的决策变量的取值紧密相关，也就是说目标值是决策变量的函数，称为目标函数。另外目标要求依具体问题的性质不同而不同，本例中求总利润，因此越大越好，用符号Max表示；有的情况下可能是计算费用或时间，因此越小越好，用符号Min表示。

人们常把线性规划研究的问题归纳为两类：第一类是某项任务确定后，如何统筹安排，尽量以最少的资源去完成这项任务；第二类是现有一定数量的资源，合理安排和使用它们，使完成的任务最多，创造的财富最大。实际上这两类问题是同一个问题的两个方面或两种提法，本质都是寻求整个问题的某项整体指标的最优解。

（3）存在一组约束条件。如【例1-1】中A、B、C三种设备可用工时的约束。

它们都是用决策变量的线性方程来表示的，约束条件反映规划的客观限制，在产品生产过程中，资源往往是有限的，约束条件确定规划的实现范围，即确定了所求变量的变化域。

2．数学模型中系数的含义

（1）目标函数中决策变量的系数cj，称为价值系数。

如【例1-1】中的70、30就叫价值系数，表示单位产品提供的利润（元/千克）。在具体问题中有明确的经济含义和计量单位。

（2）约束条件左边决策变量前的系数aij，称为约束条件系数。

在具体问题中也有明确的经济含义和计量单位，如表1-1中的3、5、9和9、5、3为单耗，表示单位产品的设备工时消耗量（小时/千克）。

（3）约束条件右边常数bi，称为限制常数。如表1-1中的540、450、720就叫限制常数，表示设备A、B、C现有最大的可用工时。在具体问题中也有明确的含义和计量单位。

1.2.3 数学模型解的名称

在线性规划数学模型式（1-1）中，一般我们能够找到决策变量的很多个解，即有很多种决策方案，将所有约束条件用图形绘出，如图1-1所示。以下定义线性规划（LP）数学模型几种解的名称。

（1）可行解：凡满足图1-1中所有约束条件②、③、④、⑤的所有解称为可行解，它们对应可行方案。所有可行解的集合构成可行解域，即图中阴影部分。可行解域中的任何一点称为可行点，对应一个可行方案，这个点的坐标构成一个列向量，称为可行解向量。

（2）最优解：凡使得目标函数Z值达到最优（最大或最小）的可行解称为最优解。最优解一般情况下是唯一存在的，但在一些特殊的LP数学模型中，可能有无穷多个最优解或者不存在最优解的情况。

（3）基本解：约束条件直线的交点对应的解称为基本解，如图1-1中所有实心点和空心点对应的解。

（4）基本可行解：可行解域边界上的约束条件直线交点对应的解，即图1-1中所有实心点对应的解。它满足两个条件：一是基本解，约束条件直线交点对应的解；二是可行解，即满足所有约束条件的解，在可行解域内。

1.2.4 线性规划数学模型的一般形式

综上所述，线性规划数学模型从结构上看包括决策变量、目标函数、约束条件三个部分，完整的表达式为：

如果式（1-2）中的方程（包括目标函数和约束条件）均是线性方程，则式（1-2）称为线性规划数学模型；如果式（1-2）中的方程出现非线性方程，则式（1-2）称为非线性规划数学模型。

1.2.5 线性规划问题求解过程

利用线性规划求解实际问题可归结为以下三个步骤。

第一步 将实际问题转化为数学模型（数学公式），这一步叫建模。

第二步 求解数学模型的最优解，有以下两种方法。

方法（1）图解法，适合于两个变量的LP数学模型。

方法（2）单纯形法，适合于任意个变量的LP数学模型。

第三步 将数学模型的最优解转化为原问题的最优方案。