# USE OF LINEAR PROGRAMMING TO SOLVE ASSIGNMENT PROBLEM - Quantitative Techniques for management

## Linear Programming Assignment problem example

A linear programming model can be used to solve the assignment problem. Consider the example shown in the previous table, to develop a linear programming model.
Let,

x11 represent the assignment of operator A to job 1
x12 represent the assignment of operator A to job 2
x13 represent the assignment of operator A to job 3
x21 represent the assignment of operator B to job 1
and so on.

Formulating the equations for the time taken by each operator,
10 x11 + 16 x12 + 7 x13 = time taken by operator A.
9 x21 + 17 x22 + 6 x23 = time taken by operator B.
6 x31 + 13 x32 + 5 x33 = time taken by operator C.

The constraint in this assignment problem is that each operator must be assigned to only one job and similarly, each job must be performed by only one operator. Taking this constraint into account, the constraint equations are as follows:

x11 + x12 + x13< 1 operator A
x21 + x22 + x23< 1 operator B
x31 + x32 + x33< 1 operator C
x11 + x21 + x31 = 1 Job 1
x12 + x22 + x32 = 1 Job 2
x13 + x23 + x33 = 1 Job 3

Objective function: The objective function minimizes the time taken to complete all the jobs. Using the cost data table, the following equation can be arrived at:

The objective function is,
Minimize Z = 10 x11 + 16 x12 + 7 x13 +9 x21 + 17 x22 + 6 x23 +6 x31 + 13 x32 + 5 x33

The linear programming model for the problem will be,

Minimize Z = 10 x11 + 16 x12 + 7 x13 +9 x21 + 17 x22 + 6 x23 +6 x31 + 13 x32 + 5 x33

subject to constraints

x11 + x12 + x13< 1 ....................(i)
x21 + x22 + x23< 1 ....................(ii)
x31 + x32 + x33< 1 ....................(iii)
x11 + x12 + x13 = 1 ....................(iv)
x12 + x22 + x32 = 1 ....................(v)
x13 + x23 + x33 = 1 ....................(vi)
where, xij> 0 for i = 1,2,3 and j = 1,2,3.

The problem is solved on a computer, using transportation model in TORA package. The input screen and output screens are shown in the previous and following figures respectively.

TORA, Input Screen

TORA, Output Screen

The objective function value = 28 mins.

The Assignment Schedule