Часть 1. Принятие решения в условиях определенности

Петров П.Е.

Теория принятия решений

Лабораторные работы

Методические указания

Ухта 2006

УДК 519.816

С 30

Семериков, А.В. Теория принятия решений. Лабораторные работы [Текст]: метод. указания/ А.В.Семериков, Е.С. Буханец. – Ухта: УГТУ, 2006. – 49 с.

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

Содержания указаний соответствует рабочей учебной программе.

Методические указания рассмотрены и одобрены кафедрой ИСТ пр. № 3 от 10.11.06 г. и предложены для издания Советом специальности 230201 от 11.11.06 г. пр. № 2.

Рецензент доцент, кандидат технических наук Н.А. Николаева.

Редактор Т.Ю. Калинина

План 2006 г., позиция 45.

Подписано в печать 28.11.2006 г. Компьютерный набор.

Объем 49 с. Тираж 50 экз. Заказ № 205.

169300, г. Ухта, ул. Первомайская, 13.

Отдел оперативной полиграфии УГТУ

169300, г. Ухта, ул. Октябрьская, 13.

Оглавление

Оглавление. 3

Ключевые слова. 4

Основные понятия. 4

Часть 1. Принятие решения в условиях определенности. 5

Метод анализа иерархий. 5

1.1 Постановка задачи. 5

1.2 Описание алгоритма решения задачи. 5

1.3 Пример решения задачи. 8

Часть 2. Принятие решения в условиях неопределенности. 17

2.1 Постановка задачи. 17

2.2 Описание алгоритма решения задачи. 17

2.3 Пример решения задачи. 19

Часть 3. Принятие решения в условиях риска. 22

3.1 Постановка задачи. 22

3.2 Описание алгоритма решения задачи. 22

3.3 Пример решения задачи. 22

Часть 4. Марковская задача принятия решений. 26

4.1 Постановка задачи. 26

4.2 Описание алгоритма решения задачи. 26

Модель динамического программирования с конечным числом этапов. 28

Модель динамического программирования с бесконечным числом этапов. 29

Метод полного перебора. 29

Метод итерации по стратегиям без дисконтирования. 30

4.3 Пример решения задачи для конечного числа этапов. 32

4.4 Пример решения задачи с бесконечным числом этапов методом полного перебора 35

4.5 Пример решения задачи с бесконечным числом этапов методом итерации по стратегиям без дисконтирования. 45

Заключение. 48

Литература. 49

Ключевые слова

Условия принятия решения, принятие решения в условиях определенности, принятие решения в условиях риска, принятие решения в условиях неопределенности, иерархии, метод анализа иерархий, относительные весовые коэффициенты, альтернативы, критерии, согласованные матрицы сравнений, коэффициент согласованности.

Состояния природы, критерий Лапласа, минимаксный (максиминный) критерий, критерий Сэвиджа, критерий Гурвица, показатель оптимизма критерия ожидаемого значения, апостериорные вероятности (Байесовские), априорные вероятности.

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

Основные понятия

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

1) принятие решений в условиях определенности, когда данные известны точно;

2) принятие решений в условиях риска, когда данные можно описать с помощью вероятностных распределений;

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

По существу, в условиях определенности, данные надежно определены, в условиях неопределенности они не определены. Принятие решений в условиях риска, следовательно, представляет “промежуточный” случай.

Часть 1. Принятие решения в условиях определенности

Метод анализа иерархий

Постановка задачи

1. Сформулировать задачу принятия решения в условиях определенности с 2 иерархическими уровнями.

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

Пример решения задачи

Формулировка задачи:

Предприятию необходимо взять в аренду складские помещения для хранения своей продукции.Склад может быть расположен в одном из трех городов: D, B или C. Руководству предприятия, в составе: Петров П.Е., Иванов И.В. и Некрасова Н.Е., необходимо решить: в каком городе рациональнее расположить склад. Для анализа альтернатив руководство выделило три критерия, оказывающих наибольшее влияние на доходность предприятия: спрос на продукцию (С), наличие конкурентов (К) и стоимость аренды складских помещений (Ар) в каждом из городов. Основываясь на выдвинутых критериях, руководство должно отдать предпочтение определенному городу.

