Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 40
Текст из файла (страница 40)
Для этого можно к каждому п~ прибавить минимальную ординату рассматриваемых точек, т. е. к каждому тт; прибавить величину ~,=ппп [с;Д. в Аналогично пусть  — множество точек, соответствующих дугам, которые удовлетворяют условиям случая 2. Все эти точки требуется переместить вертикально вниз так, чтобы ордината ни одной из них не стала бы положительной.
Для этого можно из каждого узлового числа п~ вычесть максимальную ординату рассматриваемых точек, т. е. к каждому и; прибавить величннч Ьг —— — шах [с~;) =ппп [ — сп). в Если узловые числа всех непомеченных узлов должны быть изменены посредством сложения их с одной и той же величиной, то к каждому и; следует прибавить величину ~=пни[~в Я. И наконец, следует отметить, что в результате вертикального перемещения всех точек из В н В на величину, равную минимальному расстоянию их от линии, все они расположились ближе к этой линии. Данная процедура гарантирует, что если множества В и В не пустые, то по крайней мере одна дефектная дуга станет бездефектной.
з.7. ОписАние ШАГОВ АлГОРитмА Шаг 1. Найти дефектную дугу (1, /). Если ее не существует, то алгоритм завершает работу. Шаг 2. Определить, как следует изменить поток по этой дуге— увеличить или уменьшить, для того чтобы она перестала быть дефектной. Если поток следует увеличить, то перейти на шаг 3, а если уменьшить, то на шаг 4. 16' 244 Глава 3 Шаг 3.
С помощью процедуры расстановки пометок, найти путь из > в 1, по которому можно пропустить поток, негувеличивая дефекта ни одной из дуг этого пути. Если такой путь найден, :то скорректировать поток ло нему и увеличить поток по дуге (>', !). Если дуга (з, у) стала бездефектной, то перейти на шаг 1. Если она по-прежнему является дефектной, то повторить шаг 3. Если такого пути не существует, то перейти на шаг 5.
Шаг 4. Найти путь из з в 1, по которому можно пропустить поток, не увеличгввая дефекта ни одной из дуг этого пути. Если -такой путь найден, то скорректировать поток по нему и умень,шить поток по дуге (>, 1). Если дуга (1, 1) стала бездефектной, то перейти на шаг 1. Есля она по-прежнему является дефектной, то повторить шаг 4. Если такого пути не существует, то перейти на шаг 5. :Шаг 5. Изменить значения переменных и и, сохраняя пометки .всех помеченных узлов, повторить шаг 2. Если хотя бы одно узловое число стало равным оо, то алгоритм завершает работу.
.Допустимого потока не существует. .3.8. ЧИСЛОВОЙ ЙРИМЕР В настоящем разделе с помощью алгоритма дефекта будет завершено решение задачи, данной на рис. 3.6. Для применения ,алгоритма необходимо выполнить два шага: (1) выбрать начальные значения двойственных переменных и (2) выбрать начальный поток в сети, удовлетворяющий условию сохранения. При этом выбор допустимого решения не является обязательным, однако необходимо, чтобы эти переменные были я>вно оп:,ределены.
Для простоты значения переменных я выберем равными нулю: п>=из=из=ггз=О. Потоки, удовлетворяющие условию (2), зададим следующим образом: 1>з=О, 1>з=2, !аз=О, > зз= 2, !24=2, !аз=О, !41=2 >. ,38Л. ЧИСЛОВОЙ ПРИМЕР ДЛЯ АЛГОРИТМА ДЕФЕКТА ,Итерация 1. 1. Выберем дефектную дугу (4, 1)". 2. Дуга (4, 1) находится в состоянии 5>, поэтому увеличим поток по ней на 1 единицу, делая его равным нижней границе, т.
е. 3. 3. С помощью процедуры расстановки пометок находим путь .из узла 1 в узел 4. '> Интуитивно понятно, что если начальные решения выбрать близкими .к оптимальным, то алгоритм завершит работу намного быстрее. В рассматриваемом примере решение было выбрано только для иллюстративных целей. Отметим, что оно не является допустимым. з> Иа данном этапе можно выбрать произвольную дефектную дугу. 245 Алгоритм дефекта =3 =О =6 (3, 3, 0) 4же =О =г =2 =О Пометка (1, 4+). Теперь узел 1 является помеченным Не может быть помечен (отсутствие дефекта) Не может быть помечен (увеличение потока приведет к увеличению дефекта дуги) Возник непрорыв. Множества узлов: А (1) А (2, 3, 4) Множества дуг: В=((1, 2), (1, 3)) В=о ьт=в!п (2, 5)=2 в ьз= .ь=г Новые значения двойственных переменных: п1=0, из 2 из=2, п4 2 Начальные условия: .и, = жз = ие Уа =О Лз ут, = О у ° гте г у34 уч =г Процедура расстановки пометок.
Узел с„, =с„, сы сы сю сзг сг4 се~ см 246 Глава 3 Итерация 2. 1. Дуга (4, 1) все еще является дефектной. 2. Дуга (4, 1) находится в состоянии аг, поэтому увеличим поток до нижней границы, равной 3. 3. С помощью процедуры расстановки пометок находим путь нз узла 1 в узел 4. Процедура расстановки пометок. Узел Пометка [1, 4+! [1, 1+! [1, 2-! Поток можно уменьшить до верхней границы, не увеличивая дефекта дуги [1, 3+1 Возник прорыв.
Изменим потоки по дугам так, как это было описано выше. Итерация 3. 1. Выберем дефектную дугу, например (1, 3). 2. Дуга (1„3) находится в состоянии аг, поэтому уменьшим поток на 2 единицы, делая его равным нижней границе. Хш = 1 ты =2 124 = 2 у„=о 332 У34 =1 У43 3 (3, 3, о) 247 Алгоритм деэректа 3. С помощью процедуры расстановки пометок находим путь из узла 1 в узел 3. Процедура расстановки пометок.
Узел Пометка [2, 3 ) [1, 1+) Несмотря на то что дефект отсутствует, поток по дуге (1, 2) может быть увеличен на 1 единицу, и она при этом не станет дефектной 3 [1, 2-) Возник прорыв. Изменим потоки по дугам в соответствии с результатами работы процедуры расстановки пометок уэ =2 Уээ =1 э'э4 = 2 уээ =О уээ =о у„=з [з, з, о) Глава 3 Две дуги все еще являются дефектными. Итерация 4. 1. Выберем дефектную дугу, например (1, 3). 2.
Дуга (1, 3) находится в состоянии аз, поэтому уменьшим поток на 1 единицу, делая его равным нижней границе. 3. С помощью процедуры расстановки пометок находим путь из узла 1 в узел 3. Процедура расстановки пометок. Узел Пометка [!, 3-] Не может быть помечен Не может быть помечен Возник непрорыв. Множества узлов: А =[1) А=(2, 3, 4) Множества дуг: в=ПП 3В В=Я Ьз =ппп[3]=3 Новые значения двойственных переменных: я~=о, аз=5 аз=5, нз-5 Итерация 5. На данном этапе только одна дуга я~вляется дефектной.
Читателю предлагается проверить, что аугме'. тальный путь потока вновь не может быть построен. Выполняя при данных условиях две последовательные итерации, получаем новые значения двойственных переменных: я~ = 1, па †в, па=6 и п4=8. Теперь выполнены следующие условия: Алгоритм дефекта Поскольку все дуги сети стали бездефектными, то условия оптимальности выполнены. Оптимальная (имеющая минимальную стоимость) циркуляция следующая: гам=3, гезз=2, 1езз=О, 1езз=1, )'ге=1, 1езз=б, 1езг=2. Минимальная стоимость равна 21.
3.9. ЗАКЛЮЧЕНИЕ Алгоритм дефекта был описан на эвристической основе с использованием хорошо известной теории д~войственностн в линейном программировании. Были описаны все шаги поиска оптимального решения и с целью показать их назначение было дано логическое обоснование алгоритма. Для описания всевозможных состояний, возникающих при работе алгоритма, приводились соответствующие таблицы. Кроме того, было дано пошаговое описание процедур, используемых при решении задачи. Рассмотрен числовой пример, решение которого было получено с помощью алгоритма дефекта. Основная цель настоящего раздела заключалась в том, чтобы описать с точки зрения логики и организации вычислений теорию и методологию, лежащие в основе алгоритма.
Хотя для сетей больших размерностей процедура поиска решения может стать очень громоздкой, все операции в ней четко определены и могут быть запрограммированы. Описание программы, реализующей алгоритм дефекта, приводится в части 1П. Несмотря на то что алгоритм дефекта применим к широкому классу задач, процедуры поиска решения и критерий оптимальности для различных задач одни и те же, а изменяется лишь конфигурация сети.
Таким образом, алгоритм дефекта обладает двумя важными достоинствами: 1. Он позволяет эффективно решать широкий класс потоковых задач. 2. Для начала работы процедуры оптимизации не требуется допустимого решения. Необходимо только, чтобы начальное решение удовлетворяло условию сохранения потока. 1В качестве начального решения всегда можно выбрать нулевой вектор.) Глава 3 Кроме того, алгоритм дефекта обладает достоинством, присущим всем потоковым алгоритмам. А именно, он допускает наглядную интерпретацию, что не свойственно для процедур линейного программирования при числе измерений, большем двух ЧАСТЫ1.
ОПТИМИЗАЦИЯ ПОТОКА, ОСНОВАННАЯ НА ПРИМЕНЕНИИ АЛГОРИТМА ДЕФЕКТА. ПОСТРОЕНИЕ МОДЕЛЕЙ Основная цель настоящего раздела состоит в том, чтобы показать возможности применения алгоритма дефекта при решении обобщенных потоковых задач. Рассматриваются следуюшие потоковые задачи: 1, Транспортная задача. 2. Задача о назначениях. 3. Задача о максимальном потоке. 4. Задача о дереве кратчайших цепей. 5. Задача о перевозках.
Для каждой из этих задач дана сетевая постановка, к которой применим алгоритм дефекта. Кроме того, с помошью алгоритма дефекта формулируется и решается задача производственного планирования. При этом дается экономическая интерпретация решения двойственной задачи. В части Ш дается описание программы, применимой для решения задач средней размерности (с числом узлов и числом дуг, не превосходяшими 500), и с ее помощью решается один пример. ЗЛО. РЕШЕНИЕ ЗАДАЧИ С ИСПОЛЬЗОВАНИЕМ АЛГОРИТМА ДЕФЕКТА Для применения алгоритма дефекта необходимо выполнить две процедуры: 1. Сформулировать исходную задачу в виде потоковой задачи с замкнутой сетью, имеющей ограниченную пропускную способность. 2. Задать начальные значения двойственных переменных пь (узловых чисел) и начальную циркуляцию, удовлетворяющую условию сохранения ~потока.
Что касается первой процедуры, то рассмотрим сначала конфигурацию сети с одним источником и одним стоком (которые в действительности могут я~влиться главным источником и главным стоком). Данная конфигурация изображена на рис. 3.9. Для построения системы типа замкнутой петли необходимо ввести дугу, соединяющую узел 1 с узлом з. Будем называть эту дугу возвратной дугой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
