Исследование операций

Содержание
  1. Исследование операций и методы оптимизации
  2. Основные понятия исследования операций
  3. Классификация задач оптимизации
  4. Исследование операций: что, когда и как
  5. 1. Исследование операций одним словом: оптимизация. 
  6. Исследование операций одним предложением: добиваться наилучших результатов в условиях ограничений 
  7. 2. Основные классы проблем в ИО 
  8. Ⅰ. Оптимизация
  9. Ⅱ. Вероятностное моделирование 
  10. Ⅲ. Имитация
  11. 3. Применение в реальной жизни
  12. Не в последнюю очередь… Головоломки (технические интервью)!
  13. 4. Предметы для освоения исследования операций. 
  14. i. Теория вероятностей 
  15. ii. Детерминированная модель 
  16. iii. Стохастическая модель
  17. iV. Имитация
  18. 5. Профессии
  19. Исследование операций: что, когда и как
  20. 1. Исследование операций одним словом: оптимизация
  21. Исследование операций одним предложением: добиваться наилучших результатов в условиях ограничений
  22. 2. Основные классы проблем в ИО
  23. Ⅱ. Вероятностное моделирование
  24. 3. Применение в реальной жизни
  25. 4. Предметы для освоения исследования операций
  26. i. Теория вероятностей
  27. ii. Детерминированная модель

Исследование операций и методы оптимизации

Исследование операций

Определение 1

Исследование операций – это научное направление, цель которого состоит в разработке и применении методов оптимизации на основе математического моделирования.

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

При исследованиях было выявлено, что:

  1. В сложных системах взаимосвязь элементов важна намного больше, чем их свойства;
  2. Элементы сложных систем могут быть разнородны, например, персонал, оборудование, транспорт, материальные ресурсы и т.д.

Получить выполненную работу или консультацию специалиста по вашему учебному проекту Узнать стоимость

Исследование операций и системный анализ возникли, когда в ВС США и Англии во время Второй мировой войны были созданы специальные группы по изучению военных операций.

К тому времени уже был накоплен опыт использования математических методов в моделировании и решении отдельных экономических задач, теоретически обоснованы возможности решения сложных задач на ЭВМ. Позднее были созданы первые ЭВМ. Так совпали необходимости и возможности.

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

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

Определение 2

Система – это множество элементов, которые, взаимодействуя друг с другом, достигают общую цель системы.

Под процессом понимается все, что происходит внутри системы. Если система функционирует, значит процесс происходит.

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

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

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

Предмет исследования операций достаточно широк, поэтому для лучшего понимания рассмотрим некоторые определения.

Операция – это любое управляемое мероприятие, которое направлено на достижение цели. От методов и способов проведения операции зависит ее результат.

Конкретный набор параметров – это решение. Оптимальными считаются такие решения, которые предпочтительнее других по тем или иным соображениям.

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

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

Все факторы, которые входят в описание операции, делятся на две группы:

  • Постоянные, на которые невозможно повлиять (обозначаются за $a_1, a_2, …$);
  • Зависимые, которые можно выбрать по своему усмотрению в известных пределах ($x_1, x_2, …$).

Критерий эффективности, который выражается некоторой функцией, называется целевой функцией и зависит от обеих групп факторов. Целевая функция Z может быть записана в виде

$Z = f(x_1, x_2, …, a_1, a_2, …)$

Все модели исследования операций делятся на классы:

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

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

Классификация задач оптимизации

Решить оптимизационную задачу означает найти оптимальное решение из нескольких возможных вариантов.

https://www.youtube.com/watch?v=JDjU1utAz5s\u0026list=PLDrmKwRSNx7LFZahXMjYKixzfMgi5MqFF

Если при оптимизации рассчитываются оптимальные значения параметров при конкретной структуре объектов, то это параметрическая оптимизация. Выбор оптимальной структуры – структурная оптимизация.

Любая оптимизационная задача решается путем построения математической модели изучаемого объекта и проводится вычислительный эксперимент.

Основа вычислительного эксперимента – взаимодействие модели, алгоритма и программы. Схема представлена на рисунке 1.

