*Mathematical
Model of the Shortest Route Problem*

The decision variables are defined *x _{ij}*,
The arc

We are searching for the shortest route from Prague
to Singapore (*Picture 8.6 in level 1*).

For Node 1 (Prague) the net stock position is 1 and one of outgoing arcs (to Frankfurt, to Zurich or to Vienna) must be on the shortest route thus

*x _{1,2} + x_{1,3} + x_{1,4}
= 1*

For Node 9 (Singapore) the net stock position is -1 and one of incoming arcs (from Bangkok or from Dubai) must be on the shortest route too, thus

*-x _{6,9} – x_{8,9} = -1*

This equation can be multiplied by –1 and so

*x _{6,9} + x_{8,9} = 1*

For nodes 2 to 8 the net stock position is 0 and the conditions are created in the same way as for Maximum Flow Problem.

Our objective is to minimize the sum of distances
between the transition airports on the route, i.e. the objective function
is

z = *410x _{1,2} + 252x_{1,3} +
526x_{1,4} + 4830x_{2,6} + 2442x_{3,5} + 2878x_{4,5}
+ 9026x_{4,8} +*

*+ 2026x _{5,6} + 6810x_{5,8} +
1937x_{6,7} + 5840x_{6,9} + 3000x_{7,8} + 1430x_{8,9}*

The entire bivalent linear programming model is