Математическое моделирование транспортных систем города, проектирование новых веток метро или расчет грузопотоков между регионами страны невозможно без четкого понимания того, сколько людей или грузов перемещается из точки А в точку Б. Эта информация агрегируется в так называемую Матрицу корреспонденций (Origin-Destination Matrix). Проблема заключается в том, что прямое измерение этих потоков путем тотальных опросов или установки датчиков требует колоссальных бюджетов и быстро устаревает. Для синтетического расчета и прогнозирования матриц корреспонденций на основе косвенных макроэкономических данных исследование операций успешно заимствовало математический аппарат из классической физики, создав класс Гравитационных пространственных моделей.

Задача поиска максимального потока в транспортной сети — от перекачки нефти по трубопроводам до маршрутизации информационных пакетов в интернете — является фундаментальной проблемой исследования операций. Хотя классический алгоритм Форда-Фалкерсона, предложенный в 1956 году, концептуально решил эту задачу, его практическая реализация таила в себе серьезные вычислительные угрозы. При неудачном выборе увеличивающих путей алгоритм Форда-Фалкерсона мог сходиться катастрофически медленно (псевдополиномиальное время), а при наличии иррациональных пропускных способностей — и вовсе зацикливаться, никогда не достигая абсолютного оптимума. В 1970 году советский математик Ефим Диниц совершил революционный прорыв, создав алгоритм, который гарантировал строгую и невероятно быструю полиномиальную сходимость для любых транспортных сетей.

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