|
|
第104行: |
第104行: |
|
== 参考 == |
|
== 参考 == |
|
{{reflist}} |
|
{{reflist}} |
|
|
|
|
|
{{Uncategorized|time=2021-12-12T15:09:37+00:00}} |
2021年12月12日 (日) 15:09的版本
一个线性规划问题(“原问题”)的对偶线性规划问题(“对偶问题”)是另一个线性规划问题,由原问题以一定方式派生而来:[1]
- 原问题中的每个变量都变为对偶问题中的一个限制条件;
- 原问题中的每个限制条件都变为对偶问题中的一个变量;
- 原问题若是求目标函数的最大值,则对偶问题是求最小值,反之亦然。
对偶问题的构建方法
对于以下形式的两个线性规划问题:
问题甲 |
问题乙
|
最大化目标函数
|
最小化目标函数
|
n个变量
|
n个限制条件
- 第i个限制条件为
- 第j个限制条件为
- 第k个限制条件为
|
m个限制条件
- 第i个限制条件为
- 第j个限制条件为
- 第k个限制条件为
|
m个变量
|
我们称甲、乙互为对偶问题,即:甲为乙的对偶问题,乙为甲的对偶问题。由此定义可知,原问题是其对偶问题的对偶问题。
特别地, 若所有限制条件的符号方向相同,我们有以下形式:
名称
|
问题甲
|
问题乙
|
对称对偶问题
|
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
|
例子
以下甲乙互为对偶问题。
问题甲 |
问题乙
|
|
|
对偶定理
对于互相对偶的最大化问题甲与最小化问题乙,我们有如下两个定理。
弱对偶定理
若、分别满足问题甲、乙的限制条件,则:。
强对偶定理
若、分别满足问题甲、乙的限制条件,则:分别为问题甲、乙的最优解(即,),当且仅当。
换言之,若甲、乙均有解,则。
无限值解与无解问题
由对偶定理,不难得出以下结论:
- 若原问题有无限值解,则其对偶问题无解;
- 若对偶问题有无限值解,则其原问题无解。
但是,原问题和对偶问题可同时无解。
对偶问题的解读
现实角度
几何角度
参考
- ^ Gärtner, Bernd; Matoušek, Jiří. Understanding and Using Linear Programming. 德国柏林: Springer. 2006: 81–104. ISBN 3-540-30697-8.