Исследование операций: что, когда и как

Несколько расплывчатый термин “исследование операций” был придуман в Первую мировую войну. Британские военные собрали группу ученых для распределения недостаточных ресурсов — например, еды, медикаментов, оружия, войск и т.д. — наиболее эффективным способом между различными военными операциями. Таким образом, термин “операции” происходит из “военных операций”. Вычисление военных операций было успешным, и в университетах в 40-ых годах исследование операций стало отдельной академической дисциплиной.

Если погуглить “исследование операций”, вам попадется длинная статья на Википедии, однако объяснение в ней немного клишированное и, честно говоря, устаревшее. Поэтому я решила добавить к предмету, который изучала в аспирантуре, дополнительное приятное объяснение: он этого заслуживает.

1. Исследование операций одним словом: оптимизация.

Скажем, мы принимаем решение. Что нужно сделать, чтобы принять наилучшее возможное решение?

Оценить все возможные варианты, взвесив плюсы и минусы каждого.

Например, для составления основного плана маршрута Uber должен решать, какого водителя нужно отправить, куда, когда, и сколько ему должны заплатить клиенты. И эти решения должны приниматься с оптимальным использованием доступных ресурсов.

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

Исследование операций одним предложением: добиваться наилучших результатов в условиях ограничений

В математических терминах проблема выше может быть записана так:

Максимизировать F(X1, X2, …, Xn)

Чтобы это соответствовало ограничениям C1, C2, …, Cm.

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

Существуют целевые функции X, которые нужно максимизировать (прибыль) или минимизировать (затраты, потери, риски и прочие нежелательные события), они называются переменными решения. Их нам и нужно скорректировать. Например, каждый X может быть водителем. X_i=1 означает, что водитель i выбран и отправляется к клиенту, X_i=0 означает, что водитель не выбран. C — ограничения. Например, у каждой машины есть расстояние до потенциального клиента, водители могут работать ограниченное количество часов в день, на каждой дороге есть ограничение скорости и каждая машина может взять определенное максимальное число пассажиров.

Это самый распространенный пример исследования операций.

2. Основные классы проблем в ИО

Большинство проблем в ИО попадает в одну из трех категорий.

Ⅰ. Оптимизация

Математическое программирование: как в примере выше с Uber, мы выбираем переменные решения (водители для распределения), целевую функцию (максимизировать прибыль)и задаем ограничения (физические, технические, экономические, экологические, правовые, общественные и т.д.). Затем решаем их математически.
Численная оптимизация: может быть градиентной и неградиентной. Градиентный спуск, один из наиболее популярных алгоритмов в машинном обучении, — это градиентная оптимизация. Существует множество неградиентных алгоритмов (оптимизация без производной), например байесовская оптимизация, алгоритм кукушки, генетический алгоритм и прочие. Неградиентные алгоритмы используются, если целевая функция не является гладкой или закрытая форма функции недоступна.

Машинное обучение тесно связано с оптимизацией. Многие проблемы машинного обучения формулируются как минимизация функций потерь. В процессе обучения алгоритм оптимизации минимизирует потери тренировочного набора. Однако конечная цель машинного обучения — минимизировать потери скрытых данных. Таким образом, машинное обучение — это проблема оптимизации с целью “обобщения”.

Ⅱ. Вероятностное моделирование

Вероятностная модель выводит распределение вероятностей, а детерминистическая модель выводит один возможный результат для события.

Одна из наиболее известных вероятностных моделей — это перекрестная энтропия, функция потерь, часто используемая для прогнозирования распределения вероятностей по цели. Байесовский вывод и оценка апостериорного максимума также являются важными применениями вероятностного моделирования.

Ⅲ. Имитация

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

3. Применение в реальной жизни

Исследование операций применимо к огромному количеству задач в реальной жизни.

Координирование (назначение водителей Uber клиентам).
Планирование (планирование расписания нескольких ТВ шоу для достижения максимально возможного количества просмотров).
Финансовый инжиниринг (распределение активов, управление рисками, ценообразование деривативов, управление портфелем ценных бумаг и т.д.).
Умные торги на YouTube. Автоматическая система открытых торгов для алгоритмической рекламы, определяющая, какую величину прироста можно отнести к определенному показу и сколько нужно за это заплатить.
Наука о ценах (цены на авиабилеты).
Построение маршрутов (основной план маршрута автобусов, чтобы нужда в них была наименьшей).
Расположение объектов (выбор наиболее приемлемого расположения новых объектов, таких как склады, фабрики или пожарные станции).
Оптимизация сети (пакетная маршрутизация).

Не в последнюю очередь… Головоломки (технические интервью)!

