跳转到内容

對偶線性規劃

维基百科,自由的百科全书

一个线性规划问题(“原问题”)的对偶线性规划问题(“对偶问题”)是另一个线性规划问题,由原问题以一定方式派生而来:[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.