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

Мы стремились использовать знания и опыт многих специалистов в этой области. Некоторые из них непосредственно участвовали в написании книги. Часть материала гл. 2 н, в частности, многие практические примеры были предоставлены нам доктором Г. Е. Беннинггоном.

Часть материала гл. 3, касающегося алгоритма дефекта, была взята нз лекций доктора Поля А. Йенсена, а некоторые примеры были предоставлены нам доктором Вулсеем и доктором Хантером Суонсоном. Ббльшую часть материала, касающегося вычислительных аспектов систем ПЕРТ и МКП (гл, 4, ч. 1), предоставил доктор Уорэи Томас. Весь материал раздела гл. 4, связанный с управлением ресурсами, был предоставлен доктором Эдвардом Дэвисом, а материал гл.

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

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

Йенсена и доктора Вулсея. Оии поймут н примут нашу особую благодарность за их неоценимую поддержку при написании книги. Особую благодарность за всестороннюю критику и участие при написании книги заслуживает доктор Джеймс Эванс. Доктор Эванс прочитал первый вариант рукописи и сделал много ценных замечаний, за которые мы ему очень признательны. Мы были бы несправедливы, если бы не поблагодарили Джен Бертч и Кэнди Филлипс, перепечатавших рукопись и испытавших немало волнений, когда материал был собран. Мы также в большом долгу перед Американским институтом инженеров-технологов, давшим разрешение на перепечатку опубликованного материала. Дои Т.

Филлипс, доктор философии, инженер-нефтякик Альберто Гарсиа-Диас, доктор философии КолледхеСгешаен, Техас Глава 1 ВВЕДЕНИŠ— Чеширский Мурлыка...,— заговорила Алиса несмело. — Скажите, пожалуйста, куда мне отсюда идти? — Это во многом зависит от того, куда ты хочешь прийти,— ответил Кот. — Ла мне почти зсе равно,— начала Алиса. — Тогда все равно, куда идти, — сказал Кот.

— Лишь бы попасть куда-нибудь, — пояснила Алиса. Л. Кэрролл. Приключения Алисы в стране чудес'> По остроумному замечанию Чеширского Кота вперед можно продвинуться, даже если просто скитаться без определенной цели. Однако для поиска оптимального решения часто существуют более разумные методы, чем тот, который избрала Алиса, блуждая по стране чудес. В частности, сетевое моделирование предоставляет такие теоретические результаты и вычислительные алгоритмы, которые позволяют в значительной степени усовершенствовать ряд традиционных подходов системного анализа.

В настоящей главе вводятся понятия, необходимые для понимания и практического применения основных алгоритмов, содержащихся в данной книге, Конечно, при практическом использовании методов сетевого анализа часто встает не только вопрос о том, «до какого места Вы хотите дойти», но и вопрос о том, «какой путь следует избрать». Надеемся, что настоящая глава поможет при ответе на оба этих вопроса.

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

Методы сетевого анализа, занимавшие некогда лишь незначительное место в исследовании операций, в настоящее время стали легко реализуемыми на ЭВМ и широко используются на практике при решении важных задач, стоящих перед современными техническими дисциплинами. Сетевой анализ возник в результате многочисленных исследований. В значительной степени он основан на теории графов — области математики, источником развития которой явилась известная задача о Кенигсбергских мостах, сформулированная и решенная Леонардом Эйлером в 1736 г. [7].

Спустя более века Джеймс Клерк Максвелл и Густав Роберт Кирхгоф, исследуя электрические цепи, сформулировали некоторые основные принципы сетевого анализа. С тех пор сетевой анализ стал широко использоваться при изучении электрических систем. В начале ХХ в, европейскими и американскими инженерами были разработаны методы расчета наибольшей пропускной способности телефонных линий и коммутаторов, позволяющие обеспечить гарантированное обслуживание определенного числа абонентов. В сороковых годах, во время второй мировой войны, в ~результате развития теории исследования операций был получен ряд математических методов, необходимых для анализа больших систем. Первые работы по современному сетевому анализу были написаны Хитчкоком [11] в 1941 г. и Купмансом [15) в 1947 г.

С тех пор в области сетевого анализа было проведено большое количество плодотворных исследований и опубликовано свыше тысячи печатных работ. В пятидесятых и начале шестидесятых годов основное внимание уделялось построению новых моделей и разработке новых алгоритмов. Позднее стали проводить более глубокие исследования построенных .ранее моделей и искать пути реализации алгоритмов на вычислительной машине. Был издан ряд обзорных статей, написанных такими авторами, как Фалкерсон [10], Элмаграби [6], Брэдли 1[2], Магнанти и Голден [16] и др. С развитием сетевого анализа возникла необходимость в книгах, которые бы отражали различные направления исследований, проводимых в данной области. Ряд книг, содержащих наиболее полное изложение вопросов, связанных с сетями, написали Форд и Фалкерсон [8], Чарнес и Купер [4], Данциг [5], Басакер и Саати [3), Ху [12), Фрэнк и Фриш [9), Введение Уайтхаус 1211 и позднее Р1енсен и Барнес 1141, Базарра и Джарвис 111, Майника 1171.

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

Притскер [201 дает следующее объяснение широкому применению на практике методов сетевого анализа: «Сетевой анализ играет всевозрастающую роль как при описании управляюших систем, так и при их усовершенствовании. В первую очередь это связано с тем, что с помощью сетей можно довольно просто построить модель системы. Кроме того, расширение области использования сетей связано с тем, что методы сетевого анализа позволяют 1.

Построить модель сложной системы как совокупности простых систем. 2. Составить формальные процедуры для определения качественных характеристик системы. 3. Указать механизм взаимодействия компонентов управляющей системы с целью описания последней в терминах ее основных характеристик. 4. Определить, какие данные необходимы для исследования системы. 5.

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