Question

Problem 22-6

The MediQuick lab has three lab technicians available to process blood samples and three jobs that need to be assigned. Each technician can do only one job. The table below represents the lab's estimate (in dollars) of what it will cost for each job to be completed.

JOB	TECH A		TECH B		TECH C
J-432	9		10		8
J-487	9		6		7
J-492	12		7		10

Assign the technicians to the jobs to minimize costs.

Job	Tech	Minimum Cost
J-432	(Click to select)BCA	$
J-487	(Click to select)CBA
J-492	(Click to select)CAB
Total		$

Answer 1

Let the binary variables for Job 432 being assigned to Tech A,B,C be a1,b1,c1 respectively. Similarly binary variables for Job 487 be a2,b2,c2 and for Job 492 be a3,b3 and c3.

Objective function is to minimize total cost and total cost = 9a1+10b1+8c1+9a2+6b2+7b2+12a3+7b3+10c3.

Constraints:

1. a1+b1+c1 = 1

2. a2+b2+c2 = 1

3. a3+b3+c3 = 1

The above 3 constraints shows that each job will only be assigned once.

4. a1+a2+a3 = 1

5. b1+b2+b3 = 1

6. c1+c2+c3 = 1

The above 3 constraints relate to the fact that each technician can do only 1 job.

7. All the variables are binary.

Solving the above in excel, using, solver function, we get the following solution:

	Tech A	Tech B	Tech C
Job
J 432	1	0	0
J 487	0	0	1
J 492	0	1	0
				Formula
Objective function	23			9a1+10b1+8c1+9a2+6b2+7b2+12a3+7b3+10c3
Constraints
1	=	1		a1+b1+c1 = 1
1	=	1		a2+b2+c2 = 1
1	=	1		a3+b3+c3 = 1
1	=	1		a1+a2+a3 = 1
1	=	1		b1+b2+b3 = 1
1	=	1		c1+c2+c3 = 1

Thus the solution (as required) is:

Job	Tech	Minimum cost
J 432	A	9
J 487	C	7
J 492	B	7
Total		23