『运筹OR帷幄』原创

作者：臧永森

作者：臧永森，清华大学工业工程系在读博士，研究方向：运筹优化算法的设计与应用、数据统计分析、大数据技术与应用，戚铭尧老师团队

编者按

此文属于电子书线性规划专题第三章单纯形法的内容。在前面的文章中，我们为引入单纯形法介绍了可行域、最优解、可行解、基解、基可行解等基础概念，也阐述了它们之间的关系（具体可见文章《在单纯形法之前》）。在明确了这些基本概念之后，这一节我们来探讨单纯形法的思想逻辑和求解步骤。

我们已经知道，优化问题的最优解一定是基可行解，那么如何找到最优的基可行解就是最优化问题的求解思路。因此，单纯形法在求解过程，就是不断地寻求变量出入基的循环迭代过程，每次迭代都达到降低目标函数值（或增大目标函数值）的目的，最终得到最优解。那么在迭代过程中，如何使解在改善过程中向着最优解的方向尽快地收敛呢？我们下面用比较直观的方式来解析这个过程。

单纯形法的基本思想与逻辑

本文采用的思路参考Dimitris Bertsimas和 John N. Tsitsiklis在 Introduction to Linear Optimization一书中提出的方法[1]。考虑如下标准线性规划问题：

我们将矩阵A拆分为n个列元素：A1, A2, A3,, An，那么我们可以将问题看成是满足非负约束（4）、凸约束（3）以及约束（5）的最小化问题。

结合式（3）和（5）我们可以看出，原优化问题转化为求解能够构造出（b, z）的使得z值最小的关于（Ai, ci）的凸组合。为了更好地理解它们之间的几何关系，我们将一个平面视作包含A的一个m维空间，将与ci相关的成本项看作是一维垂直数轴，这时每一个点（Ai, ci）都可以唯一在该三维坐标系中表示出来，如图1所示：

图1 线性规划问题1—4的“列几何”图示

我们将（b, z）同样视为一条垂直线表示在图1中，这条垂直线叫做需求线，其与平面的交点是（b, 0）点。需求线与（Ai, ci）的凸组合在几何上有一定的关系，它们或相交或相离，这取决于我们对（Ai, ci）凸组合的选取，选取的凸组合不一样，几何关系就不同。很容易能理解，如果需求线和凸组合相交，说明（b, z）可以用相应的凸组合表示出来，也就表明这个凸组合就是原问题的一个可行解；而如果相离，则说明这个凸组合不满足能够表达（b, z）的条件，也就不是原问题的可行解。所有的凸组合构成了一个凸包，如果需求线能够与凸包相交，那么原问题就存在可行解，如果需求线不能与凸包相交，说明原问题无解。进一步将图1抽象，得到图2，从图中我们可以看出，点I、H、G就是三个不同的凸组合与需求线的交点，也就是原问题的三个可行解。

图2 可行解的“列几何”图示

经过上面的分析我们得知，要找到最优解，就是找到与需求线相交的使得z值最小的凸组合。那么如何找这样的凸组合呢？首先引入两个定义：

1. 如果向量

1. 是线性独立的，那么向量

1. 被称为Rn空间中的仿射独立或者仿射无关，其中k<=n。
2. 在Rn空间中由k+1个仿射无关向量组成的凸包被称为k维单纯形。

对模型（1—4）来说，总共有m+1个等式约束，假定约束系数矩阵是满秩的，那么一个基可行解将对应m+1个线性独立的列向量，也就意味着有m+1个基点，根据上述定义，由基点之间的差向量线性独立可以得到其仿射独立，由此可以知道它们组成的凸包是m维单纯形。

假设m维单纯形与需求线相交于点（b, z），由（5）知用来表示（b, z）的线性组合的权重向量是xi ，该向量就是一个基可行解，也就对应我们上节所分析的基变量的内容，当然z就是相应的目标函数值。我们用图2做一个解释，阴影区域的三角形CDF，就是一个2维单纯形，其与需求线的交点H点就是基可行解，点C、D、F是基点。

