Публикация Школы траблшутеров

Венгерский алгоритм: как назначить людей на задачи

Время чтения: 9 мин
03 ноября 2026 Просмотров: 10

Двадцать четыре группы шкал описывали каждого подчинённого, и лучший кандидат на любую должность находился за считаные минуты, но сумма таких назначений упиралась в локальный максимум. Основатель «Школы траблшутеров», экс-директор Альфа-Банка по процессам, Олег Брагинский рисует жадное назначение и венгерский алгоритм в трёх нотациях.

Венгерский алгоритм: как назначить людей на задачи

Рис. 1. Венгерский алгоритм: вычитание минимумов, закрытие нулей, поправка и выбор

Когда-то создал пространство компетенций: оцифровал подчинённых по 24 группам шкал, в каждой от одного до трёх параметров. Аналогичную работу сделал для позиций, чтобы назначать лучших на каждую должность.

Очень быстро оказалось, что так достигаются лишь локальные максимумы: лучший кандидат на первую должность часто был ещё нужнее на второй. Пришлось искать не лучшего на позицию, а лучшую комбинацию претендентов на все освобождающиеся должности сразу.

Короткий ответ: назначение «лучший на каждое место по очереди» считается мгновенно, но теряет общий результат. Венгерский алгоритм находит лучший набор пар людей и задач, а объём расчёта растёт примерно как куб числа людей.

Рисовать назначения руководителю удобнее всего матрицей «люди × задачи», где каждый шаг – новая таблица с нулями на месте выгодных пар.

Как устроен венгерский алгоритм?

Венгерский алгоритм – способ найти назначение «каждому – одна задача» с наименьшими суммарными затратами. Он преобразует таблицу затрат так, чтобы выгодные пары превратились в нули, а затем выбирает из них пары без пересечений.

По ГОСТ 19.701 это две операции с минимумами, ромб и петля поправки. Отнять два часа у всей строки – всё равно что сказать: этот человек везде на два часа медленнее. Порядок задач для него не меняется, а ноль отмечает лучшую.

Затем нули закрывают наименьшим числом линий по строкам и столбцам. Если линий столько же, сколько людей, выбор найден. Если меньше, наименьшее открытое число вычитают из открытых клеток, прибавляют на пересечениях линий и закрывают нули снова.

Метод опубликовал Гарольд Кун в 1955 году и назвал венгерским в честь работ Денеша Кёнига и Енё Эгервари. Джеймс Манкрес в 1957 году показал, что объём работы растёт полиномиально, а не взрывается, как при переборе.

Как «Кедр» распределяет инженеров?

Сервисная компания «Кедр» назначает четырёх специалистов на четыре срочные заявки: склад, офис, цех и насосную станцию. В таблице – часы, которые понадобятся каждому на каждую заявку с учётом дороги и допусков.

image html

Рис. 2. Жадное назначение – 23 часа, лучшее – 18

Диспетчер действует жадно: на склад – самую быструю Анну, 2 часа, в офис – Бориса, ведь у остальных там по 9 часов. Цех достаётся Вере, насосная – Глебу. Итого 23 часа.

Лучшее назначение отправляет Анну в офис, а Бориса на склад: 3 и 3 часа вместо 2 и 9. Анна – лучшая на складе, но в офисе она незаменима. Итог – 18 часов, на 22% меньше, а самая долгая заявка занимает 7 часов вместо 9.

Как считать в матрице?

Матричная запись – способ показать алгоритм серией таблиц, где каждая следующая получена из предыдущей одним действием. Ошибку видно в конкретной клетке, а каждый шаг легко повторить в Excel и проверить сложением.

Почему вычитание не портит ответ? В любом назначении у Анны ровно одна задача, поэтому минус два часа во всей строке уменьшают итог любого варианта ровно на два. Порядок вариантов не меняется, а нули отмечают пары, дешевле которых в строке нет.

Из строк вычитаем минимумы 2, 3, 4 и 5, из столбцов – минимумы 0, 1, 1 и 2. Нули закрываются четырьмя линиями – двумя строками и двумя столбцами. Линий столько же, сколько людей, значит, поправка здесь не нужна.

Остаётся выбрать нули без конфликтов. У Бориса единственный ноль – склад, и Анне достаётся офис, Вере – цех, Глебу – насосная. На больших таблицах цикл повторяется несколько раз, но каждый проход добавляет хотя бы одну выгодную пару.

image html

Рис. 3. Шаги расчёта: вычитания, закрытие нулей и выбор назначения

Стоит ли менять людей местами?

