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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

126
получено при начальном размещении точки x в пункте
1
A при
замене дуги (1;4) ребром
(
)
3
1,44,1
=
=
cc . Точка x сместится в пункт
4
A
, при этом
()
61, =xL .
Вводить очередную точку следует,
максимально улучшив вариант
размещения предыдущих точек. Для этого в строке 3
=
i (пусть в
3
A
находится точка
1
x
) следует найти по крайней мере два наибольших
элемента
(
)
6,9
0
5,3
0
2,3
0
,3
== LLL
j
и путем выбора пункта размещения точки
2
x
попытаться уменьшить значение найденных элементов, начиная с
наибольшего. Помещая точку
2
x
в любом из пунктов с номерами
{} { }
6,5,4,2
2
=
x
j (табл. 46, 6
5,32,
=
≤
LL
i
), согласно (7.7) получим
улучшенное решение
()
61, =x
m
L . Из множества
{}
2
x
i
теперь следует
попытаться выбрать пункт размещения точки
2
x
, при котором новое
значение целевой функции (7.14) станет меньше шести. Номер
{}
2
x
ji ∈
оптимального пункта размещения точки
2
x
следует искать в столбце
5=
j
, в котором находится второй из наибольших элементов
(
)
6
0
5,
=
i
L .
Строки с номерами
{}
6;2∈i сразу отпадают, т.к. они только ухудшат
решение
(
)
69,12
0
5,6
0
5,2
>== LL . Выбор любой из оставшихся строк
{
}
5;4
также не позволяет улучшить решение:
()
{}
7,2,62,3,0,0,,5max2,:4
5;45;44;43;32;41;3
≈
′
===
ср
j
m
LxLi 6 , (7.22)
()
2,3,6
6.3
5,
5.5
0,
4.3
3,
3.3
0,
2.5
6,
1.3
5max2,:5 ≈
′
=
⎭
⎬
⎫
⎩
⎨
⎧
=
′
=
ср
L
j
x
m
Li
.
Смещением точек
21
, xx от вершин решения не улучшаются,
поэтому окончательный выбор можно сделать из условия
минимума
средней длины маршрута
, поместив точку
2
x
в пункте
4
A .
Обслуживаемые пункты распределятся на обслуживание следующим
образом [см. (7.22)]:
из точки
()
3
1
Ax
пункты
{
}
31
, AA ,
из точки
(
)
4
2
Ax пункты
{
}
6542
,,, AAAA .
Маршрут к каждому из них и его длина записаны в табл. 46.

Страницы