单纯形表法求解线性规划问题

首先将目标函数转化为标准形式： max z = 10x1 + 15x2 + 12x3 - Mx7 = -10x1 - 15x2 - 12x3 + Mx7 (由于是最大化问题，将目标函数取反，即转化为最小化问题) s.t. 5x1 + 3x2 + x3 + x4 = 9 -5x1 + 6x2 + 15x3 + x5 = 15 2x1 + x2 + x3 - x6 + x7 = 5 x1, x2, ..., x7 ≥ 0

引入松弛变量，得到增广矩阵： [ 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 ]

选取入基变量，可以发现第一行的系数最小，即x3为入基变量。为了让第一列的系数为1，需要将第一行除以5，得到： [ 1 0 1/5 1/5 0 0 0 | 9/5 ] [ 0 1 3 1/5 1 0 0 | 24/5 ] [ 0 0 3/5 -2/5 0 -1 1 | 1/5 ] [ 0 0 6/5 -2/5 0 0 -M | -9/5 ]

接着选取出基变量，由于第三行的最小值为-2/5，因此x6为出基变量。将第三行除以-2/5得到： [ 1 0 1/5 1/5 0 2/5 1/5 | 11/5 ] [ 0 1 3 1/5 1 2/5 -1/5 | 34/5 ] [ 0 0 1 -3/2 0 2/5 -2/5 | -1/2 ] [ 0 0 6/5 2/5 0 6/5 -2/5M| -9/5 ]

再选取入基变量，可以发现第三行的系数最小，即x1为入基变量。为了让第一列的系数为1，需要将第三行除以1，得到： [ 1 0 1/5 1/5 0 2/5 1/5 | 11/5 ] [ 0 1 3 1/5 1 2/5 -1/5 | 34/5 ] [ 0 0 1 -3/2 0 2/5 -2/5 | -1/2 ] [ 0 0 0 5/2 0 3/5 -7/10M | -13/10 ]

由于最后一行的系数均为非负，因此达到最优解。解为： x1 = 11/5, x2 = 34/5, x3 = 1/2, x4 = 0, x5 = 0, x6 = 0, x7 = 0 最大值为z = -(-10x1 - 15x2 - 12x3 + Mx7) = 10(11/5) + 15(34/5) + 12(1/2) = 233/5。