线性规划和对偶问题_学习笔记

线性规划和对偶问题

任一线性规划问题都存在另一与之伴随的线性规划问题,它们组成一对互为对偶的线性规划问题。

线性规划的对偶问题与原问题互为对偶,线性规划的原问题与对偶问题地位具有对称关系。


原问题和对偶问题的转化

例子

原问题:

线性规划和对偶问题_学习笔记_第1张图片

对偶问题:

线性规划和对偶问题_学习笔记_第2张图片

转化方法

线性规划和对偶问题_学习笔记_第3张图片

线性规划和对偶问题_学习笔记_第4张图片

1、原问题有几个约束,对偶问题就有几个变量
2、原来的约束系数矩阵转个置就是对偶问题的约束系数矩阵
3、原来的目标函数系数变对偶问题约束常量,原来的约束常量变对偶问题的目标系数
4、左边求最大,右边求最小,按照这个模板带进去就可以了 ——大佬


对偶问题的性质

在这里给出对偶问题的一些基本结论,暂不做证明
弱对偶引理:假设 x x x λ λ λ 分别是线性规划的原问题和对偶问题(对称形式及非对称形式)的可行解,则 x T x ≥ λ T b x^Tx\ge λ^Tb xTxλTb ,即“极大值 ≤ \le 极小值”。

定理1:假设 x 0 x_0 x0 λ 0 λ_0 λ0 分别是原问题和对偶问题的可行解,如果 c T x 0 ≥ λ 0 T b c^Tx_0\ge λ_0^Tb cTx0λ0Tb,那么 x 0 x_0 x0 λ 0 λ_0 λ0 分别是各自问题的最优解。

定理2(对偶定理):如果原问题有最优解,那么其对偶问题也有最优解,并且它们目标函数的最优解相同。

定理3(互补松弛条件) x x x λ λ λ 分别是原问题和对偶问题的可行解,则它们分别是各自问题的最优解的充分必要条件为
1.      ( c T − λ T A ) x = 0 2.      λ T ( A x − b ) = 0 \begin{aligned} & 1.\ \ \ \ (c^T-λ^TA)x=0 \\ & 2.\ \ \ \ λ^T(A_x-b)=0 \end{aligned} 1.    (cTλTA)x=02.    λT(Axb)=0

你可能感兴趣的