线性规划和单纯形法-原理篇

引言

很多运筹学的教材都是从线性规划开始的， 我平时做算法策略的落地应用时也研发了一部分基于线性规划的技术方案。 可以说，如果搞不懂线性规划，很难成为一名优秀的运筹优化算法工程师。

但是我在体系化学习时，却是先在其他地方转了一大圈，才来到这里。

主要原因是，这线性规划的原理着实有点难，之前看了很多遍，总有种好像懂了但又没完全懂的挫败感。 痛定思痛下终于决定，还是从最简单的无约束问题开始，然后逐渐过渡到有约束问题，以及现在的线性规划问题。

针对无约束优化问题，我细分为一维问题和多维问题，并分别学习了适合解决一维问题的黄金分割法、切线法和进退法等，以及用于解决多维问题的坐标轮转法、最速下降法和拟牛顿法等；针对约束优化问题，相继学习了拉格朗日乘子法和罚函数法。

线性规划问题本质上是一类特殊的约束优化问题，这类优化问题在实际场景中十分常见，同时由于问题的特殊性，也给问题的高效求解带来了新思路。

前面提到过，线性规划对我来说挺难的，只用一篇文章是很难讲清楚。 所以打算分成上下两篇：本篇着重讲明白算法原理，下一篇着重研究实践应用。

必须要预警的是，后续内容很枯燥，因为夹杂着非常多的证明和推理过程。 我愿意花大量时间在这上面，是希望不仅能知其然，还能知其所以然。 不想看细节过程的，可以更多关注整体的逻辑框架：线性规划问题相比一般约束问题的特殊性在哪里-->该特殊性使得线性规划问题具有哪些特点-->基于这些特点，所设计的算法(单纯形法)是如何实现高效求解的。

线性规划标准型

线性规划的标准型矩阵形式为

也可以写成分量形式

从定义上可以看出，相比一般的约束优化问题，线性规划问题在目标函数、约束条件和变量范围方面都增加了限制： (1)目标函数为线性加和的表达式； (2)约束条件只有线性等式； (3)优化变量大于等于0。

问题特点

增加了上述限制后的线性规划问题，具有哪些特点呢？

先说结论：问题的可行域为凸集-->最优解在凸集的顶点上-->顶点和基本可行解一一对应。

接下来逐个详细说明(证明)。

（1）可行域为凸集。

既然提到凸集，就需要先定义清楚凸集的含义：设是维欧式空间中的一个点集，若对于，以及任意，必有

则称为凸集。

以下是凸集和非凸集的实例

对于线性规划问题，根据标准型约束的定义

那么，针对任意，假设新变量，可做如下推导

即等式约束成立。

由于，下式显然也成立

即大于等于0亦成立。

所以也在可行域内。 根据凸集定义，线性规划问题的可行域就是个凸集。

可行域是凸集，有什么好处呢——看下一条结论。

（2）最优值一定在凸集的某个顶点上达到。

顶点这个词在物理世界很容易理解，但为了后续推导，还是需要用数学语言描述清楚这一概念： 针对可行域内的，如果不存在，使得

则这个为凸集上的顶点。

要证明以上结论，此处使用反证法。

假设凸集的顶点为，最优解为。

因为在可行域的凸集范围内，所以它可以由顶点表示为

式中，，。能被顶点通过线性组合的方式表示，很容易想象，但证明起来有些难，这里就不深入了，有兴趣的可以参考：多面集的表示定理。

上式两边同时左乘

设，上式可以做如下推导

但由于是最优解，并且不在顶点上，所以

上述两式互相矛盾，所以假设不成立，即最优解必定在某个顶点上取到。

这个结论的最大优点在于，把决策空间从一个非常大的可行域空间收缩到了可行域的顶点上，而顶点的数量在大部分情况下是比较有限的，这就极大降低了问题求解的复杂度。

