运筹学 9 对偶问题的性质.ppt

Lec. 9 Operational Research对偶问题的性质
ZHU Tong
Chang’an University
E-mail:zhutongtraffic@
Oct. 2012
Home
Home
对偶问题的性质
(1)为什么要讲这些基本性质?
建立对偶问题与原问题之间的桥梁。
(2)怎么讲这些基本性质?
少证明,多说明其本质与应用的价值。
(3)常用表达形式
2
对偶问题的性质
原问题和对偶问题的关系;
原问题和对偶问题解的关系;
如何从对偶问题求原问题的最优解。
3
对偶问题的性质:七个定理
(1)对称性定理:原问题-对偶问题之间的关系(对偶的对偶是原问题)
(2)弱对偶定理:原-对偶问题可行解之间的关系(CX (0) ≤Y(0)b )
最优定理:可行解满足一定条件下( CX (0) =Y(0)b ), X (0) 、Y(0)成为最优解
强对偶定理:原问题有最优解,对偶问题也有,且目标函数相等。
无界性:若原问题为无界解,则其对偶问题无可行解。
(3)兼容性定理:可行基检验数相反数是对偶问题的一个基本解。
互补松弛定理: Y(0) 、X (0)是最优解的充要条件是
Y(0) X (0) s=0、 Y(0) s X (0) =0
4
对称性定理
对偶的对偶是原问题
又变为max问题:
两边乘负号
两边再乘负号
A取转置,(YA)'= A'Y'
5
弱对偶性定理
原-对偶问题可行解之间的关系(CX (0) ≤Y(0)b )
(1)原问题任一可行解所对应的目标函数值,是对偶问题最优目标函数值的下界(都小于等于)。
(2)对偶问题任一可行解所对应的目标函数值,是原问题最优目标函数值的上界(都大于等于)。
原问题
对偶问题
6
最优性定理
最优定理:可行解满足一定条件下( CX (0) =Y(0)b ), X (0) 、Y(0)成为最优解
原问题
对偶问题
7
强对偶性定理
强对偶定理:原问题有最优解,对偶问题也有,且目标函数相等。
8
无界性:若原问题为无界解,则其对偶问题无可行解。
书上没有,请补充!
⑤无界性定理
原问题
对偶问题
9
例题(1)
(1)观察出原问题有可行解,如(000);
(2)因为对偶问题的式1与基本条件存在矛盾,因此,无可行解。根据强对偶性,如果原问题有最优解,则对偶问题也有最优解。因此,原问题不可能有最优解,只可能“无最优解”。
(3)原问题即有解,又无最优解,是无界解。
10