15 Fly-by-Night Airlines is considering flying three flights.

The revenue from each flight and the airports used by each flight are shown in Table 11. When Fly-by-Night uses an airport, the company must pay the following landing fees

(independent of the number of flights using the airport):

airport 1, $300; airport 2, $700; airport 3, $500. Thus, if flights 1 and 3 are flown, a profit of 900 800 300

700 500 $200 will be earned. Show that for the network in Figure 25 (maximum profit) (total revenue from all flights) (capacity of minimal cut). Explain how this result can be used to help Fly-by-Night maximize profit (even if it has hundreds of possible flights). (Hint: Consider any set of flights F (say, flights 1 and 3). Consider the cut corresponding

to the sink, the nodes associated with the flights not in F, and the nodes associated with the airports not used by F. Show that (capacity of this cut) = (revenue from flights not in F)
+ (costs associated with airports used by F).)

Transcribed Image Text:

00 FL (Al) 900 300 600 F2 700 8 A2 800 F3 00 500 A3