ТПР ЛР1 Шакиров АР
.docxУФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
ФАКУЛЬТЕТ ИНФОРМАТИКИ И РОБОТОТЕХНИКИ
КАФЕДРА ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ
Отчёт по лабораторной работе №1
«Дискретные марковские процессы»
по предмету: «Теория принятия решений»
Выполнил:
студент группы МО-417
Шакиров А.Р.
Проверил:
доцент каф. ВМиК
Николаева М. А.
Уфа 2021
Цель работы: освоение способов принятия решений в условиях риска.
Цель работы
Целью работы является освоение способов принятия решений в условиях риска.
Задачи:
1. Изучение рекуррентного метода дискретных марковских процессов (ДМП).
2. Реализация алгоритма для решения конкретной задачи.
Постановка задачи
Дано:
N – число состояний системы (оно неизменно на каждом этапе);
k – номер стратегии;
n – количество этапов моделирования;
– вероятность перехода от одного состояния (i) к другому (j);
– доходность.
Обозначим: – ожидаемая доходность; – полная ожидаемая доходность на n-ом этапе моделирования.
Требуется найти: – номера оптимальных стратегий на каждом этапе процесса (n=1, 2, 3…) для каждого i-того состояния системы.
Пример
В качестве примера возьмем три состояния качества программного продукта:
содержащий критические ошибки, блокирующие выполнение бизнес-процессов (3),
содержащий ошибки, позволяющие выполнять бизнес-процессы незапланированным проектированием образом (2),
не содержащий ошибок вовсе или содержащий незначительные ошибки, не влияющие на бизнес-процессы (1).
В качестве стратегий возьмем:
А) На каждый функциональный участок программного продукта прикрепляются 2 специалиста по ручному тестированию и 1 специалиста по автотестированию. Функциональные участки объединяются в группы участков, ответственными за которые являются ведущие специалисты контроля качества.
Б) На каждый функциональный участок программного продукта прикрепляются специалисты по ручному тестированию, специалиста по автотестированию и старшего специалиста контроля качества в роли ответственного.
В) На каждый функциональный участок программного продукта прикрепляются по 2 специалиста по ручному тестированию и автотестированию. Функциональные участки объединяются в равные по размеру и сложности группы участков, ответственными за которые являются по 2 ведущих специалиста контроля качества.
Для каждой стратегии заполним матрицы вероятностей и доходности.
Таблица 1.1
Матрицы переходных вероятностей
А(1) |
1 |
2 |
3 |
Б(2) |
1 |
2 |
3 |
В(3) |
1 |
2 |
3 |
1 |
0,7 |
0,2 |
0,1 |
1 |
0,7 |
0,25 |
0,05 |
1 |
0,8 |
0,1 |
0,1 |
2 |
0,7 |
0,2 |
0,1 |
2 |
0,6 |
0,3 |
0,1 |
2 |
0,8 |
0,1 |
0,1 |
3 |
0,5 |
0,3 |
0,2 |
3 |
0,4 |
0,5 |
0,1 |
3 |
0,4 |
0,4 |
0,2 |
Таблица 1.2
Матрицы доходностей
А(1) |
1 |
2 |
3 |
Б(2) |
1 |
2 |
3 |
В(3) |
1 |
2 |
3 |
1 |
18 |
13 |
7 |
1 |
17 |
12 |
6 |
1 |
17 |
14 |
7 |
2 |
15 |
12 |
5 |
2 |
19 |
12 |
6 |
2 |
16 |
14 |
6 |
3 |
15 |
9 |
6 |
3 |
17 |
11 |
7 |
3 |
16 |
12 |
6 |
Решение
Рассмотрим первый этап моделирования (принятия решений).
Шаг 1.
Величина является ожидаемым доходом за один переход при выходе из состояния i и при выборе стратегии k. Таким образом:
Таблица 1.3
Результаты первого этапа моделирования
Стратегии |
Состояния |
Переходные вероятности |
Доходности |
Ожидаемые доходности |
|||||
1 |
2 |
3 |
1 |
2 |
3 |
||||
1 |
1 |
0,7 |
0,2 |
0,1 |
18 |
13 |
7 |
15,9 |
|
2 |
0,7 |
0,2 |
0,1 |
15 |
12 |
5 |
13,4 |
||
3 |
0,5 |
0,3 |
0,2 |
15 |
9 |
6 |
11,4 |
||
2 |
1 |
0,7 |
0,25 |
0,05 |
17 |
12 |
6 |
15,2 |
|
2 |
0,6 |
0,3 |
0,1 |
19 |
12 |
6 |
15,6 |
||
3 |
0,4 |
0,5 |
0,1 |
17 |
11 |
7 |
13 |
||
3 |
1 |
0,8 |
0,1 |
0,1 |
17 |
14 |
7 |
15,7 |
|
2 |
0,8 |
0,1 |
0,1 |
16 |
14 |
6 |
14,8 |
||
3 |
0,4 |
0,4 |
0,2 |
16 |
12 |
6 |
12,4 |
Оптимальным является такое поведение, которое максимизирует полный ожидаемый доход для всех состояний и шагов моделирования.
Шаг 2.
Полный ожидаемый доход вычисляется по следующей рекуррентной формуле:
Зададим
Вычислим полный ожидаемый доход для 1-ой стратегии на первом этапе моделирования:
Вычислим полный ожидаемый доход для 2-ой стратегии на первом этапе моделирования:
Вычислим полный ожидаемый доход для 3-ей стратегии на первом этапе моделирования:
Найдем максимальное значение полного ожидаемого дохода для каждого состояния для первого этапа моделирования:
Шаг 3.
Если система находится в (1) состоянии, то рекомендуется придерживаться 1-й стратегии. Эта стратегия принесет доход на 1-ом этапе моделирования в размере 15,9 у.е.
Если же система находится во (2) состоянии, то рекомендуется также придерживаться 2-й стратегии. Эта стратегия принесет доход на 1-ом этапе моделирования в размере у.е.
Если же система находится в (3) состоянии, то рекомендуется также придерживаться 2-й стратегии. Эта стратегия принесет доход на 1-ом этапе моделирования в размере 13 у.е.
Таким образом, d1(1) = 1, d2(1) = 2, d3(1) = 2.
Аналогичным образом вычисляются остальные этапы моделирования. Итоговые результаты представлены в таблице ниже.
Таблица 1.4
Итоговая таблица выбора стратегий
-
n
0
1
2
3
v1(n)
0
15,9
31,45
46,99
v 2(n)
0
15,6
31,12
46,65
v 3(n)
0
13
28,46
43,99
d1(n)
-
1
1
1
d2(n)
-
2
2
2
d3(n)
-
2
2
2
Руководство пользователя разработанного приложения
Для начала необходимо ввести число состояний, число стратегий и количество этапов моделирования системы и нажать кнопку «Создать таблицу» (рис. 1).
Рисунок 1
Далее необходимо заполнить матрицу переходных вероятностей и матрицу доходностей (рис. 2).
Рисунок 2
После необходимо нажать на кнопку «Вычислить» (рис. 3).
Рисунок 3
Далее происходит вывод таблицы ожидаемой доходности, итоговой таблицы с результатами вычислений и графа состояний. Граф состояний отображается для выбранной стратегии (рис. 4).
Рисунок 4
Вывод
В ходе лабораторной работы был изучен рекуррентный метод дискретных марковских процессов и реализован алгоритм для решения конкретной задачи.