优化 | 线性规划的历史、模型及案例

作者：李崇楠
作者：李崇楠，北京交通大学研究生在读，交通运输规划与管理专业，研究方向：运输组织优化

本文为《线性规划入门电子书》第一章内容。《线性规划入门电子书》是「运筹OR帷幄」优化理论科普丛书系列的第一本，已上线Github，欢迎亲朋好友们一睹为快！

本章带领读者走进线性规划的世界。首先介绍线性规划的历史，读者将了解到在线性规划领域作出杰出贡献的学者及其成就 ；接下来的内容为线性规划的基本概念 ，模型假设和“标准形”，并介绍了将一个一般的线性规划模型转化为标准形的技巧；最后给出了若干线性规划案例。

1 线性规划的历史

1939年，苏联学者Kantorovich为前苏联政府解决优化问题时提出了极值问题，并且提出了解乘数法的新方法，可惜他的工作在当时并未引起足够的重视。事实上，他所提出的问题正是线性规划的雏形。

与此同时，美国的线性规划却获得了飞快的发展。1941年，Hitchcock提出运输问题；1945年，Stigler提出了营养问题；1945年，Koopmans提出了经济问题。而奠定线性规划整套理论方法的，还要说是G.B.Dantzig，他被誉为“线性规划之父”。他在1947年担任美国空军审计官的数学顾问，为找到解决问题的机制化工具，提出了“在一组线性方程或不等式约束下，求某一线性形式极小值问题的数学模型”，这便是“线性规划”（linear programming）这一经典优化模型。而“线性规划”这一名字的由来是在之后1948年，Koopmans和Dantzig在海滩散步时共同想出的。1947年夏天，Dantzig提出了单纯形算法。这个算法在后来被评为20世纪最伟大的算法之一。

尽管单纯形法(Simplex method)作为解决线性规划的有效方法在学术界具有统治地位，但是1971年，Klee和Minty两位学者构造出一个例子，该例子下单纯形法的运作需要访问指数数量级别的顶点，也就是说，在最坏情况下，单纯形法是一个指数时间算法(exponential-time algorithm)。Dantzig在得知这个消息后感叹到他的噩梦到来了，单纯形法并不是在任何情况下都是高效可行的。那么，是否有更加高效的算法，比如多项式时间算法(polynomial-time algorithm)，来解决线性规划问题呢？8年后，即1979年，L.G.Khachiyan发明了椭球算法(ellipsoid method)，这是第一个解决线性规划问题的多项式时间算法。但是，这个算法虽然理论上是多项式时间运行，但是算法被证明是不切实际的，这个算法的杰出贡献是在理论层面告诉世人，线性规划是可以用多项式时间算法来解决的，同时也启发了学者在更加深入的优化领域进行算法开发。1984年，N.Karmarkar发明了内点算法(interior point method)，这是线性规划第一个实际可用的多项式时间算法。

2 线性规划模型

2.1 基本概念

线性规划是一类经典的优化模型。与一般的优化模型类型，线性规划模型也有目标函数，决策变量和约束条件。那决定这个优化模型是线性规划的因素是什么呢？下面我们将以一个例子展开介绍。

上述模型为典型的线性规划模型，式(1.1)是目标函数， 是决策变量，式(1.2)-(1.4)为约束条件，其中式(1.2)和式(1.3)为线性约束，式(1.4)为非负约束。可以发现，对线性规划模型而言，目标函数和约束条件都是线性函数。线性函数可以理解为每一项未知数(变量)的最高次数为1，即不会出现 等未知数次数超过1的情况。

2.2 模型假设

线性规划作为一类数学模型，含有以下三种假设：

1.比例假设

在线性规划中，目标函数的系数是固定的常数，但是在现实生活中不见得如此，比如考虑目标函数是计算采购蔬菜计划的总花费。那么可能会面对“2元钱1个，3元钱2个”的这种促销，这时线性规划的目标函数就无法表示。

2.非负假设

线性规划的决策变量要求时非负数，但是不要求是非负整数，所以可以取小数。这同样有局限性，依然以采购蔬菜的问题为例，如果需要买土豆，但是土豆只能按整袋来卖的话，那么表示买土豆数量的决策变量就只能取整数了。

3.确定性假设

线性规划中像是目标函数的系数，线性约束中的常数与决策变量的系数，都是已知且保持不变的常数。但是有些参数在实际中是会变化的，通常参数变化的范围是已知的，这就涉及到鲁棒优化(robust optimization)、随机优化(stochastic optimization)等领域的内容了。

2.3 线性规划的标准形

