p>
Наближення k=1.
Визначимо час прямування по можливому маршруту з i-го вузла у вузол 16 (пункт D2), що проходить через j-й вузол, з числом проміжних вузлів не більше одного як суму часу проходження від i-го вузла до j-го вузла і часу проходження по прямому маршруту з цього вузла у вузол 16 (пункт D2):
, i=1,2, ... 17, j=1,2, ... 17, i? 16, j? 16,.
Як найменшого часу проходження по маршруту з i-го вузла у вузол 16 приймається мінімальне з можливих значень:
.
Отримані маршрути з кожного вузла у вузол 16 і значення часів проходження по ним занесемо в таблицю 5.12 (додаток).
Наближення k=2.
Визначимо час прямування по можливому маршруту з i-го вузла у вузол 16, що проходить через j-й вузол, з числом проміжних вузлів не більше двох, як суму часу проходження від i-го вузла до j-го вузла і часу проходження за маршрутом з j-го вузла у вузол 16 з числом вузлів не більше одного:, i=1,2, ... 17, j=1,2, ... 17, i? 16, j? 16, i? j.
Як мінімального часу проходження по маршруту з i-го вузла у вузол 16 приймається мінімальне значення з можливих:
.
Отримані маршрути з кожного вузла у вузол 16 і значення часів проходження по ним занесемо в таблицю 5.12 (додаток).
Наближення k=3.
Визначимо час прямування по можливому маршруту з i-го вузла у вузол 16, що проходить через j-й вузол, з числом проміжних вузлів не більше трьох як суму часу проходження від i-го вузла до j-го вузла і часу проходження по маршруту з j-го вузла у вузол 16 з числом вузлів не більше двох:
, i=1,2, ... 17, j=1,2, ... 17, i? 16, j? 16, i? j.
Як найменшого часу проходження по маршруту з i-го вузла у вузол 16 приймається мінімальне з можливих значення:
.
Отримані маршрути з кожного вузла у вузол 16 і значення часів проходження по ним занесемо в таблицю 5.12 (додаток).
Наближення k=4
Визначимо час прямування по можливому маршруту з i-го вузла у вузол 16, що проходить через j-й вузол, з числом проміжних вузлів не більше чотирьох як суму часу проходження від i-го вузла до j-го вузла і часу проходження по маршруту з j-го вузла у вузол 16 з числом вузлів не більше трьох:
, i=1,2, ... 17, j=1,2, ... 17, i? 16, j? 16, i? j.
Як найменшого часу проходження по маршруту з i-го вузла у вузол 16 приймається мінімальне з можливих значення:
.
Результати розрахунків показують, що на
іменьшее час проходження по маршруту з числом проміжних вузлів не більше чотирьох виявляється рівним довжині мінімального часу проходження по маршруту з числом проміжних пунктів не більше трьох. У зв'язку з цим подальші розрахунки припиняються.
У таблиці 5.12 (додаток) для кожного наближення наведені отримані маршрути у вузол 16 і значення часу проходження по ним.
Шукані маршрути з мінімальними значеннями часів прямування у вузол 16 (пункт D2):
З вузла 1 (пункт A1): 1-8-12-16 (A1-E3-E7-D2); час перевезення 24;
З вузла 2 (пункт A2): 2-10-13-12-16 (A2-E5-Е8-E7-D2); час перевезення 21;
З вузла 3 (пункт A3): 3-10-13-12-16 (A3-E5-Е8-E7-D2); час перевезення 28;
З вузла 4 (пункт A4): 4-13-12-16 (A4-E8-Е7-D2); час перевезення 18;
З вузла 5 (пункт A5): 5-16 (A5-D2); час перевезення 126;
.3.6 Пункт D1
Побуду...
