原始-对偶算法.ppt

1、1,原始-对偶算法,14721472 马 韶 东,2,互补松弛定理,定理1 设 和 分别是原问题和对偶问题的可行解，那么 和 都是最优解的充要条件是，对于所有j，下列关系成立： （1）如果 ，就有 ； （2）如果 ，就有,3,原始对偶算法的基本思想,原始对偶算法不同于原始的单纯形法，也不同于对偶算法，它的基思思想是，从对偶问题的一个可行解开始，同时计算原问题和对偶问题，试图求出原问题的满足互补松弛条件的可行解，当然，这样的可行解就是最优解。 考虑原问题 （4.3.1） 它的对偶问题 （4.3.2） 其中 是m*n矩阵，,4,设 是对偶问题（4.3.2）的一个可行解，即满足 在已知对偶问题的一个

2、可行解 的条件下，把对偶问题的约束划分为两组，定义下标集 显然，当 时， 。 假如 是对偶问题的最优解（当然，现在的 不一定是最优解），根据互补松弛定理， 时 。,5,下面用两阶段法求对偶问题的最优解。 在 的假设下解一阶段问题 （4.3.4） 其中 是分量全为1的m维向量，y是由m个人工变量组成的m维列向量。 我们称线性规划（4.3.4）为限定原始问题。这个问题必存在最优解，求解的结果必是最优值等于零或大于零。,6,若问题（4.3.4）的最优值等于零，则y=0。设其最优解为 再由假设可以得到 根据互补松弛定理，它也是原问题（4.3.1）的最优解。,7,若限定原始问题（4.3.4）的最优值大于

3、零，则原问题（4.3.1）不存在使 的可行解，同时也表明了 不是对偶问题（4.3.2）的最优解。 因此需要修改对偶问题的可行解 ，并构造新的原始限定问题，再进行求解，以此类推，直至得到原问题的最优解，或者得出原问题无可行解的结论。,8,现在分析当原始限定问题的最优值大于零时怎样修改对偶问题的可行解 。 考虑限定原始问题（4.3.4）的对偶问题 （4.3.5） 设上述线性规划（4.3.5）的最优解是 ，可由求解限定原始问题的单纯形乘子结果得到。,9,下面利用对偶问题（4.3.2）的可行解 和线性规划(4.3.5)的最优解 来构造对偶问题(4.3.2)的一个新的可行解，令 其中 .这时有 (4.3

4、.7) 在下面的讨论中可以看到，只要适当选择 的取值，就能使w为对偶问题(4.3.2)的可行解。,10,分两种情形讨论。 (1) 这时， 是限定原始问题中的变量，由于 是线性规划（4.3.5）的最优解，因此 ，根据Q的定义， 的 又知0，因此，由式（4.3.7）可得 (4.3.8) 因此，w是对偶问题的可行解,11,(2) 这时，根据Q的定义，有 。 如果 ，则根据(4.3.7)式，有 ； 如果 ，则令 (4.3.9),12,将式(4.3.9)带入式(4.3.7)，必有 因此，按(4.3.7)式确定值，必有 (4.3.10) 即用上述方法构造出的w是对偶问题的可行解。,13,求出对偶问题可行解

5、w后，修改集合Q，再解限定原始问题。由于限定原始问题中，对应基变量 的判别数呵 ，把它代入(4.3.7)得到 ，因此这些变量的下标仍属于Q。在解限定原始问题时可从现行基开始继续迭代。此外，把值代入(4.3.7)时，有 这表明 ，由(4.3.9)知判别数 ，因此 可作为进基变量。,14,如果限定原始问题是非退化的，当原问题存在最优解时，经有限次迭代必收敛。 当限定原始问题的最优值大于零时，可能遇到这样的情形：对于所有j（包括不属于Q的j），有 。这时，由(4.3.7)知，任意0，均有 。即w是对偶问题的可行解。对偶问题目标函数值,对偶问题,15,其中 是限定原始问题最优值。由于 0，可取任意大正

6、数，对偶问题目标函数值在可行域上无上界，原问题无可行解。,限定原始问题,16,总结一下大体思路如下图,初始可行解w,最优值0,17,计算步骤,根据以上分析，原始对偶算法计算步骤如下： (1) 给定对偶问题(4.3.2)的一个可行解w， 使得对所有j，成立 。 (2) 构造原始限定问题，令 求解问题,若 =0，则停止迭代，得到最优解。否则，进行(3)。,限定原始问题,18,(3) 设上述问题达到最优时单纯形乘子（即问题4.3.5的最优解）v。若对所有j均成立 ，则停止计算，原问题无可行解。否则。进行步骤(4)。 (4) 令 令 ，返回步骤(2)。,19,实际求解时我们运用表格形式进行迭代。初始表结构如下：,变量xj 中属于限定原始问题的，则用在上方标注。解限定原始问题的进离基运算要在标的列和y的列进行,20,限定原始问题达到最 优时,若