Question

College Department. A college department has the problem of providing teachers for all courses offered by the department at the highest possible level of educational quality. There are two professors, two associate professors, one assistant professor, and one teaching assistant (TA). Six courses must be offered, and after appropriate introspection and evaluation, the following relative ratings (100 best rating) regarding the ability of each instructor to teach each of the six courses are assigned. Professor Course 1 Course 2 Course 3 Course 4 Course 5 Course 6 40 60 20 20 90 30 40 40 60 30 80 10 90 60 50 40 70 30 30 70 70 60 40 40 20 30 50 40 50 20 90 70 60 60 40 10 4 TA How the teaching staff be assigned to the courses to maximize educational quality in the department?

Answer 1

This is the original cost matrix: 40 40 90 30 20 90 60 40 60 70 30 70 20 60 50 70 50 60 20 30 40 60 40 60 90 80 70 40 50 40 30 10 30 40 20 10 Negate all values Because the objective is to maximize the total cost we negate all elements -40 -40-90 30 -20 90 -60 40 -60 70 -30 70 20 60 50 70 50 -60 20 30 40 -60 40 -60 -90 80 -70 40-50 -40 30 10 30 40-20 10 Make the matrix nonnegative The cost matrix contains negative elements, we add 90 to each entry to make the cost matrix nonnegative 50 50 30 50 30 20 60 20 70 30 40 20 40 30 70 60 50 30 50 30 0 60 70 0 10 20 50 40 50 60 80 60 50 70 80 Subtract row minima We subtract the row minimum from each row: 50 50 10 30 10 40 0 (-20) 50 10 20 0 20 10 (-20) 40 30 20 020 0 (-30) 0 60 70 0 10 20 50 40 50 10 30 10 20 30 (-50)

Subtract column minima We subtract the column minimum from each column: 50 40 0 60 50 0 20 10 20 10 0 20 40 20 20 50 0 1O 0 0 20 50 20 50 0 30 0 10 20 (-10) 10 (-20) Cover all zeros with a minimum number of lines There are 6 lines required to cover all zeros: 50 40 10 20 10 50 40 20 20 0 X 0 X 0 10 x 0 X 0 20 50 20 50 x 10 20 10 00 30 x 0 60 50 0 20 0 0 0 20 0 0 The optimal assignment Because there are 6 lines required, the zeros cover an optimal assignment 50 40 10 20 10 50 40 20 20 0 60 500 0 20 0 0 20 0 0 0 20 50 20 50 1O 10 20 10 00 30 This corresponds to the following optimal assignment in the original cost matrix: 40 40 90 3020 90 60 40 60 70 30 70 20 60 5070 50 60 20 30 40 6060 90 80 70 40 50 40 30 10 30 40 20 10 The optimal value equals 390
Professor 1 should teach course 3

Prof 2 must teach course 6

Prof 3 --Course 2

Prof 4 -- course 5

prof 5--course 1

ta- course 4

If you need any further clarification regarding this problem feel free to comment below