线性规划在做什么

线性规划（LP）就是：在线性约束下，最大化或最小化一个线性函数。它是整个优化的发动机——课程提到，1987 年 CPLEX 问世后成为最赚钱的求解器之一，背后的商业价值说明了它的地位。

本讲做四件事：写两个模型、定义标准形与规范形、说明两者如何互转、推出对偶。

时间轴

例一：饮食问题

给小鼠配餐。需要 $8$ 单位淀粉、$15$ 单位蛋白质、$7$ 单位维生素。谷物 1 每单位提供 $(5,4,2)$，价格 $0.60$；谷物 2 每单位提供 $(7,2,1)$，价格 $0.35$。

设 $x_1,x_2$ 分别是两种谷物的用量。模型：

$$\begin{aligned} \min\quad & 60x_1+35x_2\\ \text{s.t.}\quad & 5x_1+7x_2\ge 8 &&\text{(淀粉)}\\ & 4x_1+2x_2\ge 15 &&\text{(蛋白质)}\\ & 2x_1+x_2\ge 7 &&\text{(维生素)}\\ & x_1,x_2\ge 0 . \end{aligned}$$

（价格按美分计。）最后一行的非负约束容易被忘掉，但它不是装饰：没有它，模型可以把 $x_1=-100$ 当作「省钱」的解，而负的谷物用量没有物理意义。线性规划软件通常把非负约束单独处理。

建模的固定套路：先选变量，再写目标函数，再写约束，最后交给求解器。本课不教怎么手算求解——实际工作中你也不会手算。

例二：烘焙问题

卖曲奇和蛋白饼。一批曲奇需要 $1$ 个蛋、$2$ 杯糖、$1.5$ 杯面粉；一批蛋白饼需要 $3$ 个蛋、$1$ 杯糖、$0$ 杯面粉。现有 $9$ 个蛋、$8$ 杯糖、$15$ 杯面粉。两批都卖 $20$ 美元。

设 $x_1$ 为曲奇批数，$x_2$ 为蛋白饼批数：

$$\begin{aligned} \max\quad & 20x_1+20x_2\\ \text{s.t.}\quad & x_1+3x_2\le 9 &&\text{(蛋)}\\ & 2x_1+x_2\le 8 &&\text{(糖)}\\ & 1.5x_1\le 15 &&\text{(面粉)}\\ & x_1,x_2\ge 0 . \end{aligned}$$

可行域。 两条变量时可以直接画。第一条约束的边界过 $(0,3)$ 与 $(9,0)$；第二条过 $(0,8)$ 与 $(4,0)$。面粉约束 $x_1\le10$ 完全多余：满足前两条的点一定满足它。可行域是这两条直线与坐标轴围成的四边形。

可行解是满足全部约束的点（不必最优）；最优解是使目标函数最优的可行解。例如 $(2,2)$ 可行，目标值 $80$；$(3,2)$ 也可行，目标值 $100$。后面会证明 $100$ 就是最优值。

两种标准形式

标准形（standard form）：

$$\max\; c^Tx \quad\text{s.t.}\quad Ax=b,\;\; x\ge0 .$$

规范形（canonical form）：

$$\max\; c^Tx \quad\text{s.t.}\quad Ax\le b,\;\; x\ge0 .$$

定理。 任何线性规划都可以化成标准形或规范形。

四类变换：

1. 最小化改最大化。 $\min 3x_1+5x_2$ 等价于 $\max -3x_1-5x_2$，最优解相同，最优值取相反数。

2. 自由变量拆成两个非负变量。 若 $x_i$ 可正可负，令

$$x_i=x_i^+-x_i^-,\qquad x_i^+,x_i^-\ge0 .$$

任意实数都能写成两个非负数之差（例如 $-3=0-3$），于是所有变量都非负。

3. 不等式加松弛/剩余变量变等式。

$$x_1+3x_2\le9 \;\Longleftrightarrow\; x_1+3x_2+s=9,\quad s\ge0 ,$$

