Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 12
Текст из файла (страница 12)
Пусть общие затраты в данном слу- Глава 2 чае равны сса Тогда значение параметра дуги 1'1, )) вычисляется по формуле 1 — ! см —— Р!+~~ ть — 51, (2.511 з=! где Р! — стоимость автомобиля в начале !что года, и, — эксплуатационные расходы в течение й-го года, 51 — ликвидационная стоимость автомобиля в начале Тчго года. На рис. 2.!2 числа, приписанные дугам 11, 17', соответствуют планируемым затратам сп. Вследствие инфляции, возрастания стоимости автомобиля и увеличения расходов на его техническое обслуживание общие затраты в различных периодах одинаковой длины не являются постоянными. Оптимальному решению данной задачи соответствует кратчайший путь из узла 8=1 в узел 1=9. Эту цепь можно рассматри|вать как цепь, минимизирующую стоимость единицы потока из узла ! в узел 9 при условии, что стоимость единицы потока по дуге 1'!', /) равна сп.
Результаты вычислений, проведенных при поиске кратчайшей цепи по алгоритму Дейкстры, даны в табл. 2.5. Для минимизации общих затрат покупку автомобиля следует производить в начале первого, пятого и девятого годов. Общие затраты при этом составляют 11 250 долл. Таблица 2.6. Результаты вычислений Узел Шаг 1 2 3 4 5 б 7 8 9 11 250 11 250 11 250 11 250 !1 250 !1 250 )Ы 2250) о 1 2 3 4 5 б 7 8 9 10 11 Га 13 !4 15 Б) ) 0) 1450 ) !Ц )1450) !О) )14501 !0) )1450Д Я] !144$Я Б) )1450) )0) !1450] [о) Ко) ПО Н450 [0~ ~~450 1О) )1450) [О) )1!4503 )0) [1450) ) 0) )1450) ! !!) )~.450) 2750 3850 2750 3850 2750 3850 [27500) 3850 )2750) 3850 )2730) 'ь3850) )2750) )3850) )2750) !3850) [2750Д [3850! )2750) [3~850 [2750) )3850) )2750) Я503' )2750) [3850) )2750) [3850) )27ЮО) )3850) 4750 сч 4750 4750 6900 4750 6900 4750 6900 4750 6900 4750 6900 )4750) 6900 !4750) 6825 )4750) )6825) !4750) )6825) ~4750 [6825) )4750) !6825) !4750) )6825) ~4750) )6825] 8550 чч 8550 о 8550 10000 8550 10 000 8550 10 000 8550 10 000 )8550) 1О 000 )85500) 1О 000 ~8550 [10 000) !8550) )!О 000) ) 8550) )10 000) 6! Детеряинировоннне патоки в сетях 2.3.4.
ОПИСАНИЕ ПРОГРАММЫ, РЕАЛИЗУЮШЕИ АЛГОРИТМ ДЕИКСТРЫ Назначение: нахождение кратчайшей цепи из источника в любой другой узел сети. Локализация: подпрограмма 1т13КА в пакете сетевой оптимизации. Ограничения: программа обрабатывает сети, содержащие до 50 узлов и 50 дуг. Размеры сети можно увеличить, изменив границы массивов в операторах размерности, записанных в подпрограмме ШЗКА и в основной программе. Входные данные: Набор 1. Одна карта с именем алгоритма в формате (А4). Набор 2. Одна карта с числом узлов и числом дуг в сети в формате (2110).
Набор 3. Общее число карт в данном наборе равно числу дуг в сети. С каждой карты считываются следующие величины: !) номер начального узла дуги; 2) номер конечного узла дуги; 3) длина дуги. Формат (4Х, 16, 110, Р10.2). Набор 4. Данный набор состоит из одной карты, содержащей слово 'РЕЯУ в формате (А4), которая указывает конец задачи. Набор 5. Данный набор состоит из одной карты, содержащей слово 'ЕХ1Т' в формате (А4), которая указывает конец входных данных. Составные части программы.
Программа состоит из следующих подпрограмм: РИКА (ввод и вычисления); ТКАСЕО (печать узлов кратчайшей цепи и ее длины). Используемые переменные: 1 — начальный узел дуги, Л— конечный узел дуги, нА1 — длина дуги, 1) — рабочий массив длин дуг, ОРТРАТ вЂ” массив оптимального решения.
Используемый метод: данный алгоритм основан на методе, описанном в равд. 2.3.1. Литература: 1!1!. 2.3.5. ЗАДАЧА, СВЯЗАННАЯ С ТРАНСПОРТИРОВКОИ НЕФТИ (ФИЛЛИПС) Недавно компанией В!аск Оо!д Ре1го!ешп было найдено крупное месторождение нефти на северном склоне Аляски. Для его разработки возникла необходимость в строительстве нефтепровода, соединяющего северную часть полуострова с одним из шести возможных пунктов потребления на территории Соединенных Штатов. Для сооружения нефтепровода потребуется семь насосных станций, расположенных между подземным нефтехранилищем на северном склоне Аляски и пункта- Глава 2 ми потребления. Каждая подстанция может быть построена на любом из имеющихся участков.
Однако между некоторыми участками строительство нефтепровода не может проводиться в силу таких причин, как сложные физико-географические условия местности !наличие гор, озер), невозможность арендовать землю, ограничения, возникающие из-за необходимости охраны природы. Для любой пары насосных станций извести ш !ч ч у! уп Пункты потрвслення Рис.
2.!3. Распределительная сеть. ны затраты на строительство соединяющего их нефтепровода, которые зависят от местоположения каждой из них. Задача заключается в определении допустимого расположения насосных станций, прн котором общие затраты ,на строительство нефтепровода минимальны. На рис. 2.13 изображена распределительная сеть для данной задачи. Каждый участок здесь представлен узлом, а каждая пара узлов, соответствующих участкам, между которыми может быть проложен нефтепровод, соединена дугой с приписанной ей стоимостью данного участка нефтепровода. На практике при решении потоковых задач вычисления целесообразно проводить на ЭВМ. С этой целью на языке ФОРТРАН АНСИ была написана специальная программа, которая имеет стандартные форматы входных и выходных дан- Детерминированнае нотона в еетих ных.
Возможности использования программы и результаты ее работы иллюстрируются с помощью приведенного выше примера. Длина, или стоимость, кратчайшей цепи из узла 1 в узел 44 равна ЗЗ. Оптимальный план размещения подстанций описывается следующей последовательностью узлов (данное решение получено с использованием программы, описанной в равд. 2.3.4): Из узла 1 в узел 3 (расстояние равно 4,00). Из узла 3 в узел 9 (расстоянне равно 5,00).
Из узла 9 в узел 14 (расстояние равно 3,00). Из узла 14 в узел 20 (расстояние равно 3,00). Из узла 20 в узел 26 (расстояние равно 6,00). Из узла 26 в узел 32 (расстояние равно 3,00). Из узла 32 в узел 38 (расстояние равно 5,00). Из узла 38 в узел 44 (расстояние равно 4,00). Аналогично можно найти кратчайшую цепь из начального узла 1 в любой из конечных узлов 39, 40, 41, 42 и 43. 2.4. ЗАДАЧА 0 МНОГОНОЛЮСНОЙ КРАТЧАЙШЕЙ НЕПН В настоящем разделе рассматривается задача нахождения кратчайших цепей между всеми парами узлов сети б= (й(, А).
Если длина каждой дуги соответствует расстоянию или стоимости единицы потока по этой дуге, то кратчайшей цепью между двумя произвольными узлами является цепь, стоимость единицы потока по которой минимальна. Дуги из множества А могут быть ориентированными и неориентированными. Однако поскольку направление потока в неориентированных дугах нельзя определить заранее, то каждую такую дугу следует заменить двумя ориентированными дугами с противоположными направлениями и длинами, равными длине неориентированной дуги. Предполагается, что длины дуг могут быть как положительными, так и отрицательными. Однако дли|на, или стоимость, каждого цикла или контура должна быть неотрицательной.
Алгоритм, описанный в настоящем разделе, первоначально был разработан Флойдом (!2). Мы предлагаем усовершенствованный вариант алгоритма, принадлежащий Ху 131). Пусть (Ч = (1, 2,...,п) — множество узлов, а сп †дли, или количественный параметр, дуги (1, 1), направленной от узла 1 к узлу 1. Обозначим через т(етв длину кратчайшей цепи из узла 1 в узел й. Предположим, что величина й;» представляет наилучшую оценку длины кратчайшей цепи, соединяющей узлы 1 и А. Мы знаем, что либо длина Йы=о(п+д;и каждой кратчайшей цепи, 64 Глава 2 проходящей через промежуточный узел !, превосходит величину э2;», либо текущая длина кратчайшей цепи равна «2«», Однако если длйна «э«» новой цепи меньше дэ», то текущее значение Н;» следует заменить на «1«». Алгоритм Флойда работает следующим образом.
Первоначально за длину кратчайшей цепи между двумя произвольными узлами э и й принимается длина дуги (й й), соединяющей этв узлы. Затем последовательно ал Кепи аа + то значениеИе заменяется значением ча + э«у» текущая оценка длины кратчайией цепи между узламн «и» расстояние от узла«до узла« Эасстоянне от уэлау до узла» Рис. 2Д4. Пример процедуры сравнения, выполняемой прн работе алгоритма Флойда.
проверяются всевозможные промежуточные узлы, расположенные между 1 и й. Если длина цепи, проходящей через некоторый промежуточный узел, меньше текущего значения «1«», то переменной э2«» присваивается новое значение. Данная процедура повторяется для всевозможных пар узлов, пока не будут получены все значения «1е«».
Для любых трех различных узлов э, 1 и й сформулированные выше условия могут быть записаны в виде неравенства «)м+«1«» Р «1,». э' чь!' Ф й, (2.52) поскольку в противном случае кратчайшая цепь из узла 1 в узел й должна содержать узел / и тогда величина «2«» не была бы равной длине кратчайшей цепи. В алгоритме Флойда начальным значением переменной дт«» является величина св, а затем данная оценка последовательно улучшается до тех пор, пока не будет найдена кратчайшая цепь между узлами « и Й Рис. 2.14 иллюстрирует выполнение процедуры сравнения для пары узлов э' и й. Алгоритм Флойда позволяет решать задачу о многополюсной кратчайшей цепи (пути) для сети из л узлов за л итераций, Для того чтобы перейти к формальному описанию итеративной процедуры поиска решения, обозначим символом Ю,» оценку длины кратчайшей цепи из узла «в узел Й, полученную на цй итерации.
Детерминированные потони е сетях Способ полУчениЯ на )чй итеРации величины а1си может быть описан с помощью следующей трехместной операцпи: с(1 1 пйп(йеи1-', с(, 1-'+йж1-ч), (ф 1' ~ й. (2.53) (2.54) После построения матриц 0' и йо нужно для каждого 1 1, 2,...,п, используя для вычислений элементы матрицы Р1-', полученной на (1 — 1)-й итерации, выполнить следующую процедуру: Шаг 1. Вычеркнуть элементы 1-й строки и )что столбца. Назовем эти множества элементов базовой строкой и базовым столбцом соответственно. Шаг 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
