Three courses, which we call A, B, and C, need final examination rooms. Three rooms, X, Y, and Z,

are available. Any course can be assigned to any room, but since the exams take place at the same

time only one course can be put in each room. The value of placing each course in each room is

given in the following table, and the total value is the sum of the values of the three placements that

will be made.

Course Room X Room Y Room Z

A 10 2 -8

B 4 6 9

C 5 -2 10

(a) Formulate an minimum-cost-network-flow-problem (MCNFP) to maximize the

total value; write down the mathematical formulation including the definition of variables, the

objective function and all constraints. Then draw a graph to include all information about the

MCNFP. Which algorithm should be used to solve the MCNFP? Why?