其中 $s$ 叫松弛变量。

$$x_1+3x_2\ge9 \;\Longleftrightarrow\; x_1+3x_2-s=9,\quad s\ge0 ,$$

其中 $s$ 叫剩余变量。

4. 等式拆成两个不等式，$\ge$ 用取负号变 $\le$。

$$x_1+3x_2=9 \;\Longleftrightarrow\; x_1+3x_2\le9 \ \text{且}\ x_1+3x_2\ge9 ,$$

而 $x_1+3x_2\ge9$ 再写成 $-x_1-3x_2\le-9$，就落进规范形。

两个形式的分工：单纯形法用标准形，因为要解线性方程组找基本可行解；对偶理论用规范形，因为约束全是 $\le$，加权相加时不等号方向一致。

基本可行解与单纯形法

定理。 有最优解的线性规划，一定存在基本可行解是最优解。

几何上，基本可行解就是可行域的顶点。回忆烘焙问题的可行域是个四边形，四个顶点中必有一个使 $20x_1+20x_2$ 最大。

为什么叫「基本」？把 LP 写成标准形，每个松弛变量对应一列。选一组线性无关的列构成基，令其余变量为 $0$，解出基变量，就得到一个基本解；若它非负，就是基本可行解。

单纯形法：从一个基本可行解出发，沿可行域的棱走到相邻顶点，每步都让目标函数变大，直到没有更好的邻点。Dantzig 提出后实践效果极好，但很长一段时间里，对任何选边策略都能构造出需要指数步的例子。直到 Spielman 与 Teng 提出平滑分析，才在理论上说明了「几乎总是很快」。

对偶：从约束组合得到上界

回到烘焙问题。可行解给出下界：$(3,2)$ 可行，目标值 $100$，所以最优值至少 $100$。

上界从哪来？ 把约束加权相加。取权重 $y_1=4$、$y_2=8$：

$$4(x_1+3x_2)+8(2x_1+x_2)=20x_1+20x_2 .$$

左边两个括号分别不超过 $9$ 与 $8$，而系数非负，所以

$$20x_1+20x_2\le4\cdot9+8\cdot8=36+64=100 .$$

上下界相等，最优值确定为 $100$。这组权重就是对偶最优解，它同时是一个「最优性证书」。

一般地，对规范形

$$\max\; c^Tx\quad\text{s.t.}\quad Ax\le b,\;x\ge0,$$

取 $y\ge0$ 作权重，把第 $i$ 行乘以 $y_i$ 再相加。要让左边能够覆盖目标函数的系数，需要

$$A^Ty\ge c .$$

在这些条件下，

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

于是 $y^Tb$ 是一个上界。要让上界尽可能紧，就求

$$\min\; b^Ty\quad\text{s.t.}\quad A^Ty\ge c,\;y\ge0 .$$

这就是对偶规划。原问题与对偶的对应关系：

为什么 $y\ge0$？因为如果某个 $y_i<0$，乘上 $\le$ 约束会翻转不等号，相加就没有意义了。

弱对偶与强对偶

弱对偶定理。 若 $x$ 是原问题可行解、$y$ 是对偶可行解，则

$$c^Tx\le b^Ty .$$

证明。 由对偶可行性 $A^Ty\ge c$，两边左乘 $x^T\ge0$：

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

由原问题可行性 $Ax\le b$ 及 $y\ge0$，左乘 $y^T$：

$$y^TAx\le y^Tb .$$

串联起来即得。整个证明只用了「非负权重乘不等号不翻向」这一件事。

强对偶定理（陈述，下一讲证明）。 若原问题的最优值 $z^*$ 有限，则对偶最优值 $w^*$ 也有限，且 $z^*=w^*$。

对偶的对偶是原问题。 把对偶 $\min b^Ty$、$A^Ty\ge c$、$y\ge0$ 先化成规范形（取负号变最大化、变 $\le$），再取对偶，得到 $\min-c^Tx$、$-Ax\ge-b$、$x\ge0$；再取负号就回到原问题。名字「对偶」由此而来。

