运筹学的单纯形法(单纯形法每一步的详细解释)
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的“列几何”图
我们也把(b，z)看作图1中的一条垂直线。这条垂直线称为需求线，它与平面的交点是点(b，0)。需求线与(Ai，ci)的凸组合有一定的几何关系。它们要么相交，要么背离，这取决于我们对(Ai，ci)的凸组合的选择。选取的凸组合不同时，几何关系也不一样。很容易理解，如果需求线与凸组合相交，就意味着(b，z)可以用相应的凸组合来表示，也就是说这个凸组合是原问题的可行解。但如果把它们分开，就说明这个凸组合不满足能表示(b，z)的条件，所以不是原问题的可行解。所有凸组合形成一个凸包。如果需求线能与凸包相交，那么原问题就有可行解。如果需求线不能与凸包相交，原问题无解。进一步抽象图1得到图2。从图中可以看出，点I、H、G是三种不同凸组合和需求线的交点，是原问题的三种可行解。
图2可行解决方案的“柱几何”图
经过以上分析，我们知道，要找到更优解，就是要找到与需求线相交且使Z值最小的凸组合。那么如何找到这样的凸组合呢？首先，引入两个定义:
如果矢量
是线性无关的，那么向量
被称为Rn空间中的仿射独立或者仿射无关，其中k
本文地址：百科常识频道 https://www.neebe.cn/changshi/939436.html，易企推百科一个免费的知识分享平台，本站部分文章来网络分享，本着互联网分享的精神，如有涉及到您的权益，请联系我们删除，谢谢！
相关阅读
