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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

116
Из пункта
6
A смещение базы 3
=
r
возможно только в пункт
2
A , что
видно из начальных дуг маршрутов (табл. 46, строка 6
=
i ). Переместив
базу 3=
r
из пункта
6
A в пункт
2
A , получим улучшенное решение,
записанное в строке № 5 табл. 48 («свертка» строк № 1 и 4). Элементы,
изменившие свои значения в ходе «свертки» (7.7), в табл. 48 выделены
шрифтом.
Дальнейшее улучшение решения смещением точки
3
х
из пункта
2
A
получить невозможно. Это следует из анализа начальных дуг маршрутов
(табл. 46, строка 2
=
i ).
Описанную процедуру можно выполнить без записи табл. 48, т.к.
элементы строки 1 табл. 48 выделены в табл. 46 шрифтом.
Из табл. 47 для неориентированного графа видно, что при полученном
решении (7.10) для 2=
R
все значащие выделенные элементы являются
минимальными в своих столбцах (не считая
niL
ii
,1,0
0
,
== ).
Следовательно, уменьшение суммы (7.5) можно достигнуть только
заменой наибольшего из выделенных элементов (
3
0
5,4
0
3,4
0
1,4
=== LLL ) на
ноль, путем размещения в соответствующем пункте
{}
5,3,1
∈
iA
i
точки
3
х
.
Таким образом будет получено три варианта решения (размещения базы
r = 3):
{
}
{
}
{
}
{
}
531 ,2,4,,2,4,,2,4:
r
k .
Суммарная длина маршрутов при 3
=
R
уменьшится на 3 ед. по
сравнению с решением (7.10) для 2
=
R
и станет равной 8 ед. Только
первая база (
4
,1 Ar = ) будет обслуживать несколько пунктов, другие две –
по одному (по месту расположения базы).
При n
R
= каждая база обслуживает свой пункт и суммарная длина
маршрутов равна нулю.
7.2. Учет грузопотоков и грузоподъемности
транспортных средств при размещении баз
В реальных условиях при размещении баз необходимо учитывать
потребности по доставке грузов в различные пункты, а также
грузоподъемность транспортных средств, используемых
r
-й базой,
расположенной в пункте
r
k
A
. Тогда задача будет состоять в таком
размещении
R
баз в
R
пунктах (вектор
(
)
R
r
k ), при котором суммарные
энергозатраты будут минимальны.
Дополнительной к совмещенной матрице кратчайших маршрутов

Страницы