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

首先将不等式约束转化为等式约束，引入松弛变量$x_4,x_5,x_6$，得到以下等价的线性规划问题：

max $z=10x_1+15x_2+12x_3$

s.t. $5x_1+3x_2+x_3+x_4=9$

$-5x_1+6x_2+15x_3+x_5=15$

$2x_1+x_2+x_3-x_6=5$

$x_1,x_2,x_3,x_4,x_5,x_6\geq0$

然后构造初始单纯形表：

| 基变量 | $x_1$ | $x_2$ | $x_3$ | $x_4$ | $x_5$ | $x_6$ | 常数 | | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | | $x_4$ | 5 | 3 | 1 | 1 | 0 | 0 | 9 | | $x_5$ | -5 | 6 | 15 | 0 | 1 | 0 | 15 | | $x_6$ | 2 | 1 | 1 | 0 | 0 | -1 | 5 | | 目标函数 | 10 | 15 | 12 | 0 | 0 | 0 | 0 |

首先进行第一阶段求解，将目标函数改为$z'=-x_4-x_5-x_6$，并求解最小化$z'$的问题。构造新的单纯形表：

| 基变量 | $x_1$ | $x_2$ | $x_3$ | $x_4$ | $x_5$ | $x_6$ | 常数 | | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | | $x_4$ | 5 | 3 | 1 | 1 | 0 | 0 | 9 | | $x_5$ | -5 | 6 | 15 | 0 | 1 | 0 | 15 | | $x_6$ | 2 | 1 | 1 | 0 | 0 | -1 | 5 | | $z'$ | 0 | 0 | 0 | -1 | -1 | -1 | 0 |

选取$B={x_4,x_5,x_6}$作为初始基，计算出基变量的系数矩阵$B^{-1}$：

$B^{-1}=\begin{bmatrix}1 & 0 & 1\0 & 1 & -3\-2 & -1 & 6\end{bmatrix}$

计算出各个非基变量的单位贡献$C_j-z'_j$：

$C_1-z'_1=10$

$C_2-z'_2=15$

$C_3-z'_3=12$

$C_4-z'_4=1$

$C_5-z'_5=1$

$C_6-z'_6=1$

可以看到，$C_4-z'_4=C_5-z'_5=C_6-z'_6=1$，不为0，说明还存在非基变量可以进入基变量。选取$C_4-z'4$最小的$x_4$作为入基变量，计算出各个基变量的离基变量的比值$b_i/a{i4}$：

$b_1/a_{14}=9/1=9$

$b_2/a_{25}=15/1=15$

$b_3/a_{36}=5/(-1)=-5$

可以看到，$b_3/a_{36}$为负数，说明该约束并不满足，需要进行人工变量的处理。将$x_4$替换为$x_7$，将$x_7$添加到基变量中，得到以下单纯形表：

| 基变量 | $x_1$ | $x_2$ | $x_3$ | $x_7$ | $x_5$ | $x_6$ | 常数 | | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | | $x_7$ | 1 | 0 | 0 | 1 | 0 | 0 | 9 | | $x_5$ | 0 | 6 | 15 | 0 | 1 | 0 | 15 | | $x_6$ | 0 | 1 | 1 | 0 | 0 | -1 | -1 | | $z'$ | 0 | 0 | 0 | 1 | -1 | -1 | 0 |

选取$B={x_5,x_6,x_7}$作为初始基，计算出基变量的系数矩阵$B^{-1}$：

$B^{-1}=\begin{bmatrix}0 & -1 & 5/6\0 & 1 & -15/6\1 & 0 & -1\end{bmatrix}$

计算出各个非基变量的单位贡献$C_j-z'_j$：

$C_1-z'_1=10$

$C_2-z'_2=15$

$C_3-z'_3=12$

$C_5-z'_5=-1$

$C_6-z'_6=-1$

可以看到，$C_5-z'_5=C_6-z'_6=-1$，为负数，说明还存在非基变量可以进入基变量。选取$C_5-z'5$最小的$x_5$作为入基变量，计算出各个基变量的离基变量的比值$b_i/a{i5}$：

$b_1/a_{15}=9/3=3$

$b_2/a_{25}=15/1=15$

$b_3/a_{35}=-1/0$，说明该约束对目标函数已经没有限制作用了。

可以看到，$b_3/a_{35}$为无穷大，说明该约束对目标函数已经没有限制作用了，可以将$x_5$替换回$x_4$，得到以下单纯形表：

| 基变量 | $x_1$ | $x_2$ | $x_3$ | $x_4$ | $x_6$ | $x_7$ | 常数 | | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | | $x_4$ | 5 | 3 | 1 | 1 | 0 | 0 | 9 | | $x_5$ | -5 | 6 | 15 | 0 | 0 | 0 | 15 | | $x_6$ | 2 | 1 | 1 | 0 | -1 | 0 | 1 | | $z'$ | 0 | 0 | 0 | 1 | -1 | -1 | 0 |

选取$B={x_4,x_6,x_7}$作为初始基，计算出基变量的系数矩阵$B^{-1}$：

$B^{-1}=\begin{bmatrix}1 & 0 & 1\0 & -1 & 3\-2 & 1 & -1\end{bmatrix}$

计算出各个非基变量的单位贡献$C_j-z'_j$：

$C_1-z'_1=10$

$C_2-z'_2=15$

$C_3-z'_3=12$

$C_5-z'_5=-1$

$C_6-z'_6=0$

可以看到，$C_5-z'_5=-1$，为负数，说明还存在非基变量可以进入基变量。选取$C_5-z'5$最小的$x_5$作为入基变量，计算出各个基变量的离基变量的比值$b_i/a{i5}$：

$b_1/a_{15}=9/3=3$

$b_2/a_{25}=15/6=2.5$

$b_3/a_{35}=1/15=-0.067$

可以看到，$b_3/a_{35}$为负数，说明$x_5$的入基会使得$x_3$的离基，不满足约束条件，因此该线性规划问题无可行解。

综上所述，该线性规划问题无可行解。