Let us consider an assignment problem involving n resources (origins) to n destinations. The objective making the assignment can be one of minimisation or maximisation(i.e .. minimisation of total time required to complete n tasks or maximisation of total profit from assigning sales persons to sales territories)

Following assumptions have to be made while formulating assignment models:-

**Assumptions **

- Each resources is assigned exclusively to one task.
- Each task is assigned exactly one resource.
- For purposes of solution, the number of resources available for assignment must equal the number of tasks to be performed. Let x
_{ij}be the variable in such a way that if and x_{ij}=0 or 1The general assignment model can be written asMaximise (or minimise) Z = C

_{11}x_{11}+ C_{12}x_{12}+ + C_{1n}x_{1n}+C_{21}x_{21}+ … C_{n}x_{nn}subject to

x

_{11}+x_{12}+…. +x_{1n}=1x

_{21}+x_{22}+…. +x_{2n}=1:

:

x

_{n1}+ x_{n2}+ …. + x_{n}_{n}= 1x

_{11}+ x_{21}+ ….. + x_{nn}= 1x

_{12}+x_{22}+….. +x_{n2}=1: : :

: : :

x

_{1n}+x_{2n}+….. +x_{nn}=1x

_{ij}= 0 or 1 for all values of i and j.The student should notice that for this model the variables are restricted to the two values of 0 i.e., non -assignment of the resources or I i.e., assignment of the resource. This restriction is quite different from the other Linear Programming models we have seen so far.

**Theorem 1**. The optimum assignment schedule remains unaltered if we add or subtract a constant to/from all elements of the row or column of the assignment cost matrix.**Theorem 2**. If for an assignment problem all C_{ij≥}0 then an assignment schedule (x_{ij}) which satisfies x_{ij}C_{ij}= 0. must be optimal. These two theorems are the basis of the assignment algorithm. We add or subtract suitable constant to/from the elements of cost matrix in such a way that new C_{ij}≥0 and can produce at least one new C_{ij}= 0 in each row and each column and try and make assignments from among

these 0 positions. The assignment schedule will be optimal if there is exactly one assignment in each row, and each column (i.e., exactly one assigned 0).

## Recent Comments