Maximum flow problem with Excel

Use the solver in Excel to find the maximum flow from node S to node T in a directed network.

Formulate the problem

To formulate this maximum flow problem, answer the following 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 2, cell D5 equals 2. (in yellow)
  • What are the constraints on these decisions? The Net Flow (Flow Out – Flow In) of node A, B, C, D and E should be equal to 0. In other words, Flow Out = Flow In. Also, each arc has a fixed capacity. The flow on each arc should be less than this capacity. (in light blue)
  • What is the overall measure of performance for these decisions? The overall measure of performance is the maximum flow, so the objective is to maximize this quantity. The maximum flow equals the Flow Out of node S. (in dark blue)

LP49

Name the following ranges:

Range Name Cells
From B4:B15
To C4:C15
Flow D4:D15
Capacity F4:F15
SupplyDemand K5:K9
MaximumFlow D17

And insert the following functions:

LP50

Solve the model

Enter the solver parameters:

LP51

The optimal solution:

LP52

Publicités