An advertising company underwent a thorough reorganization during which the m employees of the department of Creative Designers got laid off.

An advertising company underwent a thorough reorganization during which the m employees of the department of Creative Designers got laid off. However n > m new positions have been created in the company. The human resources manager interviews all m employees regarding their interest in the positions and their qualifications. Then he assigns a score sij to each employee i for each position j (s)he is willing to accept reflecting how qualified employee i is for position j.

The goal of the manager is to assign jobs to employees so that the sum of the scores of the employees who are assigned to jobs is maximized. A single job cannot be assigned to more than one employee and a single employee may not be assigned to more than one job.

Now consider the specific instance of the above problem where m = 2, n = 3, sij = 1 for all

1 <= i <= 2; 1 <= j 3.

i. Write out the IP for this instance. Write the LP for its linear programming

relaxation and take the dual of the relaxed LP (show all your work).

ii. Assume that the dual LP has an integral solution. Interpret the dual LP in

graph-theoretic terms.