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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

47
указанным способом также будет оптимальным. Любое иное разбиение
потребует введения новых дуг, а следовательно, и увеличения общей
длины маршрутов.
4. В полученном решении в качестве исходного пункта может быть
взята любая вершина (
nk ;1= ). Для этого достаточно номера, стоящие в
цикле перед выбранным исходным номером k, перенести в конец кортежа
и в конце приписать номер k. Например, для k = 6 из (3.18) получим
316,4,1,3,2,5,4,3,6
=
L .
Для классической задачи коммивояжера решение инвариантно к
исходному пункту цикла.
4. ОБОБЩЕННАЯ ЗАДАЧА КОММИВОЯЖЕРА
4.1. Постановка обобщенной задачи коммивояжера
Содержательная постановка обобщенной задачи практически остаётся
такой же, как и у классической задачи коммивояжера, с тем лишь
добавлением, что коммивояжер, превратившись фактически в поставщика,
должен выбрать такой маршрут для
развозки грузов );1( nja
j
= , при
котором энергозатраты будут минимальными.
Задача, как и ранее, будет состоять в определении гамильтонова цикла
0
k
μ
, соответствующего минимальным энергозатратам. Дополнительной
исходной информацией, по сравнению с предыдущей задачей, будет
являться вес груза
j
a , который должен быть доставлен в пункт
j
A
);1( nj = .
Поскольку в исходный пункт
k
A груз
k
a доставлять не требуется, то
под величиной
k
a будем понимать вес самого транспортного средства,
которое по циклу пройдет весь маршрут длиной )(
kkkk
LLL
μ
== ,
энергозатраты на что составят
kk
La
⋅
ед. (т·км, кг·м). Первый номер
присвоим исходному пункту (1
=
k
), в который возвратится транспортное
средство с пассивным грузом 1
1
=
a .
Формальная постановка обобщенной задачи коммивояжера как
задача минимизации энергозатрат )(
1
μ
Э путём выбора гамильтонова
цикла
1
μ
из всего их множества
{
}
1
μ
(4.2) при ограничениях на частные

Страницы