Theorem 1: If a constant is added (or subtracted) to every element

of any row (or column) of the cost matrix [cij] in an assingment

problem then an assingment which minimises the total cost for the

new matrix will also minimize the total cost matrix.

Theorem 2: If all cij 0 and there exists a solution

xij = Xij such that

i

j

cij xij = 0.

then this solution is an optimal solution, i.e., minimizes z.

The computational proecdure is given as under: