(3.4.2)--03_4_2对偶问题的基本性质.pdf

《(3.4.2)--03_4_2对偶问题的基本性质.pdf》由会员分享，可在线阅读，更多相关《(3.4.2)--03_4_2对偶问题的基本性质.pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、对偶问题的基本性质 为了便于讨论，下面不妨总是假设（1）对称性：对偶的对偶就是原问题min=-CXs.t.-AX -bX 0max z=-Ybs.t.-YA -CY 0min=Ybs.t.YA CY 0max z=CXs.t.AX bX 0对偶的定义对偶的定义对偶的定义对偶的定义对偶问题(min)的任何可行解Y，其目标函数值总是不小于原问题(max)任何可行解X的目标函数值（2）弱对偶性:若是原问题的可行解，是对偶问题的可行解。则存在XYbYXC（3）无界性：若原问题（对偶问题）为无界解，其对偶问题（原问题）无可行解证：由弱对偶定理推论1，结论是显然的。同理可证明:对于原问题的所有可行解 存在

2、是使目标函数取最小值的解，因此是最优解也是最优解（4）可行解是最优解的性质(最优性准则定理)若是原问题的可行解，是对偶问题可行解，当,分别是相应问题的最优解（5）对偶定理若原问题和对偶问题两者皆可行,则两者均有最优解,且此时目标函数值相等。证：由于原问题和对偶问题均可行,根据弱对偶性,可知两者均有界,于是均有最优解。设为原问题的最优解它所对应的基矩阵是B，则其检验数满足C CBB1A 0 因此有对偶问题目标函数值而原问题最优解的目标函数值为显然为对偶问题的可行解。故由最优解准则定理可知为对偶问题的最优解.（6）互补松弛定理设,分别是原问题和对偶问题的可行解，为原问题的松弛变量的值，为对偶问题剩

3、余变量的值。,分别是原问题和对偶问题最优解的充分必要条件是证：由定理所设，可知有根据最优解判别定理，分别是原问题和对偶问题最优解。反之亦然。分别以左乘(1)式，以 右乘(2)式后，两式相减，得(1)(2)（7）原问题单纯形表检验数行与对偶问题解的关系原问题单纯形表检验数的相反数对应对偶问题的一个基解.显然,原问题最终单纯形表检验数的相反数对应对偶问题的一个基可行解证：标准化后的原问题和对偶问题的表达式为：若B是A中的一个基，A=（B，N）Slide 10原问题解为 XB=B-1b，N=CN-CBB-1N，Z=CBB-1b对偶问题的约束条件：检验数：B=CB-CBB-1B=0，N=CN-CBB-1N，S=-CBB-1原问题单纯形表检验数行与对偶问题解的关系