Учебно-методическое пособие
Ю.О. Матузко
Запорожье 2009
Содержание
Ведение
Раздел 1. Основные понятия и структура исследования операций
Раздел 2. Принятие решения в условиях риска
2.1 Постановка задачи
2.2 Критерий Байеса
2.3 Критерий Лапласа (Бернулли)
2.4 Критерий Гермейера
2.5 Критерий Ходжа-Лемана
Раздел 3. Принятие решения в условиях неопределенности
3.1 Принцип максимина
3.2 Критерий азартного игрока
3.3 Критерий произведений
3.4 Критерий Сэвиджа
3.5 Критерий Гурвица
Раздел 4. Принятие решения в условиях противодействия
4.1 Матричные игры
4.2 Матричные игры, разрешимые в чистых стратегиях
4.3 Матричные игры, разрешимые в смешанных стратегиях
4.3.1 Постановка задачи
4.3.2 Решение задачи симплекс-методом
4.3.3 Решение задачи графическим методом
Раздел 5. Принятие решения в условиях нескольких критериев выбора40
5.1 Постановка задачи, основные понятия
5.2 Линейные свёртки
5.3 Максиминная и лексикографическая свёртки
5.4 Мультипликативные свёртки
5.5 Многокритериальный выбор на языке бинарных отношений
Раздел 6. Принятие корпоративных решений
6.1 Групповая оценка объектов
6.2 Определение коэффициентов компетентности экспертов
Раздел 7. Критерии модульного оценивания знаний
Раздел 8. Задания для самостоятельной работы студентов
8.1 Домашняя контрольная работа
8.2 Вопросы к модульным тестированиям
8.3 Контрольные вопросы к экзамену по дисциплине
Учебно-методический материал по дисциплине
Ведение
Дисциплина "Теория принятия решений" читается студентам специальности "Автоматизированное управление технологическими процессами". Такой специалист по окончании учебы должен уметь выдать заказчику законченный программно-алгоритмический продукт, который будет автоматизировать процесс принятия решений в конкретном технологическом процессе, описанном заказчиком. Заказчик в таких случаях может представлять различные отрасли народного хозяйства: он может быть химиком, металлургом, строителем, экономистом, электронщиком и т.п. Главное, чтобы его технологический процесс, в котором нужно принимать решения, был успешно автоматизирован. Предлагаемый курс дает теоретические и практические основы математически обоснованного процесса принятия решений. Рассматриваемые в данном пособии задачи носят чисто абстрактный характер по своему текстовому условию. Главное в них – это количественные и качественные методы решения поставленной проблемы принятия решений, которые могут быть применены к различным отраслям.
В пособии охвачена лишь общая часть дисциплины "Принятие решений". Дело в том, что предмет "Теория принятия решений" читается студентам на протяжении всего двух календарных месяцев. Автор по возможности попытался за столь короткий срок охватить наиболее общие и значимые понятия и методы довольно широкой дисциплины "Принятие решений". Более детальную информацию по дисциплине можно получить из специальной литературы, указанной в пособии.
Данное учебное пособие содержит критерии модульного оценивания знаний, задания домашней контрольной работы, вопросы к модульным тестированиям, а также контрольные вопросы к экзамену по предмету "Теория принятия решений".
Раздел 1. Основные понятия и структура исследования операций
Принимать решения, как отдельному человеку, так и различным группам людей, вплоть до всего человечества приходится практически во всех областях своей деятельности. Единственное, чего мы не выбираем, следуя народной мудрости, так это родителей и Родины. Причем в некоторых областях (военных, медицинских, космических, в атомной энергетике, химической промышленности и др.) возникает потребность принятия достаточно сложных управленческих решений, ошибка в которых может повлечь за собой катастрофические последствия. В силу этого появилась необходимость выделить процесс принятия оптимальных решений в отдельную область науки, которая бы формализовала и систематизировала данный процесс.
Исторически считается, что это произошло в начале 40-х годов ХХ века, когда группа английских ученых математически сформулировала и нашла решение задачи об оптимальном способе доставки на фронт войск, оружия и снаряжения. И сразу же стали интенсивно поступать заказы на решение новых военных задач. Позднее эти исследования были перенесены и на гражданскую сферу и обобщены в отдельную науку – исследование операций.
Исследование операций стала основным научным инструментом при принятии оптимальных решений в самых разнообразных областях человеческой деятельности. Специалиста в этой науке в литературе обычно называют аналитиком (или системным аналитиком, или лицом, принимающим решение (далее ЛПР)).
Дадим некоторые основные определения и обозначим ориентировочное структурное строение исследования операций. Даная структура также отражает этапы, которые должен последовательно пройти ЛПР при принятии решения.
1 этап. Постановка (формулировка) задачи (проблемы).
На этом этапе аналитик должен трансформировать слова заказчика "хочу, чтобы было так" в четко сформулированную задачу. В 99% случаях заказчик не только не может предоставить, но и понятия не имеет о тех данных, которые необходимы аналитику для успешного разрешения проблемы. Оно и понятно – ведь у него нет соответствующего образования. (На самом деле, такое образование заказчику и не нужно, ведь он обратился к грамотному специалисту-аналитику, выпускнику ЗГИА! J) Все необходимое аналитик должен добыть себе сам. Так будет лучше по всем показателям – и по времени и, что немаловажно, по искажению информации (формулировка задачи с чьих-то слов уже априори чревато ошибками). Аналитику необходимо увидеть и изучить проблему "изнутри", для этого ему нужно "внедриться" в сложившуюся ситуацию. Зачастую аналитику надо "внедриться" и поработать на всех ключевых постах в организации заказчика, столкнувшейся с проблемой. На это может уйти от нескольких дней до месяцев.
2 этап. Построение математической модели задачи.
Здесь четко поставленная и сформулированная жизненная проблема формализуется математически.
1) Определяются переменные – переменные величины (их может быть как несколько, так и одна), изменение которых влияет на конечный результат задачи. Наборы различных конкретных значений переменных называются альтернативами (также во многих литературных источниках набор переменных называется планом).
2) Определяются ограничения, которые накладываются на переменные. Пересечение всех полученных ограничений задает допустимое множество. Набор переменных, которые удовлетворяют всем ограничениям, называется допустимым планом.
3) Определяется критерий, по которому должны отбираться альтернативные решения (планы). Такой критерий называется целевой функцией.
Задача состоит в том, чтобы найти такой набор переменных (выбрать такую альтернативу), чтобы они принадлежали допустимому множеству (т.е. удовлетворяли всем ограничениям задачи) и чтобы целевая функция от этих переменных принимала свое оптимальное значение. Такой набор переменных называется оптимальным планом. Понятно, что оптимальный план должен быть допустимым, поэтому и ищется оптимальный план только среди допустимых планов.
Описанными первыми двумя этапами занимается дисциплина "математическое моделирование", являющаяся составной частью исследования операций.
3 этап. Решение математической модели задачи.
Решением математических моделей задач занимается дисциплина "математическое программирование".
В исследовании операций нет единого общего метода решений всех математических моделей. Многолетние исследования позволили обобщить и сгруппировать схожие типы моделей в определенные классы задач. Методы решения данных классов задач составляют отдельные разделы математического программирования, со временем они даже трансформировались в отдельные дисциплины. Дадим краткий обзор некоторых из них.
1) Линейное программирование. В этом классе задач и целевая функция и все ограничения являются линейными функциями. К таким задачам относятся:
задача о плане производства;
задача о диете;
и др.
2) Целочисленное программирование. В этих задачах целевая функция и все ограничения также являются линейными. Все переменные должны принимать только целочисленные значения. К таким задачам относятся:
транспортная задача;
задача о назначениях;
и др.
3) Динамическое программирование. Применяется, когда исходную задачу можно разбить на меньшие подзадачи и решать их пошагово. К таким задачам относятся:
задача коммивояжера;
задача об управлении запасами;
задача о ранце;
и др.
4) Нелинейное программирование. В этом классе задач либо целевая функция, либо все или некоторые ограничения являются нелинейными функциями.
Еще раз акцентируем внимание, что выше приведены лишь некоторые основные разделы математического программирования. Кроме указанных разделов еще существуют теория графов, теория расписаний, сетевое планирование, системы массового обслуживания, теория марковских процессов и др. Каждый раздел математического программирования – это отдельная сформировавшаяся дисциплина, требующая достаточно углубленного теоретического и, особенно, практического изучения.
4 этап. Принятие решений.
На этой стадии аналитик (лицо, принимающее решение) на основе пройденных предыдущих этапов должен принять оптимальное решение. Это и является предметом изучаемого курса "Теория принятия решений".
Само собой разумеется, что студенты, приступившие к изучению курса "Теория принятия решений" ранее должны были изучить и, что немаловажно, успешно сдать и математическое моделирование, и математическое программирование. Без этого необходимого условия ЛПР вряд ли примет оптимальное решение. Невозможно ведь учиться в пятом классе, до этого не выучив во втором классе таблицы умножения! Равно как и невозможно быть директором роддома, не зная, откуда берутся дети.
Принятие решения – это задача управленческого типа. Под ней понимается задача выбора лицом, принимающим решение (ЛПР) наилучшего способа (исхода) из некоторого конечного множества допустимых вариантов (альтернатив). После принятия решения изучаемая система переходит в новое состояние, на которое будет реагировать окружающая среда. Окружающей средой может быть военная, экономическая, финансовая, техническая или какая-либо другая обстановка. При этом возможны такие случаи:
1) ЛПР знает реакцию окружающей среды на выбор им той или иной альтернативы, т.е. он знает насколько "полезной" или "вредной" для его системы будет реакция окружающей среды на выбор им той или иной альтернативы. Такая ситуация называется задачей принятия решения в условиях определенности. В условиях определенности математическое программирование дает точное решение поставленной задачи. Поэтому необходимости выбирать из нескольких вариантов попросту нет. Таким образом, в условиях определенности "Теория принятия решений" не используется, такими задачами занимается математическое программирование.
2) ЛПР знает вероятность реакции окружающей среды на выбор им той или иной альтернативы. Такая ситуация называется задачей принятия решения в условиях риска.
3) ЛПР ничего не знает о реакции окружающей среды на выбор им той или иной альтернативы. Такая ситуация называется задачей принятия решения в условиях неопределенности.
При этом предполагается, что в перечисленных случаях окружающая среда реагирует на принятое ЛПР решение беспристрастно (как природа), не преследуя никаких своих целей.
4) Однако зачастую бывают ситуации, когда в качестве окружающей среды может выступать, например, конкурирующая фирма, военный противник, конкурент на выборах и т.п. В этом случае такая окружающая среда будет реагировать уже совсем не беспристрастно, а сугубо в своих интересах. Такая ситуация называется задачей принятия решения в условиях противодействия.
Постановка задачи
Рассмотрим следующую ситуацию.
Представьте что вы – глава пенсионного фонда Украины. На счета пенсионного фонда Украины поступают налоговые отчисления по достаточно большой процентной (большей, чем в большинстве развитых странах) ставке. По расчетам этих денег должно хватить на выплату пенсий сегодняшним пенсионерам и на накопление для выплат сегодняшним налогоплательщикам, по достижении ими пенсионного возраста. Ваша непосредственная обязанность, как главы пенсионного фонда обеспечить выполнение этих двух задач. Первая задача – выплата текущих пенсий – это чисто техническое задание. Будем считать, что с ним вы блестяще справитесь.
А что делать с накоплениями? Если эти деньги не трогать и "заморозить", то через несколько лет ввиду инфляции сегодняшний налогоплательщик получит сущие гроши. Естественным выходом (так делают во всем мире) будет эти средства во что-нибудь вложить (инвестировать).
Допустим, что вы, как инвестор, имеете возможность вложить средства пенсионного фонда Украины в один из четырех финансовых институтов: акции кампании г-на Сороса, в депозит Bank of America, в облигации госказначейства США и в золото. Эти четыре альтернативы (ваши возможные стратегии) обозначим А1, А2, А3, А4 .
Допустим, окружающая среда (В), в данном случае, ситуация на финансовом рынке на момент завершения депозита может принять одно из пяти определенных состояний. Эти пять состояний обозначим В1, В2, В3, В4, В5 .
Из многолетних статистических данных известны приближенные вероятности (Q) этих состояний: q1, q2, q3, q4, q5 .
Инвестиционная привлекательность проекта вложения средств определяется как конечная рентабельность. Оценка рентабельности считается известной для каждой стратегии инвестора и каждого состояния окружающей среды. Эти данные представлены в матрице, называемой матрицей выигрышей инвестора (игрока А),
где аij – это рентабельность инвестиционного проекта при выборе Аi-той альтернативы и при Вj-том состоянии окружающей среды.
От вас, как главы пенсионного фонда Украины, требуется выбрать наилучший вариант вложения средств налогоплательщиков.
Отметим, что понятие наилучшего исхода в различных условиях трактуется по-разному. Для различных условий принятия решений разработаны различные критерии выбора ЛПР наилучшего исхода. Решим данную задачу с помощью различных критериев.
Критерий Байеса
Критерий Байеса (принцип математического ожидания) предполагает полное доверие ЛПР известным вероятностям состояний окружающей среды. Следовательно, данная задача – это задача принятия решения в условиях риска.
Показатель эффективности стратегии Аi по критерию Байеса находится по формуле:
Z = 
,
гдеm – количество строк матрицы, заданной в условии;
n – количество столбцов матрицы, заданной в условии;
qj – заданные вероятности ;
аij – элементы матрицы, заданной в условии.
Для случая оптимизации потерь критерий будет таким:
Z = 
#
Заметим, что 
– это математическое ожидание стратегии Аi . Таким образом, исходную матрицу необходимо дополнить справа еще одним столбцом, в который нужно внести значения математических ожиданий всех стратегий:
Пример вычислений для первой строки:
= 0,33 + 0,27 + ,153 + ,115 + ,256 = ,6 + 1,4 + ,45 + 1,5 + 1,5 = 5,75
Далее в добавленном столбце нужно найти наибольший элемент (наибольшее математическое ожидание). Строка, в которой он стоит и будет оптимальной стратегией. Необходимо заметить, что наибольших элементов может быть несколько, тогда и оптимальных стратегий соответственно будет несколько.
В нашем случае наибольший элемент 5,95 (в матрице он выделен). Таким образом, в нашем примере оптимальной стратегией будет А3, т.е. средства фонда вам нужно вложить в третий проект.
Ответ А3 .
Критерий Лапласа (Бернулли)
Критерий Лапласа (принцип недостаточного основания) предполагает недоверие ЛПР известным вероятностям состояний окружающей среды. Вероятности состояний окружающей среды считаются одинаковыми и равными 
. Следовательно, данная задача – это задача принятия решения в условиях риска с вероятностями .
Показатель эффективности стратегии Аi по критерию Лапласа находится аналогично критерию Байеса с вероятностями 
:
Z = 
= 
,
Заметим, что нет необходимости вычислять эти математические ожидания. Достаточно просто просуммировать элементы строк матрицы и выбрать из них максимальную сумму:
Z = 
Для случая оптимизации потерь критерий будет таким:
Z = 
#
Таким образом, исходную матрицу необходимо дополнить справа еще одним столбцом, в который нужно внести значения сумм элементов строк всех стратегий:
Далее в добавленном столбце нужно найти наибольший элемент. Строка, в которой он стоит и будет оптимальной стратегией. Необходимо заметить, что наибольших элементов может быть несколько, тогда и оптимальных стратегий соответственно будет несколько.
В нашем случае наибольший элемент в добавленном столбце 34 (в матрице он выделен). Таким образом, в нашем примере оптимальной стратегией будет А1 , т.е. инвестор должен выбрать для вложения первый проект.
Ответ А1 .
Критерий Гермейера
Критерий Гермейера применяется для задач принятия решений в условиях риска.
Он применяется в основном для решения задач выбора для оптимизации величины потерь или затрат. Такие задачи довольно часто встречаются в хозяйственной практике. Матрица потерь, задаваемая в условии, будет содержать отрицательные элементы (потери выражаются отрицательными величинами). Если в матрице помимо отрицательных будут и положительные элементы, то исходная матрица потерь преобразуется в матрицу, содержащую только отрицательные элементы по правилу:
аij – с ,
где с – некое выбранное ЛПР положительное число.
Следует иметь в виду, что оптимальное решение зависит от выбора с.
Критерий Гермейера применяется и для оптимизации величины прибыли (как в нашей задаче), т.е. для положительных матриц.
В общем случае Гермейер предложил ввести в рассмотрение матрицу с такими элементами:
Построим новую матрицу для нашего примера:
Далее к этой матрице применяется принцип максимина. Показатель эффективности стратегии Аi при этом находится по формуле:
Таким образом, новую матрицу необходимо дополнить справа еще одним столбцом, в который нужно внести наименьшие значения элементов каждой строки.
Затем из элементов добавленного столбца нужно выбрать наибольший. Строка, в которой он стоит и будет оптимальной стратегией.
В нашем случае наибольший элемент в добавленном столбце 16 (в матрице он выделен). Таким образом, в нашем примере оптимальной стратегией будет А3, т.е. инвестор должен выбрать для вложения третий проект.
Ответ А3 .
Критерий Ходжа-Лемана
Критерий Ходжа-Лемана привносит фактор определенной субъективности при принятии решения.
Решение принимается в условиях риска. Однако у ЛПР есть некое недоверие к распределению вероятностей состояний окружающей среды. Поэтому ЛПР вводит некий "коэффициент доверия" l к вероятностям состояний окружающей среды (0 £ l £ 1). Чтобы сильно не рисковать, обычно таким коэффициентом берут 0,4. Этот коэффициент ещё называют уровнем оптимизма.
Показатель эффективности стратегии Аi по критерию Ходжа-Лемана находится по формуле:
Z = 
,
#Для случая оптимизации потерь критерий будет таким:
Z = 
#
Таким образом, исходную матрицу необходимо дополнить справа еще тремя столбцами. В первый нужно внести значения математических ожиданий всех стратегий, умноженных на уровень оптимизма l = 0,4. Во второй нужно внести значения наименьших элементов всех строк, умноженных на уровень пессимизма 1 – l = 1 – 0,4 = 0,6 . В третий добавленный столбец внесем сумму значений первых двух добавленных столбцов:
Пример вычислений для первой строки:
= 0,4 (,33 + 0,27 + ,153 + ,115 + ,256) = ,4 5,75 = 2,3
= 0,6 3 = 1,8
Z1 = 2,3 + 1,8 = 4,1
Далее в добавленном столбце нужно найти наибольший элемент. Строка, в которой он стоит и будет оптимальной стратегией.
В нашем случае наибольший элемент 4,78 (в матрице он выделен). Таким образом, в нашем примере оптимальной стратегией будет А3, т.е. инвестор для вложения должен выбрать третий проект.
Ответ А3 .
Принцип максимина
Решим поставленную выше задачу при принятии решения в условиях неопределенности. В таких условиях также нет единой трактовки понятия наилучшего исхода. Поэтому данную задачу тоже будем решать с помощью различных критериев.
Принцип максимина (критерий Вальда) предполагает полное недоверие ЛПР известным вероятностям состояний окружающей среды. Либо же вероятности состояний окружающей среды считаются неизвестными. Следовательно, данная задача – это задача принятия решения в условиях неопределенности.
При неопределенности выбор наилучшей стратегии может основываться на введении различных разумных гипотез о поведении окружающей среды.
Одна из важнейших и основополагающих гипотез такого типа называется гипотезой антагонизма. Она состоит в предположении, что окружающая среда ведет себя наихудшим для ЛПР образом. На этой гипотезе основывается принцип максимина, называемый также принципом гарантированного результата.
Показатель эффективности стратегии Аi по критерию максимина находится по формуле:
Z = 
Для случая оптимизации потерь критерий превратится в минимаксный и будет таким:
Z = 
#
Таким образом, исходную матрицу необходимо дополнить справа еще одним столбцом, в который нужно внести значения минимальных элементов каждой строки.
Затем из элементов добавленного столбца нужно выбрать наибольший. Строка, в которой он стоит и будет оптимальной стратегией.
Выбранные таким образом альтернативы полностью исключают всякий риск! Это означает, что ЛПР не может столкнуться с худшим результатом, чем тот на который он ориентируется. В силу этого принцип максимина является принципом крайнего пессимизма ЛПР (принципом наибольшей осторожности).
Как бы ни вела себя окружающая среда, результат не может оказаться ниже значения критерия максимина! Это свойство делает принцип максимина наиболее применяемым на практике, особенно в случаях, где от конечного результата зависят жизни людей.
Народная интуиция уже веками непроизвольно использует принцип максимина. Это подтверждается такими поговорками как "Семь раз отмерь – один раз отрежь", "Береженого бог бережет", "Лучше синица в руках, чем журавль в небе".
В нашем случае наибольший элемент в добавленном столбце 4 (в матрице он выделен). Таким образом, в нашем примере оптимальной стратегией будет А3, т.е. инвестор должен выбрать для вложения средств третий проект.
Ответ А3 .
Критерий азартного игрока
Критерий азартного игрока (принцип максимакса) – это диаметральная противоположность принципу максимина, он тоже применяется при принятии решения в условиях неопределенности. Критерий азартного игрока допустим в случаях очень низкого риска, а также когда выигрыш намного превышает возможные потери.
Показатель эффективности стратегии Аi по критерию азартного игрока находится по формуле:
Z = 
Для случая оптимизации потерь критерий будет таким:
Z = 
#
Таким образом, исходную матрицу необходимо дополнить справа еще одним столбцом, в который нужно внести значения максимальных элементов каждой строки.
Затем из элементов добавленного столбца нужно выбрать наибольший. Строка, в которой он стоит и будет оптимальной стратегией.
В нашем случае наибольший элемент в добавленном столбце 15 (в матрице он выделен). Таким образом, в нашем примере оптимальной стратегией будет А1, т.е. инвестор должен выбрать для вложения первый проект.
Применение критерия азартного игрока народная мудрость выразила пословицей "Кто не рискует, тот не пьет шампанского".
Ответ А1 .
Критерий произведений
Критерий произведений тоже применяется при принятии решения в условиях неопределенности. Это более нейтральный критерий по сравнению с принципом максимина и критерием азартного игрока. Критерий произведений производит некое "выравнивание" между большими и малыми значениями аij .
Показатель эффективности стратегии Аi по критерию произведений находится по формуле:
Z = 
Для случая оптимизации потерь критерий будет таким:
Z = 
#
Таким образом, исходную матрицу необходимо дополнить справа еще одним столбцом, в который нужно внести значения произведений всех элементов каждой строки.
Затем из элементов добавленного столбца нужно выбрать наибольший. Строка, в которой он стоит и будет оптимальной стратегией.
В нашем случае наибольший элемент в добавленном столбце 8640 (в матрице он выделен). Таким образом, в нашем примере оптимальной стратегией будет А3, т.е. инвестор должен выбрать для вложения третий проект.
Ответ А3 .
Критерий Сэвиджа
Решение опять принимается в условиях неопределенности.
Сэвидж предложил ввести в рассмотрение новую матрицу, элементы которой определяются по формуле:
rij = 
Построим новую матрицу для нашего примера:
Пример вычислений для первого столбца:
= 6; r11 = 6 – 3 = 3; r21 = 6 – 4 = 2; r31 = 6 – 6 = 0; r41 = 6 – 3 = 3.
Построенная таким способом матрица называется "матрицей сожалений". И действительно, ведь каждый элемент rij выражает "сожаление" ЛПР по поводу того, что он не выбрал наилучшего решения по отношению к 
Далее к матрице сожалений применяется критерий минимакса. Показатель эффективности стратегии Аi при этом находится по формуле:
Z = 
= 
Для случая оптимизации потерь критерий будет таким:
Z = 
#
Таким образом, матрицу сожалений необходимо дополнить справа еще одним столбцом, в который нужно внести наибольшие значения элементов каждой строки.
Затем из элементов добавленного столбца нужно выбрать наименьший. Строка, в которой он стоит и будет оптимальной стратегией.
В нашем случае наименьший элемент в добавленном столбце 5 (в матрице он выделен). Таким образом, в нашем примере оптимальной стратегией будет А3, т.е. инвестор должен выбрать для вложения третий проект.
Ответ А3 .
Критерий Гурвица
Решение принимается в условиях неопределенности.
Гурвиц предложил критерий, показатель эффективности стратегии Аi при котором находится где-то между точками зрения крайнего оптимизма (критерий азартного игрока) и крайнего пессимизма (критерий максимина). Для этого вводят некий коэффициент l – уровень пессимизма. Выбор уровня пессимизма – процесс субъективный. Чаще всего его выбирают равным либо 0,6 либо 0,5. После этого показатель эффективности стратегии Аi по критерию Гурвица находится по формуле:
Z = 
Для случая оптимизации потерь критерий будет таким:
Z = 
#
Таким образом, исходную матрицу необходимо дополнить справа еще тремя столбцами. В первый нужно внести значения наименьших элементов всех строк, умноженных на уровень пессимизма l = 0,6. Во второй нужно внести значения наибольших элементов всех строк, умноженных на уровень оптимизма 1 – l = 1 – 0,6 = 0,4 . В третий добавленный столбец внесем сумму значений первых двух добавленных столбцов:
Затем из элементов добавленного столбца нужно выбрать наибольший. Строка, в которой он стоит и будет оптимальной стратегией.
В нашем случае наибольший элемент в добавленном столбце 7,2 (в матрице он выделен). Таким образом, в нашем примере оптимальной стратегией будет А1, т.е. инвестор должен выбрать для вложения средств первый проект.
Ответ А1 .
Матричные игры
Раздел "Теории принятия решений" в условиях противодействия называется теорией игр. А так как в основном условия задач в "Теории принятия решений" задаются в виде матриц, то рассматриваемые конфликтные ситуации называются матричными играми. В матричных играх состояниями В1, В2, …, Вn управляет не беспристрастная природа, а активный противник, преследующий сугубо свои цели.
ЛПР, управляющий своими стратегиями (ходами) А1, А2, …, Аn, и его противник, управляющий стратегиями (ходами) В1, В2, …, Вn в данной ситуации называются игроками.
Элементы матрицы аij , заданной в условии, называются выигрышами(платежами) игрока А. А вся матрица называется матрицей платежей.
Далее возможны два случая. Если в матричной игре задана одна платежная матрица, то естественно предположить, что выигрыши первого игрока будут являться проигрышами второго игрока. Такая антагонистическая ситуация называется матричной игрой с нулевой суммой. Цель игры для первого игрока (ЛПР) – побольше выиграть, а для второго игрока – поменьше проиграть. Иными словами, целью игры является определение оптимальной стратегии для каждого игрока – такой стратегии, при которой выигрыш первого игрока будет максимальным, а проигрыш второго игрока будет минимальным.
Однако, такая ситуация бывает не всегда. Зачастую в жизни ваш противник преследует сугубо свои цели, определенные своими выигрышами. В этом случае матричная игра задается двумя платежными матрицами. Или для краткости элементы одной платежной матрицы состоят из двух чисел: (аij, bij). Такая ситуация называется матричной игрой с ненулевой суммой. И для первого и для второго игроков цель игры – побольше выиграть.
Очевидно, что рассмотренная матричная игра предполагает, что каждый игрок делает только по одному ходу. Естественно, что многие конфликтные ситуации предполагают по нескольку ходов каждого игрока. Такие игры рассматриваются пошагово и решаются методами динамического программирования. На каждом отдельном шаге такая игра рассматривается как игра с одним ходом.
Матричные игры для двух игроков с нулевой и ненулевой суммой достаточно хорошо изучены и для них разработана теория оптимального поведения игроков.
Однако в жизненной практике в конфликтных ситуациях зачастую участвуют более чем две стороны. Чем больше игроков – тем больше проблем. Такие игры менее изучены и здесь есть просторное поле для новых фундаментальных научных исследований.
Несмотря на несколько легкомысленное звучание основных терминов, теория игр является строго научной дисциплиной с точными математическими выкладками.
На протяжении всего своего исторического пути развития человечество ежедневно сталкивается с конфликтными ситуациями: политическими, военными, экономическими, социальными и прочими, которые проявляются как в глобальных, так и в малых (вплоть до личных) формах. И если бы Человеку хватило бы ума в конфликтных ситуациях пользоваться не силой, не надеждой на "авось", а математикой, то жизнь наверняка была бы другой. Будем надеяться, что новое поколение, усвоив курс "Исследование операций" J, изменит жизнь к лучшему!
Итак, рассмотрим игру, в которой ЛПР противостоит "думающий" противник.
Возможны такие случаи:
1) Ходы игроками делаются одновременно.
2) Первым ходит игрок 2 – противник, но игрок 1 – ЛПР, не имеет информации о ходе противника.
3) Первым ходит игрок 2 – противник, но игрок 1 – ЛПР, знает о ходе противника.
4) Первым ходит игрок 1, но игрок 2 не имеет информации о ходе противника.
5) Первым ходит игрок 1, но игрок 2 знает о ходе противника.
Очевидно, что случаи 1), 2) и 4) идентичны – никто из игроков не знает о ходе противника ничего.
Рассмотрим случай 3). Так как ЛПР имеет полную информацию о ходе противника, то мы имеем ситуацию принятия решения в условиях полной определенности. Как уже отмечалось выше, такими задачами занимается математическое программирование.
Рассмотрим случай 5). Так как ЛПР ходит первым, то его противник наверняка выберет самую худшую для ЛПР стратегию. Поэтому в такой ситуации ЛПР необходимо принимать решение о своем ходе согласно принципу наибольшей осторожности, т.е. согласно принципу максимина. Это утверждение однозначно, легко математически доказывается и не должно подвергаться сомнению ни в каких жизненных ситуациях.
Итак, содержательны по своей сути только случаи 1), 2) и 4), которые сводятся к одному случаю. Это как мы видим, принятие решения в условиях неопределенности.
Постановка задачи
Если платежная матрица не имеет седловой точки, то 
. А значит 
. Такая игра в чистых стратегиях не разрешима. Первый игрок в таком случае будет стремиться увеличить свой выигрыш, а второй – уменьшить свой проигрыш. Поиск такого решения приводит к применению сложной стратегии, состоящей в случайном применении двух и более чистых стратегий с определенными вероятностями:
PA = (p1, p2, …, pm) где pi – это вероятности применения чистых стратегий игроком А;
QB = (q1, q2, …, qn) где qj – это вероятности применения чистых стратегий игроком B;
при этом 
и 
.
Такие наборы вероятностей применения чистых стратегий игроками А и В называются смешанными стратегиями.
Заметим, что чистые стратегии – это частный случай смешанных стратегий. Например, чистая стратегия первого игрока – это смешанная стратегия, у которой все вероятности pi = 0 , кроме соответствующего номера k чистой стратегии: pk = 1 .
Основная теорема теории игр (Теорема фон-Неймана): любая конечная игра двух лиц с нулевой суммой разрешима в смешанных стратегиях.
Как же искать смешанные стратегии? Их можно найти точно – алгебраическим способом (в частности, с помощью симплекс-метода) или графическим способом (для игры размерности 2 х n или m х 2 ).
Для того чтобы точно найти решение матричной игры в смешанных стратегиях, нужно представить заданную матричную игру в виде задачи линейного программирования и решить её симплекс-методом.
Рассмотрим матричную игру, не разрешимую в чистых стратегиях, в общем виде:
Заметим, что в матричной игре, разрешимой в чистых стратегиях, элементы платежной матрицы могут быть как положительными, так и отрицательными. Для симплекс-метода, которым будем решать игру, не разрешимую в чистых стратегиях, необходимо, чтобы элементы платежной матрицы были неотрицательными. Для этого, если в платежной матрице будут отрицательные элементы, нужно ко всем элементам платежной матрицы прибавить достаточно большое число с . При этом решение задачи не изменится, а цена игры увеличится на с.#
PA = (p1, p2, …, pm)– это оптимальная смешанная стратегия первого игрока. Её применение гарантирует первому игроку выигрыш не меньший, чем цена игры n . Если при этом второй игрок выберет стратегию В1, математически все вышесказанное будет иметь вид:
а11р1 + а21р2 + … + am1pm ≥ n
Таких неравенств будет столько, сколько есть возможных альтернатив у второго игрока, т.е. столбцов платежной матрицы – n штук:
а11р1 + а21р2 + … + am1pm ≥ n
а12р1 + а22р2 + … + am2pm ≥ n
а1nр1 + а2nр2 + … + amnpm ≥ n
Разделив все неравенства на n , получим (в общем виде):
а1j 
+ а2j 
+ … + amj 
≥ 1
Обозначим: 
= xi, . С помощью таких новых переменных вышеуказанные неравенства запишутся в виде:
а11 x1 + а21 x2 + … + am1 xm ≥ 1
а12 x1 + а22 x2 + … + am2 xm ≥ 1
а1n x1 + а2n x2 + … + amn xm ≥ 1
Просуммируем новые переменные:
= x1 + x2 + … + xm = 
+ 
+ … + = 
= 
PA = (p1, p2, …, pm)– это оптимальная смешанная стратегия первого игрока. То есть нужно так подобрать (p1, p2, …, pm) , чтобы n была как можно большей. Или же, что то же самое, чтобы 
была как можно меньшей.
Таким образом, используя новые переменные и учитывая всё вышесказанное, исходную матричную игру можно представить в виде задачи линейного программирования:
найти вектор переменных Х = {x1, x2, … , xm}, такой что:
целевая функция f = 
min
при множестве ограничений:
АТХ ≥ Е
гдеА – матрица коэффициентов (платежная матрица), заданная в условии;
Е – единичный вектор
Х – вектор неизвестных переменных, такой что xi = 
;
n – это цена игры:n = 
= 
;
рi – это коэффициенты вектора смешанной стратегии первого игрока.
Линейные свёртки
Начнем с линейных свёрток. Все линейные свёртки основываются на принципе: "низкая оценка по одному критерию может быть компенсирована высокой оценкой по другому".
Рассмотрим простую линейную аддитивную свёртку:
Z* = max 
,
То есть, данная свёртка подсчитывает, сколько раз та или иная стратегия была оптимальной. Результаты отобразим в таблице:
В последнем столбе таблицы размещены результаты свёртки. Как видим, оптимальной стратегией является А3.
Такая свёртка является самой простой из линейных, она не учитывает количественных показателей значений критериев.
Рассмотрим линейную аддитивную свёртку с нормирующими множителями:
Z* = max 
,
где aj = 
– нормирующие множители.
Как видим, оптимальной стратегией также является А3. Но в этом случае уже нет такого количественного отрыва как в предыдущей простой линейной свёртке. Да и стратегия А2 уже не кажется очень сильно плохой. Если бы были чуть другие начальные данные, то ответы двух рассмотренных вариантов свёрток могли бы и не совпасть.
Линейная аддитивная свёртка с нормирующими множителями позволяет работать с количественными критериями, имеющими, как в нашем случае, разные единицы измерений.
Рассмотрим линейную аддитивную свёртку с весовыми коэффициентами:
Z* = max 
,
где aj – те же нормирующие множители,
вj – весовые коэффициенты, отражающие относительный
вклад частных критериев в общий критерий.
Весовые коэффициенты принято указывать уже нормированными величинами (Sвj = 1).
Очевидно, что в каждой отдельной конкретной ситуации частные критерии по-разному влияют на общий суперкритерий. Поэтому естественно им придать в общей формуле разный удельный вес. Это можно сделать с помощью весовых коэффициентов. Но где же их взять? Обычно ЛПР сам назначает каждому критерию весовые коэффициенты на свой "мудрый" взгляд. На этом этапе строгая математическая наука заканчивается – конечный результат лежит целиком на совести ЛПР и зависит от его опыта и интуиции в данной сфере. Однако от такого субъективизма никуда не денешься – нельзя же всю жизнь формализовать с помощью математических формул!
Как видим, при неизменном условии задачи оптимальной получилась стратегия А2, хотя в двух предыдущих свёртках она "пасла задних". Все дело в весовых коэффициентах!
Мультипликативные свёртки
Рассмотрим мультипликативную свёртку с нормирующими множителями:
Z* = max 
,
где aj – нормирующие множители.
Мультипликативная свёртка основывается на постулате: "низкая оценка хотя бы по одному критерию влечет за собой низкое значение функции полезности". Действительно, если вы выбираете торт, и он – несвежий, то это обстоятельство никак не может быть компенсировано его красотой или ценой.
Оптимальной стратегией снова является А3.
Посмотрим, какие результаты даст мультипликативная свёртка с весовыми коэффициентами:
Z* = max 
,
где aj – нормирующие множители,
вj – весовые коэффициенты.
Итоги отражены в таблице:
Оптимальной стратегией снова является А3.
В конце еще раз напомним непременное правило: перед тем, как применять какую-либо свёртку нужно автоматически всегда выделять множество Парето. И именно для множества Парето применять свёртки. Иначе вы или ваша программа будете выполнять лишнюю ненужную работу.
Групповая оценка объектов
В приведенном выше материале подразумевалось, что ЛПР – это некий эксперт-аналитик, принимающий решение по поставленной проблеме. А если проблемой занимаются несколько экспертов? А решение то должно быть одно! Такая задача называется задачей группового выбора или задачей принятия корпоративного решения.
Тут нужно отметить один важный психологический момент. Взрослого человека (начиная лет с 5-10) практически никогда невозможно заставить изменить свое мнение. (Есть, конечно, "безотказные" методы типа насилия, или денежного подкупа, но они к науке не имеют никакого отношения.) Поэтому эксперты в группе всегда будут:
- иметь разные мнения по поводу набора критериев, по которым надо оценивать альтернативные решения;
- иметь разные мнения о сравнительной значимости (весовых коэффициентах) критериев;
- давать разные оценки альтернатив по критериям;
- кроме этого эксперты будут иметь разную компетентность.
Исходя из таких очевидных фактов, можно с уверенностью утверждать, что у группы экспертов всегда должен быть руководитель.
Каждый из экспертов группы в принятии своего решения будет руководствоваться своим опытом и своими знаниями. Будем надеяться, что вышеприведенный материал окажет экспертам некую посильную помощь. Материал данного подраздела предназначен для руководителей групп экспертов, которые на основе всех решений группы обязаны приять единственное правильное решение.
Вспомним, как обычно преодолеваются групповые разногласия? В подавляющем большинстве случаев это делается с помощью обыкновенного голосования.
Рассмотрим формализованный пример голосования. В таблице начальных данных отражены количественные оценки четырёх альтернативных решений девятью экспертами:
Для начала необходимо найти множество Парето: это будут альтернативы А1, А2, А4. Оптимальное решение будем искать среди них. Для проведения голосования определим функцию полезности:
Z* = max ,
В последнем столбе таблицы размещены результаты голосования. Как видим, оптимальным решением является альтернатива А4 – за неё проголосовало пять экспертов из девяти – больше половины.
При всей простоте, широкой распространенности и многовековой исторической традиции использования метод голосования имеет один существенный недостаток. Голосование не считается с мнением меньшинства. Мнение меньшинства полностью игнорируется! Но иногда ведь случается, (правда очень редко) что именно среди этого меньшинства и находилось наилучшее решение! Кроме практического результата голосование наносит психологический удар по тем экспертам, мнения которых были отброшены. Математические методы принятия корпоративных решений стараются исправить этот недостаток. Учитываются мнения всех экспертов.
Рассмотрим такую функцию полезности с нормирующими множителями:
Z* = max 
,
где aj = .
В этом случае оптимальным решением является альтернатива А1.
Заметим, что такой способ учитывает также и то, что эксперты пользовались разными шкалами оценок объектов.
А теперь попробуем учесть ещё и степень компетентности каждого эксперта. Функция полезности при этом будет выглядеть так:
Z* = max 
,
где aj – те же нормирующие множители,
kj – коэффициенты компетентности экспертов.
Ниже будет рассмотрен один из способов определения коэффициентов компетентности экспертов.
А пока рассмотрим ту же задачу с уже якобы вычисленными коэффициентами компетентности экспертов. В таблице снова сначала – условие, ниже – результаты:
А теперь мы получили в качестве оптимальной альтернативу А2.
Надо отметить, что приведенные два последних способа принятия группового решения годятся только для согласованных суждений экспертов. Согласованность – это степень расхождения мнений экспертов. Методика вычисления согласованности оценок экспертов достаточно сложна. По необходимости с ней можно ознакомиться в специальной литературе по принятию корпоративных решений.
Если эксперты честно оценивают реальный объект, то их оценки не должны сильно расходиться. Если же они все-таки существенно расходятся, то можно получить часто упоминаемую в литературе так называемую "среднюю температуру по больнице". Действительно, если сложить температуру всех высокотемпературных больных и температуру тел в морге, а потом поделить на общее количество замеров, то можно получить 36,6°. Свидетельствует ли это о том, что "в среднем" все находящиеся в больнице здоровы?
Если согласованность оказалась низкой, то нужно пытаться выяснить причину расхождений и по возможности попытаться устранить её. Часто причиной может быть отсутствие важной информации у некоторых экспертов. В некоторых случаях эксперты разбиваются на две устойчивые группы. Группы нужно уметь выявлять и обрабатывать отдельно.
Домашняя контрольная работа
Согласно рабочей учебной программе дисциплины "Теория принятия решений" в модуле №3 выполняется домашняя контрольная работа.
Цель домашней контрольной работы – детальная и более тщательная проработка лекционного и практического материала, с целью проверки и контроля степени его усвоения, формирование у студентов предусмотренных рабочей программой навыков.
Домашняя контрольная работа выполняется на бумажных носителях.
Домашняя контрольная работа содержит 30 вариантов. Каждый вариант содержит четыре задания:
- задание №1 – решение матричной игры в чистых стратегиях;
- задание №2 – решение матричной игры в смешанных стратегиях симплекс-методом;
- задание №3 – решение матричной игры в смешанных стратегиях графическим методом.
Студент выбирает вариант домашней контрольной работы согласно своему порядковому номеру в журнале списка своей группы. Контрольная работа, не соответствующая своему варианту, не проверяется и к защите не допускается.
Задание №1.
Определить оптимальные чистые стратегии и цену игры:
1 вариант 2 вариант 3 вариант
4 вариант 5 вариант 6 вариант
7 вариант 8 вариант 9 вариант
10 вариант 11 вариант 12 вариант
13 вариант 14 вариант 15 вариант
16 вариант 17 вариант 18 вариант
19 вариант 20 вариант 21 вариант
22 вариант 23 вариант 24 вариант
25 вариант 26 вариант 27 вариант
28 вариант 29 вариант 30 вариант
Задание №2.
Определить симплекс-методом оптимальные смешанные стратегии и цену игры:
1 вариант 2 вариант 3 вариант
4 вариант 5 вариант 6 вариант
7 вариант 8 вариант 9 вариант
10 вариант 11 вариант 12 вариант
13 вариант 14 вариант 15 вариант
16 вариант 17 вариант 18 вариант
19 вариант 20 вариант 21 вариант
22 вариант 23 вариант 24 вариант
25 вариант 26 вариант 27 вариант
28 вариант 29 вариант 30 вариант
Задание №3.
Определить графическим методом оптимальные смешанные стратегии и цену игры:
1 вариант 2 вариант 3 вариант
4 вариант 5 вариант 6 вариант
7 вариант 8 вариант 9 вариант
10 вариант 11 вариант 12 вариант
13 вариант 14 вариант 15 вариант
16 вариант 17 вариант 18 вариант
19 вариант 20 вариант 21 вариант
22 вариант 23 вариант 24 вариант
25 вариант 26 вариант 27 вариант
28 вариант 29 вариант 30 вариант
Вопросы к модульным тестированиям
Общие вопросы к всем модулям:
1. Что такое исследование операций?
2. Что такое ЛПР?
3. Что такое математическая модель?
4. Что такое переменные?
5. Что такое альтернатива?
6. Что такое план?
7. Что такое ограничение?
8. Что такое допустимое множество?
9. Что такое допустимый план?
10. Что такое целевая функция?
11. Что такое оптимальный план?
12. Что такое математическое моделирование?
13. Что такое математическое программирование?
14. Что такое линейное программирование?
15. Что такое целочисленное программирование?
16. Что такое динамическое программирование?
17. Что такое нелинейное программирование?
18. Что такое задача принятия решения?
19. Что такое бинарные отношения?
20. Что такое ориентированный граф?
21. Что такое множество Парето?
22. Найти множество Парето.
23. Что такое принятие решения в условиях определенности?
Вопросы к модулю №1:
24. Что такое принятие решения в условиях риска?
25. Какие условия использования критерия Байеса?
26. Решить задачу с помощью критерия Байеса.
27. Какие условия использования критерия Лапласа?
28. Решить задачу с помощью критерия Лапласа.
29. Какие условия использования критерия Гермейера?
30. Решить задачу с помощью критерия Гермейера.
31. Какие условия использования критерия Ходжа-Лемана?
32. Решить задачу с помощью критерия Ходжа-Лемана.
Воп росы к модулю №2:
33. Что такое принятие решения в условиях неопределенности?
34. Какие условия использования принципа максимина?
35. Решить задачу с помощью принципа максимина.
36. Какие условия использования критерия азартного игрока?
37. Решить задачу с помощью критерия азартного игрока.
38. Какие условия использования критерия произведений?
39. Решить задачу с помощью критерия произведений.
40. Какие условия использования критерия Севиджа?
41. Решить задачу с помощью критерия Севиджа.
42. Какие условия использования критерия Гурвица?
43. Решить задачу с помощью критерия Гурвица.
Вопросы к модулю №4:
44. Что такое принятие решения в условиях противодействия?
45. Что такое матричная игра?
46. Что такое платежи матричной игры?
47. Что такое матрица платежей?
48. Что такое матричная игра с нулевой суммой?
49. Что такое матричная игра с ненулевой суммой?
50. Что такое седловая точка?
51. Что такое чистая стратегия?
52. Что такое смешанная стратегия?
53. Найти седловую точку матрицы.
54. Решить матричную игру в чистых стратегиях.
55. Найти множество Парето для задачи двукритериального выбора.
56. Решить задачу многокритериального выбора методом линейной аддитивной свертки.
57. Решить задачу многокритериального выбора методом мультипликативной свертки.
58. Решить задачу многокритериального выбора методом максиминной свертки.
59. Решить задачу про групповую экспертную оценку.
60. Решить задачу экспертной оценки объектов с учетом компетентности экспертов.
8.3 Контрольные вопросы к экзамену по дисциплине
1. Исследование операций как наука о принятии оптимальных решений.
2. Построение математической модели.
3. Математическое программирование. (Общий обзор, основные понятия, классы задач.)
4. Принятие решения: постановка задачи, возможные случаи.
5. Принятие решений в условиях риска. Критерий Байеса.
6. Принятие решений в условиях риска. Критерий Лапласа.
7. Принятие решений в условиях риска. Критерий Гермейера.
8. Принятие решений в условиях риска. Критерий Ходжа-Лемана.
9. Принятие решений в условиях неопределенности. Принцип максимина.
10. Принятие решений в условиях неопределенности. Критерий азартного игрока.
11. Принятие решений в условиях неопределенности. Критерий произведений.
12. Принятие решений в условиях неопределенности. Критерий Севиджа.
13. Принятие решений в условиях неопределенности. Критерий Гурвица.
14. Принятие решений в условиях противодействия. Общие понятия.
15. Матричные игры.
16. Чистые стратегии, седловая точка, цена игры.
17. Смешанные стратегии.
18. Представление матричной игры в виде задачи линейного программирования.
19. Графический метод решения матричной игры.
20. Принятие решений в условиях нескольких критериев выбора (многокритериальный выбор).
21. Линейные свёртки.
22. Максиминная и лексикографическая свёртки.
23. Мультипликативные свёртки.
24. Описание выбора на языке бинарных отношений.
25. Множество Парето. Максимальный элемент.
26. Матрицы смежности и инцидентности.
27. Принятие корпоративных решений.
28. Компетентность экспертов.
Контрольные экзаменационные вопросы используются в случае сдачи студентом экзамена по дисциплине на повышенную оценку в сравнении с оценкой, которую он получил по рейтингу полусеместра. В соответствии с действующим "Положением о кредитно-модульной системе организации учебного процесса и рейтинговом оценивании знаний студентов ЗГИА" оценка, которая получена на экзамене является окончательной и именно она вносится в экзаменационную ведомость и индивидуальный план (зачетную книжку) студента.
Учебно-методический материал по дисциплине
Основная литература (имеется в наличии в библиотеке ЗГИА)
1.Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для вузов. - М.: Высшая школа , 1986. - 319 c.
2.Волков И.К., Загоруйко Е.А. Исследование операций: Учебник для втузов / Ред. Зарубин В.В., Крищенко А.П. - 2-е изд. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2002. - 435 c.
3.Евланов В.Г. Теория и практика принятия решений. – М.: Экономика, 1984. – 175 с.
4.Кини Р.Л., Райфа Х. Принятие решений при многих критериях: предпочтения и замещения. – М.: Радио и связь, 1981. – 560 с.
5.Колпаков В.М. Теория и практика принятия управленческих решений: Учеб. пособие для вузов. – К.: МАУП, 2000. – 254 с.
6.Костевич Л.С., Лапко А.А. Теория игр. Исследование операций: Учеб. пособие для вузов. - Мн.: Вышэйшая школа, 1982. - 230 c.
7.Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование: Учеб. пособие для вузов - М.: Высшая школа , 1976. - 350 c.
8.Мулен Э. Кооперативное принятие решений: Аксиомы и модели. - М.: Мир, 1991. - 463c.
9.Таха Хемди А. Введение в исследование операций, 7-е изд: Пер. с англ. – М.: Изд. дом "Вильямс", 2005. – 912 с.
10.Теория выбора и принятия решений Учеб. пособие для вузов. - М.: Наука, 1982. - 328 c.
11.Тоценко В.Г. Методы и системы поддержки принятия решений: Алгоритмический аспект / НАН Украины. Ин-т пробл. регистрации информ. - К.: Наук. думка, 2002. – 381 c.
12.Трухаев Р.И. Модели принятия решений в условиях неопределенности / АН СССР. Дальневост. науч. центр. Хабаров. комплекс НИИ. - М.: Наука, 1981. - 257 c.
Дополнительная литература
13.Вентцель Е.С. Исследование операций. – М.: Советское радио, 1972.
14.Гафт М.Г., Подиновский В.В. О построении решающих правил в задачах принятия решений. - Автоматика и телемеханика, №6, 1981.
15.Джексон П. Введение в экспертные системы: Пер. с англ.: Учеб. пособие. – М.: Изд. дом "Вильямс", 2001.
16.Ершов А.Т., Карандаев И.С., Статкус А.В. Матричные игры и графы. – М.: МИУ, 1986.
17.Ларичев О.И. Наука и искусство принятия решений. – М.: Наука, 1979.
18.Ларичев О.И. Теория и методы принятия решений, а также Хроника событий в Волшебных странах: Учебник. – М.: Логос, 2003.
19.Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: Учеб. пособие. – М.: ФИЗМАТЛИТ, 2002. – 240с.
20.Фон Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение. – М.: Наука, 1970.
21.Черноруцкий И.Г. Методы принятия решений. – СПб.: БХВ-Петербург, 2005. – 416 с.
Учебно-методическое пособие
Ю.О. Матузко
Запорожье 2009
Содержание
Ведение
Раздел 1. Основные понятия и структура исследования операций
Раздел 2. Принятие решения в условиях риска
2.1 Постановка задачи
2.2 Критерий Байеса
2.3 Критерий Лапласа (Бернулли)
2.4 Критерий Гермейера
2.5 Критерий Ходжа-Лемана
Раздел 3. Принятие решения в условиях неопределенности
3.1 Принцип максимина
3.2 Критерий азартного игрока
3.3 Критерий произведений
3.4 Критерий Сэвиджа
3.5 Критерий Гурвица
Раздел 4. Принятие решения в условиях противодействия
4.1 Матричные игры
4.2 Матричные игры, разрешимые в чистых стратегиях
4.3 Матричные игры, разрешимые в смешанных стратегиях
4.3.1 Постановка задачи
4.3.2 Решение задачи симплекс-методом
4.3.3 Решение задачи графическим методом
Раздел 5. Принятие решения в условиях нескольких критериев выбора40
5.1 Постановка задачи, основные понятия
5.2 Линейные свёртки
5.3 Максиминная и лексикографическая свёртки
5.4 Мультипликативные свёртки
5.5 Многокритериальный выбор на языке бинарных отношений
Раздел 6. Принятие корпоративных решений
6.1 Групповая оценка объектов
6.2 Определение коэффициентов компетентности экспертов
Раздел 7. Критерии модульного оценивания знаний
Раздел 8. Задания для самостоятельной работы студентов
8.1 Домашняя контрольная работа
8.2 Вопросы к модульным тестированиям
8.3 Контрольные вопросы к экзамену по дисциплине
Учебно-методический материал по дисциплине
Ведение
Дисциплина "Теория принятия решений" читается студентам специальности "Автоматизированное управление технологическими процессами". Такой специалист по окончании учебы должен уметь выдать заказчику законченный программно-алгоритмический продукт, который будет автоматизировать процесс принятия решений в конкретном технологическом процессе, описанном заказчиком. Заказчик в таких случаях может представлять различные отрасли народного хозяйства: он может быть химиком, металлургом, строителем, экономистом, электронщиком и т.п. Главное, чтобы его технологический процесс, в котором нужно принимать решения, был успешно автоматизирован. Предлагаемый курс дает теоретические и практические основы математически обоснованного процесса принятия решений. Рассматриваемые в данном пособии задачи носят чисто абстрактный характер по своему текстовому условию. Главное в них – это количественные и качественные методы решения поставленной проблемы принятия решений, которые могут быть применены к различным отраслям.
В пособии охвачена лишь общая часть дисциплины "Принятие решений". Дело в том, что предмет "Теория принятия решений" читается студентам на протяжении всего двух календарных месяцев. Автор по возможности попытался за столь короткий срок охватить наиболее общие и значимые понятия и методы довольно широкой дисциплины "Принятие решений". Более детальную информацию по дисциплине можно получить из специальной литературы, указанной в пособии.
Данное учебное пособие содержит критерии модульного оценивания знаний, задания домашней контрольной работы, вопросы к модульным тестированиям, а также контрольные вопросы к экзамену по предмету "Теория принятия решений".
Раздел 1. Основные понятия и структура исследования операций
Принимать решения, как отдельному человеку, так и различным группам людей, вплоть до всего человечества приходится практически во всех областях своей деятельности. Единственное, чего мы не выбираем, следуя народной мудрости, так это родителей и Родины. Причем в некоторых областях (военных, медицинских, космических, в атомной энергетике, химической промышленности и др.) возникает потребность принятия достаточно сложных управленческих решений, ошибка в которых может повлечь за собой катастрофические последствия. В силу этого появилась необходимость выделить процесс принятия оптимальных решений в отдельную область науки, которая бы формализовала и систематизировала данный процесс.
Исторически считается, что это произошло в начале 40-х годов ХХ века, когда группа английских ученых математически сформулировала и нашла решение задачи об оптимальном способе доставки на фронт войск, оружия и снаряжения. И сразу же стали интенсивно поступать заказы на решение новых военных задач. Позднее эти исследования были перенесены и на гражданскую сферу и обобщены в отдельную науку – исследование операций.
Исследование операций стала основным научным инструментом при принятии оптимальных решений в самых разнообразных областях человеческой деятельности. Специалиста в этой науке в литературе обычно называют аналитиком (или системным аналитиком, или лицом, принимающим решение (далее ЛПР)).
Дадим некоторые основные определения и обозначим ориентировочное структурное строение исследования операций. Даная структура также отражает этапы, которые должен последовательно пройти ЛПР при принятии решения.
1 этап. Постановка (формулировка) задачи (проблемы).
На этом этапе аналитик должен трансформировать слова заказчика "хочу, чтобы было так" в четко сформулированную задачу. В 99% случаях заказчик не только не может предоставить, но и понятия не имеет о тех данных, которые необходимы аналитику для успешного разрешения проблемы. Оно и понятно – ведь у него нет соответствующего образования. (На самом деле, такое образование заказчику и не нужно, ведь он обратился к грамотному специалисту-аналитику, выпускнику ЗГИА! J) Все необходимое аналитик должен добыть себе сам. Так будет лучше по всем показателям – и по времени и, что немаловажно, по искажению информации (формулировка задачи с чьих-то слов уже априори чревато ошибками). Аналитику необходимо увидеть и изучить проблему "изнутри", для этого ему нужно "внедриться" в сложившуюся ситуацию. Зачастую аналитику надо "внедриться" и поработать на всех ключевых постах в организации заказчика, столкнувшейся с проблемой. На это может уйти от нескольких дней до месяцев.
2 этап. Построение математической модели задачи.
Здесь четко поставленная и сформулированная жизненная проблема формализуется математически.
1) Определяются переменные – переменные величины (их может быть как несколько, так и одна), изменение которых влияет на конечный результат задачи. Наборы различных конкретных значений переменных называются альтернативами (также во многих литературных источниках набор переменных называется планом).
2) Определяются ограничения, которые накладываются на переменные. Пересечение всех полученных ограничений задает допустимое множество. Набор переменных, которые удовлетворяют всем ограничениям, называется допустимым планом.
3) Определяется критерий, по которому должны отбираться альтернативные решения (планы). Такой критерий называется целевой функцией.
Задача состоит в том, чтобы найти такой набор переменных (выбрать такую альтернативу), чтобы они принадлежали допустимому множеству (т.е. удовлетворяли всем ограничениям задачи) и чтобы целевая функция от этих переменных принимала свое оптимальное значение. Такой набор переменных называется оптимальным планом. Понятно, что оптимальный план должен быть допустимым, поэтому и ищется оптимальный план только среди допустимых планов.
Описанными первыми двумя этапами занимается дисциплина "математическое моделирование", являющаяся составной частью исследования операций.
3 этап. Решение математической модели задачи.
Решением математических моделей задач занимается дисциплина "математическое программирование".
В исследовании операций нет единого общего метода решений всех математических моделей. Многолетние исследования позволили обобщить и сгруппировать схожие типы моделей в определенные классы задач. Методы решения данных классов задач составляют отдельные разделы математического программирования, со временем они даже трансформировались в отдельные дисциплины. Дадим краткий обзор некоторых из них.
1) Линейное программирование. В этом классе задач и целевая функция и все ограничения являются линейными функциями. К таким задачам относятся:
задача о плане производства;
задача о диете;
и др.
2) Целочисленное программирование. В этих задачах целевая функция и все ограничения также являются линейными. Все переменные должны принимать только целочисленные значения. К таким задачам относятся:
транспортная задача;
задача о назначениях;
и др.
3) Динамическое программирование. Применяется, когда исходную задачу можно разбить на меньшие подзадачи и решать их пошагово. К таким задачам относятся:
задача коммивояжера;
задача об управлении запасами;
задача о ранце;
и др.
4) Нелинейное программирование. В этом классе задач либо целевая функция, либо все или некоторые ограничения являются нелинейными функциями.
Еще раз акцентируем внимание, что выше приведены лишь некоторые основные разделы математического программирования. Кроме указанных разделов еще существуют теория графов, теория расписаний, сетевое планирование, системы массового обслуживания, теория марковских процессов и др. Каждый раздел математического программирования – это отдельная сформировавшаяся дисциплина, требующая достаточно углубленного теоретического и, особенно, практического изучения.
4 этап. Принятие решений.
На этой стадии аналитик (лицо, принимающее решение) на основе пройденных предыдущих этапов должен принять оптимальное решение. Это и является предметом изучаемого курса "Теория принятия решений".
Само собой разумеется, что студенты, приступившие к изучению курса "Теория принятия решений" ранее должны были изучить и, что немаловажно, успешно сдать и математическое моделирование, и математическое программирование. Без этого необходимого условия ЛПР вряд ли примет оптимальное решение. Невозможно ведь учиться в пятом классе, до этого не выучив во втором классе таблицы умножения! Равно как и невозможно быть директором роддома, не зная, откуда берутся дети.
Принятие решения – это задача управленческого типа. Под ней понимается задача выбора лицом, принимающим решение (ЛПР) наилучшего способа (исхода) из некоторого конечного множества допустимых вариантов (альтернатив). После принятия решения изучаемая система переходит в новое состояние, на которое будет реагировать окружающая среда. Окружающей средой может быть военная, экономическая, финансовая, техническая или какая-либо другая обстановка. При этом возможны такие случаи:
1) ЛПР знает реакцию окружающей среды на выбор им той или иной альтернативы, т.е. он знает насколько "полезной" или "вредной" для его системы будет реакция окружающей среды на выбор им той или иной альтернативы. Такая ситуация называется задачей принятия решения в условиях определенности. В условиях определенности математическое программирование дает точное решение поставленной задачи. Поэтому необходимости выбирать из нескольких вариантов попросту нет. Таким образом, в условиях определенности "Теория принятия решений" не используется, такими задачами занимается математическое программирование.
2) ЛПР знает вероятность реакции окружающей среды на выбор им той или иной альтернативы. Такая ситуация называется задачей принятия решения в условиях риска.
3) ЛПР ничего не знает о реакции окружающей среды на выбор им той или иной альтернативы. Такая ситуация называется задачей принятия решения в условиях неопределенности.
При этом предполагается, что в перечисленных случаях окружающая среда реагирует на принятое ЛПР решение беспристрастно (как природа), не преследуя никаких своих целей.
4) Однако зачастую бывают ситуации, когда в качестве окружающей среды может выступать, например, конкурирующая фирма, военный противник, конкурент на выборах и т.п. В этом случае такая окружающая среда будет реагировать уже совсем не беспристрастно, а сугубо в своих интересах. Такая ситуация называется задачей принятия решения в условиях противодействия.
Раздел 2. Принятие решения в условиях риска
Постановка задачи
Рассмотрим следующую ситуацию.
Представьте что вы – глава пенсионного фонда Украины. На счета пенсионного фонда Украины поступают налоговые отчисления по достаточно большой процентной (большей, чем в большинстве развитых странах) ставке. По расчетам этих денег должно хватить на выплату пенсий сегодняшним пенсионерам и на накопление для выплат сегодняшним налогоплательщикам, по достижении ими пенсионного возраста. Ваша непосредственная обязанность, как главы пенсионного фонда обеспечить выполнение этих двух задач. Первая задача – выплата текущих пенсий – это чисто техническое задание. Будем считать, что с ним вы блестяще справитесь.
А что делать с накоплениями? Если эти деньги не трогать и "заморозить", то через несколько лет ввиду инфляции сегодняшний налогоплательщик получит сущие гроши. Естественным выходом (так делают во всем мире) будет эти средства во что-нибудь вложить (инвестировать).
Допустим, что вы, как инвестор, имеете возможность вложить средства пенсионного фонда Украины в один из четырех финансовых институтов: акции кампании г-на Сороса, в депозит Bank of America, в облигации госказначейства США и в золото. Эти четыре альтернативы (ваши возможные стратегии) обозначим А1, А2, А3, А4 .
Допустим, окружающая среда (В), в данном случае, ситуация на финансовом рынке на момент завершения депозита может принять одно из пяти определенных состояний. Эти пять состояний обозначим В1, В2, В3, В4, В5 .
Из многолетних статистических данных известны приближенные вероятности (Q) этих состояний: q1, q2, q3, q4, q5 .
Инвестиционная привлекательность проекта вложения средств определяется как конечная рентабельность. Оценка рентабельности считается известной для каждой стратегии инвестора и каждого состояния окружающей среды. Эти данные представлены в матрице, называемой матрицей выигрышей инвестора (игрока А),
где аij – это рентабельность инвестиционного проекта при выборе Аi-той альтернативы и при Вj-том состоянии окружающей среды.
От вас, как главы пенсионного фонда Украины, требуется выбрать наилучший вариант вложения средств налогоплательщиков.
Отметим, что понятие наилучшего исхода в различных условиях трактуется по-разному. Для различных условий принятия решений разработаны различные критерии выбора ЛПР наилучшего исхода. Решим данную задачу с помощью различных критериев.
Критерий Байеса
Критерий Байеса (принцип математического ожидания) предполагает полное доверие ЛПР известным вероятностям состояний окружающей среды. Следовательно, данная задача – это задача принятия решения в условиях риска.
Показатель эффективности стратегии Аi по критерию Байеса находится по формуле:
Z = ,
гдеm – количество строк матрицы, заданной в условии;
n – количество столбцов матрицы, заданной в условии;
qj – заданные вероятности ;
аij – элементы матрицы, заданной в условии.
Для случая оптимизации потерь критерий будет таким:
Z = #
Заметим, что – это математическое ожидание стратегии Аi . Таким образом, исходную матрицу необходимо дополнить справа еще одним столбцом, в который нужно внести значения математических ожиданий всех стратегий:
Пример вычислений для первой строки:
= 0,33 + 0,27 + ,153 + ,115 + ,256 = ,6 + 1,4 + ,45 + 1,5 + 1,5 = 5,75
Далее в добавленном столбце нужно найти наибольший элемент (наибольшее математическое ожидание). Строка, в которой он стоит и будет оптимальной стратегией. Необходимо заметить, что наибольших элементов может быть несколько, тогда и оптимальных стратегий соответственно будет несколько.
В нашем случае наибольший элемент 5,95 (в матрице он выделен). Таким образом, в нашем примере оптимальной стратегией будет А3, т.е. средства фонда вам нужно вложить в третий проект.
Ответ А3 .
Критерий Лапласа (Бернулли)
Критерий Лапласа (принцип недостаточного основания) предполагает недоверие ЛПР известным вероятностям состояний окружающей среды. Вероятности состояний окружающей среды считаются одинаковыми и равными . Следовательно, данная задача – это задача принятия решения в условиях риска с вероятностями .
Показатель эффективности стратегии Аi по критерию Лапласа находится аналогично критерию Байеса с вероятностями :
Z = = ,
Заметим, что нет необходимости вычислять эти математические ожидания. Достаточно просто просуммировать элементы строк матрицы и выбрать из них максимальную сумму:
Z =
Для случая оптимизации потерь критерий будет таким:
Z = #
Таким образом, исходную матрицу необходимо дополнить справа еще одним столбцом, в который нужно внести значения сумм элементов строк всех стратегий:
Далее в добавленном столбце нужно найти наибольший элемент. Строка, в которой он стоит и будет оптимальной стратегией. Необходимо заметить, что наибольших элементов может быть несколько, тогда и оптимальных стратегий соответственно будет несколько.
В нашем случае наибольший элемент в добавленном столбце 34 (в матрице он выделен). Таким образом, в нашем примере оптимальной стратегией будет А1 , т.е. инвестор должен выбрать для вложения первый проект.
Ответ А1 .
Критерий Гермейера
Критерий Гермейера применяется для задач принятия решений в условиях риска.
Он применяется в основном для решения задач выбора для оптимизации величины потерь или затрат. Такие задачи довольно часто встречаются в хозяйственной практике. Матрица потерь, задаваемая в условии, будет содержать отрицательные элементы (потери выражаются отрицательными величинами). Если в матрице помимо отрицательных будут и положительные элементы, то исходная матрица потерь преобразуется в матрицу, содержащую только отрицательные элементы по правилу:
аij – с ,
где с – некое выбранное ЛПР положительное число.
Следует иметь в виду, что оптимальное решение зависит от выбора с.
Критерий Гермейера применяется и для оптимизации величины прибыли (как в нашей задаче), т.е. для положительных матриц.
В общем случае Гермейер предложил ввести в рассмотрение матрицу с такими элементами:
Построим новую матрицу для нашего примера:
Далее к этой матрице применяется принцип максимина. Показатель эффективности стратегии Аi при этом находится по формуле:
Таким образом, новую матрицу необходимо дополнить справа еще одним столбцом, в который нужно внести наименьшие значения элементов каждой строки.
Затем из элементов добавленного столбца нужно выбрать наибольший. Строка, в которой он стоит и будет оптимальной стратегией.
В нашем случае наибольший элемент в добавленном столбце 16 (в матрице он выделен). Таким образом, в нашем примере оптимальной стратегией будет А3, т.е. инвестор должен выбрать для вложения третий проект.
Ответ А3 .
Критерий Ходжа-Лемана
Критерий Ходжа-Лемана привносит фактор определенной субъективности при принятии решения.
Решение принимается в условиях риска. Однако у ЛПР есть некое недоверие к распределению вероятностей состояний окружающей среды. Поэтому ЛПР вводит некий "коэффициент доверия" l к вероятностям состояний окружающей среды (0 £ l £ 1). Чтобы сильно не рисковать, обычно таким коэффициентом берут 0,4. Этот коэффициент ещё называют уровнем оптимизма.
Показатель эффективности стратегии Аi по критерию Ходжа-Лемана находится по формуле:
Z = ,
#Для случая оптимизации потерь критерий будет таким:
Z = #
Таким образом, исходную матрицу необходимо дополнить справа еще тремя столбцами. В первый нужно внести значения математических ожиданий всех стратегий, умноженных на уровень оптимизма l = 0,4. Во второй нужно внести значения наименьших элементов всех строк, умноженных на уровень пессимизма 1 – l = 1 – 0,4 = 0,6 . В третий добавленный столбец внесем сумму значений первых двух добавленных столбцов:
Пример вычислений для первой строки:
= 0,4 (,33 + 0,27 + ,153 + ,115 + ,256) = ,4 5,75 = 2,3
= 0,6 3 = 1,8
Z1 = 2,3 + 1,8 = 4,1
Далее в добавленном столбце нужно найти наибольший элемент. Строка, в которой он стоит и будет оптимальной стратегией.
В нашем случае наибольший элемент 4,78 (в матрице он выделен). Таким образом, в нашем примере оптимальной стратегией будет А3, т.е. инвестор для вложения должен выбрать третий проект.
Ответ А3 .
Дата: 2019-07-31, просмотров: 180.
