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.
|
