Как разместить минимальное количество пожарных депо так, чтобы каждый район города находился в зоне пятиминутной доступности хотя бы от одной станции? Как выбрать минимальный набор радиочастот для покрытия всей территории страны сигналом сотовой связи? Как составить расписание так, чтобы минимальное число экипажей авиакомпании обслужило абсолютно все запланированные на месяц рейсы? Все эти жизненно важные логистические проблемы математически сводятся к одной из самых известных NP-трудных задач комбинаторной оптимизации — Задаче о покрытии множества (Set Covering Problem, SCP). Эффективное решение этой проблемы критически важно для минимизации капитальных и операционных затрат транснациональных корпораций.

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

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