Калькулятор венгерского алгоритма

Венгерский алгоритм используется для оптимального назначения работ исполнителям в соотношении один-к-одному и снижения затрат по выполнению. На этом калькуляторе можно решить задачу о назначениях с помощью венгерского алгоритма.

Калькулятор задачи о назначениях

Венгерский алгоритм используется для оптимального назначения работ исполнителям в соотношении один-к-одному и снижения затрат по выполнению. На этом калькуляторе можно решить задачу о назначениях с помощью венгерского алгоритма.

пример:

Допустим есть 3 работы, которые должны быть назначены 3 работникам (одна работа каждому). Затраты на выполнение работ:

Работа/Человек J1 J2 J3
M1 52 19 20
M2 8 83 24
M3 42 35 89

шаг 1 :

Вычтите строку минимумы,
Вычитаем минимальное значение в строке из остальных значений.

Работа/Человек J1 J2 J3 Ряд минимумы
M1 33 0 1 -19
M2 0 75 16 -8
M3 7 0 54 -35

шаг 2 :

Вычитаем минимум столбца,
Вычитаем минимальное значение в столбце из остальных значений.

Работа/Человек J1 J2 J3
M1 33 0 0
M2 0 75 15
M3 7 0 53
Колонка минимумы -1

шаг 3 :

Покрытие все нули с минимальным количеством линий,


Работа/Человек J1 J2 J3
M1 33 0 0
M2 0 75 15
M3 7 0 53

шаг 4 :

Выберите Зеро


Работа/Человек J1 J2 J3
M1 33 0 0
M2 0 75 15
M3 7 0 53

шаг 5 :

Применяем выборку к оригинальной матрице. Это и будут назначенные им работы, а сумма затрат всех назначений работ будет минимальной затратой.


Работа/Человек J1 J2 J3
M1 52 19 20
M2 8 83 24
M3 42 35 89

Мы видим, что решение задачи о назначениях благодаря венгерскому алгоритму облегчается.


ru домой


Sitemap