Расчет оптимального замкнутого маршрута

Информация » Стратегия управления доставкой груза на транспорте » Расчет оптимального замкнутого маршрута

Страница 3

Определим оценку для множества G11:

ξ(G11)=ξ(G0)+=230+0=230.

Так как ξ(G11)=ξ(G21), то на следующем шаге производим ветвление подмножества G11.

Шаг 2.

2.1 Выбираем пары городов-претендентов на ветвление, т.е. (i,j) для которых Cij=0:

C24=0; C26=0; C36=0; C42=0; C45=0; C51=0; C54=0; C65=0.

Для выделенных претендентов подсчитаем оценки по формуле:

Θ(i,j)=.

Θ(2,4)=0; Θ(2,6)=0; Θ(3,6)=30; Θ(4,2)=22; Θ(4,5)=0; Θ(5,1)=30; Θ(5,4)=0; Θ(6,5)=22.

Для ветвления выберем пару претендентов с максимальной оценкой Θ(i,j), то есть пару (5,1), так как max Θ(i,j)=Θ(5,1)=30.

2.2. Произведем ветвление: G11=G12 G22, где G12={(1,3), (5,1)}, а G22≠{(1,3), (5,1)}.

2.3. Вычислим оценку для G22: ξ(G22)=ξ(G11)+Θ(5,1)=230+30=260.

2.4. Построим матрицу С(2) для этого вычеркнем в матрице C(1) пятую строку и первый столбец. Чтобы избежать образования замкнутых подциклов, запретим переезд коммивояжера из города 3 в город 5, полагая С53→¥, и выполним процесс приведения. В результате получим матрицу С(2):

С(2) =

2

4

5

6

hi

2

∞

0

20

0

0

3

42

30

∞

0

0

4

0

∞

0

90

0

6

22

70

0

∞

0

Hj

0

0

0

0

Определим оценку для множества G12:

ξ(G12)=ξ(G11)+=230+0=230.

Шаг 3.

3.1 Выбираем пары городов-претендентов на ветвление, т.е. (i,j) для которых Cij=0:

C24=0; C26=0; C36=0; C42=0; C45=0; C65=0.

Для выделенных претендентов подсчитаем оценки по формуле:

Страницы: 1 2 3 4 5

Популярные материалы:

Расчет неоднородной симметричной буксирной линии
Дано: симметричная буксирная линия состоит из 2-х участков троса АС и DВ длиной ℓт = 180 м каждый и участка цепи СD длиной 50 м (2ℓц). Вес одного погонного метра троса в воздухе qmp = 92 Н, цепи qц = 687 Н. Горизонтальная сост ...

Изучение производственной программы и основных показателей
Изучение производственной программы и основных показателей представлено в таблице 1 Таблица 1 – Изучение производственной программы и основных показателей Наименование Ед. Изм. Период % выполнения 2008 год 2009 год ...

Годовой объем работ по ТО
Годовой объем работ по ТО-1 (ВАЗ-2101): ТТО-1 г = ΣNТО-1 г * tТО-1 = 73 * 6 = 438 чел. ч Годовой объем работ по ТО-2 (ВАЗ-2101): ТТО-2 г = ΣNТО-2 г * tТО-2 = 20 * 29,75 = 595 чел. ч Годовой объем работ по ТО-1 (ПАЗ-672 и ГАЗ ...