Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 39

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 39)

Если же после выполнения описанных выше шагов состояние ни одной дуги, ведущей из А в А, не изменится то допустимого решения не существует. Если имеет место прорыв, то дополнительный путь из 1 в 1 (или из 1 в 1) найден. В этом случае остается только пройти по данному пути в обратном направлении и изменить поток по каждой его дуге на величину йч (или д;) последней (среди всех пометок, приписанных узлам этого пути) пометки.

Затем все пометки стираются, выбирается другая дефектная дуга н вновь выполняется указанная процедура. Оптимальное решение исходной потоковой задачи будет найдено тогда, когда все дуги станут бездефектнымн. Если прорыв не возникает, то вновь определяются множества В и В и вновь изменяются узловые числа согласно описанным выше правилам. Процедура расстановки пометок повторяется до тех пор, пока либо дуга (й)) не станет бездефектной, либо не возникнет непрорыв при ~Фоо. В случае когда ~=со, оптимального решения задачи не существует и алгоритм завершает работуо.

Отметим, что если си=0 для всех дуг, то потоки по всем прямым дугам равны Уп, а потоки по всем обратным дугам равны Ць В этом случае дополнительный путь построить нельзя. Итак, алгоритм дефекта может быть описан следующим образом. Строится сеть и определяется начальная циркуляция, удовлетворяющая условию сохранения потока.

Нулевая цирку- и Необходимые н достаточные условия сходимости здесь не приводятся. Их можно найти в работах [7) н [131. Алгоритм дефекта ляция всегда удовлетворяет этому условию. Затем узлам приписываются произвольные числа тт и выполняется процедура расстановки пометок. В случае ~возникновения прорыва потоки по дугам изменяются, в противном случае определяются новые узловые числа и данная процедура повторяется. В следующем разделе будет дана графическая интерпретация описанных вы- ше процедур. З.а.

ГРАФИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ АЛГОРИТМА ДЕФЕКТА В настоящем разделе описан графический подход к выполнению корректирующих операций в алгоритме дефекта. Логичность и простота данной процедуры делают этот мнемонический еп) О е; =о 7» е><о ертикапьныя О Рис. 3.7. Мнемонический прием для алгоритма дефекта. прием особенно привлекательным с вычислительной точки зрения.

