问题描述
假设我们有一个线性规划问题如下：
目标函数：
最小化 \( Z = 3x_1 + 2x_2 \)
约束条件：
\[
\begin{align}
x_1 + x_2 &\geq 4 \\
2x_1 + x_2 &\leq 5 \\
x_1, x_2 &\geq 0
\end{align}
\]
步骤1：标准化问题
首先，将不等式约束转换为等式约束。对于第一个约束 \( x_1 + x_2 \geq 4 \)，引入一个松弛变量 \( s_1 \) 并将其改写为：
\[
x_1 + x_2 - s_1 = 4
\]
同时，为了处理非标准形式（即不等式方向），我们引入一个人工变量 \( a_1 \)，使得：
\[
x_1 + x_2 - s_1 + a_1 = 4
\]
第二个约束 \( 2x_1 + x_2 \leq 5 \) 已经是标准形式，因此只需添加一个松弛变量 \( s_2 \)：
\[
2x_1 + x_2 + s_2 = 5
\]
最终的标准形式为：
\[
\begin{align}
Z &= 3x_1 + 2x_2 \\
x_1 + x_2 - s_1 + a_1 &= 4 \\
2x_1 + x_2 + s_2 &= 5 \\
x_1, x_2, s_1, s_2, a_1 &\geq 0
\end{align}
\]
步骤2：构造初始单纯形表
在单纯形法中，我们需要构造初始基可行解。为此，选择 \( a_1 \) 和 \( s_2 \) 作为初始基变量，对应的初始值分别为 4 和 5。其他变量的初始值均为 0。
初始单纯形表如下：
| 基变量 | \( x_1 \) | \( x_2 \) | \( s_1 \) | \( s_2 \) | \( a_1 \) | 右侧 |
|--------|------------|------------|------------|------------|------------|-------|
| \( s_1 \) | -1 | -1 | 1| 0| -1 | -4|
| \( s_2 \) | -2 | -1 | 0| 1| 0| -5|
| \( Z \) | -3 | -2 | 0| 0| 0| 0 |
步骤3：计算检验数
检验数的计算公式为：
\[
\text{检验数} = c_j - \sum c_i \cdot a_{ij}
\]
其中 \( c_j \) 是目标函数中对应变量的系数，\( a_{ij} \) 是单纯形表中相应列的系数。
计算得到检验数：
\[
\begin{align}
\text{检验数}_{x_1} &= -3 - (-1)(-1) - (-2)(-2) = -6 \\
\text{检验数}_{x_2} &= -2 - (-1)(-1) - (-2)(-1) = -5 \\
\text{检验数}_{s_1} &= 0 - (-1)(1) - (-2)(0) = 1 \\
\text{检验数}_{s_2} &= 0 - (-1)(0) - (-2)(1) = 2 \\
\text{检验数}_{a_1} &= 0 - (-1)(-1) - (-2)(0) = -1
\end{align}
\]
步骤4：选择入基变量和出基变量
根据检验数，选择具有最大负值的变量作为入基变量。这里 \( x_1 \) 的检验数为 -6，是最小的负值，因此 \( x_1 \) 为入基变量。
接下来，确定出基变量。使用最小比值法则：
\[
\text{最小比值} = \min\left(\frac{\text{右侧值}}{\text{对应列的正系数}}\right)
\]
计算比值：
\[
\frac{4}{1} = 4, \quad \frac{5}{2} = 2.5
\]
因此，\( s_2 \) 为出基变量。
步骤5：更新单纯形表
通过高斯消元法更新单纯形表，得到新的表如下：
| 基变量 | \( x_1 \) | \( x_2 \) | \( s_1 \) | \( s_2 \) | \( a_1 \) | 右侧 |
|--------|------------|------------|------------|------------|------------|-------|
| \( x_1 \) | 1| 0.5| -0.5 | 0.5| -0.5 | 2.5 |
| \( s_2 \) | 0| 0| 1| 1| 1| 2.5 |
| \( Z \) | 0| -0.5 | 1.5| 1.5| 1.5| 7.5 |
重复上述步骤，直到所有检验数非负为止。最终得到最优解为：
\[
x_1 = 2.5, \quad x_2 = 1.5, \quad Z = 7.5
\]
结论
通过单纯形法和大M法的结合应用，我们成功解决了该线性规划问题，并得到了最优解 \( x_1 = 2.5, x_2 = 1.5 \)，最小化目标函数值为 \( Z = 7.5 \)。这种方法不仅适用于理论研究，也在实际问题中有广泛应用。
