如何理解 Farkas 引理？
拨开迷雾，理解 Farkas 引理
Farkas 引理，这个名字在最优化、控制论和图论等领域中常常出现，却也常常让初学者感到一丝晦涩。它究竟说了什么？为何如此重要？今天，我们就来一层层地剥开它神秘的面纱，力求用最直观、最接地气的方式，让你真正理解这个强大的数学工具。
想象一下，我们不是在枯燥地学习抽象的数学公式，而是在解决一个现实世界的问题。
从一个简单的场景出发
假设你是一位农场主，你拥有两块土地，一块专门种玉米，另一块专门种小麦。每种作物都需要一定的劳动力和化肥。
玉米： 每亩需要 2 个单位的劳动力， 1 个单位的化肥。
小麦： 每亩需要 1 个单位的劳动力， 2 个单位的化肥。
你现在拥有总共 6 个单位的劳动力 和 5 个单位的化肥。
你希望最大化你的总产量（假设每亩玉米产量是 1，每亩小麦产量也是 1，所以我们其实就是在最大化种植面积）。
你可能会列出这样的问题：
设 $x_1$ 是你种植玉米的亩数， $x_2$ 是你种植小麦的亩数。
你要满足的约束是：
劳动力约束：$2x_1 + x_2 le 6$ （你不能用超过 6 个单位的劳动力）
化肥约束：$x_1 + 2x_2 le 5$ （你不能用超过 5 个单位的化肥）
你的目标是最大化：$x_1 + x_2$
而且，你不能种植负数亩数：$x_1 ge 0, x_2 ge 0$
这是一个典型的线性规划问题。
现在，我们换个角度来思考。假设有一个神秘的“观察者”，他并不知道你实际的种植计划（$x_1, x_2$），但他知道你拥有的资源（劳动力和化肥），以及每种作物对这些资源的需求。
观察者想要判断一个“假设”：是否存在一个非负的种植组合 ($x_1, x_2$)，能够让你实现一个“目标产量”（比如，你想知道是否能种植总共 4 亩地）。
如果你的目标是种植 4 亩地，也就是说，你想找到满足：
$x_1 + x_2 = 4$
$2x_1 + x_2 le 6$
$x_1 + 2x_2 le 5$
$x_1 ge 0, x_2 ge 0$
的 $(x_1, x_2)$。
Farkas 引理登场：从“可行性”到“不可能”的判断
Farkas 引理提供的就是一种判断这种“假设”是否成立的强大工具，但它并非直接给出那个种植组合，而是从一个 “对偶” 的角度来衡量。
Farkas 引理最常见的形式之一是这样说的：
对于矩阵 $A$ 和向量 $b$，方程组 $Ax = b$ 存在非负解 $x ge 0$ 的充要条件是：对于任意满足 $y^T A ge 0$ 的向量 $y ge 0$，都有 $y^T b ge 0$。
这听起来还是有点抽象，我们把它和你刚才的农场主问题联系起来。
先将你的问题改写成更标准的矩阵形式：
目标是找到 $x = egin{pmatrix} x_1 \ x_2 end{pmatrix}$ 满足：
$egin{pmatrix} 2 & 1 \ 1 & 2 end{pmatrix} egin{pmatrix} x_1 \ x_2 end{pmatrix} le egin{pmatrix} 6 \ 5 end{pmatrix}$
$x ge 0$
我们假设你想达到的目标是 $c^T x ge K$，例如 $1 cdot x_1 + 1 cdot x_2 ge 4$。
Farkas 引理的核心思想是：如果你无法实现一个目标，那么一定存在一个“加权组合”的方式来证明你的“失败”。
让我们回到农场主场景。你有一个计划，你想看看能不能种出 4 亩地。
观察者可以这样思考：
“如果我的农场主朋友真的能够种出 4 亩地，那么他的计划 $(x_1, x_2)$ 必定满足：
$x_1 + x_2 = 4$
$2x_1 + x_2 le 6$
$x_1 + 2x_2 le 5$
$x_1 ge 0, x_2 ge 0$
现在，我能不能找到一种‘组合’这三个不等式的方法，来证明他这个计划是不可能的呢？”
这里的“组合”就是 Farkas 引理中的“向量 $y$”。
设你想达到的目标是找到一个非负的 $x$ 使得：
$Ax le b$
其中 $A = egin{pmatrix} 2 & 1 \ 1 & 2 end{pmatrix}$ (资源需求矩阵), $b = egin{pmatrix} 6 \ 5 end{pmatrix}$ (可用资源向量)。
我们想要看的是，是否存在 $x ge 0$ 使得 $c^T x ge K$（例如 $c = egin{pmatrix} 1 \ 1 end{pmatrix}$, $K = 4$）。
Farkas 引理的另一种表述方式会更贴近我们的例子：
对于矩阵 $A$ 和向量 $b$，以下两个命题是等价的：
1. 存在 $x ge 0$ 使得 $Ax le b$。 （存在一个可行的种植计划）
2. 对于任意满足 $y^T A ge 0$ 的向量 $y ge 0$，都有 $y^T b ge 0$。 （这句比较绕，我们后面解释）
更实用、更容易理解的版本是关于“不可行性”的：
对于矩阵 $A$ 和向量 $b$，以下两个命题是等价的：
1. 不存在 $x ge 0$ 使得 $Ax le b$。 （即，无论如何都无法满足所有约束）
2. 存在 $y ge 0$ 使得 $y^T A ge 0$ 并且 $y^T b < 0$。 （存在一个“反证组合”）
这第二条就是 Farkas 引理的核心！
让我们用农场主的问题来解释它：
“如果我的农场主朋友无论如何都无法找到一个种植方案来满足所有资源约束，那么一定存在一个‘资源配额’（向量 $y ge 0$）的分配方式，能够证明他的计划是不可能的。”
这里的“资源配额” $y = egin{pmatrix} y_1 \ y_2 end{pmatrix}$ 意味着：
$y_1$：你分配给“劳动力”这个资源的“权重”或“影子价格”。
$y_2$：你分配给“化肥”这个资源的“权重”或“影子价格”。
条件 $y ge 0$ 意味着这些权重不能是负的，这是符合常理的。
条件 $y^T A ge 0$ 意味着：
$y_1 cdot 2 + y_2 cdot 1 ge 0$ （劳动力权重 玉米劳动力需求 + 化肥权重 玉米化肥需求 $ge 0$）
$y_1 cdot 1 + y_2 cdot 2 ge 0$ （劳动力权重 小麦劳动力需求 + 化肥权重 小麦化肥需求 $ge 0$）
这其实是在说，你找到的这个“权重组合” $y$，对于每一种作物（即每一列 $A$）来说，其“资源需求的总权重”都是非负的。换句话说，你不能找到一个权重组合，让两种作物都“有利可图”（即资源需求的总权重为负）。
而 Farkas 引理的关键在于 $y^T b < 0$。
将 $y^T b$ 展开：
$y_1 cdot 6 + y_2 cdot 5 < 0$
这意味着，用你找到的那个“资源配额” $y$ 来衡量你的可用资源的总价值是负的。
所以，Farkas 引理的第二条表述可以这样理解：
“如果不存在一个可行的种植计划（$Ax le b, x ge 0$），那么一定存在一组非负的‘影子价格’（$y ge 0$），使得：
1. 这个‘影子价格’组合对每种作物（的资源需求）都没有‘好处’（$y^T A ge 0$）。 也就是说，如果种植一单位的玉米，其资源总价值（按影子价格计算）是正的，种植一单位的小麦，其资源总价值也是正的。换句话说，这两种作物都“不值得”你去种植。
2. 然而，用这组‘影子价格’来衡量你拥有的总资源，其价值却是负的（$y^T b < 0$）。
这听起来是不是有点矛盾？
让我们回到农场主例子，假设你想种出 4 亩地，即目标是 $x_1+x_2 ge 4$。
你的约束是 $A = egin{pmatrix} 2 & 1 \ 1 & 2 end{pmatrix}$, $b = egin{pmatrix} 6 \ 5 end{pmatrix}$。
我们来看看是否能找到一个 $y ge 0$ 使得 $y^T A ge 0$ 且 $y^T b < 0$。
设 $y = egin{pmatrix} y_1 \ y_2 end{pmatrix}$，其中 $y_1, y_2 ge 0$。
$y^T A = egin{pmatrix} y_1 & y_2 end{pmatrix} egin{pmatrix} 2 & 1 \ 1 & 2 end{pmatrix} = egin{pmatrix} 2y_1+y_2 & y_1+2y_2 end{pmatrix}$
我们要让 $2y_1+y_2 ge 0$ 且 $y_1+2y_2 ge 0$。由于 $y_1, y_2 ge 0$，这两个条件总是满足的。
现在看 $y^T b < 0$:
$y_1 cdot 6 + y_2 cdot 5 < 0$
问题来了！ 由于我们要求 $y_1 ge 0$ 且 $y_2 ge 0$，那么 $6y_1 + 5y_2$ 永远是大于等于零的。它不可能小于零！
这意味着什么？
这意味着，我们找不到一个 $y ge 0$ 使得 $y^T b < 0$。
根据 Farkas 引理的第二条表述：如果找不到 $y ge 0$ 使得 $y^T b < 0$（同时满足 $y^T A ge 0$），那么就一定存在 $x ge 0$ 使得 $Ax le b$。
换句话说，根据 Farkas 引理，我们证明了：存在一个可行的种植方案，让你能够满足资源约束。
更具体的例子：证明“不可能”
现在，假设你拥有 2 个单位的劳动力 和 1 个单位的化肥。
你的资源限制是 $b = egin{pmatrix} 2 \ 1 end{pmatrix}$。
你想看看是否能种出 3 亩地，即目标是 $x_1+x_2 ge 3$。
约束：
$2x_1 + x_2 le 2$
$x_1 + 2x_2 le 1$
$x_1 ge 0, x_2 ge 0$
Farkas 引理说：如果不可能找到这样的 $x$，那么一定存在 $y ge 0$ 使得 $y^T A ge 0$ 且 $y^T b < 0$。
我们来找找看这个 $y$。
$A = egin{pmatrix} 2 & 1 \ 1 & 2 end{pmatrix}$, $b = egin{pmatrix} 2 \ 1 end{pmatrix}$
我们需要找 $y = egin{pmatrix} y_1 \ y_2 end{pmatrix} ge 0$ 使得：
1. $y^T A ge 0 implies egin{pmatrix} 2y_1+y_2 & y_1+2y_2 end{pmatrix} ge egin{pmatrix} 0 & 0 end{pmatrix}$ （总是满足的，因为 $y_1, y_2 ge 0$）
2. $y^T b < 0 implies egin{pmatrix} y_1 & y_2 end{pmatrix} egin{pmatrix} 2 \ 1 end{pmatrix} < 0 implies 2y_1 + y_2 < 0$
注意： 这里我把 Farkas 引理的条件简化了。更严谨地说，Farkas 引理关注的是 方程组 $Ax = b$ 是否有非负解。而我们的农场问题是 不等式组 $Ax le b$ 是否有非负解。这需要稍作转化。
Farkas 引理的另一种标准形式是：
对于矩阵 $A$ 和向量 $b$，以下两个命题是等价的：
1. 方程组 $Ax = b$ 存在非负解 $x ge 0$。
2. 对于任意满足 $y^T A ge 0$ 的向量 $y ge 0$，都有 $y^T b ge 0$。
我们想解决的是 $Ax le b$ 的非负解问题。
我们可以将其转化为等式问题：
令 $s = egin{pmatrix} s_1 \ s_2 end{pmatrix} ge 0$ 为松弛变量。
那么 $Ax le b$ 等价于 $Ax + s = b$，其中 $x ge 0, s ge 0$。
我们可以写成这样的形式：
$egin{pmatrix} A & I end{pmatrix} egin{pmatrix} x \ s end{pmatrix} = b$, 其中 $egin{pmatrix} x \ s end{pmatrix} ge 0$。
设 $M = egin{pmatrix} A & I end{pmatrix}$ 和 $z = egin{pmatrix} x \ s end{pmatrix}$。
那么我们有 $Mz = b$, $z ge 0$ 的解存在性问题。
根据 Farkas 引理（第一种表述）：
存在 $z ge 0$ 使得 $Mz = b$ 的充要条件是：对于任意满足 $y^T M ge 0$ 的向量 $y ge 0$，都有 $y^T b ge 0$。
这里的 $y$ 是一个（可能包含负数的）向量，其长度与 $b$ 相同。但是，当我们将问题转化为寻找 非负 的 $y$ 时，Farkas 引理又有更直观的表述。
最关键的理解点在于： Farkas 引理提供了一种“分离超平面”的几何解释。它说明了，如果一个点集（由线性不等式定义）是“有界的”或者说“不包含无限延伸”，那么它要么是“有界的且包含原点”，要么一定存在一个超平面，将原点与这个点集“分离”。
回到农场主例子，我们想知道的是：
“是否存在一个非负的种植方案 $(x_1, x_2)$，使得你能利用你的资源（不超过 6 个单位劳动力，不超过 5 个单位化肥）来种植总共 4 亩地？”
我们把问题转化为：
找到 $x_1 ge 0, x_2 ge 0$ 使得：
$2x_1 + x_2 le 6$
$x_1 + 2x_2 le 5$
$x_1 x_2 le 4$ （即 $x_1 + x_2 ge 4$ 的否定形式）
现在，我们来看看 Farkas 引理的这个版本：
对于矩阵 $A$ 和向量 $b$，以下两个命题等价：
1. 方程组 $Ax = b$ 有非负解 $x ge 0$。
2. 对于所有 $y ge 0$ 满足 $y^T A ge 0$ 的情况，必有 $y^T b ge 0$。
我们可以重新构造我们的问题，使其符合这个形式。
假设我们想测试的是：是否存在 $x ge 0$ 使得 $Ax le b$ 且 $c^T x ge K$。
这等价于寻找非负的 $x$ 满足：
$egin{pmatrix} A \ c^T end{pmatrix} x le egin{pmatrix} b \ K end{pmatrix}$
或者说，存在 $x ge 0$ 使得：
$egin{pmatrix} 2 & 1 \ 1 & 2 \ 1 & 1 end{pmatrix} egin{pmatrix} x_1 \ x_2 end{pmatrix} le egin{pmatrix} 6 \ 5 \ 4 end{pmatrix}$
令 $A' = egin{pmatrix} 2 & 1 \ 1 & 2 \ 1 & 1 end{pmatrix}$ 和 $b' = egin{pmatrix} 6 \ 5 \ 4 end{pmatrix}$。
Farkas 引理的结论是：不存在非负解 $x$ 满足 $A'x le b'$ 的充要条件是，存在 $y' ge 0$ 使得 $(y')^T A' ge 0$ 并且 $(y')^T b' < 0$。
我们来找这个 $y' = egin{pmatrix} y_1 \ y_2 \ y_3 end{pmatrix} ge 0$。
$(y')^T A' = egin{pmatrix} y_1 & y_2 & y_3 end{pmatrix} egin{pmatrix} 2 & 1 \ 1 & 2 \ 1 & 1 end{pmatrix} = egin{pmatrix} 2y_1+y_2y_3 & y_1+2y_2y_3 end{pmatrix}$
我们要求这个向量非负：
$2y_1 + y_2 y_3 ge 0$
$y_1 + 2y_2 y_3 ge 0$
而 $(y')^T b' < 0$ 是：
$y_1 cdot 6 + y_2 cdot 5 + y_3 cdot (4) < 0$
$6y_1 + 5y_2 4y_3 < 0$
现在，我们就是要看，是否能找到这样的 $y_1, y_2, y_3 ge 0$ 来满足这三个条件。
我们可以尝试一些组合。
比如，如果取 $y_3 = 0$，那么条件就变成了：
$2y_1 + y_2 ge 0$ (总是满足的)
$y_1 + 2y_2 ge 0$ (总是满足的)
$6y_1 + 5y_2 < 0$
然而，由于 $y_1, y_2 ge 0$， $6y_1 + 5y_2$ 永远是非负的，不可能小于零。这说明 $y_3=0$ 的情况无法证明“不可能”。
那么，我们是不是可以取 $y_3 > 0$ 来“抵消”前面的项？
考虑一个例子：
令 $y_1 = 1, y_2 = 1, y_3 = 3$。
此时 $y' = egin{pmatrix} 1 \ 1 \ 3 end{pmatrix} ge 0$。
检查 $(y')^T A' ge 0$:
$2(1) + 1 3 = 0 ge 0$ (满足)
$1 + 2(1) 3 = 0 ge 0$ (满足)
检查 $(y')^T b' < 0$:
$6(1) + 5(1) 4(3) = 6 + 5 12 = 11 12 = 1 < 0$ (满足)
Bingo！我们找到了一个 $y' ge 0$ 满足 $(y')^T A' ge 0$ 并且 $(y')^T b' < 0$。
根据 Farkas 引理，这就证明了：
不存在非负解 $x$ 使得 $A'x le b'$。
换句话说，不存在非负的种植方案 $(x_1, x_2)$，能够同时满足：
劳动力约束 ($2x_1 + x_2 le 6$)
化肥约束 ($x_1 + 2x_2 le 5$)
目标产量（$x_1 + x_2 ge 4$）
这就是 Farkas 引理的强大之处。它提供了一种 “对偶证明” 的方式，用来证明一个线性系统是不可行的。我们没有直接找到那个不可能存在的 $x$，而是通过找到一个“证书”（向量 $y$），来证明它的不存在。
总结 Farkas 引理的核心思想
核心问题： 判断一个线性方程组或不等式组是否有非负解。
关键工具： Farkas 引理提供了一种“对偶”的视角来解决这个问题。
“不可能”的证明： 如果一个系统没有非负解，那么一定存在一个特殊的“权重向量”（$y$）来证明它的“不可行性”。这个权重向量具有两个关键性质：
1. 它使得“资源需求”的加权和非负（$y^T A ge 0$）。这可以理解为，即使赋予资源“影子价格”，每种“产出”（或行动）的净价值也不能为负。
2. 它使得“可用资源”的加权和为负（$y^T b < 0$）。这就像一个“紧箍咒”，用这些影子价格衡量，你拥有的总资源竟然是“亏本”的。
“可行”的保证： 反之，如果找不到这样的“证明向量” $y$，那么原系统就一定有非负解。
为什么 Farkas 引理如此重要？
1. 理论基石： 它是许多线性规划对偶理论的基础，对理解对偶问题、最优性条件至关重要。
2. 判定可行性： 在设计算法或分析系统时，能够快速判断一个系统是否可解，避免浪费计算资源。
3. 敏感性分析： 其中的“影子价格” $y$ 在经济学和运筹学中有实际意义，代表了对资源变化的敏感度。
4. 普适性： Farkas 引理的思想可以推广到更一般的问题，例如凸优化。
理解 Farkas 引理，就像掌握了一门“反证法”的利器。当你面对一个看似复杂的线性系统时，不妨想想：能否找到一个“聪明”的加权组合来证明它无解？这正是 Farkas 引理的魅力所在。它将一个直接求解的难题，转化为了一个证明题，而且这个证明题往往比原问题更容易处理。
Farkas 引理，这个名字在最优化、控制论和图论等领域中常常出现，却也常常让初学者感到一丝晦涩。它究竟说了什么？为何如此重要？今天，我们就来一层层地剥开它神秘的面纱，力求用最直观、最接地气的方式，让你真正理解这个强大的数学工具。
想象一下，我们不是在枯燥地学习抽象的数学公式，而是在解决一个现实世界的问题。
从一个简单的场景出发
假设你是一位农场主，你拥有两块土地，一块专门种玉米，另一块专门种小麦。每种作物都需要一定的劳动力和化肥。
玉米： 每亩需要 2 个单位的劳动力， 1 个单位的化肥。
小麦： 每亩需要 1 个单位的劳动力， 2 个单位的化肥。
你现在拥有总共 6 个单位的劳动力 和 5 个单位的化肥。
你希望最大化你的总产量（假设每亩玉米产量是 1，每亩小麦产量也是 1，所以我们其实就是在最大化种植面积）。
你可能会列出这样的问题：
设 $x_1$ 是你种植玉米的亩数， $x_2$ 是你种植小麦的亩数。
你要满足的约束是：
劳动力约束：$2x_1 + x_2 le 6$ （你不能用超过 6 个单位的劳动力）
化肥约束：$x_1 + 2x_2 le 5$ （你不能用超过 5 个单位的化肥）
你的目标是最大化：$x_1 + x_2$
而且，你不能种植负数亩数：$x_1 ge 0, x_2 ge 0$
这是一个典型的线性规划问题。
现在，我们换个角度来思考。假设有一个神秘的“观察者”，他并不知道你实际的种植计划（$x_1, x_2$），但他知道你拥有的资源（劳动力和化肥），以及每种作物对这些资源的需求。
观察者想要判断一个“假设”：是否存在一个非负的种植组合 ($x_1, x_2$)，能够让你实现一个“目标产量”（比如，你想知道是否能种植总共 4 亩地）。
如果你的目标是种植 4 亩地，也就是说，你想找到满足：
$x_1 + x_2 = 4$
$2x_1 + x_2 le 6$
$x_1 + 2x_2 le 5$
$x_1 ge 0, x_2 ge 0$
的 $(x_1, x_2)$。
Farkas 引理登场：从“可行性”到“不可能”的判断
Farkas 引理提供的就是一种判断这种“假设”是否成立的强大工具，但它并非直接给出那个种植组合，而是从一个 “对偶” 的角度来衡量。
Farkas 引理最常见的形式之一是这样说的：
对于矩阵 $A$ 和向量 $b$，方程组 $Ax = b$ 存在非负解 $x ge 0$ 的充要条件是：对于任意满足 $y^T A ge 0$ 的向量 $y ge 0$，都有 $y^T b ge 0$。
这听起来还是有点抽象，我们把它和你刚才的农场主问题联系起来。
先将你的问题改写成更标准的矩阵形式：
目标是找到 $x = egin{pmatrix} x_1 \ x_2 end{pmatrix}$ 满足：
$egin{pmatrix} 2 & 1 \ 1 & 2 end{pmatrix} egin{pmatrix} x_1 \ x_2 end{pmatrix} le egin{pmatrix} 6 \ 5 end{pmatrix}$
$x ge 0$
我们假设你想达到的目标是 $c^T x ge K$，例如 $1 cdot x_1 + 1 cdot x_2 ge 4$。
Farkas 引理的核心思想是：如果你无法实现一个目标，那么一定存在一个“加权组合”的方式来证明你的“失败”。
让我们回到农场主场景。你有一个计划，你想看看能不能种出 4 亩地。
观察者可以这样思考：
“如果我的农场主朋友真的能够种出 4 亩地，那么他的计划 $(x_1, x_2)$ 必定满足：
$x_1 + x_2 = 4$
$2x_1 + x_2 le 6$
$x_1 + 2x_2 le 5$
$x_1 ge 0, x_2 ge 0$
现在，我能不能找到一种‘组合’这三个不等式的方法，来证明他这个计划是不可能的呢？”
这里的“组合”就是 Farkas 引理中的“向量 $y$”。
设你想达到的目标是找到一个非负的 $x$ 使得：
$Ax le b$
其中 $A = egin{pmatrix} 2 & 1 \ 1 & 2 end{pmatrix}$ (资源需求矩阵), $b = egin{pmatrix} 6 \ 5 end{pmatrix}$ (可用资源向量)。
我们想要看的是，是否存在 $x ge 0$ 使得 $c^T x ge K$（例如 $c = egin{pmatrix} 1 \ 1 end{pmatrix}$, $K = 4$）。
Farkas 引理的另一种表述方式会更贴近我们的例子：
对于矩阵 $A$ 和向量 $b$，以下两个命题是等价的：
1. 存在 $x ge 0$ 使得 $Ax le b$。 （存在一个可行的种植计划）
2. 对于任意满足 $y^T A ge 0$ 的向量 $y ge 0$，都有 $y^T b ge 0$。 （这句比较绕，我们后面解释）
更实用、更容易理解的版本是关于“不可行性”的：
对于矩阵 $A$ 和向量 $b$，以下两个命题是等价的：
1. 不存在 $x ge 0$ 使得 $Ax le b$。 （即，无论如何都无法满足所有约束）
2. 存在 $y ge 0$ 使得 $y^T A ge 0$ 并且 $y^T b < 0$。 （存在一个“反证组合”）
这第二条就是 Farkas 引理的核心！
让我们用农场主的问题来解释它：
“如果我的农场主朋友无论如何都无法找到一个种植方案来满足所有资源约束，那么一定存在一个‘资源配额’（向量 $y ge 0$）的分配方式，能够证明他的计划是不可能的。”
这里的“资源配额” $y = egin{pmatrix} y_1 \ y_2 end{pmatrix}$ 意味着：
$y_1$：你分配给“劳动力”这个资源的“权重”或“影子价格”。
$y_2$：你分配给“化肥”这个资源的“权重”或“影子价格”。
条件 $y ge 0$ 意味着这些权重不能是负的，这是符合常理的。
条件 $y^T A ge 0$ 意味着：
$y_1 cdot 2 + y_2 cdot 1 ge 0$ （劳动力权重 玉米劳动力需求 + 化肥权重 玉米化肥需求 $ge 0$）
$y_1 cdot 1 + y_2 cdot 2 ge 0$ （劳动力权重 小麦劳动力需求 + 化肥权重 小麦化肥需求 $ge 0$）
这其实是在说，你找到的这个“权重组合” $y$，对于每一种作物（即每一列 $A$）来说，其“资源需求的总权重”都是非负的。换句话说，你不能找到一个权重组合，让两种作物都“有利可图”（即资源需求的总权重为负）。
而 Farkas 引理的关键在于 $y^T b < 0$。
将 $y^T b$ 展开：
$y_1 cdot 6 + y_2 cdot 5 < 0$
这意味着，用你找到的那个“资源配额” $y$ 来衡量你的可用资源的总价值是负的。
所以，Farkas 引理的第二条表述可以这样理解：
“如果不存在一个可行的种植计划（$Ax le b, x ge 0$），那么一定存在一组非负的‘影子价格’（$y ge 0$），使得：
1. 这个‘影子价格’组合对每种作物（的资源需求）都没有‘好处’（$y^T A ge 0$）。 也就是说，如果种植一单位的玉米，其资源总价值（按影子价格计算）是正的，种植一单位的小麦，其资源总价值也是正的。换句话说，这两种作物都“不值得”你去种植。
2. 然而，用这组‘影子价格’来衡量你拥有的总资源，其价值却是负的（$y^T b < 0$）。
这听起来是不是有点矛盾？
让我们回到农场主例子，假设你想种出 4 亩地，即目标是 $x_1+x_2 ge 4$。
你的约束是 $A = egin{pmatrix} 2 & 1 \ 1 & 2 end{pmatrix}$, $b = egin{pmatrix} 6 \ 5 end{pmatrix}$。
我们来看看是否能找到一个 $y ge 0$ 使得 $y^T A ge 0$ 且 $y^T b < 0$。
设 $y = egin{pmatrix} y_1 \ y_2 end{pmatrix}$，其中 $y_1, y_2 ge 0$。
$y^T A = egin{pmatrix} y_1 & y_2 end{pmatrix} egin{pmatrix} 2 & 1 \ 1 & 2 end{pmatrix} = egin{pmatrix} 2y_1+y_2 & y_1+2y_2 end{pmatrix}$
我们要让 $2y_1+y_2 ge 0$ 且 $y_1+2y_2 ge 0$。由于 $y_1, y_2 ge 0$，这两个条件总是满足的。
现在看 $y^T b < 0$:
$y_1 cdot 6 + y_2 cdot 5 < 0$
问题来了！ 由于我们要求 $y_1 ge 0$ 且 $y_2 ge 0$，那么 $6y_1 + 5y_2$ 永远是大于等于零的。它不可能小于零！
这意味着什么？
这意味着，我们找不到一个 $y ge 0$ 使得 $y^T b < 0$。
根据 Farkas 引理的第二条表述：如果找不到 $y ge 0$ 使得 $y^T b < 0$（同时满足 $y^T A ge 0$），那么就一定存在 $x ge 0$ 使得 $Ax le b$。
换句话说，根据 Farkas 引理，我们证明了：存在一个可行的种植方案，让你能够满足资源约束。
更具体的例子：证明“不可能”
现在，假设你拥有 2 个单位的劳动力 和 1 个单位的化肥。
你的资源限制是 $b = egin{pmatrix} 2 \ 1 end{pmatrix}$。
你想看看是否能种出 3 亩地，即目标是 $x_1+x_2 ge 3$。
约束：
$2x_1 + x_2 le 2$
$x_1 + 2x_2 le 1$
$x_1 ge 0, x_2 ge 0$
Farkas 引理说：如果不可能找到这样的 $x$，那么一定存在 $y ge 0$ 使得 $y^T A ge 0$ 且 $y^T b < 0$。
我们来找找看这个 $y$。
$A = egin{pmatrix} 2 & 1 \ 1 & 2 end{pmatrix}$, $b = egin{pmatrix} 2 \ 1 end{pmatrix}$
我们需要找 $y = egin{pmatrix} y_1 \ y_2 end{pmatrix} ge 0$ 使得：
1. $y^T A ge 0 implies egin{pmatrix} 2y_1+y_2 & y_1+2y_2 end{pmatrix} ge egin{pmatrix} 0 & 0 end{pmatrix}$ （总是满足的，因为 $y_1, y_2 ge 0$）
2. $y^T b < 0 implies egin{pmatrix} y_1 & y_2 end{pmatrix} egin{pmatrix} 2 \ 1 end{pmatrix} < 0 implies 2y_1 + y_2 < 0$
注意： 这里我把 Farkas 引理的条件简化了。更严谨地说，Farkas 引理关注的是 方程组 $Ax = b$ 是否有非负解。而我们的农场问题是 不等式组 $Ax le b$ 是否有非负解。这需要稍作转化。
Farkas 引理的另一种标准形式是：
对于矩阵 $A$ 和向量 $b$，以下两个命题是等价的：
1. 方程组 $Ax = b$ 存在非负解 $x ge 0$。
2. 对于任意满足 $y^T A ge 0$ 的向量 $y ge 0$，都有 $y^T b ge 0$。
我们想解决的是 $Ax le b$ 的非负解问题。
我们可以将其转化为等式问题：
令 $s = egin{pmatrix} s_1 \ s_2 end{pmatrix} ge 0$ 为松弛变量。
那么 $Ax le b$ 等价于 $Ax + s = b$，其中 $x ge 0, s ge 0$。
我们可以写成这样的形式：
$egin{pmatrix} A & I end{pmatrix} egin{pmatrix} x \ s end{pmatrix} = b$, 其中 $egin{pmatrix} x \ s end{pmatrix} ge 0$。
设 $M = egin{pmatrix} A & I end{pmatrix}$ 和 $z = egin{pmatrix} x \ s end{pmatrix}$。
那么我们有 $Mz = b$, $z ge 0$ 的解存在性问题。
根据 Farkas 引理（第一种表述）：
存在 $z ge 0$ 使得 $Mz = b$ 的充要条件是：对于任意满足 $y^T M ge 0$ 的向量 $y ge 0$，都有 $y^T b ge 0$。
这里的 $y$ 是一个（可能包含负数的）向量，其长度与 $b$ 相同。但是，当我们将问题转化为寻找 非负 的 $y$ 时，Farkas 引理又有更直观的表述。
最关键的理解点在于： Farkas 引理提供了一种“分离超平面”的几何解释。它说明了，如果一个点集（由线性不等式定义）是“有界的”或者说“不包含无限延伸”，那么它要么是“有界的且包含原点”，要么一定存在一个超平面，将原点与这个点集“分离”。
回到农场主例子，我们想知道的是：
“是否存在一个非负的种植方案 $(x_1, x_2)$，使得你能利用你的资源（不超过 6 个单位劳动力，不超过 5 个单位化肥）来种植总共 4 亩地？”
我们把问题转化为：
找到 $x_1 ge 0, x_2 ge 0$ 使得：
$2x_1 + x_2 le 6$
$x_1 + 2x_2 le 5$
$x_1 x_2 le 4$ （即 $x_1 + x_2 ge 4$ 的否定形式）
现在，我们来看看 Farkas 引理的这个版本：
对于矩阵 $A$ 和向量 $b$，以下两个命题等价：
1. 方程组 $Ax = b$ 有非负解 $x ge 0$。
2. 对于所有 $y ge 0$ 满足 $y^T A ge 0$ 的情况，必有 $y^T b ge 0$。
我们可以重新构造我们的问题，使其符合这个形式。
假设我们想测试的是：是否存在 $x ge 0$ 使得 $Ax le b$ 且 $c^T x ge K$。
这等价于寻找非负的 $x$ 满足：
$egin{pmatrix} A \ c^T end{pmatrix} x le egin{pmatrix} b \ K end{pmatrix}$
或者说，存在 $x ge 0$ 使得：
$egin{pmatrix} 2 & 1 \ 1 & 2 \ 1 & 1 end{pmatrix} egin{pmatrix} x_1 \ x_2 end{pmatrix} le egin{pmatrix} 6 \ 5 \ 4 end{pmatrix}$
令 $A' = egin{pmatrix} 2 & 1 \ 1 & 2 \ 1 & 1 end{pmatrix}$ 和 $b' = egin{pmatrix} 6 \ 5 \ 4 end{pmatrix}$。
Farkas 引理的结论是：不存在非负解 $x$ 满足 $A'x le b'$ 的充要条件是，存在 $y' ge 0$ 使得 $(y')^T A' ge 0$ 并且 $(y')^T b' < 0$。
我们来找这个 $y' = egin{pmatrix} y_1 \ y_2 \ y_3 end{pmatrix} ge 0$。
$(y')^T A' = egin{pmatrix} y_1 & y_2 & y_3 end{pmatrix} egin{pmatrix} 2 & 1 \ 1 & 2 \ 1 & 1 end{pmatrix} = egin{pmatrix} 2y_1+y_2y_3 & y_1+2y_2y_3 end{pmatrix}$
我们要求这个向量非负：
$2y_1 + y_2 y_3 ge 0$
$y_1 + 2y_2 y_3 ge 0$
而 $(y')^T b' < 0$ 是：
$y_1 cdot 6 + y_2 cdot 5 + y_3 cdot (4) < 0$
$6y_1 + 5y_2 4y_3 < 0$
现在，我们就是要看，是否能找到这样的 $y_1, y_2, y_3 ge 0$ 来满足这三个条件。
我们可以尝试一些组合。
比如，如果取 $y_3 = 0$，那么条件就变成了：
$2y_1 + y_2 ge 0$ (总是满足的)
$y_1 + 2y_2 ge 0$ (总是满足的)
$6y_1 + 5y_2 < 0$
然而，由于 $y_1, y_2 ge 0$， $6y_1 + 5y_2$ 永远是非负的，不可能小于零。这说明 $y_3=0$ 的情况无法证明“不可能”。
那么，我们是不是可以取 $y_3 > 0$ 来“抵消”前面的项？
考虑一个例子：
令 $y_1 = 1, y_2 = 1, y_3 = 3$。
此时 $y' = egin{pmatrix} 1 \ 1 \ 3 end{pmatrix} ge 0$。
检查 $(y')^T A' ge 0$:
$2(1) + 1 3 = 0 ge 0$ (满足)
$1 + 2(1) 3 = 0 ge 0$ (满足)
检查 $(y')^T b' < 0$:
$6(1) + 5(1) 4(3) = 6 + 5 12 = 11 12 = 1 < 0$ (满足)
Bingo！我们找到了一个 $y' ge 0$ 满足 $(y')^T A' ge 0$ 并且 $(y')^T b' < 0$。
根据 Farkas 引理，这就证明了：
不存在非负解 $x$ 使得 $A'x le b'$。
换句话说，不存在非负的种植方案 $(x_1, x_2)$，能够同时满足：
劳动力约束 ($2x_1 + x_2 le 6$)
化肥约束 ($x_1 + 2x_2 le 5$)
目标产量（$x_1 + x_2 ge 4$）
这就是 Farkas 引理的强大之处。它提供了一种 “对偶证明” 的方式，用来证明一个线性系统是不可行的。我们没有直接找到那个不可能存在的 $x$，而是通过找到一个“证书”（向量 $y$），来证明它的不存在。
总结 Farkas 引理的核心思想
核心问题： 判断一个线性方程组或不等式组是否有非负解。
关键工具： Farkas 引理提供了一种“对偶”的视角来解决这个问题。
“不可能”的证明： 如果一个系统没有非负解，那么一定存在一个特殊的“权重向量”（$y$）来证明它的“不可行性”。这个权重向量具有两个关键性质：
1. 它使得“资源需求”的加权和非负（$y^T A ge 0$）。这可以理解为，即使赋予资源“影子价格”，每种“产出”（或行动）的净价值也不能为负。
2. 它使得“可用资源”的加权和为负（$y^T b < 0$）。这就像一个“紧箍咒”，用这些影子价格衡量，你拥有的总资源竟然是“亏本”的。
“可行”的保证： 反之，如果找不到这样的“证明向量” $y$，那么原系统就一定有非负解。
为什么 Farkas 引理如此重要？
1. 理论基石： 它是许多线性规划对偶理论的基础，对理解对偶问题、最优性条件至关重要。
2. 判定可行性： 在设计算法或分析系统时，能够快速判断一个系统是否可解，避免浪费计算资源。
3. 敏感性分析： 其中的“影子价格” $y$ 在经济学和运筹学中有实际意义，代表了对资源变化的敏感度。
4. 普适性： Farkas 引理的思想可以推广到更一般的问题，例如凸优化。
理解 Farkas 引理，就像掌握了一门“反证法”的利器。当你面对一个看似复杂的线性系统时，不妨想想：能否找到一个“聪明”的加权组合来证明它无解？这正是 Farkas 引理的魅力所在。它将一个直接求解的难题，转化为了一个证明题，而且这个证明题往往比原问题更容易处理。
网友意见
Farkas引理算是凸优化中经典和常用的引理了，可以用在很多地方（例如证明KKT条件），最近在看最优运输问题和Wasserstein距离的一些东西，中间对偶性的证明过程中用到了Farkas引理，顺路上来回答一发。
原引理长这样：
设 ， ，那么以下两个论断有且只有一个是对的：
（1）存在 ，使得 ，且 。
（2）存在 ，使得 ，且 。
乍一看容易懵逼，都是些什么鬼啊，但是只要了解这个引理得出的来龙去脉，结合一些几何上面的直观认识，你会发现，上述引理描述的事实几乎是显而易见的。
注意到两个事实：
事实一和锥有关：
是锥（cone），当任取 ， ，有 。
被称为是凸锥（convex cone），当任取 ， ，有 。当然，不难论证它是锥而且是凸集（convex set），且选择不止两个向量和对应的正系数上述事实也是满足的。
有了以上认识，了解一个概念叫conic hull，一个集合 的conic hull被定义为：
可以看到，这是一个由 中的向量张成的一个凸锥，长成下图这样。
事实二是点和凸集的分离定理，它可以认为是两个凸集可以被超平面分开的推论（Corollary）：
假设 是一个闭凸集，如果 ，那么存在一个超平面 能够把 和 分开。换句话说就是存在一个非零向量 和 ，满足对于所有 ，有 同时 。
直观上面来说，就是总能在空间中找到一个超平面，平面方程参数是 和 ，使得 在平面这边，闭凸集 在平面那边，如下图所示（盗图，侵删）。
特别的，如果 不仅是凸集，还是事实一中所提到的凸锥，我们可以找到一个过原点的平面，分开凸锥和它外面的一个点，也就是说如果 是一个凸锥， ，存在非零 满足对于所有的 ，有 ，且 。
根据上面两个事实，我们就可以很直观的理解farkas引理在说些什么了，注意这是直观的说明，并不是严谨的证明。
我们把矩阵 的列空间写出来，其实就是 n个m维的向量： ，根据事实一，这些向量前面加权非负系数组合出来的点构成的集合就是一个凸锥，是集合 的conic hull。
对于向量 ，只可能存在两种互斥情况：（1） 在这个凸锥里。（2） 在这个凸锥外。
如果情况（1）成立，说明 属于的conic hull，所以肯定能够找到一组非负的 使得 。这就也是定理中的情况（1），直观感受如下面左图。
反之如果情况（2）成立， 在凸锥外面，根据事实二，肯定能够找到一个过原点的超平面，使得 在一边，凸锥在另外一边。这个超平面法向量为 ，因为 都在凸锥里面，所以 ， ，...， ，合并写成矩阵乘向量形式就是 。且此时 。如上面右图所示。
题外话：
证明Farkas引理的话，大致步骤基本是这样：（1）证明有限向量集合的conic hull是闭凸集。（2）利用超平面分离定理，结合凸锥是包含原点的闭凸集，加上一点反证法的论证，得到存在过原点的超平面分离该凸锥外一点和凸锥。（3）证明引理本身。
具体证明有时间再补上吧～
类似的话题
-
拨开迷雾，理解 Farkas 引理Farkas 引理，这个名字在最优化、控制论和图论等领域中常常出现，却也常常让初学者感到一丝晦涩。它究竟说了什么？为何如此重要？今天，我们就来一层层地剥开它神秘的面纱，力求用最直观、最接地气的方式，让你真正理解这个强大的数学工具。想象一下，我们不是在枯燥地学习抽象的............. -
这句话“文官的衣服上绣的是禽，武官的衣服上绣的是兽。披上了这身皮，我们哪一个不是衣冠禽兽”融合了历史、文化、隐喻和讽刺，需要从多个层面进行解析： 一、历史背景与服饰象征1. 古代官服制度 在中国历史上，官服的纹饰（如禽鸟、兽类）是等级制度和身份象征的重要标志。 文官：常以“禽”为纹.............
-
“自称迪士尼在逃公主”的现象在网络上出现后，引发了广泛讨论。这一说法通常指一些女性在社交媒体、论坛或网络社区中自称是“迪士尼公主”，并可能涉及身份扮演、文化认同、心理需求等多重层面。以下从多个角度详细分析这一现象的可能内涵和背景： 一、文化符号的再诠释：迪士尼公主的象征意义1. 迪士尼公主的原始形象.............
-
自由主义和新自由主义是两种重要的思想体系，它们在政治哲学、经济学和社会政策等领域具有深远的影响。以下是对这两个概念的详细解析： 一、自由主义的定义与核心特征自由主义（Liberalism）是一种以个人自由、法治、民主和理性为价值基础的政治哲学思想体系，其核心在于保障个体权利和限制国家权力。自由主义的.............
-
无政府主义（Anarchism）是一种深刻批判国家权力、追求个体自由与社会平等的政治哲学和实践运动。它并非主张“混乱”或“无序”，而是反对一切形式的强制性权威，尤其是国家对个人生活的控制。以下从多个维度深入解析这一复杂的思想体系： 一、核心定义与本质特征1. 对国家的彻底否定 无政府主义者认.............
-
“爱国家不等于爱朝廷”这句话在理解中国古代政治和文化时非常重要。它揭示了国家与政权（即朝廷）之间的区别，以及臣民对这两者的情感和责任的不同层面。要理解这句话，我们需要先拆解其中的概念： 国家（Guó Jiā）： 在古代，我们通常将其理解为国家的疆土、人民、文化、民族认同和长期的历史延续。它是根植.............
-
理解中国人民银行工作论文中提到的“东南亚国家掉入中等收入陷阱的原因之一是‘文科生太多’”这一论断，需要从多个层面进行深入分析，因为这是一个相对复杂且具有争议性的议题。下面我将尽量详细地解释其背后的逻辑和可能含义：一、 背景：中等收入陷阱首先，我们需要理解什么是“中等收入陷阱”。 定义： 中等收入.............
-
郭主席对房地产的表述“不希望房地产剧烈波动”可以从多个层面来理解，这背后反映了他对中国经济稳定和健康发展的深切关切。要详细理解这一点，我们需要从房地产在中国经济中的地位、波动可能带来的影响、以及“不剧烈波动”的具体含义等角度进行分析。一、 房地产在中国经济中的特殊地位：首先，理解为什么房地产会引起如.............
-
如何理解科幻小说《时间的二分法》？ 详细解读科幻小说《时间的二分法》（英文原名：The Time Machine），由英国著名作家赫伯特·乔治·威尔斯（H.G. Wells）于1895年创作，是科幻文学史上的经典之作。这部小说不仅为我们描绘了一个令人着迷的未来世界，更通过其深刻的社会寓言和哲学思考，.............
-
尹建莉老师关于“延迟满足是鬼话，孩子要及时满足”的观点，确实在教育界引发了不少讨论。要理解她的观点，我们需要深入探讨她为什么会提出这样的论断，以及她所强调的“及时满足”的真正含义。首先，我们来拆解一下“延迟满足”这个概念及其传统理解。传统理解的“延迟满足”：延迟满足（Delayed Gratific.............
-
理解外交部发言人陆慷的说法，即“《中英联合声明》作为一个历史文件，不再具有任何现实意义”，需要从几个关键角度来解读：1. 历史文件的定义与性质： 历史文件是过去的产物： 陆慷的表述首先强调了《中英联合声明》的“历史文件”属性。这意味着它是在特定历史时期、基于当时国际政治格局和两国关系背景下签署的.............
-
杨振宁先生作为一位享誉世界的物理学家，他关于中美教育的评论引起了广泛关注和讨论。理解他的话需要从多个角度进行深入剖析，包括他所处的时代背景、他对教育本质的理解、以及他观察到的中美教育体系的差异。一、 杨振宁先生评论的时代背景与个人经历：首先，要理解杨振宁先生的话，必须考虑到他所处的时代背景和他的个人.............
-
“中国是发达国家的粉碎机”这个说法，虽然带有一定的情绪化和夸张色彩，但其核心要表达的是：中国凭借其独特的经济模式、庞大的市场规模、强大的制造能力和不断进步的科技创新，对传统发达国家在经济和产业领域构成了前所未有的挑战，并在一定程度上“粉碎”了它们原有的竞争优势和发展路径。为了详细理解这一说法，我们可.............
-
“爱国主义是流氓的最后一块遮羞布”这句话，最早出自塞缪尔·约翰逊（Samuel Johnson），一位杰出的18世纪英国作家和评论家。这句话的含义深刻且复杂，通常被用来讽刺和批评那些打着爱国旗号，但实际上在追求个人利益、制造分裂或煽动仇恨的人。要理解这句话，我们可以从以下几个层面来深入剖析：1. 字.............
-
“Control is Dead”这句话的含义非常丰富且具有多层次的解读，它不是一个简单的字面陈述，而是对当前社会、技术、政治、经济等领域中一种普遍的失控感、权力分散化、个体自主性增强以及传统权威式微的深刻反映。要理解这句话，我们需要从不同的角度去剖析：一、 字面含义与引申含义： 字面含义： 最.............
-
“小孩子才分对错，成年人只看利弊”这句话，乍一听可能有些功利甚至冷酷，但深入剖析，它揭示了一种关于成长、认知和处世态度的深刻变化。这句话并不是说成年人完全泯灭了道德感，而是强调在复杂的社会现实中，判断的侧重点会发生微妙而重要的转移。我们来详细地理解这句话的各个层面：一、 “小孩子才分对错”：儿童的认.............
-
这句话以一种诗意且深刻的方式，阐述了科学与宗教（在此特指佛学）在追求真理和理解宇宙本质上可能存在的殊途同归。要理解它，我们可以从几个层面进行剖析：一、 表象的理解：科学探索的艰难与佛学智慧的超前 科学探索的“爬山”隐喻： 科学研究是一个漫长、艰辛、充满挑战的过程。科学家们如同登山者，需要克服无数.............
-
“Don't judge”（别评判）这句简单的话语，却蕴含着深刻的道理，它不仅仅是一个简单的行为准则，更是一种生活态度和哲学。要理解它，需要从多个层面去深入剖析。核心含义：停止对他人进行预设的、带有偏见的、负面判断。“评判”（judge）这个词在中文里可以有几种理解： 审判（legal cont.............
-
这句话， "对他们的伟大人物忘恩负义，这是伟大民族的标志"，是一句富有争议且深刻的论断。要理解它，我们需要从多个层面进行剖析，包括字面含义、潜在的哲学思想、历史现实以及它可能带来的积极或消极影响。核心解读：反思与进步的动力从最核心的角度来看，这句话并非在鼓吹忘恩负义的行为本身是值得赞扬的，而是指向了.............
-
「看山是山，看山不是山，看山还是山」，这句禅语，通常被称为“禅宗三境界”或者“悟道三阶段”，意境深远，历久弥新。它并非指代实际的山，而是用“山”这个意象来比喻一个人对事物、对真理、对自我的认知过程。理解这三层境界，能帮助我们更深刻地认识自己，认识世界。下面我将详细阐述这三层境界的含义：第一层境界：看.............
本站所有内容均为互联网搜索引擎提供的公开搜索信息，本站不存储任何数据与内容，任何内容与数据均与本站无关，如有需要请联系相关搜索引擎包括但不限于百度，google,bing,sogou 等
© 2025 tinynews.org All Rights Reserved. 百科问答小站 版权所有