Книга Вагнера является одной из фундаментальных работ по исследованию операций. На русском языке она издается в трех томах.
В первом томе подробно изложены основные концепции исследования операций и рассмотрены методы оптимизации управляющих решений с помощью аппарата линейного программирования. Значительная часть книги посвящена обсуждению специфических приемов оптимизации на сетях. Особое внимание уделяется искусству построения моделей и анализу оптимальных решений на чувствительность. Приведено много примеров, которые помогают быстро освоить методы решения линейных оптимизационных задач.
Книга предназначена для специалистов, интересующихся операционными методами решения задач организационного управлений- Она, несомненно, окажется полезной для математиков-прикладников, экономистов, специалистов но теории алгоритмизации, программистов, системотехников, а также различных категорий руководящих лиц как производственной, так и непроизводственной сферы деятельности. Студенты, специализирующиеся по исследованию операций или по смежным дисциплинам, могут использовать эту " книгу в качестве учебного пособия.
Том посвящен методам динамического, целочисленного и нелинейного программирования. Рассмотрены различные классы динамических моделей (модели управления запасами, модели распределения, модели замен и ряд других) и обсуждены процедуры построения соответствующих алгоритмов оптимизации. Приведен подробный анализ зависимости этих процедур от величины интервала времени, для которого ведется поиск оптимальной стратегии.
Операционным задачам, решение которых можно получить методами целочисленного программирования, посвящена специальная глава. В ней обсуждены также возможности и особенности комбинаторных приемов оптимизации.
Разделы, в которых рассматриваются нелинейные модели, содержат описание всех представляющих практический интерес методов оптимизации, включая разделение переменных, линеаризацию и аппроксимацию решений выпуклыми и вогнутыми функциями. Специально рассмотрен случай нелинейных ограничений. Приведен обобщенный алгоритм нелинейной оптимизации.
В томе 3 отражены современные достижения в области стохастического моделирования и рассмотрены многочисленные проблемы оптимизации управляющих решений применительно к процессам, явлениям и состояниям, характеризуемым параметрами, подчиняющимися законам теории вероятностей. Как и в первых двух томах, приведен ряд поучительных примеров, иллюстрирующих возможности излагаемых методов (модели очередей, вероятностные модели управления запасами, модель управляемой экономики и др.).
Автор знакомит читателя также с проблемой построения имитационных моделей систем управления и возможностями реализации такого рода моделей на ЭВМ.
Заключительная глава данного тома посвящена вопросам организации работ на всех этапах операционного исследования и практического использования получаемых при этом результатов.
**
ОГЛАВЛЕНИЕ
Том 1
Предисловие к русскому изданию
Глава 1
ИСКУССТВО И НАУКА В ОРГАНИЗАЦИОННОМ УПРАВЛЕНИИ 9
1.1. Несколько слов о термине «исследование операций» . . 9
1.2. О других названиях | 9
1.3. Границы применимости количественного анализа ... 16
1.4. Важность построения моделей 19
1.5. Процесс количественного анализа 22
1.6. Исследование операций «в миниатюре» 26
1.7. На пределе возможностей 39
1.8. О чем не следует забывать 45
Контрольные упражнения 45
Глава 2
ПОСТРОЕНИЕ ЛИНЕЙНЫХ ОПТИМИЗАЦИОННЫХ МОДЕЛЕЙ 50
2.1. Введение 50
2.2. Задача распределения ресурсов 54
2.3. Задача рационального составления комбикорма ... 57
2.4. Задача составления жидких смесей 59
2.5. Многосторонний коммерческий арбитраж 62
2.6. Динамическое планирование (пример комплексного производственного планирования) 64
2.7. Распределение потоков товарных поставок на транспортной сети 73
2.8. Задача выбора оптимального транспортного маршрута 78
2.9. Использование линейного программирования для решения производственных задач 84
Контрольные упражнения 90
Глава 3
АЛГЕБРАИЧЕСКОЕ И ГЕОМЕТРИЧЕСКОЕ ПРЕДСТАВЛЕНИЯ ЛИНЕЙНЫХ ОПТИМИЗАЦИОННЫХ МОДЕЛЕЙ 104
3.1. Введение 104
3.2. Алгебраическая формулировка задачи в общем виде . . 104
3.3. Канонические формы для линейных оптимизационных моделей 109
3.4. Геометрическая интерпретация 110
3.5. Представление в пространстве решений большего числа измерений 114
3.6. Представление в пространстве условий 115
Упражнения 119
Глава 4
СИМПЛЕКСНЫЙ МЕТОД 124
4.1. В перспективе — теория 124
4.2. Общее ознакомление с задачей 125
4.3. Алгоритмический метод 129
4.4. Введение в симплексный алгоритм 132
4.5. Полнота алгоритма 144
4.6. Область применимости 148
4.7. Свойства сходимости 150
4.8. Требования к вычислительным процедурам 155
4.9. Табличное представление 156
4.10. Матричное представление 158
Упражнения 160
Глава 5
АНАЛИЗ МОДЕЛЕЙ НА ЧУВСТВИТЕЛЬНОСТЬ И ДВОЙСТВЕННАЯ ЗАДАЧА 167
5.1. Анализ модели после нахождения оптимального решения 167
5.2. Целевая функция 169
5.3. Константы в правых частях ограничений 171
5.4. Двойственность 173
5.5. Решение двойственной задачи 178
5.6. Продолжение анализа на чувствительность 182
5.7. Заключение . , 186
5.8. Двойственный симплекс-алгоритм 187
5.9. Дополнительные ограничения 192
5.10. Переменные, значения которых ограничены сверху 194
Контрольные упражнения 198
Глава 6
ОПТИМИЗАЦИЯ НА СЕТЯХ 212
6.1. Значение сетевых моделей 212
6.2. Классическая транспортная задача 1213
6.3. Модель с промежуточными пунктами '219
6.4. Модель назначений 226
0.5. Модель выбора кратчайшего пути 227
6.6. Календарное планирование методом критического пути 236
6.7. Календарное планирование трудовых ресурсов .... 1239
6.8. Общие понятия сетевых моделей '243
6.9. Обобщенная сетевая задача 247
6.10. Многопродуктовая сеть 248
Упражнения 250
Глава 7
АЛГОРИТМЫ РЕШЕНИЯ СЕТЕВЫХ ЗАДАЧ 269
7.1. Сущность и оценка рассматриваемых вопросов .... 269
7.2. Основные положения '270
7.3. Симплексный метод решения транспортных задач . . . 272
7.4. Дополнительные замечания по симплексному методу 282
7.5. Оценка чувствительности решения 289
7.6. Кратчайший маршрут в сети общего вида 290
7.7. Кратчайший маршрут в ациклической сети 294
Упражнения 296
Приложение I
АЛГОРИТМЫ РЕШЕНИЯ СЕТЕВЫХ ЗАДАЧ 313
1.1. Максимальный поток в сети с ограниченными пропускными способностями 313
1.2. Решение задачи о назначениях 317
1.3. Алгоритмы решения других классов сетевых задач . . 329
______________
Том 2
Глава 8
ВВЕДЕНИЕ В ТЕОРИЮ ДИНАМИЧЕСКИХ ОПТИМИЗАЦИОННЫХ МОДЕЛЕЙ I 5
8.1. Анализ динамических процессов 5
8.2. Задача о дилижансах: аллегория 8
8.3. Простейшая задача управления запасами !14
8.4. Числовой пример 22
8.5. Анализ чувствительности решения |25
8.6. Попеки возможностей улучшения плана 34
Упражнения 137
Глава 9
ДИНАМИЧЕСКИЕ ОПТИМИЗАЦИОННЫЕ МОДЕЛИ УПРАВЛЕНИЯ ЗАПАСАМИ 49
9.1. Использование особенностей структуры 49
9.2. Выпуклые вогнутые целевые функции |49
9.3. Модель управления запасами с выпуклой функцией затрат 52
9.4. Анализ длительности планового периода в моделях с выпуклой функцией затрат |59
9.5. Модель управления производством и запасами с вогнутой функцией затрат 63
9.6. Алгоритм оптимизации модели с вогнутой функцией затрат 66
9.7. Анализ длительности планового периода в моделях с вогнутой функцией затрат 71
9.8. Модель управления запасами при сглаживании производства 74
Упражнения 80
Глава 10
ЕЩЕ О ДИНАМИЧЕСКОМ ПРОГРАММИРОВАНИИ . . 97
10.1 Введение [97
10.2. Модель распределения усилий 98
10.3. Распределение усилий. Два ограничения 104
10.4. Распределение усилий. Погруженная задача .... 105
10.5. Целочисленное линейное программирование .... 108
10.6. Модель замены оборудования 108
10.7. Структура многошагового анализа 111
10.8. Сущность динамических процессов 113
10.9. Вычислительные возможности метода динамического программирования 115
10.10. Область применения динамического программирования 116
Упражнения . . 117
Глава 11
ПРИНЯТИЕ РЕШЕНИЙ ПРИ БЕСКОНЕЧНОМ ПЛАНОВОМ ПЕРИОДЕ 131
11.1. Модели с бесконечным плановым периодом 131
11.2. Топкости, связанные с оценкой бесконечных последовательностей 134
11.3. Модель эксплуатации лесного хозяйства 150
11.4. Модель восстановления с бесконечным числом этапов 1|53
11.5. Методы последовательных приближений 158
11.6. Метод последовательных приближений в пространстве функций (метод итераций по критерию) 1159
11.7. Метод последовательных приближений в пространстве стратегий (метод итераций по стратегиям) 1|63
11.8. Эквивалентная задача линейного программирования 166
11.9. Повторное рассмотрение задачи нахождения кратчайшего пути 1!68
Упражнения 174
Глава 12
МЕТОДЫ ОПТИМИЗАЦИИ ПРИ БЕСКОНЕЧНОМ ПЛАНОВОМ ПЕРИОДЕ 188
12.1. Дискретное динамическое программирование . . . 188
12.2. Методы последовательных приближений 192
12.3. Минимизация среднего эффекта за отрезок 197
12.4. Демонстрация метода итераций по стратегиям на численных примерах 203
12.5. Простая модель управления запасами 211
12.6. Подход на основе линейного программирования . . 216
12.7. Заключительные замечания 223
Упражнения 226
Глава 13
МОДЕЛИ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ И КОМБИНАТОРНЫЕ МОДЕЛИ 240
13.1. Поиск философского камня .- 240
13.2. Постановки задач целочисленного программирования 246
13.3. Общие сведения о методах решения задач целочисленного программирования 256
13.4. Алгоритмы отсечения. (Метод целочисленных форм) 258
13.5. Метод ветвей и границ 267
13.6. Задачи коммивояжера 274
13.7. Метод частичного (неявного) перебора 284
Упражнения 294
Глава 14
ОПТИМИЗАЦИЯ ПРИ НЕЛИНЕЙНОЙ ЦЕЛЕВОЙ ФУНКЦИИ 324
14.1. Введение в нелинейное программирование 324
14.2. Направленность подхода и круг охватываемых вопросов 331
14.3. Оптимизация нелинейной функции одной переменной 334
14.4. Максимизация нелинейной функции многих переменных без ограничений 343
14.5. Метод скорейшего подъема 350
14.6. Квадратичное программирование 358
14.7. Сепарабельное программирование 371
14.8. Непосредственная линеаризация 380
14.9. Максимизация выпуклой целевой функции 383
Упражнения 384
Глава 15
УСОВЕРШЕНСТВОВАННЫЕ МЕТОДЫ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 402
15.1. Крупношаговые методы 402
15.2. Метод выпуклых комбинаций 405
15.3. Симплексный метод вогнутого программирования . . 411
15.4. Другие подходы 418
15.5. Оптимизация при нелинейных ограничениях .... 421
15.6. Метод допустимых направлений 426
15.7. Теоретические свойства оптимального решения . . 430
15.8. Возвращение к квадратичному программированию 437
15.9. Метод штрафной функции 443
15.10. Обобщенный алгоритм программирования .... 449
15.11. Декомпозиция задач линейного программирования 455
Упражнения 459
Литература 478
___________
Том 3
Глава 16
ВВЕДЕНИЕ В ТЕОРИЮ СТОХАСТИЧЕСКИХ ОПТИМИЗАЦИОННЫХ МОДЕЛЕЙ . 5
16.1. Управляющие решения в условиях неопределенности 5
16.2. На пути к оптимальному решению 13
16.3. Заблуждение относительно средних !. 29
16.4. Двухшаговая линейная модель 34
16.5. Модель с вероятностными ограничениями 46
16.6. Случай транспортной сети 52
16.7. Многошаговая линейная модель 61
16.8. Квадратичная критериальная функция (линейный вид оптималь-
ного решения) 69
Упражнения I. 72
Глава 17
ВЕРОЯТНОСТНЫЕ МОДЕЛИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
17.1. Введение 90
17.2. Задача распределения усилий 91
17.3. Проблема улучшения качества продукции и дерево решений . . I. 93
17.4. Элементарная модель управления запасами 98
17.5. Задача определения оптимального размера партии I. 102
17.6. Задача составления коммерческого прогноза 107
17.7. Стохастическая модель восстановления (задача замены оборудования) 110
17.8. Вопросы применимости и вычислительные аспекты методов вероятностного динамического программирования 114
Упражнения 115
Глава 18
ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ НА МАРКОВСКИХ ЦЕПЯХ 138
18.1. Введение [ 138
18.2. Стохастическая модель задачи о кратчайшем маршруте . . . . , 139
18.3. Бесконечный плановый период с дисконтированием (а < 1) . . . 145
18.4. Эквивалентный средний эффект (а = 1) 154
18.5. Подход, основанный на использовании аппарата линейного программирования 165
18.6. Вычислительные аспекты 169
18.7. Модель замены оборудования в виде марковских цепей .... I 170
Упражнения 172
Глава 19
СТОХАСТИЧЕСКИЕ МОДЕЛИ УПРАВЛЕНИЯ ЗАПАСАМИ .... 197
19.1. Новый подход 197
19.2. Научный подход к решению задачи управления запасами .... 198
19.3. Основные факторы, учитываемые при анализе систем управления запасами 201
19.4. Статическая модель 207
19.5. Модели экономически выгодных размеров заказываемых, партий 224
19.6. Динамические вероятностные модели с режимом непрерывного контроля уровня запасов 237
19.7. Несколько общих замечаний по поводу практического использовании результатов исследования 251
Упражнения 255
Глава 20
МОДЕЛИ МАССОВОГО ОБСЛУЖИВАНИЯ 270
20.1. Введение 270
20.2. Классификация моделей массового обслуживания 274
20.3. Распределение вероятностей для длительностей интервалов между последовательными поступлениями требований на обслуживание . . . 278;
20.4. Распределение вероятностей для длительностей обслуживания 287
20.5. Одиоканальная модель с пуассоновским входным потоком и экспоненциальным распределением длительностей обслуживания 294
20.6. Многоканальная модель с пуассоновским входным потоком и экспоненциальным распределением длительностей обслуживания 313
20.7. Процессы рождения и гибели 320
20.8. О других моделях массового обслуживания 328
Упражнения 329
Глава 21
ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ОПЕРАЦИОННЫХ СИСТЕМ С ПОМОЩЬЮ ЭВМ 343
21.1. Когда другие методы беспомощны 343
21.2. Имитационное моделирование в перспективе 349
21.3. Пример имитационного моделирования фондовой биржи 351
21.4. Построение имитационной модели 356
21.5. Генерация случайных событий 359
21.6. Приращепие времени 368
21.7. Проектирование имитационного эксперимента 375
21.8. Языки программирования 383
21.9. Задачи ближайшего будущего 386
Упражнения 387
Глава 22
ВНЕДРЕНИЕ РЕЗУЛЬТАТОВ ОПЕРАЦИОННОГО ИССЛЕДОВАНИЯ 393
22.1. Текущее положение 393
22.2. Как поставить исследование операций на службу руководителю 395
22.3. Как руководить разработкой операционного проекта 401
22.4. Как руководить подразделением, выполняющим операционное исследование 408
22.5. Взгляд в будущее 410
Приложение II
СТОХАСТИЧЕСКИЕ МОДЕЛИ УПРАВЛЕНИЯ ЗАПАСАМИ С ПЕРИОДИЧЕСКИМ КОНТРОЛЕМ ". . . . 413
ПЛ. Введение 413
П.2. Временные соотношения и неудовлетворенный спрос 413
11.3. Модель с конечным плановым периодом 418
11.4. Вид и полное определение оптимальных стратегий 422
11.5. Случай нулевых накладных расходов 433
11.6. Модель с бесконечным плановым периодом 437
11.7. Анализ модели с помощью марковских цепей 445
Приложение III
НЕКОТОРЫЕ СПЕЦИАЛЬНЫЕ МЕТОДЫ АНАЛИЗА МОДЕЛЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ 453
II 1.1. Предварительные замечания 453
111.2. Модель типа М/С/1 456
111.8. Модель типа С//М/1 465
III.4. Модель типа 61/М/8 469
II 1.5. Модель типа С//С/1 471
Приложение IV 473
ТАБЛИЦЫ 473
Литература 476
Предметный указатель 487