知识卡片

普通读书笔记卡 · 3689.c

强对偶使有限最优值相等

理解等级:高级

标准形原问题是 max cᵀx,满足 Ax≤b、x≥0;对偶是 min bᵀy,满足 Aᵀy≥c、y≥0。若两者都可行且有界,则各自最优解满足 cᵀx*=bᵀy*。

弱对偶只保证任意可行对有 cᵀx≤bᵀy;强对偶进一步保证最优时对偶间隙为 0,即最紧上界确实达到。原书证明用法卡斯引理构造出与原最优值相等的对偶可行证书。

这张卡片看不懂?

已有反馈 · 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