C&O 370
Final Project
The Teacher Assignment Problem
EOIN BRADY
94091270
JULIA RHEE
94041016
KEVIN WILLIAMS
94051616
November 18, 1997
Table of Contents
|
Summary of Results: |
|
|
Solution Summary – Core Problem |
Pg. 1 |
|
Hard Core Problem |
Pg. 1 |
|
Problem Statement - including discussions of extensions |
Pg. 4 |
|
Model - Core Version : |
|
|
Assumptions |
Pg. 5 |
|
Index Sets and Variables |
Pg. 5 |
|
Program |
Pg. 5 |
|
Model - Core Version Extension 1: |
|
|
Assumptions |
Pg. 6 |
|
Index Sets and Variables |
Pg. 6 |
|
Program |
Pg. 6 |
|
Model - Core Version Extension 2: |
|
|
Assumptions |
Pg. 7 |
|
Index Sets and Variables |
Pg. 7 |
|
Program |
Pg. 7 |
|
Model - Core Version Extension 3: |
|
|
Assumptions |
Pg. 8 |
|
Index Sets and Variables |
Pg. 8 |
|
Program |
Pg. 8 |
|
Model - Core Version Extension 4: |
|
|
Assumptions |
Pg. 8 |
|
Index Sets and Variables |
Pg. 9 |
|
Program |
Pg. 9 |
|
Model - Final Extension – Hard Core Version: |
|
|
Assumptions |
Pg. 10 |
|
Index Sets and Variables |
Pg. 10 |
|
Program |
Pg. 10 |
|
Core Problem Analysis |
Pg. 11 |
|
Model and Solution Critique |
Pg. 12 |
|
Analysis of the Core Parameters |
Pg. 13 |
|
Sensitivity Analysis to the Core Problem |
Pg. 13 |
|
Assessment of the Solution Validity |
Pg. 15 |
|
Usability by the Customer |
Pg. 15 |
|
Avenues for Further Study |
Pg. 16 |
|
Appendices – title page |
Pg. 17 |
Abstract:
The problem presented is the teacher - school assignment problem. The method used to solve this problem and further extensions of this problem is integer linear programming, more specifically network programming. The base model that has been used for the development of the models and the GAMS program is the 'Assignment Problem' as explained in Chvatal's text Linear Programming pg. 341. We have discovered that the models developed based on the specialised transportation pr oblem, the 'Assignment Problem', are efficient and effective. They provide consistently accurate results and have been tested under various scenarios. Therefore we conclude that the models developed are relevant and reliable, the GAMS programs developed p rovides unambiguous, accurate results and all the users' desired requirements have been met.
Summary of Results:
Solution Summary: - Core Problem
We have assumed that
|
· Teacher 1 prefers school |
1 |
· School 1 prefers teacher |
5 |
|
· Teacher 2 prefers school |
3 |
· School 2 prefers teacher |
1 |
|
· Teacher 3 prefers school |
2 |
· School 3 prefers teacher |
3 |
|
· Teacher 4 prefers school |
6 |
· School 4 prefers teacher |
4 |
|
· Teacher 5 prefers school |
5 |
· School 5 prefers teacher |
7 |
|
· Teacher 6 prefers school |
8 |
· School 6 prefers teacher |
6 |
|
· Teacher 7 prefers school |
2 |
· School 7 prefers teacher |
1 |
|
· Teacher 8 prefers school |
4 |
· School 8 prefers teacher |
5 |
|
· Teacher 9 prefers school |
6 |
· School 9 prefers teacher |
9 |
|
· Teacher 10 prefers school |
8 |
· School 10 prefers teacher |
7 |
In our solution we have
|
· Teacher 1 at school |
7 |
· Teacher 6 at school |
8 |
|
· Teacher 2 at school |
3 |
· Teacher 7 at school |
10 |
|
· Teacher 3 at school |
2 |
· Teacher 8 at school |
4 |
|
· Teacher 4 at school |
6 |
· Teacher 9 at school |
9 |
|
· Teacher 5 at school |
5 |
· Teacher 10 at school |
1 |
Solution Summary: - Hard Core Problem
Morning Preferences:
We have assumed that
|
· Teacher 1's preferences in order are School 1, 3, 5 |
· Teacher 2's preferences in order are School 3, 6, 9 |
|
· Teacher 3's preferences in order are School 2, 5, 8 |
· Teacher 4's preferences in order are School 1, 4, 6 |
|
· Teacher 5's preferences in order are School 5, 7, 10 |
· Teacher 6's preferences in order are School 8, 10, 4 |
|
· Teacher 7's preferences in order are School 4, 1, 2 |
· Teacher 8's preferences in order are School 7, 4, 3 |
|
· Teacher 9's preferences in order are School 6, 2, 9 |
· Teacher 10's preferences in order are School 10, 8, 1 |
|
NOW FOR THE SCHOOL |
· School 1's preferences in order are Teacher 5, 3, 8 |
|
· School 2's preferences in order are Teacher 1, 6, 9 |
· School 3's preferences in order are Teacher 3, 5, 7 |
|
· School 4's preferences in order are Teacher 4, 1, 10 |
· School 5's preferences in order are Teacher 7, 9, 2 |
|
· School 6's preferences in order are Teacher 6, 8, 3 |
· School 7's preferences in order are Teacher 1, 10, 4 |
|
· School 8's preferences in order are Teacher 5, 2, 8 |
· School 9's preferences in order are Teacher 9, 7, 1 |
|
· School 10's preferences in order are Teacher 10, 3, 5 |
|
|
|
|
|
Afternoon Preferences: |
· Teacher 1's preferences in order are School 2, 4, 6 |
|
· Teacher 2's preferences in order are School 5, 3, 7 |
· Teacher 3's preferences in order are School 8, 9, 1 |
|
· Teacher 4's preferences in order are School 4, 10, 6 |
· Teacher 5's preferences in order are School 7, 1, 2 |
|
· Teacher 6's preferences in order are School 3, 8, 5 |
· Teacher 7's preferences in order are School 10, 6, 4 |
|
· Teacher 8's preferences in order are School 1, 7, 9 |
· Teacher 9's preferences in order are School 2, 9, 8 |
|
· Teacher 10's preferences in order are School 6, 5, 3 |
NOW FOR THE SCHOOL |
|
· School 1's preferences in order are Teacher 4, 6, 8 |
· School 2's preferences in order are Teacher 5, 8, 3 |
|
· School 3's preferences in order are Teacher 2, 10, 7 |
· School 4's preferences in order are Teacher 1, 4, 6 |
|
· School 5's preferences in order are Teacher 9, 1, 2 |
· School 6's preferences in order are Teacher 3, 5, 7 |
|
· School 7's preferences in order are Teacher 6, 9, 4 |
· School 8's preferences in order are Teacher 7, 2, 8 |
|
· School 9's preferences in order are Teacher 5, 7, 10 |
· School 10's preferences in order are Teacher 8, 10, 1 |
In our solution we have:
Morning Solution
|
Teacher 1 goes to School 1 |
|
Teacher 6 goes to School 6 |
|
Teacher 2 goes to School 3 |
|
Teacher 7 goes to School 5 |
|
Teacher 3 goes to School 2 |
|
Teacher 8 goes to School 7 |
|
Teacher 4 goes to School 4 |
|
Teacher 9 goes to School 9 |
|
Teacher 5 goes to School 8 |
|
Teacher 10 goes to School 10 |
Afternoon Solution:
|
Teacher 1 goes to School 4 |
|
Teacher 6 goes to School 8 |
|
Teacher 2 goes to School 5 |
|
Teacher 7 goes to School 6 |
|
Teacher 3 goes to School 9 |
|
Teacher 8 goes to School 10 |
|
Teacher 4 goes to School 1 |
|
Teacher 9 goes to School 7 |
|
Teacher 5 goes to School 2 |
|
Teacher 10 goes to School 3 |
These results are for the basic core problem and the final hardcore problem. Further explanation of how these results were determined and the assumptions taken are discussed in the main body of the report. The programs written to determine these answer s can be found in the appendix.