В каком городе выгоднее разместить склад, при условии, что мнения экспертов равнозначны?

Решение:

1. Матрицы парных сравнений критериев:

Петров П.Е.

Иванов И.В.

Некрасов Н.Е.

Ар

0, 2

0, 5

0, 25

0, 5

Ар

0, 25

Ар

0, 333

Ар

0, 2

0, 25

2. Для определения относительных весов критериев «С», «К» и «Ар» нормализуем полученные матрицы сравнения и найдем средние значения элементов соответствующих строк нормализованной матрицы.

Аналогично получаем весовые коэффициенты критериев для других экспертов:

Иванов И.В.		Некрасов Н.Е.
		С	К	Ар	w_i			С	К	Ар	w_i
N_D=	С	0, 632	0, 667	0, 6	0, 633	N_D=	С	0, 588	0, 615	0, 5	0, 568
К	0, 158	0, 167	0, 2	0, 175	К	0, 294	0, 308	0, 4	0, 334
Ар	0, 211	0, 167	0, 2	0, 192	Ар	0, 118	0, 077	0, 1	0, 098

3. Проверим: является ли уровень несогласованности полученных матриц парных сравнений приемлемым.

Петров П.Е.
=				0, 681	=	2, 076
0, 2	0, 5	0, 118	0, 355
0, 25		0, 201	0, 607

Отсюда получаем:

n_max = 2, 076 + 0, 355 + 0, 607 = 3, 038

Следовательно, для n=3 имеем:

Так как CR< 0, 1, уровень несогласованности матрицы D является приемлемым.

Аналогично находим:

Иванов И.В.
=			0, 633	=	1, 909
0, 25	0, 175	0, 525
0, 333	0, 192	0, 578

Отсюда получаем:

n_max = 3, 013

Следовательно, для n=3 имеем:

Так как CR< 0, 1, уровень несогласованности матрицы D является приемлемым.

Некрасов Н.Е.
=				0, 568	=	1, 727
0, 5		0, 334	1, 011
0, 2	0, 25	0, 098	0, 295

Отсюда получаем:

n_max = 3, 033.

Следовательно, для n=3 имеем:

Так как CR< 0, 1, уровень несогласованности матрицы D является приемлемым.

В результате мы имеем весовые коэффициенты критериев для каждого эксперта, представленные в Таблица 1.

Таблица 1

	Петров П.Е.	Иванов И.В.	Некрасов Н.А.
С	0, 681	0, 633	0, 568
К	0, 118	0, 175	0, 334
Ар	0, 201	0, 192	0, 098

Произведем действия, аналогичные пп.1-3, для получения весов альтернативных решений (D, B и С).

1. Матрицы парных сравнений альтернатив в соответствии с каждым критерием.

Петров П.Е.

D_С=

D_К=

D_Ар=

0, 5

0, 25

0, 5

0, 333

0, 5

Иванов И.В.

D_С=

D_К=

D_Ар=

0, 25

0, 5

0, 333

0, 25

0, 5

0, 25

0, 5

Некрасов Н.Е.

D_С=

D_К=

D_Ар=

0, 5

0, 333

0, 5

0, 2

0, 25

2. Соответствующие нормализованные матрицы и весовые коэффициенты альтернатив:

Петров П.Е.
N_DC=		D	В	С	w_i
D	0, 4	0, 429	0, 333	0, 387
В	0, 4	0, 429	0, 5	0, 443
С	0, 2	0, 143	0, 167	0, 170
N_D_К=		D	В	С	w_i
D	0, 545	0, 571	0, 5	0, 539
В	0, 273	0, 286	0, 333	0, 297
С	0, 182	0, 143	0, 167	0, 164
N_D_Ар=		А	В	С	w_i
D	0, 286	0, 286	0, 286	0, 286
В	0, 143	0, 143	0, 143	0, 143
С	0, 571	0, 571	0, 571	0, 571

Иванов И.В.
N_DC=		D	В	С	w_i
D	0, 632	0, 571	0, 667	0, 623
В	0, 158	0, 143	0, 111	0, 137
С	0, 211	0, 286	0, 222	0, 239
N_D_К=		D	В	С	w_i
D	0, 632	0, 667	0, 571	0, 623
В	0, 211	0, 222	0, 286	0, 239
С	0, 158	0, 111	0, 143	0, 137
N_D_Ар=		D	В	С	w_i
D	0, 571	0, 6	0, 5	0, 571
В	0, 286	0, 3	0, 375	0, 286
С	0, 143	0, 1	0, 125	0, 143

Некрасов Н.Е.
N_DC=		D	В	С	w_i
D	0, 588	0, 625	0, 455	0, 556
В	0, 294	0, 313	0, 455	0, 354
С	0, 118	0, 063	0, 091	0, 090
N_D_К=		D	В	С	w_i
D	0, 632	0, 667	0, 571	0, 623
В	0, 211	0, 222	0, 286	0, 239
С	0, 158	0, 111	0, 143	0, 137
N_D_Ар=		D	В	С	w_i
D	0, 4	0, 4	0, 4	0, 4
В	0, 2	0, 2	0, 2	0, 2
С	0, 4	0, 4	0, 4	0, 4

3. Проверим согласованности матриц сравнений альтернатив.

Столбцы матрицы N_D_Ар (Петров П.Е.) и N_D_Ар(Некрасов Н.Е.) одинаковы. Это имеет место лишь в случае, когда лицо, принимающее решение, проявляет идеальную согласованность в определении элементов матрицы сравнений, т.е. матрица сравнений является согласованной.

Оценим уровень несогласованности остальных матриц сравнений.

Проверим согласованность матрицы сравнений альтернатив в рамках критерия «Спрос», составленную экспертом Петровым П.Е.

=				0, 387	=	1, 170
		0, 443	1, 340
	0, 333	0, 170	0, 511

Отсюда получаем: n_max = 3, 021

Следовательно, для n=3 имеем:

Так как CR< 0, 1, уровень несогласованности матрицы D_С является приемлемым.

Проверим согласованность матрицы сравнений альтернатив в рамках критерия «Конкуренция», составленную экспертом Петровым П.Е.

=				0, 539	=	1, 625
0, 5		0, 297	0, 894
0, 333	0, 5	0, 164	0, 492

Отсюда получаем: n_max = 3, 011

Следовательно, для n=3 имеем:

Так как CR< 0, 1, уровень несогласованности матрицы D_К является приемлемым.

Проверим согласованность матрицы сравнений альтернатив в рамках критерия «Спрос», составленную экспертом Ивановым И.В.

=				0, 623	=	1, 891
0, 25	0, 5	0, 137	0, 413
0, 3333		0, 239	0, 722

Отсюда получаем: n_max = 3, 025

Следовательно, для n=3 имеем:

Так как CR< 0, 1, уровень несогласованности матрицы D_С является приемлемым.

Проверим согласованность матрицы сравнений альтернатив в рамках критерия «Конкуренция», составленную экспертом Ивановым И.В.

=				0, 623	=	1, 891
0, 333		0, 239	0, 722
0, 25	0, 5	0, 137	0, 413

Отсюда получаем: n_max = 3, 025

Следовательно, для n=3 имеем:

Так как CR< 0, 1, уровень несогласованности матрицы D_К является приемлемым.

Проверим согласованность матрицы сравнений альтернатив в рамках критерия «Арендная плата», составленную экспертом Ивановым И.В.

=				0, 557	=	1, 688
0, 5		0, 320	0, 967
0, 25	0, 333	0, 123	0, 369

Отсюда получаем: n_max = 3, 023

Следовательно, для n=3 имеем:

Так как CR< 0, 1, уровень несогласованности матрицы D_Ар является приемлемым.

Проверим согласованность матрицы сравнений альтернатив в рамках критерия «Спрос», составленную экспертом Некрасовым И.В.

=				0, 090	=	1, 715
0, 5		0, 090	1, 083
0, 2	0, 2	0, 090	0, 272

Отсюда получаем: n_max = 3, 071

Следовательно, для n=3 имеем:

Так как CR< 0, 1, уровень несогласованности матрицы D_С является приемлемым.

Проверим согласованность матрицы сравнений альтернатив в рамках критерия «Конкуренция», составленную экспертом Некрасовым И.В.

