原始-对偶算法.ppt

1 原始 对偶算法 14721472马韶东 2 互补松弛定理 定理1设和分别是原问题和对偶问题的可行解 那么和都是最优解的充要条件是 对于所有j 下列关系成立 1 如果 就有 2 如果 就有 3 原始 对偶算法的基本思想 原始 对偶算法不同于原始的单纯形法 也不同于对偶算法 它的基思思想是 从对偶问题的一个可行解开始 同时计算原问题和对偶问题 试图求出原问题的满足互补松弛条件的可行解 当然 这样的可行解就是最优解 考虑原问题 4 3 1 它的对偶问题 4 3 2 其中是m n矩阵 4 设是对偶问题 4 3 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 的最优值大于零 则原问题 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 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 求出对偶问题可行解w后 修改集合Q 再解限定原始问题 由于限定原始问题中 对应基变量的判别数呵 把它代入 4 3 7 得到 因此这些变量的下标仍属于Q 在解限定原始问题时可从现行基开始继续迭代 此外 把 值代入 4 3 7 时 有这表明 由 4 3 9 知判别数 因此可作为进基变量 14 如果限定原始问题是非退化的 当原问题存在最优解时 经有限次迭代必收敛 当限定原始问题的最优值大于零时 可能遇到这样的情形 对于所有j 包括不属于Q的j 有 这时 由 4 3 7 知 任意 0 均有 即w是对偶问题的可行解 对偶问题目标函数值 对偶问题 15 其中是限定原始问题最优值 由于 0 可取任意大正数 对偶问题目标函数值在可行域上无上界 原问题无可行解 限定原始问题 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 限定原始问题达到最优时 若要修改对