!4 Введение в исследование операций: В 2-х книгах. Кн. 1. Пер. с англ.— М.: Мир, 1985.— 479 с., ил.
В монографии известного американского специалиста рассматриваются методы линейного, целочисленного, динамического и нелинейного программирования, а также вероятностные' модели, используемые для анализа систем со случайным поведением и принятия соответствующих решений. Многочисленные примеры помогут читателю освоить описанные модели и методы исследования операций. В русском переводе выходит в двух книгах.
Для научных работников, инженеров, экономистов и студентов высших учебных заведений.
Предисловие к русскому изданию
История развития исследования операций как самостоятельной научной дисциплины насчитывает немногим более тридцати лет. За это время достигнуты большие успехи в разработке методологических и математических основ анализа функциональных систем, т. е. систем, принципы функционирования которых в существенной степени определяются решениями людей. Опубликовано много работ по вопросам математического моделирования сложных организационно-экономических, инженерно-технических и других функциональных систем, а также работ практической направленности, в которых содержатся полезные сведения об использовании теоретических результатов исследования операций при формировании конкретных управляющих решений.
Исследование операций ориентировано на решение практических задач, которые можно корректно описать с помощью той или иной математической модели с целью получения оптимального решения. Постоянное усложнение изучаемых процессов и явлений, иерархичность и многомерность задач, решаемых в различных областях науки и техники, совершенствование электронно-вычислительной техники, применяемой при анализе сложных динамических систем и управлении такими системами, а также многие другие факторы приводят к тому, что методология исследования операций все теснее смыкается с методологией системного подхода. Вместе с тем необходимо отметить, что исследование операций как научную дисциплину нельзя считать тождественной теории систем, поскольку методы, используемые в теории систем, являются более общими и абстрактными, а задачи — существенно более сложными. Однако вполне правомерно рассматривать исследование операций как одно из направлений прикладной математики, способствующих прогрессу в общей теории систем.
Книга, предлагаемая вниманию читателей, может служить учебным пособием по теории и практическому использованию методов исследования операций. Здесь представлены в. основном важнейшие разделы исследования операций: математическое программирование, теория принятия решений и теория игр, теория управления запасами, теория массового обслуживания, имитационное моделирование.
К числу несомненных достоинств книги следует отнести простоту и стройность изложения на достаточно высоком уровне математической строгости, а также практическую направленность. Значительный методологический интерес представляют взгляды автора на связь между линейным и нелинейным программированием, которая позволяет обосновать основные идеи симплекс-метода с помощью метода приведенного, или условного, градиента; кроме того, интересен подход к оценке роли метода ветвей и границ среди методов целочисленного программирования. С большим педагогическим мастерством написана глава, посвященная основам такого традиционно трудного для восприятия раздела исследования операций, как динамическое программирование.
Эта книга выгодно отличается-от других учебных пособий прежде всего тем, что используемый автором способ изложения делает ее чтение увлекательным. Популярность книги за рубежом (где за одиннадцать лет она выдержала три издания), по-видимому, связана с замечательной способностью автора объяснять сложные вопросы просто и наглядно. Написанная без излишнего академизма, но достаточно строго, книга будет доступна и полезна широкому кругу читателей: студентам, аспирантам и преподавателям высших учебных заведений, инженерам, экономистам, специалистам по обработке информации, разработчикам математического обеспечения АСУ и т. д.
Б. Вавилов, В, Моторин
Предисловие
Основная цель, которую преследовал автор при подготовке третьего издания] книги, заключалась в том, чтобы повысить степень доступности излагаемого мате-? риала для студентов. Источником информации, необходимой для достижения этой? цели, был именно тот круг читателей, для которого и предназначалась данная книга, т. е. сами студенты. За десять лет, прошедших после выхода в свет первого^ издания, автор яснее понял трудности, с которыми обычно сталкиваются студенты1 при изучении основ исследования операций. Третье издание книги как раз и> должно помочь студентам преодолеть эти затруднения.
Работая в течение трех лет с материалом, необходимым для подготовки настоящего издания, автор старался мысленно ставить себя на место студентов и, пытаясь предугадать вопросы, которые ему будут заданы, стремился заранее ответить \ на них по возможности ясно и подробно. Во многих случаях он воспроизводил в -памяти вопросы, которые возникали у него в студенческие годы при попытках разобраться в методах исследования операций.
Предлагаемое вниманию читателей третье издание книги существенно переработано по сравнению с двумя предыдущими изданиями. Книга дополнена тремя i новыми главами, посвященными сетевым моделям, анализу марковских процессов • и, наконец, вопросам практического применения теории массового обслуживания. \ Те главы книги в ее предыдущих изданиях, которые содержат изложения основ' линейного и динамического программирования, а также главы, в которых рассматриваются основные положения теории массового обслуживания и принципы имитационного моделирования, почти полностью переработаны. В этих главах теперь больше внимания уделяется анализу конкретных ситуаций и интерпретации получаемых результатов. Главы, посвященные целочисленному и нелинейному программированию, теории принятия решений, теории игр и методам управления запасами, также существенно отличаются от соответствующих глав двух первых изданий книги. •:
Во многих главах нового издания книги увеличено количество упражнений' и задач. При этом дополнительно введенные задачи позволяют расширить круг/ понятий, проверить те или иные'теоретические положения. Упражнения, включенные в текст книги, просты, и на поставленные в них вопросы даются ответы. Эти упражнения, подобранные и составленные с особой тщательностью, служат для проверки степени усвоения читателем только что проработанного им материала. Упражнения такого рода, как правило, предусматривают небольшой объем] вычислений и не отрывают читателя надолго от чтения основного текста. Кром| того, в конце большинства глав книги приводятся контрольные вопросы, ответа на которые предусматривают два варианта: «верно» или «неверно». Личный пракз тический опыт свидетельствует о большой пользе такой проверки, позволяющей лучше проследить за взаимосвязью основных теоретических положений соответ ствующей главы.
Ясно, что в книге, где рассматриваются многие разделы исследования опера ций, весьма трудно, а иногда и нежелательно излагать каждый из них так, как эти можно было бы сделать в отдельной книге, полностью посвященной соответствую щему вопросу. Хотелось'бы подчеркнуть, что автор стремился к изложению раз; личных разделов исследования операций приблизительно на одинаковом уровн полноты и детализации. Однако степень «сбалансированности» представления м»
Предисловие '
териала — понятие весьма условное, поскольку в интерпретацию «сбалансированности» всегда вводится элемент субъективизма. В данной книге отношение к этой проблеме определялось критериями предпочтения, вытекающими из желания повысить качество учебного пособия по исследованию операций. В частности, автор считал, что для понимания существа идей и методов исследования операций прежде всего необходимо знание линейного программирования. Действительно, без глубокого усвоения теории линейного программирования можно получить лишь поверхностные представления о таких разделах, как, например, потоки в сетях, целочисленное и нелинейное программирование.
Благодарности
При подготовке настоящей книги существентгую помощь оказали многие мои коллеги, сделавшие критические замечания по предыдущему (второму) изданию. Я многим им обязан. Особую же признательность хочется выразить проф. Гаю Кэрри (Техасский университет), Шриканту Пенволкеру (Техасский университет), Чарльзу Проктору (Университет шт. Мичиган) и Аллену К. Шуерману (Университет в г. Вичита).
Глубокую благодарность я приношу также редактору издательства Macmillan г-же Элен Уеттероу за отлично выполненную работу по редактированию книги, а также Кэрол Ланкастер и Каролине Рэми за тщательное выполнение машинописных работ. Наконец, я не могу не выразить искренней признательности моему аспиранту Хосе Пабло Нунчо де ла Парра за помощь в составлении задач и упражнений.
'. - X. Таха
Оглавление
Предисловие к русскому изданию................... 5
Предисловие............т................. 6
Глава 1. Исследование операций и искусство организационного управления 8
1.1. Исследование операций как наука и искусство....... 8
1.2. Структурные характеристики задач формирования управляющих решений....................... 10
1.3. Искусство моделирования................. 12
1.4. Этапы исследования операций............... 20
1.5. Несколько замечаний о книге в целом........... 23
ЧАСТЬ I. ЛИНЕЙНОЕ, ЦЕЛОЧИСЛЕННОЕ И ДИНАМИЧЕСКОЕ
ПРОГРАММИРОВАНИЕ................. 25
Глава 2. Линейное программирование: формулировка задач < их графическое решение....................... 26
2.1. Задача линейного программирования и ее графическое решение 26
2.2. Примеры применения методов линейного программирования 41
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
Задачи............................. 122
Глава 4. Линейное программирование: двойственность и анализ моделей
на чувствительность ..................... 133
4.1. Определение двойственной задачи.............. 133
4.2. Соотношения двойственности................ 138
4.3. Экономическая интерпретация двойственности....... . 152
4.4. Двойственный симплекс-метод................ 159
4.5. Анализ моделей на чувствительность (после нахождения оптимального решения)........-........... 162
4.6. Заключение........................ 176
Контрольные вопросы..................'...'. 177
Задачи.........................'.'..'. 179
Глава 5. Линейное программирование: транспортная модель....... 193
5.1. Определение транспортной модели и ее применение..... 193
5.2. Решений транспортной задачи ............... 204
478 Оглавление *
5.3. Задача о назначениях................... 2191
5.4. Транспортная модель с промежуточными пунктами.....
'5.5. Заключение........................ 228
Контрольные вопросы...................... 229
Задачи............................. 230
Глава в. Линейное программирование: сети.............. 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
479
10.4. Взаимосвязь между различными распределениями вероятно-
стей ........................... 445
10.5. Совместные распределения вероятностей.......... 447
10.6. Математические ожидания и моменты случайной величины 451
10.7. Производящая функция моментов............ 454
10.8. Центральная предельная теорема............. 456
10.9. Свертки......................... 4f7
10.10. Случайные (стохастические) процессы........... 459
10.11. г-преобразование..................... 467
Контрольные вопросы...................... 471
Задачи............................ 473
Цена: 300руб.
