原始-对偶算法

1原始-对偶算法14721472马韶东2互补松弛定理定理1设和分别是原问题和对偶问题的可行解，那么和都是最优解的充要条件是，对于所有j，下列关系成立：（1）如果，就有；（2）如果，就有)0(x0)0(jxjjcpw)0(jjcpw)0(0)0(jx)0(w)0(x)0(w3原始—对偶算法的基本思想原始—对偶算法不同于原始的单纯形法，也不同于对偶算法，它的基思思想是，从对偶问题的一个可行解开始，同时计算原问题和对偶问题，试图求出原问题的满足互补松弛条件的可行解，当然，这样的可行解就是最优解。考虑原问题（4.3.1）它的对偶问题（4.3.2）其中是m*n矩阵，0..minxbAxtscxcwAtswb..max0b),,(1nppA4设是对偶问题（4.3.2）的一个可行解，即满足在已知对偶问题的一个可行解的条件下，把对偶问题的约束划分为两组，定义下标集显然，当时，。假如是对偶问题的最优解（当然，现在的不一定是最优解），根据互补松弛定理，时。)0(wcAw)0()0(w}{)0(jjcpwjQQjjjcpw)0()0(w)0(wQj0jx5下面用两阶段法求对偶问题的最优解。在的假设下解一阶段问题（4.3.4）其中是分量全为1的m维向量，y是由m个人工变量组成的m维列向量。我们称线性规划（4.3.4）为限定原始问题。这个问题必存在最优解，求解的结果必是最优值等于零或大于零。0,0..minyQjxbyxptsyejQjjiT)1,...,1(TeQj0jx)(0Qjxj6若问题（4.3.4）的最优值等于零，则y=0。设其最优解为再由假设可以得到根据互补松弛定理，它也是原问题（4.3.1）的最优解。0,,)0(yQjaxjjQjxQjaxjjj,0;,)0()0(7若限定原始问题（4.3.4）的最优值大于零，则原问题（4.3.1）不存在使的可行解，同时也表明了不是对偶问题（4.3.2）的最优解。因此需要修改对偶问题的可行解，并构造新的原始限定问题，再进行求解，以此类推，直至得到原问题的最优解，或者得出原问题无可行解的结论。)(0Qjxj)0(w)0(w8现在分析当原始限定问题的最优值大于零时怎样修改对偶问题的可行解。考虑限定原始问题（4.3.4）的对偶问题（4.3.5）设上述线性规划（4.3.5）的最优解是，可由求解限定原始问题的单纯形乘子结果得到。)0(w.,,0..maxTjevQjvptsvb)0(v9下面利用对偶问题（4.3.2）的可行解和线性规划(4.3.5)的最优解来构造对偶问题(4.3.2)的一个新的可行解，令其中.这时有(4.3.7)在下面的讨论中可以看到，只要适当选择的取值，就能使w为对偶问题(4.3.2)的可行解。)0(w)0(v,)0()0(vww0jjjjjjjpvcpwcpvwcwp)0()0()0()0()()(10分两种情形讨论。(1)这时，是限定原始问题中的变量，由于是线性规划（4.3.5）的最优解，因此，根据Q的定义，的又知θ0，因此，由式（4.3.7）可得(4.3.8)因此，w是对偶问题的可行解Qjjx)0(v0)0(jpv0)0(jjcpwQjcwpjj,0jjjjjjjpvcpwcpvwcwp)0()0()0()0()()(}{)0(jjcpwjQ11(2)这时，根据Q的定义，有。如果，则根据(4.3.7)式，有；如果，则令(4.3.9)Qj0)0(jjcpw0)0(jpv0jjcwp0)0(jpv.)(0)(min)0()0()0()0()0(kkkjjjjjpvcpwpvpvcpwjjjjjjjpvcpwcpvwcwp)0()0()0()0()()(12将式(4.3.9)带入式(4.3.7)，必有因此，按(4.3.7)式确定θ值，必有(4.3.10)即用上述方法构造出的w是对偶问题的可行解。0)()()()()0()0()0()0()0()0()0()0(jjjjjjjkkkjjjjpvpvcpwcpwpvpvcpwcpwcwpQjcwpjj,0jjjjjjjpvcpwcpvwcwp)0()0()0()0()()(13求出对偶问题可行解w后，修改集合Q，再解限定原始问题。由于限定原始问题中，对应基变量的判别数呵，把它代入(4.3.7)得到，因此这些变量的下标仍属于Q。在解限定原始问题时可从现行基开始继续迭代。此外，把θ值代入(4.3.7)时，有这表明，由(4.3.9)知判别数，因此可作为进基变量。jx0)0(jpvjjjjjjjpvcpwcpvwcwp)0()0()0()0()()(0jjcwp0kkcwpQk0)0(kpvkx14如果限定原始问题是非退化的，当原问题存在最优解时，经有限次迭代必收敛。当限定原始问题的最优值大于零时，可能遇到这样的情形：对于所有j（包括不属于Q的j），有。这时，由(4.3.7)知，任意θ0，均有。即w是对偶问题的可行解。对偶问题目标函数值0)0(jpv0jjcwp0)0()0()0()0()0()(Zbwbvbwbvwwbjjjjjjjpvcpwcpvwcwp)0()0()0()0()()(对偶问题cwA15其中是限定原始问题最优值。由于0，θ可取任意大正数，对偶问题目标函数值在可行域上无上界，原问题无可行解。0Z0Z0)0()0()0()0()0()(Zbwbvbwbvwwb限定原始问题0,0..minyQjxbyxptsyejQjjiT16总结一下大体思路如下图原始对偶限定原始限定原始对偶w调整到w新的W初始可行解w最优值017计算步骤根据以上分析，原始—对偶算法计算步骤如下：(1)给定对偶问题(4.3.2)的一个可行解w，使得对所有j，成立。(2)构造原始限定问题，令求解问题0jjcwp}0{jjcwpjQ0,0..minyQjxbyxptsyejQjjiT若=0，则停止迭代，得到最优解。否则，进行(3)。0ZcwAtswb..max限定原始问题18(3)设上述问题达到最优时单纯形乘子（即问题4.3.5的最优解）v。若对所有j均成立，则停止计算，原问题无可行解。否则。进行步骤(4)。(4)令令，返回步骤(2)。0jvp.0)(minjjjjvpvpcwpvww:19实际求解时我们运用表格形式进行迭代。初始表结构如下：ˆ-0-mxyyAIbvAcZwAcf变量xj中属于限定原始问题的，则用在上方标注。解限定原始问题的进离基运算要在标的列和y的列进行20限定原始问题达到最优时,若要修改对偶问题的可行解，只需把第m+1行倍加到第m+2行即可ˆ-0-mxyyAIbvAcZwAcfjjwwpcfwb对偶问题的可行解为时所有的和函数值ˆˆ()0.ˆˆˆjjjjjjjzcRPxczcvZp一阶段问题的判别数及限定原始问题目标函数对于原来变量，值求解每一限定原始问题的过程中除第m+2行外，均作运算但只能是属于限定原始问题的变量才有资格作为进基变量。21“限定原始问题达到最优时,若要修改对偶问题的可行解，只需把第m+1行倍加到第m+2行即可”的理由由(4.3.7))()()()0()0()0(jjjjjjjjjczcpwpvcpwcwp0)0(Zbwwbˆ-0-mxyyAIbvAcZwAcfjjczwbf0)0()0()0()0()0()(Zbwbvbwbvwwb22谢谢