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 ijbe any variable then;
Xij = (1 if resource I is assigned to task j @0 if resource I is not assigned to task j)
Cij = 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 = ijCij
Hence, the mathematical formulation assumes this following form;
Determine ij 0 (i, j = 1, 2, …..n) so as to minimize, Z = ijCij 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 = C1111 + C1212 + …………+ C1n1n + C2121 + ………Cnnnsubject 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 Cij 0, the assignment schedule (ij) that satisfy ijCij= 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 Cij 0 should produce at least one new Cij= 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:-
