大M法例题详解：线性规划问题的求解技巧

大M法（也称为改进的单纯形法）是线性规划中的一种常用算法，用于求解约束条件为不等式的标准形式最优解。以下是一道大M法例题及详解。

例题：

maximize 2x1 + x2

subject to

x1 + x2 ≤ 6

2x1 + x2 ≤ 8

x1, x2 ≥ 0

详解：

将目标函数和约束条件转化为标准形式：

maximize 2x1 + x2

subject to

x1 + x2 + s1 = 6

2x1 + x2 + s2 = 8

x1, x2, s1, s2 ≥ 0

其中，s1和s2是人工变量，用于将不等式约束转化为等式约束。

接下来，引入大M法中的'人工变量法'：

将目标函数中的所有变量后面都加上一个很大的M，其中M为一个足够大的正数。这里我们选择M=1000。

maximize 2x1 + x2 + M(s1 + s2)

subject to

x1 + x2 + s1 = 6

2x1 + x2 + s2 = 8

x1, x2, s1, s2 ≥ 0

在第一个约束条件中，我们需要消去s1，因此引入一个新的变量a1，使得s1 = 6 - x1 - x2 - a1，同时将a1的系数设置为-M。这里注意，我们需要保证a1的系数为负数，否则可能会产生错误的结果。

maximize 2x1 + x2 + M(s1 + s2)

subject to

x1 + x2 - a1 + s1 = 6

2x1 + x2 + s2 = 8

x1, x2, s1, s2, a1 ≥ 0

同理，在第二个约束条件中，我们引入一个新的变量a2，使得s2 = 8 - 2x1 - x2 - a2，同时将a2的系数设置为-M。

maximize 2x1 + x2 + M(s1 + s2)

subject to

x1 + x2 - a1 + s1 = 6

2x1 + x2 - a2 + s2 = 8

x1, x2, s1, s2, a1, a2 ≥ 0

现在，我们需要将人工变量法中引入的人工变量去掉。为了使这些人工变量在最终解中为0，我们需要将目标函数中的人工变量的系数设置为0。这样，在求解过程中，这些人工变量将不会对解产生影响。此时，我们得到了以下线性规划问题：

maximize 2x1 + x2

subject to

x1 + x2 - a1 + s1 = 6

2x1 + x2 - a2 + s2 = 8

x1, x2, s1, s2, a1, a2 ≥ 0

使用单纯形法求解上述线性规划问题，得到最优解为x1=2，x2=4，目标函数值为10。

综上所述，大M法是求解约束条件为不等式的标准形式最优解的一种有效算法。通过引入人工变量和大M，将不等式约束转化为等式约束，再使用单纯形法求解，即可得到最优解。