Венгерский алгоритм используется для оптимального назначения работ исполнителям в соотношении один-к-одному и снижения затрат по выполнению. На этом калькуляторе можно решить задачу о назначениях с помощью венгерского алгоритма.
Венгерский алгоритм используется для оптимального назначения работ исполнителям в соотношении один-к-одному и снижения затрат по выполнению. На этом калькуляторе можно решить задачу о назначениях с помощью венгерского алгоритма.
Допустим есть 3 работы, которые должны быть назначены 3 работникам (одна работа каждому). Затраты на выполнение работ:
| Работа/Человек | J1 | J2 | J3 |
|---|---|---|---|
| M1 | 52 | 19 | 20 |
| M2 | 8 | 83 | 24 |
| M3 | 42 | 35 | 89 |
Вычтите строку минимумы,
Вычитаем минимальное значение в строке из остальных значений.
| Работа/Человек | J1 | J2 | J3 | Ряд минимумы |
|---|---|---|---|---|
| M1 | 33 | 0 | 1 | -19 |
| M2 | 0 | 75 | 16 | -8 |
| M3 | 7 | 0 | 54 | -35 |
Вычитаем минимум столбца,
Вычитаем минимальное значение в столбце из остальных значений.
| Работа/Человек | J1 | J2 | J3 |
|---|---|---|---|
| M1 | 33 | 0 | 0 |
| M2 | 0 | 75 | 15 |
| M3 | 7 | 0 | 53 |
| Колонка минимумы | -1 |
Покрытие все нули с минимальным количеством линий,
| Работа/Человек | J1 | J2 | J3 |
|---|---|---|---|
| M1 | 33 | 0 | 0 |
| M2 | 0 | 75 | 15 |
| M3 | 7 | 0 | 53 |
Выберите Зеро
| Работа/Человек | J1 | J2 | J3 |
|---|---|---|---|
| M1 | 33 | 0 | 0 |
| M2 | 0 | 75 | 15 |
| M3 | 7 | 0 | 53 |
Применяем выборку к оригинальной матрице. Это и будут назначенные им работы, а сумма затрат всех назначений работ будет минимальной затратой.
| Работа/Человек | J1 | J2 | J3 |
|---|---|---|---|
| M1 | 52 | 19 | 20 |
| M2 | 8 | 83 | 24 |
| M3 | 42 | 35 | 89 |
Мы видим, что решение задачи о назначениях благодаря венгерскому алгоритму облегчается.
домой