對偶線性規劃

一個線性規劃問題(「原問題」)的對偶線性規劃問題(「對偶問題」)是另一個線性規劃問題,由原問題以一定方式派生而來:[1]

  • 原問題中的每個變量都變為對偶問題中的一個限制條件;
  • 原問題中的每個限制條件都變為對偶問題中的一個變量;
  • 原問題若是求目標函數的最大值,則對偶問題是求最小值,反之亦然。

對偶問題的構建方法

對於以下形式的兩個線性規劃問題:

問題甲 問題乙
最大化目標函數
 
最小化目標函數
 
n個變量 
  •  
  •  
  •  
n個限制條件 
  • 第i個限制條件為 
  • 第j個限制條件為 
  • 第k個限制條件為 
m個限制條件 
  • 第i個限制條件為 
  • 第j個限制條件為 
  • 第k個限制條件為 
m個變量 
  •  
  •  
  •  

我們稱甲、乙互為對偶問題,即:甲為乙的對偶問題,乙為甲的對偶問題。由此定義可知,原問題是其對偶問題的對偶問題。

特別地, 若所有限制條件的符號方向相同,我們有以下形式:

名稱 問題甲 問題乙
對稱對偶問題 Maximize cTx 滿足 Axb, x ≥ 0 Minimize bTy 滿足 ATyc, y ≥ 0
非對稱對偶問題 Maximize cTx 滿足 Axb Minimize bTy 滿足 ATy = c, y ≥ 0
Maximize cTx 滿足 Ax = b, x ≥ 0 Minimize bTy 滿足 ATyc

例子

以下甲乙互為對偶問題。

問題甲 問題乙
   

對偶定理

對於互相對偶的最大化問題甲與最小化問題乙,我們有如下兩個定理。

弱對偶定理

  分別滿足問題甲、乙的限制條件,則: 

強對偶定理

  分別滿足問題甲、乙的限制條件,則: 分別為問題甲、乙的最優解(即  ),當且僅當 

換言之,若甲、乙均有解,則 

無限值解與無解問題

由對偶定理,不難得出以下結論:

  • 若原問題有無限值解,則其對偶問題無解;
  • 若對偶問題有無限值解,則其原問題無解。

但是,原問題和對偶問題可同時無解。

對偶問題的解讀

經濟學角度

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

現乙公司欲租用該核酸檢測實驗室。問題乙:乙公司應該為每單位人力、每人次核酸檢測能力、每人次VIP檢測許可分別支付多少錢一天?

問題甲 問題乙
利潤最大化
 
成交價格最小化
 
2個變量 
  •  (普通核酸服務次數)
  •  (VIP核酸服務次數)
2個限制條件 
  •  (否則甲公司寧可自己做普通核酸服務)
  •  (否則甲公司寧可自己做VIP核酸服務)
3個限制條件 
  •  (人手限制)
  •  (檢測能力限制)
  •  (政府免許限制)
3個變量 
  •  (單位人力價格)
  •  (單位檢測能力價格)
  •  (單位免許價格)

問題甲、乙均有解。由前述強對偶定理可知,甲公司能獲得的最大利潤即是乙公司能獲得的最低成交價格。最優解為: 

幾何角度

參考

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