数学规划5.3 原始对偶算法.ppt

5.3 原始对偶算法 基本思想 这一方法实际上是由某些网络问题的一个特殊算法发展起来的. 考虑原问题 5.3 原始对偶算法 互补松弛条件是:如果x和?分别是P和D的可行解,则它们是最优解的充要条件是对一切的i和j有 5.3 原始对偶算法 下面我们集中讨论关系式(2) 假定?是对偶问题D的可行解,若能设法找出P的一个可行解x,使得满足关系式(2),即 5.3 原始对偶算法 对给定?求这样一个x的思想,导致了原始对偶算法.给定?,要找这样一个x,可以通过解由 ?所确定的辅助问题(称为限制的原始问题RP)而得到.当这样的x没有有哪些信誉好的足球投注网站到, 那么就得到RP的对偶信息(RP的对偶记为DRP),此信息告诉我们如何修改? ,于是得到新的? .重复此过程,在有限步内就收敛到最优解 5.3 原始对偶算法 原始对偶算法 算法开始时?是D的可行解且始终保持对偶可行性.在c?0时可直接取?=0为初始对偶可行解. 当c不是非负的时候,应用Beale等人的方法很容易的找出可行解?: 5.3 原始对偶算法 显然增加约束后不会改变原问题P的解,此时新的原始问题的对偶为 5.3 原始对偶算法 中将有一些取严格不等式,而另一些取等式.设取等式的约束指标集为J: 5.3 原始对偶算法 这即相当于求一个x,使得满足 5.3 原始对偶算法 利用单纯形法求解此RP:若最优值为0则已找到(6)的解,因此也是P的最优解.若最优值大于0,如何处理? 5.3 原始对偶算法 为解决此问题,需要考察限制的原始问题RP的对偶DRP 5.3 原始对偶算法 这就可能考察利用原来的?和新得到的 来校正? 5.3 原始对偶算法 所以我们应该选取?0,从而改进D的费用 5.3 原始对偶算法 为维持可行性,只需考察下述不等式 5.3 原始对偶算法 5.3 原始对偶算法 Procedure primal-dual 5.3 原始对偶算法 5.3 原始对偶算法 5.3 原始对偶算法 5.3 原始对偶算法 5.3 原始对偶算法 5.3 原始对偶算法 5.3 原始对偶算法 5.3 原始对偶算法 5.3 原始对偶算法 5.3 原始对偶算法 5.3 原始对偶算法 5.3 原始对偶算法 5.3 原始对偶算法 5.3 原始对偶算法 * 构造对偶问题 由于P是标准形式,故对任意可行解 x,(1)总是成立的 则这个 .x(及?)是最优的 原始P 对偶D 限制原始 RP 限制原始 对偶DRP ? 调整到? 因此不妨设D有一可行解,则不等式约束 称J为允许列集合.为找出这样的x,构造新的LP,称为限制的原始问题(RP): 现在我们处于这样的情形:试图只应用允许列来找出 一个可行解x,但由于RP的最优值0,所以努力失败了 因为RP和DRP是一对相互对偶的规划,所以它们的 最优值相等.因此有 但是我们得到了RP的最优解及其对偶的最优解, 此时,可行性准则变为 于是有 当解限制的原始问题并达到了改进D的解的时候,我们 重新定义集合J,然后重复上述过程直到或者?opt=0并因 此得到P的最优解,或者由定理1知P无可行解. begin infeasible:=‘no’, opt:= ‘no’ let ? be feasible in D(comment:possible by(3) ); while infeasible:=‘no’and opt:= ‘no’ do begin set solve RP by the simplex algorithm if ?opt=0 then opt:= ‘yes’ else if then infeasible:=‘yes’ else end end