Lesson 268: Maximum flow problem in Excel

This article will guide you to calculate the maximum flow in Excel.

Maximum flow

Use the solver in Excel to find the largest flow from node S to node T in a directed graph. The points in the graph are called nodes (S, A, B, C, D, E and T). The lines in the graph are called arcs (SA, SB, SC, AC, etc.).

Model building

The model we will deal with looks like this in Excel.

1. To construct this problem, we need to answer the following three questions.

a. What decisions will be made? For this problem, we need Excel to find the flow per arc. For example, if the traffic on SB is 2, cell D5 is equal to 2.

b. What are the constraints on these decisions? Net Flow (Flow Out – Flow In) of nodes A, B, C, D and E must be zero. In other words, Flow Out = Flow In.

c. What are the overall performance metrics for these decisions? The overall metric of performance is maximum flow, so the goal is to maximize this.

2. To make the model easier to understand,

3. Add function

Trial and error

1. For example, SADT path with flow is 2. SCT path with flow is 4. SBET path with flow is 2. These paths for total flow are 8.

Solve the model

1. On the Data tab, Solver

Enter the parameters. The result should match the figure below.

2. Import MaximumFlow for Objective.

3. Click Max.

4. Enter Flow into Changing Variable Cells.

5. Click Add .

6. Click Add

7. Click ‘Make Unconstrained Variables Non-Negative’ and select ‘Simplex LP’.

8. Click Solve

Optimal solution:

Conclusion: SADT path with flow 2. SCT path with flow 4. SBET path with flow 2. SCET path with flow 2. SACET path with flow 1. SACDT path with flow 1. These paths give total flow is 12.

In addition, you can also view many other excel articles here.