\section*{Task 1 - 041111}

A company delivers annually 600 tons and 400 tons of a certain product to companies (1) and (2). For transportation, trucks 1 and 2 with payloads of 1 ton and 4 tons are available. The smaller truck is available for a maximum of 300 trips per year, and the larger one for 200 trips. The transportation costs in thousand euros per trip are as follows for

\begin{tabular}{l|c|c} 
& Truck 1 & Truck 2 \\
\hline to the trip to Company 1 & 10 & 20 \\
to the trip to Company 2 & 30 & 60
\end{tabular}

How many trips must each truck make to each of the two companies in a year to minimize the total transportation costs?
}

The number of trips per year of the truck \(L_{i}\) to the business \(B_{j}\) is denoted by \(x_{i j}\) \((i=1,2 ; j=1,2)\). Then it follows:

\[
\begin{aligned}
x_{11}+4 x_{21} & \geq 600 \geq x_{11}+1+4\left(x_{21}-1\right) \\
x_{12}+4 x_{22} & \geq 400 \geq x_{12}+1+4\left(x_{22}-1\right) \\
x_{11}+x_{12} & \leq 300 \\
x_{21}+x_{22} & \leq 200 \\
x_{i j} & \geq 0 \quad \text { and integer }
\end{aligned}
\]

If the total transportation costs are denoted by \(K\), then

\[
K=10 x_{11}+20 x_{21}+30 x_{12}+60 x_{22}
\]

It is to be investigated for which values of \(x_{i j}\) the costs are as low as possible under consideration of the relationships (1) to (5). From (1) it follows:

\[
600-4 x_{21} \leq x_{11} \leq 603-4 x_{21}
\]

and from (2)

\[
400-4 x_{22} \leq x_{12} \leq 403-4 x_{22}
\]

Due to (7) and (8), it follows from (6)

\[
18000-20 x_{21}-60 x_{22} \leq K \leq 18120-20 x_{21}-60 x_{22}
\]

and from this, due to (4)

\[
14000-40 x_{22} \leq K \leq 18120-20 x_{21}-60 x_{22}
\]

From (8) it follows that \(x_{22} \leq \frac{403-x_{12}}{4}\) and from this, due to (5), \(x_{22} \leq 100 \quad\) (10).

Due to (9), the transportation costs will be as low as possible exactly when \(x_{22}\) is as large as possible, i.e., when \(x_{22}\) is 100 due to (10). From the conditions of the problem, it follows that \(x_{12}=0\). Therefore, \(K\) cannot take a value smaller than 1000. For \(K=1000\), it must follow from (6)

\[
10 x_{11}+20 x_{21}=4000, \quad \text { so } \quad x_{11}+2 x_{21}=400
\]

From (1) and (11), it further follows that \(x_{21} \leq 100\) and from (4), due to \(x_{22}=100: x_{21} \leq 100\). Therefore, \(x_{21}=100\) and due to (11), \(x_{11}=200\). Therefore, \(K\) can only be 1000 in the case

\begin{tabular}{lll} 
& \(L_{1}\) & \(L_{2}\) \\
\hline Number of annual trips to \(B_{1}\) & 200 & 100 \\
Number of annual trips to \(B_{2}\) & 0 & 100
\end{tabular}

\(K=1000\). As can be easily verified, \(K=1000\) in this case, thus the problem is completely solved.

Adapted from \([2]\)