對偶線性規劃

一個線性規劃問題（「原問題」）的對偶線性規劃問題（「對偶問題」）是另一個線性規劃問題，由原問題以一定方式派生而來：^[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 cTx 滿足 Ax ≤ b, x ≥ 0	Minimize bTy 滿足 ATy ≥ c, y ≥ 0
非對稱對偶問題	Maximize cTx 滿足 Ax ≤ b	Minimize bTy 滿足 ATy = c, y ≥ 0
	Maximize cTx 滿足 Ax = b, x ≥ 0	Minimize bTy 滿足 ATy ≥ 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}$

幾何角度

主條目：最大流最小割定理 § 線性規劃公式