Problem 39. Minimize $\boldsymbol{F}=\boldsymbol{x}_{2}-\boldsymbol{x}_{1}$ for non-negative $x_{1}$ and $x_{2}$, satisfying the system of constraints:

$$
\left\{\begin{aligned}
-2 x_{1}+x_{2}+x_{3} & =2 \\
x_{1}-2 x_{2}+x_{4} & =2 \\
x_{1}+x_{2}+x_{5} & =5
\end{aligned}\right.
$$

56
## S o l u t i o n.

These constraints can be considered as derived from inequalities, since each of the variables $x_{3}, x_{4}, x_{5}$ appears only in one equation.

1. Write the constraints as equations expressing the basic variables in terms of the non-basic variables:

$$
\left\{\begin{array}{l}
x_{3}=2+2 x_{1}-x_{2} \\
x_{4}=2-x_{1}+2 x_{2} \\
x_{5}=5-x_{1}-x_{2}
\end{array}\right.
$$

The basis B consists of the variables $x_{3}, x_{4}, x_{5}$. It corresponds to the basic non-negative solution $(0 ; 0 ; 2 ; 2 ; 5)$.

Now we need to express $F$ in terms of the non-basic variables. In our specific case, this has already been done.

2. Check if the objective function has reached its minimum value. The coefficient of $x_{1}$ in the expression for $F$ is negative. Therefore, increasing $x_{1}$ will further decrease $F$. However, as the value of $x_{1}$ increases, the values of $x_{4}$ and $x_{5}$ will decrease, and it is necessary to ensure that none of them become negative. Since increasing the value of $x_{1}$ leads to an increase in the value of $x_{3}$, there is no such danger for this variable. From the analysis of the other variables, we find that the value of $x_{1}$ can only be increased to 2. Such an increase gives $x_{4}=0, x_{3}=6, x_{5}=3$.

The new basis B consists of $x_{1}, x_{3}, x_{5}$.

3. To proceed to the next step, express these variables and the objective function in terms of the non-basic variables $x_{2}$ and $x_{4}$. For this, first solve the second equation of the system (2) for the new basic variable $x_{1}$:

$$
x_{1}=2+2 x_{2}-x_{4}
$$

Substituting this expression into the other equations and the objective function gives:

$$
\begin{aligned}
& x_{3}=6+3 x_{2}-2 x_{4} \\
& x_{5}=3-3 x_{2}+x_{4} \\
& F=-2-x_{2}+x_{4}
\end{aligned}
$$

4. We can further decrease the objective function $F$ by increasing the value of $x_{2}$. However, $x_{2}$ can only be increased to 1: this follows from the equation $x_{5}=3-3 x_{2}+x_{4}$. Substituting $x_{2}=1$ into the other equations gives $x_{1}=4, x_{3}=9$. Once again, express the basic variables and $F$ in terms of the non-basic variables:

$$
\begin{aligned}
& \left\{\begin{array}{l}
x_{1}=4-\frac{1}{3} x_{4}-\frac{2}{3} x_{5} \\
x_{2}=1+\frac{1}{3} x_{4}-\frac{1}{3} x_{5} \\
x_{3}=9-x_{4}-x_{5}
\end{array}\right. \\
& F=-3+\frac{2}{3} x_{4}+\frac{1}{3} x_{5}
\end{aligned}
$$

The basis B consists of the variables $x_{1}, x_{2}, x_{3}$.

5. By increasing the values of $x_{4}$ and $x_{5}$, we can no longer achieve a further decrease in $F$. Therefore, we have obtained the optimal solution.

The minimum value of $F$, equal to -3, is achieved at $x_{1}=4$, $x_{2}=1, x_{3}=9$.

Compare the values of the objective function corresponding to different bases:

$$
\begin{gathered}
F_{\mathrm{B}}=5, F_{\mathrm{b}^{\prime}}=-2, F_{\mathrm{E}^{\prime \prime}}=-3 \\
-3<-2<5
\end{gathered}
$$