Тема 12. Модели и методы принятия решений

Наука управления (исследование операций, MS/OR) зародилась в Англии во время второй мировой войны, когда группа ученых получила задание на решение сложных военных проблем, таких, как оптимальное размещение сооружений гражданской обороны и огневых позиций, оптимизация глубины подрыва противолодочных бомб и конвоя транспортных караванов. В 50-60-е гг. методология была обновлена, преобразована в целый ряд специфических методов и стала все более широко применяться для решения проблем промышленности и принятия решений в разных ситуациях. Сегодня модели и методы науки управления используются для решения таких задач, как регулирование транспортных потоков, составление графиков работы аудиторий в университетах, управление запасами в супермаркетах и на заводах, разработка новых видов продукции, распределение расходов на рекламу различных видов продукции, планирование материального обеспечения, распределение оборудования и трудовых ресурсов для производства разных изделий на заводе.

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

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

Научный метод: 1. Наблюдение (сбор и анализ информации) => 2. Формулирование гипотезы (предположения о существовании определенной зависимости между компонентами проблемы) => 3. Проверка гипотезы => Реализация решения (или модели), если гипотеза верна, или возврат к (1), если нет.

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

Основные виды моделей и методов принятия решений

Линейное программирование

Общий вид моделей линейного программирования:

F(X) = c1*x1 + c2*x2 + … + cN*xN => max/min – линейная целевая функция

a11*x1 + a12*x2 + … + a1N*xN <= b1 - система линейных ограничений

a21*x1 + a22*x2 + … + a2N*xN >= b2

…………………………………………………………………………………………

aN1*x1 + aN2*x2 + … + aNN*xN = bN

x1, x2, …, xN >= 0

Пример 1. Задача об использовании ресурсов (задача планирования производства). Для изготовления 2 видов продукции используют 4 вида ресурсов. Известны затраты ресурсов на изготовление единиц продукции каждого вида и прибыль, получаемая от единицы продукции. Необходимо составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной.

Пример 2. Транспортная задача. Имеется несколько поставщиков и потребителей с известными объемами предложения / спроса. Известна стоимость перевозки единицы продукции от каждого из поставщиков к каждому из потребителей. Необходимо найти такой план перевозок, чтобы перевезти все произведенные товары от поставщиков к потребителям и при этом минимизировать транспортные расходы.

При решении данных задач используется симплекс-метод и его модификации, а также специализированные методы решения транспортных задач. Симплекс-метод разработан независимо американцем Дж. Данцигом (1949) и советским математиком Леонидом Витальевичем Канторовичем (1939).

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

Нелинейное программирование

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

Динамическое программирование

Решение проблемы состоит из нескольких этапов (элементов), и решение на каждом последующем этапе зависит от ранее принятых решений.

Теория игр

Теория игр помогает принимать решения в условиях неопределенности. Моделирует игровые ситуации, в которых 2 или более стороны (игроки) преследуют различные цели, а результаты любого действия каждой из сторон зависят от действий партнеров. Так как цели различны, то возникает конфликт между ними, и часто выигрыш одного игрока означает проигрыш другого. Эти ситуации часто случаются на практике (шахматы, домино, карты, военные действия, взаимоотношения поставщик - потребитель, банк - клиент, покупатель – продавец и т. п.). Иногда противоположным игроком считают Природу (которая вредит как может) – так называемые игры с Природой (игра в рулетку, игра на бирже и т. п.).

Для простоты будем рассматривать парные (участвуют 2 игрока) антагонистические (выигрыш одного игрока равен проигрышу другого) игры. Игра проходит следующим образом. На каждом этапе игроки делает по одному ходу. Личный ход – сознательный выбор игроком одного из возможных действий. Случайный ход – случайно выбранное действие. Стратегия игрока – совокупность правил, определяющих выбор его действия при каждом личном ходе в зависимости от сложившейся ситуации. Цель игроков – найти оптимальные стратегии (дающие максимальный выигрыш / минимальный проигрыш). Если игра состоит из нескольких этапов, то максимизируют средний выигрыш / минимизируют средний проигрыш.

Для каждого игрока можно составить платежную матрицу (матрицу игры). Пусть игру ведут игроки A и B. Построим платежную матрицу для игрока A. Ход игрока A соответствует выбору строки матрицы, ход игрока B – выбору столбца. На пересечении выбранной строки – столбца находится выигрыш игрока A (равный проигрышу игрока B). Например:

Игрок A стремится максимизировать свой выигрыш, а игрок B – уменьшить его (навредить). Для любой строки, выбранной игроком A, игрок B будет выбирать столбец, дающий наименьший выигрыш игроку A. Для строки 1 – столбец 1 или 2 (выигрыш 3), для строки 2 – столбец 4 (2), для строки 3 – столбец 4 (4). Игрок A выберет в итоге строку 3, которая дает ему наибольший выигрыш при вреде со стороны игрока B (4). Это гарантированный выигрыш игрока A при любой стратегии игрока B. Он называется также нижней ценой игры или максимином.

Если поменять теперь роли игроков, то можно определить по аналогии гарантированный проигрыш игрока B – верхнюю цену игры или минимакс. Для любой столбца, выбранного игроком B, игрок A будет выбирать строку, дающую наибольший проигрыш игроку B. Для столбца 1 – строку 2 (проигрыш 9), для столбца 2 – строку 2 (10), для столбца 3 – строку 1 (6), для столбца 4 – строку 1 (8). Игрок B выберет в итоге столбец 3, который дает ему наименьший проигрыш при вреде со стороны игрока A (6).

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

Задачи теории игр решаются с использованием методов линейного программирования.

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: