Problem 33. Every day, 12 tons of potatoes are supplied to the city by one type of transport from three collective farms: from the I farm at a price of 4 rubles per ton, from the II - at a price of 3 rubles, from the III - 1 ruble. To ensure timely delivery of potatoes to the city, it is necessary to spend no more than 40 minutes on loading the required 12 tons. It is known that the level of mechanization in the I farm allows loading 1 ton in 1 minute, in the II - in 4 minutes, in the III - in 3 minutes. The production capacities of these farms are as follows: the I farm should allocate no more than 10 tons daily for delivery to the city, the II - no more than 8 tons, the III - no more than 6 tons. How should the orders for the supply of 12 tons be distributed among the farms so that the total cost of the potatoes delivered to the city is minimized?
S o l u t i o n.

First, let's construct a mathematical model of this problem. Let $x_{1}, x_{2}, x_{3}$ be the tons of potatoes delivered to the city from the I, II, and III collective farms, respectively. Then the problem can be formulated as follows: Minimize the objective function

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

subject to the conditions

$$
\left\{\begin{aligned}
x_{1} \geqslant 0 & (a) \\
x_{2} \geqslant 0 & \left(x_{3} \geqslant 0\right. \\
x_{1}+x_{2}+x_{3}=12 & (d) \\
x_{1}+4 x_{2}+3 x_{3} \leqslant 40 & (d) \\
x_{1} \quad \leqslant 10 & (f) \\
x_{2} \quad \leqslant 8 & (g) \\
x_{3} \leqslant 6 & (h)
\end{aligned}\right.
$$

1. Let's represent the conditions (2) geometrically in space, i.e., construct the polyhedron of feasible plans.

From the non-negativity conditions of the variables, it follows that the solution region of the problem is confined between the positive coordinate axes $O x_{1}, O x_{2}, O x_{3}$, as shown in Figure 31.

![](https://cdn.mathpix.com/cropped/2024_05_21_07b5a7f6f561b0ff634dg-48.jpg?height=1099&width=1088&top_left_y=1341&top_left_x=495)

Conditions (f), $(g)$, and $(h)$ limit the set of possible solutions to a rectangular parallelepiped formed by six planes described by the equations $x_{1}=0, x_{2}=0$, $x_{3}=0, x_{1}=10, x_{2}=8, x_{3}=6$.

If we consider a point outside this parallelepiped, the plan corresponding to the coordinates of this point is infeasible, as it would exceed the production capacities of the collective farms. From condition (d), it follows that the optimal solution must belong to the part of the plane $D_{1}, D_{2}, D_{3}$ described by the equation $x_{1}+x_{2}+x_{3}=12$ and bounded by the rectangular parallelepiped. Thus, without considering condition (e), we have the polygon of feasible plans $P_{1} P_{2} P_{3} N_{1} N_{2} P_{6}$. We now apply the last condition (e). Points satisfying this condition lie on the side of the plane $E_{1} E_{2} E_{3}$ closer to the origin. However, the planes $E_{1} E_{2} E_{3}$ and $D_{1} D_{2} D_{3}$ intersect along the line $M_{1} M_{2}$. Thus, the polygon $P_{1} P_{2} P_{3} N_{1} N_{2} P_{6}$ is divided into two parts, and in the points of one of these parts $\left(P_{4} N_{1} N_{2} P_{5}\right)$, the last condition (e) is not satisfied.

Therefore, the polygon of feasible plans for this linear programming problem is the polygon $P_{1} P_{2} P_{3} P_{4} P_{5} P_{6}$, the points of which satisfy all eight conditions of the system of constraints (2).

2. Let's use the optimality criterion: from the set of points of the polygon $P_{1} P_{2} P_{3} P_{4} P_{5} P_{6}$, we need to select only those whose coordinates minimize the objective function $F=4 x_{1}+3 x_{2}+1 x_{3}$.

In linear programming theory, it is proven that the objective function attains its minimum (or maximum) value at the extreme points of the polygon of feasible plans. There are two ways to find the required points: 1) the coordinates of all six vertices of the polygon are determined, and by substituting the obtained coordinates of the vertices into $F=4 x_{1}+3 x_{2}+x_{3}$, the optimal plan corresponding to the minimum of $F$ is selected;

2) first, a plane $4 x_{1}+3 x_{2}+x_{3}=a$ corresponding to some (any) value of the objective function is constructed, and then the vertex that this plane reaches first (or last) when moved parallel to itself is determined.

The second method is more rational. Let's construct the plane $Z_{1} Z_{2} D_{3}$ defined by the equation $4 x_{1}+3 x_{2}+x_{3}=12$ (we took $a=12$ arbitrarily). When this plane is moved parallel to itself in the direction of increasing $a$ from the origin (i.e., $a>12$), the first vertices it will touch are either $P_{3}$ or $P_{4}$. The fact that vertices $P_{2}, P_{5}$, and $P_{6}$ will not be the first is evident from the consideration of $\triangle D_{1} Z_{1} D_{3}$ and $\triangle D_{2} Z_{2} D_{3}$. Let's find the coordinates of $P_{3}$: $P_{3}$ is the point of intersection of three planes defined by the equations: $x_{3}=6, x_{1}+x_{2}+x_{3}=12, x_{2}=0$. Therefore, its coordinates are $(6 ; 0 ; 6)$.

The value of the objective function $F$ corresponding to the plan $P_{3}(6 ; 0 ; 6)$ is $F\left(P_{3}\right)=4 \cdot 6+3 \cdot 0+1 \cdot 6=30$ (rubles).

Let's calculate the coordinates of point $P_{4}$:

$$
\begin{aligned}
& \quad\left\{\begin{array}{l}
x_{3}=6 \\
x_{1}+x_{2}+x_{3}=12 \\
x_{1}+4 x_{2}+3 x_{3}=40, \quad P_{4}\left(\frac{2}{3}, 5 \frac{1}{3}, 6\right)
\end{array}\right. \\
& F\left(P_{4}\right)=4 \cdot \frac{2}{3}+3 \cdot 5 \frac{1}{3}+6=24 \frac{2}{3} \quad \text { (rubles). }
\end{aligned}
$$

Thus, at the extreme point $P_{4}\left(\frac{2}{3} ; 5 \frac{1}{3} ; 6\right)$, the objective function $F=4 x_{1}+3 x_{2}+x_{3}$ attains its minimum value.

In other words, the minimum total cost of transporting 12 tons of potatoes to the city is achieved if $\frac{2}{3}$ tons are taken from the I collective farm, $5 \frac{1}{3}$ tons from the II, and 6 tons from the III.