Content deleted Content added
No edit summary |
No edit summary |
||
Line 35:
The problem is "linear" because the cost function to be optimized as well as all the constraints can be expressed as linear equations.
==Solving an assignment problem==
Assignment problems are generally easy to solve since there exists a one to one correspondence.
First the problem is written in the form of a matrix as given below
:<math>\begin{bmatrix}
a1 & a2 & a3 & a4\\
b1 & b2 & b3 & b4\\
c1 & c2 & c3 & c4\\
d1 & d2 & d3 & d4\end{bmatrix}</math>
Where a,b,c and d are the agents who have to perform tasks 1,2,3 and 4. a1,a2,a3,a4 denote the penalties incurred when a does task 1,2,3,4 respectively. Same hold true for the other symbols as well. Note that the matrix is a square matrix[this has to be so since each agent can perform only one task].
Then we perform row operations on the matrix. To do this, the lowest of all ai [i belonging to 1-4] is taken and is subtracted from the other elements in that row. This will lead to at least one zero in that row [We get multiple zeros when there are two equal elements which also happen to be the lowest in that row]. This procedure is repeated for all rows. We now have a matrix with at least one zero per row. Now we try to assign tasks to agents such that each agent is doing only one task and the penalty incurred in each case is zero. This is illustrated below.
:<math>\begin{bmatrix}
0 & a2' & ''0'' & a4'\\
b1' & b2' & b3' & ''0''\\
''0'' & c2' & c3' & c4'\\
d1' & ''0'' & d3' & d4'\end{bmatrix}</math>
The zeros that are in italics are the assigned tasks.
In some cases it may turn out that the above matrix cannot be used for assigning.
:<math>\begin{bmatrix}
0 & a2' & a3' & a4'\\
b1' & b2' & b3' & 0\\
0 & c2' & c3' & c4'\\
d1' & 0 & d3' & d4'\end{bmatrix}</math>
In the above case no assignment can be made. Note that task one is done efficiently by both agent a and c. Both cant do the same task. Also note that no one foes the task 3 efficiently.
To overcome this, we repeat the above procedure for all columns and then check if an assignment is possible. In most situations this will lead the result, but if it is still not possible to assign then the procedure described below must be followed.
[[Category:Optimization]]
| |||