CS3252 Management Science
Tutorial # 8, September 28 - October 3, 1998

1. Four cargo ships (labeled A, B, C, and D) will be used for shipping goods from one port to four other ports (labeled 1,2,3, and 4). Any ship can be used for making any one of these four trips. However, because of differences in the ships and cargoes, the total cost of loading, transporting, and unloading the goods for the different ship-port combinations varies considerably, as shown in the following table:

   

   The objective is to assign the ships to ports on a one-to-one basis in such a way as to minimize the total cost for all four shipments. Use the Hungarian method to solve this problem.

2. Three tutors must be assigned to teach six tutorial groups of CS1000 Very Basic Computer Science. Each tutor must teach 2 tutorials and each has ranked the six time periods during which CS1000 is taught as shown in the table below. A ranking of 10 means that the tutor wants to teach that time, and a ranking of 1 means that he or she does not want to teach at that time. Determine an assignment of tutors to groups that will maximize total satisfaction of the tutors.

   

3. You have just been hired by SDU and face the following problem. There are 4 men and 4 women, and let be a measure of the mutual pleasure the ith man and the jth woman derive, on the average per day spent together on a scale of one to ten. This measure is summarized in the following matrix

   

   1. Let be the fraction of his time/day that man i spends with woman j. Suppose that the men and women do nothing but spend their time together. Formulate a linear program that will help these men and women to find out how much time that they should spend with each other to maximize their total happiness.
   2. Explain why the optimal solution in part (a) will have four and twelve Since the optimal solution requires that each person spend all his or her time with one person of the opposite sex, this result is often referred as the Marriage Theorem.
   3. Determine the marriage partner of each person.
   4. What can you say about the solution of the linear program if you replace the max in the objective function by min.