4.Задача выбора кратчайшего пути

Задача выбора кратчайшего пути

Как и в транспортной задаче с промежуточными пунктами считаем, что каждойориентированной дуге сети соответствует переменная модели хij представляющее собой ко­личество товара, которое должно быть отправленос i-го складана j-й. Длякаждого к-го промежуточного пункта вводимпеременные хкк с соот­ветствующими им коэффициентами скк = 0в целевойфункции, а величи­ну чистого запаса обозначаем через Тк. Тогдав общем случае математическую постановку задачи выбора кратчайшего пути можно записать следующим образом.

Пример

Пусть задана транспортная сеть, изображенная на 1-ом слайде. Нужно найти кратчайший путь от пункта с номером 1 до

пункта с номером 8, если с12 = 1 км, с13 = 4 км,

с14 = 6 км, с23 = 3 км, с26 = 5 км, с27 = 1 км, c34 —

3км, с35 = 5 км, с45 = 1 км, c48 = 4 км, с54 = 1 км,

с56 = 1 км, с58 = 2 км, с65 = 1 км, c67 = 3 км, с68 =

4км, с72 = 1 км, C76 = 3 км, с78 =7 км.

Исходныеданныео задачи о выборе кратчайшего пути

Окнопоискрешения

Параметрыпоискрешения

Сообщение

Результаты