LAB 5: ASSIGNMENT PROBLEMS AND SPARSE MATRICES
Mathematics:
The assignment problem is to assign tasks to facilities on a onetoone basis in an optimal way. An example of the assignment problem is to assign n workers to n jobs such that the total cost (e.g. the costs of training, qualificationdependent salaries, etc.) is minimized. There are exactly n! = n*(n1)*(n2)*…*3*2*1 ways to assign n workers to n jobs. Costs of all n! combinations can be checked and the minimal cost can be found. However, such algorithm is computational inefficient, since the number of combinations grows fast with larger n, e.g. 10! = 3,628,800. Two Hungarian mathematicians, D. Konig and E. Egervary, proposed a better algorithm called the Hungarian method. This project exploits a simple computational method to approach to the optimal solution. (The Hungarian method would be the best solution but it is much more difficult to code).
Let us define the nbyn cost matrix C and the nbyn assignment matrix X:
C = _{}, X = _{}
Here c_{i,j} is
the cost of assigning the ith worker to the jth job
(in $) and x_{i,j} is assignment, such that x_{i,j} = 1 if
the ith worker is assigned to the jth job, and x_{i,j }=
0, otherwise. The assignment is onetoone if the matrix X has no two ones in the same row or in the same column. The cost of the current
assignment is
z = _{}_{}c_{i,j} x_{i,j}
We will be working
with the following problem: assign n
= 9 candidates to n=9 jobs to minimize the total salary cost paid by the department. The
individual salaries of each candidate at each job position depend on their
qualification and are given by the cost matrix (in $ per hour):

Sam 
Jill 
John 
Liz 
Ann 
Lois 
Pete 
Alex 
Herb 
Administrator 
20 
15 
10 
10 
17 
23 
25 
5 
15 
Secretary to the
Chair 
10 
10 
12 
15 
9 
7 
8 
7 
8 
Undergraduate
Secretary 
12 
9 
9 
10 
10 
5 
7 
13 
9 
Graduate
Secretary 
13 
14 
10 
15 
15 
5 
8 
20 
10 
Financial Clerk 
12 
13 
10 
15 
14 
5 
9 
20 
10 
Secretary 
15 
14 
15 
16 
15 
5 
10 
20 
10 
Web designer 
7 
9 
12 
12 
7 
6 
7 
15 
12 
Receptionist 
5 
6 
8 
8 
5 
4 
5 
10 
7 
Typist 
5 
6 
8 
8 
5 
4 
5 
10 
7 
If we start with
the position of Administrator and assign it to Alex (he gets the minimal
salary for this position), then we assign the position of Secretary to Chair to Lois (he gets the minimal
salary for this position), and so on, up to the position of Typist, then the assignment is given by the assignment matrix:
X =
0 0 0 0
0 0 0 1 0
0 0
0 0 0 1 0
0 0
0 0
0 0 0 0 1
0 0
0
0 1 0 0 0
0 0 0
0 0
0 0 0 0 0
0 1
0 1
0 0 0 0 0
0 0
1 0
0 0 0 0 0
0 0
0 0
0 0 1 0
0 0 0
0 0
0 1 0 0 0
0 0
where the total
cost z = 73. The optimal assignment is however different
from the firsttoassign solution above. The optimal assignment is:
X = 0 0
0 0 0 0
0 1 0
0 0
0 0 0 0 0
0 1
0 0
0 1 0 0 0
0 0
0 0
0 0 0 0 1
0 0
0 0
1 0 0 0 0
0 0
0 0
0 0 0 1 0
0 0
0 0
0 0 1 0 0
0 0
1 0
0 0 0 0 0
0 0
0 1
0 0 0 0 0
0 0
where the total
minimal cost z_{*} =
64.
Objectives:
·
understand
computational algorithms for solving the assignment problems
·
code
the computational algorithms by using MATLAB programming constructions
·
exploit
the algorithms for different assignment problems
Steps
of the computational algorithm:
a)
Build
up the assignment matrix X from a zero nbyn matrix
by assigning 1 rowbyrow to the columns of the permutation
matrix.
b)
Compute the total cost z of
the assignment. Use
function "sum" to compute z.
Steps
of the computational algorithm:
a)
Organize
a single loop for rows of matrix X.
b)
Use
MATLAB function "sort" with two output arguments (for the
value and for its index in the row) to sort costs in the ascending order.
c)
Organize
another loop for elements of the sorted vector in the ascending order.
d)
Use
MATLAB function "any" to check if the selected column has
already nonzero values.
e)
For
each row, compute the difference in costs that would result if the current 1assigned
position interchanges with the position in the other (n1)
column. You should compute (n1) numbers for each row.
f)
Use
functions "find" and "min".
g)
If
all numbers are positive or zero, move to the next row.
h)
If
there exists a negative value for Dz, select the minimal value of
Dz and make the interchange of 1s and 0s in
the corresponding positions in the assignment matrix X.
i)
Compute
the total cost of the new assignment.
Quiz:
(a) _{} (b) _{} (c) _{}