Exercise¶

Extreme of linear function with linear constraints. The transportation problem

Two cement factories, $F_{1}$ and $F_{2}$, produce respectively 3000 and 4000 bags of cement everyday. That cement must be sent to three sales centers $C_{1}$, $C_{2}$ and $C_{3}$ in quatities of 3000, 2500 and 1500 , respectively. The transport costs of each factory to the points of sale are given, in euros per bag,

$$ \begin{array}{|c|c|c|c|} \hline \mathbf{Costs}\;\mathbf{per}\;\mathbf{unit} & \mathrm{to}\; C_{1} & \mathrm{to}\; C_{2} & \mathrm{to} \;C_3\\ \hline \hline \mathrm{from}\; F_{1} & 2 & 2.5 & 2\\ \hline \mathrm{from} \;F_{2} & 1.5 & 4 & 1\\ \hline \end{array} $$

Determine how to distribute production so that transportation is as economical as possible.

$$ \begin{array}{|c|c|c|c|c|} \hline \mathbf{Units} & \mathrm{to}\; C_{1} & \mathrm{to}\; C_{2} & \mathrm{to} \;C_3 & \Sigma\\ \hline \mathrm{from}\; F_{1} & {\color{red}{x}} & {\color{red}{y}} & {\color{red}{3000-x-y}} & 3000\\ \mathrm{from} \;F_{2} & {\color{red}{3000-x}} & {\color{red}{2500-y}} & {\color{red}{x+y-1500}} & 4000\\ \hline \Sigma & 3000 & 2500 & 1500 & 7000\\ \hline \end{array} $$

We assume $x$ units to be transported from $F_1$ to $C_1$ and $y$ units to be transported from $F_1$ to $C_2.$ We obtain all the others taking into account $x$ and $y$ and the total units to send from the factories and to receive at the sales centers.

Cost

We obtain the cost for each of the 6 itineraries by multiplying the number of units (table 2) by the cost per unit (table 1). We get the total cost by adding the 6 different cases.

$$ C = 2 x +2.5 y +2(3000-x-y)+1.5(3000-x)+4(2500-y)+1(x+y-1500) $$

Simplifying

$$ C=19000-0.5x-2.5y $$

Constraints

The constraints are that the number of units transported from each factory to each sales center must be positive. As there are 6 distribution channels we have 6 constraints

\begin{array}{c} x \ge 0 \\ y \ge 0 \\ 3000-x-y \ge 0 \\ 3000-x \ge 0 \\ 2500-y \ge 0 \\ x+y-1500 \ge 0 \end{array}

Problem

Minimize $$C=19000-0.5x-2.5y$$

with the constraints (we rearrange the previous conditions)

$$ \begin{array}{c} x+y \le 3000 \\ x \le 3000 \\ y \le 2500 \\ x+y \ge 1500 \\ \\ x,y \ge 0 \end{array} $$

The conditions $x\geq 0$ and $y\geq 0$ mean that the region of the plane described by the constraint must be in the first quadrant.

The condition $x \le 3000$ means that $x$ must be to the left of the vertical line $r_1$ that passes through $3000$ and $y \le 2500$ means that $y$ must be below the horizontal line $r_2$ that passes through $2500$

We draw the other borders of the region where the solution is to be found. We have two lines $r_3$ and $r_4$

\begin{array}{ll} r_{3}\qquad x+y=3000\qquad\rightarrow\qquad & \dfrac{x}{3000}+\dfrac{y}{3000}=1\\ \\ r_{4}\qquad x+y=1500\qquad\rightarrow\qquad & \dfrac{x}{1500}+\dfrac{y}{1500}=1 \end{array}

and $r_{3}$ intersects with $OX$ in $x=3000$ and with $OY$ in $y=3000$. Similarly, $r_{4}$ intersects with $OX$ in $x=1500$ and with $OY$ in $y=1500$.

Each of these lines divides the plane into two regions, one that meets the condition and the other that does not. Therefore, it is enough to try with a point and if this point meets the condition, the region of the plane where this point is located belongs to the region.

For simplicity, we try with the origin $\left(0,0\right)$

The origin meets the condition $x+y\le 3000$ because $0+0\le 3000$. Therefore, the region is the one below the blue line.
The origin does not meet the conditions $x+y\ge 1500$, therefore, the region is the one that is above the line $r_4$ (red).