在线性规划中，根据目标函数是试图取得最大还是取得最小，能够分成“最大化问题”与“最小化问题”两种问题。此外，线性约束根据决策变量的线性表达式和常数项之间的连接符为“大于等于”“等于”“小于等于”，又可以分为“大于等于约束”“等于约束”“小于等于约束”。因此，线性规划可以有不同的形式，这不利于定理、算法的表示及推导。为解决这一问题，引入线性规划的标准形。

观察上面的模型可以看到，线性规划的标准形具有如下特点：

（1）目标函数要取得最大值

（2）所有的决策变量都要满足非负约束（nonnegativity constraint）

（3）线性约束均为等式约束（equality constraint）

如果有一个非标准形的线性规划，那么如何等效地转化为标准形呢？这里要强调所谓“等效”的概念，即最优解是不变的，或转化后问题的最优解能够通过一定的方式推出原问题的最优解。

下面我们介绍将一个线性规划模型转换为标准形式的技巧。

3 线性规划标准形式的转换技巧

针对如下线性规划问题，我们将使用一些技巧，将它转化为线性规划模型的标准形式。

与标准形进行对比，观察到有如下的差别：

（1）目标函数是最小化，而不是最大化。

（2）线性约束中有大于等于约束，有小于等于约束。

（3）决策变量无约束，我们称之为自由变量。

（4）目标函数含有绝对值项，这是一个很难处理的要点，需要一定技巧才能化解。

下面逐一介绍转化为标准形的技巧。

1.目标函数最大化

针对目标函数是最小化的模型，我们可以将原问题的目标函数乘以负一，并最大化这个新的目标函数。在本例中，目标函数可以转化为

2.消除不等式约束

我们可以看到第一个约束条件是“小于等于约束”，第二个约束条件是“大于等于约束”。在这里我们分别引入松弛变量（slack variable）进行转化。松弛变量均满足非负约束。对“小于等于约束”，我们加上一个松弛变量 ；对“大于等于约束”，我们减去一个松弛变量 。这样两个不等式约束都转换成了等式约束：

3.消除自由变量

在本例中， 变量没有约束。针对这类无约束变量，我们需要引入两个非负变量 来表示它： 。但是这个例子的目标函数中，对 取绝对值，所以此处对 的转换还需要进一步的操作。

4.消除绝对值符号

在转换的时候，我们需要对绝对值符号内的项进行正负号判断，将原本含有绝对值符号的式子拆分成两个不含绝对值符号的式子。考虑到绝对值符号可能出现在目标函数中，也可能出现在约束条件中，接下来我们给出两种示例。

(1)目标函数中有绝对值符号

本例中目标函数值的第三项含有绝对值符号 ,其中为 自由变量。我们引入两个变量 ,定义为:

由变量定义可知， 一定都是非负的，并且 , 。读者可以 令取某一具体的数值来验证.

(2)约束条件中有绝对值符号

如有以下约束 。可以将其转化为：

然后对上述式子添加松弛变量，转换成等式约束。

所以总结起来，我们可以把原线性规划问题转化为如下的标准形式：

为了让大家更加深入的理解之前引入的 这两个变量，我们去考察一下如下的等价性关系。如图1.1，左边灰色矩形框中的式子是可以推出右侧灰色矩形框的式子的。这在之前我们分别让 取值4为-4和的实例中就可以看到。那么右边的式子是否可以反推得到左边的式子呢？我们来看图1.2的证明

那么，之前定义的 是不是就完美无缺了呢？并不是。

请看下面这个线性规划模型：

其中并没有非负约束。这个问题的最优解极其明显，就是 。

我们将 , 代入到上面的例子中，就有：

这个问题读者现在可能不会求解，但是我们可以告诉读者。这个问题的最优解是

这与原问题确实等价。但是，细心的读者会发现，此时计算 。原因是，由 的定义可以知道， 不能同时取正数，至少有一个为0 (当时 ， 同时取值为零)。所以说， 的取值分别为0和2才是一个完全符合定义的最优解。

那么，为什么会出现这样的情况呢？实际是有一个隐含的二次约束(quadratic constraint)被忽略掉了，即 ，如果有了它，那么得到的 就会满足“至少有一个为0”的条件。读者会问，这有什么用吗，我求出来 ，还是能得到最优解是 。事实上，大多数情况下，确实没必要苛求“至少有一个为0”的条件。所以通常转化中，我们也不要求非要引入这样的二次约束。

4 线性规划案例

4.1 资源分配生产问题

某军工厂生产甲、乙、丙三种产品，生产三种产品需要A、B两种资源，其单位需求量及利润由下表1给出，问每天生产甲、乙、丙三种产品各多少，可使总利润最大？

表1.1 资源分配生成问题信息

这个问题的解决需要建立线性规划模型，用三个变量 代表每天生产甲、乙、丙产品的数量（假设决策变量）。题干提到要使“总利润最大”，所以建立目标函数：

目标函数的含义就是总利润的大小，那么函数值自然越大越好，但是需要考虑题干中提到的各种限制，也就是约束条件。因此，可以写出如下的约束条件：

经过三个步骤：假设决策变量、建立目标函数、寻找约束条件，我们就得到了如下的线性规划模型：

只要解出满足这个模型的约束同时使目标函数最大的 即为最终答案。

4.2 营养问题

一个健身人士需要购买A、B两种食品，已知食品含有营养成份1、2、3的数量及每日人体对该三种成份的必需量如表2所示，请问他应当每天分别购买多少A、B食品，使得在满足要求的情况下总费用最少？

表1.2 营养信息

本问题仿照例一，应当先假设决策变量，设 为每天购买食品A的量，设 为每天购买食品B的量。下一步为建立目标函数，这个题目要求我们尽可能让健身人士少花钱，也就是总花费最小，所以有: 。最后一步就是考虑约束条件，本例要求每天摄入三种营养成分的数量应至少达到表1.2中要求的最低摄入量，所以有：

所以得到如下的线性规划模型：

同理，只要解出满足这个模型的约束同时使目标函数最小即总花费最小的即为最终答案。

4.3卷钢问题

卷钢问题又称为下料问题，这个问题严格来讲不能算是“线性规划”的内容，而是“整数规划”的内容，所谓整数规划，读者可以理解为是在线性规划的基础上，给决策变量加上整数限制，即决策变量必须是整数，这比线性规划的求解难度要大得多。但是这个问题在建模的角度上又是一个非常典型的问题，所以特此介绍。

本例采用卷钢问题中最简单的一种，也就是一维卷钢问题。有一个卷钢加工工厂，现在有100个卷钢，每个卷钢(roll)的宽度都是1000。现在有5个客户，每个客户都需要一定数量的零件(item)，这些零件都可以通过卷钢切割加以生产。比如说1号客户需要5个宽度为100的零件，那么工厂可以按照图1.3的方式进行生产。2号客户需要4个宽度为150的零件；3号客户需要14个宽度为375的零件；4号客户需要7个宽度为800的零件；5号客户需要3个宽度为50的零件。

现在的问题是，如何安排使用卷钢数量最少的切割计划，使得所有客户的需求能够满足，同时还要考虑到卷钢的宽度是有限制的。

下面我们建立问题的模型，第一步为假设决策变量。考虑到工厂一共有1000个卷钢，面对5个客户的需求，不一定所有的卷钢都要得到使用，所以我们引入一种取值仅为0或1的决策变量 ，其中 表示第 个卷钢。如果取1，表示 号卷钢被用来切割零件；如 取0，表示 号卷钢没有被用来切割零件。

题干要求我们安排使用卷钢数量最少的切割计划，因此我们的目标函数其实就是 。除了 ，我们还要引入一个决策变量，它也是取值为非负整数，但是不局限于0和1，而是所有非负整数，它就是 , 其中 表示 第位客户，或者说第 种零件。 这个决策变量的含义是在号卷钢上切下第种零件的个数。 由于目标函数已经建立完成，所以建模只剩下考虑约束条件了。 第一类约束条件是所有客户的需求要得到满足，这里有5个客户，所以有5条约束，我们用符号 表示客户 需要的零件个数，那么我们就有

第二类约束条件是在每个卷钢上的切割方案需要考虑到卷钢总宽度的限制，但是不一定1000个卷钢都要拿来投入生产用以满足这5位客户的要求，也就是说有一些卷钢不会进行切割，那么如何表达这一事实呢，我们其实可以引入刚才使用的决策变量 ，那么约束就为:

这一类约束共有1000个，其中 为零件 的宽度。 综上，卷钢问题的模型如下所示：

该问题实际上并不是线性规划，因为决策变量加上了必须为整数这一约束，这其实是整数规划问题，这个问题的模型最早是前苏联的学者Kantorovich建立的。这个模型虽然非常清晰地描述了一维卷钢问题，但是直接求解这个模型效率非常低，后来Gomory针对此问题建立了其他版本的模型，并应用著名的列生成算法(column generation)进行高效求解，这些内容就不在这里展开描述了，读者感兴趣的话可以阅读本书第5章列列生成算法部分。

参考文献：
[1] 马国瑜. 线性规划的发展历史[J]. 北京化工大学学报(自然科学版), 1985(4):27-33.
[2] SC Fang. Linear Optimization and Extensions – Theory and Algorithms[M]. Prentice-Hall, Inc,1993, 1-9.

文章须知
文章作者：李崇楠
责任编辑：翁欣
审核编辑：阿春
微信编辑：玖蓁
本文由『运筹OR帷幄』原创发布
如需转载请在公众号后台获取转载须知