本节结论

• 线性规划 = 线性目标 + 线性约束 + 非负约束；建模顺序是变量、目标、约束。
• 标准形是 $Ax=b,\ x\ge0$；规范形是 $Ax\le b,\ x\ge0$；两者可以互相转换。
• 转换四招：取负、拆自由变量、加松弛/剩余变量、等式拆成两个不等式。
• 基本可行解是可行域的顶点，单纯形法沿棱走到最优顶点。
• 对偶 = 用非负权重把约束相加，得到最优值的上界；权重就是灵敏度。
• 弱对偶：任何原可行值不超过任何对偶可行值。

理解检验

1. 写出饮食问题的完整模型，并说明为什么非负约束不能省。

参考答案：

$$\min\ 60x_1+35x_2\quad\text{s.t.}\quad 5x_1+7x_2\ge8,\;4x_1+2x_2\ge15,\;2x_1+x_2\ge7,\;x_1,x_2\ge0 .$$

省掉 $x_1,x_2\ge0$ 后，模型允许负的用量，而负用量可以减少「成本」、又能无限制地满足 $\ge$ 约束（取足够负的值也不行——实际上会让营养约束更难过，但目标会趋向 $-\infty$，问题变成无界或荒谬）。更本质的理由是：用量在物理上不能为负，非负性属于问题本身，而不是求解技巧。

2. 把下面的问题化成规范形：$\min 3x_1+5x_2$，约束 $x_1+x_2\ge4$，$x_1-2x_2\le6$，$x_1\ge0$，$x_2$ 自由。

参考答案：先令 $x_2=x_2^+-x_2^-$，$x_2^\pm\ge0$；再把最小化取负变最大化；最后把 $\ge$ 约束两边取负：

$$\max\ -3x_1-5x_2^++5x_2^- \quad\text{s.t.}\quad -x_1-x_2^++x_2^-\le-4,\;\; x_1-2x_2^++2x_2^-\le6,\;\; x_1,x_2^+,x_2^-\ge0 .$$

3. 用松弛变量把 $x_1+3x_2\le9$ 写成等式；如果是 $\ge9$，又该怎么写？

参考答案：$\le$ 引入松弛变量 $s\ge0$，写成 $x_1+3x_2+s=9$；$\ge$ 引入剩余变量 $s\ge0$，写成 $x_1+3x_2-s=9$。两者都保持「原不等式与等式解集相同」。

4. 对烘焙问题，给出一个可行解、一个上界证书，并说明最优值。

参考答案：可行解 $x=(3,2)$：$3+6=9$，$6+2=8$，满足全部约束，目标值 $100$。上界证书取对偶可行解 $y=(4,8)$：$4(x_1+3x_2)+8(2x_1+x_2)=20x_1+20x_2\le4\cdot9+8\cdot8=100$；对偶约束为 $y_1+2y_2=4+16=20\ge20$、$3y_1+y_2=12+8=20\ge20$，非负。上下界相等，故最优值为 $100$。

5. 证明弱对偶。

参考答案：由 $A^Ty\ge c$ 与 $x\ge0$ 得 $c^Tx\le (A^Ty)^Tx$；由 $(A^Ty)^Tx=y^TAx$、$Ax\le b$ 与 $y\ge0$ 得 $y^TAx\le y^Tb$。串联：$c^Tx\le y^TAx\le y^Tb$，即原问题任意可行值不超过对偶任意可行值。

6. 为什么把等式拆成两个不等式，而不是别的方式？

参考答案：等式 $a^Tx=b$ 与「$a^Tx\le b$ 且 $a^Tx\ge b$」完全等价，这是集合层面的等价，不引入新变量。而规范形只允许 $\le$，所以再把 $a^Tx\ge b$ 写成 $-a^Tx\le-b$。这样写的好处是每条约束的权重符号规则统一，取对偶时不必特殊处理。

