Поиск кратчайших расстояний на транспортной сети
Исходные дынные
Начальная вершина – Смоленск
Вершины транспортной сети: Александров,Брянск, Вязьма, Горбачево, Дмитров, Занозная, Калуга, Куровская, Курск, Манихино, Москва, Орел, Петушки, Рославль, Ряжск I, Рязань, Смоленск, Столбовая, Сухиничи, Унеча.
Транспортная сеть.
Рис. Схема транспортной сети
Таблица - Соответствия номеров транспортной сети названиям железнодорожных станций
| Номер вершины | Название железнодорожной станции |
| Александров | |
| Брянск | |
| Вязьма | |
| Горбачево | |
| Дмитров | |
| Занозная | |
| Калуга | |
| Куровская | |
| Курск | |
| Манихино | |
| Москва | |
| Орел | |
| Петушки | |
| Рославль | |
| Ряжск I | |
| Рязань | |
| Смоленск | |
| Столбовая | |
| Сухиничи | |
| Унеча | |
| Тула | |
| Кубинка | |
| Фаянсовая |
Транспортная сеть.
| 1эт. | 17-14: М-0>122 p14=122 17-6: М-0>167 p6=167 17-3: М-0>176 p3=176 | 4эт. | 12-4: 348-388<107 4-12: 388-348<107 4-21: 419-348<82 4-15: М-348>204 p15=552 18-21: 419-438<130 18-11: 419-419<62 11-18: 438-419<62 11-16: М-419>158 p16=577 11-8: М-419>67 p8=486 11-13: М-419>205 p13=624 11-1: М-419>112 p1=531 11-5: М-419>65 p5=484 11-10: 410-419<52 10-11: 419-401<52 10-5: 484-401>77 p5=478 21-7: 340-419<141 21-18: 438-419<130 21-15: 552-419<144 21-4: 484-419<82 | |
| 2эт. | 14-2: М-122>255 p2=255 14-22: М-122>233 p22=233 6-22: 233-167>34 p22=201 6-19: М-167>34 p19=240 6-3: 176-167<105 – 3-6: 167-176<105 – 3-7: М-167>164 p7=340 3-23: М-176>180 p23=356 | |||
| 3эт | 2-20: М-255>139 p20=394 2-9: М-255>286 p9=541 2-12: М-255>133 p12=388 2-19: 240-255<122 2-22: 201-255<94 22-14:122-201<111 22-2: 255-201<94 22-19: 201-176<76 7-21: M-340>141 p21=481 23-18: М-356>82 p18=438 23-10: М-356>45 p10=401 23-11: М-356>63 p11=419 19-6: 167-240<63 19-22: 201-240<63 19-4: М-240>108 p4=348 19-21: 481-240>179 p21=419 | |||
| 5эт | 1-5: 476-531<58 1-13: 624-531<115 5-11: 401-476<65 5-1: 531-476<58 8-13: 624-486>137 p13=623 13-1: 531-623<115 13-8: 486-623<137 16-15: 577-552<116 15-16: 552-577<116 15-21: 419-552<144 | |||
| 4эт. | 20-9: 541-394<466 9-20: 394-541<466 9-12: 388-541<154 12-9: 541-388<154 | |||
| 6эт | 8-13: 623-486<137 13-8: 486-623<137 |
| 1этап | 2этап | 3этап | 4этап | 5этап | 6этап | |||||||||
| i | li | pi | li | pi | li | pi | li | pi | li | pi | li | pi | li | pi |
| М | М | М | М | -11 | ||||||||||
| М | М | -14 | ||||||||||||
| М | -17 | |||||||||||||
| М | М | М | -19 | |||||||||||
| М | М | М | М | -10 | ||||||||||
| М | -17 | |||||||||||||
| М | М | -3 | ||||||||||||
| М | М | М | М | -11 | -11 | |||||||||
| М | М | М | -2 | |||||||||||
| М | М | М | -23 | |||||||||||
| М | М | М | -23 | |||||||||||
| М | М | М | -2 | |||||||||||
| М | М | М | М | -11 | -8 | |||||||||
| М | -17 | |||||||||||||
| М | М | М | М | -4 | ||||||||||
| М | М | М | М | -11 | ||||||||||
| -17 | ||||||||||||||
| М | М | М | -23 | |||||||||||
| М | М | -6 | ||||||||||||
| М | М | М | -2 | |||||||||||
| М | М | М | -19 | |||||||||||
| М | -6 | |||||||||||||
| М | М | -3 |
Конечные вершины 1; 5; 7; 9; 12; 13; 15; 16; 18; 20; 21; 22.
| S17-1 | (1,11,23,3,17)= | |
| S17-5 | (5,10,23,3,17)= | |
| S17-7 | (7,3,17)= | |
| S17-9 | (9,2,14,17)= | |
| S17-12 | (12,2,14,17)= | |
| S17-13 | (13,8,11,23,3,17)= | |
| S17-15 | (15,4,19,6,17)= | |
| S17-16 | (16,11,23,3,17)= | |
| S17-18 | (18,23,3,17)= | |
| S17-20 | (20,2,14,17)= | |
| S17-21 | (21,19,6,17)= | |
| S17-22 | (22,6,17)= |
Поиск кратчайшего пути с помощью макроса TOP в MS Excel
Решение транспорной задачи в сетевой постановке методом сокращения невязки
Объемы производства и потребления грузов для вершин транспортной сети
| Груз | Цемент | |
| Объемы производства (с плюсом) и потребления (с минусом) | Дмитров | |
| Александров | ||
| Петушки | ||
| Куровская | -57 | |
| Рязань | -69 | |
| Ряжск I | ||
| Калуга | ||
| Вязьма | ||
| Манихино | ||
| Москва | -67 | |
| Столбовая | ||
| Занозная | ||
| Брянск | -97 | |
| Рославль | -51 | |
| Смоленск | ||
| Сухиничи | -29 | |
| Горбачево | -87 | |
| Курск | ||
| Унеча | ||
| Орел |
ТОП1
Получаем оптимальные маршруты:
S[3,7];
S[6,22,2], S[6,19,4];
S[9,12];
S[10,11,8], S[10,11,16], S[10,23];
S[17,14];
S[18,21,15].
ТОП 2
Получаем оптимальные маршруты:
S[1,5];
S[3,7];
S[9,12];
S[17,14];
S[18,21,15], S[18,11,16], S[18,11,8], S[18,11,10,23];
S[20,2,22,6,19,4].
Потребители присутствуют только в маршрутах S[20,2,22,6,19,4] и S[18,11,10,23]
Получили оптимальный план перевозок.
Суммарная стоимость перевозки по найденному плану :
90*139+7*94+7*34+51*122+87*108+116*73+69*158+57*67+84*62+109*52=
=63089