In: Statistics and Probability
The network above shows the flows possible between pairs of five locations.
1) Formulate an LP to find the maximal flow possible from Node 1 to Node 5 (identify all constraints),
Please show full steps.
The solution is:
The formulas are:
Data - Arc capacities | ||||||
From\to | Node 1 | Node 2 | Node 3 | Node 4 | Node 5 | |
Node 1 | 0 | 2 | 1 | 6 | 0 | |
Node 2 | 0 | 0 | 3 | 0 | 0 | |
Node 3 | 0 | 0 | 0 | 3 | 7 | |
Node 4 | 0 | 0 | 4 | 0 | 3 | |
Node 5 | 0 | 0 | 0 | 0 | ||
Flows | ||||||
From\to | Node 1 | Node 2 | Node 3 | Node 4 | Node 5 | Outflow |
Node 1 | 2 | 1 | 6 | 9 | ||
Node 2 | 2 | 2 | ||||
Node 3 | 7 | 7 | ||||
Node 4 | 4 | 2 | 6 | |||
Node 5 | 9 | 9 | ||||
Inflow | 9 | 2 | 7 | 6 | 9 | |
Outflow | 9 | 2 | 7 | 6 | 9 | |
Max Flow | 9 |