networks3

Maximum Flow and Minimum Cut Problem

During peak traffic hours, many cars are travelling from a downtown parkade to the nearest freeway on-ramp.  The traffic engineers have decided to widen some downtown roads to accommodate the heavy flow of cars traveling between these two points.  Which roads should the engineers widen in order to achieve this goal?

The video shows a network of roads that connect the parkade (at node A) to the freeway on-ramp (at node G).  The answer to the question is found by first finding the maximum flow from A to G, and then analyzing the flow pattern to find the minimum cut. Arcs in the minimum cut set are restricting the flow between A and G.

Arc labelling: Arcs are labelled with their flow capacities in either direction. The figure below shows the arc connecting nodes A and B. This shows that the arc has a flow capacity of 5 in the A-to-B direction, and a flow capacity of 0 in the B-to-A direction, in other words it is a one-way street from A to B. 





Popular posts from this blog

Contents

Chapter 1: Introduction.  An introduction to the process of optimization and an overview of the major topics covered in the course.  Last revision: December 2020 . Chapter 2: Introduction to Linear Programming.  The basic notions of linear programming and the simplex method. The simplex method is the easiest way to provide a beginner with a solid understanding of linear programming.  Last revision: December 2020. See animation  LP1 . A good  article on formulating LPs  by Gerry Brown and Rob Dell. Example questions with solutions . March 4, 2021. Chapter 3: Towards the Simplex Method for Efficient Solution of Linear Programs.  Cornerpoints and bases. Moving to improved solutions.  Last revision: December 2020 . See animation  LP2 . Chapter 4: The Mechanics of the Simplex Method.  The tableau representation as a way of illustrating the process of the simplex method. Special cases such as degeneracy and unboundedness.  Last revis...
Read more