Институт космических и информационных технологий
Институт космических и информационных технологий
Кафедра вычислительной техники
Г.А. Доррер
Методы и системы принятия решений
Лабораторный практикум для студентов
Направления 09.03.01 – Информатика и вычислительная техника всех форм обучения
Красноярск 2016
УДК 681.3.06
Доррер, Г.А. Методы и системы принятия решений. Лабораторный практикум для студентов направления 09.03.01 «Информатика и вычислительная техника» всех форм обучения / Красноярск: СФУ. – 2017. – 27с .
Пособие предназначено для студентов, обучающихся по направлениям подготовки бакалавров 09.03.01 «Информатика и вычислительная техника» при изучении дисциплины «Методы и системы принятия решений». Кроме того, оно может быть полезным студентам других направлений и специальностей при ознакомлении с основами системного анализа и теории принятия решений.
Приведен цикл из восьми лабораторных работ, рассчитанный на 36 часов работы при очном обучении и 11 часов – при заочном обучении, а также на соответствующий объем самостоятельной работы.
Тематика работ соответствует Государственному образовательному стандарту по направлению 09.03.01 « Информатика и вычислительная техника» 3+ поколения и рабочей программе дисциплины «Методы и системы принятия решений».
Первые работы посвящены освоению основных понятий и терминов системного анализа и теории принятия решений: лицо, принимающее решения, порядок подготовки решения (регламент), цели, ресурсы, риски и неопределенности, критерии оценки решения.
Рассмотрены так называемые «мягкие» модели и экспертные оценки при принятии решений в слабоструктурированных системах, при описании деятельности и ранжировании. решений. Кратко рассмотрены вопросы принятия решений, основанных на знаниях, в том числе Нейлоровский алгоритм.
Ряд работ посвящен изучению методов математического моделирования как способа формирования множества альтернатив решения. Рассмотрены следующие модели и методы: вероятностное моделирование динамики систем на основе цепей Маркова с дискретным временем, моделирование систем с помощью обыкновенных сетей Петри, моделирование систем с помощью GERT-сетей. Одна из работ посвящена созданию имитационных моделей систем с помощью пакета AnyLogic
В заключение лабораторного практикума студенты знакомятся с одной из крупных действующих систем поддержки принятия решений – Информационной системой дистанционного мониторинга лесных пожаров федерального агентства лесного хозяйства (ИСДМ – Рослесхоз)
©Доррер г.а. 2016
©СФУ, 2013
Оглавление
Введение. 4
Лабораторная работа № 1 Общие понятия системного анализа и теории принятия решений. 5
Лабораторная работа № 2 Принятие решений, основанное на знаниях. 7
Лабораторная работа № 3 Принятие решений на основе методов оптимизации 8
Лабораторная работа № 4 Вероятностное моделирование динамики систем на основе цепей Маркова с дискретным временем. 10
Лабораторная работа № 5 Моделирование систем с помощью обыкновенных сетей Петри. 14
Лабораторная работа № 6 Моделирование систем с помощью GERT-сетей. 17
Лабораторная работа №7 Имитационное моделирование систем с помощью пакета AnyLogic. 20
Лабораторная работа № 8 Знакомство с Информационной системой дистанционного мониторинга лесных пожаров федерального агентства лесного хозяйства (ИСДМ – Рослесхоз) 23
Библиографический список. 25
Введение
Процессы принятия решений лежат в основе любой целенаправленной деятельности – в технике, экономике, политике, социальной сфере, обеспечении безопасности.
Научным обслуживанием этих процессов, т.е. изучением и развитием методов принятия решений, первоначально занималась такая научная дисциплина, как «Исследование операций», вошедшая затем в направление, названное «Системным анализом». Исторически системный анализ представляет собой совокупность методов исследования систем, методик выработки и принятия решений при проектировании, конструировании и управлении сложными объектами различной природы.
Ключевая особенность системного анализа – учет системного эффекта, когда совокупность объектов, объединенных в систему, приводит к появлению новых свойств. При этом для понимания поведения системы необходимы теоретические знания различных дисциплин, а для исследования должны применяться не только формализованные методы, но и неформальные процедуры. Эта теория получила широкое распространение при решении проблем, возникающих в различных областях.
Математическим аппаратом дисциплины «Системный анализ» традиционно служат различные методы прикладной математики: прогнозирование, оптимизация, теория вероятностей и математическая статистика, теория массового обслуживания, структурный анализ и другие.
Со временем практика управления потребовала вовлечения в процесс принятия решений не только формальных методов, но и качественных, слабоструктурированных факторов. К последним относятся знания специалистов, которые сложно формализовать. Это, прежде всего, опыт, интуиция, приверженность к тем или иным взглядам лиц, принимающих решения. Отсюда появилось новое комплексное научное направление «Теория принятия решений» – ТПР, которое использует не только формальные методы дисциплин, входящих в направление системного анализа, но и методы экспертных оценок, так называемые «мягкое» моделирование ситуаций, достижения в области информационных технологий и искусственного интеллекта, в частности, продукционных систем. Для помощи персоналу, занятому подготовкой решений, созданы специализированные информационно-управляющие системы, называемые системами поддержки принятия решений – СППР.
Настоящее пособие ставит целью в процессе выполнения лабораторных работ ознакомить студентов с основными понятиями системного анализа и теории принятия решений, а также дает возможность освоить ряд наиболее известных методов формирования альтернатив решений и выбора из них наилучших.
Лабораторный практикум рассчитан на 18 часов аудиторных занятий и такой же объем самостоятельной работы при дневной форме обучения и на 11 часов при заочном обучении. Поэтому студенты дневной формы обучения должны выполнить все 8 работ, приведенных в пособии, а студенты-заочники выполняют работы № 1, 2, 4, 5.
Первые три работы выполняются бригадами из 3-4 студентов, остальнве работы – индивидуальные.
Содержание работы
Изучите по материалам учебного пособия, лекциям и другим источникам понятия и терминологию системного анализа и принятия решений и дайте ответы на следующие вопросы.
1. Что такое система? Дайте определение. Чем система отличается от совокупности различных элементов?
2. Как идентифицировать границу между системой и внешней средой? Является ли граница частью системы?
3. Приведите примеры проявления эмерджентности в системах.
4. Может ли социальная система состоять из одного человека или требуются как минимум двое?
5. Рассматривая процесс обучения в вузе как систему, выделите в нем и охарактеризуйте перечисленные выше термины: элемент, система, функция, структура, организация (функциональная и структурная), эффективность, обратная связь, показатель эффективности, критерий эффективности, анализ и синтез системы.
6. Обязательно ли система должна иметь цель?
7. По мнению некоторых ученых, социальной системой является любая группа, не обязательно состоящая из людей, например, рой пчел, стая птиц. Является ли в таком случае социальной системой сеть компьютеров?
8. Как происходит согласование решений на различных уровнях управления? Приведите примеры.
9. Кто определяет качество решения и успешность его выполнения? Обязано ли ЛПР участвовать в реализации решения?
10. Опишите процедуры принятия решения в одной из следующих систем:
- Государственная дума,
- министерство (ведомство),
- корпорация,
- предоставление кредита,
- планирование работы промышленного предприятия,
- управление проектами,
- ликвидация чрезвычайных ситуаций,
- военная операция.
11. Кто в перечисленных системах является ЛПР? Из кого состоит персонал, готовящий проект решения?
12. Опишите процедуры принятия решений, касающихся студентов, в Вашем учебном заведении: (альтернативы, критерии, ЛПР, персонал, и так далее) в соответствии со схемой на рисунке 1.1 пособия по следующим вопросам:
- зачисление в вуз,
- начисление стипендии,
- допуск к сессии,
- перевод на следующий курс,
- отчисление из вуза,
- присвоение квалификации.
Содержание отчета по работе
Отчет по лабораторной работе должен содержать:
· титульный лист с указанием фамилии студента;
· письменные ответы на предложенные выше вопросы.
Содержание работы
Изучите по материалам учебного пособия (глава 2), лекциям и другим источникам методы когнитивного моделирования, решения задач ранжирования решений, теорию продукционных моделей знаний и и проделайте следующую работу.
1. Составьте когнитивную карту какой-либо знакомой Вам деятельности, например, успехов в спорте, в учебе, в научной работе и др.
2. Выберите знакомую Вам область и проранжируйте входящие в нее объекты (например, марки автомобилей, футбольные команды, изучаемые Вами дисциплины и др.). Сравните ранжировки, полученные по методу средних арифметических и по методу медиан.
3. Для знакомой Вам области составьте продукционную систему, позволяющую выбрать одну из гипотез (например, Крис Нейлор иллюстрирует создание продукционной системы на примере выбора между птицей и самолетом), проиллюстрируйте работу системы..
4. Найдите в Интернете программу «Малая экспертная система». В базу знаний этой программы загрузите гипотезы и свидетельства из продукционной системы, составленной в пункте 3. Протестируйте полученную экспертную систему.
5. Предположим, Вы отправляетесь в поход и собираете рюкзак. Предельный вес рюкзака для юношей – 15 кг, для девушек – 10 кг. Составьте список возможных вещей и продуктов, их веса и цены, а затем решите задач об упаковке рюкзака с помощью описанного в пособии алгоритма. Дпалее предположим, что выбранные Вами вещи нужно нести в сумках весом не более 3 кг. Определите количество необходимых сумок и загрузку каждой из них.
Содержание отчета по работе
Отчет по лабораторной работе должен содержать:
· титульный лист с указанием номера группы и исполнителей;
· когнитивную карту выбранной деятельности,
· описание объектов выбранной области, таблица рангов и результаты ее обработки методом средних и методом медиан,
· описание продукционной системы, дерево принятия решений для детерминированного случая,
· список гипотез и свидетельств для байесовского подхода,
· протокол принятия решения с помощью программы «Малая экспертная система»
· список выбранных в поход вещей и результаты упаковки в рюкзаки для юношей и для девушек,
· распределение вещей по контейнерам (сумкам).
Содержание работы
Изучите по материалам учебного пособия, лекциям и другим источникам методы линейного программирования, решения задач многокритериальной оптимизации, смены оборудования и проделайте следующую работу.
1. Составьте на свой вкус суточное меню из 4–5 продуктов, исходя из следующих условий: суточная потребность человека в белках – 80 г, в жирах – 100г, углеводах – 360г. Общая калорийность меню для юношей 2700 ккал, для девушек – 2300 ккал. Сформулируйте и решите задачу линейного программирования для определения количества продуктов в двух вариантах:
а) Минимальная стоимость при балансе по белкам, жирам и углеводам и общей калорийности.
б) Минимальный вес продуктов при таком же балансе.
в) Сформулируйте двухкритериальную задачу на основе задач а) и б) и решите ее методом линейной свертки критериев, задавшись весом каждого из критериев.
Примечание Калорийность продуктов найдите в Интернете, а их стоимость – в ближайшем магазине. Для решения задачи используйте программу симплекс-метода, которую тоже можно найти в Интернете.
2. Определите для своего варианта оптимальный срок смены автомобиля по методике учебного пособия (п. 2.5.1) при следующих условиях (время рассчитывается в месяцах):
а) начальная цена автомобиля 
рублей,
б) потеря стоимости определяется формулой 
;
в) стоимость обслуживания возрастает по закону 
Исходные данные приведены в таблице 3.1.
Таблица 3.1
| № варианта |  тыс. руб. |  1/мес. |  1/мес. |
| 0,05 | 0,03 | ||
| 0,07 | 0,04 | ||
| 0,02 | 0,06 | ||
| 0,03 | 0,02 | ||
| 0,01 | 0,05 | ||
| 0,015 | 0,07 | ||
| 0,017 | 0,065 | ||
| 0,025 | 0,03 | ||
| 0,04 | 0,05 | ||
| 0,06 | 0,015 | ||
| 0,03 | 0,03 | ||
| 0,01 | 0,04 | ||
| 0,015 | 0,06 | ||
| 0,017 | 0,02 | ||
| 0,025 | 0,05 | ||
| 0,01 | 0,065 | ||
| 0,015 | 0,03 | ||
| 0,017 | 0,05 | ||
| 0,025 | 0,015 | ||
| 0,04 | 0,03 | ||
| 0,05 | 0,03 | ||
| 0,07 | 0,04 | ||
| 0,02 | 0,06 | ||
| 0,03 | 0,02 | ||
| 0,01 | 0,05 | ||
| 0,015 | 0,07 | ||
| 0,017 | 0,065 | ||
| 0,025 | 0,03 | ||
| 0,04 | 0,05 | ||
| 0,06 | 0,015 | ||
| г00 | 0,03 | 0,03 | |
| 0,01 | 0,04 | ||
| 0,015 | 0,06 | ||
| 0,017 | 0,02 | ||
| 0,025 | 0,05 |
Содержание отчета по работе
Отчет по лабораторной работе должен содержать:
· Титульный лист с указанием номера группы и исполнителей;
· Для задачи 1 выпишите переменные, ограничения и критерии оптимизации, а также полученные решения для каждого из варианта постановки.
· Для задачи 2 постройте график изменения удельной себестоимости 
и укажите время, когда эта функция достигает минимума.
Цели работы
1. Освоить основные положения теории конечных цепей Маркова (ЦМ) с дискретным временем.
2. Научиться составлять ЦМ для моделирования систем и анализа динамики их функционирования.
3. Научиться вычислять характеристики функционирования ЦМ.
Содержание работы
1) Изучить теоретический материал по ЦМ по учебному пособию
(глава 3), по лекциям или другим источникам.
2) Для заданного варианта модели системы составить матрицу переходных вероятностей.
3) Вычислить с помощью пакета MathCad или специально написанной программы векторы вероятностей X(t)пребывания системы в каждом из состояний для 15 шагов при старте из заданного входного состояния и построить соответствующие графики.
4) Структурировать матрицу 
, выделить множества невозвратных и эргодических состояний 
и 
. Выписать матрицы 
, 
, 
.
5) Определить среднее число тактов пребывания процесса в каждом из невозвратных состояний путем вычисления матрицы 
.
6) На основе матрицы 
вычислить среднюю трудоемкость процесса 
.
7) Оценить среднеквадратичное отклонение от среднего числа пребываний процесса в множестве невозвратных состояний 
, где 
и соответствующее среднеквадратичное отклонение трудоемкости от среднего 
.
8) Оценить предельные вероятности пребывания процесса в множестве эргодических состояний:
а) путем прямого возведения матрицы 
в высокую степень,
б) путем спектрального разложения матрицы.
Содержание отчета по работе
Отчет по лабораторной работе должен содержать:
· титульный лист с указанием исполнителя и номера варианта,
· исходные данные по ЦМ – граф смены состояний, матрицы переходных вероятностей ; , и вектор начальных условий X(0),
· таблицу векторов X(t), t=0,1,…15, полученных по формуле 
и графики 
, j=1,…n, t=0,…15;
· матрицу средних значений 
и оценку средней трудоемкости процесса ,
· матрицу дисперсий 
и оценку среднеквадратичного отклонения трудоемкости ,
· оценки предельных вероятностей пребывания процесса в состояниях эргодического множества, вычисленные:
а) путем прямого возведения матрицы в высокую степень,
б) путем спектрального разложения матрицы 
Исходные данные к работе
Исходные данные представлены в виде таблицы 4.1 и набора схем. По указанному преподавателем номеру варианта в таблице выбирается соответствующая строка. Второй столбец таблицы указывает код схемы и стартовое состояние (например, Г1 – схема Г, старт происходит из состояния S1). Далее указаны вероятности перехода между состояниями в десятых долях (т.е. указанное в таблице значение 
означает, что 
). Этими вероятностями помечены дуги на схеме. Некоторые дуги не помечены – соответствующие вероятности определяются из условия, что сумма вероятностей на дугах, отходящих от каждого узла, равна единице. Следующая группа столбцов задает трудоемкости отдельных процессов 
в секундах.
| Таблица 4.1 | mмах 1/с | 0.1 | 1.2 | 0.2 | 0.5 | 1.2 | 2.5 | 10.5 | |||||||||||||
| Трудоемкости, С, c | С7 | - | - | - | - | - | - | - | - | - | - | - | - | ||||||||
| С6 | |||||||||||||||||||||
| С5 | |||||||||||||||||||||
| С4 | |||||||||||||||||||||
| С3 | |||||||||||||||||||||
| С2 | |||||||||||||||||||||
| С1 | |||||||||||||||||||||
| Вероятности переходаРk´10 | Р10 | - | - | - | - | - | - | - | - | ||||||||||||
| Р9 | |||||||||||||||||||||
| Р8 | |||||||||||||||||||||
| Р7 | |||||||||||||||||||||
| Р6 | |||||||||||||||||||||
| Р5 | |||||||||||||||||||||
| Р4 | |||||||||||||||||||||
| Р3 | |||||||||||||||||||||
| Р2 | |||||||||||||||||||||
| Р1 | |||||||||||||||||||||
| Схема, вход | A1 | А2 | Б1 | Б2 | В1 | В2 | Г1 | Г2 | Д1 | Д2 | А1 | А2 | Б1 | Б2 | В1 | В2 | Г1 | Г2 | Д1 | Д2 | |
| № вар. |
| Таблица 4.1(продолжение) | mмах 1/с | 0.1 | 1.2 | 0.2 | ||||||||||||
| Трудоемкости, С, c | С7 | - | - | - | - | - | - | - | - | |||||||
| С6 | ||||||||||||||||
| С5 | ||||||||||||||||
| С4 | ||||||||||||||||
| С3 | ||||||||||||||||
| С2 | ||||||||||||||||
| С1 | ||||||||||||||||
| Вероятности переходаРk´10 | Р10 | - | - | - | - | |||||||||||
| Р9 | ||||||||||||||||
| Р8 | ||||||||||||||||
| Р7 | ||||||||||||||||
| Р6 | ||||||||||||||||
| Р5 | ||||||||||||||||
| Р4 | ||||||||||||||||
| Р3 | ||||||||||||||||
| Р2 | ||||||||||||||||
| Р1 | ||||||||||||||||
| Схема, вход | A1 | А2 | Б1 | Б2 | В1 | В2 | Г1 | Г2 | Д1 | Д2 | А1 | А2 | Б1 | Б2 | В1 | |
| № вар. |
Цели работы
1. Освоить основные формализмы обыкновенных сетей Петри (PN)
2. Научиться составлять формальное описание PN.
3. Разработать программу моделирования динамики маркировок и составления слов свободного языка обыкновенных сетей Петри.
4. Провести исследования заданной сети с помощью разработанной программы.
Содержание работы
1. Изучить теоретический материал по пособию (глава 5), лекциям или другим источникам.
2. Составить программу, моделирующую изменение маркировок и построение свободного языка обыкновенной сети Петри.
3. Для заданного варианта задания:
1) Составить список позиций и переходов, матрицы инцидентности F(p,t) и F(t,p) и начальную маркировку для указанного варианта схемы СП.
2) Для начальной маркировки PN, указанной в таблице, составить дерево разметок на глубину до 5 шагов или до общего числа маркировок, равного 100. При обнаружении повторяющихся маркировок они помечаются значками Mpi, где i - номер обнаруженной повторяющейся маркировки, а построение дерева продолжается только из одной из них. Циклические маркировки, т.е. повторяющиеся на одном пути в дереве, обозначаются Mci. Тупиковые маркировки обозначаются Mti.
3) Выписать все полученные слова свободного языка PN, начиная с пустого слова. Аналогично п.2 указать повторения, циклы и тупики.
4) Оценить свойства PN: ограниченность, консервативность, безопасность, живость.
Оформление работы
Оформленный отчет по лабораторной работе должен содержать:
- титульный лист с указанием группы, фамилии исполнителя и номера варианта;
- исходную схему с начальной маркировкой;
- матрицы инцидентности;
- дерево маркировок;
- словарь свободного языка PN;
- анализ свойств рассматриваемой PN;
- листинг программы.
Таблица 5.1
| № вари-анта | № схемы | Начальная маркировка M0 | |||||
| m1 | m2 | m3 | m4 | m5 | m6 | ||
| А | |||||||
| Б | |||||||
| В | |||||||
| Г | |||||||
| Д | |||||||
| А | |||||||
| Б | |||||||
| В | |||||||
| Г | |||||||
| Д | |||||||
| А | |||||||
| Б | |||||||
| В | |||||||
| Г | |||||||
| Д | |||||||
| А | |||||||
| Б | |||||||
| В | |||||||
| Г | |||||||
| Д | |||||||
| А | |||||||
| Б | |||||||
| В | |||||||
| Г | |||||||
| Д | |||||||
| А | |||||||
| Б | |||||||
| В | |||||||
| Г | |||||||
| Д | |||||||
| А | |||||||
| Б | |||||||
| В | |||||||
| Г | |||||||
| Д |
Цели работы
1. Ознакомиться с методами исследования систем на основе формализмов GERT-сетей
2. Научиться составлять производящие M-функции и передаточные W-функции для GERT- сетей.
3. Освоить методику и составить программу для расчета первого и второго моментов распределения выходной функции GERT –сети.
4. Провести исследования заданной сети с помощью разработанной программы
Содержание работы
1. Изучить теоретический материал по пособию (глава 5, п. 5.4), лекциям или по рекомендованной литературе.
2. Для заданного варианта задания в соответствии с таблицей 6.1 и схемами GERT-сетей для всех дуг GERT-сети составить выражения для 
- функций и 
- функций 
, где i – номер дуги.
3. Путем использования формул для типового соединения дуг написать выражение для передаточной функции всей сети, а затем – для производящей функции выходной величины GERT-сети.
4. Вычислить величины 
и 
аналитически или численно.
5. В случае использования численных методов воспользоваться формулами (5.42) из учебного пособия.
Таблица 6.1
| № вар | № схем |  |  |  |  |  | |||||||||||||
  | ТР | Параметр |  | ТР | Параметр | Параметр |  | ТР | Параметр | Параметр |  | ТР | Параметр | Параметр |  | ТР | Параметр | ||
