Поиск кратчайших расстояний на транспортной сети

Исходные дынные

Начальная вершина – Смоленск

Вершины транспортной сети: Александров,Брянск, Вязьма, Горбачево, Дмитров, Занозная, Калуга, Куровская, Курск, Манихино, Москва, Орел, Петушки, Рославль, Ряжск I, Рязань, Смоленск, Столбовая, Сухиничи, Унеча.

Транспортная сеть.

Рис. Схема транспортной сети

Таблица - Соответствия номеров транспортной сети названиям железнодорожных станций

Транспортная сеть.

Конечные вершины 1; 5; 7; 9; 12; 13; 15; 16; 18; 20; 21; 22.

Поиск кратчайшего пути с помощью макроса TOP в MS Excel

Решение транспорной задачи в сетевой постановке методом сокращения невязки

Объемы производства и потребления грузов для вершин транспортной сети

ТОП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