从规范形推广到任意形式

上一讲只对规范形（全部约束是 $Ax\le b$、全部变量非负）给出了对偶。真实问题里约束方向混杂、变量有正有负，所以这一讲先补上一般规则，再证明两个核心定理：互补松弛与强对偶。

时间轴

三种可能的情形

任何线性规划恰属于下列之一：

1. 有有限最优值：存在可行解，且最优值有限。
2. 不可行：可行域为空，例如 $x_1\ge5$ 且 $x_1\le3$。
3. 无界：可行，但目标函数可以任意大（或任意小），例如 $\max x$ 且 $x\ge3$。

由弱对偶立刻得到两个推论：

• 若原问题无界，则对偶不可行。否则任取一个对偶可行解 $y$，它的值 $b^Ty$ 就是原问题上界，与原问题无界矛盾。
• 若对偶无界，则原问题不可行。

原问题与对偶同时不可行也是可能的。这种情况少见，但不是矛盾——弱对偶只说「若两者都可行，则不等式成立」。

任意线性规划的对偶规则

设原问题是最大化。规则只有一张表：

理由就是弱对偶的证明：要把约束相加而不翻转不等号，$\le$ 约束的权重必须非负，$\ge$ 约束的权重必须非正，等式约束的权重随意。反过来，变量 $x_j$ 的符号决定了对偶约束的方向。

例子。 原问题

$$\max\;3x_1+5x_2-2x_3$$ $$\text{s.t.}\quad x_1+x_2\le8,\qquad x_1-x_3\ge1,\qquad x_2+x_3=4,$$ $$x_1,x_3\ge0,\qquad x_2\ \text{无约束}.$$

按表：第一条约束给 $y_1\ge0$，第二条给 $y_2\le0$，第三条给 $y_3$ 无约束。于是对偶是

$$\min\;8y_1+1\!\cdot\! y_2+4y_3$$

（注意第二条约束右端是 $1$，故系数为 $1$；若把约束写成 $-x_1+x_3\le-1$，则系数变为 $-1$，两者等价），约束为

$$\begin{aligned} y_1+y_2&\ge3 &&(x_1\text{ 的列})\\ y_1+y_3&=5 &&(x_2\text{ 无约束})\\ -y_2+y_3&\ge-2 &&(x_3\text{ 的列})\\ y_1\ge0,\quad y_2\le0,&\quad y_3\ \text{无约束}. \end{aligned}$$

更省事的做法

课程明说：不喜欢「负变量」的规则，因为容易出错。替代方案是先把原问题化成规范形，再套上一讲的公式。

对上面的例子：把第二条约束取负变成 $-x_1+x_3\le-1$，把自由变量 $x_2$ 拆成 $x_2^+-x_2^-$ 或者保留为等式后再按规则处理。课程采用的写法是保留等式、但把自由变量对应的对偶约束写成等式，得到

$$\min\;8y_1-y_2+4y_3 \quad\text{s.t.}\quad y_1-y_2\ge3,\;\; y_1+y_3=5,\;\; y_2+y_3\ge-2,\;\; y_1,y_2\ge0,\;y_3\ \text{无约束},$$

所有变量都在规范方向上，没有「$y_2\le0$」这种反直觉的东西。

互补松弛

定理。 设 $x$ 是规范形原问题的可行解，$y$ 是对偶可行解。则 $x$ 与 $y$ 同时最优，当且仅当

$$\text{对每个 } i:\quad y_i=0\ \text{或}\ (Ax)_i=b_i,$$ $$\text{对每个 } j:\quad x_j=0\ \text{或}\ (A^Ty)_j=c_j .$$

用一句话说：约束越紧，对应的对偶权重可以非零；约束有松弛，对偶权重必须为零。 反过来，原变量非零则对应的对偶约束必须取等号。

证明

弱对偶的链条是

$$c^Tx\;\le\;(A^Ty)^Tx\;=\;y^TAx\;\le\;y^Tb .$$

若 $x,y$ 都最优，由强对偶可知两端相等，于是中间每一步都必须取等号。

先看第一个不等号。$A^Ty\ge c$ 且 $x\ge0$，所以

$$(A^Ty-c)^Tx\ge0 .$$

取等号意味着这个非负量等于 $0$。它是 $m$ 项之和 $\sum_j (A^Ty-c)_j\,x_j$，每项都非负，所以每项都为 $0$：对每个 $j$，要么 $x_j=0$，要么 $(A^Ty)_j=c_j$。

