Lagrange 对偶问题

定义其的对偶问题:

Lagrange函数

考虑线性规划问题

若取集合约束D={x|x≥0}，则该线性规划问题的Lagrange函数为

线性规划的对偶问题为：

对偶定理
原问题：

对偶问题：

定理1(弱对偶定理)

LP对偶问题的基本性质
原问题(P) 对偶问题(D)

定理1(弱对偶定理)

定理2(最优性准则)

证明：

定理3(强对偶定理)
若(P),(D)均有可行解,则(P),(D)均有最优解,且(P),(D)的最优目标函数值相等.
证明：因为(P),(D)均有可行解,由推论2,推论3知,(P)的目标函数值在其可行域内有下界, (D)的目标函数值在其可行域内有上界, 故则(P),(D)均有最优解.

参考：http://wenku.baidu.com/view/1ae29f1119e8b8f67d1cb95b