证明如果标准形式的线性规划存在非退化的最优基可行解，其对偶规划必有唯一最优解

设标准形式的线性规划为：

$$\begin{aligned} \text{maximize} \quad & \mathbf{c}^T\mathbf{x} \\ \text{subject to} \quad & \mathbf{Ax} = \mathbf{b} \\ & \mathbf{x} \geq \mathbf{0} \end{aligned}$$

其对偶规划为：

$$\begin{aligned} \text{minimize} \quad & \mathbf{b}^T\mathbf{y} \\ \text{subject to} \quad & \mathbf{A}^T\mathbf{y} \geq \mathbf{c} \\ & \mathbf{y} \geq \mathbf{0} \end{aligned}$$

假设标准形式的线性规划存在非退化的最优基可行解，那么最优解一定位于某个基可行解上。设这个基可行解对应的基矩阵为 $\mathbf{B}$，基变量对应的解为 $\mathbf{x_B}$，非基变量对应的解为 $\mathbf{x_N}=\mathbf{0}$。则有：

$$\mathbf{x} = \begin{bmatrix} \mathbf{x_B} \\ \mathbf{0} \end{bmatrix} = \mathbf{B}^{-1}\mathbf{b}$$

由于 $\mathbf{B}$ 是一个满秩矩阵，因此 $\mathbf{B}^{-1}$ 存在。同时，根据最优性条件，有：

$$\mathbf{c}^T\mathbf{x} \leq \mathbf{c}^T\mathbf{x'}$$

其中 $\mathbf{x'}$ 是任意的可行解。代入 $\mathbf{x}$ 的表达式，可得：

$$\mathbf{c}^T\mathbf{B}^{-1}\mathbf{b} \leq \mathbf{c}^T\mathbf{B}^{-1}\mathbf{A}\mathbf{x_N}+\mathbf{c}^T\mathbf{x_B}$$

由于 $\mathbf{x_N}=\mathbf{0}$，因此：

$$\mathbf{c}^T\mathbf{B}^{-1}\mathbf{b} \leq \mathbf{c}^T\mathbf{x_B}$$

而对偶问题的最优值为 $\mathbf{b}^T\mathbf{y}^*$，其中 $\mathbf{y}^*$ 是对偶问题的最优解。对偶问题的约束条件可以写成：

$$\mathbf{A}^T\mathbf{y}^* - \mathbf{c} \geq \mathbf{0}$$

于是：

$$\mathbf{b}^T\mathbf{y}^* = \mathbf{y}^{*T}\mathbf{A}\mathbf{x} = (\mathbf{A}^T\mathbf{y}^*)^T\mathbf{x} - \mathbf{c}^T\mathbf{x} \geq -\mathbf{c}^T\mathbf{x}$$

因此：

$$\mathbf{b}^T\mathbf{y}^* \geq -\mathbf{c}^T\mathbf{B}^{-1}\mathbf{b}$$

综上所述，可得：

$$\mathbf{c}^T\mathbf{x_B} = \mathbf{b}^T\mathbf{y}^*$$

也就是说，标准形式的线性规划的最优解与其对偶规划的最优解相等，并且唯一。因此，如果标准形式的线性规划存在非退化的最优基可行解，其对偶规划必有唯一最优解。