与前后课的关系

本讲建立了模型与对偶的框架，但把强对偶留作结论。下一讲给出强对偶的三种证明思路（单纯形表、Farkas 引理、力学类比），并用互补松弛从原问题最优解反推对偶最优解，最后用它证明二分图的 König 定理。再往后，对偶会直接变成零和博弈的极小极大定理与最大流最小割定理。

What linear programming does

A linear program (LP) is: maximise or minimise a linear function subject to linear constraints. It is the engine behind a great deal of optimisation — the lecture notes that when CPLEX appeared in 1987 it became the dominant solver, and the commercial sums involved show how much it matters.

This lecture does four things: writes two models, defines standard and canonical form, shows how to convert between them, and derives the dual.

Timeline

Example 1: the diet problem

Feed some mice. They need $8$ units of starch, $15$ of protein and $7$ of vitamins. Grain 1 supplies $(5,4,2)$ per unit at $0.60$; grain 2 supplies $(7,2,1)$ at $0.35$.

Let $x_1,x_2$ be the amounts of the two grains:

$$\begin{aligned} \min\quad & 60x_1+35x_2\\ \text{s.t.}\quad & 5x_1+7x_2\ge 8 &&\text{(starch)}\\ & 4x_1+2x_2\ge 15 &&\text{(protein)}\\ & 2x_1+x_2\ge 7 &&\text{(vitamins)}\\ & x_1,x_2\ge 0 . \end{aligned}$$

(Prices in cents.) The final line, the non-negativity constraints, is easy to forget and is not decoration: without it the model can regard a negative amount of grain as a saving, while negative grain has no physical meaning. Solvers usually treat non-negativity separately from the other constraints.

The modelling recipe is fixed: choose variables, write the objective, write the constraints, hand it to a solver. This course does not teach hand-solving — in practice you would not either.

Example 2: the bake sale

You sell cookies and meringues. A batch of cookies needs $1$ egg, $2$ cups of sugar and $1.5$ cups of flour; a batch of meringues needs $3$ eggs, $1$ cup of sugar and no flour. You have $9$ eggs, $8$ cups of sugar and $15$ cups of flour. Each batch sells for \20$.

Let $x_1$ be batches of cookies and $x_2$ batches of meringues:

$$\begin{aligned} \max\quad & 20x_1+20x_2\\ \text{s.t.}\quad & x_1+3x_2\le 9 &&\text{(eggs)}\\ & 2x_1+x_2\le 8 &&\text{(sugar)}\\ & 1.5x_1\le 15 &&\text{(flour)}\\ & x_1,x_2\ge 0 . \end{aligned}$$

The feasible region. With two variables it can be drawn. The first constraint's boundary passes through $(0,3)$ and $(9,0)$; the second through $(0,8)$ and $(4,0)$. The flour constraint $x_1\le10$ is redundant: every point satisfying the first two satisfies it. The feasible region is the quadrilateral cut out by the two lines and the axes.

A feasible solution satisfies all constraints (not necessarily optimally); an optimal solution optimises the objective among feasible points. For instance $(2,2)$ is feasible with value $80$, and $(3,2)$ is feasible with value $100$. We will see that $100$ is optimal.

Two standard forms

Standard form:

$$\max\; c^Tx \quad\text{s.t.}\quad Ax=b,\;\; x\ge0 .$$

Canonical form:

$$\max\; c^Tx \quad\text{s.t.}\quad Ax\le b,\;\; x\ge0 .$$

Theorem. Any linear program can be put into standard or canonical form.

Four transformations:

1. Minimisation to maximisation. $\min 3x_1+5x_2$ is equivalent to $\max -3x_1-5x_2$: same optimiser, objective negated.

2. Split a free variable. If $x_i$ may have either sign, set

$$x_i=x_i^+-x_i^-,\qquad x_i^+,x_i^-\ge0 .$$

Every real number is a difference of two non-negative numbers (for example $-3=0-3$), so all variables become non-negative.

