对偶问题和对偶理论
最后更新时间:
对偶问题
对偶的含义
这里的对偶是指对同一事物(问题)从不同的角度(立场)观察,有两种拟似对立的表述。如“平面中矩形的面积与周长的关系”。可分别表述为：周长一定，面积最大的矩形是正方形；面积一定,周长最短的矩形是正方形。又如同一个数据集的线性规划问题,可以有两种优化的表述：一个企业决策者做生产规划时，可以提出最大利润为目标函数；也可以提出以最小资源消耗为目标。
对偶问题的一般形式
原问题 \[ \begin{array}{c} \max z=c_{1} x_{1}+c_{2} x_{2}+\cdots+c_{n} x_{n} \\ {\left[\begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1 n} \\ \vdots & \vdots & & \vdots \\ a_{m 1} & a_{m 2} & \cdots & a_{m n} \end{array}\right]\left[\begin{array}{c} x_{1} \\ x_{2} \\ \vdots \\ x_{n} \end{array}\right] \leqslant\left[\begin{array}{c} b_{1} \\ \vdots \\ b_{m} \end{array}\right]} \\ x_{1}, x_{2}, \cdots, x_{n} \geqslant 0 \end{array} \] 对偶问题 \[ \begin{array}{c} \min \omega=y_{1} b_{1}+y_{2} b_{2}+\cdots+y_{m} b_{m} \\ \left(y_{1}, y_{2}, \cdots, y_{m}\right)\left[\begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1 n} \\ \vdots & \vdots & & \vdots \\ a_{m 1} & a_{m 2} & \cdots & a_{m n} \end{array}\right] \geqslant\left(c_{1}, c_{2}, \cdots, c_{n}\right) \\ y_{1}, y_{2}, \cdots, y_{m} \geqslant 0 \end{array} \] 以上是原问题与对偶问题的标准形式。
- 原问题收益最大化=maxz→对偶问题代价最小化(min w)
- 原问题方程个数=资源种类数→对偶问题的决策变量数
- 原问题的价值系数=原有收益（c向量）→对偶问题约束条件右端项向量
- 原问题的资源约束=资源个数（b向量）→对偶问题的价值系数
基本性质
弱对偶性
弱对偶性：若 \(\mathbf{X}\) 是原问题的可行解， \(\mathbf{Y}\) 是对偶问题可行解，则恒有： \[ \mathbf{C X} \leq \mathrm{Y}^{\mathrm{T}} \mathbf{b} \]
证: 已知条件为: 有： \(\mathbf{Y}^{\mathbf{T}} \mathbf{b} \geq \mathbf{Y}^{\mathrm{T}} \mathbf{A X} \geq \mathbf{C X}\) ，得证
根据弱对偶性，我们得到如下推论: - 原问题最优解目标函数值是对偶问题目标函数值的下界， - 对偶问题最优解目标函数值是原问题目标函数值的上界。 - 原问题有无界解，则对偶问题无可行解，反之亦然 即对偶问题有无界解，则原问题无可行解，但逆不成立 ， 对偶问题无可行解时，原问题也可能无可行解。 - 原问题有可行解而对偶问题无可行解，则原问题为无界解，反之亦然。