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