再看第二个不等号。$b-Ax\ge0$ 且 $y\ge0$，所以

$$y^T(b-Ax)\ge0 .$$

取等号意味着每项 $y_i(b_i-(Ax)_i)=0$，即对每个 $i$，要么 $y_i=0$，要么 $(Ax)_i=b_i$。

反过来，如果这些互补条件都成立，上面两个不等号都取等号，于是 $c^Tx=y^Tb$，由弱对偶可知两者都达到最优。

用互补松弛反推对偶解

继续上面的例子。已知 $x=(4,4,0)$ 是原问题最优解（验证：$4+4=8$ 紧，$4-0=4\ge1$ 松，$4+0=4$ 紧；目标值 $3\cdot4+5\cdot4-2\cdot0=32$）。

由互补松弛：

• $x_1=4\ne0$，所以第一条对偶约束取等号：$y_1+y_2=3$。
• $x_2=4\ne0$，所以第二条对偶约束取等号：$y_1+y_3=5$。
• 第二条原约束不紧（$4>1$），所以 $y_2=0$。

解出 $y_1=3$，$y_3=2$，$y_2=0$。对偶目标值 $8\cdot3-1\cdot0+4\cdot2=24+8=32$，与原问题相等——强对偶得到验证。

这个过程也说明了互补松弛的实际用途：手算时不必再解第二个 LP，直接列出线性方程组即可。

强对偶的三种证明

课程列出了三条路线：

1. 单纯形表。 算法结束时表上同时读出原问题与对偶的最优解，两者相等。完全严格，但依赖算法细节。
2. Farkas 引理。 直接用分析中的引理。问题是这条引理本身与强对偶几乎是同一句话换个写法，证明不带来新理解。
3. $n$ 维力学。 用几条经典力学定理，把 LP 想成小球在斜面上滚动。课程选的是这一条，因为它给出几何直觉。

力学证明

把每条约束 $A_ix\ge b_i$ 看成一张超平面。目标函数 $\min c^Tx$ 是重力方向，小球被重力往下拉，落在可行区域最低的点上停住——那就是最优解。

停住意味着受力平衡：所有接触到的超平面施加的支持力之和等于重力。设第 $i$ 张超平面施加的力为

$$\text{力}_i=y_i\,A_i,\qquad y_i\ge0,$$

方向沿法向量 $A_i$（指向可行区域外侧），大小是 $y_i$。平衡条件写成

$$\sum_i y_iA_i=c, \quad\text{即}\quad A^Ty=c .$$

再看接触条件：

• 小球碰到第 $i$ 张超平面时，约束取等号 $(Ax)_i=b_i$；
• 没碰到时，那张超平面不施力，$y_i=0$。

这正是互补松弛。于是

$$y^T(Ax-b)=\sum_i y_i\big((Ax)_i-b_i\big)=0,$$

而 $A^Ty=c$ 给出 $y^TAx=c^Tx$，所以

$$c^Tx=y^Tb .$$

原问题与对偶问题的最优值相等，强对偶得证。这个论证的美妙之处在于：它把「线性规划强对偶」与「$n$ 维静力学自洽」说成了同一件事。

应用：König 定理

设定。 $G=(L\cup R,E)$ 是二分图。匹配是一组两两不共端点的边；顶点覆盖是一组与每条边都相邻的顶点。

定理（König）。 最大匹配的大小等于最小顶点覆盖的大小。

一个方向是显然的。 任何顶点覆盖都必须覆盖匹配的每条边，而匹配的边两两不交，所以覆盖至少要有「匹配大小」那么多个顶点。

另一个方向用 LP。 给每条边 $e$ 一个变量 $x_e\in[0,1]$，把匹配写成

$$\max\;\sum_e x_e \quad\text{s.t.}\quad \sum_{e\ni v}x_e\le1\ \ \text{对每个顶点 }v, \qquad x_e\ge0 .$$

每条边最多被选一次，每个顶点最多被一条选中的边占用——这就是匹配的「分数版本」。它的对偶是给每个顶点 $v$ 一个变量 $y_v\ge0$，

$$\min\;\sum_v y_v \quad\text{s.t.}\quad y_u+y_v\ge1\ \ \text{对每条边 }uv .$$

