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