Maximum Stream Resolution with Excel

The solver makes it possible to solve the problem of maximum flow with Excel from a node S to a node T in a directed graph.

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. In addition, each bow has a fixed capacity. The flow rate on each arc must be less than this capacity. (in light blue)
  • What is the overall measure of performance for these decisions? The overall measure of performance is maximum throughput, so the objective is to maximize this quantity. The maximum flow is equal to the output of node S. (in dark blue)

résolution flot maximum avec excel

Let us name the following ranges:

Beach nameCells
FromB4: B15
ToC4: C15
FlowD4: D15
CapacityF4: F15
SupplyDemandK5: K9

And let's insert the following functions:

résolution flot maximum avec excel

Solve the model

Let’s enter the solver parameters:

résolution flot maximum avec excel

The optimal solution is:

résolution flot maximum avec excel

To share
%d bloggers like this: