原始-对偶算法

《原始-对偶算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、18.433组合最优化原始－对偶算法October28授课教师：SantoshVempala在这一讲中，我们介绍互补松弛性条件并利用它们得到求解线性规划的原始－对偶方法。1互补松弛性由前面的强对偶定理我们已经知道，下面两个线性规划都有可行解时其最优值是相等的，即利用上面的结论，我们可以验证原始和/或其对偶问提解的最优性。定理1.设和分别是(P)和(D)的可行解，那么和是最优解当且仅当下面的条件成立：证明：首先，由于和是可行解，故且对下标和做加和，可得把上面两式相加并利用强对偶定理，可得，因此，不等式(1)和(2)一定为等式。故结论得证

2、。□2原始－对偶算法定理1主要蕴含的结论是：如果和是可行解且满足互补松弛性条件，则他们是最优解。这个结论产生了原始－对偶算法：从某个可行解和出发，使之越来越满足互补松弛性条件。方便起见，我们考虑如下原始和对偶规划：在这种形式下，互补松弛性条件可简化为：原始－对偶算法步骤如下：1、从(D)的一个可行解开始。在多数情况下得到这样的一个可行解要比求解线性规划简单得多。令现在我们需要利用(3)得到(P)的一个可行解满足问题是有没有一个满足这种性质的可行解。2、写出限定原始规划(RP)如下：事实上，(RP)的可行解即满足上述提到的性质(3)。这

3、里，变量为人工变量。如果为0，那么即为(P)的最优解。3、如果，那么和是最优的。否则，这时我们写出(RP)的对偶形式，称为(DRP)，并求其解4、令来改进（D）的解，其中的取值需满足是可行的，而且由可行性可知，对有又因为任意均有所以当时可取任意正数。故取则满足且是可行的。又因为且，注意，在上面的原始－对偶算法中，求解(DRP)通常要比求解(P)或(D)简单。实际上，在这种方法中，(P)和(RP)都是临时规划，我们真正想解的是(D)。为此，我们先解出(DRP)再用这个解来反复改进。2.1实例考虑下面形式的最大流问题：值得一提的是，在初始

4、的最大流问题中，前三组约束为等式。但是我们将这三组不等式相加，得到0<=0，这些不等式的弱集蕴涵着等式。我们把上述表示形式作为(D)，取为零向量即可得到它的一个可行解。现在我们直接给出(DRP):可以看出(DRP)有如下释义。寻找一条从到的路（流值为1）且路上只能经过下列弧：饱和的后向弧，零流的前向弧和任意方向的其它弧。换句话说，我们需要在剩余图中找一条路。这种观察说明最大流算法实际上是一个原始－对偶算法。最后，需要注意，原始－对偶算法不一定具有多项式执行时间。