原始-对偶算法.ppt

原始-对偶算法14721472马韶东1互补松弛定理定理1设和分别是原问题和对偶问题的可行解,那么和都是最优解的充要条件是,对于所有j,下列关系成立:(1)如果,就有;(2)如果,就有2原始—对偶算法的基本思想原始—对偶算法不同于原始的单纯形法,也不同于对偶算法,它的基思思想是,从对偶问题的一个可行解开始,同时计算原问题和对偶问题,试图求出原问题的满足互补松弛条件的可行解,当然,这样的可行解就是最优解。考虑原问题()它的对偶问题()其中是m*n矩阵,3设是对偶问题()的一个可行解,即满足在已知对偶问题的一个可行解的条件下,把对偶问题的约束划分为两组,定义下标集显然,当时,。假如是对偶问题的最优解(当然,现在的不一定是最优解),根据互补松弛定理,时。4下面用两阶段法求对偶问题的最优解。在的假设下解一阶段问题()其中是分量全为1的m维向量,y是由m个人工变量组成的m维列向量。我们称线性规划()为限定原始问题。这个问题必存在最优解,求解的结果必是最优值等于零或大于零。5若问题()的最优值等于零,则y=0。设其最优解为再由假设可以得到根据互补松弛定理,它也是原问题()的最优解。6若限定原始问题()的最优值大于零,则原问题()不存在使的可行解,同时也表明了不是对偶问题()的最优解。因此需要修改对偶问题的可行解,并构造新的原始限定问题,再进行求解,以此类推,直至得到原问题的最优解,或者得出原问题无可行解的结论。7现在分析当原始限定问题的最优值大于零时怎样修改对偶问题的可行解。考虑限定原始问题()的对偶问题()设上述线性规划()的最优解是,可由求解限定原始问题的单纯形乘子结果得到。8下面利用对偶问题()的可行解和线性规划()的最优解来构造对偶问题()的一个新的可行解,()在下面的讨论中可以看到,只要适当选择的取值,就能使w为对偶问题()的可行解。9分两种情形讨论。(1)这时,是限定原始问题中的变量,由于是线性规划()的最优解,因此,根据Q的定义,的又知θ>0,因此,由式()可得()因此,w是对偶问题的可行解10