Выработка решений в условиях определенности

Глава 3. Линейное и целочисленное программирование............... 41

3.1. Линейное программирование...................................................... 41

3.1.1. Постановка задачи линейного программирования.................... 41

3.1.2. Формы представления задачи линейного программирования.. 44

3.2. Геометрическая интерпретация задачи линейного программирования.................................................................................................. 47

3.2.1. Представление задачи линейного программирования на плоскости........................................................................................................... 47

3.2.2. Алгоритм решения задачи линейного программирования графическим методом...................................................................................... 50

3.3. Симплекс-метод решения задачи линейного программирования................................................................................................................ 52

3.3.1. Основная идея симплекс-метода.................................................. 52

3.3.2. Алгоритм табличного симплекс-методом................................... 54

3.4. Нахождение допустимых решений задачи линейного программирования............................................................................................. 60

3.4.1. Допустимое решение в задаче линейного программирования.. 60

3.4.2. Алгоритм поиска допустимого решения.................................... 65

3.5. Транспортная задача.................................................................... 69

3.5.1. Постановка транспортной задачи линейного программирования................................................................................................................ 69

3.5.2. Нахождение опорного плана....................................................... 75

3.6. Методы решения транспортной задачи с правильным балансом................................................................................................................ 77

3.6.1. Распределительный метод решения транспортной задачи........ 77

3.6.2. Метод потенциалов...................................................................... 82

3.7. Методы решения транспортной задачи с неправильным балансом.......................................................................................................... 96

3.7.1. Решение транспортных задач с неправильным балансом......... 96

3.7.2.Метод запрещенных клеток.......................................................... 99

3.8. Целочисленное программирование............................................ 102

3.8.1. Постановка задачи целочисленного программирования.......... 102

3.8.2. Метод ветвей и границ................................................................. 103

3.8.3. Метод отсекающих плоскостей................................................... 106

Глава 4. Нелинейное и динамическое программирование............ 108

4.1. Методы поиска экстремумов унимодальных функций........... 108

4.1.1. Локальный и глобальный экстремумы функций. Нахождение экстремумов методом общего поиска........................................................ 108

4.1.2. Методы поиска экстремумов унимодальных функций.............. 112

4.2. Поиск экстремумов многомерных функций............................. 116

4.2.1. Постановка задачи. Метод случайного поиска.......................... 116

4.2.2. Методы прямого поиска.............................................................. 120

4.3. Динамическое программирование............................................. 125

4.3.1. Сущность метода динамического программирования.............. 125

4.3.2. Алгоритм решения задачи динамического программирования 130

Глава 5. Сетевые задачи..................................................................... 133

5.1. Введение в теорию графов........................................................... 133

5.1.1. Основные понятия и определения теории графов...................... 133

5.1.2. Определение связности вершин графа........................................ 139

5.2. Определение кратчайших путей в графе................................... 147

5.2.1. Метод Форда – Беллмана............................................................ 147

5.2.2. Метод Дейкстры........................................................................... 156

5.3. Определение пропускной способности сетей связи................... 159

5.3.1. Постановка задачи определения максимального потока........... 159

5.3.2. Максимальный поток в сети........................................................ 162

ВЫРАБОТКА РЕШЕНИЙ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ

Глава 6. Принятие решений в условиях конфликта....................... 166

6.1. Основные понятия теории игр.................................................... 166

6.1.1. Предмет, задачи и основные понятия теории игр...................... 166

6.1.2. Классификация игр...................................................................... 170

6.2. Матричные игры.......................................................................... 176

6.2.1. Антагонистические матричные игры и их решение................... 176

6.2.2. Графический метод решения игр................................................ 182

6.3. Методы решения конечных игр.................................................. 185

6.3.1. Решение игр m x n.......................................................................... 186

6.3.2. Численные методы решения игр................................................. 190

6.4. Анализ экспертных оценок.......................................................... 192

6.4.1. Общая характеристика метода экспертных оценок................... 192

6.4.2. Обработка и анализ ранжировок................................................ 205

6.4.3. Обработка и анализ бальных оценок.......................................... 208

Глава 7. Марковские модели принятия решений............................ 204

7.1. Марковские модели принятия решений.................................... 204

7.1.1. Общие понятия............................................................................. 204

7.1.2. Управляемые цепи Маркова........................................................ 207

7.2. Вероятности состояний Марковских моделей........................... 208

7.2.1. Поглощающие марковские цепи................................................. 210

7.2.2. Эргодические цепи....................................................................... 216

 

ЛИТЕРАТУРА...................................................................................... 218

ВВЕДЕНИЕ

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

Еще сравнительно недавно считалось, что выработка решения является искусством, основанным на опыте, знаниях и интуиции. Однако в современных условиях только опыт, знания и интуиция далеко не всегда могут обеспечить выбор не только оптимального (наилучшего), но даже всего лишь удовлетворительного решения в сложных практических задачах.

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

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

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

Учебное пособие состоит из семи глав. В первой главе излагаются основные понятия исследования операций и системного анализа. Методологические основы теории принятия решений.

Во второй главе рассматриваются теоретические основы выбора альтернатив. Отношения, операции над отношениями. Функции выбора и операции над ними.

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

В четвертой главе рассматриваются нелинейные оптимизационные задачи, методы решения задач одномерной и многомерной оптимизации.

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

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

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