SOLUTION: An airline company has drawn up a new flight schedule involving five flights. To assist in allocating five pilots to the flights, it has asked them to state their preference score

Question 1174850: An airline company has drawn up a new flight schedule involving five flights. To assist
in allocating five pilots to the flights, it has asked them to state their preference scores by giving each flight a number out of 10 .The higher the number , the greater is the preference.
Certain of these flights are unsuited to some pilots owing to domestic reasons. These have
been marked with a X
a b C d e
A 8 2 x 5 4
B 10 9 2 8 4
C 5 4 9 6 x
D 3 6 2 8 7
E 5 6 10 4 3
Flight number
What should be the allocation of the pilots to flights in order to meet as many performances as
possible? (Hint: The problem is to maximize the total preference score).
Answer by CPhill(1959) (Show Source): You can put this solution on YOUR website!
This is a classic assignment problem that can be solved using the Hungarian Algorithm. Since we need to maximize the total preference score, we'll need to negate the preference scores to convert it to a minimization problem.
**1. Prepare the Cost Matrix**
First, replace the 'x' entries with a very low number (e.g., -100) to ensure they are not selected. Then, negate all the preference scores to convert the maximization problem to a minimization problem.
```
a b c d e
A -8 -2 100 -5 -4
B -10 -9 -2 -8 -4
C -5 -4 -9 -6 100
D -3 -6 -2 -8 -7
E -5 -6 -10 -4 -3
```
**2. Apply the Hungarian Algorithm**
* **Row Reduction:** Subtract the smallest element in each row from all elements in that row.
```
a b c d e
A -6 6 108 -3 -2
B -8 -7 0 -6 -2
C -1 0 -5 -2 104
D 1 -3 0 -6 -5
E -2 -3 -7 -1 0
```
* **Column Reduction:** Subtract the smallest element in each column from all elements in that column.
```
a b c d e
A -5 9 108 -2 -2
B -7 -4 0 -5 -2
C 0 3 -5 -1 104
D 2 0 0 -5 -5
E 0 0 -7 0 0
```
* **Cover Zeros:** Draw the minimum number of horizontal and vertical lines to cover all zeros.
```
a b c d e
A -5 9 108 -2 -2
B -7 -4 0 -5 -2
C 0 3 -5 -1 104
D 2 0 0 -5 -5
E 0 0 -7 0 0
| | --- | ---
```
* **Optimal Allocation:** Since we have five lines covering the zeros, we can make an optimal allocation.
* **Find Optimal Assignments:**
* Start by looking for rows or columns with single zeros.
* Pilot E: E-e
* Pilot D: D-c
* Pilot C: C-a
* Pilot B: B-b
* Pilot A: A-d
**3. Convert Back to Preference Scores**
* A-d: 5
* B-b: 9
* C-a: 5
* D-c: 2
* E-e: 3
**4. Calculate Total Preference Score**
* Total = 5 + 9 + 5 + 2 + 3 = 24
**Allocation**
* Pilot A: Flight d
* Pilot B: Flight b
* Pilot C: Flight a
* Pilot D: Flight c
* Pilot E: Flight e
**Total Preference Score: 24**

RELATED QUESTIONS
An airline company has drawn up a new flight schedule involving five flights. To assist... (answered by CubeyThePenguin)

1. A car rental company has one car at each of five depots a, b, c, d and e. A customer... (answered by edlawitayele@yahoo.com)

An airline has 82% of its flights depart on schedule, it has 65%. of its flights depart... (answered by Boreal)

An airline has room for 262 passengers. Because some people do not show up, the airline... (answered by ewatrrr)

There are 10 Airmoon flights and 15 Airsun flights daily from Yorktown to Newcity, as... (answered by ewatrrr)

Suppose you work for an airline and you are taking reservations for a flight on an... (answered by Boreal)

An airline has 6 flights that it wishes to advertise in one-page ads in a sunday... (answered by robertb)

A one-plane airline has a passenger capacity of 120. The number of passengers on a... (answered by jim_thompson5910)

From experience, an airline knows that only 73 percent of the passengers booked on a... (answered by math_tutor2020)