文章目录
一、弱对偶性质
二、弱对偶定理分析
三、弱对偶定理推论 1
四、弱对偶定理推论 2 对偶问题的无界性
五、弱对偶定理推论 3
一、弱对偶性质
弱对偶定理 :
假设 X 0 \rm X^0X
0
和 Y 0 \rm Y^0Y
0
分别是 问题 ( P ) \rm (P)(P) ( 目标函数求最大值 ) 和 问题 ( D ) \rm (D)(D) ( 目标函数求最小值 ) 的 可行解 , 则必有 C X 0 ≤ Y 0 b \rm CX^0 \leq Y^0 bCX
0
≤Y
0
b ,
展开后为 ∑ j = 1 n c j x j ≤ ∑ i = 1 m y i b i \rm \sum_{j = 1}^n c_j x_j \leq \sum_{i = 1}^{m} y_i b_i∑
j=1
n
c
j
x
j
≤∑
i=1
m
y
i
b
i
二、弱对偶定理分析
弱对偶定理分析 :
问题 ( P ) \rm (P)(P) 与 问题 ( D ) \rm (D)(D) 互为对偶 , 其中
问题 ( P ) \rm (P)(P) 是 原问题 , 目标函数求 最大值 ,
问题 ( D ) \rm (D)(D) 是 对偶问题 , 目标函数求 最小值 ;
C X 0 \rm CX^0CX
0
是 原问题 ( P ) \rm (P)(P) 目标函数 代入 X 0 \rm X^0X
0
可行解之后的值 ; 计算出一个具体的数值 ;
Y 0 b \rm Y^0bY
0
b 是 对偶问题 ( D ) \rm (D)(D) 目标函数 代入 Y 0 \rm Y^0Y
0
可行解之后的值 ; 计算出一个具体的数值 ;
只要互为对偶的两个问题都有可行解 , 目标函数求最大值的 C X 0 \rm CX^0CX
0
值 ( 原问题 ) , 一定小于等于 , 目标函数求最小值的 Y 0 b \rm Y^0bY
0
b 值 ( 对偶问题 ) ;
如果互为对偶的两个问题都有可行解 , 原问题求最大值 , 对偶问题求最小值 ,
求最大值的原问题一定都 在某个界限值之下 ,
求最小值的对偶问题一定都 在某个界限之上 ,
上述描述中的 界限值是同一个界限值 ;
三、弱对偶定理推论 1
弱对偶定理推论 1 :
原问题 任何一个 可行解 的目标函数值 , 都是其对偶问题 目标函数值的下界 ;
反之 ,
对偶问题 任何一个 可行解 的目标函数值 , 都是其原问题 目标函数的上界 ;
问题 ( P ) \rm (P)(P) 与 问题 ( D ) \rm (D)(D) 互为对偶 , 其中
问题 ( P ) \rm (P)(P) 是 原问题 , 目标函数求 最大值 ,
问题 ( D ) \rm (D)(D) 是 对偶问题 , 目标函数求 最小值 ;
C X 0 \rm CX^0CX
0
是 原问题 ( P ) \rm (P)(P) 目标函数 代入 X 0 \rm X^0X
0
可行解之后的值 , 该值是其对偶问题目标函数值的下界 ;
Y 0 b \rm Y^0bY
0
b 是 对偶问题 ( D ) \rm (D)(D) 目标函数 代入 Y 0 \rm Y^0Y
0
可行解之后的值 , 该值是其原问题目标函数值的上界 ;
四、弱对偶定理推论 2 对偶问题的无界性
弱对偶定理推论 2 : ( 对偶问题的无界性 )
在一对 对偶问题 ( P ) \rm (P)(P) 和 ( D ) \rm (D)(D) 中 ,
如果其中 一个线性规划问题可行 , 但是 目标函数无界 , 则 另外一个问题没有可行解 ;
如果其中 一个线性规划问题不可行 , 其 对偶问题不一定不可行 ;
弱对偶定理推论 2 ( 对偶问题的无界性 ) 解析 :
如果目标函数求最小值的问题无界 , 则 取值一直可以减小 , 此时不存在一个界限值 ,
因此其对偶问题 一定没有可行解 ;
只要该问题有可行解 , 将可行解代入目标函数 , 即可获得一个 界限值 ;
这个界限值一定是另外对应对偶问题的可行解 ;
如果目标函数求最大值的问题无界 , 则 取值一直可以增大 , 此时不存在一个界限值 ,
因此其对偶问题 一定没有可行解 ;
只要该问题有可行解 , 将可行解代入目标函数 , 即可获得一个 界限值 ;
这个界限值一定是另外对应对偶问题的可行解 ;
一个线性规划是不可行的 , 其对偶问题不一定不可行 ;
一个线性规划不可行 , 其对偶问题可能有如下情况 :
① 有最优解 ( 不会成立 ) , 根据最优性定理 , 一个有最优解 , 另一个也有最优解 ;
② 无界解
③ 无可行解
原问题 与 对偶问题 ,
一个无界 , 另一个肯定不可行 ;
一个不可行 , 另一个不一定可行 , 有两种情况 ① 无界解 ② 无可行解 ;
五、弱对偶定理推论 3
弱对偶定理推论 3 :
在一对 对偶问题 ( P ) \rm (P)(P) 和 ( D ) \rm (D)(D) 中 ,
如果其中 一个线性规划问题可行 , 而 另一个线性规划问题不可行 , 则 该可行问题的目标函数是无界的;
