原始对偶算法.pdf

该【原始对偶算法 】是由【小辰GG】上传分享，文档一共【4】页，该文档可以免费在线阅读，需要了解更多关于【原始对偶算法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。
原始-对偶算法
October28授课教师:SantoshVempala
在这一讲中,我们介绍互补松弛性条件并利用它们得到求解线性规划的原始-对偶方法。
1互补松弛性
由前面的强对偶定理我们已经知道,下面两个线性规划都有可行解时其最优值是相等的,即
利用上面的结论,我们可以验证原始和/或其对偶问提解的最优性。
(P)和(D)的可行解,那么和是最优解当且仅当下面的条件成立:
证明:首先,由于和是可行解,故且
对下标和做加和,可得
把上面两式相加并利用强对偶定理,可得,
因此,不等式(1)和(2)一定为等式。故结论得证。□
2原始-对偶算法
定理1主要蕴含的结论是:如果和是可行解且满足互补松弛性条件,则他们是最优解。
这个结论产生了原始-对偶算法和出发,使之越来越满足互补松弛性
条件。
方便起见,我们考虑如下原始和对偶规划:
在这种形式下,互补松弛性条件可简化为:
原始-对偶算法步骤如下:
1、从(D)的一个可行解开始。在多数情况下得到这样的一个可行解要比求解线性
规划简单得多。
令
现在我们需要利用(3)得到(P)的一个可行解满足问题是有没有
一个满足这种性质的可行解。
2、写出限定原始规划(RP)如下:
事实上,(RP)的可行解即满足上述提到的性质(3)。这里,变量为人工变量。
如果为0,那么即为(P)的最优解。
3、如果,那么和是最优的。否则,这时我们写
出(RP)的对偶形式,称为(DRP),并求其解
4、令来改进(D)的解,其中的取值需满足是可行的,而且
由可行性可知,对有
又因为任意均有
所以当时可取任意正数。故取
则满足且是可行的。
又因为且,
注意,在上面的原始-对偶算法中,求解(DRP)通常要比求解(P)或(D)简单。实际上,在这
种方法中,(P)和(RP)都是临时规划,我们真正想解的是(D)。为此,我们先解出(DRP)再用
这个解来反复改进。

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