3. Inequalities to equations with slack or surplus variables.

$$x_1+3x_2\le9 \;\Longleftrightarrow\; x_1+3x_2+s=9,\quad s\ge0 ,$$

where $s$ is a slack variable, and

$$x_1+3x_2\ge9 \;\Longleftrightarrow\; x_1+3x_2-s=9,\quad s\ge0 ,$$

where $s$ is a surplus variable.

4. Equations become two inequalities; $\ge$ becomes $\le$ after negation.

$$x_1+3x_2=9 \;\Longleftrightarrow\; x_1+3x_2\le9 \ \text{and}\ x_1+3x_2\ge9 ,$$

and $x_1+3x_2\ge9$ is rewritten as $-x_1-3x_2\le-9$, which is canonical.

The division of labour: the simplex method uses standard form, since it solves linear systems to find basic feasible solutions; duality uses canonical form, since all constraints point the same way and can be added with non-negative weights.

Basic feasible solutions and the simplex method

Theorem. If a linear program has an optimal solution, then some basic feasible solution is optimal.

Geometrically, basic feasible solutions are the vertices of the feasible region. The bake-sale region is a quadrilateral, and one of its four vertices maximises $20x_1+20x_2$.

Why "basic"? In standard form each slack variable contributes a column. Pick a linearly independent set of columns — a basis — set the remaining variables to zero, and solve for the basic variables. The result is a basic solution; if it is non-negative it is a basic feasible solution.

The simplex method starts at a basic feasible solution and walks along an edge of the feasible region to a neighbouring vertex, each step improving the objective, until no neighbour is better. Dantzig's method worked extremely well in practice, yet for a long time every pivot rule admitted examples requiring exponentially many steps. Spielman and Teng's smoothed analysis finally explained why it is fast almost always.

Duality: upper bounds from combining constraints

Back to the bake sale. A feasible solution gives a lower bound: $(3,2)$ is feasible with value $100$, so the optimum is at least $100$.

Where does an upper bound come from? Weight and add the constraints. Take $y_1=4$, $y_2=8$:

$$4(x_1+3x_2)+8(2x_1+x_2)=20x_1+20x_2 .$$

The two brackets are at most $9$ and $8$, and the weights are non-negative, so

$$20x_1+20x_2\le4\cdot9+8\cdot8=36+64=100 .$$

The bounds meet, so the optimum is exactly $100$. Those weights form a dual optimal solution and act as a certificate of optimality.

In general, for canonical form

$$\max\; c^Tx\quad\text{s.t.}\quad Ax\le b,\;x\ge0,$$

take weights $y\ge0$, multiply row $i$ by $y_i$ and add. To cover the objective coefficients on the left we need

$$A^Ty\ge c .$$

Under that condition,

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

so $y^Tb$ is an upper bound. The tightest such bound solves

$$\min\; b^Ty\quad\text{s.t.}\quad A^Ty\ge c,\;y\ge0 ,$$

the dual program. The correspondence:

Why $y\ge0$? If some $y_i<0$, multiplying a $\le$ constraint flips its inequality, and adding the results would prove nothing.

Weak and strong duality

Weak duality. If $x$ is primal feasible and $y$ is dual feasible, then

$$c^Tx\le b^Ty .$$

Proof. From dual feasibility $A^Ty\ge c$, left-multiply by $x^T\ge0$:

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

From primal feasibility $Ax\le b$ and $y\ge0$, left-multiply by $y^T$:

$$y^TAx\le y^Tb .$$

Chaining the two gives the claim. The whole proof rests on one fact: a non-negative weight times an inequality does not flip it.

Strong duality (stated; proved next lecture). If the primal optimum $z^*$ is finite, so is the dual optimum $w^*$, and $z^*=w^*$.

