Сайт в помощь студенту Грамоте учиться – всегда пригодится


Скачать полностью

ВВЕДЕНИЕ                         

Современное общество можно рассматривать как систему сетей, предназначенных для транспортирования, передачи и распределения электроэнергии, товаров, информации. Возникает проблема проектирования и усовершенствования больших и сложных систем, а также поиска путей их наиболее рационального использования, которая может быть решена с помощью методов сетевого анализа. Эти методы являются мощным математическим средством, с помощью которого могут быть сформулированы и решены многие технические задачи. Наглядность и логическая обоснованность этих методов нередко позволяет выработать новый и довольно естественный подход к решению поставленной задачи, позволяющий определить пути последующего прикладного анализа. Методы сетевого анализа, занимавшие некогда лишь незначительное место в исследовании операций, в настоящее время стали легко реализуемыми на ЭВМ и широко используются на практике при решении важных задач, стоящих перед современными техническими дисциплинами.
Сетевой анализ возник в результате многочисленных исследований. В значительной степени он основан на теории графов. Основные принципы сетевого анализа были сформулированы Максвеллом и Кирхгофом в девятнадцатом веке как результат исследований электрических цепей. С тех пор сетевой анализ стал широко использоваться при изучении электрических систем. В начале двадцатого века европейскими и американскими инженерами были разработаны методы расчета наибольшей пропускной способности телефонных линий и коммутаторов, позволяющие обеспечить гарантированное обслуживание определенного числа абонентов. В сороковых годах был получен ряд математических методов анализа больших систем. Первые работы по современному сетевому анализу были написаны Хитчкоком в 1941 г. и Купмансом в 1947 г. В пятидесятых и начале шестидесятых годов основное внимание уделялось построению новых моделей и разработке новых алгоритмов. Развитие вычислительной техники дало сильный толчок разработке и применению на практике новых сетевых алгоритмов, так как была устранена основная проблема при их реализации – вычислительные трудности. В настоящее время сетевые модели широко применяются в исследовании операций и могут быть использованы на практике, например, при проектировании больших оросительных систем, вычислительных комплексов, транспортных сетей, телетрансляционных сетей, систем космической связи. Для решения практических задач, связанных со складированием и распределением товаров, календарным планированием, заменой оборудования, контролем за уровнем издержек, перевозками, работой систем массового обслуживания, обеспечением ритмичности производственного процесса, управлением запасами, распределением рабочей силы, а также многих других задач разработаны эффективные алгоритмы, основанные на методах сетевого анализа.
Сетевой анализ не является дисциплиной, принадлежащей какой-то одной области науки или отрасли производства. Основное достоинство сетевого подхода заключается в том, что он может быть успешно применен к решению практически любой задачи, когда исследователь обладает необходимыми знаниями и способностью точно построить сетевую модель. Сетевые модели могут быть как детерминированными, так и стохастическими, имеющими детерминированный аналог; как статическими, так и динамическими. Динамические модели возникают в тех случаях, когда узлы сети соответствуют временным периодам или комбинациям «момент времени – место расположения».
Большинство потоковых задач, рассмотренных в этом учебном пособии, могут быть сформулированы как задачи линейного программирования (ЛП) и решены соответствующими методами. Однако, специфика структуры потоковых моделей позволяет находить более эффективные алгоритмы поиска решения, чем симплекс-метод. Эти алгоритмы позволяют решать задачи ЛП большой размерности за время, меньшее среднего времени решения подобных задач.
В настоящем учебном пособии рассмотрены некоторые детерминированные потоковые модели, часто используемые при постановке и решении важных экономических и инженерных задач. Для каждой рассмотренной задачи описан эффективный алгоритм ее решения. Приведены следующие алгоритмы: алгоритм Дейкстры решения задачи о кратчайшей цепи; алгоритм Флойда решения задачи о многополюсной кратчайшей цепи; алгоритм построения кратчайшего остовного дерева; алгоритм нахождения максимального потока (метод расстановки пометок Форда – Фалкерсона); алгоритм нахождения многополюсного максимального потока (алгоритм Гомори – Ху); алгоритм нахождения многополюсной цепи с максимальной пропускной способностью; методы управления проектами (ПЕРТ и МКП), алгоритм дефекта.