Return to Index
Operations Research Models and Methods
Problems Section
Problems for Network Flow Programming Models
 - Variations on the Shortest Path Problem

For each of the problems, the given network forms the basis of the network model. Each part modifies the network or adds features.

a. Put an external flow of 1 at node 1, and put an external flow of -1 at node 16. The arc from node i to node j has the unit cost of t(i, j).

b. Replace each node i into two nodes and label one node i' and the other node i''. All the nodes formerly entering node i will now enter node i', and all the nodes formerly leaving node i will now leave node i''. Put an arc from i' to i'' with upper bound 1. This restricts the flow into each node i' to one unit. Now put external flows of 2 at node 1, and -2 at node 16. The arc costs are t(i, j) as before. Solving the problem will result in two disjoint paths.

c. Use the network as given but make the upper bound on arc (i, j) equal to c(i, j). Put an arc entering each node i. The origin of the arc is 0, outside the network. Place an upper bound on the arc of b(i). Put an arc leaving node 16. The upper bound should be high and the cost is -1. Solving the problem will result in a maximum flow leaving node 16.

d. The problem asks for a mathematical programming formulation. Write the linear programming model that represents the network in the picture. The variables are arc flows. Add a constraint that says the sum of the arc flows must be greater than 1. Note that the network given has no directed cycles, so the solution will have no cycle flows.

Return to Top

tree roots

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