Рисунок 1. Схема вычислительного эксперимента. Автор24 — интернет-биржа студенческих работ

На первом этапе осуществляется построение эквивалента объекта, его модели, которая отражает в математической форме основные свойства.

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

Третий этап – создание программ, реализующих алгоритмы.

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

Определение 3

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

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

Источник: https://spravochnick.ru/ekonomika/issledovanie_operaciy_i_metody_optimizacii/

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

Исследование операций

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

 — наиболее эффективным способом между различными военными операциями. Таким образом, термин “операции” происходит из “военных операций”.

Вычисление военных операций было успешным, и в университетах в 40-ых годах исследование операций стало отдельной академической дисциплиной.

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

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

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

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

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

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

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

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

Максимизировать F(X1, X2, …, Xn) Чтобы это соответствовало ограничениям C1, C2, …, Cm.

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

Существуют целевые функции X, которые нужно максимизировать (прибыль) или минимизировать (затраты, потери, риски и прочие нежелательные события), они называются переменными решения. Их нам и нужно скорректировать.

Например, каждый X может быть водителем. X_i=1 означает, что водитель i выбран и отправляется к клиенту, X_i=0 означает, что водитель не выбран. C — ограничения.

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

https://www.youtube.com/watch?v=LHh5wFYHYOg\u0026list=PLDrmKwRSNx7LFZahXMjYKixzfMgi5MqFF

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

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

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

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

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

Машинное обучение тесно связано с оптимизацией. Многие проблемы машинного обучения формулируются как минимизация функций потерь. В процессе обучения алгоритм оптимизации минимизирует потери тренировочного набора.

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

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

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

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

Ⅲ. Имитация

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

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

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

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

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

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

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

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

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

Решение

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

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

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

Решение

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

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

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

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

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

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

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

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

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

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

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

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

https://www.youtube.com/watch?v=x-Sp-I_Zb9c\u0026list=PLSYi8CBfi0qehTkDVHsPWu-0pwm40E9vq

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

iV. Имитация

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

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

5. Профессии

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

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

Многие стали специалистами в области данных и прикладных технологий в технических компаниях.

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

Команды ценообразования и планирования в сервисных компаниях (Uber, Lyft, AmazonPrimeNow, Doordash) ищут специалистов по исследованию операций для научных целей.

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

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

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

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

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

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

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

Однако существуют задачи, в которых L-BFGS превосходит SGD.

“Наши экспериментальные результаты показывают сильные и слабые стороны различных методов оптимизации.

L-BFGS высококонкурентна и иногда превосходит SGD/CG для низкоразмерных задач, особенно для сверточных моделей. Для высокоразмерных задач CG более конкурентна и обычно превосходит L-BFGS и SGD.

Кроме того, использование крупных мини-пакетов и поиска строк с SGD может повысить производительность.”

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

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

Источник: https://nuancesprog.ru/p/7030/

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

Исследование операций
Статья в Википедии об исследовании операций

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

— наиболее эффективным способом между различными военными операциями. Таким образом, термин “операции” происходит из “военных операций”.

Вычисление военных операций было успешным, и в университетах в 40-ых годах исследование операций стало отдельной академической дисциплиной.

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

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

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

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

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

https://www.youtube.com/watch?v=Nfqy6SVBHAo\u0026list=PLSYi8CBfi0qehTkDVHsPWu-0pwm40E9vq

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

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

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

Максимизировать F(X1, X2, …, Xn)Чтобы это соответствовало ограничениям C1, C2, …, Cm.

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

Существуют целевые функции X, которые нужно максимизировать (прибыль) или минимизировать (затраты, потери, риски и прочие нежелательные события), они называются переменными решения. Их нам и нужно скорректировать.

Например, каждый X может быть водителем. X_i=1 означает, что водитель i выбран и отправляется к клиенту, X_i=0 означает, что водитель не выбран. C ограничения.

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

https://www.youtube.com/watch?v=LHh5wFYHYOg\u0026list=PLDrmKwRSNx7LFZahXMjYKixzfMgi5MqFF

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Все термины
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: