USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

DEFINITION OF ASSIGNMENT MODEL

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

  1. Each resources is assigned exclusively to one task.
  2. Each task is assigned exactly one resource.
  3. For purposes of solution, the number of resources available for assignment must equal the number of tasks to be performed. Let xij be the variable in such a way that if and xij=0 or 1The general assignment model can be written as

    Maximise (or minimise) Z = C11 x11 + C12 x12 +           + C1n x1n +C21 x21 + … Cnxnn

    subject to

    x11+x12+…. +x1n      =1

    x21+x22+…. +x2n      =1

    :

    :

    xn1 + xn2 + …. + xnn = 1

    x11 + x21 + ….. + xnn = 1

    x12+x22+….. +xn2 =1

    :        :                :

    :        :                :

    x1n+x2n+….. +xnn =1

    xij= 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 Cij≥0 then an assignment schedule (xij) which satisfies  xij Cij= 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 Cij ≥0 and can produce at least one new Cij= 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).