§1.1 线性规划问题的一般形式

1.1.1 线性规划问题建模举例

在实际的生产运营和日常生活中，需要经常进行计划或规划。虽然各个行业的计划和规划的内容各有不同，但其共同点可以归结为两类：在现有各项资源的限制条件下，如何制订方案，使得预期的目标或效益最优；或者为了达到预期的目标，寻求一种方案能使各类资源消耗最少。

例1.1 生产计划安排问题。某工厂计划生产甲、乙两种产品，生产工艺路线为：各自的零部件分别由设备A、B加工，最后都须由设备C装配。已知各制造一件产品分别消耗的设备台时，3种设备的工时成本及每天可用的生产能力，如表1.1所示。

表1.1 甲、乙单位产品的生产消耗

据市场分析，甲、乙单位产品的销售价格分别为73元和75元，问该工厂每天应如何安排生产计划，可使获取的利润最大。

例1.2 配料问题（食谱问题）。某公司饲养实验用的动物以供出售，已知这些动物的生长需要饲料中的3种营养成分：蛋白质、矿物质和维生素。按照营养需求，每个动物每周至少需要蛋白质60g，矿物质3g，维生素8mg，该公司能买到5种不同的饲料，每种饲料1kg所含各种营养成分和成本如表1.2所示。

表1.2 配料（食谱）问题的数据

试确定最佳的饲料配方，既能满足动物营养需要又使总成本最低。

1.1.2 线性规划问题的数学模型

为了求解例1.1和例1.2，首先用数学语言对例1.1和例1.2进行描述。

例1.1中，生产单位甲产品需要消耗设备A的工时数为2小时，需要消耗设备C的工时数为3小时；而设备A的单位工时成本为20元/小时，设备C的单位工时成本为10元/小时。因此单位甲产品的生产成本为70（2× 20+3× 10）元，进而可知生产单位甲产品的利润为3（73-70）元。同理，单位乙产品的生产成本为70（2× 15+4× 10）元，生产单位乙产品的利润为5（75-70）元。

设该工厂每天生产产品甲和产品乙的数量分别为x₁和x₂，这时该工厂可获取的利润为（3x₁ +5x₂）元，令z=3x₁ +5x₂，因问题中要求获取的利润最大，即max z。由于z是该工厂能够获取利润的目标值，是变量x₁和x₂的函数，被称为目标函数。同时，变量x₁和x₂的取值受到设备可用生产能力的限制，用于描述限制条件的数学表达式称为约束条件。设备A每天的加工能力不超过16小时，受设备A可用生产能力的限制，用不等式表示为2x₁≤16，同理，受设备B和设备C生产能力的限制，可以得到以下不等式：，。由此，例1.1的数学模型可表示为

目标函数

约束条件其中，约束条件x₁，x₂≥0称为变量的非负约束，表示产品甲和乙的产量不可能为负值。符号s.t.（subject to）表示“约束于”。

在例1.2的饲料配方中，设含有饲料A_i的量为。该饲料配方希望总成本最低，因此建立如下的数学模型：

目标函数

约束条件

模型中的约束条件分别表示饲料配方中蛋白质、矿物质和维生素的含量不低于营养最低要求，分别不低于60g、3g和8mg。

1.线性规划模型的一般形式

通过上面的两个例子可以看出，规划问题的数学模型由三个要素组成。

（1）变量，或称决策变量。在规划模型中，用一组决策变量来表示某一方案或措施，即描述所要做出的决策，可由决策者决定和控制。

（2）目标函数。这是决策变量的函数表达式，表示决策者希望实现的目标。按问题的不同，要求目标函数实现最大化或最小化，在前面加上max或min来表示，目标函数也是衡量方案优劣的标准。

（3）约束条件。这是指决策变量取值时受到的各种资源条件的限制，通常表示为一组含有决策变量的等式或不等式，是决策方案可行的保障。

如果规划模型中，目标函数是决策变量的线性函数，且为单一的，决策变量是连续的，可以在实数范围内取值，约束条件是含决策变量的线性等式或不等式，则称该类规划问题的数学模型为线性规划问题的数学模型。线性规划的数学模型中，目标函数里决策变量的系数也被称为价值系数，它反映了每个决策变量的单位取值对决策目标的贡献程度。

一般的，线性规划模型具有如下形式：

目标函数

约束条件

在上述模型中，式（1.1.1）称为目标函数，c_j为决策变量x_j的价值系数，式（1.1.2）称为约束条件，决策变量的取值受m种资源的约束，第i个约束条件的右端项b_i表示第i种资源的拥有量， a_ij表示单位变量x_j所消耗的第i种资源的数量，通常被称为技术系数或工艺系数。

在实际问题中，线性的含义包含：一是比例性，每个决策变量对目标的贡献与决策变量的取值严格成比例；同样，每个决策变量对约束条件左端的贡献和决策变量的取值也成比例；二是相加性，如每个决策变量对目标函数的贡献都与其他决策变量的取值无关，这意味着目标函数应为各变量贡献的总和，另外每个决策变量对约束条件的贡献也具有相加性。此外还应注意，线性规划的数学模型中允许决策变量取非整数，而且应确切地知道模型中每个参数（价值系数、技术系数和约束条件右端项）的取值。

为了方便起见，线性规划模型可简写为

进一步，令，，，，则线性规划的数学模型也可写成如下矩阵形式：

2.线性规划问题的标准形式

可以看出，线性规划问题有各种不同形式，如目标函数有的要求最大值（max），有的要求最小值（min）；约束条件有的是等式，有的是不等式（“≥”或“≤”）；决策变量一般是非负约束，但有的是无约束。为了便于以后的讨论和制定统一的算法，规定线性规划的标准形式如下：

线性规划的标准型中，要求目标函数为求最大值，约束条件是等式，右端常数项b_i≥0且所有变量均满足非负限制。

对不符合标准形式的线性规划问题，可分别通过下列方法化为标准形式。

（1）若原规划模型中目标函数为求极小值，即。因为求minz等价于求，令，则目标函数即转化为。

（2）化不等式约束为等式约束。当约束条件为“≤”时，如，则在不等式左端加入一个非负变量，此时化为等式约束

加入的这个非负变量被称为松弛变量，在实际问题中表示未被充分利用的资源数。当约束条件为“≥”时，如，则在不等式左端减去一个非负变量，此时化为等式约束

加入的这个非负变量被称为剩余变量，在实际问题中表示超出的资源数。

（3）当决策变量jx为无约束时，可令，其中，将其代入线性规划模型即可。若某决策变量，这时可令，显然。

（4）如果某个约束条件右端的常数项，则用乘以该式两端即可。

例1.3 将线性规划问题

化为标准形式。

解 令，其中，并引入松弛变量x₅和剩余变量x₆，按上述规则，线性规划模型（1.1.4）可转化为如下标准形式

一般的，线性规划的标准形式可以写成如下矩阵形式：

我们称满足约束条件{AX=b且X≥0}的向量为线性规划[式（1.1.5）]的可行解；使目标函数达到最大值的可行解称为线性规划[式（1.1.5）]的最优解。