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

运筹学单纯形法(单纯形法每一步的详细解释)
r薇薇原创
作者:臧永森
作者简介:臧永森,清华大学工业工程系博士,研究方向:运行优化算法的设计与应用,数据统计分析,大数据技术与应用,齐老师团队 。
编辑评论/注释
本文属于电子书线性规划项目第三章单纯形法的内容 。在上一篇文章中,我们介绍了单纯形法引入的可行域、最优解、可行解、基解、基可行解等基本概念,也阐述了它们之间的关系(详见“单纯形法之前”一文) 。在明确这些基本概念后,本节我们将讨论单纯形法的思想逻辑和求解步骤 。
我们已经知道优化问题的最优解一定是基可行解,那么如何找到最优基可行解就是优化问题的求解思路 。所以求解过程中的单纯形法是一个不断寻找变量进出基的循环迭代过程 。每次迭代达到降低目标函数值(或增加目标函数值)的目的,最终获得最优解 。那么,在迭代过程中,如何在改进过程中使解尽快收敛到最优解?让我们用更直观的方式来分析这个过程 。
单纯形法的基本思想和逻辑
本文采用的思路参考了Dimitris Bertsimas和John N. Tsitsiklis在《线性最优化导论》一书中提出的方法[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是三个不同凸组合与需求线的交点,即原问题的三个可行解 。

图2可行解决方案的“柱几何”图
通过上面的分析我们知道,要找到最优解,就是要找到与需求线相交且使Z值最小的凸组合 。那么如何找到这样的凸组合呢?首先,引入两个定义:
如果矢量

是线性无关的,那么向量

【单纯形法各个步骤详解 运筹学单纯形法】被称为Rn空间中的仿射独立或者仿射无关,其中k

    推荐阅读