Fill in the cost matrix of an assignment problem and click on 'Solve'. The optimal assignment will be determined and a step by step explanation of the hungarian algorithm will be given.

Fill in the cost matrix (random cost matrix):

This is the original cost matrix:

3 | 2 | 1 |

12 | 23 | 23 |

123 | 23 | 12 |

**Subtract row minima**

We subtract the row minimum from each row:

2 | 1 | 0 | (-1) |

0 | 11 | 11 | (-12) |

111 | 11 | 0 | (-12) |

**Subtract column minima**

We subtract the column minimum from each column:

2 | 0 | 0 |

0 | 10 | 11 |

111 | 10 | 0 |

(-1) |

**Cover all zeros with a minimum number of lines**

There are 3 lines required to cover all zeros:

2 | 0 | 0 | x |

0 | 10 | 11 | x |

111 | 10 | 0 | x |

**The optimal assignment**

Because there are 3 lines required, the zeros cover an optimal assignment:

2 | 0 | 0 |

0 | 10 | 11 |

111 | 10 | 0 |

This corresponds to the following optimal assignment in the original cost matrix:

3 | 2 | 1 |

12 | 23 | 23 |

123 | 23 | 12 |

The optimal value equals 26.

HungarianAlgorithm.com © 2013-2023