Москвин Б.В. Теория принятия решений

Подождите немного. Документ загружается.

МИНИСТЕРСТВО ОБОРОНЫ РОССИЙСКОЙ ФЕДЕРАЦИИ

ВОЕННО-КОСМИЧЕСКАЯ АКАДЕМИЯ ИМЕНИ А.Ф. МОЖАЙСКОГО

519.8

М 822

48396 у

Б.В. Москвин

ТЕОРИЯ ПРИНЯТИЯ РЕШЕНИЙ

Учебник

Допущено Министерством обороны Российской Федерации в каче-

стве учебника для курсантов высших военно-учебных заведений,

обучающихся по направлению "Информатика и вычислительная

техника", и для слушателей военных академий, обучающихся по

специальности "Управление эксплуатацией вооружения, военной

техники и техническим обеспечением войск (сил)"

Санкт-Петербург - 2005

УДК 519.816 (075.8)

М822 Москвин Б.В.

Теория принятия решений: Учебник / Б.В. Москвин. –

СПб.: ВКА имени А.Ф. Можайского, 2005. – 383 с.

В учебнике рассматриваются математические модели и алгоритмы при-

нятия решений, построенные на основе статических и динамических моделей, а

также вопросы принятия решений в сложных военно-технических системах.

Разбираются теоретические основы и вычислительные схемы решения

