对偶理论、拉格朗日对偶问题、LP线性规划对偶性质

对偶理论、拉格朗日对偶问题、LP线性规划对偶性质

对偶理论、拉格朗日对偶问题、LP线性规划对偶性质对偶理论、拉格朗日对偶问题、LP线性规划对偶性质对偶理论、拉格朗日对偶问题、LP线性规划对偶性质对偶理论、拉格朗日对偶问题、LP线性规划对偶性质

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

上一篇:Linux实战案例(4)CentOS清除用户登录记录和命令历史方法


下一篇:JS计算时间差值