Return to Index
Operations Research Models and Methods
Problems Section
Problems for Network Flow Programming Models
 - Distance Problems

The solution to this problem uses the picture given as the network. Each undirected edge is replaced by two arcs, one in either direction. The costs on the arcs are both equal to the flight cost between the two cities.

a. Part a is a simple shortest path network. External flows are at LA (+1) and NY (-1). The solution will be the minimum cost route.

b. Put an external flow of +3 at LA and -3 at NY. Put an upper bound of 1 on each arc. The solution will restrict the flow to no more than 1 on each flight.

c.In an attempt to solve this problem, we divide each node i into two nodes i' and i''. Put an arc going from i' to i'' with lower bound on flow of 1. The solution will have flow through each city, but there is no guarantee that the solution will not include a cycle. For instance, the flow might plass from Phoe to Chic to Dal and back to Phoe. A cycle flow will not originate at LA or terminate at NY. A solution with a cycle would not have meaning as a solution to this problem.

Return to Top

tree roots

Operations Research Models and Methods
by Paul A. Jensen
Copyright 2001 - All rights reserved