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?

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

1 Answer 1


It seems like the solution is saying you can start maximizing the amount of tomatoes you send to Frankfurt by first maximizing the amount of tomatoes you send out of Athens, which will eventually arrive at Frankfurt.

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.

I’m not too familiar with linear programming, but apparently you can assign a high cost to these slack variables to ensure they get minimized.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .