一個線性規劃問題(「原問題」)的對偶線性規劃問題(「對偶問題」)是另一個線性規劃問題,由原問題以一定方式派生而來:[1]
- 原問題中的每個變量都變為對偶問題中的一個限制條件;
- 原問題中的每個限制條件都變為對偶問題中的一個變量;
- 原問題若是求目標函數的最大值,則對偶問題是求最小值,反之亦然。
對偶問題的構建方法
對於以下形式的兩個線性規劃問題:
問題甲 |
問題乙
|
最大化目標函數
|
最小化目標函數
|
n個變量
![{\displaystyle x_{i}\geq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/90a99710f61d5dea19e49ae5b31164d2b56b07e3)
![{\displaystyle x_{j}\leq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a25b709060717a8e06c7429faf7077a149f93ec)
![{\displaystyle x_{k}\in \mathbb {R} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/d0f1c1e7bc4aa15ca4089aabb589614c336b6ee1)
|
n個限制條件
- 第i個限制條件為
![{\displaystyle \geq c_{i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7d4f47b3df3d9caf88cbd6c0ee3ef87187819045)
- 第j個限制條件為
![{\displaystyle \leq c_{j}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/81f2b8f166eeacfd67093e7cad85d8afb7bdf8bc)
- 第k個限制條件為
![{\displaystyle =c_{k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f6dc1eea997c4cddef02ba94e93f79f6be207845)
|
m個限制條件
- 第i個限制條件為
![{\displaystyle \geq b_{i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/72342156ccfdf33657bbb386491a4a68ddf0486b)
- 第j個限制條件為
![{\displaystyle \leq b_{j}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c4d531e7ab7c6b721661762faeb769fbff1f74f9)
- 第k個限制條件為
![{\displaystyle =b_{k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/555be3056c0a3d3678b0c02e310e84a69a96a172)
|
m個變量
![{\displaystyle y_{i}\leq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/94b2bbe1e2efdcb82e5e9f27e9dbb034664f5360)
![{\displaystyle y_{j}\geq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/49f3403ec2784b5cfb5dbb9f7672742464846410)
![{\displaystyle y_{k}\in \mathbb {R} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/c486373245a33944746545a9020ed6540424ac35)
|
我們稱甲、乙互為對偶問題,即:甲為乙的對偶問題,乙為甲的對偶問題。由此定義可知,原問題是其對偶問題的對偶問題。
特別地, 若所有限制條件的符號方向相同,我們有以下形式:
名稱
|
問題甲
|
問題乙
|
對稱對偶問題
|
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
|
例子
以下甲乙互為對偶問題。
問題甲 |
問題乙
|
|
|
對偶定理
對於互相對偶的最大化問題甲與最小化問題乙,我們有如下兩個定理。
弱對偶定理
若
、
分別滿足問題甲、乙的限制條件,則:
。
強對偶定理
若
、
分別滿足問題甲、乙的限制條件,則:
分別為問題甲、乙的最優解(即
,
),當且僅當
。
換言之,若甲、乙均有解,則
。
無限值解與無解問題
由對偶定理,不難得出以下結論:
- 若原問題有無限值解,則其對偶問題無解;
- 若對偶問題有無限值解,則其原問題無解。
但是,原問題和對偶問題可同時無解。
對偶問題的解讀
經濟學角度
甲公司有擁有一間核酸檢測實驗室,提供普通、VIP兩種核酸檢測服務,每人次普通、VIP檢測分別可獲利潤10元、20元。每人次普通、VIP檢測分別需要占用1單位、8/3單位人力,而該實驗室有每天4千單位人力。由於PCR擴增儀檢測能力限制,該實驗室每天最多檢測2千人次。另由於政府規管,該實驗室每天最多允許1.5千人次VIP檢測。因核酸檢測需求旺盛,不論該實驗室提供多少次核酸檢測服務均有人買單。問題甲:該實驗室每天應該分別提供多少次普通、VIP核酸檢測服務?
現乙公司欲租用該核酸檢測實驗室。問題乙:乙公司應該為每單位人力、每人次核酸檢測能力、每人次VIP檢測許可分別支付多少錢一天?
問題甲 |
問題乙
|
利潤最大化
|
成交價格最小化
|
2個變量
(普通核酸服務次數)
(VIP核酸服務次數)
|
2個限制條件
(否則甲公司寧可自己做普通核酸服務)
(否則甲公司寧可自己做VIP核酸服務)
|
3個限制條件
(人手限制)
(檢測能力限制)
(政府免許限制)
|
3個變量
(單位人力價格)
(單位檢測能力價格)
(單位免許價格)
|
問題甲、乙均有解。由前述強對偶定理可知,甲公司能獲得的最大利潤即是乙公司能獲得的最低成交價格。最優解為:
幾何角度
參考
- ^ Gärtner, Bernd; Matoušek, Jiří. Understanding and Using Linear Programming. 德國柏林: Springer. 2006: 81–104. ISBN 3-540-30697-8.