Приймаємо l11=92 км.
Для пункту P12:
l12=l7 + l7-12=59 + 48=107 км;
l12=l8 + l8-12=65 + 50=115 км;
l12=l11 + l11-12=92 + 38=130 км.
Приймаємо l12=107 км.
Для пункту P13:
l13=l7 + l7-13=59 + 66=125 км;
l13=l8 + l8-13=65 + 47=112 км;
l13=l9 + l9-13=74 + 39=113 км;
l13=l12 + l12-13=107 + 42=149 км.
Приймаємо l13=112 км.
Для пункту P14:
l14=l8 + l8-14=65 + 46=111 км;
l14=l9 + l9-14=74 + 25=99 км;
l14=l10 + l10-14=79 + 31=110 км.
Приймаємо l14=99 км.
Для пункту P15:
l15=l6 + l6-15=60 + 43=103 км;
l15=l11 + l11-15=92 + 18=110 км.
Приймаємо l15=103 км.
Для пункту P16:
l16=l11 + l11-16=92 + 33=125 км;
l16=l12 + l12-16=107 + 30=137 км;
l16=l15 + l15-16=103 + 26=129 км.
Приймаємо l16=125 км.
Для пункту P17:
l17=l12 + l12-17=107+ 28=135 км;
l17=l13 + l13-17=112 + 46=158 км;
l17=l16 + l16-17=125+ 40=165 км.
Приймаємо l17=135 км.
Для пункту P18:
l18=l13 + l13-18=112 + 28=140 км;
l18=l17 + l17-18=135 + 16=151 км.
Приймаємо l18=140 км.
Для пункту P19:
l19=l15 + l15-19=103 + 87=190 км;
l19=l16 + l16-19=125 + 35=160 км.
Приймаємо l19=160 км.
Для пункту P20:
l20=l16 + l16-20=125 + 31=156 км;
l20=l17 + l17-20=135 + 46=181 км.
Приймаємо l20=156 км.
Для пункту P21:
l21=l17 + l17-21=135 + 35=170 км;
l21=l18 + l18-21=140 + 75=215 км;
l21=l20 + l20-21=156 + 68=224 км.
Приймаємо l21=170 км.
Таблиця 1.1 - Вихідний і оптимальний варіанти моделі транспортної мережі
пункти PjРасстояніяПункти PiP1P2P3P4P5P6P7P8P9P10P11P12P13P14P15P16P17P18P19P20P21li lj02829304260596574799210711299103125135151160156170P10-28293042 ---------------- P22828-22- - 3245 --------------P3292922-23-353038 ------------- P43030-23-20- - 3 544 ------------ P54242- - 20 --- - 4037 ----------- P660-3235-- - 30-- - 40-- - 43 ------ P759-4530 --- - 27- - 334866 -------- P865-- 3835- - 27-25- - 504746 ------- P974-- - 44-- - 25-20- - 39 -------- P1079 --- - 37-- - 20-- - 31 ------- P1192 ---- - 4 033 --- - 38- - +1833 ----- P12107 ----- - 4850- - 38-42- - 3028 ----P13112 ----- - 664739- - 42 --- - 4 628 --- P1499 ------ - 462 531 ----------- P15103 ---- - 43 ---- 18 --- - 26- - 87 - P16125 --------- - 3330- - 26-- - 3531-P17135 ---------- - 2846- - 40-16-4635P18151 ----------- - 28 ------ - 75P19160 ------------- - 8735 ----- P20156 -------------- - 3146-- - 68P21170 --------------- - 3575-68 -
. 2 Поліпшення початкового варіанту мережі і визначення найкоротших відстаней
Отримані значення відстаней від пункту P1 до Pj (лівий стовпець li і верхній рядок li таблиці 1.1) перевіримо на оптимальність, тобто виконаємо можливе поліпшення початкового варіанту з метою оптимізації маршрутів. Для цього, починаючи з рядка P1, порівняємо різниці lj і li з відповідними значеннями, при цьому можливі випадки:
lj - li lt;=lji (1.3)
lj - li gt; lji (1.4)
Для клітин, в яких виконується умова (1.3), lj і li залишаємо без зміни. При виконанні умови (1.4) зробимо поліпшення варіанту за формулою:
lj=li + lji (1.5)
і потім виправляємо li у відповідному стовпці до тих пір, поки не отримаємо виконання умови (1.3).
Для стовпця P1:
l2 - l1=28 - 0=28=l1-2=28 км;
l3 - l1=29 - 0=29=l1-3=29 км;
l4 - l1=30 - 0=30=l1-4=30 км;
l5 - l1=42 - 0=42=l1-5=42 км.
Для стовпця P2:
l1 - l2=0 - 28=- 28 lt; l2-1=28 км;
l3 - l2=29 - 28=1 lt; l2-3=22 км;
l6 - l2=60 - 28=32=l2-6=32 км;...