这正是分数顶点覆盖。

为什么最优解可以是整数？ 若存在分数解，可以沿一条交替路径或偶环调整：把 0.5 的边按奇偶交替加减同一个 $\varepsilon$，直到某个变量碰到 $0$ 或 $1$。二分图没有奇环，所以调整总能进行，最终消掉所有分数值。于是匹配 LP 有整数最优解；同理对偶也有整数最优解。两边的整数最优值相等，正是 König 定理。

课程在这里没有把细节讲完，但给出了完整的思路骨架：把组合问题写成 LP，证明松弛仍取整数解，再让强对偶替你完成计数。

本节结论

• 线性规划只有三种命运：有限最优、不可行、无界；原问题无界则对偶不可行。
• 任意 LP 的对偶由一张符号表决定；更稳妥的做法是先化成规范形。
• 互补松弛：紧约束才可能有非零对偶权重，非零原变量才要求对偶约束取等号。
• 互补松弛可直接从原问题最优解解出对偶最优解。
• 强对偶有一个力学证明：支持力平衡即 $A^Ty=c$，接触条件即互补松弛。
• König 定理：最大匹配 = 最小顶点覆盖，本质是匹配 LP 与其对偶的强对偶。

理解检验

1. 原问题是 $\max c^Tx$，第一条约束是 $\ge$，第二个变量自由，第三个变量 $\le0$。对应的对偶变量与对偶约束各是什么？

参考答案：第一条约束是 $\ge$，故 $y_1\le0$；第二个变量自由，故第二条对偶约束取等号；第三个变量 $\le0$，故第三条对偶约束是 $\le$。若不想记「负变量」规则，可先取负把约束改成 $\le$、把变量改成非负，再套规范形公式。

2. 用互补松弛求对偶最优解：原问题 $\max 3x_1+5x_2-2x_3$，约束 $x_1+x_2\le8$、$x_1-x_3\ge1$、$x_2+x_3=4$，已知 $x=(4,4,0)$ 最优。

参考答案：$x_1,x_2\ne0$ 使第一、二条对偶约束取等号；第二条原约束不紧（$4>1$）使 $y_2=0$。于是 $y_1+y_2=3\Rightarrow y_1=3$，$y_1+y_3=5\Rightarrow y_3=2$。对偶目标 $8y_1-y_2+4y_3=24+0+8=32$，等于原问题目标值 $32$，验证强对偶。

3. 证明规范形下的互补松弛定理。

参考答案：弱对偶给出 $c^Tx\le(A^Ty)^Tx\le y^Tb$。若两者最优，由强对偶两端相等，两个不等号都取等号。第一处等号意味着 $(A^Ty-c)^Tx=0$；因为 $A^Ty-c\ge0$、$x\ge0$，这是非负项之和，故每项为零：$x_j=0$ 或 $(A^Ty)_j=c_j$。第二处等号意味着 $y^T(b-Ax)=0$；因为 $y\ge0$、$b-Ax\ge0$，故 $y_i=0$ 或 $(Ax)_i=b_i$。反向由同样的等式链即得。

4. 在力学证明中，$y_i$ 代表什么？为什么「没接触」对应 $y_i=0$？

参考答案：$y_i$ 是第 $i$ 张超平面施加在小球上的支持力大小，方向沿法向量 $A_i$。小球没碰到那张超平面时，它与小球之间没有接触，也就没有力，所以 $y_i=0$；碰到时约束取等号 $(Ax)_i=b_i$。两者合起来正是互补松弛。受力平衡 $\sum_i y_iA_i=c$ 给出 $A^Ty=c$，于是 $c^Tx=y^TAx=y^Tb$，强对偶成立。

5. 为什么二分图匹配的 LP 松弛一定有整数最优解？

参考答案：任取一个分数最优解。若存在分数边，就能找到一条由分数边组成的交替路径或偶环（二分图没有奇环）。沿这条路径把边按 $+\varepsilon,-\varepsilon$ 交替调整，顶点约束保持不变，目标值不变；取最大的可行 $\varepsilon$，至少有一条边变成 $0$ 或 $1$。反复进行，最终所有边都取 $0$ 或 $1$，得到整数最优解。对偶（分数顶点覆盖）同理，于是整数最优值相等，即 König 定理。

与前后课的关系