我们对二维单纯形CDF做一些改变，会发现相应的z值（与需求线的交点）也会变化，比如我们令基点B取代基点F，单纯形变为BCD，这时可行解变为I点，相应的z值较之前有所增长。类似地，若点E取代点C成为基点，单纯形由CDF变为EDF，可行解就出现在G点，此时z值有所减小。从这些变化中我们找出这样一个规律，当且仅当新加入基的点在当前单纯形平面上方（下方）时，所得的交点（即可行解）对应的z值会增大（减小）。

如果我们更加形象地描述这个基点变化的过程，就如同用手抓住单纯形CDF的基点C，保持D点和F点固定不变，用力向上拉（向下拉），将C点拉到B点（E点），也就产生了新的单纯形BCD（EDF）。单纯形法的旋转迭代过程，就是不断找到基点向上拉（向下拉）到新基点形成新单纯形的过程。

单纯形法的求解过程

简单总结一下单纯形法的求解原理。先找到一个基可行解，然后从非基解中找一个比较有前途的点入基，替换掉基可行解中有待改善的基点，从而达到改善目标函数的目的，如此重复迭代，直至无法找到可以入基的点。

下面我们用一个例题来演示单纯形法的求解过程。用单纯形法求解如下LP问题：

第一步：将上述LP转化为标准形式，目的是能够在初始单纯形表中很容易地获得初始基可行解。

第二步，将标准LP列入第0个单纯形表，如表1：

表1 单纯形表0

上述单纯形表中可以看出初始基变量是（s1,s2,s3），从表中找一个能够入基的变量，要求该变量入基后能够使得目标函数值增大量最大。决策变量在第0行的系数看成是这个变量的缩减成本，就是当这个变量增加1时，目标函数z的值将减少的量。比如x1的系数是-2，就说明当x1每增加1，z值将减少-2，也就是增加2。因此如果我们要选择能够使目标函数增加量最大的量入基，应该选择第0行中系数最小的负值（读者可以考虑下为什么必须是负值）。因此这里选择x2入基。

那如何选择出基变量呢？这里我们采用比值法，用右端项的值（即rhs列）除以出基变量对应的列系数（红色线框标注），从中选择最小的比值对应的基变量出基。如果不选择最小比值对应的基变量出基，将会导致后面的迭代过程出现负的右端项，相应行的基变量将为负值，这与LP标准型的变量非负约束相违背，因此这种操作是不被允许的。所以，表1中的比值优胜者是3，因此s3出基（蓝色线框标注）。

第三步：通常我们会在x2所在列与s3所在行交汇点圈一个圈，也就是元素4。这表示这一点是我们的转轴点，通过初等变化，将该元素所在的行与列的其他元素变为0，该元素本身变为1，得到下一个单纯形表，如表2所示：

表2 单纯形表1

第四步：继续在第0行找负系数对应的入基变量，发现x1对应的系数是-2，可以入基。同时比值运算发现s1对应的变量需要出基，因此第一行、x1列对应的元素1是转轴点，圈一个圈，并进行列运算，得表3：

表3 单纯形表2

第五步：继续上述计算，注意这里因为入基变量s3对应的列有负值，在比值运算时直接赋值为空，因为比值只看正值，如果将负值也考虑进来取最小比值，同样将导致负的右端项。通过入基变量选取和比值测试，对元素2圈圈，做行列变换，得表4：

表4 单纯形表3

第六步：最新表中发现第0行的所有元素均为正值，此时选取任何变量入基，都会使得z值因为正的缩减成本而降低，很显然这对于最大化问题来说是不利的。因此，上表已经达到最优状态，单纯形法迭代结束。

综上，原问题最优解就是

本文主要介绍了单纯形法的基本逻辑思路，以及具体的求解过程，接下来我们将继续带领大家探索单纯形法求解过程中可能出现的几种解，以及单纯形法的变形求解方法。，希望大家继续关注【优化】板块，电子书线性规划专题的科普文。

参考文献：

[1] Dimitris Bertsimas, John N. Tsitsiklis, Introduction to Linear Optimization. Athena Scientific, Belmont, Massachusetts. P120—123.