Коршунов Ю. М. Математические основы кибернетики: Учебное пособие для вузов. — 3-е изд., перераб. и доп. — М.: Энергоатомиздат, 1987. — 496 с.: ил.
Изложены основы математического аппарата, используемого при исследовании и описании кибернетических моделей и методов оптимизации сложных систем По сравнению с изданием 1980 г. в книгу добавлены новые разделы по векторным производным, многомерному нормальному распределению и гауссовским марковским случайным процессам, матричным моделям систем, фильтрации сигналов и др.
Для студентов, обучающихся по специальности «Автоматика и телемеханика».
ОГЛАВЛЕНИЕ
Предисловие................3
Указатель обозначений..........7
Глава 1. Введение.............9
1.1. Предмет кибернетики ..........9
1.2. Передача и кодирование информации.......11
1.3. Понятие об управляемой системе......18
1.4. Сложные системы........22
Задачи к гл. I...........23
Глаиа 2. Основные поиятня теории множеств.....24
2.1. Конечные и бесконечные множестиа......24
2.1.1. Основные определения.........94
2.1.2. Понятие подмножества ..........27
2.1.3. Взаимно однозначное соответствие между множествами .........28
2.1.4. Счетные и несчетные множества........30
2.1.5. Верхняя и нижняя границы множества .......33
2.2. Операции над множествами.......31
2.2.1. Предварительные замечания......34
2.2.2. Объединение множеств..........35
2.2.3. Пересечение множеств.......36
2.2.4. Разность множеств...........38
2 2.5. Универсальное множество ........39
2.2.6. Дополнение множества .........40
2.2.7. Разбиение множества........41
2.2.8. Тождества алгебры миожеств ........42
2.3. Упорядочение элементов и прямое произведение множеств......44
2 3.1. Упорядоченное множество.......44
2.3.2. Прямое произведение множеств ........46
2.3.3. Проекция множества ........48
2.4. Соответствия..........48
2.4.1. Определение соответствия.......48
2.4 2. Обратное соответствие .......50
2.4.3. Композиция соответствия.......50
2.5. Отображения и функции........51
2.5.1. Отображения и их свойства.......51
2.5.2. Отображения, заданные на одном множестве ......63
2.5.3. Функция............64
2.5.4 Обратная функция.........57
2.5.5. Функция времени.........59
2.5.6. Понятие функционала ......60
2.5.7. Понятие оператора ...........61
2.6. Отношения.............62
2.6.1. Свойства отношений .
2.6.2. Отношение эквивалентности ......63
2.6.3. Отношение порядка ........64
2.6.4. Отношение доминирования ....65
Задачи к гл. 2...........66
Глава 3. Основы теории графов.........67
З.1. Основные определения теории графов.....67
3.1.1. Теоретико-множественное определение графа .....67
3.1.2. Неориентированные графы.......70
3.1.3. Изоморфизм графов.........72
3.1.4. Отношение порядка и отношение эквивалентности на графе...........73
3.1.5. Характеристики графов
3.2 Задача о кратчайшем пути......76
3.2.1. Постановка задачи.........76
3.2.2. Нахождение кратчайшего пути в графе с ребрами единичной длины.........77
3.2 3 Нахождение кратчайшего пути в графе с ребрами произвольной длины ..........80
3.2.4. Построение графа наименьшей длины .......82
3.3. Транспортные сети .............84
3.3.1. Основные понятия .......84
3.3.2. Задача о наибольшем потоке.........86
3.3.3. Транспортная задача ........89
Глава 4. Элементы линейной алгебры и выпуклые множества ......96
4.1. Метрические пространства и расстояния .......96
4.1.1. Понятие о расстоянии .......96
4.1. 2. Определение метрического пространства .......98
4.1.3. Примеры метрических пространств.........98
4.2. Использование метрических пространств в некоторых задачах кибернетики ........100
4.2.1. Пространство сообщении.......100
4.2.2. Понятие о помехоустойчивых кодах ........102
4.2.3. Сглаживание ошибок в экспериментальных данных......103
4.2.4. Задача распознавания образов......105
4.3. Линейные пространства.........106
4.3.1. Определение линейного пространства .... 107
4.3 2. Действия над векторами.......109
4.3.3. Линейная зависимость и независимость векторов.......110
4.3.4. Линейное подпространство .....111
4.3.5. Размерность линейного пространства ....112
4.4. Евклидовы пространства.........112
4.4.1. Линейное нормированное пространство ......112
4.4.2. Скалярное произведение векторов.....113
4.4.3. Угол между векторами Ортогональные векторы.....116
4.5. Матрицы и линейные преобразования ......117
4.5.1. Понятие матрицы...........117
4.5.2. Линейное преобразование.......113
4.5.3 Операции над матрицами.......120
4.5.4. Транспонированная матрица ......122
4.6. Квадратные матрицы..........123
4.6.1. Особенности квадратных матриц. Нулевая и единичная матрицы.........123
4.6 2. Определитель квадратной матрицы .....124
4.6.3. Обратная матрица и решение систем линейных уравнений..............125
4.6.4. Инвариантное подпространство. Собственные векторы н собственные значения матриц......127
4.6.5. Диагонализация матриц........131
4.6.7. Симметрические матрицы и квадратичные формы .......132
4 7.1. Собственные векторы и собственные значения вещественных симметрических матриц......132
4.7.2. Диагонализация симметрических матриц......134
4.7.3. Квадратичные формы........135
4.7.4. Использование квадратичных форм при отыскании экстремумов функций многих переменных ....136
4.7.5. Векторные производные........137
4.8. Выпуклые множества..........138
4.8.1. Понятие гиперсферы ........138
4.8.2. Ограниченные и конечные множества .....139
4.8.3. Открытые и замкнутые множества.....139
4.8.4. Гиперплоскости и полупространства .......140
4.8.5. Прямая и отрезок. Средневзвешенное по элементам множества............142
4.8.6. Выпуклые множества........143
4.8.7. Выпуклая оболочка конечного множества .......144
4.8.8. Разделительная и опорная гиперплоскости ........146
Задачи к гл. 4.............147
Глава 5. Элементы теории вероятностей и математической статистики ...........148
5.1. Понятие вероятности..........148
5.1.1. События и пространство исходов эксперимента........148
5.1.2 Понятие вероятности........149
5.1 3. Вероятность события........150
5.1.4. Способы приписывания вероятностей исходам эксперимента .........151
5.1.5. Вычисление вероятностей сложных событий ........153
5.2. Условные вероятности .......155
5.2.1. Понятие условной вероятности......155
5.2.2. Формула полной вероятности......167
5.2.3 Определение апостериорных вероятностей. Формула Байеса.........157
5.3. Непрерывные случайные величины и их распределения .......158
5.3.1. Понятие непрерывной случайной величины......158
5.3.2. Функция распределения вероятностей ..........159
5.3.3. Плотность вероятности........100
5 3.4. Равномерное распределение вероятностей ........162
5.3.5. Гауссовское (нормальное) распределение вероятностей .............162
5.4. Числовые характеристики случайных величии ..........164
5.4.1. Понятие о числовых характеристиках ...........164
5.4 2. Математическое ожидание случайной величины..........164
5.4.3. Математическое ожидание функции от случайной величины............166
5.4.4. Моменты. Дисперсия. Среднеквадратичное отклонение ...........168
5.5. Двумерные случайные величины ........170
5.5.1. Понятие двумерной случайной величины ........170
5.5.2. Распределение вероятностей для непрерывных двумерных случайных величин........172
5.5 3. Математические ожидания для двумерной случайной величииы............175
5.5.4. Регрессия и корреляция.........176
5.6. Многомерное гауссовское распределение вероятностей .........180
5.6.1. Вектор математических ожиданий и ковариационная матрица..........180
5.6.2. Гауссовское распределение вероятностей случайного вектора...........182
5.6.3. Нормальное распределение вероятностей двух случайных векторов..........183
5.6.4. Условное нормальное распределение вероятностей ........184
5.7. Случайные процессы с дискретным временем .........185
5.7.1. Понятие о случайных процессах с дискретным временем ...........185
5.7.2. Процесс независимых испытаний с двумя исходами Биномиальное распределение вероятностей .......187
5.7.3. Распределение Пуассона .......189
5.7.4. Экспоненциальное распределение. Понятие о надежности ...........190
5.7.5. Марковские цепи.........195
5.7.6. Гауссовскис марковские процессы.....198
5.7.7. Примеры гауссовских марковских процессов .......200
5.8. Элементы математической статистики..........203
5.8.1. Предмет математической статистики .........203
5.8.2. Понятие случайной выборки ........204
5.8.3. Предельные теоремы теории вероятностей ........205
5.8.4. Критерии статистических оценок .........208
5.8.5. Несмещенные оценки математического ожидания и дисперсии ..........210
5.8.6. Нахождение оценок по методу максимального правдоподобия........
6.8.7. Оценка параметров по методу доверительных интервалов.............
5.8.8. Проверка статистических гипотез. Понятие о критерии согласия............219
5.8.9. Оценка влияния некоторого фактора на характер случайной величины.........221
5.8.10. Проверка гипотезы о дисперсиях. Понятие о F-распределении..........222
5.9. Регрессионный анализ и планирование эксперимента
5.9.1. Задача регрессионного анализа......223
5.9.2 Определение коэффициентов регрессии по данным пассивного эксперимента.........226
5.9.3. Понятие о планировании эксперимента ........230
5.9 4. Полный факторный эксперимент........231
5.9.5. Понятие дробных реплик.......235
Задачи и гл. 5..........238
Глава 6. Структура и математическое описание задач оптимального управления..........239
6.1. Основные черты процесса управления......239
6.1.1. Понятие об управлении........239
6 1.2. Виды задач управления........240
6.1.3. Понятие об исследовании операций.....242
6.2. Оптимизация процесса управления......244
6.2.1. Критерий качества управления .....244
6.2.2. Ограничения, накладываемые на процесс управления .....
6.2.3. Постановка задачи оптимального управления ......245
6.3. Математическое описание объекта управления ......247
6.3.1. Производственно-экономические модели ......247
6 3.2. Структура объекта управления ......251
6.3 3. Уравнения движения объекта управления ......256
6.3.4 Линейные модели динамических систем ........257
6.3.5. Дискретные линейные системы .........261
6.4. Классификация задач оптимального управления .......201
6.4.1. Одношаговые задачи принятия решения .......261
6.4.2. Динамические задачи оптимизации управления......265
6.4.3. Управление конечным состоянием.....268
6.5. Многошаговые процессы управления ......269
6.5.1. Поведение динамической системы как функция начального состояния.........2G9
6.5.2. Представление динамического процесса в виде последовательности преобразований .......270
6.5.3. Многошаговый процесс управления.....271
6.5.4. Критерий качества управления при многошаговом процессе.............272
6.6 Основные понятия теории оптимизации ..........274
6.6.1. Общая постановка задачи оптимизации ........274
6.6.2. Ограничения на допустимое множество .......275
6.6.3. Выпуклые и вогнутые функции......276
6.6.4. Свойства выпуклых (вогнутых) функций .......279
6.6.5. Классическая задача оптимизации ........280
6.6.6. Функция Лагранжа.........281
Глава 7. Линейное и нелинейное программирование .......2Н2
7.1. Постановка задачи линейного программирования .....282
7.1.1. Основные определения........282
7.1.2. Примеры задач линейного программирования ......285
7.1.3. Геометрическая интерпретация задачи линейного программирования.........289
7.2 Решение задачи линейного программирования ......293
7 2 1. Алгебра симплекс-метода.......293
7.2.2. Табличный метод нахождения оптимального решения ..............295
7 2.3 Получение начального допустимого базисного решения ..............299
7.2 4 Двойственная задача линейного программирования 300
7.2.5. Понятие о целочисленном программировании ......304
7.3. Нелинейное программирование ......306
7.3.1. Постановка задачи.........306
7 3.2. Метод штрафных функций.........З06
7.3.3. Ограничения типа равенств и неотрицательность переменных.............308
7.3.4. Условия Куна — Таккера........369
7.3.5. Квадратичное программирование ......311
7.4. Итеративные методы поиска оптимума ........313
7.4.1. Постановка задачи.........313
7.4.2. Градиентный метод.........316
7.4.3. Метод наискорейшего спуска (подъема) ......316
7.4 4. Алгоритм Ньютона..........319
7.4.5. Учет ограничений и многоэкстремальные задачи
Задачи к гл. 7 ..............319
Глава 8. Динамическое программирование......322
8.1. Оптимальное управление как вариационная задача .......322
8.1.1. Математическая формулировка задачи оптимального управления...........322
8.1.2. Трудности, связанные с решением вариационной задачи.............326
8.2. Метод динамического программирования .....
8.2.1. Дискретная форма вариационной задачи.......328
8.2.2. Рекуррентное соотношение метода динамического программирования..........330
8.2.3. Вычислительные аспекты динамического программирования
8.2.4. Управление конечным состоянием.....339
8.2.5. Рекуррентное соотношение для марковских процессов .........310
Задачи к гл. 8 .........342
Глава 9. Теория игр............343
9.1. Предмет теории игр ........343
9.1.1. Игра как модель конфликтной ситуации .......343
9.1.2. Понятие стратегии........345
9.1.3. Формальное описание игры двух лиц ......345
9.1.4. Верхняя и нижняя цены игры .....351
9.2. Цены и оптимальные стратегии игр......353
9.2.1. Игра с седловой точкой.......353
9.2.2. Чистые и смешанные стратегии ....354
9.2.3. Функция потерь при использовании смешанных стратегий.............356
9.2.4. Верхняя и нижняя иены игры при использовании смешанных стратегии ..........358
9.3. Основная теорема теории игр ......362
9.3.1. 5-игра ............362
9.3.2. Нижняя и верхняя цены игры в 5-игре .....362
9.3.3. Теорема о минимаксе ........367
9.3.4. Геометрическая иллюстрация принципа минимакса.......370
9.4. Решение игр ............371
9.4.1. Доминирующие и полезные стратегии ........371
9.4.2. Нахождение оптимальных стратегий .........375
9.4.3. Геометрическая иллюстрация принципа минимакса в игре 2Хя.............378
Задачи к гл. 9..............379
Глава 10. Теория статистических решений (статистические игры).....380
10.1. Структура статистических игр........380
10.1.1. Стратегические и статистические игры ........380
10.1.2. Пространство стратегий природы........381
10.1.3. Пространство стратегий статистика и функция потерь........... 382
10.1.4. Примеры статистических игр ........384
10.2. Статистические игры без эксперимента ........385
10.2.1. Представление статистической игры без эксперимента в виде 5-игры..........385
10.2.2. Допустимые стратегии в статистических играх.....386
10.2.3. Принципы выбора стратегий в статистических играх .............388
10.2.4. Геометрическая трактовка байесовских стратегий.........391
10.3. Статистические игры с проведением единичного эксперимента ..............393
10.3.1. Постановка задачи.........393
10.3 2. Пространство выборок........394
10.3.3. Решающая функция .........395
10.3.4. Функция риска..........397
10.3 5. Принципы выбора стратегии в играх с единичным экспериментом...........399
10.4. Использование апостериорных вероятностей ........400
10.4.1. Определение числа стратегий в играх с проведением эксперимента...........400
10.4.2. Апостериорное распределение вероятностей ........401
10.4.3. Принцип максимального правдоподобия ........403
10.4.4. Определение байесовского решения на основе использования апостериорных вероятностей ......404
10 4.5 Двухальтернативиая задача ..........405
10.5. Статистические игры с последовательными выборками 408
10.5.1 Предварительные замечания......408
10.5.2. Использование апостериорного распределения вероятностей для определения последовательных байесовских правил...........410
10.5.3. Правило последовательных выборок .........411
10.5.4. Функция риска при оптимальном последовательном правиле............413
10.5.5. Определение областей остановки для двухальтериативной задачи при усеченной последовательной выборку......416
10.6. Оценивание параметров и фильтрация.........418
10.6.1. Задача оценки параметров .........418
10.6.2 Опенки метода наименьших квадратов ......421
10.6.3. Анализ точности оценки метода наименьших квадратов.......423
10.6.4 Применение метода наименьших квадратов для оценки параметров нелинейных объектов.........424
10.6.5. Постановка задачи фильтрации...........425
10.6 6. Фильтрация по методу наименьших квадратов........426
10 6.7. Представление вектора оценок с помощью весовых коэффициентов..........429
10.6.8. Фильтры с растущей памятью .........431
10.6.9. Экспоненциальные фильтры ........435
Задачи к гл. 10 ............437
Глава 11. Задачи теории расписаний и массового обслуживания.....437
11.1. Предмет теории расписаний .........437
11.1.1. Общие сведения.........437
11.1.2. Постановка задачи теории расписаний ........438
11.1.3. Виды задач на составление расписаний .......440
11.2. Сетевое планирование и управление......441
11.2.1. Понятие сетевого графика. Составление перечня работ ..........441
11.2.2. Упорядочение (ранжировка) работ .......443
11.2.3. Определение резервов времени.....444
11.2.4. Построение сетевого графика......445
11.2 5. Коррекция распределения ресурсов ........449
11.2 6. Оптимизация срока выполнения комплекса работ......451
11.2.7. Вероятностные методы сетевого планирования......452
11.3. Комбинаторные задачи на составление расписания .......454
11.3.1. Понятие о комбинаторных задачах ........454
11.3.2. Задача коммивояжера ........454
11.3.3. Представление задачи коммивояжера в виде графа..............4о6
11.4. Примеры задач, сводящихся к задаче коммивояжера
11.4.1 Задача Гамильтона..........457
11.4.2. Транспортные задачи........457
11.4.3. Оптимизация программирования для ЭВМ .........457
11.4.4 Определение оптимальной последовательности обработки деталей на двух стайках......458
11.5. Методы решения задачи коммивояжера.....460
11.5.1. Применение метода Монте-Карло ........460
11.5.2. Сведение к задаче целочисленного линейного программирования.........460
11.5.3. Метод ветвей и границ.......
11.5.4. Применение метода ветвей и границ к решению задачи коммивояжера .........464
11.6. Задачи массового обслуживания..........468
11.6.1. Основные понятия. Терминология .......468
11.6.2. Дифференциальные уравиеняя системы массового обслуживания...........469
11.6.3. Система массового обслуживания с отказами.......472
11.6.4. Однокаиальная система обслуживания с ожиданием ...........473
11.6.5. Многоканальная система обслуживания с ожиданием .............474
11.6.6 Статистическое моделирование систем массового обслуживания .............476
Список литературы ...........480
Предметный указатель...........483
