知识卡片

普通读书笔记卡 · 3689.b.1

相等可行目标值证明双最优

理解等级:中级

对标准原问题 max cᵀx 及其对偶 min bᵀy,如果找到一对可行解 x,y 且 cᵀx=bᵀy,那么任意原可行解 x′ 都满足 cᵀx′≤bᵀy=cᵀx,任意对偶可行解 y′ 都满足 bᵀy′≥cᵀx=bᵀy。因此 x 与 y 分别达到最大值和最小值,两者均最优。

等式把弱对偶留下的“对偶间隙”闭合为 0,所以这对可行解是一张无需枚举其他解的最优性证书。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      Thus, if feasible solutions x and ӯ have the same objective value, neither can be improved. ▪ We now show that, at optimality, the primal and dual objective values are indeed equal. To prove linear programming duality, we will require one lemma from linear algebra, known as Farkas’s lemma, the

    参考来源

    - 位置:《算法导论(第4版)》第29章《线性规划》(OEBPS/chapter029.xhtml,文本字符[35000,40000))。 - 结论依据:引理29.1后的直接推论指出,若原、对偶可行解目标值相同,则两者都不能继续改进。 - 原始内容:Thus, if feasible solutions x and ӯ have the same objective value, neither can be improved. ▪ We now show that, at optimality, the primal and dual objective values are indeed equal. To prove linear programming duality, we will require one lemma from linear algebra, known as Farkas’s lemma, the