单纯形法求解线性规划问题 - 以 max z = 10x1+15x2+12x3-Mx7 为例

首先将目标函数转化为标准形式，即：

max z = 10x1 + 15x2 + 12x3 - Mx7

转化为：

max z = 10x1 + 15x2 + 12x3 + 0x4 + 0x5 + 0x6 - Mx7

然后再将约束条件转化为等式形式：

5x1 + 3x2 + x3 + x4 = 9 -5x1 + 6x2 + 15x3 + x5 = 15 2x1 + x2 + x3 - x6 + x7 = 5

构造单纯形表：

基变量 x1 x2 x3 x4 x5 x6 x7 b
5 3 1 1 0 0 0 9
-5 6 15 0 1 0 0 15
2 1 1 0 0 -1 1 5
-10 -15 -12 0 0 0 M 0

首先选择x2作为入基变量，x4作为出基变量。

进行高斯消元法，得到新的单纯形表：

基变量 x1 x4 x3 x2 x5 x6 x7 b
1 1/3 1/5 0 0 0 0 3
0 19/3 76/5 1 0 0 0 12
0 2/3 3/5 0 0 -1 1 1
0 -5/3 -6/5 0 0 0 M 45

继续选择x3作为入基变量，x5作为出基变量。

进行高斯消元法，得到新的单纯形表：

基变量 x1 x4 x5 x2 x3 x6 x7 b
1 1/3 0 0 1/5 0 -1/5 4
0 19/3 0 1 -76/5 0 19/5 3
0 2/3 0 0 -3/5 -1 2/5 2
0 -5/3 1 0 6/5 0 -M/5 9

此时目标函数已经达到最大值，即z=174/M。

因为M无穷大，所以最优解为z=0，x1=4，x2=0，x3=2，x4=0，x5=3，x6=0，x7=0。