Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 14
Текст из файла (страница 14)
Для иллюстрации результатов, приведенных в табл. 2.6, рассмотрим кратчайшую цепь из узла 1 в узел 5. Длина этой цепи равна ам!3=9. Для того чтобы найти соответствующую последовательность узлов, обратимся к матрице Кз. Поскольку значение т'м равно 4, то узел 4 является первым промежуточным узлом в кратчайшей пепи из узла 1 в узел 5. Затем, для того чтобы найти узел, следующий за узлом 4 в цепи, ведущей к узлу 5, мы определяем значение тззз. Данное значение равно 3. Точно так же, поскольку тззз=5, узел 5 следует за узлом 3. Следовательно, кратчайшая цепь из узла 1 в узел 5 определяется последовательностью узлов 1, 4, 3, 5. 9 !3 б !О 4 3 б 1О 0 10 10 0 !О 7 9 12 9 13 б 10 4 8 б 10 0 Ю 10 0 10 7 9 12 8 б 5 о 1О сс 7 0 1О О 8 8 ю б тч 5 ст 10 3 3 3 3 5 б 7 8 3 3 3 4 3 б 7 8 1 2 3 4 5 б 7 8 1 4 4 4 4 4 4 3 4 2 3 3 3 3 3 8 4 2 3 4 5 б 7 8 1 3 3 4 3 3 7 8 4 3 3 3 5 б 3 3 4 3 3 3 5 б 7 3 4 3 3 4 3 б 7 8! 1 2 3 4 5 б 7 8 ~ 1 4 4 4 4 4 4 8 4 2 3 3 3 3 3 8 4 2 3 4 5 б 7 8 1 3 3 4 3 3 7 8 4 3 3 3 5 б 3 8 4 3 3 3 5 б 7 8 4 3 3 4 3 б 7 8 5 5 5 5 5 6 7 8 Остаатся неизменной Оотается неизменной Оставтсяивизмвнной Глава 2 1 2 3 4 5 б 7 З Базовая строка Базовый столбец Рис.
2.17. Элемента, исследуемые (с помощью трехместной операции) на второй итерации. 2.4.2. ПРИМЕНЕНИЕ ЗАДАЧИ О МНОГОПОЛЮСНОЙ КРАТЧАЙШЕЙ ЦЕПИ ПРИ ПРОЕКТИРОВАНИИ СИСТЕМЫ ДОСТАВКИ ПОЧТЫ Крупное учреждение планирует разработать систему внутренней доставки почты, основанную на использовании линий пневматической связи, для распределения корреспонденции между восьмью отделами. Не!е 3 которые отделы будут только отсылать поступающую кор- 3 респонденцию в другие отделы, 2 не имея при этом возможности 4 5 получать почту.
Все остальные отделы смогут отправлять и получать почту без каких-либо 1о э ограничений. Расположение линий, изо- браженное на рис. 2.18, было 6 установлено заранее. Каждый отдел представлен узлом, а э каждая линия — дугой. Ориентированные дуги соответствуют распределительным звеньям, которые могут быть использоРис.
2ЛВ ~петена доставки по"'" ваны для посылки почты толь- ко в указанном направлении. Числа, приписанные дугам, равны расстояниям между соответствующими отделами. Для того чтобы каждый отдел при пересылке почты в дру- гой отдел смог бы определить оптимальный путь, необходимо Детерминированные нотони в еетн» заготовить таблицу, указывающую кратчайшую цепь между каждой парой отделов. Такая таблица может быть построена с помощью алгоритма Флойда. В рассматриваемой задаче (рис. 2.18) начальные значения элементов матрицы длин кратчайших путей и матрицы маршрутов могут быть выбраны следующим образом: 0 3 1О оо оо с со оо со 0 оо 5 оо со оо оо оо оо 0 б оо оо оо оо со 5 б 0 оо оо оо 4 оо оо оо 10 10 оо 5 оо 3 оо ре 0 оо 6 0 1 2 3 4 5 б 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 б 7 8 1 2 3 4 5 б 7 8 1 2 3 4 5 б 7 8 1 2 3 4 5 б 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 б 7 8 Читателю предлагается проверить, что оптимальное решение соответствует следующим матрицам: 0 3 1О 8 оо 0 11 5 с 11 0 .б оо 5 б 0 о 9 10 4 со 17 18 12 оо 15 15 19 оо 20 21 15 4 оо 0 9 9 0 со 3 оо 9 12 20 17 9 17 14 10 18 15 4 12 10 0 8 5 9 0 3 15 3 0 11 9 б 74 Глава л 2 3 2 4 7 5 8 2 4 4 4 7 5 8 4 3 4 4 7 5 8 2 3 4 5 7 5 8 4 4 4 5 7 7 8 7 7 7 7 6 7 8 5 5 5 5 6 7 8 7 7 7 7 6 7 8 Длина кратчайшей цепи из узла 8 в узел 2 равна Рва=20.
Для определения узлов, соответствующих этой цепи, обратимся к матрице йв. Нетрудно заметить, чтогввв=7, гата=5, гввв=4 и гала=2. Следовательно, кратчайшая цепь из узла 8 в узел 2 определяется последовательностью узлов 8, 7, 5, 4, 2. 2.4,3. ОПИСАНИЕ ПРОГРАММЫ, РЕАЛИЗУЮЩЕИ АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ О МНОГОПОЛЮСНОИ КРАТЧАИШЕИ ЦЕПИ Назначение: решение задачи о многополюсной кратчайшей цепи. Локализаций: подпрограмма М11).ТБН в пакете сетевой оптимизации. Ограничения: программа позволяет обрабатывать сети, содержащие до 50 узлов и 50 дуг. Размеры сети можно увеличить, изменив границы массивов в операторах размерности, записанных в подпрограмме М(11ТЗН и в основной программе. Входные данные: Набор 1.
Одна карта с именем алгоритма МТЗС в формате (А4). Набор 2. Одна карта с числом узлов и числом дуг в сети в формате (2110). Набор 3. Общее число карт в данном наборе равно числу дуг в сети. С каждой карты считываются следующие величины: 1) номер начального узла дуги; 2) номер конечного узла дуги; 3) длина дуги. Формат (4Х, 16, 110, Р10.2).
Набор 4. Данный набор состоит из одной карты, содержащей слово 'РЕ)Ч13' в формате (А4), которая указывает конец задачи. Набор 5. Данный набор состоит из одной карты, содержащей слово 'ЕХ1Т' в формате (А4), которая указывает конец входных данных. 75 Детерминированные потоки в сетях Составные части программы. Программа состоит из следующих подпрограмм: М(11.ТЗН (ввод и вычисления); РКВ)ТКХ (печать исходной матрицы); РКХТКУ (печать оптимального решения).
Используемые переменные: ? — начальный узел дуги, )в конечный узел дуги,  — длина дуги, П вЂ” рабочий массив длин дуг. Используемый метод: данный алгоритм основан на методе, в котором в качестве начальной оценки длины кратчайшей цепи из узла 1 в узел К выбирается длина дуги из 1 в К. На ,1-й итерации производится сравнение длины цепи из 1 в К, содержащей промежуточные узлы из множества (1, 2, ..., 1), с длиной цепя, проходящей через узел 1 с промежуточными узламн из множества (1, 2, ..., 1 — 1).
Если использование узла 1 позволяет получить более короткую цепь, то длина последней принимается за новую оценку длины кратчайшей цепи. Литература: [ЗЦ. 2.4.4. СОСТАВЛЕНИЕ МАРШРУТА ПЕРЕГОНА ВАГОНОВ Среди общих расходов на транспортировку груза, поступающего в порт Хьюстон и вывозимого из него, значительную долю составляют затраты на перегон вагонов из одного пункта портового комплекса в другой. В сети, изображенной на рис.
2.!9, узел 1 соответствует станции прибытия поездов, из которой вагоны прибывающих составов перегоняются к различным пунктам назначения в портовом комплексе, обозначенным остальными узлами сети. Числа, приписанные дугам, представляют собой затраты на перегон вагонов по соответствующей ветке, Рассмотрим следующий пример. Поезд состоит из 200 вагонов, 100 из которых хопперы, груженные зерном. Хопперы с зерном должны быть доставлены к элеваторам, расположенным в узлах 3, 6 и 10.
После разгрузки они могут быть либо доставлены на заводы, производящие удобрения (узлы 2, Ь и 8), либо перевезены на станцию отправления (узел 11). Остальные типы вагонов, такие, как крытые товарные вагоны, вагоны-платформы и цистерны, следует доставить в пункты 4, 7 и 9, разгрузить их там и перегнать на станцию отправления. Применение алгоритма решения задачи о многополюсной кратчайшей цепи к транспортной сети, изображенной на рнс. 2.19, позволит минимизировать затраты на перегон вагонов из каждого пункта портового комплекса в любой другой пункт. Например, решение данной задачи позволит определить оптимальный путь перевозки хопперов, соединяющий станцию прибытия, элеваторы, заводы, производящие удобрения, н станцию отправки.
Данная задача была решена с помощью про- 78 Глава 2 граммы, описанной в равд. 2.4.3. Результаты решения приводятся на с. 76 — 77. Длины дуг, не содержащихся в сети, изображенной на рис. 2.!9, были взяты равными 999999,00. Уэлы Г1ункты портового комплекса 1 Станция прибытия 3, б, 10 Элеваторы 2, 5, 8, Заводы производящиеудобрвния 4, т, 9, Другие пункты портового комплекса 11 Станцияотправления Ряс. 2.19. Траяслортяая сеть. 2.8. ЗАДАЧИ О КРАТЧАЙШЕМ ПУТИ С ФИКСИРОВАННЫМИ ПЛАТЕЖАМИ В предыдущих разделах были даны алгоритмы, которые могут быть использованы для определения цепи минимальной стоимости из заданного источника з в заданный сток Е Кроме того, алгоритм Дейкстры позволяет находить кратчайшую цепь из произвольного источника з в каждый другой узел сети.
Эти алгоритмы, как и все другие алгоритмы поиска кратчайшей цепи, основаны на следующем утверждении: «Если кратчайшая цепь между узлами з и 1 проходит через узел Й, то отрезок этой цепи, расположенный между з и й, образует кратчайшую цепь, соединяющую з и А. Кроме того, отрезок цепи, расположенный между й и 1, также образует кратчайшую цепь между к и 1». Сейчас мы рассмотрим класс задач, для которых данное утверждение несправедливо. Такие задачи называются задачами о кратчайшем пути с фиксированными платежами, или просто задачами с фиксированными платежами.
79 етернинироеиннае патоки е сетях Задачи с фнкскрованными платежами возникают в тех случаях, когда за прохождение через один или несколько заданных узлов сети взимается штраф или плата. В качестве примера можно рассмотреть задачу транспортировки товаров са складов в пункты потребления, когда за первое использование каждого промежуточного пункта распределительной сети взимается фиксированная плата. Другим примером является задача определения маршрута движения грузового 'судна, когда плата взимается за то, чтобы войти в некоторый порт. При этом пла- г Въезд- — ~ Я вЂ” н — -~ Ваези Рис. 2.20. Сеть со штрафама аа вазпояпеппе поворота.
та в каждом порту может быть различна и зависит от размеров судна, вида перевозимого им груза н налога. Вообще данные задачи возникают в тех случаях, когда строятся, покупаются или сдаются на временное пользование сооружения, предназначенные для стоянки грузового транспорта. Для решения сетевых задач с фиксированными платежами описанного выше класса был разработан ряд итеративных процедур, основанных на использовании множителей Лагранжа нз (или) теории двойственности ~23, 36, 37). Хотя анализ подобного подхода выходит за рамки данной книги, хотелось бы рассмотреть один класс транспортных задач, которые могут быть просто решены с помощью методов, описанных в предыдущих разделах. Во многих задачах транспортного планирования требуется определить оптимальный маршрут движения по сети улиц с односторонним и (или) двусторонним движением.
При решении задач, связанных с транспортным потоком, обычно вводятся задержки при переезде через перекресток или «штрафы за выполнение поворота». Эти задержки и штрафы можно рассматривать как фиксированную плату. Штраф за выполнение поворота обычно зависит от направления движения при въезде на перекресток и направления движения при выезде с перекрестка. Предполагается, что за выполнение запрещенного поворота взимается бесконечно большая плата или штраф.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