| А | С | 0,2 | N | 0,5 | 0,2 | U | B | 0,3 | 0,8 | C | |||||||||
| Б | C | 0,4 | N | 1,5 | 0,4 | 0,7 | B | 0,3 | N | 0,2 | C | ||||||||
| В | C | 0,3 | N | 1,2 | 0,5 | 0,7 | N | B | 0,3 | C | |||||||||
| Г | C | U | 0,2 | N | 0,5 | N | 0,5 | 0,8 | C | 0,9 | |||||||||
| Д | 0,6 | C | 0,4 | N | 0,4 | U | 1,4 | 0,4 | N | 0,3 | 0,6 | C | 0,5 | ||||||
| А | С | 0,5 | 0,1 | B | 0,1 | 0,2 | N | 0,8 | 0,4 | U | 1,5 | 0,9 | C | ||||||
| Б | C | 0,3 | 0,2 | N | 1,5 | 0,5 | 0,8 | B | 0,2 | U | C | 0,5 | |||||||
| В | C | 0,1 | 0,6 | U | 0,4 | N | 0,5 | 0,1 | U | 0,5 | C | 0,5 | |||||||
| Г | C | 0,1 | U | 0,5 | 0,1 | N | 0,5 | B | 0,5 | 0,9 | C | 1,2 | |||||||
| Д | 0,5 | C | 0,5 | B | 0,5 | N | 0,1 | 0,9 | N | 0,3 | 0,1 | C | |||||||
| А | С | 0,3 | N | 1,5 | 0,2 | B | 0,5 | U | 0,7 | C | |||||||||
| Б | C | 0,5 | N | 2,5 | 0,4 | 0,5 | N | 0,3 | B | 0,2 | C | ||||||||
| В | C | 0,7 | N | 0,2 | 0,3 | U | N | 0,3 | C | ||||||||||
| Г | C | 0,2 | N | 0,1 | 0,3 | B | 0,2 | U | 0,7 | C | 0,5 | ||||||||
| Д | 0,3 | C | 0,7 | U | N | 0,4 | 0,4 | B | 0,3 | 0,6 | C | 0,5 | |||||||
| А | С | 0,1 | 0,1 | N | 0,5 | 0,2 | U | B | 0,3 | 0,9 | C | 0,2 | |||||||
| Б | C | 0,2 | N | 0,5 | 0,4 | 0,8 | B | 0,3 | U | C | 0,5 | ||||||||
| В | C | 0,5 | N | 1,5 | 0,5 | U | B | 0,5 | C | Наши рекомендации |