证明:如果标准形式的 LP 存在非退化的最优基可行解,其对偶规划必有唯一 最优解
时间: 2023-06-11 16:06:43 浏览: 77
首先,非退化的最优基可行解意味着所有基变量都有非零取值,且目标函数的系数矩阵在基变量组成的子矩阵中是非奇异的。因此,该最优解的基本解是唯一的。
其次,由于标准形式的 LP 的对偶规划也是一个 LP,因此它也拥有基本解。如果对偶规划存在最优解,那么该最优解必须是可行的,并且其对应的基本解也是唯一的。因此,我们只需要证明该基本解是唯一的即可证明原命题。
假设对偶规划存在两个不同的最优解,它们对应的基本解分别为 $y_1$ 和 $y_2$。由于这两个解都是最优解,它们的目标函数值相等。因此,我们有:
$$c^Tx = y_1^TA \cdot x = y_2^TA \cdot x$$
其中,$x$ 是原问题的最优解,$A$ 是约束条件的系数矩阵,$c$ 是目标函数的系数向量。
考虑两个基本解 $y_1$ 和 $y_2$ 所对应的基向量分别为 $B_1$ 和 $B_2$。由于 $y_1$ 和 $y_2$ 是最优解,它们必须满足对偶约束条件:
$$y_1^T \cdot B_1 = 1,\ y_1^T \cdot B_2 = 0$$
$$y_2^T \cdot B_1 = 0,\ y_2^T \cdot B_2 = 1$$
因此,我们有:
$$y_1^TA \cdot B_1 = c^T \cdot B_1 = y_2^TA \cdot B_1$$
$$y_1^TA \cdot B_2 = c^T \cdot B_2 = y_2^TA \cdot B_2$$
将上面两个式子相减,我们有:
$$y_1^TA \cdot (B_1 - B_2) = y_2^TA \cdot (B_1 - B_2) = 0$$
由于 $B_1 - B_2$ 是非零的基向量,而 $A$ 是非奇异的,因此必须有 $y_1^TA = y_2^TA$。因此,我们可以得出 $y_1 = y_2$,即对偶规划的最优解是唯一的。
因此,如果标准形式的 LP 存在非退化的最优基可行解,则其对偶规划必有唯一最优解。