В апреле 2012 года, воспользовавшись неожиданностью, допустимой в День дурака, сменили команды двух розничных отделений Москвы – Даниловского и Московского. Решение о перестановке приняли на базе расчётов.

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

Это назначение два на два: две группы людей, два офиса, четыре клетки. Привычный взгляд «каждая группа лучше всех знает родной офис» оставлял выигрыш в соседней клетке.

Как нарисовать назначение графом?

Двудольный граф – способ изобразить две группы вершин, людей и задачи, со связями только между группами. Назначение – набор связей, где у каждой вершины ровно одна.

image html

Рис. 4. Лучшее назначение перекрещивает связи Анны и Бориса

На графе видно главное: лучшее решение меняет местами две пары. Венгерский алгоритм ищет на графе чередующиеся цепочки, по которым пары переставляются с выигрышем.

Что записывать в клетку?

Квалифицированные сотрудники принимают решения быстрее и чётче, но и стоят дороже. Однажды взялся за проект в операционном центре Ульяновска. Самолёты с бизнес-классом туда, к счастью, не летали, но годовой эффект всё равно съела стоимость командировок: дорогие гостиницы и трансферы. Лучше было бы послать пару толковых проектных менеджеров.

Венгерский алгоритм точен ровно настолько, насколько точна таблица. Если в клетке только скорость, лучшим окажется самый опытный. В клетку пишут полную цену пары: часы, ставку, дорогу, жильё, риск ошибки. Тогда опытный достаётся задаче, где без него не обойтись.

Если людей больше, чем задач, добавляют условные задачи с нулевыми затратами. Если нужен наибольший эффект, а не наименьшие затраты, все числа вычитают из наибольшего.

Сколько стоит точность?

Перебор всех назначений растёт как факториал: для 4 человек – 24 варианта, для 10 – 3,6 млн, для 20 – 2,4 квинтиллиона. Современные версии венгерского алгоритма требуют порядка n³ действий: тысяча для десяти человек и 8’000 для двадцати.

image html

Рис. 5. Сколько вычислений нужно трём способам при 4, 10 и 20 участниках

Жадное назначение ещё быстрее – порядка n² сравнений, но в «Кедре» оно потеряло 5 часов на четырёх заявках. На освобождающиеся должности крупной компании – десятки претендентов: перебор невозможен, жадность теряет, а венгерский алгоритм считает мгновенно.

Когда уместен венгерский алгоритм?

Там, где каждый человек берёт ровно одну задачу, а затраты пары можно оценить заранее: инженеры и заявки, менеджеры и клиенты, претенденты и должности. Если человек может взять две задачи, строку повторяют дважды.

Метод не подходит, если пары влияют друг на друга: сильный руководитель усиливает слабую команду, и цена пары зависит от соседей. Тогда таблица – первое приближение, а окончательное решение остаётся за людьми.

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

Какими нотациями рисовать назначение?

ГОСТ 19.701 передаёт порядок шагов и петлю поправки, но не показывает, что происходит с числами. Его предпочитают авторы регламентов: каждый блок – пункт инструкции.

Матрица держит на виду затраты каждого шага. Её любят финансисты и аналитики: итог сверяется сложением четырёх клеток, а таблица переносится в Excel без перерисовки.

Двудольный граф ценят те, кто объясняет решение людям: перекрещённые связи сразу говорят, кто с кем поменялся. Но на десяти людях граф превращается в паутину.

Какая нотация лучше?

Лучшая нотация для назначений – матрица: 22 балла против 17 у графа и 16 у ГОСТ. Руководитель видит и затраты, и итог, а аналитик повторяет расчёт без программиста. Вес вопроса о руководителе удвоен: сборник написан для него.

image html

Рис. 6. Оценка трёх нотаций: 16, 22 и 17 баллов

Граф отстал на пять баллов, но лучше всех объясняет перестановку команде. ГОСТ остаётся для регламента: с чего начинать и когда повторять поправку.

Что сделать руководителю?

Хватит четырёх шагов:

  1. Соберите таблицу «люди × задачи» с полной ценой каждой пары: время и дорога.
  2. Сравните жадное назначение с венгерским: разница – цена выбора по одному.
  3. Освобождающиеся должности заполняйте комбинацией претендентов, а не по очереди.
  4. Проверьте расчёт на практике: поменяйте команды местами на время.

Что запомнить?

  • назначение «лучший на каждое место» быстро, но теряет общий результат
  • венгерский алгоритм находит лучшую комбинацию людей и задач
  • вычитание минимумов не меняет порядок кандидатов, а нули отмечают выгодные пары
  • в клетку пишут полную цену пары, а не только скорость
  • назначения лучше всего рисовать матрицей.