对偶线性规划

一个线性规划问题（“原问题”）的对偶线性规划问题（“对偶问题”）是另一个线性规划问题，由原问题以一定方式派生而来：^[1]

原问题中的每个变量都变为对偶问题中的一个限制条件；
原问题中的每个限制条件都变为对偶问题中的一个变量；
原问题若是求目标函数的最大值，则对偶问题是求最小值，反之亦然。

对偶问题的构建方法

对于以下形式的两个线性规划问题：

问题甲	问题乙
最大化目标函数 $\max _{x}c^{T}x=\max _{x}\sum _{i}c_{i}x_{i}$	最小化目标函数 $\min _{y}b^{T}y=\min _{y}\sum _{i}b_{i}y_{i}$
n个变量 $x_{1},\ldots ,x_{n}$ $x_{i}\geq 0$ $x_{j}\leq 0$ $x_{k}\in \mathbb {R}$	n个限制条件 $A^{T}y\lesseqqgtr c$ 第i个限制条件为 $\geq c_{i}$ 第j个限制条件为 $\leq c_{j}$ 第k个限制条件为 $=c_{k}$
m个限制条件 $Ax\lesseqqgtr b$ 第i个限制条件为 $\geq b_{i}$ 第j个限制条件为 $\leq b_{j}$ 第k个限制条件为 $=b_{k}$	m个变量 $y_{1},\ldots ,y_{m}$ $y_{i}\leq 0$ $y_{j}\geq 0$ $y_{k}\in \mathbb {R}$

我们称甲、乙互为对偶问题，即：甲为乙的对偶问题，乙为甲的对偶问题。由此定义可知，原问题是其对偶问题的对偶问题。

特别地，若所有限制条件的符号方向相同，我们有以下形式：

名称	问题甲	问题乙
对称对偶问题	Maximize c^Tx 满足 Ax ≤ b, x ≥ 0	Minimize b^Ty 满足 A^Ty ≥ c, y ≥ 0
非对称对偶问题	Maximize c^Tx 满足 Ax ≤ b	Minimize b^Ty 满足 A^Ty = c, y ≥ 0
非对称对偶问题	Maximize c^Tx 满足 Ax = b, x ≥ 0	Minimize b^Ty 满足 A^Ty ≥ c

例子

以下甲乙互为对偶问题。

问题甲	问题乙
${\begin{aligned}{\text{maximize }}&3x_{1}+4x_{2}\\{\text{s.t. }}&5x_{1}+6x_{2}=7\\&x_{1}\geq 0,x_{2}\geq 0\end{aligned}}$	${\begin{aligned}{\text{minimize }}&7y_{1}\\{\text{s.t. }}&5y_{1}\geq 3\\&6y_{1}\geq 4\\&y_{1}\in \mathbb {R} \end{aligned}}$

对偶定理

对于互相对偶的最大化问题甲与最小化问题乙，我们有如下两个定理。

弱对偶定理

若 $x\in \mathbb {R} ^{n}$ 、 $y\in \mathbb {R} ^{m}$ 分别满足问题甲、乙的限制条件，则： $c^{T}x\leq b^{T}y$ 。

强对偶定理

若 $x^{*}\in \mathbb {R} ^{n}$ 、 $y^{*}\in \mathbb {R} ^{m}$ 分别满足问题甲、乙的限制条件，则： $x^{*},y^{*}$ 分别为问题甲、乙的最优解（即 $x^{*}=\operatorname {argmax} _{x}c^{T}x$ ， $y^{*}=\operatorname {argmin} _{y}b^{T}y$ ），当且仅当 $c^{T}x^{*}=b^{T}y^{*}$ 。

换言之，若甲、乙均有解，则 $\max _{x}c^{T}x=\min _{y}b^{T}y$ 。

无限值解与无解问题

由对偶定理，不难得出以下结论：

若原问题有无限值解，则其对偶问题无解；
若对偶问题有无限值解，则其原问题无解。

但是，原问题和对偶问题可同时无解。

对偶问题的解读

经济学角度

甲公司有拥有一间核酸检测实验室，提供普通、VIP两种核酸检测服务，每人次普通、VIP检测分别可获利润10元、20元。每人次普通、VIP检测分别需要占用1单位、8/3单位人力，而该实验室有每天4千单位人力。由于PCR扩增仪检测能力限制，该实验室每天最多检测2千人次。另由于政府规管，该实验室每天最多允许1.5千人次VIP检测。因核酸检测需求旺盛，不论该实验室提供多少次核酸检测服务均有人买单。问题甲：该实验室每天应该分别提供多少次普通、VIP核酸检测服务？

现乙公司欲租用该核酸检测实验室。问题乙：乙公司应该为每单位人力、每人次核酸检测能力、每人次VIP检测许可分别支付多少钱一天？

问题甲	问题乙
利润最大化 $\max _{x}c^{T}x=\max _{x}10x_{1}+20x_{2}$	成交价格最小化 $\min _{y}b^{T}y=\min _{y}4y_{1}+2y_{2}+1.5y_{3}$
2个变量 $x_{1},x_{2}$ $x_{1}\geq 0$ （普通核酸服务次数） $x_{2}\geq 0$ （VIP核酸服务次数）	2个限制条件 $A^{T}y\geq c$ $y_{1}+y_{2}\geq 10$ （否则甲公司宁可自己做普通核酸服务） ${\frac {8}{3}}y_{1}+y_{2}+y_{3}\geq 20$ （否则甲公司宁可自己做VIP核酸服务）
3个限制条件 $Ax\leq b$ $x_{1}+{\frac {8}{3}}x_{2}\leq 4$ （人手限制） $x_{1}+x_{2}\leq 2$ （检测能力限制） $x_{2}\leq 1.5$ （政府免许限制）	3个变量 $y_{1},y_{2},y_{3}$ $y_{1}\geq 0$ （单位人力价格） $y_{2}\geq 0$ （单位检测能力价格） $y_{3}\geq 0$ （单位免许价格）

问题甲、乙均有解。由前述强对偶定理可知，甲公司能获得的最大利润即是乙公司能获得的最低成交价格。最优解为： $x_{1}=0.8,x_{2}=1.2$

几何角度

参考

^ Gärtner, Bernd; Matoušek, Jiří. Understanding and Using Linear Programming. 德国柏林: Springer. 2006: 81–104. ISBN 3-540-30697-8.

[1] Gärtner, Bernd; Matoušek, Jiří. Understanding and Using Linear Programming. 德国柏林: Springer. 2006: 81–104. ISBN 3-540-30697-8.

[1]