Исследование операций: В 2-х томах. Пер. с англ./Под 38 ред. Дж. Моудера, С. Элмаграби.—М.: Мир, 1981. Т. 1. 712 с., ил.
В первом томе приводятся теоретические основы исследования операций и ряд детерминированных и стохастических моделей, используемых для оптимизации систем. В качестве математического аппарата для анализа детерминированных моделей применяются методы линейного, нелинейного, целочисленного и геометрического программирования. При рассмотрении стохастических моделей используются методы теорий массового обслуживания и полезности, принятия решений, теории игр, имитационного моделирования и динамического программирования.
Для специалистов в области исследования операций, теории управления, экономистов, инжереров-конструкторов, разработчиков АСУ, а также для студентов соответствующих специальностей.
ПРЕДИСЛОВИЕ К РУССКОМУ ПЕРЕВОДУ
В настоящее время методы исследования операции широко применяются в самых различных областях человеческой деятельности. В нашей стране теоретическим аспектам и практическим применениям методов исследования операций придается исключительно большое значение, о чем свидетельствует значлтельное количество публикаций по этим вопросам. Однако очень важно иметь руководство, в котором были бы отражены все направления теории исследования операций. Поэтому издание на русском языке двухтомника по исследованию операций, написанного группой ведущих американских специалистов под редакцией Дж. Моудера и С. Элмаграби, представляет значительный интерес.
Исследование операций как самостоятельное научное направление1 возникло из потребностей наилучшей организации боевых действий, а также прогнозирования их исхода при принятии командованием различных решений. С помощью методов исследования операций можно планировать стратегические и тактические военные операции, в частности, в условиях неполного знания о состоянии вооруженных сил противника.
Математические методы этой науки используются при проектировании сложных авиационных, ракетных и космических комплексов. Основу математического аппарата проектирования составляют линейное и нелинейное программирование, способы принятия решений, теория массового обслуживания, теория игр и имитационное моделирование.
После второй мировой войны методы исследования операций получили широкое применение при перспективном и текущем планировании научно-исследовательских работ, проектировании различных объектов, управлении производственными и технологическими процессами, прогнозировании развития отдельных отраслей промышленности и сельского хозяйства. Особенно часто к ним обращаются при решении задач распределения трудовых ресурсов п запасов, назначения сроков профилактического ремонта оборудования, выбора средств транспортировки грузов, составления графиков расписаний перевозок, размещения новых заводов и складов, сбора информации в автоматизированных системах управления и целого ряда других. В таких задачах и качестве критериев эффективности применяются различные целевые функции. Для нахождения оптимальных решений производится максимизация (минимизация) целевой функции. Следует отметить, что при решении таких задач наряду со строгим математическим аппаратом программирования, теории графов, потоков в сетях и оптимального управления применяются эвристические методы, основанные на интуиции разработчиков.
В решении задач проектирования принимают участие группы людей, которые оказывают большое влияние как на сам процесс проектирования, гак и на принятие решения на отдельных этапах выполнения проекта. Естественно, что при принятии решения проектировщики учитывают не только рекомендации,полученные на основе расчетов на цифровых вычислительных машинах, но и свои соображения, зачастую носящие качественный характер. •-"Тим вопросам в данном двухтомнике уделяется значительное внимание, так как создаваемые в настоящее время системы автоматизированного проектирования и конструирования представляют собой человеко-машинные комплексы, где принятие окончательного решения возлагается на человека.
——,.««™,
Предисловие к русскому переводу Предисловие
Часть I
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ
I- 1 . История развития и использование методов исследования операций,
X. Майаер ... ...................... jg
1. Начальный период ................... 13
2. Научная сущность исследования операций . ....... jg
3. Практические применения методов исследования операций 19
4. Развитие методов исследования операций в период с 1945 по
1975 г ......................... 21
5. Дальнейшее развитие методов исследования операций .... 32
6. Перспективы развития методов исследования операций Литература
.. 33 33
1-2. Методика проведения исследований операций, Н. Эйджин ... 37
1. Введение ........................ 37
2. Определение целей ................... 38
3. Составление плана разработки проекта .......... 40
4. Формулировка проблемы ................. 44
5. Построение модели .................... 52
6. Разработка вычислительного метода ............ 55
7. Разработка технического задания на программирование; программирование и отладка ............... 57
8. Сбор данных ...................... 59
9. Проверка модели .................... 61
10. Реализация результатов исследования операций ..... 64 Литература ......................... 65
1-3. Подготовка специалистов по исследованию операций, Р. Т ролл
1. Введение ....................... 66
2. Структура системы подготовки специалистов по исследованию операций ....................... 67
3. Уровни научной квалификации специалистов по исследованию операций ....................... 72
4. Учебные программы .................. 76
5. Привлечение кадров в сферу исследования операций .... 79 Литература ..................... . . • "
Часть П
МЕТОДЫ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ (ДЕТЕРМИНИРОВАННЫЕ МОДЕЛИ)
QJ
П-1. Линейное программирование, X. Taxa .......... • •
81
1. Введение ........................ SA
2. Применение моделей линейного программирования . . • •
3. Свойства решений задач линейного программирования ... 89
4. Симплекс-метод.........,............ 93
5. Теория двойственности................. 105
6. Анализ моделей на чувствительность .......... 115
7. Линейные задачи, допускающие декомпозицию ..... 117
8. Заключительные замечания............... 118
Литература........................ 118
П-2. Целочисленное программирование и комбинаторика, Ф. Гловер
1. Введение........................ 122
2. Примеры задач ЦП .................. 126
3. Методы решения задач целочисленного программирования 136
4. Задачи целочисленного программирования, обладающие особыми свойствами.................... 147
Литература ........................ 150
П-3. Теория графов: некоторые методы и приложения, Т. Caamu
1. Введение........................ 153
2. Основные определения ................. 156
3. Связность ...................... 159
4. Экстремальные графы.................. 168
5. Укладка ........................ 174
6. Некоторые из основных теорем ............. 183
7. Матрицы........................ 184
8. Два примера приложений ............... 189
9. Заключительные замечания ............... 191
Литература ........................ 191
П-4. Потоки в сетях, Э. Джонсон................ 194
1. Введение ....................... 194
2. Кратчайшие пути ................... 194
3. Максимальные потоки ................. 197
4. Прямо-двойственный алгоритм ............. 201
5. Кратчайшие пути и отрицательные циклы........ 207
6. Линейное программирование .............. 208
7. Приложения ..................... 218
8. Потоки с выигрышами................. 220
9. Многополюсные и многопродуктовые потоки....... 220
Литература........................ 222
П-5. Геометрическое программирование, Э. Питерсон....... 225
1." Введение........................ 225
2/Формулировка задачи и примеры............ 226
3. Основы теории..................... 236
Литература ....................... 265
П-6. Нелинейное программирование, О. Мангасариан....... 267
1. Введение........................ 267
2. Условия оптимальности ................ 269
3. Двойственность .................... 274
4. Алгоритмы минимизации в одномерном случае...... 275
5. Алгоритмы безусловной минимизации.......... 278
6. Алгоритмы минимизации при наличии ограничений .... 281 Литература........................ 288
П-7. Математическое программирование задач^большой размерности
Л. Ласдон........................' „о*
1. Введение........................ „о.
2. Решение задач линейного программирования^ большой раз-мерности модифицированным симплекс-методом (МСМ) . . . 992
3. Метод обобщенных ограничений сверху ........ 29/
4. Метод генерации столбцов............... a^l
5. Метод декомпозиции Данцига—Вулфа ......... gj?
6. Нелинейные задачи большой размерности........ gji
7. Перспективы развития ................' 322
Литература.......................| 324
П-8. Оптимальное управление, Г. Саган ............. 327
1. Постановка задачи................... 327
2. Необходимые условия.................. 330
3. Синтез......................... 337
4. Достаточные условия ................. 341
5. Заключительные замечания............... 345
Литература.................'....... 347
Часть Ш
МЕТОДЫ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ
(СТОХАСТИЧЕСКИЕ МОДЕЛИ)
Ш-1. Стохастические процессы, В. Смит............. 349
1. Введение ....................... 349
2. Случайные блуждания ................. 357
3. Простое случайное блуждание ............. 361
4. Рекуррентные события (процессы) ............ 363
5. Цепи Маркова ..................... 366
6. Мартингалы ...................... 371
7. Процессы восстановления ............... 373
8. Кумулятивные процессы ................ 376
9. Ветвящиеся процессы ................. 379
10. Обобщенные процессы рождения и гибели....... 380
11. Временные ряды и стационарные^процессы....... 383
Литература ........................ 389
Ш-2. Теория массового обслуживания, Ю. Б хат......... 391
1. Введение........................ 391
2. Задачи, терминология и обозначения .......... 393
3. Области применения .................. 396
4. Анализ поведения систем................ 399
5. Статистический анализ ................. 414
6. Операционный анализ ................. 419
7. Методы теоретического анализа............. ад
8. Вычислительные проблемы ............... 436
9. Основные направления современных исследований .... 439
10. Заключение...................... 44О
Литература........................ 441
Ш-3. Теория полезности, П. Фишберн.............. *^
1. Введение........................ 448
2. Предпочтение, и полезность...............
3. Теория ожидаемой полезности ............. 460
4. Многофакторная теория полезности .......... 468
5. Субъективная вероятность и ожидаемая полезность .... 473
6. Заключительные замечания ............... 477
Литература........................ 477
Ш-4. Теория принятия решений, Р. Кини............ 481
1. Введение........................ 481
2. Аксиомы теории принятия решений........... 486
3. Методологические основы теории принятия решений .... 489
4. Числовая форма представления неопределенности суждений. 495
5. Оценка полезности................... 500
6. Успехи теории принятия решений ........... 506
7. Будущее теории принятия решений........... 509
Литература ....................... 509
Ш-5. Теория игр и игровое моделирование, Г. Оуэн........ 513
Некоторые исторические сведения ............ 513
1. Позиционные игры и нормальная форма игры...... 513
2. Игры двух лиц с нулевой суммой............ 516
3. Игры двух лиц с ненулевой суммой 534
4. Игры п лиц ..................... 537
5. Игровое моделирование................. 546
Литература ........................ 548
Ш-6. Теория поиска, Ф. Морз ................. 549
Введение ......................... 549
1. Основные понятия ................... 551
2. Движение наблюдателя................. 557
3. Выявление зоны поиска ................ 567
4. Оптимальное распределение поисковых усилий ..... 576
5. Поиск в случае движущейся мишени........... 594
6. Поиск дискретно локализованных объектов ....... 611
7. Поиск активно ускользающей мишени ......... 623
8. Вопросы практического применения .......... 627
Литература........................ 628
Ш-7. Имитационное моделирование, Д. Гвйеер ......... 630
1. Введение........................ 630
2. Этапы имитационного эксперимента .......... 630
3. Формирование модели ................. 632
4. Методы генерации случайных чисел........... 634
5. Построение имитационной модели и методы уменьшения дисперсии ........................ 640
6. Статистический анализ данных ............ 648
Литература........................ 653
Ш-8. Вычислительные аспекты имитационного моделирования, Д. Гордон ...........................' 655
1. Имитационное моделирование системы ......... 655
2. Модели систем .................... 657
3. Модель механического цеха............... 660
4. Отображение системы ................. 661
5. Процесс имитации (имитационный эксперимент)..... 663
6. Накопление статистических данных........... 664
7. Обработка списков................... 664
8. Языки имитационного моделирования.......... 666
9. Алгоритмы управления "'имитационными моделями .... 666
10. Способ организации языка GPSS ........... 667
11. Модели механического цеха на языке GPSS....... 670
12. Структура системы SIMSCRIPT............ 671
13. Модель механического цеха на языке SIMSCRIPT .... 672
14. Сравнительные характеристики языков имитационного моделирования ....................... 674
Литература........................ 675
Ш-9. Динамическое программирование, Э. Денардо ....... 680
1. Введение ....................... 680
2. Прототип многошагового процесса принятия решений ... 681
3. Некоторые принципы динамического программирования . . 684
4. Пример ........................ 686
5. Состояния ....................... 688
6. Неопределенность ................... 690
7. Язык для описания многошаговых процессов принятия решений ....................... 692
8. Марковская модель процесса принятия решений..... 696
9. Заключение ...................... 702
Литература........................ 703
Предметный указатель.................... 704
Цена: 300руб.
