知识卡片
弱对偶给原目标设上界
对原问题可行解 x,有 Ax≤b、x≥0;对偶可行解 y 满足 Aᵀy≥c、y≥0。两次利用非负性逐项相乘可得
cᵀx≤xᵀAᵀy=yᵀAx≤yᵀb=bᵀy。
这就是弱对偶:任何原问题目标值都不超过任何对偶可行值。即使尚未求到最优解,一个可行 y 也能给原问题提供可验证上界。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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