线性规划单纯形法求解示例
字数 2836 2025-10-25 16:02:02
线性规划单纯形法求解示例
题目描述：
求解以下线性规划问题：
最大化目标函数：\(z = 3x_1 + 2x_2\)
约束条件：
- \(2x_1 + x_2 \leq 100\)
- \(x_1 + x_2 \leq 80\)
- \(x_1 \leq 40\)
- \(x_1, x_2 \geq 0\)
解题步骤：
1. 标准化问题
将不等式约束转化为等式，引入松弛变量 \(s_1, s_2, s_3 \geq 0\)：
- \(2x_1 + x_2 + s_1 = 100\)
- \(x_1 + x_2 + s_2 = 80\)
- \(x_1 + s_3 = 40\)
目标函数变为：\(z - 3x_1 - 2x_2 = 0\)
2. 构造初始单纯形表
| 基变量 | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(s_3\) | 右端项 |
|---|---|---|---|---|---|---|
| \(s_1\) | 2 | 1 | 1 | 0 | 0 | 100 |
| \(s_2\) | 1 | 1 | 0 | 1 | 0 | 80 |
| \(s_3\) | 1 | 0 | 0 | 0 | 1 | 40 |
| \(z\) | -3 | -2 | 0 | 0 | 0 | 0 |
3. 选择进基变量
在 \(z\) 行中，找最负的系数（最大化问题）。\(x_1\) 的系数为 -3，比 \(x_2\) 的 -2 更小，故 \(x_1\) 进基。
4. 选择离基变量
计算右端项与进基变量列系数的比值（仅正系数参与）：
- \(s_1\): \(100 / 2 = 50\)
- \(s_2\): \(80 / 1 = 80\)
- \(s_3\): \(40 / 1 = 40\)（最小比值）
最小比值对应 \(s_3\)，故 \(s_3\) 离基。
5. 行变换（主元在 \(x_1\) 列、\(s_3\) 行）
- 将主元行（\(s_3\) 行）除以主元系数 1，使主元变为 1：
\(x_1 + 0 \cdot x_2 + 0 \cdot s_1 + 0 \cdot s_2 + 1 \cdot s_3 = 40\) - 更新其他行，使主元列除主元外均为 0：
- \(s_1\) 行：原行 \(-2 \times\) 新主元行 → \(s_1\) 新行：\(0x_1 + x_2 + s_1 + 0s_2 - 2s_3 = 20\)
- \(s_2\) 行：原行 \(-1 \times\) 新主元行 → \(s_2\) 新行：\(0x_1 + x_2 + 0s_1 + s_2 - 1s_3 = 40\)
- \(z\) 行：原行 \(+3 \times\) 新主元行 → \(z\) 新行：\(0x_1 - 2x_2 + 0s_1 + 0s_2 + 3s_3 = 120\)
6. 更新单纯形表（第一次迭代后）
| 基变量 | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(s_3\) | 右端项 |
|---|---|---|---|---|---|---|
| \(s_1\) | 0 | 1 | 1 | 0 | -2 | 20 |
| \(s_2\) | 0 | 1 | 0 | 1 | -1 | 40 |
| \(x_1\) | 1 | 0 | 0 | 0 | 1 | 40 |
| \(z\) | 0 | -2 | 0 | 0 | 3 | 120 |
7. 第二次迭代
- \(z\) 行中 \(x_2\) 的系数为 -2（仍为负），故 \(x_2\) 进基。
- 比值测试（右端项 / \(x_2\) 列系数）：
\(s_1\): \(20 / 1 = 20\)，\(s_2\): \(40 / 1 = 40\)，最小比值为 20，对应 \(s_1\) 离基。 - 主元行（\(s_1\) 行）系数已为 1，直接用于消元：
- \(s_2\) 行减去 \(s_1\) 新行：\(0x_1 + 0x_2 + 0s_1 + 1s_2 + 1s_3 = 20\)
- \(x_1\) 行不变（因 \(x_2\) 系数为 0）
- \(z\) 行加 \(2 \times s_1\) 新行：\(0x_1 + 0x_2 + 0s_1 + 0s_2 + (-1)s_3 = 160\)
8. 最终单纯形表
| 基变量 | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(s_3\) | 右端项 |
|---|---|---|---|---|---|---|
| \(x_2\) | 0 | 1 | 1 | 0 | -2 | 20 |
| \(s_2\) | 0 | 0 | -1 | 1 | 1 | 20 |
| \(x_1\) | 1 | 0 | 0 | 0 | 1 | 40 |
| \(z\) | 0 | 0 | 2 | 0 | -1 | 160 |
9. 解读结果
- \(z\) 行所有非基变量系数非负，达到最优解。
- 基变量值：\(x_1 = 40, x_2 = 20, s_2 = 20\)（\(s_1 = s_3 = 0\)）
- 最大值：\(z = 3 \times 40 + 2 \times 20 = 160\)
结论：最优解为 \(x_1 = 40, x_2 = 20\)，目标函数最大值为 160。