# Optimization: One-way shipping lanes within cities, with specified maximum capacities of tons of tomatoes per year.

Suppose there are the following one-way shipping lanes from the following cities to the following cities, with the specified maximum capacities of tons of tomatoes per year:

[![enter image description here][1]][1]

Consider the problem of finding how many tons of (nonperishable) tomatoes should be sent yearly along each of these different shipping lanes to maximize the the number of tomatoes delivered from Athens to Frankfurt (assuming that tomatoes are grown in Athens and eaten in Frankfurt, and are neither created nor destroyed in any of the other cities). Express this problem as a linear programming problem in standard form. If so inclined, find a solution to this problem in an ad-hoc way, and demonstrate that your solution is indeed optimal.

Define $$x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8$$ as the respective flows from $$\text{A to B, A to C, C to B, B to D, C to E, D to E, D to F, E to F}$$.

Problem is to minimize $$—x_1 — x_2$$ subject to the conditions

• $$x_1 + x_3 — x_4 = 0$$
• $$x_2 — x_3 — x_5 = 0$$
• $$x_4 — x_6 — x_7 = 0$$
• $$x_5 + x_6 — x_8 = 0$$
• $$x_1+ x_9 = 5.1$$
• $$x_2 + x_{10} = 7.2$$
• $$x_3 + x_{11} = 2.1$$
• $$x_4 + x_{12} = 5.9$$
• $$x_5 + x_{13} = 3.1$$
• $$x_6 + x_{14} = 2.9$$
• $$x_7 + x_{15} = 4.0$$
• $$x_8 + x_{16} = 10.5$$
• $$x_i \ge 0 \; \forall i=1,2,...,16$$ (which are slack variables when $$i > 8$$)

If we need to maximize the amount flying from Athens to Frankfurt why is this only $$-x_1-x_2?$$, why we are not including Frankfurt at all? Also, what are all the variables after $$x_8$$ stand for?

• This is the "maximum flow" problem, and a linear programming formulation is given here. May 31, 2022 at 20:54

The variables after $$8$$ are slack variables as mentioned at the bottom. They represent the amount of capacity you have available for a route but aren’t utilizing. You want to minimize these slack variables so that all the routes are operating as close to full capacity as possible.