线性规划单纯形法求解步骤详解 - 以实例演示

首先将线性规划转化为标准型：

min Z = x1 + x2

s.t.

3x1 + x2 + x3 = 6

x1 + x2 + x4 = 4

x1 + 3x2 + x5 = 6

x1, x2, x3, x4, x5 >= 0

构造初始单纯形表：

| x1 | x2 | x3 | x4 | x5 | RHS | --|----|----|----|----|----|-----| x3| 3 | 1 | 1 | 0 | 0 | 6 | x4| 1 | 1 | 0 | 1 | 0 | 4 | x5| 1 | 3 | 0 | 0 | 1 | 6 | Z | -1 | -1 | 0 | 0 | 0 | 0 |

选择进入变量为x1，离开变量为x4。

进行一次单纯形迭代：

| x1 | x2 | x3 | x4 | x5 | RHS | --|----|----|----|----|----|-----| x3| 0 | 1/3| 1 |-1/3| 0 | 2 | x1| 1 | 1 | 0 | 1 | 0 | 4 | x5| 0 | 8/3| 0 |-1/3| 1 | 2 | Z | 0 | -2 | 0 | 1 | 0 | -4 |

目标函数系数x1的系数为正，说明还需要进行迭代。

选择进入变量为x2，离开变量为x3。

进行一次单纯形迭代：

| x1 | x2 | x3 | x4 | x5 | RHS | --|----|----|----|----|----|-----| x2| 0 | 1 | 3 |-1 | 0 | 2 | x1| 1 | 0 |-1 | 1 | 0 | 2 | x5| 0 | 0 |8/3|-1/3| 1 | 2 | Z | 0 | 0 |-2 | 1 | 0 | -2 |

目标函数系数已经全部为负，达到最优解。

解为：x1=2，x2=2，Z=-2。

因此，线性规划的最优解为Z=-2，当x1=2，x2=2时取到最优解。