Ali Baba, upon returning to the cave filled with diamonds and gold, pondered the following: The treasures can only be placed in his sack. From experience, he knows that 40 pounds of diamonds and 200 pounds of gold can fit into it, but he can only carry and take away 100 pounds. In the market, 1 pound of gold can be exchanged for 20 tevets, and 1 pound of diamonds for 60 tevets. How should he fill his sack so that he can buy the maximum number of tevets?
Let's assume that Ali Baba puts $x$ pounds of gold and $y$ pounds of diamonds into his bag. First, we need to determine for which $x$ and $y$ this is possible. The total weight cannot exceed 100 pounds, so

$$
x + y \leq 100
$$

It is obvious that $x \geq 0, y \geq 0$, since only non-negative quantities are possible. We also need to ensure that the treasures fit into the bag, meaning their volume cannot be arbitrarily large. If 40 pounds of diamonds fit into the bag, then 1 pound of diamond takes up $\frac{1}{40}$ of the bag, and $y$ pounds take up $\frac{y}{40}$. Similarly, $x$ pounds of gold take up $\frac{x}{200}$ of the bag. The condition is therefore

$$
\frac{x}{200} + \frac{y}{40} \leq 1
$$

The possible $(x; y)$ pairs thus form the set

$$
F = \left\{(x; y): x \geq 0, y \geq 0, \quad x + y \leq 100, \quad \frac{x}{200} + \frac{y}{40} = 1\right\}
$$

The set of points corresponding to the elements of $F$ can also be represented in a coordinate system (Figure 1). The resulting shape is a quadrilateral $ABCD$, with the coordinates of vertex $C$ being $x_0, y_0$. For these,

$$
x_0 + y_0 = 100 \quad \text{and} \quad \frac{y_0}{40} + \frac{x_0}{200} = 1
$$

From the second equation, $x_0 = 200 - 5y_0$, substituting this into the first equation gives $200 - 4y_0 = 100$, so $y_0 = 25$ and $x_0 = 75$.

For given $x, y$, in exchange for the treasures, $20x + 60y$ pounds of tea are given. We need to find the point (or points) among the points of the feasible region where $20x + 60y$ (which we call the objective function) is maximized. This can be done by determining the largest $c$ for which the equation

$$
20x + 60y = c
$$

still has a solution $(x; y)$ in $F$. This is because the objective function can achieve this value, but not a larger one; the sought $x, y$ pair is given by the solution to (1).

Some of the lines with the equation $20x + 60y = c$ are drawn in Figure 2. These lines are parallel to each other, and as $c$ increases, they move in the direction indicated by the arrow. The question, then, is how far we can move these lines "upward" so that they still have a common point with $F$. It is clear that in the limit, this common point will be one of the vertices of $F$ (it is possible that there are other common points, but a vertex can always be found among them). Therefore, it is sufficient to calculate the value of the objective function at points $A, B, C, D$, and the one with the largest value corresponds to the sought $c$. For point $A(0; 0)$, $c = 20x + 60y = 0$; for $B(100; 0)$, $c = 2000$; for $C(75; 25)$, $c = 3000$; for $D(0; 40)$, $c = 2400$. The best solution is therefore 25 pounds of diamonds and 75 pounds of gold, for which 3000 pounds of tea can be obtained.

Based on the work of András Zsíros (Nyíregyháza, Evang. Kossuth L. Gymnasium, 1st year)

Note. It can be verified that $(75; 25)$ is the only point in $F$ for which $c = 3000$. This can also be seen from the following consideration. If this were not the only point, then the "limiting" line corresponding to $c = 3000$ would intersect $F$ at more points, and among these, there would be another vertex, which, as the numbers show, is impossible.

From all of this, the following general observation can be derived. If we want to maximize a linear objective function over a polyhedron, it is sufficient to search for the maximum among the vertices. If the maximum is unique, then that vertex is the only maximum point in the entire set.

If not, it is clear that all points on the face formed by the vertices representing the maximum are also maximum points. This is also true for minimization problems. This topic belongs to the theory of linear programming.

![](https://cdn.mathpix.com/cropped/2024_05_02_5cee20419e1d2d61ac18g-1.jpg?height=729&width=767&top_left_y=1961&top_left_x=663)

![](https://cdn.mathpix.com/cropped/2024_05_02_5cee20419e1d2d61ac18g-2.jpg?height=475&width=764&top_left_y=131&top_left_x=667)