Also,

The condition $x \le 3000$ means that $x$ must be to the left of the vertical line $r_1$ that passes through $3000$
The condition $y \le 2500$ means that $y$ must be below the horizontal line $r_2$ that passes through $2500$

So the region is the intersection of the three regions (pink, blue, and green) and it is the region represented in yellow, which is in the first quadrant because in addition $x\ge 0$ and $y\ge 0.$

The minimum will be at one of the vertices (or sides) of the polygon that surrounds the area. So we need to calculate the vertices.

$A$ is the intersection of $x+y=1500$ with $OX$, that is, $y=0$. Then, $A=(1500,0).$
$B$ is the intersection of $y=2500$ with $0Y$, that is, $x=0$. Then, $B=(0,2500)$
$C$ is the intersection of $y=2500$ with $x=0$. $C=(0,2500).$
$D$ is the intersection of $x+y=3000$ with $y=2500$. As $x = 3000-2500$, we have $D=(500,2500).$
$E$ is the intersection of $x+y=3000$ with $y=0$ (axis $OX$). Then, $E=(3000,0).$

We compute the value of the function
$ C=19000-0.5x-2.5y $ at these points

\begin{array}{cccc} \hline \mathrm{Vertex} & x & y & C\\ \hline A & 1500 & 0 & 18250\\ B & 0 & 1500 & 16750\\ C & 0 & 2500 & 15250\\ {\color{red}D} & {\color{red}{500}} & {\color{red}{2500}} & {\color{red}{15000}}\\ E & 3000 & 0 & 17500\\ \hline \end{array}

And the minimum is in $D$ with $x=500$ and $y=2500$, because, at this point, the value of the function is minimum. We obtain the solution of the problem substituting these values in the table

$$ \begin{array}{|c|c|c|c|c|} \hline \mathbf{Units} & \mathrm{to}\; C_{1} & \mathrm{to}\; C_{2} & \mathrm{to} \;C_3 & \Sigma\\ \hline \mathrm{from}\; F_{1} & {\color{red}{x}} & {\color{red}{y}} & {\color{red}{3000-x-y}} & 3000\\ \mathrm{from} \;F_{2} & {\color{red}{3000-x}} & {\color{red}{2500-y}} & {\color{red}{x+y-1500}} & 4000\\ \hline \Sigma & 3000 & 2500 & 1500 & 7000\\ \hline \end{array} $$

the values $x=500$ and $y=2500$

$$ \begin{array}{|c|c|c|c|c|} \hline \mathbf{Units} & \mathrm{to}\; C_{1} & \mathrm{to}\; C_{2} & \mathrm{to} \;C_3 & \Sigma\\ \hline \mathrm{from}\; F_{1} & {\color{red}{500}} & {\color{red}{2500}} & {\color{red}{3000-500-2500}} & 3000\\ \mathrm{from} \;F_{2} & {\color{red}{3000-500}} & {\color{red}{2500-2500}} & {\color{red}{500+2500-1500}} & 4000\\ \hline \Sigma & 3000 & 2500 & 1500 & 7000\\ \hline \end{array} $$

And the solution is

$$ \begin{array}{|c|c|c|c|c|} \hline \mathbf{Units} & \mathrm{to}\; C_{1} & \mathrm{to}\; C_{2} & \mathrm{to} \;C_3 & \Sigma\\ \hline \mathrm{from}\; F_{1} & {\color{red}{500}} & {\color{red}{2500}} & {\color{red}{0}} & 3000\\ \mathrm{from} \;F_{2} & {\color{red}{2500}} & {\color{red}{0}} & {\color{red}{1500}} & 4000\\ \hline \Sigma & 3000 & 2500 & 1500 & 7000\\ \hline \end{array} $$

As we can see, we are avoiding high-priced transportation to carry cement at $C_2$ and $C_3$ and we compensate by distributing transportation to $C_1$ where prices are more similar

$$ \begin{array}{|c|c|c|c|} \hline \mathbf{Costs}\;\mathbf{per}\;\mathbf{unit} & \mathrm{to}\; C_{1} & \mathrm{to}\; C_{2} & \mathrm{to} \;C_3\\ \hline \hline \mathrm{from}\; F_{1} & 2 & 2.5 & 2\\ \hline \mathrm{from} \;F_{2} & 1.5 & 4 & 1\\ \hline \end{array} $$