Compute the minimal value of
$$x_1 + 2x_2 + 3x_3$$
when $x_1$, $x_2$, $x_3$ satisfy
$$x_1 − 2x_2 + x_3 = 4$$
$$−x_1 + 3x_2 = 5$$
and
$$x_1 \ge 0, \qquad x_2 \ge 0, \qquad x_3 \ge 0$$
I thought of using Fourier-Motzkin elimination, but we only worked with inequalities.
Should I implement an extra variable on $x_1 + 2x_2 + 3x_3$, so $x_1 + 2x_2 + 3x_3 = z$, and handle the task in this way? I am a bit confused. It is first time i work with Fourier-Motzkin, so I hope you will be gentle against me :)
Why use Fourier-Motzkin?
The conjunction of the two equality constraints defines the intersection of two planes in $\mathbb R^3$. As these two planes are not parallel, their intersection is a line. Given the nonnegativity constraints, we intersect this line with the nonnegative octant, which produces a line segment in $(\mathbb{R}_0^+)^3$.
From the two equality constraints, we have the linear system
$$\begin{bmatrix} 1 & -2 & 1\\ -1 & 3 & 0\end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ x_3\end{bmatrix} = \begin{bmatrix} 4\\ 5\end{bmatrix}$$
whose solution is the line parametrized by
$$\begin{bmatrix} x_1\\ x_2\\ x_3\end{bmatrix} = \begin{bmatrix} 22\\ 9\\ 0\end{bmatrix} + \gamma \begin{bmatrix} -3\\ -1\\ 1\end{bmatrix}$$
From the nonnegativity constraints,
$$\begin{bmatrix} 22\\ 9\\ 0\end{bmatrix} + \gamma \begin{bmatrix} -3\\ -1\\ 1\end{bmatrix} \geq \begin{bmatrix} 0\\ 0\\ 0\end{bmatrix}$$
we obtain
$$0 \leq \gamma \leq \min \left(\frac{22}{3}, 9\right) = \frac{22}{3}$$
The objective function is
$$f (\gamma) := (22 - 3 \gamma) + 2 (9 - \gamma) + 3 (0 + \gamma) = 40 - 2 \gamma$$
Since
$$f \left(\left[0,\frac{22}{3}\right]\right) = \left[\frac{76}{3}, 40\right]$$
the minimum is $\dfrac{76}{3}$, which is attained at the boundary of the nonnegative octant
$$\begin{bmatrix} 22\\ 9\\ 0\end{bmatrix} + \frac{22}{3} \begin{bmatrix} -3\\ -1\\ 1\end{bmatrix} = \begin{bmatrix} 0\\ \frac{5}{3}\\ \frac{22}{3}\end{bmatrix}$$