В монографии известного американского специалиста рассматриваются методы линейного, целочисленного, динамического и нелинейного программирования, а также вероятностные' модели, используемые для анализа систем со случайным по-ведением и принятия соответствующих решений. Многочисленные примеры помогут читателю освоить описанные модели и методы исследования операций. В русском переводе выходит в двух книгах.
Для научных работников, инженеров, экономистов и студентов высших учебных заведений.
**
ОГЛАВЛЕНИЕ
Книга 1
Предисловие к русскому изданию 5
Предисловие 6
Глава 1. Исследование операций и искусство организационного управления 8
1.1. Исследование операций как наука и искусство 18
1.2. Структурные характеристики задач формирования управляющих решений 10
1.3. Искусство моделирования 12
1.4. Этапы исследования операций , 20
1.5. Несколько замечаний о книге в целом 23
ЧАСТЬ I. ЛИНЕЙНОЕ, ЦЕЛОЧИСЛЕННОЕ И ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ 25
Глава 2. Линейное программирование: формулировка задач их графическое решение 26
2.1. Задача линейного программирования и ее графическое решение 26
2.2. Примеры применения методов линейного программирования
2.3. Задача линейного программирования как задача распределения ресурсов 59
2.4. Заключение 60
Контрольные вопросы 61
Задачи 61
Глава 3. Линейное программирование: алгебраический метод решения задач 71
3.1. Стандартная форма линейных оптимизационных моделей . . 71
3.2. Симплекс-метод |74
3.3. Особые случаи применения симплекс-метода 96
3.4. Интерпретация симплекс-таблиц — анализ модели на чувствительность 109
3.5. Заключение 119
Контрольные вопросы 120
Задачи
Глава 4. Линейное программирование: двойственность и анализ моделей на чувствительность 1133
4.1. Определение двойственной задачи 1ЙЗ
4.2. Соотношения двойственности 1138
4.3. Экономическая интерпретация двойственности 1152
4.4. Двойственный симплекс-метод 1|59
4.5. Анализ моделей на чувствительность (после нахождения оптимального решения) \ . . . 162
4.6. Заключение 176
Контрольные вопросы 177
Задачи 179
Глава 5. Линейное программирование: транспортная модель 193
5.1. Определение транспортной модели и ее применение 193
5.2. Решение транспортной задачи , . , , 204
5.3. Задача о назначениях 219
5.4.Транспортная модель с промежуточными пунктами
5.5. Заключение 228
Контрольные вопросы 229
Задачи 230
Глава 6. Линейное программирование: сети 241
6.1. Минимизация сети 242
6.2. Задача о кратчайшем пути 245
6.3. Задача о максимальном потоке 258
6.4. Представление сетевых задач как задач линейного программирования 263
6.5. Заключение 265
Контрольные вопросы 266
Задачи 267
Глава 7. Линейное программирование: развитие теории 271
7.1. Матричное представление стандартной задачи ЛП 271
7.2. Теоретические основы линейного программирования 273
7.3. Модифицированный симплекс-метод 283
7.4. Задачи с ограниченными переменными 294
7.5. Метод декомпозиции 301
7.6. Параметрическое линейное программирование 312
7.7. Заключение 326
Контрольные вопросы 326
Задачи 329
Глава 8. Целочисленное программирование 339
8.1. "Примеры задач целочисленного программирования 340
8.2. Методы решения задач целочисленного программирования 344
8.3. Алгоритмы, реализующие метод отсекающих плоскостей . . 345
8.4. Метод ветвей и границ 357
8.5. Частичный перебор в задачах с булевыми переменными. . . . 364
8.6. Заключение 376
Контрольные Вопросы 378
Задачи 380
Глава 9. Динамическое программирование 387
9.1. Элементы модели динамического программирования. Задача распределения капиталовложений 388
9.2. Несколько замечаний к определению состояния 401
9.3. Примеры моделей динамического программирования 404
9.4. Проблема размерности в динамическом программировании 420
9.5. Решение линейных оптимизационных задач методом динамического программирования 421
9.6. Заключение 424
Контрольные вопросы 425
Задачи 426
ЧАСТЬ II. ВЕРОЯТНОСТНЫЕ МОДЕЛИ 433
Глава 10. Основы теории вероятностей 434
10.1. Исходы, пространства событий и события 434
10.2. Законы теории вероятностей 435
10.3. Случайные величины и распределения вероятностей , , . 436
10.4. Взаимосвязь между различными распределениями вероятностей 445
10.5. Совместные распределения вероятностей 447
10.6. Математические ожидания и моменты случайной величины 451
10.7. Производящая функция моментов 454
10.8. Центральная предельная теорема 456
10.9. Свертки 457
10.10. Случайные (стохастические) процессы 459
10.11. г-преобразование 467
Контрольные вопросы 471
Задачи 473
__________
Книга 2
Глава 11. Теория игр и принятия решений Б
11.1. Принятие решений в условиях риска 6
11.2. Деревья решений 19
11.3. Принятие решений в условиях неопределенности 22
11.4. Теория игр 27
11.5. Заключение 39
Литература 40
Контрольные вопросы 40
Задачи 41
Глава 12. Календарное планирование программ сетевыми методами ... 49
12.1. Сетевое представление программы (сетевая модель) .... 51
12.2. Расчет сетевой модели 54
12.3. Построение календарного графика и распределение ресурсов 59
12.4. Учет неопределенности и затрат при календарном планировании программ 64
12.5. Управление процессом реализации программы 77
12.6. Заключение 78
Литература .... 78
Контрольные вопросы 79
Задачи 80
Глава 13. Модели управления запасами 89
13.1. Обобщенная модель управления запасами 89
13.2. Типы моделей управления запасами 91
13.3. Детерминированные модели 94
13.4. Вероятностные модели 125
13.5. Заключение 145
Литература 146
Контрольные вопросы 146
Задачи 147
Глава 14. Марковские процессы принятия решений 158
14.1. Марковская задача принятия решений. Пример с садовником 158
14.2. Модель динамического программирования с конечным числом этапов 161
14.3. Модель с бесконечным числом этапов 166
14.4. Решение марковской задачи принятия решений методом линейного программирования ... 177
14.5. Заключение ' 181
Литература 181
Задачи 182
Глава 15. Теория массового обслуживания 185
15.1. Основные компоненты моделей массового обслуживания . . 186
15.2. Роль пуассоновского и экспоненциального распределений вероятностей в теории массового обслуживания 192
15.3. Системы массового обслуживания при наличии входного и выходного потоков 203
15.4. Системы массового обслуживания с приоритетами .... 231
15.5. Тандем очередей 235
15.6. Анализ очередей с помощью вложенных цепей Маркова . , 241
15.7. Заключение , 250
15.8. Приложение. Вывод основных формул для операционных, характеристик процессов массового обслуживания . .-, 251
Литература 258
Контрольные вопросы 258
Задачи 260
Глава 16. Практическое применение теории массового обслуживания . , 281
16.1. Трудности, возникающие при моделировании системы массового обслуживания 282
16.2. Подготовка исходных данных и проверка статистических гипотез 288
16.3. Принятие решений с использованием моделей массового обслуживания 1 294
16.4. Анализ конкретной ситуации 303
16.5. Заключение 314
Литература ; 314
Задачи 314
Глава 17. Имитационное моделирование . 321
17.1. Области применения имитационного моделирования . ... 322
17.2. Роль случайных чисел ; 323
17.3. Моделирование как эксперимент. Метод Монте-Карло , . . 333
17.4. Приемы построения и эксплуатации имитационных моделей 338
17.5. Получение наблюдений при моделировании 1 344
17.6. Оптимизация в имитационном моделировании. Задача управления запасами 354
17.7. Заключение I 358
Литература [ 358
Контрольные вопросы [ 358
Задачи 360
Упражнения , 364
Часть III. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ , 365
Глава 18. Классическая теория оптимизации 366
18.1. Экстремальные задачи без ограничений , 366
18.2. Экстремальные задачи при наличии ограничений .'-.,,[ 373
18.3. Заключение , 399
Литература 399
Контрольные вопросы [ 399
Задачи 401
Глава 19. Алгоритмы решения задач нелинейного программирования . . 405
19.1. Алгоритмы решения нелинейных задач без ограничений . . 405
19.2. Алгоритмы решения нелинейных задач с ограничениями , . 411
19.3. Заключение 438
Литература 439
Задачи . 439
Приложение А. Векторы и матрицы 444
А.1. Векторы 444
А.2. Матрицы '. 445
А.З. Квадратичные формы 494
Литература - 456
Задачи 456
Приложение Б. Основные теоремы дифференциального исчисления . . . 458
Б.1. Определения 458
Б.2. Теорема Ролля 459
Б.З. Теоремы о среднем значении 459
Б.4. Правило Лопиталя 461
Б.5. Полиномиальная аппроксимация 461
Б.6. Выпуклые и вогнутые функции 464
Литература
Задачи
Приложение В. Машинная программа для реализации на ЭВМ модели массового обслуживания 468
Приложение Г. Ответы к задачам 471
Предметный указатель 49
