Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 6
Текст из файла (страница 6)
РЫ11!рв О. Т., апач!пдгап А., 8о(Ьег8 Л. Л., Орега1!опв йевеагсЬ: Рг!пс!р1ев апй РгасВсе, %!!еу, 1пс., Ыем УогЬ, 1977. 19. Роев К. В., 01!чег й. М., Р!отче 1п Тгапврог1аВоп г!е!тчогЬв, АсайегЫс Ргевв, 1пс., Меаг УогЬ, 1972. 20. Рг!1вКег А. А. В., Нарр %. 97., СЕЕТ: Раг1 1 — Рипдагпеп!а!в, Уоигпа! ог упг(ив!с!а! Епд!пееПп8, 17 (5), 267 (1966). 21. 7КЫ!еЛоиве б. Тч'., Вув1егав Апа!ув!в апд Оев!8п Бв!п8 Не!чгогЬ ТесЬп!опав, РгепВсе-На11, 1пс., Еп81етчоод С1!1!в, Х.
Л., 1973. Глава 2 ДЕТЕРМИНИРОВАННЫЕ ПОТОКИ В СЕТЯХ Кролик Питер скорчил рожу Скунсу Джимми: Я не люблю, когда меня поучают. Я ие поучаю: я просто говорю, что Вам следует знать без всяких объяснений,— ответил Скунс Джимми, Т. Баргес. Приключения кролика Питера В настоящей главе рассматриваются некоторые детерминированные пото- новые модели, часто используемые при постановке и решении важных экономических и инженерных задач.
Для каждой рассматриваемой задачи описан эффективный алгоритм ее решения. В числе рассмотренных будут следующие: 1. Алгоритм Дейкстры решения задачи о кратчайшей цепи [1Ц. 2. Алгоритм поиска многополюсной кратчайшей цепи [ЗЦ. 3. Алгоритм поиска кратчайшего пути для решения класса задач с фиксированными платежами [4Ц. 4. Алгоритм двойного поиска для решения задачи о К кратчайших путях [47]. 5.
Алгоритм построения кратчайшего остова (ЗЦ. 6. Метод ветвей и границ для решения задачи коммивояжера [40]. 7. Алгоритм нахождения максимального потока [15]. 8. Алгоритм нахождения многополюсного максимального потока [ЗЦ. 9. Алгоритм нахождения многополюсной цепи с максимальной пропускной способностью [32]. 10.
Алгоритм нахождения числа узлов и дуг, исключение которых из сети приводит к ее разрыву [18]. Кроме того, для более глубокого понимания принципов работы указанных алгоритмов мы остановимся на нескольких специальных. В главе большое внимание уделяется рассмотрению конкретных примеров. Для каждой изучаемой проблемы дается общее описание, математическая постановка и затем — описание алгоритма решения. Для иллюстрации основных понятий и методов вычислений, используемых в каждом нз описанных алгоритмов, рассматриваются и решаются вручную одни или несколько примеров.
Затем формулируется некоторая задача, решение которой может быть получено с помощью специальной программы, написанной на языке ФОРТРАН АНСИ. Каждая программа содержит раздел с документацией и инструкциями для пользователя. В ряде случаев на модельных примерах удается получить дополнительные результаты, касающиеся изучаемой проблемы. Тексты ФОРТРАН-программ приводятся в приложении. Глава 2 2Л. ПРИЛОЖЕНИЯ ПОТОКОВЫХ МОДЕЛЕЙо В данном разделе будут рассмотрены задачи, при решении которых используются потоковые алгоритмы.
Это познакомит читателя с сетевым моделированием и сообщит ему основные сведения, необходимые для эффективного использования сетевых алгоритмов. 2.1.1. ЗАМЕНА ОБОРУДОВАНИЯ В инженерном проектировании и прикладном анализе часто встречаются задачи, которые могут быть сформулированы в виде задач о кратчайшей цепи. Задача о кратчайшей цепи заключается в следующем. Заданы множества узлов и дуг. Каждой дуге 11, )) поставлена в соответствие величина сн, равная стоимости единицы потока по этой дуге. Требуется найти цепь из источника з в сток 1, минимизирующую стоимость единицы потока, протекающего из з в Е В качестве примера рассмотрим задачу периодической замены оборудования.
Для удобства будем предполагать, что вышедшее из строя оборудование предпочтительнее заменить на новое, чем отремонтировать его. Предполагается также, что после трех лет работы в поточной линии оборудование устаревает и в дальнейшем не может быть использовано. Ликввдационная стоимость при различных сроках службы оборудования, а также эксплуатационные, расходы и расходы на техническое обслуживание и текущий ремонт в каждый промежуток времени считаются известными. Обозначим узлом начало каждого планируемого периода. Тогда заданный период полезного срока службы оборудования может быть обозначен дугой.
Данная информация позволяет вычис.лить величину сн в виде суммы затрат на приобретение нового оборудования в начале периода 1 и торговых издержек в конце периода / — 1 (или в начале периода /). Эта величина рассматривается как «длина» дуги 11, 1). Множество всех планов замены оборудования за л — 1 год может быть представлено совокупностью цепей сети, изображенной на рис. 2.1 (п=4). Каждый узел сети соответствует началу планируемого периода; узел 4 соответствует концу планируемого периода. Каждая ориентированная цепь из узла 1 в узел 4 представляет собой план замены оборудования на трехлетний период. Цепь 11, 3), (3, 4) соответствует закупке оборудования в начале первого периода, его содержанию в течение двух лет и его продаже в конце второго периода.
Затем в " Часть материала данного раздела была заимствована у Бениингтона Г. Е. и пеРепечатана с разрегвення Ашепсап 1пзщше о1 1пдпз1ба1 Епя1- пеегз 14). Детерминированные нагони в сетях начале третьего периода закупается новое оборудование, которое продается в конце этого же периода. Для данного плана замены оборудования общие затраты составляют е,з+сз4. Кратчайшая цепь из узла 1 в узел 4 в данной сети будет соответствовать плану с минимальными затратами на рассмотренные тр.и периода.
Сделаем несколько замечаний. Нами была рассмотрена временная, или ди~намическая, модель, в которой временные с! ° Рнс, 2.1. Сеть планов замены оборудования. периоды представлены узлами сети. Поскольку в начале первого периода оборудование следует закупить, а в конце периода планирования его следует продать, то все цепи в сети должны вести из узла 1 в узел 4. Модели подобного типа называются моделями с конечным планируемым периодом. Задачи о кратчайшей цепи рассматриваются в равд. 2.3 и 2.4.
2.1.2. ПЛАНИРОВАНИЕ РАБОТ ПО ОСУЩЕСТВЛЕНИЮ ПРОЕКТА Значительное место в теории сетей занимают задачи, связанные с планированием и составлением расписания выполнения работ по осуществлению больших проектов, таких, как запуск космических кораблей, проведение научных исследований и опытных разработок, организация сложных конструкторских разработок. В рассматриваемой модели проект представляется множеством работ и заданными между ними отношениями~ предшествования.
Время 4 выполнения каждой работы известно. Кроме того, прежде чем |работа может начаться, все предшествующие ей работы должны быть завершены. Предположим, например, что заданы пять работ и что работа 1 предшествует работе З,,работы 1, 2 предшествуют работе 4, а работы 1, 2, 3 и 4 предшествуют работе 5. Данная совокупность работ может быть представлена сетью, изображенной на Рис. 2.2.
Для обозначения начала и завершения проекта вводятся два фиктивных узла. Остальные узлы соответствуют началу выполнения рассматриваемых работ. Если работа 1 мо- 32 Глава 2 жет быть начата непосредственно после окончания, работы 1, то в сеть включается дуга !'1, !) длиной А. Поскольку работа 1 предшествует работе 3, которая в свою очередь предшествует,работе 5, то дуга (1, 5) в сеть не включается.
Длина максимальной цепи из начального узла сети в некоторый задан- На про ение Рис. 2,2. Сетевая модель узел — работа. ный узел ! соответствует самому раннему сроку начала выполнения работы й Поэтому длина максимальной цепи .из начального узла сети в конечный узел соответствует минимальному времени осуществления проекта. Если сеть содержит контуры положительной длины, то задача нахождения максимальной цепи, не содержащей конту- ршение кта Рис. 2.3. Сетевая модель дуга — работа. ров, является весьма сложной. Рассматриваемая нами сеть проекта не содержит контуров, и цепь максимальной длины определяется несложно. Рассмотренная модель называется моделью узел — работа, поскольку началу выполнения каждой работы соответствует узел. В другой сетевой модели, называемой лгоделью дуга— узабота, каждая работа представляется дугой.
Соответствующая сеть рассматриваемого нами проекта изображена на рис. 2.3. Числа, приписанные дугам, обозначают номера соответствующих .работ. Пунктирной стрелкой обозначена фиктивная работа нулевой продолжительности, введенная для того, чтобы, работа 1 предшествовала .работе 4. Каждый узел в данной сети соответствует некоторому событию, например завершению закладки фундамента при строительстве здания. В общем случае пред- Детерминированные потоки в сетях полагается, что событие является точно определенным во времени.
Как и раньше, длина максимальной цепи из начального узла сети проекта в конечный узел равна минимальному времени осуществления проекта. Метод планирования работ по осуществлению проекта, использующий сетевое представление совокупности, работ, называется методом критического луги (МКП). Впервые он был разработан Дюпоном и Ремингтоном Рандом для управления .работой химических заводов. Цепь максимальной длины называется критическим путем потому, что задержка в выполнении любой работы, принадлежащей этому пути, приведет к увеличению времени осуществления проекта. Аналогичный метод был независимо, разработан для построения стохастической модели управления научными исследованиями и опытными разработками, которая использовалась при создании ракетной системы «Поларис».
Этот метод называется методом оценки и пересмотра планов (ПЕРТ). Он позволяет получить оценку среднего времени выполнения проекта н дисперсию этой оценки. Процедуры поиска решения в системах МКП и ПЕРТ описаны в гл. 4. 2.1.3. СОСТАВЛЕНИЕ РАСПИСАНИЯ ДВИЖЕНИЯ ГРУЗОВОГО СУДНА Предположим, что имеется грузовое судно и требуется составить оптимальный график прибытия в порты. Рассмотрим сеть, в которой узлы соответствуют портам, а стоимость сн дуги (1, /) равна затратам на транспортировку груза из порта 1 в порт З,1 / за время /н, которое включает в 1 себя время, необходимое для погрузки судна в порту й перевозки груза из порта ( в порт /' и разгруз- 1 2,2 -а,з ки судна в порту /.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
