双单纯形法最优解咨询：线性规划问题转化结果及求解指导

首先，先明确你给出的原线性规划问题：
$$\min(z_k) = -2x_1 + 7x_2$$
约束条件：
$$x_1 + x_2 - x_4 = 2$$
$$2x_1 + 7x_2 = 3$$
$$x_i \geq 0 \quad (i=1,2,4)$$

一、你的当前结果存在的问题 #

你给出的最终形式有几个明显的错误和不合理之处：

• 目标函数 max(W)=2Π + 4Π + 3Π 表述不规范，没有明确对偶变量的对应关系，原问题约束的右端项是2和3，正确的对偶目标函数应该是针对对应约束的对偶变量构建的，比如max W = 2Π₁ + 3Π₂（Π₁对应第一个等式约束，Π₂对应第二个）。
• 约束中引入了x₃⁺和x₃⁻变量，但原问题里并没有x₃相关的约束，这属于多余的变量引入。而且x^{+}_{3} → +Π_{3} ≤ -3和x^{-}_{3} → -Π_{3} ≤ 3这两个约束等价于Π₃ = -3，完全没有必要——因为原问题的约束都是等式，对应的对偶变量应该是自由变量（可正可负），不需要拆分成正负变量。

二、正确的求解步骤与结论 #

我们先从原问题的可行性检查入手，这是双单纯形法的核心前提：

1. 检查原问题的可行性
   联立两个等式约束：
   $$\begin{cases}
   x_1 + x_2 = 2 + x_4 \
   2x_1 + 7x_2 = 3
   \end{cases}$$
   用消元法求解：将第一个式子乘以2，得到2x₁ + 2x₂ = 4 + 2x₄，减去第二个式子可得：
   $$-5x_2 = 1 + 2x_4$$
   整理得：$$x_2 = -\frac{1 + 2x_4}{5}$$
   因为x₂ ≥ 0且x₄ ≥ 0，所以1 + 2x₄ ≥ 1 > 0，这会导致x₂为负数，直接违反非负约束。这说明原问题没有可行解。

2. 结合对偶理论验证结论
   根据线性规划的对偶理论，原问题无可行解时，对偶问题要么无界，要么也无可行解。我们构建正确的对偶问题：
   $$\max W = 2\Pi_1 + 3\Pi_2$$
   约束条件：
   $$\Pi_1 + 2\Pi_2 \geq -2 \quad (\text{对应原变量} \ x_1)$$
   $$\Pi_1 + 7\Pi_2 \geq 7 \quad (\text{对应原变量} \ x_2)$$
   $$-\Pi_1 \geq 0 \quad (\text{对应原变量} \ x_4)$$
   $$\Pi_1, \Pi_2 \text{为自由变量} \quad (\text{因为原约束是等式})$$
   观察对偶约束：当Π₂ → +∞，且Π₁ = 0时，所有约束都满足（0+2Π₂≥-2、0+7Π₂≥7、0≤0），此时目标函数W = 3Π₂ → +∞，说明对偶问题是无界解，这也进一步验证了原问题无可行解的结论。

所以，你的原线性规划问题不存在可行解，自然也没有最优解。

内容的提问来源于stack exchange，提问作者Harton