分别用大M法和两阶段法求解如下线性规划问题 max z =10x1+15x2+12x3 st 5x1+3x2+x3≤9 −5x1+6x2+15x3≤15 2x1+x2+x3≥5 x1x2x3 ≥0

使用大M法：

将约束条件转化为等式形式： 5x1+3x2+x3+s1=9 -5x1+6x2+15x3+s2=15 2x1+x2+x3-s3=5

引入人工变量： max z =10x1+15x2+12x3 s.t. 5x1+3x2+x3+s1=9 -5x1+6x2+15x3+s2=15 2x1+x2+x3-s3+M1=5 x1，x2，x3，s1，s2，s3，M1 ≥0

求解初始单纯形表： x1 x2 x3 s1 s2 s3 M1 b

1 5 3 1 1 0 0 0 9 2 -5 6 15 0 1 0 0 15 3 2 1 1 0 0 -1 1 5

z -10 -15 -12 0 0 0 0 0

第一次迭代： x1 x2 x3 s1 s2 s3 M1 b

1 5 3 1 1 0 0 0 9 2 -5 6 15 0 1 0 0 15 3 2 1 1 0 0 -1 1 5 4 0 0 0 0 0 1 M1 5

z -10 -15 -12 0 0 -M1 M1 -5

由于M1无限制增大，所以此时解无界。

使用两阶段法：

第一阶段： max z1 =-M1y1-M2y2-M3y3 s.t. 5x1+3x2+x3+y1=9 -5x1+6x2+15x3+y2=15 2x1+x2+x3-y3=5 x1，x2，x3，y1，y2，y3 ≥0

引入人工变量： max z1 =-M1y1-M2y2-M3y3 s.t. 5x1+3x2+x3+y1=9 -5x1+6x2+15x3+y2=15 2x1+x2+x3-y3+M4=5 x1，x2，x3，y1，y2，y3，M4 ≥0

求解初始单纯形表： x1 x2 x3 y1 y2 y3 M4 b

1 5 3 1 1 0 0 0 9 2 -5 6 15 0 1 0 0 15 3 2 1 1 0 0 -1 1 5

z1 0 0 0 -M1 -M2 -M3 0 0

第一次迭代： x1 x2 x3 y1 y2 y3 M4 b

1 5 3 1 1 0 0 0 9 2 -5 6 15 0 1 0 0 15 3 2 1 1 0 0 -1 1 5 4 0 0 0 0 0 1 M4 5

z1 0 0 0 -M1 -M2-M4 -M3-M4 M4 -5

第二阶段： max z =10x1+15x2+12x3 s.t. 5x1+3x2+x3+y1=9 -5x1+6x2+15x3+y2=15 2x1+x2+x3-y3=5 x1，x2，x3，y1，y2，y3 ≥0

求解初始单纯形表： x1 x2 x3 y1 y2 y3 b

1 5 3 1 1 0 0 9 2 -5 6 15 0 1 0 15 3 2 1 1 0 0 -1 5

z -10 -15 -12 0 0 0 0

第一次迭代： x1 x2 x3 y1 y2 y3 b

1 5 3 1 1 0 0 9 2 -5 6 15 0 1 0 15 3 2 1 1 0 0 -1 5

z -10 -15 -12 0 0 0 0

最优解为z=195，x1=3，x2=0，x3=2。