=				0, 623	=	1, 891
0, 333		0, 239	0, 722
0, 25	0, 5	0, 137	0, 413

Отсюда получаем: n_max = 3, 025

Следовательно, для n=3 имеем:

Так как CR< 0, 1, уровень несогласованности матрицы D_К является приемлемым.

В результате мы имеем весовые коэффициенты альтернатив в соответствии с каждым критерием для каждого эксперта, которые представлены в Таблица 2.

Таблица 2

	Петров П.Е.	Иванов И.В.	Некрасов Н.А.
	С	К	Ар	С	К	Ар	С	К	Ар
D	0, 387	0, 539	0, 286	0, 623	0, 623	0, 557	0, 556	0, 623	0, 4
В	0, 443	0, 297	0, 143	0, 137	0, 239	0, 320	0, 354	0, 239	0, 2
С	0, 170	0, 164	0, 571	0, 239	0, 137	0, 123	0, 090	0, 137	0, 4

4. Полученные в результате расчетов данные (Таблица 1 и Таблица 2) для наглядности представим на дереве (Рис. 1).

Комбинированный вес W для каждого города определяется по единой схеме. Например, для города D можно записать:

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

W_D=	0, 519
W_B =	0, 285
W_C =	0, 195

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

Рис. 1

Постановка задачи

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

2. На основе данных задачи выбрать оптимальную альтернативу.

Пример решения задачи

Формулировка задачи:

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

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

Матрица затрат (в тыс. рублей) выглядит следующим образом:

	s1	s2	s3	s4
a1
a2
a3
a4

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

Решение:

Критерий Лапласа

При заданных вероятностях , ожидаемые значения затрат для различных возможных решений вычисляются следующим образом:


	← оптимум

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

Вывод: наименьший уровень расходов был получен при использовании альтернативы а2, организаторы решают построить санаторий на 200 отдыхающих.

Минимаксный критерий

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

s1 s2 s3 s4

a1

a2 ← минимакс

a3

a4

Вывод: наименьший уровень расходов получен при использовании а2 альтернативы, организаторы решают построить санаторий на 200 отдыхающих.

Критерий Сэвиджа

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

где минимальное значение элемента в столбце матрицы

	s1	s2	s3	s4
a1
a2
a3
a4

Матрица сожалений в данном случае имеет следующий вид:

	s1	s2	s3	s4	Максимум строк
a1						← минимакс
a2						← минимакс
a3
a4

Вывод: наименьший уровень расходов получен при использовании a1 или a2 альтернатив, организаторы могут выбрать любую из этих двух альтернатив.

Критерий Гурвица

Для отражения своего мнения по рассматриваемому процессу принятия решения примем показатель оптимизма (высказывается точка зрения направленная к оптимизму)

Оптимальное решение ищется из соотношения .

Тогда получаем:

	s1	s2	s3	s4
a1
a2
a3
a4

Вывод: наименьший уровень расходов получен при использовании a2 альтернативы, организаторы решают построить санаторий на 200 отдыхающих.

Постановка задачи

1. Сформулировать задачу принятия решения в риска с 3 альтернативами.

2. На основе данных задачи выбрать оптимальную альтернативу.

Пример решения задачи

Формулировка задачи:

На фондовой бирже можно вложить 300 тыс. рублей в три компании: «А», «В» и «С». Акции компаний:

«А» могут принести 65% прибыли в условиях повышения котировок, 20% в условиях постоянства котировок и 50% потерь в условиях понижения котировок.

«В» - 30% прибыли в условиях повышенных котировок, 20% в условиях постоянства котировок, 5% в условиях пониженных котировок.

«С» - 50% прибыли в условиях повышения котировок, 20% в условиях постоянных котировок, 30% потерь в условиях понижения котировок.

Аналитические публикации прогнозируют повышение котировок с вероятностью 45%, постоянство котировок – 25%, а понижение – 30%.

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

Так, при повышении котировок его мнение будет «за» с вероятностью 60%, при постоянстве - 25%, а при понижении – 30%.

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

Решение:

Введем следующие обозначения:

мнение «за»,

мнение «против».

Количество событий j , относящихся к мнению специалиста равно 2.

