To find the maximum value of $F=4 x_{1}+6 x_{2}$

subject to

$$
\left\{\begin{array}{c}
x_{1}+x_{2} \leqslant 18 \\
0.5 x_{1}+x_{2} \leqslant 12 \\
0 \leqslant x_{1} \leqslant 12 \\
0 \leqslant x_{2} \leqslant 9
\end{array}\right.
$$
S o l u t i o n.

This problem has already been solved graphically (see problem 32).

When solving by the simplex method, the system of constraints, consisting of inequalities, must be transformed into a system of linear equations by introducing additional variables:

$$
\begin{gathered}
x_{1}+x_{2}+x_{3}=18 \\
0.5 x_{1}+x_{2}+x_{4}=12 \\
x_{1}+x_{5}=12 \\
x_{2}+x_{6}=9 \\
x_{1} \geqslant 0, \ldots, 6 \\
i=1, \ldots, 6
\end{gathered}
$$

1. Find the basic non-negative solution of the system of constraints. Let variables $x_{3}, x_{4}, x_{5}, x_{6}$ be the basic ones, then $x_{1}$ and $x_{2}$ are non-basic:

$$
\left\{\begin{array}{l}
x_{3}=18-x_{1}-x_{2} \\
x_{4}=12-0.5 x_{1}-x_{2} \\
x_{5}=12-x_{1} \\
x_{6}=9-x_{2} \\
x_{l} \geqslant 0, i=1, \ldots, 6
\end{array}\right.
$$

The basis B consists of variables $x_{3}, x_{4}, x_{5}, x_{6}$. The basic solution is $(0 ; 0 ; 18 ; 12 ; 12 ; 9)$

$$
F_{\text {B }}=4 \cdot 0+6 \cdot 0=0
$$

2. $F$ can be increased by increasing $x_{1}$ or $x_{2}$. Let's increase, for example, $x_{2}$. From system (4), it is clear that the maximum allowable value that $x_{2}$ can take is 9. Let's transition to the basis B, consisting of $x_{3}, x_{4}, x_{5}, x_{6}$. For this, we will move the non-basic variable $x_{6}$ to the non-basic variables and introduce $x_{2}$ into the basic variables:

$$
\left\{\begin{array}{l}
x_{3}=9-x_{1}+x_{6} \\
x_{4}=3-0.5 x_{1}+x_{6} \\
x_{5}=12-x_{1} \\
x_{2}=9-x_{6} \\
x_{i} \geqslant 0, i=1, \ldots, 6
\end{array}\right\}
$$

The basic solution is $(0 ; 9 ; 9 ; 5 ; 12 ; 0), F_{\mathrm{b}^{\prime}}=54$.

3. Further increasing $F$ is only possible by increasing $x_{1}$. Analysis of system (5) shows that $x_{1}$ can be no more than 6 (otherwise,
\begin{array}{|c|c|c|c|c|}
\hline
A & 3 & 15 & 8 & 70 \\
\hline
B & 6 & 3 & 12 & 80 \\
\hline
Shipped & 20 & 40 & 30 & \\
\hline
\end{array}

11. Solve graphically the following linear programming problem. On the set of solutions of the system

$$
\left\{\begin{array}{l}
x_{1}+x_{2} \leqslant 1 \\
x_{1} \leqslant x_{2} \leqslant 1 \\
x_{1} \geqslant 0, x_{2} \geqslant 0
\end{array}\right.
$$

find the maximum value of $F=x_{1}+2 x_{2}$.

12. Find the minimum value of $F=x_{1}-x_{2}$ given

$$
\left\{\begin{array}{c}
x_{1}+x_{2} \leqslant 1 \\
x_{1}+2 x_{2} \leqslant 1 \\
2 x_{1}+3 x_{2} \leqslant 2 \\
3 x_{1}+2 x_{2} \leqslant 3 \\
x_{1}+x_{2} \leqslant \frac{1}{2} \\
x_{1} \geqslant 0, x_{2} \geqslant 0
\end{array}\right.
$$

13. Find the maximum value of $F=x_{1}-x_{2}$ given

$$
\left\{\begin{array}{l}
1 \leqslant x_{1}+x_{2} \leqslant 2 \\
2 \leqslant x_{1}-2 x_{2} \leqslant 3 \\
1 \leqslant 2 x_{1}-x_{2} \leqslant 2 \\
x_{1} \geqslant 0, x_{2} \geqslant 0 .
\end{array}\right.
$$

14. Find the minimum value of $F=x_{1}+x_{2}-x_{3}$ given

$$
\left\{\begin{array}{l}
x_{1}+x_{2}+x_{3} \leqslant 4 \\
x_{1}-x_{2}+x_{3} \leqslant 2 \\
x_{1} \geqslant 0, x_{2} \geqslant 0, x_{3} \geqslant 0
\end{array}\right.
$$

Solve the following linear programming problems analytically and, where possible, provide a geometric interpretation.
15. $2 x_{1}+x_{2}-x_{3}+x_{4}=3$

$\left\{\begin{array}{c}-2 x_{1}+x_{2}+x_{3}-x_{4}=-1 \\ x_{i} \geqslant 0, i=1,2,3,4,\end{array}\right.$

$$
F_{\min }=x_{1}+x_{2}+x_{3}+x_{4} .
$$

16. $x_{1}+x_{3}=2$

$\left\{\begin{array}{l}x_{2}-x_{3}+x_{4}=1 \\ x_{i} \geqslant 0, i=1,2,3,4,\end{array}\right.$

$F_{\max }=x_{1}+x_{2}$.
17. $\left(x_{1}-3 x_{2}+x_{3}=5\right.$

$\left\{\begin{array}{l}x_{2}-x_{3}=2 \\ x_{1} \geqslant 0, x_{2} \geqslant 0, x_{3} \geqslant 0,\end{array}\right.$

$F_{\max }=x_{2}+x_{3}$.
18. $\left(2 x_{1}+x_{2}+x_{3}=4\right.$

$\left\{\begin{array}{l}x_{1}-x_{2}-x_{3} \leqslant 2 \\ x_{1} \geqslant 0, x_{2} \geqslant 0, x\end{array}\right.$

$F_{\max }=x_{1}-4 x_{2}+5 x_{3}$.
19. $10 x_{1}+x_{3} \leqslant 10$

$\left\{\begin{array}{l}10 x_{2}+x_{3} \leqslant 10 \\ x_{1} \geqslant 0, x_{2} \geqslant 0\end{array}\right.$

$F_{\max }=x_{1}-x_{2}+x_{3}$.

In preparing this manual, the authors used the following literature:

1. R. Courant, H. Robbins. What is Mathematics? Moscow, "Prosveshchenie", 1967.
2. N. P. Natanson. Simplest Problems on Maximum and Minimum. Moscow, Fizmatgiz, 1960.
3. D. O. Shklyarsky, N. N. Chentsov, I. M. Yaglom. Geometric Inequalities and Problems on Maximum and Minimum, Moscow, "Nauka", 1970.

## CONTENTS

Introduction ..... 3
§1. On the History of the Development of the Theory of Extreme Values of Quantities. ..... 6
§2. Analysis of the Set of Values of a Function ..... 15
§3. Using the Property of the Inequality Connecting the Arithmetic and Geometric Means of Two Non-Negative Numbers ..... 24
§4. Practical Problems Leading to a Linear Objective Function ..... 26
§5. Concept of Linear Programming Problems ..... 36
5.1. Types of Linear Programming Problems
5.2.