Г.А. Доррер
ТЕОРИЯ ПРИНЯТИЯ РЕШЕНИЙ
Учебное пособие
Красноярск 2013
Стр.1
2
ФГАОУ ВПО «Сибирский федеральный университет»
Г.А. Доррер
ТЕОРИЯ ПРИНЯТИЯ РЕШЕНИЙ
Учебное пособие для студентов направления
230100.62 – Информатика и вычислительная техника
Красноярск 2013
Стр.2
3
УДК 681.3.06
Доррер Г.А. Теория принятия решений: Учебное пособие для студентов
направления 230100.62 – Информатика и вычислительная техника,
Красноярск: ФГАОУ ВПО «Сибирский федеральный университет», 2013. – 180
с.
Учебное пособие предназначено для студентов, обучающихся по
направлениям подготовки бакалавров 230100.62. Кроме того, оно может быть
полезным студентам других направлений и специальностей при ознакомлении с
основами теории принятия решений.
Приводятся основные понятия и термины системного анализа и теории
принятия решений: лицо, принимающее решения, порядок подготовки решения
(регламент), цели, ресурсы, риски и неопределенности, критерии оценки
решения. Отмечается роль математического моделирования как способа
формирования множества альтернатив решения, дается классификация
используемых при этом математических моделей.
Показана роль так называемых «мягких» моделей и экспертных оценок
при принятии решений в слабоструктурированных системах.
Приводятся примеры выбора оптимальных решений на основе
линейного программирования, многокритериальной
формализмов
оптимизации, задач раскроя-упаковки и задач о замене оборудования.
В классе вероятностных моделей рассмотрены цепи Маркова с
дискретным временем, приведены примеры их использования при решении
различных задач. Приведена задача Г. Марковица выбора эффективного
инвестиционного портфеля.
Описаны возможности системы имитационного моделирования AnyLogic
и приведены примеры ее использования.
Рассмотрена теория обыкновенных и раскрашенных сетей Петри,
приведены примеры их применение для моделирования систем.
Приводятся краткие сведения о методологии решения задач
моделирования и принятия решений на основе формализма GERT-сетей.
В качестве примеров действующих систем поддержки принятия решений
описаны две системы, актуальные для Сибирского региона: экспертная система
по ликвидации аварий ЭСПЛА и система космического мониторинга состояния
лесов ИСДМ-Рослесхоз.
Рецензент: д.т.н. проф. М.Н. Фаворская (СибГАУ им.М.Ф. Решетнева)
© Доррер Г.А. 2012
© ГБОУ ВПО «СибГТУ», 2012
Стр.3
4
Оглавление
Предисловие ........................................................................................................................... 6
Введение ................................................................................................................................. 7
Глава 1 Общие сведения о теории принятия решений .................................................... 12
1.1 Понятия, связанные с принятием решений ............................................................. 12
1.2 Определенность результатов принимаемых решений ........................................... 14
1.3 Критерии оценки решения ........................................................................................ 15
1.4 Системы поддержки принятия решения .................................................................. 17
1.5 Математическое моделирование при принятии решений ..................................... 19
1.6 Классификация математических моделей структурированных систем ............... 25
1.7 Задачи моделирования на различных уровнях принятия решений ...................... 27
Глава 2 Детерминированные модели формирования и выбора альтернатив
решений ................................................................................................................ 30
2.1 О методологии «мягкого» моделирования .............................................................. 30
2.1.1 Когнитивные карты .............................................................................................. 32
2.1.2 Онтологические модели процесса принятия решений ..................................... 35
2.2 Методы экспертных оценок ...................................................................................... 39
2.2.1 Экспертный подход к принятию решений ........................................................ 39
2.2.2 Методы средних баллов ...................................................................................... 42
2.3 Методы оптимизации в задачах принятия решений............................................... 45
2.3.1 Принятие решений на основе методов линейного программирования .......... 45
2.3.2 Математическая модель планирования производства ..................................... 47
2.3.3 Задачи оптимального планирования производства .......................................... 49
2.3.4 Транспортная задача ............................................................................................ 54
2.4 Задачи об упаковке ..................................................................................................... 56
2.4.1 Задача о рюкзаке .................................................................................................. 56
2.4.2 Задачи упаковки в контейнеры ........................................................................... 58
2.5 Задачи о замене оборудования .................................................................................. 59
2.5.1 Простейшая задача о замене оборудования ...................................................... 59
2.5.2 Задача об оптимальных сроках змены дискового оборудования .................... 60
2.6 Многокритериальные задачи принятия решений ................................................... 63
Глава 3 Вероятностные модели формирования и выбора альтернатив решений ......... 70
3.1 Моделирование систем на основе формализма цепей Маркова ........................... 70
3.1.1 Определение и динамика цепи Маркова ........................................................... 70
3.1.2 Оценка длительности пребывания процесса в множестве
невозвратных состояний ....................................................................................... 73
3.1.3 Оценка поведения цепей Маркова при большом чсисле шагов ...................... 75
3.2 Модель процесса обучения как цепь Маркова ........................................................ 78
3.3 Система обслуживания заявок с очередью и отказами .......................................... 81
3.4 Модель динамики информационных ресурсов ....................................................... 83
3.5 Принятие решений об оптимизации инвестиционного портфеля ........................ 88
3.6 Имитационное моделирование при принятии решений ........................................ 92
3.6.1 Система AnyLogic: активные объекты, классы и экземпляры
активных объектов ................................................................................................ 93
3.6.2 Объектно-ориентированный подход .................................................................. 93
3.6.3 Средства описания поведения объектов ............................................................ 94
3.6.4 Анимация поведения и интерактивный анализ модели ................................... 95
3.6.5 Примеры имитационного моделирования ......................................................... 96
Стр.4
5
Глава 4 Сетевые модели поддержки принятия решений .............................................. 101
4.1 Обыкновенные сети Петри ...................................................................................... 101
4.1.1 Формальное определение .................................................................................. 101
4.1.2 Графы сетей Петри ............................................................................................. 104
4.1.3 Пространство состояний сети Петри ............................................................... 105
4.1.4 Основные свойства сетей Петри ....................................................................... 107
4.1.5 Некоторые обобщения сетей Петри ................................................................. 108
4.2 Раскрашенные (цветные) сети Петри (CPN) ......................................................... 115
4.2.1 Мультимножества .............................................................................................. 115
4.2.2 Формальное определение CPN ......................................................................... 116
4.2.3 Функционирование CPN ................................................................................... 119
4.2.4 Расширения CPN ................................................................................................ 122
4.2.5 Сравнение формализмов обыкновенных и раскрашенных сетей
Петри ..................................................................................................................... 124
4.2.6 О моделирующих возможностях сетей Петри ................................................ 124
4.3 Моделирование дискретных систем ....................................................................... 125
4.3.1 Моделирование вычислительных систем ........................................................ 126
4.3.2 Моделирование программ ................................................................................. 134
4.3.3 Моделирование протоколов передачи данных ............................................... 137
4.3.4. Об исследовании сетей Петри с помощью ЭВМ ........................................... 141
4.4 ГЕРТ-сети .................................................................................................................. 143
4.4.1 Описание ГЕРТ-сети .......................................................................................... 143
4.4.2 Производящие функции ГЕРТ-сетей ............................................................... 145
4.4.3 Вычисление W-функций для типовых соединений дуг ................................. 147
4.4.4 Модель процесса интерактивного обучения как ГЕРТ- сеть ........................ 149
Глава 5 Примеры систем поддержки принятия решений ............................................. 155
5.1 Система ЭСПЛА ....................................................................................................... 155
5.1.1 Режимы функционирования системы .............................................................. 156
5.1.2 Принятие решений при техногенных авариях ................................................ 158
5.1.3 Использование информационных ресурсов .................................................... 160
5.2 Информационная система дистанционного мониторинга лесных пожаров
Федерального агентства лесного хозяйства РФ .................................................. 161
5.2.1 Общая характеристика системы ....................................................................... 161
5.2.2 Использование спутниковых данных .............................................................. 164
5.2.3 Центры приема и обработки спутниковых данных ........................................ 166
5.2.4 Информационные продукты, формируемые системой .................................. 168
5.2.5 Прогнозирование параметров лесных пожаров по данным ИСДМРослесхоз
.............................................................................................................. 172
Заключение ........................................................................................................................ 176
Библиографический список .............................................................................................. 177
Стр.5
6
Предисловие
Настоящее пособие написано на основе лекций, которые автор читал в
Институте космических и информационных технологий Сибирского
федерального университета.
В настоящее время теория принятия решений – актуальное направление
научных исследований и прикладных разработок, специфика которых зависит
от предметной области. Автор в рамках односеместрового курса основное
внимание уделил методам принятия решений в областях, связанных с
профилем подготовки бакалавров. Пособие ставит целью приобретение
студентами компетенций, предусмотренных ГОС ВПО 3-го поколения для
направления 23100.62, в частности, следующих.
ОК-10 Использование основных законов естественнонаучных дисциплин
в профессиональной деятельности, применение методов математического
анализа и моделирования, теоретического и экспериментального
исследования.
ПК-6 Обоснование принимаемых проектных решений, постановка и
проведение экспериментов по проверке их корректности и эффективности.
Кроме того, в работе учтены требования профессиональных стандартов в
области информационных технологий, разработанных в рамках Национальной
системы компетенций и квалификаций.
В работе помимо общих понятий теории принятия решений и
традиционных методов оптимизации более подробно рассмотрены два класса
моделей: модели, базирующиеся на формализме сетей Петри, и вероятностные
модели, основанные на теории конечных цепей Маркова. Приводится также
краткое изложение теории GERT-сетей, позволяющих определять
вероятностные характеристики сложных процессов.
Ограниченный объем книги не позволил рассмотреть ряд других методов,
используемых в задачах принятия решений, в частности, методы
искусственного интеллекта, нечеткой логики, нейронных сетей.
Изложение ведется по возможности неформально, на «инженерном»
уровне строгости и сопровождается численными примерами. В конце каждой
главы содержится набор вопросов, задач и упражнений для самостоятельной
работы. Кроме того, по материалам пособия предусмотрен цикл лабораторных
работ, который издается отдельно.
Автор благодарен коллегам по работе И.М. Горбаченко, А.А. Попову и
В.С. Коморовскому, чьи результаты частично использованы при написании
пособия, а также рецензентам: д.т.н. проф. М.Н. Фаворской (СибГАУ им. М.Ф.
Решетнева.
Стр.6
7
Введение
Процессы принятия решений лежат в основе любой целенаправленной
деятельности – в технике, экономике, политике, социальной сфере,
обеспечении безопасности.
Научным обслуживанием этих процессов, т.е. изучением и развитием
методов принятия решений, первоначально занималась такая научная
дисциплина, как «Исследование операций», вошедшая затем в направление,
названное «Системным анализом». Исторически системный анализ
представляет собой совокупность методов исследования систем, методик
выработки и принятия решений при проектировании, конструировании и
управлении сложными объектами различной природы.
Ключевая особенность системного анализа – учет системного эффекта,
когда совокупность объектов, объединенных в систему, приводит к появлению
новых свойств. При этом, для понимания поведения системы необходимы
теоретические знания различных дисциплин, а для исследования должны
применяться не только формализованные методы , но и неформальные
процедуры. Эта теория получила широкое распространение при решении
проблем, возникающих в различных областях. В качестве примера можно
привести список (далеко не полный) организационно-технических систем, где
методы системного анализа играют важную роль [2, 4, 23, 26, 35]:
прогнозирование процессов в различных областях,
управление финансами,
информационные технологии,
управление трудовыми ресурсами,
управление социальными системами.
планирование производства,
управление запасами,
управление процессами обучения,
транспортные системы,
военные системы,
управление чрезвычайными ситуациями,
электроэнергетические системы,
производственные и технологические процессы,
организация досуга (туризм, спорт, развлечения).
Математическим аппаратом дисциплины «Системный анализ»
традиционно служат различные методы прикладной математики:
прогнозирование, оптимизация, теория вероятностей и математическая
статистика, теория массового обслуживания, структурный анализ и другие.
Со временем практика управления потребовала вовлечения в процесс
принятия решений не только формальных методов, но и качественных,
слабоструктурированных факторов. К последним относятся знания
специалистов, которые невозможно формализовать. Это, прежде всего, опыт,
интуиция, приверженность к тем или иным взглядам лиц, принимающих
Стр.7
8
решения. Отсюда появилось новое комплексное научное направление «Теория
принятия решений» – ТПР, которое использует не только формальные методы
дисциплин, входящих в направление системного анализа, но и методы
экспертных оценок, так называемые «мягкое» моделирование ситуаций,
достижения в области информационных технологий и искусственного
интеллекта. В числе последних особенно важными являются интеллектуальные
системы, способные к воспроизведению таких антропоморфных (человеческих)
свойств, как опыт и интуиция, а также имитации убеждений, желаний,
замыслов и обязательств.
Для помощи персоналу, занятому подготовкой решений, созданы
специализированные информационно-управляющие системы, называемые
системами поддержки принятия решений – СППР.
Близкие по смыслу и назначению задачи решает теория управления, ведь
управление – это последовательность принимаемых решений. Однако
традиционно теория управления сосредотачивается на изучении методов
управления динамическими системами различной природы, информация о
которых имеет достаточно структурированный вид.
Терминология системного анализа
В качестве введения, необходимого для понимания дальнейшего материала,
мы рассмотрим важнейшие термины и понятия системного анализа [31].
Элемент – это минимальный неделимый объект. Элемент можно
использовать только как целое, поэтому недопустимо говорить о половине или
четверти элемента. Неделимость элемента — это, прежде всего, удобное
понятие, но не физическое свойство. Оперируя понятием «элемент»,
исследователь оставляет за собой право перейти на другой уровень
рассмотрения вопросов и говорить о том, из чего состоит элемент, а это
свидетельствует о физической разложимости последнего. Таким образом,
объекты называются элементами по соглашению, принимаемому с целью дать
ответ на определенные вопросы, стоящие перед исследователями. Изменение
вопросов может потребовать разложения элементов на составные части или
объединения нескольких элементов в один.
Система – это совокупность связанных элементов, объединенных в одно
целое для достижения определенной цели. Здесь под целью понимается
совокупность результатов, определяемых назначением системы. Наличие цели
и заставляет связывать элементы в систему. Целостность — наиболее важное
свойство системы. Элемент принадлежит системе потому, что он связан с
другими ее элементами, так что множество элементов, составляющих систему,
невозможно разбить на два и более несвязанных подмножества. Удаление из
системы элемента или совокупности элементов непременно изменяет ее
свойства в направлении, отличном от цели.
Искусственные (инженерные) системы описывают путем определения их
функций и структур.
Функция системы – это правило получения результатов, предписанных
целью (назначением) системы. Определяя функцию системы, ее поведение
описывают с использованием некоторой системы понятий — отношений между
Стр.8
9
переменными, векторами, множествами и т.п. Функция устанавливает, что
делает система для достижения поставленной цели безотносительно к
физическим средствам (элементам, связям), составляющим саму систему, и не
определяет, как устроена система. Системы изучают на разных уровнях
абстракции, с использованием различных подходов, каждый из которых дает
ответ на определенные вопросы. В связи с этим функции системы могут
описываться с разной степенью детализации. Для описания функций систем
используются различные теории: теория множеств, теория алгоритмов, теория
случайных процессов, теория информации и другие. Функционировать –
значит реализовать функцию, т.е. получать результаты, предписанные
назначением системы.
Обратная связь – воздействие результатов функционирования системы
на характер этого функционирования. Различают положительную и
отрицательную обратную связь.
Структура системы – это фиксированная совокупность элементов и
связей между ними. В общей теории систем под структурой принято понимать
только множество связей между элементами, т. е. структура понимается как
картина, отображающая только конфигурацию системы безотносительно к
составляющим ее элементам. Такое толкование ее понятия удобно при
структурном подходе к изучению свойств различных систем — систем с
параллельными, последовательными, иерархическими структурами, обратными
связями и т. п. На практике в понятие «структура» включают не только
множество связей, но и множество элементов, между которыми существуют
связи. Этот смысл отражен в данном определении структуры. Наиболее часто
структура системы изображается в форме графа: элементы системы
представляются вершинами графа, а связи – дугами (ребрами) графа. Граф – это
математическая форма отображения структур. Инженерной формой
изображения структур систем являются схемы. Схема и граф – понятия
адекватные по содержанию, но различные по форме. В схемах элементы и связи
обозначаются любыми фигурами, удобными для инженерных
(производственных) применений.
Организация – это способ реализации определенных функций в системах,
состоящих из большого числа элементов. Обычно к одной и той же цели
можно, прийти различными способами, исходя из различных принципов
организации систем. Каждый принцип организации задает определенный
способ построения множества систем, аналогичных по назначению, но
различных по функциям и структурам. Конкретная система представляет собой
лишь пример реализации некоторого способа организации. Например,
подавляющее большинство современных ЭВМ строится на основе одного
принципа организации – принципа программного управления реализацией
алгоритма на основе команд, имеющих операционно-адресную структуру.
Таким образом, организация – понятие более высокого ранга, чем функция и
структура; организация – это модель, на основе которой могут строиться
многие конкретные системы.
Стр.9
10
Если речь идет о способе порождения функций, достаточных для
достижения определенной цели (определенных результатов), то используется
термин функциональная организация. Если же речь идет о наборе элементов и
способе их соединения в структуру, обеспечивающую реализацию функций
определенного класса, то используется термин структурная организация.
Определяя некоторый способ функциональной организации, выявляют класс
функций, присущих системам определенного назначения (безотносительно к
средствам, необходимым для реализации этих функций), а, определяя способ
структурной организации, выявляют правило построения структур, реализующих
некоторый класс функций, т.е. отвечающих некоторому назначению.
Целостность системы – ее относительная независимость от среды и
других аналогичных систем.
Эмерджентность – свойство несводимости системы к свойствам
элементов системы. Это означает, что элементы, соединенные в систему,
приобретают новые свойства.
Анализ – это процесс определения свойств, присущих системе. Типичная
задача анализа состоит в следующем. Известны функции и характеристики
элементов, входящих в состав системы, и определена структура системы.
Необходимо определить функции или характеристики, присущие совокупности
элементов в целом.
Синтез – это процесс порождения функций и структур, необходимых и
достаточных для получения определенных результатов. Выявляя функции,
реализуемые системой, определяют некоторую абстрактную систему, о которой
известно только то, что она будет делать. В связи с этим этап синтеза функций
называется абстрактным синтезом, а этап порождения структуры,
реализующей заданные функции, — структурным синтезом.
Эффективность – это степень соответствия системы своему
назначению. Из двух систем более эффективной считается та, которая лучше
соответствует своему назначению. Оценка эффективности системы — одна из
задач анализа систем.
Показатель эффективности (качества) – это мера одного свойства
(характеристики) системы. Показатель эффективности всегда имеет
количественный смысл, т. е. является измерением некоторого свойства. По этой
причине использование некоторого показателя эффективности предполагает
наличие способа измерения (оценки) значения этого показателя. Для оценок
эффективности систем могут применяться, например, такие показатели, как
производительность, стоимость, надежность, габариты и т. п.
Критерий эффективности – это мера эффективности системы.
Критерий эффективности имеет количественный смысл и измеряет степень
эффективности системы, обобщая все ее свойства в одной оценке — значении
критерия эффективности. Эффективность систем, создаваемых для одной цели,
оценивается на основе одного критерия, общего для этого класса систем.
Различие в назначениях систем предполагает, что для оценки эффективности
таких систем используются различные критерии. Если при увеличении
эффективности значение критерия возрастает, то критерий называется прямым;
Стр.10