||
原规划与对偶规划问题的变量及解之间的对应关系
除了互补松弛定理求解外,还有如下的直观关系:
(1)对偶(min型)变量的最优解等于原问题松弛变量检验数的绝对值
(2)对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值
(3)由于原问题和对偶问题是相互对偶的,因此对偶问题的检验数与原问题的解也有类似上述关系。
(4)更一般地讲,不管原问题是否标准,在最优解的单纯型表中,都有原问题虚变量(松弛或剩余) 的检验数对应其对偶问题实变量 (对偶变量)的最优解,原问题实变量(决策变量) 的检验数对应其对偶问题虚变量 (松弛或剩余变量)的最优解。因此,原问题或对偶问题只需求解其中之一就可以了。
例1 两个互为对偶的线性规划问题:
两者分别加上松弛和剩余变量后为:
两个问题的最终单纯形表(注第2张表以最小化为目标)见:
| 原问题变量 | 松弛变量 | |||||
Cjà | 2 | 1 | 0 | 0 | 0 | ||
CB | XB | b | x1 | x2 | x3 | x4 | x5 |
0 | x3 | 15/2 | 0 | 0 | 1 | 5/4 | -15/2 |
2 | x1 | 7/2 | 1 | 0 | 0 | 1/4 | -1/2 |
1 | x2 | 3/2 | 0 | 1 | 0 | -1/4 | 3/2 |
Cj-zj | 0 | 0 | 0 | -1/4 | -1/2 | ||
| 对偶问题的剩余变量 | 对偶问题变量 | |||||
y4 | y5 | y1 | y2 | y3 |
| 对偶问题变量 | 对偶问题的剩余变量 | |||||
Cjà | 15 | 24 | 5 | 0 | 0 | ||
CB | XB | b | y1 | y2 | y3 | y4 | y5 |
24 | y2 | 1/4 | -5/4 | 1 | 0 | -1/4 | 1/4 |
5 | y3 | 1/2 | 15/2 | 0 | 1 | 1/2 | -3/2 |
Cj-zj | 15/2 | 0 | 0 | 7/2 | 3/2 | ||
| 原问题的松弛变量 | 原问题变量 | |||||
x3 | x4 | x5 | x1 | x2 |
明显可见其中类似(4)的对应关系。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-12-19 04:03
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社