知识卡片

普通读书笔记卡 · 3689

对偶把最大化配成最小化

理解等级:初级

线性规划对偶为原最大化问题构造相关的最小化问题。两者的可行解可相互提供上下界;在满足可行且有界等条件时,最优目标值相等,因此可用对偶解核验原问题的最优性。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      In general, given a maximization problem, duality allows you to formulate a related minimization problem that has the same objective value. The idea of duality is actually more general than linear programming, but we restrict our attention to linear programming in this section. Duality enables us to prove that a solution is indeed optimal. We saw

    参考来源

    - 位置:《算法导论(第4版)》第29章《线性规划》(OEBPS/chapter029.xhtml,文本字符[30000,35000))。 - 结论依据:原文陈述多商品流、对偶、可行性证书或网络优化的定义与条件;相应公式图已核对。 - 原始内容:In general, given a maximization problem, duality allows you to formulate a related minimization problem that has the same objective value. The idea of duality is actually more general than linear programming, but we restrict our attention to linear programming in this section. Duality enables us to prove that a solution is indeed optimal. We saw