задач математического программирования (линейного, нелинейного и дискрет-

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

ритмов. Рассматриваются факторы, усложняющие процессы принятия решений.

Особое внимание здесь уделяется вопросам принятия решений в условиях неоп-

ределенности обстановки, в условиях критериальной неопределенности, вы-

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

нию, принятию решений в военно-технических системах, обладающих сложной

иерархической структурой. Приводятся примеры решения военно-прикладных

задач различных классов.

Учебник предназначен для самостоятельной подготовки слушателей при

изучении дисциплины "Методы и технологии выработки управленческих реше-

ний" и курсантов при изучении дисциплины "Теория принятия решений", а так-

же адъюнктов и специалистов, интересующихся вопросами автоматизации при-

нятия решений при управлении сложными военно-техническими системами.

Рецензенты:

Кафедра боевого применения АСУ войсками и связи

Военной академии

связи;

Санкт-Петербургский институт информатики и автоматизации РАН:

доктор технических наук, профессор Соколов Б.В.;

Кафедра автоматизации и обработки информации ВКА имени

А.Ф.Можайского:

доктор технических наук, профессор Дмитриев А.К.

Подп. к печ. 21.04.2005 Печ. л. 22,88 Уч.-изд. л. 22,5

Зак. 1512 Свободная цена

Типография ВКА имени А.Ф.Можайского

ОГЛАВЛЕНИЕ

ВВЕДEНИЕ........................……………………………………… 9

1. ПОСТАНОВКА ЗАДАЧ ПОДГОТОВКИ И ПРИНЯТИЯ РЕШЕ-

НИЙ ПРИ УПРАВЛЕНИИ ВОЕННО-ТЕХНИЧЕСКИМИ СИС-

ТЕМАМИ……………………………………………………….. 15

1.1. Принятие решений в системно-кибернетических

исследованиях............................................................. 15

1.2. Основные элементы и этапы принятия решения..... 21

1.3. Проблемы моделирования при принятии решений.. 27

1.4. Обобщенная математическая модель принятия

решения (математическая структура выбора)......... 32

Контрольные вопросы…………………………………………… 34

РАЗДЕЛ 1. ПРИНЯТИЕ РЕШЕНИЙ

НА ОСНОВЕ СТАТИЧЕСКИХ

МОДЕЛЕЙ ВОЕННО-ТЕХНИЧЕСКИХ СИСТЕМ

2. ПОСТАНОВКА ЗАДАЧ ВЫБОРА РЕШЕНИЙ В КОНЕЧНО-

МЕРНЫХ ВЕКТОРНЫХ ПРОСТРАНСТВАХ.......................... 35

2.1. Особенности задач математического

программирования……………………………………… 35

2.2. Примеры моделей принятия решения в виде

задач математического программирования.............. 38

2.3. Элементы выпуклого анализа задач оптимизации... 44

2.4. Необходимые и достаточные условия

существования оптимального решения.

Теорема Куна-Таккера................................................ 48

3. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ................................. 51

3.1.

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

3.2. Свойства выпуклых многогранников в задаче

линейного программирования.................................... 55

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

программирования...................................................... 58

3.4. Основные элементы алгоритмов линейного

программирования...................................................... 61

3.5. Алгоритмы линейного программирования.

Симплекс-метод.......................................................... 64

3.6. Построение исходного опорного решения................ 68

3.7. Вырожденность в задачах линейного

программирования...................................................... 72

Контрольные вопросы…………………………………………… 73

4. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ............................ 75

4.1.Особенности задач нелинейного программирования 75

4.2. Алгоритмы решения задач нелинейного

программирования...................................................... 77

4.3. Методы приведенной безусловной оптимизации..... 79

4.3.1. Методы безусловной оптимизации.................. 79

4.3.2. Функции Лагранжа............................................. 82

4.3.3. Штрафные функции.......................................... 83

4.4. Методы прямой условной оптимизации.................... 85

4.4.1. Метод условного градиента............................. 85

4.4.2. Метод возможных направлений ……………... 87

Контрольные вопросы…………………………………………… 89

5. ДИСКРЕТНОЕ ПРОГРАММИРОВАНИЕ............................. 90

5.1. Постановка задач дискретного программирования.. 90

5.2. Целочисленные и почти

целочисленные

многогранники решений............................................ 92

5.3. Методы отсечения в задачах дискретного

программирования. Алгоритм Р.Гомори.................. 95

5.4. Методы типа "ветвей и границ" в задачах

дискретного программирования................................ 98

Контрольные вопросы…………………………………………… 101

6. СПЕЦИАЛЬНЫЕ ЗАДАЧИ МАТЕМАТИЧЕСКОГО

ПРОГРАММИРОВАНИЯ..................................................... 102

6.1. Транспортная задача……………………………..…….. 102

6.1.1. Построение исходного опорного плана

транспортной задачи………………………..….. 106

6.1.2. Метод потенциалов……………………………... 110

6.2. Транспортная задача в сетевой постановке............. 114

6.3. Задача о назначениях................................................. 121

Контрольные вопросы…………………………………………… 127

7. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ МАТЕМАТИЧЕСКОГО

ПРОГРАММИРОВАНИЯ…………………………………… 128

7.1. Постановка задач математического

программирования…………………………………….. 128

7.2. Линейное программирование.................................... 132

7.2.1. Графо-аналитический способ решения задач 133

7.2.2. Симплекс-метод решения задач...................... 136

7.2.3. Способы построения исходного решения…... 140

7.2.4. Вырожденные задачи. Зацикливание............. 145

7.3. Нелинейное программирование................................ 146

7.3.1. Градиентные методы....................................... 146

7.3.2. Метод покоординатной оптимизации………... 149

7.3.3. Метод условного градиента............................. 151

7.3.4. Метод возможных направлений...................... 152

7.4. Дискретное программирование.................................. 153

7.4.1. Метод отсечений Р.Гомори.............................. 153

7.4.2. Метод "ветвей и границ"................................... 157

РАЗДЕЛ 2. ПРИНЯТИЕ РЕШЕНИЙ НА ОСНОВЕ ДИНАМИЧЕ-

СКИХ МОДЕЛЕЙ ВОЕННО-ТЕХНИЧЕСКИХ СИСТЕМ

8. ПОСТАНОВКА И КАЧЕСТВЕННЫЙ АНАЛИЗ ПРОБЛЕМЫ

ОПТИМАЛЬНОГО УПРАВЛЕНИЯ ДИНАМИЧЕСКИМИ

СИСТЕМАМИ………………………………………………….. 159

8.1. Содержание проблемы управления динамическими

системами................................................................... 159

8.2. Основные понятия динамических систем................ 162

8.2.1. Математические модели динамических

систем.…………………..................................... 163

8.2.2. Решение дифференциальных уравнений

состояния.......................………………….......... 166

8.2.3. Сопряженная система.............………………... 172

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

8.3.1. Способы задания функционала............…...... 176

8.3.2. Виды дифференциальных связей.............….. 177

8.3.3. Ограничения вдоль

траектории............……… 178

8.3.4. Краевые условия......................................…….. 179

8.4. Примеры задач оптимального управления..….......... 180

8.4.1. Оптимальное управление сближением

космических аппаратов....................………….. 180

8.4.2. Управление операциями обслуживания

космического аппарата.................................… 182

8.5. Качественный анализ проблемы оптимального

управления..........................................…………........... 183

8.5.1. Управляемость динамической системы…….. 184

8.5.2. Достижимость состояний динамической

системы..………………...................................... 185

8.5.3. Существование и единственность

оптимального управления.......................…...... 186

8.6. Необходимые условия существования

оптимального управления..............................……….. 187

8.6.1. Функция Гамильтона......………………….......... 188

8.6.2. Принцип максимума Л.С.Понтрягина...………. 189

8.6.3. Условия трасверсальности..............………….. 191

8.7. Многошаговые процессы управления

рекуррентными динамическими системами....……... 192

Контрольные вопросы…………………………………………… 195

9. АЛГОРИТМЫ ВЫБОРА ОПТИМАЛЬНОГО ПРОГРАММНОГО

УПРАВЛЕНИЯ ДИНАМИЧЕСКИМИ СИСТЕМАМИ........... 196

9.1. Вычислительные методы расчета оптимальных

программ..……............................................................. 196

9.2. Методы, основанные на решении краевой

задачи… 198

9.3. Метод Ньютона............................................................ 200

9.4. Алгоритм И.Крылова-Ф.Черноусько........................... 204

9.5. Особые (вырожденные) и скользящие управления.. 206

Контрольные вопросы…………………………………………… 209

10. АЛГОРИТМЫ ВЫБОРА ОПТИМАЛЬНОГО РЕШЕНИЯ В

ФОРМЕ СИНТЕЗА УПРАВЛЕНИЯ………………………………… 210

10.1. Постановка задачи синтеза управления.................. 210

10.2. Синтез управления в линейных динамических

системах.................................................................…. 211

10.3. Синтез управления в рекуррентных системах.

Принцип оптимальности Р.Беллмана

..................... 214

10.4. Алгоритм динамического программирования.......... 216

Контрольные вопросы…………………………………………… 219

11. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ ОПТИМАЛЬНОГО

УПРАВЛЕНИЯ………………………………………………… 220

11.1. Оптимальное управление сближением КА.............. 220

11.1.1. Управление КА, оптимальное

по быстродействию…………........................ 221

11.1.2. Оптимальное по расходу топлива

управление КА.............................…………...... 227

11.2. Алгоритм Ньютона в задаче поиска оптимального

по быстродействию управления сближением КА.. 231

11.3. Оптимальное многошаговое управление

выполнением операции обслуживания

КА...………. 235

РАЗДЕЛ 3. ПРИНЯТИЕ РЕШЕНИЙ В СЛОЖНЫХ ВОЕННО-

ТЕХНИЧЕСКИХ СИСТЕМАХ

12. ПОСТАНОВКА ЗАДАЧ ПОДГОТОВКИ И ПРИНЯТИЯ

РЕШЕНИЙ В СЛОЖНЫХ ВОЕННО-ТЕХНИЧЕСКИХ

СИСТЕМАХ……………………………………………………. 242

12.1. Понятие сложных военно-технических систем и

особенности принятия решений в них..………….… 242

12.2. Обобщенная постановка задач принятия решений

в сложных системах...........……….........…………….. 246

12.3. Автоматизированная система управления КА,

как сложная военно-

техническая система............... 250

12.4. Модели принятия решений в АСУ КА…….............. 254

12.4.1. Характеристика ситуации управления КА.... 255

12.4.2. Статическая модель планирования

операций управления КА................................ 258

12.4.3. Динамическая модель планирования

операций управления КА................................ 261

Контрольные вопросы.......................………………………….. 264

13. ПРИНЯТИЕ РЕШЕНИЙ В УСЛОВИЯХ НЕОПРЕДЕЛЕННО-

ГО ВОЗДЕЙСТВИЯ ВНЕШНЕЙ СРЕДЫ………………... 265

13.1. Характеристика задач принятия решений в

условиях неопределенности среды....……......... 265

13.2.

Принятие решений в условиях стохастической

среды..………………………………………………... 269

13.2.1. Методы детерминизации.........……………. 270

13.2.2. Методы имитационной оптимизации.……... 272

13.2.3. Модель двухэтапного стохастического

выбора...............................………………….. 273

13.3. Принятие решений в условиях целенаправленной

среды...................…….....…………..……………… 275

13.3.1. Постановка задач игрового выбора…........ 277

13.3.2. Матричные игры. Чистые и смешанные

стратегии....……………………................……. 278

13.3.3. Методы нахождения оптимальных

смешанных стратегий..................………….. 285

13.4. Принятие решений в условиях неизвестной

среды

.…………………...................................... 290

13.4.1. Модели типа "игра с природой"…………… 291

13.4.2. Выбор на основе нечеткого

описания среды.……………......................... 294

Контрольные вопросы.........................………………………… 302

14. ПРИНЯТИЕ РЕШЕНИЙ В УСЛОВИЯХ КРИТЕРИАЛЬНОЙ

НЕОПРЕДЕЛЕННОСТИ..................……………………….. 304

14.1. Характеристика задач многокритериального

выбора…………………………………………………. 304

14.2. Множество недоминируемых решений............……. 308

14.3. Принятие решений на основе операторных

решающих правил.…………….....................…..……. 314

14.3.1. Решающие правила в задачах

бесприоритетной оптимизации…………....... 315

14.3.2. Учет относительной важности критериев…. 318

14.3.3. Оптимизация по последовательно

применяемым критериям.........……………... 319

14.4. Принятие решений на

основе

лингвистического решающего правила.................... 320

Контрольные вопросы..............................…………………… 323

15. ПРИНЯТИЕ РЕШЕНИЙ В ИЕРАРХИЧЕСКИХ ВОЕННО-

ТЕХНИЧЕСКИХ СИСТЕМАХ………………………………. 324

15.1. Принцип декомпозиции в задачах выбора..………. 324

15.2. Координация с модификацией целевой функции.. 330

15.3. Координационное планирование на основе

перераспределения ресурсов....…………………..... 338

15.4. Релаксация в задачах координации......................... 343

15.5. Координационное планирование операций

управления КА...………………………………………. 344

Контрольные вопросы....…….........................………………... 351

16.ПРИМЕРЫ ЗАДАЧ

ПРИНЯТИЯ РЕШЕНИЙ В СЛОЖНЫХ

СИСТЕМАХ……………………………………………………. 352

16.1. Принятие решений в условиях неопределенного

воздействия внешней среды..................…………… 352

16.2. Принятие решений в условиях критериальной

неопределенности......................…………….……….. 359

16.3. Декомпозиционные методы принятия решений

в сложных системах...................……………………... 370

Библиографический список..................................................... 379

ВВЕДЕНИЕ

Военно-космическая деятельность Российской Федерации,

начиная с момента запуска первого искусственного спутника

Земли и по настоящее время, тесно связана с решением одной из

центральных проблем исследования сложных систем любой ма-

териальной природы – проблемой у п р а в л е н и я космически-

ми средствами. Среди этих средств, в

первую очередь, необхо-

димо выделить орбитальные группировки космических аппаратов

(КА) различного целевого назначения (навигация, связь, развед-

ка) и соответствующие технические средства, образующие на-

земные комплексы управления. Основу существующей и перспек-

тивной технологии управления перечисленными орбитальными и

наземными космическими средствами составляет комплекс опе-

раций, связанных с получением, обработкой, анализом траектор-

ной

, телеметрической информации о состоянии средств, перио-

дическим формированием и реализацией управляющих воздей-

ствий, выдаваемых на борт космического аппарата с использова-

нием технических средств наземного комплекса управления.

Главная особенность и отличительная черта указанных

процессов состоит в необходимости оперативной и качественной

обработки огромных потоков разнородной информации, произво-

димой с целью выработки рациональных

р е ш е н и й по управ-

лению космическими средствами. Развитие и возрастание слож-

ности объектов управления (КА и средств наземного комплекса),

повышение требований к качеству управления в связи с возрас-

танием цены управленческой ошибки, рост технологической

сложности процессов управления ведет к повышению интенсив-

ности управленческого труда. Такая тенденция

имеет устойчивый

характер во всех областях деятельности человека, и она обу-

славливает необходимость а в т о м а т и з а ц и и управления.

Однако, развитие автоматизации даже в передовых отраслях от-

стает от роста требований к интенсивности обработки возрас-

тающих потоков информации, требований к оперативности и

ка-

честву принятия решений - центральной функции управления. В

связи с этим во всех отраслях производственной деятельности

проявляется устойчивая тенденция роста количества специали-

стов управленческого характера.

Сложность обстановки, в которой командиру приходится

управлять современными военными системами в реальном мас-

штабе времени, требует значительного усиления поддержки про-

цессов подготовки и принятия решений на основе комплексной

автоматизации. Основой автоматизированного управления кос-

мическими средствами является формализованное описание –

м а т е м а т и ч е с к а я м о д е л ь ситуации принятия реше-

ния. В настоящее время имеются значительные успехи в разра-

ботке

и широком практическом применении математических мо-

делей различных классов, для которых разработаны эффектив-

ные алгоритмы оптимизации, позволяющие получать решения в

приемлемое для войсковой практики время. Большое разнообра-

зие ситуаций, возникающих при управлении космическими сред-

ствами, необходимость оперативного принятия решений, удовле-

творяющих разнородным качественным требованиям, опреде-

ляемым спецификой целевого функционирования военных

сис-

тем, вызывают необходимость комплексного использования бога-

того арсенала математических моделей, разработанных в рамках

системно-кибернетических исследований. Это, прежде всего, мо-

дели математического программирования и оптимального управ-

ления, позволяющие учитывать основные особенности функцио-

нирования космических средств. В рамках моделей данных клас-

сов накоплен значительный опыт разработки достаточно эффек-

тивных алгоритмов, позволяющих

наиболее полно отражать спе-

цифику решаемых задач.

Оптимизация процессов управления военно-техническими

системами на основе аналитических статических моделей приня-

тия решений связана с поиском некоторого конечномерного век-

тора, описывающего решение, который доставляет оптимум (мак-

симум или минимум) целевой функции. Алгоритмы нахождения

таких векторов, основанные на использовании методов оптими-

зации, развиваются

в рамках м а т е м а т и ч е с к о г о п р о г -

р а м м и р о в а н и я - наиболее изученного и широко применяе-

мого на практике направления оптимизации решений. Здесь,

прежде всего, различают задачи с непрерывными

переменными

(компоненты вектора, описывающего решение, действительные

числа) и задачи с целочисленными переменными. В зависимости

от характера целевой функции и ограничений различают задачи

линейные и нелинейные. Одной из первых практических задач

данного класса была задача о выборе производственной про-

граммы, которая была решена в 1939 г. в работе известного рос-

сийского математика

академика Л.В.Канторовича. Однако наибо-

лее интенсивное развитие математическое программирование

получило в период 1955-1970 г.г., и в настоящее время имеются