Головоломки из исследования операций часто попадаются в технических интервью, по крайней мере в FAAMG. Лично мне задали две из трех задач ниже.

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

Решение

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

Решение. Комикс.

Диета Стиглера: названа в честь лауреата Нобелевской премии по экономике Джорджа Стиглера, который рассчитал недорогой способ удовлетворить базовые потребности в питательных веществах, учитывая заданный набор продуктов. Это классическая задача линейной оптимизации. Как выбрать набор продуктов, удовлетворяющий ежедневной норме питательных веществ при минимальных затратах?

Решение

4. Предметы для освоения исследования операций.

Я изучала исследование операций в Колумбийском университете в магистратуре, и вот четыре обязательных предмета.

i. Теория вероятностей

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

ii. Детерминированная модель

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

iii. Стохастическая модель

В исследовании операций мы изучили такие методы стохастического моделирования, как цепи Маркова, процессы рождения и смерти, пуассоновы процессы, задачу о разорении игрока, броуновское движение и т.д. Для меня это был самый интересный и трудный предмет в программе.

Эти методы можно применять и в обучении с подкреплением (исследовании стохастических процессов), финансовом инжиниринге (ценообразовании, опционах с правом продажи, опцион-корзинах, измерении страхового риска и т.д.), организации очередей, моделирования надежности, товаров и прочих.

В отличие от детерминированных моделей стохастические учитывают случайность. Следовательно, та же самая модель с теми же параметрами может выдавать различные результаты.

iV. Имитация

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

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

5. Профессии

Сейчас мои сокурсники работают в совершенно различных областях.

Многие работают в финансовой индустрии. Возможно, потому что мой университет был расположен близко к Уолл Стрит. Они работают в различных направлениях, например в управлении рисками, трейдинге, количественном анализе, даже в продажах или инвестиционном банковском бизнесе.

Многие стали специалистами в области данных и прикладных технологий в технических компаниях. Azure и AWS нанимают большое количество специалистов по данным для оптимизации времени простоя облака, распределения мощности, оценки потребностей в режиме реального времени и т.д. Команды ценообразования и планирования в сервисных компаниях (Uber, Lyft, AmazonPrimeNow, Doordash) ищут специалистов по исследованию операций для научных целей. У команд, занимающихся алгоритмическими ставками (Adtech) в социальных медиа (Twitter, Facebook, YouTube, etc.), существует множество задач для специалистов в исследовании операций: ценообразование системы алгоритмических торгов, настройки аудиторий, прогнозирующее моделирование для привлечения пользователей и т.д.

Я, к примеру, начала свою карьеру сразу после получения диплома в качестве дилера по производным финансовым инструментам в компании, предоставляющей финансовые услуги. Затем в качестве специалиста по данным я присоединилась к стартапу, занимающемуся рекламными технологиями. Сейчас я работаю в Microsoft инжнером-исследователем над задачей обработки естественного языка по ответам на вопросы.

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

Несколько дополнений:

Согласно “Теореме об отсутствии бесплатных обедов”, не существует единственного конкретного алгоритма оптимизации, наилучшим образом подходящего к любой задаче.

“Мы показали, что все алгоритмы, занимающиеся поиском экстремума функции потерь работают точно так же, когда усредняются по всем возможным функциям потерь. В частности, если алгоритм А превосходит алгоритм B для некоторых функций потерь, то, грубо говоря, должно существовать столько же функций, для которых B превосходит А.”

Следовательно, выбор алгоритма оптимизации должен зависеть от задачи. Например, когда я тренирую модели глубокого обучения обработки естественного языка, одним из лучших алгоритмов является ADAM, потому что он работает хорошо и быстро. Я никогда не использую I L-BFGS, даже если он теоретически быстрее сходится, потому что, по моему опыту, стохастический градиентный спуск так же хорош, как и алгоритмы второго порядка с точки зрения времени обучения и конечного результата. Однако существуют задачи, в которых L-BFGS превосходит SGD.

“Наши экспериментальные результаты показывают сильные и слабые стороны различных методов оптимизации. L-BFGS высококонкурентна и иногда превосходит SGD/CG для низкоразмерных задач, особенно для сверточных моделей. Для высокоразмерных задач CG более конкурентна и обычно превосходит L-BFGS и SGD. Кроме того, использование крупных мини-пакетов и поиска строк с SGD может повысить производительность.”

2. У Google есть хорошее бесплатное приложение OR-Tools, у которого есть решающие программы для:

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

Перевод статьи Aerin Kim: Operations Research — what, when and how

Поделиться статьей:

Вернуться к статьям