повышение котировок,

постоянство котировок,

понижение котировок.

Количество событий i, относящихся к состоянию котировок равно 3.

Мнение специалиста можно записать в виде вероятностных соотношений следующим образом:

С помощью полученной дополнительной информации задачу выбора решения можно сформулировать следующим образом:

если мнение специалиста «за», акции какой компании следует покупать?

если мнение специалиста «против», акции какой компании следует покупать?

Рассмотренную задачу можно представить в виде дерева решений, представленного на Рис.2. Узлу 1 здесь соответствует случайное событие, мнение специалиста, с соответствующими вероятностями «за» и «против». Узлы 2 и 3 представляют выбор между компаниями А, В и С при известном мнении эксперта «за» или «против» соответственно. Узлы 4 – 9 соответствуют случайным событиям, связанным с состоянием котировок.

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

Шаг 1.

Условные вероятности для данной задачи запишем следующим образом.

		ν ₁	ν ₂
	m₁	0, 6	0, 4
m₂	0, 25	0, 75
m₃	0, 3	0, 7

Шаг №2.

Вычисляем вероятности совместного появления событий m и v.

для всех i и j. В результате получаем:

		ν ₁	ν ₂
	m₁	0, 27	0, 18
m₂	0, 0625	0, 1875
m₃	0, 09	0, 21

Шаг №3.

Вычисляем абсолютные вероятности появления события v.

ν ₁	ν ₂
0, 4225	0, 5775

Шаг №4.

Определяем искомые апостериорные вероятности по формуле

		ν ₁	ν ₂
	m₁	0, 639	0, 312
m₂	0, 148	0, 325
m₃	0, 213	0, 364

Эти вероятности отличаются от исходных априорных вероятностей.

Теперь можно оценить альтернативные решения, основанные на ожидаемых платежах для узлов 4 – 9.

Рис. 2

Мнение “ЗА”:

Доход от акций компании А

в узле 4=195000· 0, 639+60000· 0, 148-150000· 0, 213 = 101538, 5.

Доход от акций компании В

в узле 5= 90000· 0, 639+60000· 0, 148+15000· 0, 213 = 69585, 8.

Доход от акций компании C

в узле 6= 150000· 0, 639+60000· 0, 148-90000· 0, 213 = 85562, 13.

Решение. Инвестировать в акции компании А.

Мнение “ПРОТИВ”:

Доход от акций компании А

в узле 7= 195000· 0, 312+60000· 0, 325-150000· 0, 364 = 25714, 29.

Доход от акций компании В

в узле 8= 90000· 0, 312+60000· 0, 325+15000· 0, 364 = 52987, 01.

Доход от акций компании C

в узле 9= 150000· 0, 312+60000· 0, 325-90000· 0, 364 = 33506, 49.

Решение. Инвестировать в акции компании В.

Постановка задачи

1. Сформулировать задачу принятия решения в условиях риска с тремя альтернативами.

2. На основе данных задачи выбрать оптимальную альтернативу.

Метод полного перебора

Предположим, что в задаче принятия решений имеется S стационарных стратегий. Пусть P^S и R^S - матрицы переходных (одношаговых) вероятностей и доходов, соответствующие применяемой стратегии, s=1, 2, …, S. Метод перебора включает четыре шага:

Шаг 1. Вычисляем - ожидаемый доход, получаемый за один этап при стратегии s для заданного состояния i, i = 1, 2, …, m.

Шаг 2. Вычисляем - долгосрочные стационарные вероятности матрицы переходных вероятностей P^S, соответствующие стратегии s. Эти вероятности (если они существуют) находятся из уравнений:

где

Шаг 3. Вычисляем E ^S - ожидаемый доход за один шаг (этап) при выбранной стратегии s:

Шаг 4. Оптимальная стратегия s^* определяется из условия, что

Пример решения задачи для конечного числа этапов

Формулировка задачи:

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

1. 3% скидка при следующей покупке;

2. бесплатная доставка;

3. не предпринимать ничего.

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

1. отличный;

2. хороший;

3. удовлетворительный.

Известны переходные вероятности и соответствующие месячные доходы по каждому из трех вариантов:

12 3 4 5 6