线性规划问题求解：二阶段法应用与无解判定

首先将不等式约束转化为等式约束，引入松弛变量$x_4,x_5,x_6$，得到以下等价的线性规划问题：/n/nmax $z=10x_1+15x_2+12x_3$/n/ns.t. $5x_1+3x_2+x_3+x_4=9$/n/n$-5x_1+6x_2+15x_3+x_5=15$/n/n$2x_1+x_2+x_3-x_6=5$/n/n$x_1,x_2,x_3,x_4,x_5,x_6/geq0$/n/n然后构造初始单纯形表：/n/n| 基变量 | $x_1$ | $x_2$ | $x_3$ | $x_4$ | $x_5$ | $x_6$ | 常数 |/n| ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ |/n| $x_4$ | 5 | 3 | 1 | 1 | 0 | 0 | 9 |/n| $x_5$ | -5 | 6 | 15 | 0 | 1 | 0 | 15 |/n| $x_6$ | 2 | 1 | 1 | 0 | 0 | -1 | 5 |/n| 目标函数 | 10 | 15 | 12 | 0 | 0 | 0 | 0 |/n/n首先进行第一阶段求解，将目标函数改为$z'=-x_4-x_5-x_6$，并求解最小化$z'$的问题。构造新的单纯形表：/n/n| 基变量 | $x_1$ | $x_2$ | $x_3$ | $x_4$ | $x_5$ | $x_6$ | 常数 |/n| ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ |/n| $x_4$ | 5 | 3 | 1 | 1 | 0 | 0 | 9 |/n| $x_5$ | -5 | 6 | 15 | 0 | 1 | 0 | 15 |/n| $x_6$ | 2 | 1 | 1 | 0 | 0 | -1 | 5 |/n| $z'$ | 0 | 0 | 0 | -1 | -1 | -1 | 0 |/n/n选取$B={x_4,x_5,x_6}$作为初始基，计算出基变量的系数矩阵$B^{-1}$：/n/n$B^{-1}=//begin{bmatrix}1 & 0 & 1//0 & 1 & -3//-2 & -1 & 6//end{bmatrix}$/n/n计算出各个非基变量的单位贡献$C_j-z'_j$：/n/n$C_1-z'_1=10$/n/n$C_2-z'_2=15$/n/n$C_3-z'_3=12$/n/n$C_4-z'_4=1$/n/n$C_5-z'_5=1$/n/n$C_6-z'6=1$/n/n可以看到，$C_4-z'4=C_5-z'5=C_6-z'6=1$，不为0，说明还存在非基变量可以进入基变量。选取$C_4-z'4$最小的$x_4$作为入基变量，计算出各个基变量的离基变量的比值$b_i/a{i4}$：/n/n$b_1/a{14}=9/1=9$/n/n$b_2/a{25}=15/1=15$/n/n$b_3/a{36}=5/(-1)=-5$/n/n可以看到，$b_3/a{36}$为负数，说明该约束并不满足，需要进行人工变量的处理。将$x_4$替换为$x_7$，将$x_7$添加到基变量中，得到以下单纯形表：/n/n| 基变量 | $x_1$ | $x_2$ | $x_3$ | $x_7$ | $x_5$ | $x_6$ | 常数 |/n| ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ |/n| $x_7$ | 1 | 0 | 0 | 1 | 0 | 0 | 9 |/n| $x_5$ | 0 | 6 | 15 | 0 | 1 | 0 | 15 |/n| $x_6$ | 0 | 1 | 1 | 0 | 0 | -1 | -1 |/n| $z'$ | 0 | 0 | 0 | 1 | -1 | -1 | 0 |/n/n选取$B={x_5,x_6,x_7}$作为初始基，计算出基变量的系数矩阵$B^{-1}$：/n/n$B^{-1}=//begin{bmatrix}0 & -1 & 5/6//0 & 1 & -15/6//1 & 0 & -1//end{bmatrix}$/n/n计算出各个非基变量的单位贡献$C_j-z'_j$：/n/n$C_1-z'_1=10$/n/n$C_2-z'_2=15$/n/n$C_3-z'_3=12$/n/n$C_5-z'5=-1$/n/n$C_6-z'6=-1$/n/n可以看到，$C_5-z'5=C_6-z'6=-1$，为负数，说明还存在非基变量可以进入基变量。选取$C_5-z'5$最小的$x_5$作为入基变量，计算出各个基变量的离基变量的比值$b_i/a{i5}$：/n/n$b_1/a{15}=9/3=3$/n/n$b_2/a{25}=15/1=15$/n/n$b_3/a{35}=-1/0$，说明该约束对目标函数已经没有限制作用了。/n/n可以看到，$b_3/a{35}$为无穷大，说明该约束对目标函数已经没有限制作用了，可以将$x_5$替换回$x_4$，得到以下单纯形表：/n/n| 基变量 | $x_1$ | $x_2$ | $x_3$ | $x_4$ | $x_6$ | $x_7$ | 常数 |/n| ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ |/n| $x_4$ | 5 | 3 | 1 | 1 | 0 | 0 | 9 |/n| $x_5$ | -5 | 6 | 15 | 0 | 0 | 0 | 15 |/n| $x_6$ | 2 | 1 | 1 | 0 | -1 | 0 | 1 |/n| $z'$ | 0 | 0 | 0 | 1 | -1 | -1 | 0 |/n/n选取$B={x_4,x_6,x_7}$作为初始基，计算出基变量的系数矩阵$B^{-1}$：/n/n$B^{-1}=//begin{bmatrix}1 & 0 & 1//0 & -1 & 3//-2 & 1 & -1//end{bmatrix}$/n/n计算出各个非基变量的单位贡献$C_j-z'_j$：/n/n$C_1-z'_1=10$/n/n$C_2-z'_2=15$/n/n$C_3-z'3=12$/n/n$C_5-z'5=-1$/n/n$C_6-z'6=0$/n/n可以看到，$C_5-z'5=-1$，为负数，说明还存在非基变量可以进入基变量。选取$C_5-z'5$最小的$x_5$作为入基变量，计算出各个基变量的离基变量的比值$b_i/a{i5}$：/n/n$b_1/a{15}=9/3=3$/n/n$b_2/a{25}=15/6=2.5$/n/n$b_3/a{35}=1/15=-0.067$/n/n可以看到，$b_3/a{35}$为负数，说明$x_5$的入基会使得$x_3$的离基，不满足约束条件，因此该线性规划问题无可行解。/n/n综上所述，该线性规划问题无可行解。