知识卡片
强对偶使有限最优值相等
标准形原问题是 max cᵀx,满足 Ax≤b、x≥0;对偶是 min bᵀy,满足 Aᵀy≥c、y≥0。若两者都可行且有界,则各自最优解满足 cᵀx*=bᵀy*。
弱对偶只保证任意可行对有 cᵀx≤bᵀy;强对偶进一步保证最优时对偶间隙为 0,即最紧上界确实达到。原书证明用法卡斯引理构造出与原最优值相等的对偶可行证书。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第29章 线性规划 · 查看原书依据
Theorem 29.4 (Linear-programming duality) Given the primal linear program in (29.31)–(29.33) and its corresponding dual in (29.34)–(29.36), if both are feasible and bounded, then for optimal solutions x* and y*, we have cTx* = bTy*. Proof Let μ = bTy* be the optimal value of the dual
参考来源
- 位置:《算法导论(第4版)》第29章《线性规划》(OEBPS/chapter029.xhtml,文本字符[35000,40000))。
- 结论依据:定理29.4在原、对偶均可行且有界的前提下证明最优值 `cᵀx*=bᵀy*`,证明使用法卡斯引理构造可行证书。
- 原始内容:Theorem 29.4 (Linear-programming duality) Given the primal linear program in (29.31)–(29.33) and its corresponding dual in (29.34)–(29.36), if both are feasible and bounded, then for optimal solutions x * and y *, we have c T x * = b T y *. Proof Let μ = b T y * be the optimal value of the dual