Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 11
Текст из файла (страница 11)
Поэтому большое значение имеет изучение вопросов, связанных со сведением некоторых практических задач к сетевым задачам и разработкой вычислительных алгоритмов поиска решений этих задач. Данной теме посвящены последующие разделы книги. 2.3. ЗАДАЧА О КРАТЧАЙШЕЙ ЦЕПИ. АЛГОРИТМ ДЕЙКСТРЫ Исходя из применения на практике, одной из наиболее важных потоковых задач является задача нахождения цепи из источника в сток, минимивирующей стоимость (время) прохождения потока заданной величины по данной цепи. Предположим, что каждой дуге (1, 1) ориентированной сети поставлено в соответствие некоторое число ссь называемое обобщенной стоимостью дуги. Фиктивным, или «бесплатным», дугам приписывается стоимость си=О, а каждой паре узлов (й 1), для которых не существует дуги, соединяющей их, приписыва- Н н утверждению, сформулированному после теоремы 4.
— Прим. перев. Детерминированные потоки в сетях ется стоимость сн=оо. Задача, решаемая в данном разделе, состоит в нахождении в заданной сети такой цепи из источника з в сток 1, для которой стоимость прохождения единицы потока по этой цепи минимальна. Математически эта задача может быть записана как следующая задача ЛП: минимизировать )' ~~!' с /!е!/ / (2.45) при условии, что (2.46) (2.4?) (2.48) (2.49) Согласно первому равенству, единица потока вытекает из источника.
Второе равенство гарантирует сохранение данной единицы потока при протекании по сети. Согласно третьему равенству, единица потока втекает в сток. В качестве кратчайшей цепи может быть взята последовательность смежных дуг (!, 1), для которых ///=1. Для решения сформулированной нами задачи линейного программирования мы воспользуемся специальным методом, известным под названием алгоритма Дейкстры !11). Данный алгоритм был разработан с целью использовать специфику рассматриваемой модели. Предположим, что стоимость каждой дуги, или расстояние между двумя узлами, выражается неотрицательным числом сн. Алгоритм основан на приписывании узлам либо вре/иенных, либо постоянных пометок. Первоначально каждому узлу, исключая источник, приписывается временная пометка, соответствующая длине кратчайшей дуги, ведущей из источника в данный узел.
Источнику приписывается постоянная пометка, значение которой равно нулю. Каждому узлу, в который нельзя попасть непосредственно вз источника, приписывается временная пометка оо, а всем остальным узлам — временные пометки с.;, )чьз. Если определено, что узел принадлежит кратчайшей цепи, его пометка становится постоянной. Алгоритм основан иа следующем простом факте: если известна кратчайшая цепь из узла з в узел 1 и узел й принадлежит этой цепи, то кратчайшая цепь из з в й является частью первоначальной цепи, оканчивающейся в узле й. Алгоритм начинает, работать при 56 Глава 2 1=з.
Затем величина 1 последовательно увеличивается на еди- ницу, и при 1'=1 алгоритм завершает работу. 2.3.1. ИТЕРАТИВНАЯ ПРОЦЕДУРА Для заданного узла 1 через б; будем обозначать оценку длины кратчайшей цепи из источника з в узел /. Если эта оценка не может быть улучшена, то соответствующее значение мы назовем «постоянной пометкой» и будем обозначать ее символом Н . В противном случае назовем его «времен- ной пометкой». Вначале процедуры постоянная пометка приписывается только источнику. Каждая другая пометка является временной и ее величина равна длине дуги, ведущей из источника в,соответствующий узел, Для определения ближайшего к источнику узла выберем временную пометку с минимальным значением и объявим ее постоянной пометкой. Затем, до тех пор пока стоку не будет приписана постоянная пометка, необходимо выполнить следующие две процедуры: 1.
Рассмотреть оставшиеся узлы с временной пометкой. Сравнить величину каждой временной пометки с срммой величины последней из постоянных пометок и длины дуги, ведущей из соответствующего постоянно помеченного узла в рассматриваемый узел. Минимальная из двух сравниваемых величин определяется как новая временная пометка рассматриваемого узла.
Отметим, что если величина старой временной пометки меньше второй из сравниваемых величин, то пометка остается прежней. 2. Среди временных пометок выбрать ту, значение которой минимально, и объявить ее постоянной пометкой. Если при этом постоянная пометка приписывается узлу Г, то алгоритм завершает работу. В противном случае перейти на шаг 1. Данная процедура может быть выполнена с помощью таблицы решения, в которой столбцы соответствуют узлам сети, строки— шагам итеративного процесса, а ее элементы — постоянным и временным пометкам. 2.3.2. ПРИМЕР, ИЛЛЮСТРИРУЮЩИЙ РАБОТУ АЛГОРИТМА ДЕЙКСТРЫ В данном разделе мы продемонстрируем работу алгоритма Дейкстры на примере, изображенном на рис.
2.11. Узел з здесь является источником, 1 — стоком, а числа сн, приписанные дугам, соответствуют их длине нли стоимости. Детериинированныв потоки в сетях Работа алгоритма начинается с того, что источнику зпри П0, а узлам /=1, 2,...,6, писывается постоянная пометка г — временные пометки бг=сеп Таким образом, 61=0 и 6;=со длЯ 1=2,...,1. ПосколькУ значение бг=0 ЯвлЯетсЯ минимальным среди всех временных пометок, узлу 1 приписывается постоян- ная пометка Узлы 2 и 3 непосредственно связаны с узлом 1, последним из постоянно помеченных узлов.
Отметим, что 6~+с,т — — О+3<оо Рис, 2.11. Сетевая модель для иллюстрации алгоритма Дейкстры. и 61+си=0+7<со. Поэтому узлам 2 в 3 приписываются новые временные пометки ба=3 и ба=7 соответственно. Поскольку ба<ба, узлу 2 приписывается постоянная пометка Узлы 3 и 6 непосредственно связаны с узлом 2. Кроме того, бт+сгз=3+2=5<7 и ба+сто=3+1=4<со. Поэтому узлам 3 и б пРиписываютсЯ новые вРеменные пометки ба=5 и бе=4 соответственно. Поскольку бе<ба, узел 6 становится помеченным постоянно, т.
е. бе= П4 На данном шаге временными являются пометки 'ба=5 и бе=ба=бг=оо. Последним узлом, которому была приписана постоянная пометка, является узел б. Он непосредственно связан только с узлом 4. Отметим, что ба+саг=4+2=6<оо. Следовательно, узлу 4 приписывается новая временная пометка бе=6. Поскольку ба — — пнп (ба, бе бю бгг, узлу 3 приписы- Глава 2 вается постоянная пометка бз= и .
Аналогично проведем дальнейшие вычисления. Алгоритм заканчивает работу, когда узлу 2 приписывается постоянная пометка. Промежуточные результаты, полученные при решении данной задачи, приводятся в табл. 2.4. Таблица 2.4. Результаты вычислений в задаче, решенной с помощью алгоритма Дейкстры Как видно из табл. 2.4, узлу Т приписывается постоянная пометка бс= Я, . Следовательно, длина кратчайшей цепи нз узла з в узел 2 равна 7. Эта цепь состоит из дуг, для каждой из которых разность между значениями постоянных пометок ее концевых узлов, равна длине этой дуги. Иными слова- ми, если ~д~ и ~Я вЂ” постоянные пометки узлов г и 1 соответственно, то условие, при выполнении которого эти узлы принадлежат кратчайшей цепи, может быть записано следующим образом: бт= б,+см.
~2.50) 39 Детермииироеаавае потоки е сетях Соотношение (2.50) можно использовать рекурсивно, двигаясь от узла 1 к узлу з. Определив узел, непосредственно предшествующий г в кратчайшей цепи, будем повторять данную процедуру до тех пор, пока не достигнем узла з. Можно показать, что кратчайшая цепь в рассмотренной нами сети образуется последовательностью узлов з — 1 — 2 — 6 — 4 — 5 — й 2.3.3. СВЕДЕНИЕ ЗАДАЧИ О ПОКУПКЕ АВТОМОБИЛЯ К ЗАДАЧЕ О КРАТЧАИШЕИ ЦЕПИ При решении вопроса о том, когда следует производить покупку нового автомобиля, необходимо учитывать его стоимость и возрастающие эксплуатационные расходы. В данном разделе мы воспользуемся алгоритмом поиска кратчайшей цепи для Рнс.
2.12. Покупка нового автомобиля. решения задачи, в которой требуется определить, как часто в течение восьмилетнего периода следует заменять автомобиль, чтобы минимизировать при этом общие затраты. Предполага. ется, что решение о покупке нового автомобиля может приниматься в начале каждого года, исходя из затрат на его приобретение, эксплуатационных расходов на период, в течение которого автомобиль будет использоваться, и ликвидационной стоимости машины в момент, когда она заменяется на новую.
Предположим, что в начальный момент человек не имеет автомобиля и что он собирается покупать новый автомобиль по крайней мере каждые 4 года. На рис. 2.12 изображена сеть для рассматриваемой задачи. Началу каждого года соответствует узел. Если покупка автомобиля цроиэводится в начале есго года, а в начале 1'-го года автомобиль заменяется на новый, то данному варианту замены соответствует дуга 15 1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
