Assignment problem: Difference between revisions

Revision as of 22:21, 14 December 2005

Revision as of 23:16, 14 December 2005

Line 52:

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.

[Note-I havent used the matrix notation since formatting is not possible with that]

:<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.

0 &nbsp;&nbsp;&nbsp; a2' &nbsp; 0'&nbsp;&nbsp; a4' <br/>

b1' &nbsp; b2' &nbsp; b3' &nbsp; ''0''\\ <br/>

0' &nbsp;&nbsp; c2' &nbsp; c3' &nbsp; c4' <br/>

d1' &nbsp; 0' &nbsp;&nbsp; d3'&nbsp; d4' <br/>

The zeros that are inindicated italicsas 0' are the assigned tasks.

In some cases it may turn out that the above matrix cannot be used for assigning.

0 &nbsp;&nbsp;&nbsp; a2' &nbsp; a3'&nbsp; a4' <br/>

:<math>\begin{bmatrix}

0b1' &nbsp; a2b2' &nbsp; a3b3' &nbsp; 0 <br/> a4'\\

0 &nbsp;&nbsp;&nbsp; c2' &nbsp; c3' &nbsp; c4' <br/>

b1' & b2' & b3' & 0\\

d1' &nbsp; 0 &nbsp;&nbsp;&nbsp; d3'&nbsp; d4' <br/>

0 & c2' & c3' & c4'\\

d1' & 0 & d3' & d4'\end{bmatrix}</math>

In the above case no assignment can be made. Note that task one1 is done efficiently by both agent a and c. Both cant dobe assigned the same task. Also note that no one foes thedoes 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.

Initially assign as many tasks as possible then do the following[assign tasks in rows 2,3 and 4]-

0 &nbsp;&nbsp;&nbsp; a2' &nbsp; a3'&nbsp; a4' <br/>

b1' &nbsp; b2' &nbsp; b3' &nbsp; 0\\' <br/>

0' &nbsp;&nbsp; c2' &nbsp; c3' &nbsp; c4' <br/>

d1' &nbsp; 0' &nbsp;&nbsp; d3'&nbsp; d4' <br/>

Mark all rows having no assignments [row 1]. Then mark all columns having zeros in that row [column 1]. Then mark all rows having assignments in the given column [row 3]. Then mark all columns having assignments in the given rows. Repeat this till a closed loop is obtained.

&times;

0 &nbsp;&nbsp;&nbsp; a2' &nbsp; a3' &nbsp; a4' &nbsp;&nbsp; &times; <br/>

b1' &nbsp; b2' &nbsp; b3' &nbsp; 0' &nbsp;&nbsp; <br/>

0' &nbsp;&nbsp; c2' &nbsp; c3' &nbsp; c4' &nbsp;&nbsp; &times; <br/>

d1' &nbsp; 0' &nbsp;&nbsp; d3' &nbsp; d4' &nbsp; <br/>

Now draw lines through all marked columns and unmarked rows.

<s>0</s> &nbsp;&nbsp;&nbsp; a2' &nbsp; a3' &nbsp; a4' <br/>

<s>b1' &nbsp; b2' &nbsp; b3' &nbsp; 0'&nbsp;&nbsp;</s> <br/>

<s>0'</s> &nbsp;&nbsp; c2' &nbsp; c3' &nbsp; c4' <br/>

<s>d1' &nbsp; 0' &nbsp;&nbsp; d3' &nbsp; d4'</s> <br/>

Note that since a verticle line cannot be drawn i have used a horizontal line to cut the 1st column.

From the elements that are left, find the lowest value. Subtract this from all elements that are not struck. Add this to elements that are present at the intersection of two lines. Leave other elements unchanged. Now assign the tasks using above rules. Repeat the procedure till an assignment is possible.