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

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

Марковские процессы принятия решений (MDP) предоставляют безупречный математический фундамент для разработки систем искусственного интеллекта, способных действовать в условиях стохастической неопределенности. Однако формулировка задачи (в виде состояний, действий, вероятностей переходов и наград) — это лишь половина дела. Настоящая магия кроется в алгоритмах, которые находят оптимальное правило поведения (политику) для агента. Одним из самых мощных и теоретически значимых алгоритмов точного решения MDP является Итерация по стратегиям (Policy Iteration), предложенная Рональдом Ховардом в 1960 году. Этот алгоритм позволяет находить абсолютно идеальную стратегию управления системами за конечное, и зачастую очень малое, число шагов.