上一讲建立了对偶公式与弱对偶；本讲补全一般规则、互补松弛与强对偶，并用 König 定理展示了「LP + 整数性」这套组合拳。下一讲把这套工具用在零和博弈上：原问题给出先手的最优混合策略，对偶给出后手的最优策略，强对偶就是极小极大定理。再下一讲的最大流最小割是同一模板的第三次出现。

From canonical form to arbitrary programs

The previous lecture defined the dual only for canonical form, where every constraint is $Ax\le b$ and every variable is non-negative. Real problems mix constraint directions and allow variables of either sign, so this lecture supplies the general rules and then proves the two central theorems: complementary slackness and strong duality.

Timeline

Three possible fates

Every linear program is exactly one of:

1. Finite optimum: feasible, and the optimal value is finite.
2. Infeasible: the feasible set is empty, e.g. $x_1\ge5$ and $x_1\le3$.
3. Unbounded: feasible, but the objective can be made arbitrarily large (or small), e.g. $\max x$ with $x\ge3$.

Weak duality gives two consequences at once:

• If the primal is unbounded, the dual is infeasible. Otherwise any dual feasible $y$ would give an upper bound $b^Ty$, contradicting unboundedness.
• If the dual is unbounded, the primal is infeasible.

Primal and dual may also be infeasible simultaneously. This is rare but not contradictory: weak duality only says that if both are feasible, the inequality holds.

Duals of arbitrary programs

Let the primal be a maximisation. One table decides everything:

The reason is the proof of weak duality: to add constraints without flipping inequalities, weights on $\le$ constraints must be non-negative, weights on $\ge$ constraints non-positive, and weights on equations arbitrary. Symmetrically, the sign of $x_j$ fixes the direction of the dual constraint.

Example. Primal:

$$\max\;3x_1+5x_2-2x_3$$ $$\text{s.t.}\quad x_1+x_2\le8,\qquad x_1-x_3\ge1,\qquad x_2+x_3=4,$$ $$x_1,x_3\ge0,\qquad x_2\ \text{free}.$$

The table gives $y_1\ge0$, $y_2\le0$, $y_3$ free, so the dual is

$$\min\;8y_1+1\cdot y_2+4y_3$$ $$\text{s.t.}\quad y_1+y_2\ge3,\qquad y_1+y_3=5,\qquad -y_2+y_3\ge-2,$$ $$y_1\ge0,\quad y_2\le0,\quad y_3\ \text{free}.$$

(The coefficient of $y_2$ is $1$ because the right-hand side of the second constraint is $1$; writing that constraint as $-x_1+x_3\le-1$ would produce $-1$ instead, with the same dual.)

An easier route

The lecture admits a dislike for the "negative variable" rule, because mistakes are easy. The alternative is to normalise the primal to canonical form first, then apply the previous lecture's formula.

For the example: negate the second constraint to $-x_1+x_3\le-1$, keep the free variable but give its dual constraint an equality, and read off

$$\min\;8y_1-y_2+4y_3 \quad\text{s.t.}\quad y_1-y_2\ge3,\;\; y_1+y_3=5,\;\; y_2+y_3\ge-2,\;\; y_1,y_2\ge0,\;y_3\ \text{free}.$$

Now every dual variable points the intuitive way; nothing says "$y_2\le0$".

Complementary slackness

Theorem. Let $x$ be primal feasible and $y$ dual feasible, for the canonical pair. Then $x$ and $y$ are both optimal if and only if

$$\text{for every } i:\quad y_i=0\ \text{or}\ (Ax)_i=b_i,$$ $$\text{for every } j:\quad x_j=0\ \text{or}\ (A^Ty)_j=c_j .$$

In words: a tight constraint may carry a nonzero dual weight; a slack constraint must carry zero weight. Conversely, a nonzero primal variable forces its dual constraint to be tight.

Proof

The chain behind weak duality is

$$c^Tx\;\le\;(A^Ty)^Tx\;=\;y^TAx\;\le\;y^Tb .$$

If both are optimal, strong duality makes the ends equal, so both inequalities must be equalities.

For the first: $A^Ty\ge c$ and $x\ge0$, so

$$(A^Ty-c)^Tx\ge0 .$$

Equality forces this non-negative quantity to be $0$. It is a sum of $m$ non-negative terms $\sum_j (A^Ty-c)_jx_j$, so every term is zero: for each $j$, either $x_j=0$ or $(A^Ty)_j=c_j$.

