知识卡片

普通读书笔记卡 · 3689.a

对偶交换目标与约束系数

理解等级:中级

设 A∈ℝ^{m×n}、x,c∈ℝ^n、b,y∈ℝ^m。原问题为最大化 cᵀx,满足 Ax≤b、x≥0;其对偶为最小化 bᵀy,满足 Aᵀy≥c、y≥0。转置把原问题的 m 行约束变成 m 个对偶变量,又把原问题的 n 个变量变成 n 条对偶约束。

这里的方向依赖这组标准形:原问题是非负变量下的最大化与 ≤ 约束。若变量可正可负或约束为等式,必须先作等价变换,不能机械套用同一不等号方向。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      Mechanically, to form the dual, change the maximization to a minimization, exchange the roles of coefficients on the right-hand sides and in the objective function, and replace each ≤ by ≥. Each of the m constraints in the primal corresponds to a variable yi in the dual.

    参考来源

    - 位置:《算法导论(第4版)》第29章《线性规划》(OEBPS/chapter029.xhtml,文本字符[35000,40000))。 - 结论依据:第29.3节原对偶形式;`OEBPS/images/Art_P1004.jpg`–`Art_P1007.jpg`(式29.31–29.36)逐项给出目标、约束和非负条件。 - 公式图核读:原问题 max cᵀx、Ax≤b、x≥0;对偶 min bᵀy、Aᵀy≥c、y≥0。 - 原始内容:Mechanically, to form the dual, change the maximization to a minimization, exchange the roles of coefficients on the right-hand sides and in the objective function, and replace each ≤ by ≥. Each of the m constraints in the primal corresponds to a variable y i in the dual.