Linear Programming: Assignment Method
It is concerned in allocating the jobs to each of the workers for minimum cost
or maximum revenues.
1. The assignment problem is the problem of assigning n workers to n
jobs, in such a way that a worker is assigned to only one job. The
workers assigned to it and the costs of completing all the jobs will be
minimized.
2. The assignment method is the standard procedure for solving the
assignment problem on the basis of the assignment table.
There are three steps to follow in solving an assignment problem:
1. Subtract the smallest cost from each entry in each row. If each zero
can now be assigned in a one-to-one correspondence with the
“workers”, an optimal solution is obtained. If not, go to step 2.
2. Subtract the smallest cost in each column. If the zero entries can now
be distributed in each one corresponding with the “workers,” an
optimal solution is obtained or reached. If not, go to step 3.
3. Cover the zero entries by vertical or horizontal lines, using least
number of lines possible. (This can be done by covering first row or
column having the most number of zeros.) Subtract the smallest
uncovered cost from each uncovered cost but add it to the entry found
at the intersection of the lines. If an assignment is already possible, an
optimal solution is reached. If not, repeat 3. An assignment is optimum
if the number of lines is equal to the number of rows or the number of
columns.
Example # 1
During the Foundation Day, the SITS Club four representatives participate in
different sports such as walkathon, marathon, Ping-pong and running. The
table below shows their performance per event (minutes).
Walkathon Marathon Ping Pong Running
Andie 20 30 25 26
Annika 25 26 27 30
Jazen 35 25 27 30
Louise 30 28 28 20
Since each representative is allowed to participate in only one event,
the assignment method is the most effective way to find an optimum
solution.
SOLUTION: n = 4…..n = 4
We start reducing the rows by subtracting the smallest number in each
row from all the numbers in the row.
Walkathon Marathon Ping Pong Running
Andie 0 10 5 6
Annika 0 1 2 5
Jazen 10 0 2 5
Louise 10 8 8 0
Now, we reduce each column by subtracting the smallest number in
each column from all of the numbers in the column.
Walkathon Marathon Ping Pong Running
Andie 0 10 3 6
Annika 0 1 0 5
Jazen 10 0 0 5
Louise 10 8 6 0
Since the number of lines is equal to the number of rows and columns,
the it is already optimal
Assigning the events to the representatives:
Andie = can play walkathon
Annika = can play walkathon and Ping-pong
Jazen = can play Marathon and Ping pong
Louise = can play running
Final Decision:
Representative Events Time
Andie Walkathon 20
Annika Ping – Pong 27
Jazen Marathon 25
Louise Running 20
TOTAL 92 minutes
Example # 2:
J1 J2 J3
W1 30 25 10
W2 15 10 20
W3 25 20 15
Step 1: Subtract the smallest value (ROW)
J1 J2 J3
W1 20 15 0
W2 5 0 10
W3 10 5 0
Step 2: Subtract the smallest value (COLUMN)
J1 J2 J3
W1 15 15 0
W2 0 0 10
W3 5 5 0
Step 3:
J1 J2 J3
W1 10 10 0
W2 0 0 15
W3 0 0 0
W1 = J3 = 10 W1 = J3 = 10
W2 = J1 = 15 W2 = J2 = 10
W3 = J2 = 20 W3 = J1 = 25
45 45
