В практике операционного менеджмента часто возникает необходимость оптимально распределить ограниченные ресурсы по конкретным задачам. Как распределить N рабочих по N станкам так, чтобы суммарная производительность была максимальной, а затраты — минимальными? Как назначить курьеров на адреса доставки или таксистов на вызовы с минимальным холостым пробегом? Эта классическая проблема исследования операций называется Задачей о назначениях. Будучи частным случаем транспортной задачи, она отличается высочайшей степенью вырожденности, из-за чего стандартный симплекс-метод на ней катастрофически теряет эффективность. Для решения этой проблемы в 1955 году был разработан блестящий комбинаторный метод, навсегда вошедший в историю как Венгерский алгоритм.