На любой фазе алгоритма дефекта решения могут быть представлены точками (~гь сн). Состояние каждой дуги ((, 1) определяется расположением соответствующей точки относительно границ Ен и Уп (рис. 3.7). Если дуга не является дефектной, то точка (~п, сп) принадлежит жирной линии, состоящей из трех отрезков (рис. 3.7). Верхний вертикальный отрезок соответствует бездефектному состоянию а, нижний вертикальный отрезок — бездефектному состоянию б и горизонтальный отрезок — бездефектному состоянию (3.

Глава 3 24о Если дуга является дефектной, то соответствующая точка не принадлежит жирной линии и следует выполнять корректирующие действия. Существуют два типа корректирующих действий: 1. Модификация потоков (1п). 2. Модификация скорректированных стоимостей (сп).

Модификация потоков (процедура расстановки пометок) соответствует горизонтальным перемещениям, указанным на рис. 3.7„ Рис, 3.8. Допустимые направлении горизонтальных и вертикальных переме- пгення. а модификация скорректированных стоимостей (изменение значений и) — еертикальным перемещениям. Направления допустимых горизонтальных перемещений для каждого из шести состояний дефекта показаны на рис. 3.8,а, б. Допустимые вертикальные перемещения показаны на рис. 3.8, в, г. Следующие правила могут быть использованы для определения величин горизонтального и вертикального смещений. Правила горизонтальных перемещений эквивалентны правилам процедуры расстановки пометок.

Правила вертикального перемещения зквивалентны правилам изменения значений двойственных переменных ах. Алгоритм дефекта 3.6.1. ГОРИЗОНТАЛЬНЫЕ ПЕРЕМЕШЕНИЯ Рассмотрим произвольную дефектную дугу (1, /). Пусть ей соответствует точка (1», с»). Эта точка может располагаться слева или справа от каждого из трех отрезков линии порядка. 1. Горизонтальные перемещения вправо (увеличение потока) Если точка расположена слева от линии, то соответствующая дуга является дефектной и допустимым горизонтальным перемещением является только перемещение вправо, как это показано на рис.

3.8,а. Любая модификация потока, соответствующая горизонтальным перемещениям влево, недопустима, поскольку она ухудшает текущее состояние дуги. В связи с процедурой расстановки пометок это означает, что узел 1 не может быть помечен из узла 1, если (1, 1) — обратная дуга. Следующие правила применяются к прямым дугам. а. Если с»)О, то переместить точку так, чтобы она находилась как можно ближе к верхнему вертикальному отрезку линии. Если величина потока достаточна, для того чтобы достичь линии, то дуга перестает быть дефектной. В противном случае дуга продолжает оставаться дефектной, но соответствующая ей точка, перемещается в горизонтальном направлении ближе к линии. Приращение, потока всегда равно минимуму из ~величины потока, который может быть получен из узла 1, и величины смещения, необходимого для достижения верхнего вертикального отрезка.

Пусть дг — величина потока, который может быть получен из узла Е Приписать узлу 1 пометку [вь 1+], где 61= =ш(п[г);, Ц~ — Ы. б. Если с»=О, то переместить точку вправо настолько, насколько это позволяет сделать имеющийся поток, не выходя при этом за верхнюю границу У». В этом случае узлу 1 может быть приписана пометка [г)ь (г], где д;=ш(п[г1н У» — 1»]. в. Если с»(О, то переместить точку вправо настолько, насколько это позволяет сделать имеющийся поток, не выходя при этом за верхнюю границу У». Если нижний ~вертикальный отрезок достигается, то дуга перестает быть дефектной. В противном случае она продолжает оставаться дефектной, но соответствующая ей точка перемещается в горизонтальном направлении ближе к линии.

В этом случае узлу 1' приписывается пометка [вь Р.[, где дт=щ(п[д» У» — 1»]. 2. Горизонтальные перемещения влево (уменьшение потока). Если точка расположена справа от линии, то соответствующая дуга является дефектной и допустимым горизонтальным перемещением является только перемещение влево, как это показано на рис. 3.8,б. Любая модификация потока, соответствующая горизонтальным перемещениям вправо, недопустима, поскольку она ухудшает текущее состояние дуги.

В связи с процедурой 16 — 1664 242 Глава 3 расстановки пометок это вновь означает, что узел / не может быть помечен из узла ~', если (~, )) — прямая дуга. Следующие правила применяются к обратным дугам. а. Если сц)0, то переместить точку так, чтобы она находилась как можно ближе к верхнему вертикальному отрезку.

Это эквивалентно тому, что поток послан из ) в ~ в направлении, противоположном направлению дуги ((, у). Если величина потока, который можно получить из узла ), достаточна, для того чтобы е результате горизонтальных перемещений влево точка достигла линии, то дуга перестает быть дефектной. В противном случае она продолжает оставаться дефектной, но соответствующая ей точка перемещается в горизонтальном направлении ближе к линии. Величина, на которую поток уменьшается (т. е. величина потока противоположного направления), всегда равна минимуму из величины потока, который может быть получен из узла ), и расстояния в горизонтальном направлении от точки до линии порядка. Поэтому узел ( может быть помечен из узла / как [дь 1-], где д;=щ!п [дь [ц — Йц~. б.

Если си=О, то переместить точку влево настолько, насколько это позволяет сделать имеющийся поток, не переходя прн этом за другую сторону вертикального отрезка линии. В этом случае узлу 4 может быть приписана пометка [дь 1' ], где д;=гп1п[дь [ц — Ец]. в.

Еслк сц(0, то переместить точку влево настолько, насколько это позволяет сделать имеющийся поток, не переходя при этом за другую сторону нижнего вертикального отрезка. Если этот отрезок достигается, то дуга перестает быть дефектной. В противном случае она продолжает оставаться дефектной, но соответствующая ей точка перемещается в горизонтальном направлении ближе к линии. В этом случае узлу ( приписывается пометка [дь )-], где д;=ппп[дь ]ц — Щ. 3.6,2. ВЕРТИКАЛЬНЫЕ ПЕРЕМЕШЕНИЯ Как видно из рис. 3.8,в, г, вартикальные перемещения приносят пользу только в том случае, когда они позволяют расположить точку на горизонтальном отрезке линии порядка.

Предположим, что узел ( помеченный, а узел ) непомеченный. Тогда точка с положительной ординатой соответствует ориентированной дуге, направленной из ( и ). Если ордината отрицательна, то точка соответствует ориентированной дуге, направленной из / в Е Поэтому достаточно рассмотреть два случая: Е с;;) 0 и [ц( Уц, 2. сн(0 и Гн)Еп. Алгоритм деФекта 243 В случае 1 в результате вертикального перемещения вниз точка расположится ближе к горизонтальному отрезку линии.

как это показано на рис. 3.8,в. Напомним, что по определению си=си+и; — пь Следовательно, О=си+и; — (пг+сп). Это означает, что, для того чтобы точка достигла линии, узловое число тп следует увеличить на величину сп. В случае 2 в результате вертикального перемещения вверх точка расположится ближе к горизонтальному отрезку линии, как это показано на рис. 3.8,г.

Поскольку по определению оп=си+я~ — пь то О=оп+(и; — сп) — ль Это означает, что, для того чтобы в результате вертикального перемещения точка достигла линии, узловое число п~ следует уменьшить на величину Куь Пусть  — множество точек, соответствующих дугам, которые удовлетворяют условиям случая 1. Все эти точки требуется переместить вертикально вниз так, чтобы ордината ни одной из них не стала бы отрицательной.

Характеристики

Список файлов книги