The solver solves the problem of maximum flow with Excel from an S node to a T node in a graph oriented.
Formulate the maximum flow problem with Excel
To formulate the flow problem, it is necessary to answer these three questions.
- What are the decisions to be made? For this problem, we need Excel to find the flow on each arc. For example, if the flow on SB is equal to 2, cell D5 is equal to 2. (in yellow)
- What are the constraints on these decisions? The net flow (Outgoing flow – Incoming flow) of nodes A, B, C, D and E must be equal to 0. In other words, Outgoing flow = Incoming flow. Additionally, each arc has a fixed capacity. The flow on each arc must be less than this capacity. (in light blue)
- What is the overall performance measure for these decisions? The overall measure of performance is maximum throughput, so the goal is to maximize this quantity. The maximum flow is equal to the output of the S node. (in dark blue)
Let us name the following ranges:
| Beach name | Cells |
|---|---|
| From | B4: B15 |
| To | C4: C15 |
| Flow | D4: D15 |
| Capacity | F4: F15 |
| SupplyDemand | K5: K9 |
| MaximumFlow | D17 |
And let's insert the following functions:
Solve the model
Let’s enter the solver parameters:
The optimal solution is:
