The class is preparing sandwiches for a club. For a cheese sandwich, $5 \mathrm{dkg}$ of bread, $1 \mathrm{dkg}$ of butter, and $2 \mathrm{dkg}$ of cheese are needed, while for a salami sandwich, $5 \mathrm{dkg}$ of bread, $5 / 3 \mathrm{dkg}$ of butter, and $1 \mathrm{dkg}$ of salami are required. Available are $2 \mathrm{~kg}$ of bread, half $\mathrm{kg}$ of butter, $60 \mathrm{dkg}$ of cheese, and $20 \mathrm{dkg}$ of salami.

a) What is the maximum number of sandwiches that can be prepared, and how many of these will be cheese sandwiches and how many will be salami sandwiches?

b) If a cheese sandwich is sold for $1.40 \mathrm{Ft}$ and a salami sandwich for $1.90 \mathrm{Ft}$, when will the highest revenue be achieved?

c) If a cheese sandwich takes 1 minute to prepare and a salami sandwich takes 2 minutes, (with the maximum number of sandwiches) when will they be prepared the fastest?

For practice 802 and problem 1208, see the introductory article of this issue.
Let the number of cheese sandwiches made be $x$, and the number of ham sandwiches be $y$ (non-negative integers). Considering the available stock of bread, cheese, and ham, as well as the amount used per sandwich, we get the following inequalities (unit: $\mathrm{dkg}$):

$$
5 x + 5 y \leqq 200, \quad x + \frac{5}{3} y \leqq 50, \quad 2 x \leqq 60, \quad y \leqq 20
$$

Simplifying and completing the system of inequalities that describe all possible programs for material usage, we get:

$$
\begin{gathered}
x + y \leqq 40, \quad 3 x + 5 y \leqq 150, \quad 0 \leqq x \leqq 30, \quad 0 \leqq y \leqq 20 ; \\
x, y \quad \text{ integers. }
\end{gathered}
$$

![](https://cdn.mathpix.com/cropped/2024_05_02_9e927275629961314994g-1.jpg?height=916&width=1152&top_left_y=637&top_left_x=473)

The pairs of numbers that satisfy all conditions are the points inside and on the boundary segments of the shaded region $H$ in the rectangular coordinate system. The boundary of $H$ is formed by the segments between the following points of the lines:

$$
x + y = 40, \quad 3 x + 5 y = 150, \quad x = 0, \quad x = 30, \quad y = 0, \quad y = 20
$$

$$
O(0; 0), \quad C_{1}(30; 0), \quad C_{2}(30; 10), \quad C_{3}(25; 15), \quad C_{4}(50 / 3; 20), \quad C_{5}(0; 20)
$$

a) The number of items made is $D = x + y$. The lines corresponding to different values of $D$ are parallel to the boundary line $x + y = 40$ in $H$. As $D$ increases, the lines move to the upper right on the diagram. The last line that still has a common point with $H$ is the line $x + y = 40$, and its segment $C_{2} C_{3}$ is common with $H$; there are 6 lattice points on this segment. Therefore, the maximum value of $D$ is 40, and it can be achieved in 6 different ways: with 30 cheese and 10 ham sandwiches, or by having 29 and 11, 28 and 12, 27 and 13, 26 and 14, and finally 25 and 15.

b) Assuming all sandwiches are sold, the revenue $B = 1.4 x + 1.9 y$. The lines corresponding to different values of $B$ are parallel to the line $1.4 x + 1.9 y = 26.6$ in the diagram (for $x = 19, y = 0$ and $x = 0, y = 14$). Moving the ruler parallel to this line (shifting it) and away from the origin - which clearly follows the increase in revenue - the last common point with the boundary of $H$ is at the point $C_{3}(25; 15)$, where $B_{\max} = 25 \cdot 1.40 + 15 \cdot 1.90 = 63.50 \mathrm{Ft}$. (In this case, all the bread and butter are used, leaving 10 dkg of cheese and 5 dkg of ham remaining.)

c) The preparation time is $T = x + 2 y$ minutes. The lines corresponding to different values of $T$ are parallel to the drawn line $x + 2 y = 30$. Since we are only concerned with the programs that produce the maximum number of items, when moving the ruler parallel to this line, we only consider the segment $C_{2} C_{3}$. The smallest $T$ is obtained when the line, starting from the drawn position and moving away from $O$ - which corresponds to increasing $T$ - first reaches the segment, i.e., at the point $C_{2}$. Here, $x = 30, y = 10$, and $T_{\min} = 50$ minutes.[^0]

[^0]:    ${ }^{1}$ Viktor Scharnitzky-János Surányi: Article on Linear Programming - K. M. L. 25 (1962/11) 97 - 104. - with the use of.