Элементарные решения неэлементарных задач на графах. Берзин Е.А. - 93 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

95
Суть метода последовательного улучшения оценок
t
lk,
π
искомой
пропускной способности
0
,lk
π
(
,...)2,1 ,
0
,,
=≥ t
lk
t
lk
ππ
состоит в следующем.
По некоторому правилу определяется начальная оценка
0
,
1
, lklk
ππ
≥ , и
все элементы
1
,lkij
c
π
< матрицы c удаляются из неё (или игнорируются
при расчётах). Далее из пункта
k
A делается попытка построения
маршрутов к пункту
l
A . Если хотя бы один такой маршрут построить
удалось, то он и является оптимальным, при этом
1
,
0
, lklk
ππ
= .
Если маршрута от
k
A к
l
A не существует, то берется новая,
улучшенная оценка
1
,
2
, lklk
ππ
< . Далее снова делается попытка построить
маршрут
lk,
μ
, вероятность ее успеха велика, поскольку возрастает
количество «рабочих» элементов
2
,, lkji
с
π
≥ . Если маршрут до пункта
l
A
построен, то процесс окончен, иначе берется новая оценка
t
lk
t
lk ,
1
,
ππ
<
+
, и
так далее, пока не будет получено решение.
Для формулировки достаточно эффективного алгоритма решения
задачи необходимо предусмотреть возможность выбора эффективной
начальной оценки
1
,lk
π
и сокращения до минимума числа промежуточных
оценок. Для решения указанных вопросов и уяснения деталей метода
улучшения оценок рассмотрим числовой пример построения оптимального
маршрута из пункта
5
A (5=
k
) в пункт
3
A (3
=
l
), (табл. 40).
Начальная дуга искомого маршрута
0
3,5
0
,
μμ
=
lk
не может иметь
(табл. 40, строка 5
=
k
) пропускную способность большую, чем
максимальный элемент
начальной дуги (строка 5
=
k
), равный 28 ед.
Пропускная способность всего маршрута также не может быть больше,
чем пропускная способность
конечной дуги маршрута, наибольшее
возможное значение которой равно 30
3,4
=
с ед. (столбец 3
=
l
).
Следовательно, в качестве начальной оценки (сверху)
1
,lk
π
максимальной
пропускной способности может быть выбрано меньшее из этих двух чисел:
min
1
,
=
lk
π
{
li
i
jk
j
cc
,,
max;max
}= .28}30;28min{
=
(6.2)
Для полученной оценки делается попытка построить маршрут
0
,lk
μ
,
при этом элементы
1
3,5
π
<
ij
c матрицы c не используются. На основе
оценки
28
1
3,5
=
π
удалось построить маршрут
t
j
t
,5
μ
(табл. 40):

Страницы