Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (Методы анализа сетей. Филлипс. Гарсиа-Диас (1981).djvu)

Д. ФИЛЛИПС, А. ГАРСИ йгДИАС МЕТОД АНАЛ СЕТЕЙ Перевод с английского Е. Г. Коваленко, М. Г. Фуругнна, под редакцией Б. Г. Сушкова Москва «Мир» 1984 Филлипс Д., Гарсиа-Диас А. Ф52 Методы анализа сетей: Пес. с англ.— Мл Мнр, 1984.— 496 с., нл. В кинге американских ученых излагаются методы и алгоритмы оптимизации детерммнированных и стохастическнх сетей различного назначения с помошью теории графов. Книга иллюстрирована большим числом примеров, взятых нз раз. личных областей науки и техники. Для специалистов, занимзюжихся применением вычислительной техники в экономике, планировании, биологии и медицине. Может быть использована аспирантами н студентами соответствующих специальностей.

1802000000-242 0411011 84 7-84, ч. 1 ББК 22.18 Б18 Редакция литературы по новой технике Дон Т. Филлипс, Альберто Гарсиа-Диас МЕТОДЫ АНАЛИЗА СЕТЕЙ ИБ % 3709 Сдано в набор 31.10.83 Сдано в печать 14.03.84. Бумага типографская уй 2. Формат 60Х900ш Гарнитура латинская. Печать высокая. Объем 15,5 бум. л. Уел. печ. л. 31,0 Уч.-нзд. л. 28,65. Уел. кр.-отт.

31,0 Тираж 10000 экз. Пена 2 р. 30 к. Зак. 1654. Издательство «Мир». 129620. ГСП, Москва, И.!10. 1-й Рижский пер., 2. Московская типография М 11 Союзполиграфп1юма при Государственном комитете СССР по делан издательств, полиграфии и книжной торговли. 1!3105, Москва, Нагатинская ул., д. 1. ББК 22.18 Ф52 УДК 519.95:62-50 Научный редактор Т. Н. Шестакова Младший научный редактор Е. П. Орлова Художественный редактор В. Б. Прищепа Технический редактор Т. А. Максимова Корректор С. А. Денисова "ау Ртеп1106-Н311, 1пс., Епе!ешоод СШ19, 1981 © Перевод ий русский язык, сМир», 1984 ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА Успехи прикладной математики в количественном анализе сложных реаль" цых систем и явлений существенно определяются двумя обстоятельствами: возможностью построения математической модели исследуемого процесса, адекватно отображающей реальность, и существованием математических средств исследования построенной модели.

По мере накопления все большего числа удачных попыток применения тех илн иных математических объектом для изучения реальных событий наступает качественно новый этап в развитии конкретной области науки: появляется формальный математический язык для описания исследуемых явлений. Формальные объекты этого языка становятся предметом исследования математиков, зачастую полностью абстрагирующихся от предметной области, к которой этн объекты поначалу относились, появляются обладающие большой общностью методы расчета этих объектов. Негативной стороной этого процесса является усложнение вводимых понятий и построений, затрудняющее использование полученных результатов специалистамн из конкретных областей, не обладающими профессиональной математической подготовкой.

Подобную эволюцию испытали н методы анализа сетей, берущие свое начало из сформулированных Г. Р. Кирхгофом законов протекания электрического тока в системах разветвляющихся проводников. В настоящее время область применения этих методов чрезвычайно широка. К примеру, она включает в себя проектирование сложных систем связи, исследование транспортных потоков, передачу информации в вычислительных системах, анализ путей материального снабжения современных заводов, финансовые операции.

Соответственно, развились и усложнились методы численного анализа сетевых моделей. Предлагаемая вниманию читателей книга является удачным сочетанием полноты, строгости, ясности и доступности в изложении. Авторы добились этого двумя путями. С одной стороны, книга содержит описание практически всех современных методов исследования сетей. Причем большинство ундаментальных свойств этих методов строго доказано и обосновано. другой стороны, в книге приведено большое количество конкретных практических задач из различных областей человеческой деятельности. Чрезвычайно важно, что в этих примерах представлены все этапы решения задачи, включая ее постановку, построение соответствующей сетевой модели, выбор алгоритма решения, получение численных результатов н нх анализ с целью выработки рекомендаций, улучшающих исследуемую систему.

Многочисленные упРажнения должны стимулировать читателя к самостоятельному проведению подобной работы для анализа самых различных объектов и явлений, начиная от выбора рационального маршрута развлекательной поездки вплоть до Решения таких серьезных практических задач, как проектирование разветвленных систем транспортировки нефти от приисков к нефтеперерабатывающим заводам н потребителям. Весьма ценным приложением является библиотека стандартных программ на языке ФОРТРАН, реализующая наиболее употребительные методы анализа сетей.

