對偶線性規劃

一个线性规划问题（“原问题”）的对偶线性规划问题（“对偶问题”）是另一个线性规划问题，由原问题以一定方式派生而来：
 原问题中的每个变量都变为对偶问题中的一个限制条件；
 原问题中的每个限制条件都变为对偶问题中的一个变量；
 原问题若是求目标函数的最大值，则对偶问题是求最小值，反之亦然。

 对偶问题的构建方法 
对于以下形式的两个线性规划问题：
 问题甲  问题乙 最大化目标函数 最小化目标函数 n个变量


  n个限制条件
 第i个限制条件为
 第j个限制条件为
 第k个限制条件为 m个限制条件
 第i个限制条件为
 第j个限制条件为
 第k个限制条件为 m个变量



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

特别地， 若所有限制条件的符号方向相同，我们有以下形式：
名称问题甲问题乙对称对偶问题Maximize cTx  满足 Ax ≤ b, x ≥ 0Minimize  bTy  满足 ATy ≥ c, y ≥ 0非对称对偶问题Maximize cTx 满足 Ax ≤ bMinimize  bTy 满足 ATy = c, y ≥ 0Maximize cTx  满足 Ax = b, x ≥ 0Minimize  bTy  满足 ATy ≥ c

例子
以下甲乙互为对偶问题。
 问题甲  问题乙   

 对偶定理 
对于互相对偶的最大化问题甲与最小化问题乙，我们有如下两个定理。
弱对偶定理
若、分别满足问题甲、乙的限制条件，则：。
强对偶定理
若、分别满足问题甲、乙的限制条件，则：分别为问题甲、乙的最优解（即，），当且仅当。

换言之，若甲、乙均有解，则。

无限值解与无解问题
由对偶定理，不难得出以下结论：
 若原问题有无限值解，则其对偶问题无解；
 若对偶问题有无限值解，则其原问题无解。
但是，原问题和对偶问题可同时无解。

对偶问题的解读
经济学角度

甲公司有擁有一間核酸檢測實驗室，提供普通、VIP兩種核酸檢測服務，每人次普通、VIP檢測分別可獲利潤10元、20元。每人次普通、VIP檢測分別需要占用1單位、8/3單位人力，而該實驗室有每天4千單位人力。由於PCR擴增儀檢測能力限制，該實驗室每天最多檢測2千人次。另由於政府規管，該實驗室每天最多允許1.5千人次VIP檢測。因核酸檢測需求旺盛，不論該實驗室提供多少次核酸檢測服務均有人買單。問題甲：該實驗室每天應該分別提供多少次普通、VIP核酸檢測服務？

現乙公司欲租用該核酸檢測實驗室。問題乙：乙公司應該為每單位人力、每人次核酸檢測能力、每人次VIP檢測許可分別支付多少錢一天？
 问题甲  问题乙 利潤最大化 成交價格最小化 2个变量
 （普通核酸服務次數）
 （VIP核酸服務次數） 2个限制条件
 （否則甲公司寧可自己做普通核酸服務）
 （否則甲公司寧可自己做VIP核酸服務） 3个限制条件
 （人手限制）
 （檢測能力限制）
 （政府免許限制） 3个变量
 （單位人力價格）
 （單位檢測能力價格）
 （單位免許價格）
問題甲、乙均有解。由前述強對偶定理可知，甲公司能獲得的最大利潤即是乙公司能獲得的最低成交價格。最優解為：

几何角度

 参考 

Category:應用數學
Category:運籌學