Question

Consider the cost of assigning a task to an individual as shown in the table below. It is assumed that each individual can be assigned to at most one task, and each task can be assigned to at most one individual. The objective is to minimize the cost of assignments.

	individual
Task	1	2	3
1	17	18	16
2	14	19	17
3	15	19	18

(a) Write down the linear programming formulation of this problem. (i.e., write down the objective function and constraints – do not use a tableau.)

(b) Using the Hungarian Algorithm, solve this assignment problem (i.e., the problem described on the previous page). Please show the order in which the tableaus are used!

(c) State the optimal values of the variables and the optimal objective function.

Answer 1

(a) Write down the linear programming formulation of this problem. (i.e., write down the objective function and constraints – do not use a tableau.)

We have to check which task is allocated to which individual

Let Xij be the decision variable – the allocation of task i to an individual j

Xij=(1,0)

1= if task is allocated to the individual

0=if task is not allocated to the individual

Objective function

Minimize

Z= 17X11+ 18X12+ 16X13 + 14X21+ 19X22 + 17X23 + 15X31+ 19X32 + 18X33

Subject to

Constraints

Each task can be allocated to only one individual

1. 17X11+ 18X12+ 16X13 =1
2. 14X21+ 19X22 + 17X23 =1
3. 15X31+ 19X32 +18X33 =1

Each individual can be allocated only one task

4.17X11+ 14X21+ 15X31 =1

5.18X12+ 19X22 + 19X32 =1

6. 16X13 + 17X23 +18X33 =1

7.X11, X12,X13 , X21,X22 ,X23 , X31,X32 ,X33 =Binary varaiable(0,1)

Example

This is just an example for your understanding. This need not be the right solution

	individual
Task	1	2	3
1	0	1	0
2	1	0	0
3	0	0	1

(b) Using the Hungarian Algorithm, solve this assignment problem (i.e., the problem described on the previous page). Please show the order in which the tableaus are used!

Solution

task 1 - Individual 3
task 2 - Individual 1
task 3 - Individual 2