Topper Copies

On a given day District headquarter has the information that one ambulance van is stationed at each of the 5 locations $A, B, C, D$ and $E$. The district quarter is to be issued for the ambulance van to reach 6 locations of ambulance vans and destinations are given in the matrix below. Decide the assignment of the vans for minimum total distance, and also state which destination should not expect ambulance van to arrive. | From \ To (distance in km) | P | Q | R | S | T | U | |---|---|---|---|---|---|---| | A | 18 | 21 | 31 | 17 | 26 | 29 | | B | 16 | 20 | 18 | 16 | 21 | 31 | | C | 30 | 25 | 27 | 26 | 18 | 19 | | D | 25 | 33 | 45 | 16 | 32 | 20 | | E | 36 | 30 | 18 | 15 | 31 | 30 |

Ayan Jain, AIR 16, 2023

To convert it to a balanced Assmt problem, let us add a Dummy SOURCE F with ZERO cost.

$\Rightarrow$

We solve it by HUNGRARIAN method.

Subtract from each row its smallest elmt,

To cover all zeros we need 4 lines; $4 < 6$.

So, subtracting from each column the smallest elmt,. That will give same matrix since there is a zero in every column.

Now subtracting the smallest element of matrix ($=1$) from all uncovered elmts, and adding it to the zeros which are at intersection of 2 lines;

Again lines $= 4 < 6$, so we repeat process, elmt $= 2$.

Lines $= 5 < 6$, so repeating with elmt $= 1$

Now minimum no. of lines $= 6 = n$

$\therefore$ We can start assignment now.

(Degeneracy case)

$\therefore$ Assignment is

$A \to Q : 21$

$B \to P : 16$

$C \to T : 18$

$D \to S : 16$

$E \to R : 18$

$F \to U : 0$ (Dummy)

Minimum distance $= 89$

$\therefore$ Total distance $= 89$.

'U' should not expect a van.