min -4x1-x2 s.t. -x1+2x2<=4 2x1+3x2<=12 x1-x2<=3 xj>=0,j=1,2

为了解决这个线性规划问题，我们可以使用单纯形法。

首先，将变量转化为标准形式，引入松弛变量$x_3,x_4,x_5$：

min -4x1-x2

s.t.

-x1+2x2+x3=4

2x1+3x2+x4=12

x1-x2+x5=3

xj>=0,j=1,2,3,4,5

现在，我们可以将这个问题表示为一个矩阵形式：

$$
\begin{bmatrix}
-1 & 2 & 1 & 0 & 0 \\
2 & 3 & 0 & 1 & 0 \\
1 & -1 & 0 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
x_1 \\
x_2 \\
x_3 \\
x_4 \\
x_5 \\
\end{bmatrix}
=
\begin{bmatrix}
4 \\
12 \\
3 \\
\end{bmatrix}
$$

目标函数可以写成向量形式：

$$
\begin{bmatrix}
-4 & -1 & 0 & 0 & 0 \\
\end{bmatrix}
\begin{bmatrix}
x_1 \\
x_2 \\
x_3 \\
x_4 \\
x_5 \\
\end{bmatrix}
$$

接下来，我们使用单纯形法求解这个问题。

首先，选择$x_1$和$x_2$作为基本变量，将其余的变量作为非基本变量。

这意味着我们对应于单位矩阵中的列是第1列和第2列，其他列均为0。

$$
\begin{bmatrix}
-1 & 2 & 1 & 0 & 0 \\
2 & 3 & 0 & 1 & 0 \\
1 & -1 & 0 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
x_1 \\
x_2 \\
x_3 \\
x_4 \\
x_5 \\
\end{bmatrix}
=
\begin{bmatrix}
4 \\
12 \\
3 \\
\end{bmatrix}
$$

$$
\begin{bmatrix}
-4 & -1 & 0 & 0 & 0 \\
\end{bmatrix}
\begin{bmatrix}
x_1 \\
x_2 \\
x_3 \\
x_4 \\
x_5 \\
\end{bmatrix}
=0
$$

接下来，我们使用高斯-约旦消元法，对矩阵进行操作，使得$x_1$和$x_2$成为单位向量。

对第1行进行操作，将其除以-1：

$$
\begin{bmatrix}
1 & -2 & -1 & 0 & 0 \\
2 & 3 & 0 & 1 & 0 \\
1 & -1 & 0 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
x_1 \\
x_2 \\
x_3 \\
x_4 \\
x_5 \\
\end{bmatrix}
=
\begin{bmatrix}
-4 \\
12 \\
3 \\
\end{bmatrix}
$$

对第2行进行操作，将其除以2：

$$
\begin{bmatrix}
1 & -2 & -1 & 0 & 0 \\
1 & \frac{3}{2} & 0 & \frac{1}{2} & 0 \\
1 & -1 & 0 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
x_1 \\
x_2 \\
x_3 \\
x_4 \\
x_5 \\
\end{bmatrix}
=
\begin{bmatrix}
-2 \\
6 \\
\frac{3}{2} \\
\end{bmatrix}
$$

对第3行进行操作，将其减去第1行：

$$
\begin{bmatrix}
1 & -2 & -1 & 0 & 0 \\
1 & \frac{3}{2} & 0 & \frac{1}{2} & 0 \\
0 & 1 & 1 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
x_1 \\
x_2 \\
x_3 \\
x_4 \\
x_5 \\
\end{bmatrix}
=
\begin{bmatrix}
-2 \\
6 \\
\frac{7}{2} \\
\end{bmatrix}
$$

现在，$x_2$已经是基本变量了，继续使用高斯-约旦消元法。

对第1行进行操作，将其加上2倍的第2行：

$$
\begin{bmatrix}
1 & 0 & -1 & 1 & 0 \\
1 & \frac{3}{2} & 0 & \frac{1}{2} & 0 \\
0 & 1 & 1 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
x_1 \\
x_2 \\
x_3 \\
x_4 \\
x_5 \\
\end{bmatrix}
=
\begin{bmatrix}
5 \\
6 \\
\frac{7}{2} \\
\end{bmatrix}
$$

对第2行进行操作，将其减去$\frac{3}{2}$倍的第1行：

$$
\begin{bmatrix}
1 & 0 & -1 & 1 & 0 \\
0 & \frac{3}{2} & \frac{3}{2} & -\frac{1}{2} & 0 \\
0 & 1 & 1 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
x_1 \\
x_2 \\
x_3 \\
x_4 \\
x_5 \\
\end{bmatrix}
=
\begin{bmatrix}
5 \\
-\frac{3}{2} \\
\frac{7}{2} \\
\end{bmatrix}
$$

对第3行进行操作，将其减去第2行：

$$
\begin{bmatrix}
1 & 0 & -1 & 1 & 0 \\
0 & \frac{3}{2} & \frac{3}{2} & -\frac{1}{2} & 0 \\
0 & 0 & \frac{1}{2} & \frac{1}{2} & 1 \\
\end{bmatrix}
\begin{bmatrix}
x_1 \\
x_2 \\
x_3 \\
x_4 \\
x_5 \\
\end{bmatrix}
=
\begin{bmatrix}
5 \\
-\frac{3}{2} \\
-\frac{1}{2} \\
\end{bmatrix}
$$

现在，所有的系数都是非负的，意味着我们已经找到了最优解。$x_1=5,x_2=-\frac{3}{2}$，代入原问题的约束条件中，可以得到$x_3=0,x_4=\frac{15}{2},x_5=\frac{13}{2}$，最优值为$-23$。