这里其实我还有个小疑惑，就是从证明过程来看，好像并不需要目标函数是线性的，是否说明即使目标函数是非线性表达式，最优解依然在顶点上取到？ 该疑惑目前暂未搞清楚，如有大佬，望不吝赐教。

（3）可行域凸集的顶点和基本可行解一一对应。

已经知道最优解在顶点上了，那顶点的数学表达式是怎样的呢？ 上述结论告诉我们，顶点就是基本可行解。

接下来，先看一下基本可行解的定义。

是的约束矩阵，可以从中取到一个非奇异方阵，然后把剩下列组成一个子阵，它们对应的分别表示为基变量和非基变量。等式约束可以表示为

令，可以求出，组合和

如果，则被称为基本可行解。

的维度是，理论上至多可以从任意列中随机选取列，所以的数量上限是，即基本可行解的数量上限为个。

上述结论需要分两步进行论证：(1)基本可行解都是顶点；(2)顶点都是基本可行解。

针对第一步，继续使用反证法。

假设某个基本可行解不是顶点，即存在可行解和，使得基本可行解可以表示为

将写成基变量和非基变量两部分

等式中，因为，故

所以和都是基本可行解，即

由于为非奇异方阵，所以有唯一解，所以

即就是基本可行解，与基本假设不符，所以基本可行解必为可行解的顶点。

针对第二步，还是使用反证法。

假设是可行域的顶点，还是先拆解为非零项和零项

但由于不是基本可行解，所以对应应该是线性相关的，即存在一组非0向量，使得

上式乘以系数，然后和上上式分别做加法和减法，得到

先令，再令，首先可得

同时只要足够小

即和都是可行解，这说明不能是顶点，两者矛盾，所以顶点也必定都是基本可行解。

有了该结论后，理论上，只要算出所有基本可行解的目标函数值，并返回最小值，即得到了最优解。 但基本可行解的数量上限是个，如果的数量比较大，用遍历的方式寻找最小值貌似就有些吃不消了。

此时大名鼎鼎的单纯形法就该登场了。

单纯形法

同样先给结论，单纯形法最厉害的地方在于：任意给定一个基本可行解后，通过简单的计算评估后，便可以告诉我们，该解是否还有改进空间，如果有，朝着哪个方向改进最好。 这样的话，便不再需要去遍历所有基本可行解，所以能极大提升问题求解的效率。

假设已经得到一个基本可行解

对应的目标函数值为

先把写成基本可行解的通用表达式，代入等式约束

移项，可以表示为

通用表达式结合上式后，再代入目标函数表达式

重组一下

上式可以描述为

其中，是非基变量集合，。

在当前的中，由于，即的后一项为0； 所以目标函数能继续降低的基本条件是：至少存在一个，使得，同时也能够从0增加为正数。

是参数不是变量，是否存在大于0的，是无法改变的； 但是的值理论上是可以优化的，当然该值也不能随意增大，其需要满足的约束是

假设，将从0变为正数（专业术语叫入基），为了保证基本可行解的要求，中需要有一个值变为0（专业术语叫出基）

其中，，。 为了保证，的最优值是

基于以上逻辑，我们可以描述为：如果存在，使得，此时令，可以使得目标函数值得到最大程度的降低。

这里还有一些特殊情况需要单独考虑：

(1) 所有，即，此时当前基本可行解就是最优解。

(2) 中，是原基本可行解的分量，所以其值≥0是毋庸置疑的；但是的大小是不确定的，如果其部分值≤0，结合的自身约束，原有流程还能继续进行；但如果全部≤0，流程就无法再继续进行了，事实上，即使取无穷大，的约束依然能够满足，将变为无穷小，所以此时原问题无下界，不存在最小值。

综上，单纯形法的基本步骤可以概述为：

（1）将所给的线性规划问题化为标准型；

（2）找出一个初始基本可行解。

（3）检验和，判断当前解的状态：最优解或不存在最优解，则退出；否则继续。

（4）找到最佳，更新，得到一个新的基本可行解，转至（3）。

好了，总算是搞明白求解线性规划问题的算法原理了。