对偶问题

##例题：##

原问题：$\max f=x_1+2x_2+4x_3$maxf=x1​+2x2​+4x3​
$x_1+x_2+3x_3≥2$x1​+x2​+3x3​≥2
$x_1+7x_2+x_3≥ 8$x1​+7x2​+x3​≥8
$2x_1+x_2+x_3≥2$2x1​+x2​+x3​≥2
$x_1≥0,x_2≥0,x_3无约束$x1​≥0,x2​≥0,x3​无约束
对偶问题：
$\min g=2y_1+8y_2+2y_3$ming=2y1​+8y2​+2y3​
$y_1+y_2+2y_3≥1$y1​+y2​+2y3​≥1
$y_1+7y_2+y_3≥2$y1​+7y2​+y3​≥2
$3y_1+y_2+y_3≥4$3y1​+y2​+y3​≥4
$y_1≥0,y_2≥0,y_3无约束$y1​≥0,y2​≥0,y3​无约束

对于一个问题：
$max(cX)$max(cX)，约束条件为：$AX\le b$AX≤b
转换为对偶问题：
$min(b^TY)$min(bTY)，约束条件为：$A^TY≥c^T$ATY≥cT
(以上$A，X，Y，c，b$A，X，Y，c，b 均为矩阵)
　
转换过程：
$A^TY≥c^T$ATY≥cT带入原问题：
$(cX) =((c^T)TX)\le ((A^TY)TX)=(Y^TAX) $
将$AX\le b$AX≤b带入式中：
$(Y^TAX) \le (Y^Tb)$(YTAX)≤(YTb)
因为$(Y^Tb)$(YTb)是最终的结果，是$(1×1)$(1×1)的矩阵，所以$(Y^Tb)$(YTb)=$(b^TY)$(bTY)

SUMMARY：
对于任意的满足各自约束的$X，Y$X，Y向量，都有$(cX)\le (b^TY)$(cX)≤(bTY)，所以$\max(cX)=\min(b^TY)$max(cX)=min(bTY)

附上截自百度文库的转换规则：