### 7.1.1. Optimal Production Task

For the production of two types of products I and II, three types of raw materials are used.

To produce one unit of product I, it is required to spend 13 kg of the first type of raw material, 32 kg of the second type of raw material, and 58 kg of the third type of raw material.

To produce one unit of product II, it is required to spend 24 kg of the first type of raw material, 32 kg of the second type of raw material, and 29 kg of the third type of raw material.

The production is supplied with 312 kg of the first type of raw material, 480 kg of the second type of raw material, and 696 kg of the third type of raw material.

The profit from the sale of one unit of finished product I is 4 conditional units, and for product II - 3 conditional units.

It is required to develop a production plan for products I and II that ensures maximum profit from their sale, if it is planned in advance to produce at least 10 units of products I and II.
Solution. Let's consider the mathematical model of the problem. If we take $x_{1}$ as the number of items I planned for production and $x_{2}$ as the number of items II, we obtain a linear programming problem.

Subject to the constraints

$$
\begin{gathered}
13 x_{1}+24 x_{2} \leq 312 \\
32 x_{1}+32 x_{2} \leq 480 \\
58 x_{1}+29 x_{2} \leq 696 \\
x_{1}+x_{2} \geq 10 \\
x_{1} \geq 0, x_{2} \geq 0
\end{gathered}
$$

find the maximum of the linear function

$$
Z=4 x_{1}+3 x_{2}
$$

## Geometric Solution of the Problem

Since the problem is two-dimensional, it can be solved graphically.

The system of constraints (7.1) gives a polygon of feasible solutions. To construct it, we draw the lines that are the boundaries of the polygon and use a test point, for example $(0 ; 0)$, to determine the half-planes defined by these lines (Fig. 86):

$$
\begin{aligned}
& l_{1}: 13 x_{1}+24 x_{2}=312, \\
& l_{2}: 32 x_{1}+32 x_{2}=480, \\
& l_{3}: 58 x_{1}+29 x_{2}=696, \\
& l_{4}: x_{1}+x_{2}=10 .
\end{aligned}
$$

In the intersection of the corresponding half-planes, we obtain the hexagon $A B C D E F$.

![](https://cdn.mathpix.com/cropped/2024_05_22_e915d089cc29fd681be5g-371.jpg?height=616&width=845&top_left_y=1197&top_left_x=280)

Fig. 86

To find $\max z$, we construct a vector $\bar{n}=(4 ; 3)$ from the origin and a line perpendicular to it, which is the level line $z=0$, i.e., the line $4 x_{1}+3 x_{2}=0$.

Next, we move the level line $z=$ const in the direction of increasing $z$, i.e., parallel to itself in the direction of the vector $\bar{n}$. In the last intersected vertex $D$, we obtain the maximum value of $z$. Vertex $D$ is the intersection point of lines $l_{2}$ and $l_{3}$.

To find the coordinates of point $D$, we solve the system:

$$
\begin{array}{rlrl}
32 x_{1}+32 x_{2} & =480, \quad x_{1}+x_{2}=15, \\
58 x_{1}+29 x_{2} & =696, \quad 2 x_{1}+x_{2} & =24 .
\end{array}
$$

Solving the system, we find that $x_{1}=9, x_{2}=6$, i.e., $D(9 ; 6)$ and at this point $z=4 \cdot 9+3 \cdot 6=54$ (conditional units).

To solve the problem using the simplex method, we convert the system of constraints (7.1) to the form of equalities by introducing non-negative slack variables $y_{i}(i=1,2,3,4)$:

$$
\begin{gathered}
13 x_{1}+24 x_{2}+y_{1}=312 \\
x_{1}+x_{2}+y_{2}=15 \\
2 x_{1}+x_{2}+y_{3}=24 \\
-x_{1}-x_{2}+y_{4}=-10 \\
-4 x_{1}-3 x_{2}+Z=0
\end{gathered}
$$

with $x_{j} \geq 0(j=1,2) ; y_{i} \geq 0(i=1,2,3,4)$.

We write the system using abbreviated tables (Table 7.1).

Table 7.1

|  | $x_{1}$ | $x_{2}$ | 1 |
| :---: | :---: | :---: | :---: |
| $y_{1}$ | 13 | 24 | $=312$ |
| $y_{2}$ | 1 | 1 | $=15$ |
| $y_{3}$ | 2 | 1 | $=24$ |
| $y_{4}$ | -1 | -1 | $=-10$ |
| $Z$ | -4 | -3 | $=0$ |

Since there is a negative element in the I-column, we need to make it positive. We choose the $y_{4}$-row with the negative free term “-10”.

In this row, there are negative elements, and we choose one of them, for example, “-1” in the $x_{1}$-column. We take the $x_{1}$-column as the pivot column.

We divide the free terms by the corresponding elements of the pivot column, obtaining $\{24,15,12,10\}$, and the smallest positive ratio will correspond to the pivot row, so the $y_{4}$-row is the pivot row, and the element -1 is the pivot element. We perform a step of the modified Jordan elimination (MJSE) with the pivot element -1 according to the rule:

1) the pivot element is replaced by its reciprocal;
2) the elements of the pivot row are divided by the pivot element;
3) the elements of the pivot column are divided by the pivot element and the sign is changed;
4) the other elements of the new table are found by the rectangle formula [17, p. 52]

