Венгерский метод решения задачи о назначениях
Для решения задачи о назначениях составляют таблицу (табл. 3.6.1):
Таблица 3.6.1
В левой колонке записаны номера кандидатов, в верхней строке – номера работ. В 
-й строке 
-м столбце стоят затраты на выполнение -м кандидатом -й работы.
В венгерском методе используется следующий принцип: оптимальность решения задачи о назначениях не нарушается при уменьшении (увеличении) элементов строки (столбца) на одну и ту же величину. Решение считается оптимальным, если все измененные таким образом затраты 
, (
; 
) и можно отыскать такой набор 
, что
Алгоритм метода содержит следующие шаги.
Шаг 1. Получение нулей в каждой сроке. Для этого в каждой строке определяют наименьший элемент, и его значение отнимают от всех элементов этой строки. Переход к шагу 2.
Шаг 2. Получение нулей в каждом столбце. В преобразованной таблице в каждом столбце определяют минимальный элемент, и его значение вычитают из всех элементов этого столбца. Переход к шагу 3.
Шаг 3. Поиск оптимального решения. Просматривают строку, содержащую наименьшее число нулей. Отмечают один из нулей этой строки и зачеркивают все остальные нули этой строки и того столбца, в котором находится отмеченный нуль. Аналогичные операции последовательно проводят для всех строк. Если назначение, которое получено при всех отмеченных нулях, является полным (т.е. число отмеченных нулей равно 
), то решение является оптимальным, в противном случае следует переходить к шагу 4.
Шаг 4. Поиск минимального набора строк и столбцов, содержащих все нули.
Для этого необходимо отметить:
1) все строки, в которых не имеется ни одного отмеченного нуля;
2) все столбцы, содержащие перечеркнутый нуль хотя бы в одной из отмеченных строк;
3) все строки, содержащие отмеченные нули хотя бы в одном из отмеченных столбцов.
Действия 2) и 3) повторяются поочередно до тех пор, пока есть что отмечать. После этого необходимо зачеркнуть каждую непомеченную строку и каждый помеченный столбец.
Цель этого шага – провести минимальное число горизонтальных и вертикальных прямых, пересекающих по крайней мере один раз все нули.
Шаг 5. Перестановка некоторых нулей.
Взять наименьшее число из тех клеток, через которые проведены прямые. Вычесть его из каждого числа, стоящего в невычеркнутых столбцах и прибавить к каждому числу, стоящему в вычеркнутых строках. Эта операция не изменяет оптимального решения, после чего весь цикл расчета повторить, начиная с шага 3.