单纯形法各个步骤详解运筹学单纯形法

r维维原创
作者:臧永森
作者:臧永森，博士，清华大学工业工程系，研究方向:运筹学优化算法设计与应用，数据统计分析，大数据技术与应用，师从祁团队。
编辑评论/说明
本文属于电子书线性规划项目第三章单纯形法的内容。在上一篇文章中，我们为单纯形法的引入介绍了可行域、最优解、可行解、基解、基可行解等基本概念，也阐述了它们之间的关系(详见“单纯形法之前”一文) 。阐明这些基本概念后，本节将讨论单纯形法的思想逻辑和求解步骤。
【单纯形法各个步骤详解运筹学单纯形法】我们已经知道优化问题的最优解一定是基可行解，所以如何找到最优基可行解是优化问题的求解思路。因此，单纯形法在求解过程中是一个不断寻找变量进出基的循环迭代过程。每次迭代达到降低目标函数值(或增加目标函数值)的目的，最终得到最优解。那么，在迭代过程中，如何在改进过程中使解尽快向最优解收敛呢？让我们以更直观的方式来分析这个过程。
单纯形法的基本思想和逻辑
本文所采用的思路参考了迪米特里斯·贝塔西马斯和约翰·恩·齐次克里斯在《线性优化导论》一书中提出的方法[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的“列几何”图
我们还在图1中将(b，z)显示为一条垂直线。这条垂直线称为需求线，它与平面的交点是(b，0)点。需求线与(Ai，ci)的凸组合之间存在一定的几何关系。它们要么相交，要么彼此分离，这取决于我们对(Ai，ci)的凸组合的选择。如果选择的凸组合不同，几何关系也会不同。很容易理解，如果需求线与凸组合相交，意味着(b，z)可以用对应的凸组合来表示，这意味着这个凸组合是原问题的可行解。如果它们相互分离，就意味着这个凸组合不满足(b，z)可以表示的条件，所以不是原问题的可行解。的所有凸组合形成一个凸包。如果需求线能与凸包相交，那么原问题就有了可行解。如果需求线不能与凸包相交，说明原问题无解。通过进一步抽象图1，我们得到图2 。从图中可以看出，点I、H、G是三种不同凸组合与需求线的交点，即原问题的三种可行解。