$$
\begin{aligned}
& \text { corresponding element } \\
& \underset{\text { new elements }}{\text { corresponding element }}=\underset{\text { old elements }}{\text { corresponding element }}-\frac{\text { pivot row elements pivot column elements }}{\text { pivot element }} .
\end{aligned}
$$

We obtain Table 7.2, in which the variables $x_{1}$ and $y_{4}$ swap places. From the table, it is clear that the free coefficients in the I-column are non-negative, so we have obtained a basic solution: $x_{1}=10, x_{2}=0, y_{1}=182, y_{2}=5, y_{3}=4, y_{4}=0, Z=40$. Geometrically, this means that we are at vertex $F(10 ; 0)$ of the polygon of feasible solutions $A B C D E F$.

Table 7.2

|  | $y_{4}$ | $x_{2}$ | 1 |
| :---: | :---: | :---: | :---: |
| $y_{1}$ | 13 | 11 | $=182$ |
| $y_{2}$ | 1 | 0 | $=5$ |
| $y_{3}$ | 2 | -1 | $=4$ |
| $x_{1}$ | -1 | 1 | $=10$ |
| $Z$ | -4 | 1 | $=40$ |

This solution is not optimal, as there is a negative coefficient in the $Z$-row, so we improve the plan.

We choose the pivot element according to the rule: we choose the column with the smallest negative element in the $z$-row as the pivot column, divide the free terms in the I-column by the corresponding coefficients, and the smallest positive ratio corresponds to the pivot row. The pivot element is 2. Performing MJSE with the pivot element 2 according to the above rule, we obtain Table 7.3.

Table 7.3

|  | $y_{3}$ | $x_{2}$ | 1 |
| :---: | :---: | :---: | :---: |
| $y_{1}$ | $-\frac{13}{2}$ | $\frac{35}{2}$ | $=156$ |
| $y_{2}$ | $-\frac{1}{2}$ | $\boxed{-\frac{1}{2}}$ | $=3$ |
| $y_{4}$ | $\frac{1}{2}$ | $-\frac{1}{2}$ | $=2$ |
| $x_{1}$ | $\frac{1}{2}$ | $\frac{1}{2}$ | $=12$ |
| $Z$ | 2 | -1 | $=48$ |

The solution obtained from Table 7.3 is also not optimal, as there is a negative coefficient in the $Z$-row. Determining the pivot element $\frac{1}{2}$ from Table 7.3 and

Table 7.4

|  | $y_{3}$ | $y_{2}$ | 1 |
| :---: | :---: | :---: | :---: |
| $y_{1}$ | 11 | -35 | $=51$ |
| $x_{2}$ | -1 | 2 | $=6$ |
| $y_{4}$ | 0 | 1 | $=5$ |
| $x_{1}$ | 1 | -1 | $=9$ |
| $Z$ | 1 | 2 | $=54$ |

performing MJSE, we arrive at Table 7.4, in which all coefficients in the $Z$-row are non-negative, and thus $\max Z$ has been reached, corresponding to the solution $x_{1}=9, x_{2}=6$, with $Z_{\max }=54$ (conditional units).

Answer: The maximum profit $Z=54$ (conditional units) is achieved by producing 9 units of item I and 6 units of item II.