知识卡片
对偶交换目标与约束系数
设 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 条对偶约束。
这里的方向依赖这组标准形:原问题是非负变量下的最大化与 ≤ 约束。若变量可正可负或约束为等式,必须先作等价变换,不能机械套用同一不等号方向。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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.