线性规划问题求解：大M法与两阶段法

本文将以一个具体实例讲解如何利用大M法和两阶段法求解线性规划问题。

问题描述：

求解以下线性规划问题：

max z = 10x1 + 15x2 + 12x3

s.t.

5x1 + 3x2 + x3 <= 9
-5x1 + 6x2 + 15x3 <= 15
2x1 + x2 + x3 >= 5
x1, x2, x3 >= 0

大M法求解

转化为标准形式

将约束条件转化为等式形式，引入松弛变量和人工变量，得到如下形式：

max z = 10x1 + 15x2 + 12x3

s.t.

5x1 + 3x2 + x3 + s1 = 9
-5x1 + 6x2 + 15x3 + s2 = 15
2x1 + x2 + x3 - s3 = 5
x1, x2, x3, s1, s2, s3 >= 0

引入人工变量

引入人工变量后，目标函数需要加上人工变量的系数，即：

max z = 10x1 + 15x2 + 12x3 + M(s1 + s2 + s3)

其中M为一个很大的正数，使得人工变量的系数在目标函数中不起作用。

构造初始单纯形表格

      x1   x2   x3   s1   s2   s3    RHS
-----------------------------------------
z     10   15   12    M    M    M     0
-----------------------------------------
s1     5    3    1    1    0    0     9
s2    -5    6   15    0    1    0    15
s3     2    1    1    0    0   -1     5

迭代求解

选择系数最大的M（即M的系数为1），将其所在列作为入基变量列，找到离基变量行（即系数为1的那个变量所在的行），进行初等行变换，得到新的单纯形表格。

经过多次迭代，最终得到所有M的系数都变成了0，说明人工变量可以全部离基，并得到最优解：

x1 = 20/7, x2 = 9/35, x3 = 321/70, z = 1415/7

两阶段法求解

转化为标准形式

与大M法相同，将约束条件转化为等式形式，引入松弛变量和人工变量。

第一阶段

最小化人工变量的和：

min z1 = Ms1 + Ms2 + Ms3

s.t.

5x1 + 3x2 + x3 + s1 = 9
-5x1 + 6x2 + 15x3 + s2 = 15
2x1 + x2 + x3 - s3 = 5
s1, s2, s3 >= 0

构造初始单纯形表格

      x1   x2   x3   s1   s2   s3   RHS
-----------------------------------------
z1     M    M    M    1    1    1     0
-----------------------------------------
s1     5    3    1    1    0    0     9
s2    -5    6   15    0    1    0    15
s3     2    1    1    0    0   -1     5

迭代求解

选择系数最小的人工变量（即M的系数为1），将其所在列作为入基变量列，找到离基变量行，进行初等行变换，得到新的单纯形表格。

当最优解的目标函数值为0时，第一阶段结束。

第二阶段

去掉人工变量，将目标函数和约束条件写成矩阵形式：

max z2 = 10x1 + 15x2 + 12x3

s.t.

5x1 + 3x2 + x3 = 9
-5x1 + 6x2 + 15x3 = 15
2x1 + x2 + x3 = 5
x1, x2, x3 >= 0

构造初始单纯形表格

      x1   x2   x3   RHS
--------------------------
z2    10   15   12    0
--------------------------
s1     5    3    1    9
s2    -5    6   15   15
s3     2    1    1    5

迭代求解

选择系数最大的目标函数系数，将其所在列作为入基变量列，找到离基变量行，进行初等行变换，得到新的单纯形表格。

经过多次迭代，最终得到所有系数都是非负的，所以可以停止迭代，得到最优解：

x1 = 20/7, x2 = 0, x3 = 321/70, z = 1415/7

结论

通过大M法和两阶段法，我们都得到了该线性规划问题的最优解：

x1 = 20/7, x2 = 9/35, x3 = 321/70, z = 1415/7。

这两种方法都是求解线性规划问题常用的方法，它们各有优缺点。大M法比较直观，但需要引入人工变量，可能会导致数值计算不稳定。两阶段法则更加稳定，但步骤相对复杂。在实际应用中，可以根据具体情况选择合适的求解方法。