Assignment problem: Hungarian method 1: Unterschied zwischen den Versionen
| [unmarkierte Version] | [unmarkierte Version] |
| Zeile 5: | Zeile 5: | ||
---- | ---- | ||
| − | '''Introduction''' | + | |
| + | == '''Introduction''' == | ||
| + | |||
| Zeile 24: | Zeile 26: | ||
---- | ---- | ||
| − | |||
| − | + | == '''Sample Solution''' == | |
| − | + | The following example shows the problem of a flat share who wants to assign specific jobs to cleaners. Their goal is to assign the jobs optimal so their costs will be minimized. | |
Version vom 22. Juni 2013, 16:50 Uhr
Assignment problem: Hungarian Method Dennis Motsch (Mtk_Nr.: 381230) Nicolas Heinrich Marian Westendorff (Mtk-Nr.: 377495)
Introduction
The Hungarian Method is an algorithm developed by Harold Kuhn to solve assignment problems in polynomial time. The assignment problem is a special case of the transportation problem in which the number of provider and consumer are equal and supply (ai) and demand (bj) amounts are defined as 1.
Typical examples of assignment problems are:
- Auction Model: A number of goods has to be evenly distrubuted to an equal number of customer. Every customer has its own price idea on the good he is interested. Goal is to maximize the all-round price.
- Job Problem: A number of work assignments has to be distributed to an equally number of workers or machines. The evaluation will be the qualification of a worker or the costs to assign the order to a machine.
- Marriage Problem: A father wants to minimize his marriage gift and wants to maximize the sympathy of his daughters to the men.
Sample Solution
The following example shows the problem of a flat share who wants to assign specific jobs to cleaners. Their goal is to assign the jobs optimal so their costs will be minimized.