For the second: $b-Ax\ge0$ and $y\ge0$, so

$$y^T(b-Ax)\ge0 .$$

Equality forces every term $y_i(b_i-(Ax)_i)$ to vanish: for each $i$, either $y_i=0$ or $(Ax)_i=b_i$.

Conversely, if all these conditions hold, both inequalities are equalities, so $c^Tx=y^Tb$ and weak duality makes both optimal.

Recovering a dual solution

Return to the example. Suppose $x=(4,4,0)$ is known to be optimal (check: $4+4=8$ tight, $4-0=4\ge1$ slack, $4+0=4$ tight; objective $3\cdot4+5\cdot4-2\cdot0=32$).

Complementary slackness gives:

• $x_1=4\ne0$, so dual constraint 1 is tight: $y_1+y_2=3$.
• $x_2=4\ne0$, so dual constraint 2 is tight: $y_1+y_3=5$.
• Primal constraint 2 is slack ($4>1$), so $y_2=0$.

Solving gives $y_1=3$, $y_3=2$, $y_2=0$. Dual objective: $8\cdot3-1\cdot0+4\cdot2=24+8=32$, equal to the primal value — strong duality confirmed.

The practical lesson: you do not have to solve a second LP; write down the linear system and solve it.

Three proofs of strong duality

The lecture lists three routes:

1. The simplex tableau. When the algorithm stops, the tableau yields optimal solutions of both problems, and they are equal. Completely rigorous, but depends on algorithmic detail.
2. Farkas' lemma. Taken from analysis. The objection is that Farkas' lemma is essentially strong duality in different notation, so the proof adds no insight.
3. Mechanics in $n$ dimensions. A few classical theorems from mechanics, with the LP pictured as a ball rolling on surfaces. The lecture chooses this one for its geometric intuition.

The mechanical proof

Treat each constraint $A_ix\ge b_i$ as a hyperplane. Gravity points in the direction $\min c^Tx$, pulling the ball down until it comes to rest at the lowest point of the feasible region — the optimum.

Rest means force balance: the support forces from all hyperplanes the ball touches sum to the gravitational force. Let the force from hyperplane $i$ be

$$\text{force}_i=y_i\,A_i,\qquad y_i\ge0,$$

along the normal $A_i$ (pointing out of the feasible region) with magnitude $y_i$. Balance reads

$$\sum_i y_iA_i=c, \quad\text{i.e.}\quad A^Ty=c .$$

Now the contact conditions:

• If the ball touches hyperplane $i$, then the constraint is tight, $(Ax)_i=b_i$;
• If it does not touch it, that hyperplane exerts no force, so $y_i=0$.

That is exactly complementary slackness. Therefore

$$y^T(Ax-b)=\sum_i y_i\big((Ax)_i-b_i\big)=0,$$

while $A^Ty=c$ gives $y^TAx=c^Tx$, hence

$$c^Tx=y^Tb .$$

Primal and dual optima coincide, which is strong duality. The appeal is that "strong duality for linear programming" and "$n$-dimensional statics is consistent" become the same statement.

Application: König's theorem

Setting. Let $G=(L\cup R,E)$ be a bipartite graph. A matching is a set of edges with no shared endpoint; a vertex cover is a set of vertices meeting every edge.

Theorem (König). The size of a maximum matching equals the size of a minimum vertex cover.

One direction is immediate. Any vertex cover must cover every matching edge, and matching edges are disjoint, so the cover needs at least as many vertices as the matching has edges.

The other direction uses an LP. Give each edge $e$ a variable $x_e\in[0,1]$ and write the matching as

$$\max\;\sum_e x_e \quad\text{s.t.}\quad \sum_{e\ni v}x_e\le1\ \ \text{for every vertex }v, \qquad x_e\ge0 .$$

Each edge is chosen at most once and each vertex is used by at most one chosen edge — the "fractional" version of a matching. Its dual assigns $y_v\ge0$ to each vertex:

$$\min\;\sum_v y_v \quad\text{s.t.}\quad y_u+y_v\ge1\ \ \text{for every edge }uv .$$

That is a fractional vertex cover.

