A regional airline, Northwest Commuter, has started operating on the west coast of the United States. It has become established as a no-frills airline providing low-cost commuter flights between the west coast cities of Seattle, Portland, and San Francisco. The company has been able to achieve fast turnaround times between flights, but in order to further keep the costs low, the management needs to find new ways for Northwest Commuter to become a more efficient airline. In particular, management wants to start by dropping unprofitable flights and then identifying the most profitable flights.

Imagine that any number of airplanes desired can be leased for now. The leasing and operating costs for each airplane is $30,000 per day, that is incurred (accounted) at 12 midnight every day. At the end of the day, an airplane might remain in the city where it landed on its last flight which does not have any additional daily operating cost (on top of $30,000). Another option is to fly empty overnight to another city to be ready to start a flight from there the next morning. The cost of this latter option is an additional $5,000.

The following table shows the 22 possible flights that are being considered for the coming year. The last column gives the estimated net revenue (with the unit of thousands of dollars) for each flight, given the average number of passengers anticipated for that flight. To simplify the analysis, assume for now that there is virtually no turnaround time between flights so the next flight can begin as soon as the current flight ends. Also, if an immediate next flight is not available, the airplane would wait in the airport until the next scheduled flight from that city.

Flight #	From	To	Depart	Arrive	Expected Revenue ($1000's)
1257	Seattle	San Francisco	8 AM	10 AM	37
2576	Seattle	Portland	10 AM	11 AM	20
8312	Seattle	San Francisco	10 AM	12 PM	25
1109	Seattle	San Francisco	12 PM	2 PM	27
3752	Seattle	San Francisco	3 PM	5 PM	23
2498	Seattle	Portland	3 PM	4 PM	18
8787	Seattle	San Francisco	5 PM	7 PM	29
8423	Seattle	Portland	7 PM	8 PM	27
7922	Portland	Seattle	9 AM	10 AM	20
5623	Portland	San Francisco	10 AM	12 PM	23
2448	Portland	San Francisco	11 AM	1 PM	19
1842	Portland	Seattle	12 PM	1 PM	21
3487	Portland	Seattle	2 PM	3 PM	22
4361	Portland	San Francisco	4 PM	6 PM	29
4299	Portland	Seattle	6 PM	7 PM	27
1288	San Francisco	Seattle	8 AM	10 AM	32
3335	San Francisco	Portland	9 AM	10 AM	26
9348	San Francisco	Seattle	11 AM	1 PM	24
7400	San Francisco	Seattle	12 PM	2 PM	27
7328	San Francisco	Portland	12 PM	2 PM	24
6386	San Francisco	Portland	4 PM	6 PM	28
6923	San Francisco	Seattle	5 PM	7 PM	32

Management developed a network associated with the above flight list that displays the feasible routings of the flights, that is "partially" shown below. There are separate nodes for each combination of city and each hour between 8am to 8pm. The forward cross arcs represent the flight options according to the above table, and the forward horizontal arcs show the option of a plane staying in the same city for the next hour at each point in time. The backward arcs from 8pm to 8am represent the case that airplane remains in the same airport until the next day or fly empty overnight to another city to prepare for the next day.