知识卡片
对偶乘子构成原问题上界
考虑标准原问题:最大化 cᵀx,满足 Ax≤b、x≥0。给第 i 条 ≤ 约束乘以非负数 y_i 并求和,不会改变不等号方向,得到 (Aᵀy)ᵀx≤bᵀy。若 Aᵀy≥c,则 cᵀx≤(Aᵀy)ᵀx≤bᵀy。所以每个对偶可行向量 y 都构成原目标值的可验证上界;对偶最小化 bᵀy,就是在这些加权上界中寻找最紧者。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第29章 线性规划 · 查看原书依据
The multipliers y1, y2, and y3 must be nonnegative, because otherwise you cannot combine the inequalities. Of course, you would like the upper bound to be as small as possible, and so you want to choose y to minimize 30y1 + 24y2 + 36y3. Observe that we have just described the dual linear program as the problem of finding the smallest possible upper bound on the primal. We’ll formalize this idea and show
参考来源
- 位置:《算法导论(第4版)》第29章《线性规划》(OEBPS/chapter029.xhtml,文本字符[35000,40000))。
- 结论依据:原文先以非负乘子组合原约束构造目标上界,再把“最小化该上界”的条件写成对偶线性规划。
- 原始内容:The multipliers y 1 , y 2 , and y 3 must be nonnegative, because otherwise you cannot combine the inequalities. Of course, you would like the upper bound to be as small as possible, and so you want to choose y to minimize 30 y 1 + 24 y 2 + 36 y 3 . Observe that we have just described the dual linear program as the problem of finding the smallest possible upper bound on the primal. We’ll formalize this idea and show