Why can the optimum be integral? Given a fractional solution, follow an alternating path or an even cycle of fractional edges and add $\pm\varepsilon$ alternately. Vertex constraints stay satisfied and the objective is unchanged; choosing $\varepsilon$ maximal drives some variable to $0$ or $1$. Bipartiteness rules out odd cycles, so the adjustment always exists, and all fractional values eventually disappear. Hence the matching LP has an integral optimum; the same argument works for the dual. The two integral optima are equal, which is König's theorem.

The lecture does not finish every detail, but the skeleton is complete: write the combinatorial problem as an LP, show the relaxation still has integral optima, and let strong duality do the counting.

What this lecture establishes

• An LP has exactly one of three fates: finite optimum, infeasible, unbounded; an unbounded primal implies an infeasible dual.
• The dual of an arbitrary LP follows one sign table; normalising to canonical form first is safer.
• Complementary slackness: only tight constraints may carry dual weight, and only nonzero primal variables force tight dual constraints.
• It recovers a dual optimum directly from a primal optimum.
• Strong duality has a mechanical proof: force balance is $A^Ty=c$, contact conditions are complementary slackness.
• König's theorem — max matching equals min vertex cover — is strong duality for the matching LP.

Comprehension check

1. The primal is $\max c^Tx$; constraint 1 is $\ge$, variable 2 is free, variable 3 is $\le0$. What are the dual variable signs and dual constraint directions?

Reference answer: Constraint 1 being $\ge$ gives $y_1\le0$; variable 2 being free makes dual constraint 2 an equality; variable 3 being $\le0$ makes dual constraint 3 a $\le$. If the negative-variable rule is unwelcome, negate constraints and variables first so everything is canonical, then apply the canonical formula.

2. Use complementary slackness: primal $\max 3x_1+5x_2-2x_3$ with $x_1+x_2\le8$, $x_1-x_3\ge1$, $x_2+x_3=4$, and $x=(4,4,0)$ optimal.

Reference answer: $x_1,x_2\ne0$ make dual constraints 1 and 2 tight; primal constraint 2 is slack ($4>1$), so $y_2=0$. Then $y_1+y_2=3$ gives $y_1=3$, and $y_1+y_3=5$ gives $y_3=2$. The dual objective is $8y_1-y_2+4y_3=24+0+8=32$, matching the primal value $32$.

3. Prove complementary slackness in canonical form.

Reference answer: Weak duality gives $c^Tx\le(A^Ty)^Tx\le y^Tb$. If both are optimal, strong duality makes the ends equal, so both inequalities are equalities. The first equality means $(A^Ty-c)^Tx=0$; since $A^Ty-c\ge0$ and $x\ge0$, this is a sum of non-negative terms, so each vanishes: $x_j=0$ or $(A^Ty)_j=c_j$. The second means $y^T(b-Ax)=0$; since $y\ge0$ and $b-Ax\ge0$, each term vanishes: $y_i=0$ or $(Ax)_i=b_i$. The converse follows by running the same chain backwards.

4. In the mechanical proof, what is $y_i$, and why does "no contact" mean $y_i=0$?

Reference answer: $y_i$ is the magnitude of the support force exerted by hyperplane $i$ on the ball, directed along the normal $A_i$. Without contact there is no force, so $y_i=0$; with contact the constraint is tight, $(Ax)_i=b_i$. Together these are complementary slackness. Force balance $\sum_i y_iA_i=c$ gives $A^Ty=c$, hence $c^Tx=y^TAx=y^Tb$ and strong duality.

5. Why does the LP relaxation of bipartite matching always have an integral optimum?

Reference answer: Take a fractional optimum. If a fractional edge exists, there is an alternating path or even cycle of fractional edges (bipartiteness excludes odd cycles). Add $\pm\varepsilon$ alternately along it: vertex constraints remain satisfied and the objective is unchanged, while the maximal feasible $\varepsilon$ sends at least one variable to $0$ or $1$. Iterating eliminates all fractional values, yielding an integral optimum. The same holds for the dual, so the two integral optima agree — König's theorem.

Relation to neighbouring lectures

The previous lecture built the duality formula and weak duality; this one completes the general rules, complementary slackness and strong duality, and uses König's theorem to show the LP-plus-integrality pattern. The next lecture applies the toolkit to zero-sum games: the primal yields the row player's optimal mixed strategy, the dual the column player's, and strong duality becomes the minimax theorem. The max-flow min-cut theorem after that is the third appearance of the same template.