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

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

Страница 2

2. Определим оценку множества G0, вычислив сумму приводящих констант

ξ(G0)= =202+28=230.

Шаг 1.

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

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

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

Θ(i,j)=.

Θ(1,3)=26; Θ(2,4)=0; Θ(2,6)=0; Θ(3,6)=10; Θ(4,2)=22; Θ(4,5)=0; Θ(5,1)=10; Θ(5,4)=0; Θ(6,5)=8.

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

1.2. Произведем ветвление: G0=G11 G21, где G11={1,3}, а G21≠{1,3}.

1.3. Вычислим оценку для G21: ξ(G21)=ξ(G0)+Θ(1,3)=230+26=256.

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

С(1) =

1

2

4

5

6

hi

2

40

0

20

0

0

3

42

30

60

0

0

4

30

0

0

90

0

5

0

38

0

50

0

6

60

22

70

0

0

Hj

0

0

0

0

0

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

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

Расчет условий отсутствия слеминга и штормование судна с застопоренными машинами
Расчет условий отсутствия слеминга. Условия отсутствия слеминга можно определить по выражению: , где: L – длина судна, м; Тн – осадка носом, м; А – коэффициент, зависящий от Fr (число Фруда) и ; Fr = (м/с); В – ширина судна, м; &# ...

Выбор режима работы производственных подразделений
Работа производственных подразделений, занятых в АТП техническим обслуживанием, диагностикой и текущим ремонтом, должна быть согласована с режимом работы автомобилей на линии. Количество дней = 353 сменность работы по 7 часов в сутки. Вр ...

Расчет модернизированной крыши на прочность и устойчивость. Анализ результатов
Предел текучести для стали Ст3СП ГОСТ 16523-97 при толщине листов до 10 мм принимается: [σ]т = 255 МПа Для первого расчетного режима при действие двух сил по 1 кН каждая, приложенных на площадке 0,25х0,25 м и приложенных на расстоян ...