對偶線性規劃

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

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

对偶问题的构建方法

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

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

例子

以下甲乙互为对偶问题。

问题甲	问题乙
${\displaystyle {\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}}}$	${\displaystyle {\begin{aligned}{\text{minimize }}&7y_{1}\\{\text{s.t. }}&5y_{1}\geq 3\\&6y_{1}\geq 4\\&y_{1}\in \mathbb {R} \end{aligned}}}$

对偶定理

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

弱对偶定理

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

强对偶定理

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

换言之，若甲、乙均有解，则${\displaystyle \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檢測許可分別支付多少錢一天？

问题甲	问题乙
利潤最大化 ${\displaystyle \max _{x}c^{T}x=\max _{x}10x_{1}+20x_{2}}$	成交價格最小化 ${\displaystyle \min _{y}b^{T}y=\min _{y}4y_{1}+2y_{2}+1.5y_{3}}$
2个变量${\displaystyle x_{1},x_{2}}$  ${\displaystyle x_{1}\geq 0}$ （普通核酸服務次數） ${\displaystyle x_{2}\geq 0}$ （VIP核酸服務次數）	2个限制条件${\displaystyle A^{T}y\geq c}$  ${\displaystyle y_{1}+y_{2}\geq 10}$ （否則甲公司寧可自己做普通核酸服務） ${\displaystyle {\frac {8}{3}}y_{1}+y_{2}+y_{3}\geq 20}$ （否則甲公司寧可自己做VIP核酸服務）
3个限制条件${\displaystyle Ax\leq b}$  ${\displaystyle x_{1}+{\frac {8}{3}}x_{2}\leq 4}$ （人手限制） ${\displaystyle x_{1}+x_{2}\leq 2}$ （檢測能力限制） ${\displaystyle x_{2}\leq 1.5}$ （政府免許限制）	3个变量${\displaystyle y_{1},y_{2},y_{3}}$  ${\displaystyle y_{1}\geq 0}$ （單位人力價格） ${\displaystyle y_{2}\geq 0}$ （單位檢測能力價格） ${\displaystyle y_{3}\geq 0}$ （單位免許價格）

問題甲、乙均有解。由前述強對偶定理可知，甲公司能獲得的最大利潤即是乙公司能獲得的最低成交價格。最優解為：${\displaystyle x_{1}=0.8,x_{2}=1.2}$ 

几何角度

主条目：最大流最小割定理 § 线性规划公式

参考

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