Let us consider one assignment problem that includes ‘n’ resources for ‘n’ destinations. The objective of finding the solution is to determine the maximization or minimization. It means the maximization of total profit and minimization of total time taken to complete each and every task (‘n’ tasks).

For the formulating of assignment models, following assumptions should be considered:

- Each resource should be assigned to only one task
- Each task should be assigned to one resource

- To find out the solution, the available number of resources must be equal to total numbers of tasks to be performed.

Let _{ij}be any variable then;

_{Xij} = (1 if resource I is assigned to task j @0 if resource I is not assigned to task j)

C_{ij} = Objective function contribution if resource is assigned to task j

n = Number of resources and the number of tasks

Now, As only one job is assigned to one resource then, it can be written as,

_{ij}= 1 and _{ij}= 1

And the total assignment cost is given by,

Z = _{ij}C_{ij}

Hence, the mathematical formulation assumes this following form;

Determine _{ij} 0 (i, j = 1, 2, …..n) so as to minimize, Z = _{ij}C_{ij }subject to following constraints, i.e.;

_{ij}= 1 where, j = 1, 2, 3, …..n and _{ij}= 0 or 1

Thus,

The general assignment model can be written as,

Maximize or Minimize,

Z = C_{11}_{11} + C_{12}_{12} + …………+ C_{1n}_{1n} + C_{21}_{21} + ………C_{n}_{nn}subject to,

_{11} + _{12} + …………+ _{1n} = 1

_{21} + _{22} + …………+ _{2n} = 1

: : :

: : :

_{n1} + _{n2} + …………+ _{nn} = 1

_{11} + _{21} + …………+ _{n1} = 1

_{12} + _{22} + …………+ _{n2} = 1

: : :

: : :

_{1n} + _{2n} + …………+ _{nn} = 1

_{ij}= 0 or, 1 for all values of i and j

Students should notice that the variables are restricted to only two values i.e. 0 and 1 for this model. Here, 0 means non-assignment of resources and 1 means assignment of resources. This restriction is different from other Linear Programming (LP) models that we have seen so far.

**Theorem 1:**

The optimum assignment schedules remain unaltered if we subtract or add ant constant to/ from all the elements of row/ column of the assignment cost matrix.

**Theorem 2:**

For assignment problems where all C_{ij} 0, the assignment schedule (_{ij}) that satisfy _{ij}C_{ij}= 0 should be optimal.

These two theorems mentioned above are the basis of assignment algorithm. If we add/ subtract any suitable constant to/ from the elements of cost matrix, then the new C_{ij} 0 should produce at least one new C_{ij}= 0 at each row and column. And, it should try to make the assignments from these 0 positions. Thus, the assignment schedule becomes optimal if there is only one assignment in each row and column (It means exactly one should be assigned to 0).

**Links of Previous Main Topic:-**

- Linear programming learning objectives and outline of chapter
- Introduction learning objectives
- Duality in linear programming
- Learning objectives
- Learning objectives and chapter outline in assignment model

**Links of Next Finance Topics:-**