Mathematical Model of the Maximum Flow Problem

The decision variables are defined xij, the number of units of flow on arc (i,j). The pipeline capacity limits (problem Aqueduct, Picture 8.3 in level 1) are maximum arc flows, mij The model has conservation of flow constraints. For Node 6, the amount of water (in m3) leaving the node is equal to the amount entering the node:

x6,7 + x6,8 = x3,6 + x5,6

After transposing all variables to the left hand side of the equation, the result is

x6,7 + x6,8 - x3,6 - x5,6 = 0

The maximum flow problem has no specified net stock position for any node. However, the goal is to maximize the flow from Node 1 to Node 8. Let the net stock position at Node 1 be +Z, and let the net stock position at Node 8 be -Z. The amount Z is a decision variable, and you define it as the maximum flow amount. In the maximum flow problem, the decision variables are Z and the flows for each arc.

The constraint for Node 1 is

x1,2 + x1,3 = Z

After transposing a decision variable Z to the left hand side of the equation, the result is

x1,2 + x1,3 – Z = 0

The entire linear programming model is