强对偶定理及其应用场景分析

强对偶定理有如下三种常见表述形式:

第一种:原问题P(max)有最优解的充要条件是对偶问题D(min)有最优解,且两个问题的最优目标函数值相等。

证明:必要性。若原问题有最优解,则对偶问题有最优解。

①存在性。设X∗是P的最优解,则有C―CBB－1 A≤0和CBB－1≥0,即检验数小于或等于零。令Y＝CBB－1,则YA≥C,Y≥0,Y就是D的一个可行解,同时有YA＝Y(B,N)≥C＝(CB,CN),即YB≥CB,Y≥CBB－1。可见,对偶问题的目标函数值有最小值,即对偶问题有最优解。

②相等性。对于原问题,有CX＝CBXB＝CBB－1b;对于对偶问题,有Y∗b＝CBB－1b。

充分性可由对称性定理得到证明。证毕。

第二种:对于原问题P(max)和对偶问题D(min),若P无界,则D不可行;若D无界,则P不可行。(www.xing528.com)

该定理可由弱对偶定理证明。需要注意的是:该定理的逆不成立,因为当P无可行解时,其对偶问题或者无可行解,或者具有无界解。

第三种:若X∗和Y∗分别是P(max)和D(min)的可行解,则它们分别为原问题和对偶问题最优解的充要条件是CX∗＝Y∗b。

证明:必要性。设X∗是P的最优解,由弱对偶定理CX∗≤Y∗b可知,若Yb有最小值,则为CX∗。又因对偶问题有最优解,则有min Yb＝Y∗b,所以CX∗＝Y∗b。

充分性。同理,对于对偶问题的任何可行解Y,存在Y∗b＝CX∗≤Yb。由于对偶问题求的是最小值,故Y∗b必为最优值,Y∗为最优解。证毕。

强对偶定理表明,当原问题(或对偶问题)达到最优时,对偶问题(或原问题)也一定达到最优,且两者对应的最优目标函数值相等。