★ FEATURED ARTICLE 文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载本文针对《算法导论第三版》CLRS第 29 章章末问题 29-4完整展开 Farkas 引理的证明先证明两个线性系统不能同时可解再通过构造目标恒为常数的线性规划及其对偶利用强对偶性与无界性证明二者至少一个可解。读完本文你将掌握 Farkas 引理的符号约定与两种等价表述、其与线性规划弱对偶/强对偶定理的深层联系并能够将这套转置 构造对偶 无界性的论证模板复用到其他线性规划可行性证明中。一、问题背景Farkas 引理在第 29 章中的位置第 29 章系统讲述了线性规划Linear Programming的建模与求解29.1 节定义标准形式与松弛形式见 docs/Chap29/29.1.md29.3 节给出 SIMPLEX 算法与 PIVOT 过程见 docs/Chap29/29.3.md29.4 节建立对偶性理论见 docs/Chap29/29.4.md29.5 节解决初始基本可行解的寻找问题见 docs/Chap29/29.5.md。Problem 29-4 正是对 29.4 节对偶性理论的一次直接应用它要求用对偶思想证明一个纯代数的择一定理alternative theorem。围绕这道题本章还有多个问题共享同一套对偶工具Problem 29-1线性不等式可行性证明有线性规划求解器 ⟺ 有可行性判定器其中用到了推论 Corollary 29.9可行解目标值相等则必最优见 docs/Chap29/Problems/29-1.mdProblem 29-2互补松弛刻画原问题可行解与对偶可行解同为最优的充要条件见 docs/Chap29/Problems/29-2.mdProblem 29-3整数线性规划说明弱对偶对整数线性规划仍然成立、而强对偶不成立见 docs/Chap29/Problems/29-3.mdProblem 29-5最小费用环流将最小费用流、最大流、单源最短路统一建模为线性规划见 docs/Chap29/Problems/29-5.md。Farkas 引理是这些对偶结论的地基之一它断言线性系统的可解性与线性规划对偶性本质上是同一件事的两种说法。二、题目重述与符号约定设 $A$ 为 $m \times n$ 矩阵$c$ 为 $n$ 维向量。Farkas 引理原题见 docs/Chap29/Problems/29-4.md断言下列两个系统恰好有一个可解$$ \begin{aligned} Ax \le 0, \ c^Tx 0 \end{aligned} $$与$$ \begin{aligned} A^Ty c, \ y \le 0 \end{aligned} $$其中 $x$ 是 $n$ 维向量$y$ 是 $m$ 维向量。注意第一个系统中的不等式 $c^T x 0$ 是严格不等式这也是择一成立的关键——若把它放宽为 $\ge$两个系统可能同时可解例如 $x 0$ 恒满足 $Ax \le 0$此时 $c^T x 0 \ge 0$。直观地说第二个系统可解等价于 $c$ 可以表示为 $A$ 的行向量的线性组合组合系数为 $y$第一个系统可解则说明存在一个方向 $x$它在 $A$ 的阴影里$Ax \le 0$却与 $c$ 成锐角$c^T x 0$。Farkas 引理断言这两种情形恰好有一种发生这是凸锥与半空间的分离这一几何事实的代数表述。三、证明第一步两个系统不能同时可解这是证明中纯粹代数的一部分不需要任何线性规划知识。假设两个系统同时可解。设 $x$ 是第一个系统的解$y$ 是第二个系统的解。由 $Ax \le 0$两边转置得$$ x^{\text T}A^{\text T} \le 0^{\text T}, $$即行向量 $x^{\text T}A^{\text T} (Ax)^{\text T}$ 的每一个分量 $(Ax)_i$ 都是非正数。现在右乘 $y$并逐项写出$$ x^{\text T}c x^{\text T}A^{\text T}y \sum_{i1}^{m} (Ax)_i , y_i. $$由于 $(Ax)_i \le 0$ 且 $y_i \le 0$两个非正数相乘得非负数因此 $x^{\text T}c \ge 0$即 $c^{\text T}x \ge 0$。这与第一个系统中的严格不等式 $c^{\text T}x 0$ 矛盾。故两个系统不可能同时可解。细节说明原题解在推导时写为 $x^{\text T}A^{\text T}y \le 0^{\text T}$docs/Chap29/Problems/29-4.md 第三段这里的不等式方向以逐项乘积复核为准——因为右乘的 $y \le 0$不等式方向会翻转正确结论是 $x^{\text T}c \ge 0$。但无论取哪个方向得到的结果都与 $c^{\text T}x 0$ 矛盾所以论证的结论不受影响。这也提示读者在 Farkas 型证明中$y$ 的符号方向必须与 $c^T x$ 的不等式方向匹配详见第六节。这一步的直觉是如果 $c$ 恰是 $A$ 的行向量按系数 $y$ 的线性组合那么 $c$ 在由 $A$ 的行向量张成的方向空间中与 $A$ 的行向量同向或反向取决于 $y$ 的符号而任何满足 $Ax \le 0$ 的 $x$ 都与这些行向量成钝角或直角自然无法再与 $c$ 成锐角。四、证明第二步第二个系统无解 ⟹ 第一个系统必有解现在假设第二个系统无解即不存在 $y \le 0$ 使 $A^{\text T}y c$。题解的做法是把这一假设翻译成一个线性规划的可行性结论再利用对偶理论推出矛盾。构造如下的线性规划作为原问题$$ \text{maximize } 0, \quad \text{subject to } A^{\text T}y c \text{ 且 } y \ge 0, $$目标函数恒为 $0$可行性是唯一关注点。相应地写出它的对偶问题对偶变量记为 $x$$$ \text{minimize } -c^{\text T}x, \quad \text{subject to } Ax \le 0. $$接下来是题解论证链条上的三个关键点原问题不可行由第二个系统无解这一假设结合符号方向约定见第六节上述原问题不存在可行解 $y \ge 0$ 满足 $A^{\text T}y c$故原问题是不可行infeasible的。对偶恒可行对偶问题的约束是 $Ax \le 0$取 $x 0$ 即满足 $A \cdot 0 0 \le 0$。因此对偶问题总是可行的无论 $A$、$c$ 取什么值。对偶必然无界假设对偶问题存在有限最优解则由强对偶定理Theorem 29.10见下节原问题也必然存在有限最优解且二者最优值相等——这与原问题不可行矛盾。于是对偶问题不可能有有限最优解而对偶可行又无有限最优解唯一的可能就是无界unbounded。对偶无界的含义是存在满足 $Ax \le 0$ 的可行向量 $x$使目标函数 $-c^{\text T}x$ 可以任意小趋于 $-\infty$。等价地$c^{\text T}x$ 可以任意大特别是可以严格大于 $0$$$ \exists x:\ Ax \le 0 \ \text{且}\ c^{\text T}x 0. $$这正是第一个系统的解。综合第三节与本节两系统不能同时可解第二个系统无解时第一个系统必有解。故恰好一个系统可解Farkas 引理得证。∎五、支撑论证的对偶理论弱对偶、强对偶与无界-不可行关系第二步论证完全建立在第 29.4 节的对偶性定理上这里把用到的三个结论及其在仓库中的证据一一列出1. 对偶的标准构造。对标准形式的最大化问题$c^{\text T}x$约束 $Ax \le b$$x \ge 0$其对偶是 $b^{\text T}y$ 的最小化问题约束 $A^{\text T}y \ge c$$y \ge 0$。这道构造规则在 docs/Chap29/29.4.md 的 29.4-1 中有直接演示转置 $A$、交换 $b$ 与 $c$、最大化改最小化。本文第四节的 LP 正是按此规则写出的对偶等式约束 $A^{\text T}y c$ 拆成两个不等式后右端向量即 $[c;\ -c]$与对偶变量 $x$ 相乘便得到目标 $-c^{\text T}x$。2. 弱对偶Lemma 29.8。对任意一对可行解原问题的 $x$ 与对偶的 $y$原问题目标值 $\le$ 对偶目标值。它的直接推论是最大化问题无界 ⟹ 对偶不可行。反过来若对偶可行则原问题不可能无界——本文用它保证对偶可行 无有限最优 ⟹ 无界的判定有效。弱对偶对整数线性规划仍然成立docs/Chap29/Problems/29-3.md 第 a 问该证明完全不含整性条件。3. 强对偶Theorem 29.10与推论Corollary 29.9。若原问题有有限最优值则对偶也有且两值相等反过来若原问题与对偶各有一可行解且目标值相等则二者都是最优解这就是 Problem 29-1 中把可行性判定归约到线性规划求解所用的关键推论见 docs/Chap29/Problems/29-1.md 第 b 问。强对偶还暗示一条边界它依赖解空间的连续性因此对整数线性规划不再成立——Problem 29-3 第 b 问给出了一个 $A (1), b (1/2), c (2)$ 的反例其中整数版原问题最优值为 $0$ 而对偶最优值为 $1$docs/Chap29/Problems/29-3.md。把这三个结论拼起来就得到第四节的完整推理原问题不可行 对偶可行 ⟹ 对偶无界 ⟹ 存在 $Ax \le 0$ 且 $c^{\text T}x 0$。这也解释了为什么 Farkas 引理常被看作强对偶定理的等价表述——教材中常见的路径正是用 Farkas 引理反过来证明强对偶。六、证明复盘符号方向与 Farkas 引理的等价形式Farkas 引理恰好一个可解的成立对两个系统中不等式/等式的方向匹配有严格要求。从代数的角度可以确认以下结论可由第四节的对偶论证逐字复核若第二个系统写作 $A^{\text T}y c,\ y \le 0$则第一个系统应取 $Ax \le 0$ 且 $c^{\text T}x 0$若第二个系统写作 $A^{\text T}y c,\ y \ge 0$则第一个系统取 $Ax \le 0$ 且 $c^{\text T}x 0$。两种形式通过整体替换 $y \rightarrow -y$同时把 $c$ 换成 $-c$或翻转 $c^{\text T}x$ 的不等式方向互相转化二者是同一个定理。本仓库题解采用 $y \le 0$ 与 $c^{\text T}x 0$ 的组合并借助原问题不可行 ⟹ 对偶无界 ⟹ 存在 $Ax \le 0$ 且 $c^{\text T}x 0$完成论证docs/Chap29/Problems/29-4.md 第二段。在自行引用或证明该引理时建议按上面的匹配关系核对一遍符号以 $1 \times 1$ 情形为例取 $A [1]$、$c [1]$若第二个系统写作 $A^{\text T}y c,\ y \ge 0$则 $y 1$ 是解第一个系统$x \le 0$ 且 $x 0$无解恰好一个成立若方向不匹配则可能出现两个系统同时无解的情形破坏择一结论。七、与本章其他问题的联动Farkas 引理的应用面这道题的论证模板在整章中反复出现可作为后续阅读的参照系Problem 29-1证明可行性判定与线性规划求解可以多项式归约它把原问题与对偶的目标值强制相等借助 Corollary 29.9 把最优翻译成可行docs/Chap29/Problems/29-1.md。这与 Farkas 引理把可解性翻译成对偶可行性是同一思想的两种形态。Problem 29-2互补松弛给出原问题可行解 $x$ 与对偶可行解 $y$ 同为最优的充要条件$\sum_i a_{ij}y_i c_j$ 或 $x_j 0$以及 $\sum_j a_{ij}x_j b_i$ 或 $y_i 0$docs/Chap29/Problems/29-2.md。它的证明同样依赖目标值相等即最优的推论与 Farkas 引理的第三步论证同源。Problem 29-3划定强对偶的边界弱对偶以及由此推出的无界-不可行关系对整数线性规划仍成立但强对偶不成立docs/Chap29/Problems/29-3.md。这从反面说明 Farkas 引理中的第二个系统之所以干净正是因为它允许 $y$ 取连续实值。Problem 29-5展示对偶与环流结构的对应给每条反向边赋予负费用把最大流、最短路都归约为最小费用环流docs/Chap29/Problems/29-5.md。该问题第 b 问所有费用为正时最优流为零与 Farkas 引理中 $x 0$ 恒为对偶可行解的性质一脉相承。八、在本仓库中如何查阅与继续深入原始题解位于 docs/Chap29/Problems/29-4.md是本文的直接依据第 29 章各节习题标准/松弛形式、SIMPLEX、对偶、初始可行解分别位于 docs/Chap29/29.1.md、docs/Chap29/29.3.md、docs/Chap29/29.4.md、docs/Chap29/29.5.md本仓库是《算法导论》第三版习题解答的 MkDocs 站点导航配置见 mkdocs.ymlProblem 29-4 在导航中登记为 29-4 Farkasss lemma站点说明见 README.md。数学公式通过 KaTeX 渲染extra_javascript引入js/katex.js与 KaTeX CDN因此文中所有 $LaTeX$ 公式在本地mkdocs serve或仓库构建的站点上均可直接显示Farkas 引理是一道纯证明题本仓库不包含对应算法的可执行实现若要验证论证可取低维实例如 $1 \times 1$ 或 $2 \times 2$ 矩阵手工代入第六节给出的方向匹配关系进行检验。掌握 Problem 29-4 之后你就拥有了一把通用钥匙任何验证某个线性系统无解的命题都可以尝试改写成对偶无界的形式再借助弱对偶与强对偶完成证明——这正是 Farkas 引理留给我们的方法论遗产。赞分享文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载相关推荐CLRS 第 29 章问题 29-3 解析整数线性规划的弱对偶保持、强对偶失效与最优值链式不等式CLRS 第 29 章问题 29 3 解析整数线性规划的弱对偶保持、强对偶失效与最优值链式不等式 整数线性规划Integer Linear Programm文档教程教育Chrome Regex Search高效使用技巧指南让正则表达式搜索如虎添翼Chrome Regex Search高效使用技巧指南让正则表达式搜索如虎添翼 在信息爆炸的今天 正则表达式搜索 已成为高效处理网页内容的必备技能。Chro文档教程教育CLRS《算法导论》问题 29-2 深度解析线性规划的互补松弛条件Complementary SlacknessCLRS《算法导论》问题 29 2 深度解析线性规划的互补松弛条件Complementary Slackness 导读 本文以开源仓库 walkccc/文档教程教育上一篇Apache Thrift netstd 测试套件实战指南构建、运行与跨语言验证下一篇Terragrunt find 命令完全指南发现、排序与筛选 IaC 配置创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
阅读完成 · 觉得有帮助？
