Decision Mathematics 2 - Allocation Problems

• Subtract the smallest value in each row from every other value in that row
• Subtract the smallest value in each column from every other value in that column
• This gives you the opportunity cost matrix

• Reduce rows then columns
• Test for optimality by covering all zero cells with as few lines as possible.  If optimal, the number of lines covering the zero cells should be equal to n for an nxn matrix
• Revise the opportunity cost matrix

• Find the smallest uncovered number in the matrix and subtract this from all uncovered values in the matrix
• Add the same number to all cells that are covered by two lines
• If a cell is only covered by one line, do not add or subtract anything

Subtract every value in the table from the largest value in the table (so to 'flip' the numbers so that the smallest is now the biggest and vice versa) and continue as normal by reducing rows, then columns, then checking for optimality, then modifying.

For any matrix, each row and column must only have one value chosen.  Therefore, when forming a linear program, you must add one of each cell and total to one.  Example, for a matrix with 3 workers P, Q & R and 3 jobs A, B & C;

Pa + Pb + Pc = 1

Qa + Qb + Qc = 1

Ra + Rb + Rc = 1

Pa + Qa + Ra = 1

Pb + Qb + Rb = 1

Pc + Qc + Rc = 1