 |
 |
 |
 |
|
 |
 |
69
Поскольку задача (3.15)-(3.17) является частным случаем задачи линейного программирования, ее
можно привести к канонической форме. При этом достаточно просто устанавливается, что ранг
матрицы задачи равен m-1, где m — количество вершин в сети. Введем дополнительно еще некоторые
понятия, используемые при описании свойств сетевых задач.
Остовом сети (I, D, G) называется любое ее частичное дерево (частичный граф, являющийся
деревом). Справедливо утверждение:
Произвольному остову сети (I, D, G) соответствует базис задачи (3.15)-(3.17) и наоборот.
Пусть имеется некоторый поток Х={х
d
}
d
?
D
. Рассмотрим множество дуг D(X)
= {d ?
D
| 0 < x
d
< r
d
}.
Опорой потока Х называется частичный граф (I, D(X), G). Говорят, что поток Х невырожден, если его
опора (7, D(X), G) является остовом сети (I, D, G). Иными словами, используя терминологию транспорт-
ной задачи, в невырожденном потоке, которому отвечает допустимый базисный план задачи, дороги, по
которым осуществляются перевозки груза, не достигающие по объему ограничения на пропускную
способность, образуют остов (связанную подсеть без циклов) рассматриваемой транспортной сети.
Теперь дадим краткое описание схемы метода потенциалов для транспортной задачи в сетевой
постановке.
1°. Предполагается, что в начале очередной итерации q имеется некоторый допустимый
невырожденный поток
Х={х
d
(q)
}
d
?
D
(о методах его генерации на начальном этапе будет сказано в
дальнейшем).
По имеющемуся потоку Х
(q)
строится система потенциалов пунктов сети. Для этого выбирается
произвольный пункт
i
0
, потенциал которого полагается
v
i0
=0. Множество вершин, смежных с i
0
,
обозначим через I(i
0
). Тогда для любой вершины j ? I(i
0
) потенциалы рассчитываются по правилу
если (i
0
,j) ? D(X
(q)
) (дуга направлена от i
0
),и
если (j,i
0
)
?
G(D(X
(q)
)) (j,i
0
)
?
D(X
(q)
) (дуга направлена к i
0
).
Получив очередную группу вершин с известными потенциалами, мы имеем возможность на основе
(3.22)-(3.23) вычислить потенциалы для следующей группы смежных вершин и т. д., пока не будут
определены все потенциалы. Возможность сделать это единственным образом вытекает из свойства
отсутствия циклов у остова сети.
Имея полную систему потенциалов, для всех дуг следует проверить условия критерия оптимальности
(3.19)-(3.21). Если они выполняются, то текущий поток Х
(q)
— оптимальный и, следовательно, алгоритм
завершен; в противном случае — переходим к построению следующего «улучшенного» потока.
2°. По аналогии с другими методами последовательного улучшения плана очередной поток
получается за счет «ввода» в него одной дуги и «вывода» другой. Если условия критерия опти-
мальности нарушаются сразу для нескольких дуг, то для ввода имеет смысл выбрать ту, на которой
достигается максимальное отклонение цены от разности потенциалов соединяемых вершин. Пусть для
ввода выбрана некоторая дуга d
l
= (s, t), направленная из вершины s в вершину t. Из правил построения
потенциалов следует, что в остове существуют две цепи, одна из которых соединяет базовую вершину
i
0
, потенциал которой был принят равным нулю, с s, а другая — i
0
с t. Если дополнить остов дугой d
l
,
образуется единственный цикл. Построенный цикл является аналогом цепочки преобразования плана в
методе потенциалов для транспортной задачи в матричной постановке. Обозначим через
D
+
(s,t)
множество дуг данного цикла, ориентация которых совпадает с ориентацией дуги d
l
= (s, t), а через D
-
(s,t)
— множество дуг, имеющих противоположную ориентацию. Определим величину возможной
корректировки объемов грузоперевозок, «перемещаемых» по циклу