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**
|
|
|