Каждая глава книги содержит обширную библиографию, включающую основополагающие работы по проблематике данной главы. К сожалению, в этой библиографии практически не отражены достижения советской школы Предисловие редактора перевода дискретной оптимизации. Для примера можно привести результаты В.

С. Танаева, В. В. Шкурбы, Е. Г. Гольштейна, Д. Б. Юдина, В. С. Михалевича, А. И. Куксы, А. А. Корбута, Э. Г. Давыдова, Г. М. Адельсона-Вельского и многнх других. Можно с уверенностью утверждать, что книга послужит хорошим подспорьем для математиков, специализирующихся в области разработки методов дискретного анализа, руководством к практическому применению сетевых методов для специалистов в прикладных областях, учебным пособием для студентов и аспирантов, изучающих численные методы анализа сетей.

Б. Г. Сушков Перевод книги выполнили М. Г. Фуругян (гзь 1 — 3, 5) и Е. Г. Коваленко (гл. 4). ПРЕДИСЛОВИЕ Эта книга является работой, в которой всесторонне рассмотрены вопросы теории и методов вычислений детерминированных потоков в сетях. Книга написана иа основе лекций, которые читались в течение 10 лет и были составлены самими авторами, а также с использованием многочисленных научных статей и трудов ведущих специалистов в этой области. Основная направленность книги — практический подход к разработке и реализации потоковых алгоритмов. Рискуя подвергнуться критике со стороны своих коллег, мы иногда не останавливались на изложении теоретических результатов н проведении математических доказательств, а рассматривали лишь вычислительную сторону изучаемого вопроса.

При рассмотрении каждой задачи вначале, если это уместно, дается ее формулировка в виде задачи линейного программирования, а затем описывается алгоритм ее решения, являющийся более быстрым и более эффективным по сравнению с процедурой, основанной на непосредственном использовании математической модели Каждый алгоритм используется для решения одной или нескольких практических задач. Особенностью книги является наличие в ней описаний и листингов программ сетевой оптимизации, написанных на языке ФОРТРАН 1Ч, которые применимы к решению задач малой и средней размерности. Программы могут быть использованы как в целях обучения, так н при проведении исследовательской работы.

Эта книга представляет собой введение в теорию сетевых потоков и окажется полезной студентам н аспирантам в качестве учебника по вводному курсу сетевого анализа. Для понимания материала, содержащегося в книге, не требуется специальной математической подготовки. Однако полезным было бы некоторое знакомство с обозначениями, используемыми в линейном программировании, и языком ФОРТРАН, но и оно не является необходимым для понимания описанных алгоритмов.

Нам было приятно отметить, что за последние 1О лет интерес к теории и приложениям потоковых алгоритмов значительно возрос. В области образования, по-видимому, не существует такого предмета, который не включал бы в себя сетевой анализ; он постоянно находит применение в управлении частными предприятиями и компаниями, во всех технических науках, при проектировании транспортных систем, в области планирования и управления работами над проектом, при составлении расписаний и во многих других областях. Основное достоинство сетевых моделей заключается в их гибкости н возможности графического их описания. Кроме того, сетевые процедуры поиска решений, которые были разработаны сравнительно недавно, являются значительно более эффективными, чем обычные методы линейного программирования.

Основным препятствием на пути широкого распространения и применения сетевого анализа, безусловно, являются трудности, возникающие при формализации языка. За небольшим исключением, все предыдущие научные и технические разработки в данной области велись на основе теории графов и математического программирования. Полученные результаты обычно излагались в научных статьях и докладах. В этой книге мы стремились избежать излишней математической строгости и рассмотреть основные вопросы сетевого анализа неформальным образом. Книга состоит из пяти глав и приложения. В гл, 1 вводятся используемые в дальнейшем обозначения и даются определения, связанные с со- Предисловие держанием последующих глав, Гл.

2 посвящена всестороннему изучению детерминированных потоков в сетях. Она начинается с рассмотрения ряда примеров, иллюстрирующих разнообразие сетевых постановок практических задач. В ней решается большое число различных примеров, а для решения шрактичсских задач большей размерности дается описание программ, написанных иа языке ФОРТРАН Г'е, Гл.

3 содержит унифицированное и исчерпывающее описание изящного алгоритма дефекта, а также подробное рассмотрение вопросов теоретического и вычислительного характера, связанных с этим мощным методом. В этой главе читателю предлагаются многочисленные прилозкения метода, а для иллюстрации процедур построения модели рассматривается несколько задач. В гл. 4 дается полное описание процедур планирования и управления проектом, основанных на системах ПЕРТ н МКП.

В этой главе подробно рассматриваются вопросы распределения ресурсов и регулирования потребления, а также описываются методы вычислений и машинные процедуры. В гл. 5 изучаются общие постановни задач: потоки в сетях с выигрышами и проигрышами, ГЕРТ-процедуры для стохастических сетей, имеющих специальную структуру, и многопродуктовые потоки. В приложении дается полный текст программ сетевой оптимизации н инструкции по их использованию.