 |
 |
 |
 |
|
 |
 |
70
Идея формулы (3.24) достаточно прозрачна: при циклическом преобразовании текущего потока
увеличиваются объемы грузоперевозок на тех дугах, которые сонаправлены вводимой дуге, и
уменьшаются на дугах, имеющих обратную ориентацию. Соответственно, при добавлении мы должны
следить за тем, чтобы не превысить ограничения на пропускные способности (
?
?
r
d
–
х
d
(q)
), а при
вычитании — за неотрицательностью х
d
(q)
. После определения
?
происходит пересчет компонент
текущего потока по формуле
В результате мы получаем новый допустимый поток х
d
(q+1)
), полагаем номер текущей итерации q+1 и
переходим к п. 1°.
В описанном алгоритме, как и в случае с матричной транспортной задачей, мы не гарантированы от
возникновения вырожденного потока. Как уже упоминалось выше, такому потоку будет
соответствовать несвязная опора. Для преодоления вырожденности рекомендуется включить в текущий
план фиктивные компоненты с нулевыми объемами так, чтобы соответствующие им дуги дополняли
опору до остова сети. Построенный таким способом план позволяет выполнить все действия, входящие
в стандартную итерацию метода потенциалов.
Отдельно следует остановиться на методах генерации исходного допустимого потока. Наиболее
простой из них (хотя, возможно, и наименее рациональный) основан на идеях, сходных с идеями метода
минимизации невязок, используемого для построения допустимого базисного плана ЗЛП. Данный
метод предполагает решение соответствующей вспомогательной задачи, которая получается из
основной в результате следующих преобразований:
1. К множеству вершин сети добавляется фиктивная нулевая вершина с нулевой интенсивностью
(b
0
= 0).
2. Все вершины, имеющие отрицательную интенсивность (спрос) b
i
< 0, соединяются с добавленной
вершиной 0 входящими дугами (0, i), а вершины, обладающие положительной интенсивностью
(запасом) b
i
>
0, — исходящими дугами (i,
0). Ограничения на пропускные способности для
добавляемых дуг отсутствуют.
3. Стоимости перемещения единицы продукта для вновь добавленных дуг полагаются равными 1, а
для дуг, соответствующих транспортной сети основной задачи, — 0.
Построенная вспомогательная задача обладает очевидным допустимым невырожденным потоком,
получаемым назначением объемов, равных интенсивностям вершин, по всем добавленным дугам.
Решив вспомогательную задачу, мы либо получим допустимый поток для основной задачи, либо
придем к выводу об отсутствии у нее допустимых планов.
3.2.3. Задача о кратчайшем пути. Классическим примером сетевых задач является определение
кратчайшего пути между вершинами сети. Пусть задан граф (I, D, G), каждой дуге которого поставлено
в соответствие число c
d
, называемое длиной. Также пусть выделены две вершины графа s и t, и требует-
ся найти путь наименьшей длины, ведущий из вершины s в вершину t.
Если в графе имеются «кратные» дуги, соединяющие одинаковые начало и конец, то достаточно
оставить одну — с наименьшей длиной, а остальные отбросить. Таким образом, достаточно
рассматривать задачу о кратчайшем пути для простого
графа (I,
D), в котором дуги определяются
упорядоченными парами вершин d = (i, j). Тогда естественно путь L, идущий из вершины s в вершину t,
задавать в виде упорядоченного набора вершин, через которые проходит данный путь:
а длины дуг обозначать как c
d
= c
i,j
.
Длина описанного выше произвольного пути L определяется по формуле