线性规划的对偶规划_线性规划对偶

线性规划的对偶规划由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“线性规划对偶”。

1对偶问题的形式 设原线性规划问题为：

maxZcixi

i1na11x1a12x2a1nxnb1a21x1a22x2a2nxnb2 s..taxaxaxbmnnmm11m22xj0,j1,2,,n则称下面线性规划问题：

minWbiyi

i1ma11y1a21y2am1ymc1a12y1a22y2am2ymc2 s..tayayaycmnmn1n12n2yj0,j1,2,,m为其对偶问题，其中yj(j1,2,,m)称为对偶变量。上述对偶问题称为对称型对偶问题。原问题简记为（P），对偶问题简记为（D）。原问题（P）矩阵形式：

maxZcTx

Axbs..t xi0,i1,2,,n对偶问题（D）矩阵形式：

maxWbTy

TAycs..t yj0,j1,2,,m2对偶关系对应表

形式 目标函数类型 目标函数系与右边项系数

右边项系数 变量数n 变量数与约束数

约束数m ≥0

原问题变量类型与对偶问题约束类型

≤0 无限制 ≥0

原问题约束类型与对偶问题变量类型

≤0 = 2对偶问题的基本性质

定理1：对偶问题的对偶就是原问题；

定理2（弱对偶定理）：若x，y分别为（P），（D）的可行解，则有cTxyTb；

原问题 max

对偶问题 min

目标函数系数 右边项系数

目标函系数 约束数n 变量数m ≥0 ≤0 = ≥0 ≤0 无限制

推论1：若（P），（D）都有可行解，则（P），（D）必定都有最优解。推论2：若（P）有可行解，但无有限最优解，则（D）无可行解。定理3：若x，y分别为（P），（D）的可行解，且有cTx=yTb，则x，（D）的最优解； y分别为（P）定理4（主对偶定理）：若（P），（D）都有可行解，则（P），（D）必定都有最优解，且目标函数的最优值必定相等；

推论：若（P），（D）中任意一个有最优解，则（P），（D）必定都有最优解，且目标函数的最优值必定相等。

定理5：若x，y分别为（P），（D）的可行解，则x，y分别为（P），Ty(bAx)0（D）的最优解的充要条件是TT同时成立。

(Ayc)x=0