知识卡片

普通读书笔记卡 · 3689.b

弱对偶给原目标设上界

理解等级:中级

对原问题可行解 x,有 Ax≤b、x≥0;对偶可行解 y 满足 Aᵀy≥c、y≥0。两次利用非负性逐项相乘可得

cᵀx≤xᵀAᵀy=yᵀAx≤yᵀb=bᵀy。

这就是弱对偶:任何原问题目标值都不超过任何对偶可行值。即使尚未求到最优解,一个可行 y 也能给原问题提供可验证上界。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第29章 线性规划 · 查看原书依据

      We begin by demonstrating weak duality, which states that any feasible solution to the primal linear program has a value no greater than that of any feasible solution to the dual linear program. Lemma 29.1 (Weak linear-programming duality) Let x be any feasible solution to the primal linear program in (29.31)–(29.33), and let ӯ be any feasible solution to

    参考来源

    - 位置:《算法导论(第4版)》第29章《线性规划》(OEBPS/chapter029.xhtml,文本字符[35000,40000))。 - 结论依据:引理29.1以原、对偶可行性和非负性证明 `cᵀx≤bᵀy`。 - 原始内容:We begin by demonstrating weak duality , which states that any feasible solution to the primal linear program has a value no greater than that of any feasible solution to the dual linear program. Lemma 29.1 (Weak linear-programming duality) Let x be any feasible solution to the primal linear program in (29.31)–(29.33), and let ӯ be any feasible solution to