The figure below shows several cities. The lines between the cities
are airline flights for a particular carrier. The numbers on the
lines are flight costs. Flights are available in either direction
with the same cost.
Several problems are listed below. You have a minimum cost
network flow algorithm to solve the problem, and you are to
show the appropriate model that you will use for each case.
If the solution to the model does not actually solve the problem
given, indicate in what way it will fail.
a. Show the model that finds the minimum cost route from LA
to NY.
b. You have three shipments to send from LA to NY. For safety
reasons we have the added requirement that a flight can carry
at most one shipment. The goal is to minimize shipping cost.
c. Show the model that finds the minimum cost route from LA
to NY. We have the added requirement that the traveler wants
to pass through every other city exactly once on his trip.
|
