证明如果标准形式的线性规划存在非退化的最优基可行解,其对偶规划必有唯一最优解
时间: 2023-06-10 08:07:43 浏览: 26
假设标准形式的线性规划为:
$$
\begin{aligned}
\text{maximize}\quad & c^T x \\
\text{subject to}\quad & Ax = b \\
& x \ge 0
\end{aligned}
$$
对应的对偶规划为:
$$
\begin{aligned}
\text{minimize}\quad & b^T y \\
\text{subject to}\quad & A^T y \ge c \\
& y \ge 0
\end{aligned}
$$
假设原问题存在一个非退化的最优基可行解 $x^*$,也就是说,$x^*$ 是一个基本可行解,且对应的基 $B$ 满秩,即 $|B|=n$,其中 $n$ 是变量的个数。
根据互补松弛性条件,对于任意的 $i$,有 $x_i^* > 0$ 当且仅当 $y_i = c_i - \sum_{j=1}^m a_{ji} y_j^*$,其中 $y^*$ 是对偶问题的最优解。
考虑对偶问题的可行解集合 $S=\{y\mid A^T y \ge c, y \ge 0\}$。我们需要证明,如果 $S$ 中存在两个最优解 $y'$ 和 $y''$,则 $y' = y''$。
假设存在 $y', y'' \in S$,满足 $b^T y' = b^T y''$,且 $y'$ 和 $y''$ 都是最优解。由于 $y'$ 和 $y''$ 都是可行解,因此对于任意的 $i$,有 $y'_i \ge 0$ 和 $y''_i \ge 0$。
根据互补松弛性条件,对于任意的 $i$,有 $x_i^* > 0$ 当且仅当 $y'_i = c_i - \sum_{j=1}^m a_{ji} y_j^*$ 和 $y''_i = c_i - \sum_{j=1}^m a_{ji} y_j^*$,其中 $y^*$ 是对偶问题的最优解。
因为 $y'$ 和 $y''$ 都是最优解,所以 $y'_i = y''_i$,即 $c_i - \sum_{j=1}^m a_{ji} y_j^* = c_i - \sum_{j=1}^m a_{ji} y_j^*$。因此,对于任意的 $i$,有 $\sum_{j=1}^m a_{ji} y_j^* = \sum_{j=1}^m a_{ji} y_j^*$。
将上式代入对偶问题的约束条件 $A^T y' \ge c$ 和 $A^T y'' \ge c$ 中,得到:
$$
\begin{aligned}
&\sum_{j=1}^m a_{ji} y_j^* \ge c_i - \sum_{j=1}^m a_{ji} y_j^*, \quad \forall i \\
&\sum_{j=1}^m a_{ji} y_j^* \ge c_i - \sum_{j=1}^m a_{ji} y_j^*, \quad \forall i
\end{aligned}
$$
将两个不等式相加,得到:
$$
2\sum_{j=1}^m a_{ji} y_j^* \ge 2c_i, \quad \forall i
$$
由于 $x^*$ 是非退化的最优基可行解,因此 $x^*$ 是唯一的最优解。因此,$y'$ 和 $y''$ 必须相等,即对偶问题存在唯一最优解。证毕。