The first thing to do for this small problem is to enumerate all feasible tours. We do not consider a collection of flights which involve an intermediate layover a tour. There are 10 one-flight tours, and either 37 or 41 three flight tours depending upon whether on distinguishes the origin city on a nondead-heaing tour. These tours are indicated below:

One-flight tours (All costs $3,000)		Two-flight tours		Cost	Three-flight tours		Cost
1	101	11	101, 23	$ 3,000	25	101, 23, 17	$ 2,000
2	410	12	410, 13	$ 2,000	26	101, 23, 11	$ 3,000
3	220	13	410, 19	$ 3,000	27	410, 19, 17	$ 3,000
4	17	14	220, 17	$ 3,000	28	410, 19, 11	$ 2,000
5	7	15	220, 11	$ 2,000	29	220, 17, 101	$ 3,000
6	13	16	17, 101	$ 3,000	30	220, 11, 410	$ 3,000
7	11	17	7, 13	$ 3,000	25	17, 101, 23	$ 2,000
8	19	18	7, 19	$ 3,000	31	7, 19, 17	$ 3,000
9	23	19	11, 410	$ 3,000	32	7, 19, 11	$ 3,000
10	3	20	19, 17	$ 2,000	33	11, 417, 13	$ 3,000
		21	19, 11	$ 3,000	28	11, 410, 19	$ 2,000
		22	23, 17	$ 3,000	34	19, 17, 101	$ 3,000
		23	23, 11	$ 3,000	28	19, 11, 410	$ 2,000
		24	3, 23	$ 2,000	25	23, 17, 101	$ 2,000
					35	23, 11, 410	$ 3,000
					36	3, 23, 17	$ 3,000
					37	3, 23, 11	$ 3,000

Formulate the problem to find the minimum cost of scheduling the crews to make sure every flight will be able to depart at the time scheduled.

Hint: We do not distinguish the city of origin on nondeadheading three flight tours. That's why the tour with flights 101, 23, 17 is the same as 17, 101, 23.

The Sayre-Priors Airline operates the following set of scheduled flights: Flight No. 101 410 220 17 7 13 11 19 Origin Chicago New York New York Miami LA Chicago Miami Chicago LA Miami Destination Time of Day LA afternoon Chicago afternoon Miami night Chicago morning Chicago afternoon New York night New York morning Miami night Miami night LA afternoon 23 3 The Flight Operations Staff would like to set up a low cost crew assignment schedule. The basic problem is to determine the next flight, if any, that a crew operates after it completes one flight. A basic concept needed in understanding this problem is that of a tour. The characteristics of a tour are as follows: A tour consists of from 1 to 3 connecting flights. A tour has a cost of $2,000 if it termintates in its city of origin. - A tour which requires "deadheading", i.e., terminates in a city other than the origin city, costs $3,000. In airline parlance, a tour is frequently called a "pairing" or a "rotation". The following are examples of acceptable tours: Tour 17, 101, 23 220, 17, 101 410, 13 Cost $2,000 $3,000 $2,000