The dual of the dual is the primal. Put the dual $\min b^Ty$, $A^Ty\ge c$, $y\ge0$ into canonical form (negate to get a maximisation with $\le$), take the dual to get $\min -c^Tx$, $-Ax\ge-b$, $x\ge0$, then negate again to recover the primal. This is where the name comes from.

What this lecture establishes

• An LP is a linear objective, linear constraints and non-negativity; model by choosing variables, objective, constraints.
• Standard form is $Ax=b,\ x\ge0$; canonical form is $Ax\le b,\ x\ge0$; either converts to the other.
• Four conversions: negate, split free variables, add slack/surplus, split equations into two inequalities.
• Basic feasible solutions are vertices; simplex walks along edges to the best vertex.
• The dual weights the constraints to bound the optimum; the weights are the certificate.
• Weak duality: no primal feasible value exceeds any dual feasible value.

Comprehension check

1. Write the full diet model and explain why non-negativity cannot be dropped.

Reference answer:

$$\min\ 60x_1+35x_2\quad\text{s.t.}\quad 5x_1+7x_2\ge8,\;4x_1+2x_2\ge15,\;2x_1+x_2\ge7,\;x_1,x_2\ge0 .$$

Without $x_1,x_2\ge0$ the model allows negative amounts of grain, which are physically meaningless; the feasible set no longer describes the problem. Non-negativity is part of the problem, not a solution technique.

2. Convert to canonical form: $\min 3x_1+5x_2$ subject to $x_1+x_2\ge4$, $x_1-2x_2\le6$, $x_1\ge0$, $x_2$ free.

Reference answer: Set $x_2=x_2^+-x_2^-$ with $x_2^\pm\ge0$; negate the objective to maximise; negate the $\ge$ constraint:

$$\max\ -3x_1-5x_2^++5x_2^- \quad\text{s.t.}\quad -x_1-x_2^++x_2^-\le-4,\;\; x_1-2x_2^++2x_2^-\le6,\;\; x_1,x_2^+,x_2^-\ge0 .$$

3. Turn $x_1+3x_2\le9$ into an equation; what if it were $\ge9$?

Reference answer: For $\le$, add a slack $s\ge0$: $x_1+3x_2+s=9$. For $\ge$, subtract a surplus $s\ge0$: $x_1+3x_2-s=9$. Both preserve the solution set of the original inequality.

4. For the bake sale, give a feasible solution, an upper-bound certificate, and the optimum.

Reference answer: $x=(3,2)$ is feasible: $3+6=9$ and $6+2=8$, objective $100$. The certificate is the dual feasible $y=(4,8)$: $4(x_1+3x_2)+8(2x_1+x_2)=20x_1+20x_2\le4\cdot9+8\cdot8=100$, with $y_1+2y_2=20\ge20$, $3y_1+y_2=20\ge20$ and $y\ge0$. The bounds agree, so the optimum is $100$.

5. Prove weak duality.

Reference answer: From $A^Ty\ge c$ and $x\ge0$ we get $c^Tx\le(A^Ty)^Tx$. Using $(A^Ty)^Tx=y^TAx$, $Ax\le b$ and $y\ge0$ gives $y^TAx\le y^Tb$. Hence $c^Tx\le y^TAx\le y^Tb$: every primal feasible value is at most every dual feasible value.

6. Why split an equation into two inequalities rather than something else?

Reference answer: $a^Tx=b$ is exactly equivalent, as a set of solutions, to "$a^Tx\le b$ and $a^Tx\ge b$", and this introduces no new variables. Since canonical form allows only $\le$, the second is rewritten as $-a^Tx\le-b$. The advantage is that every constraint now has the same orientation, so the sign rules for dual weights are uniform.

Relation to neighbouring lectures

The lecture sets up modelling and duality but leaves strong duality as a statement. The next lecture gives three proof routes (simplex tableau, Farkas' lemma, a mechanical analogy), uses complementary slackness to recover a dual optimum from a primal one, and closes with König's theorem for bipartite graphs. Further on, duality becomes the minimax theorem for zero-sum games and the max-flow min-cut theorem.