Пример решения задачи о кратчайшем пути

1. Пример решения задачи о кратчайшем пути

2.

Найти кратчайший путь на заданной транспортной сети из узла №3
в узел №7.

3. Построение математической модели.

Обозначим:

4. Частная мат. модель

4x12 + 3x13 +1x14 +2 x25 + 2x31 +1x43 +7x46 +5x53 +1x54 +4x57+ 4x62
+1x67 min
x31=1
x57+ x67=1
x31-( x12+ x13+ x14)=0
(x12+ x62)- x25=0
(x14+ x54)- ( x43+ x46)=0
x25- ( x53+ x54+ x57)=0
x46 - ( x62+ x67)=0
xij {0;1}

5. Решение задачи.

r=3,
s=7.
Полагаем сначала
3=0. Далее:

6. Проверка на оптимальность

Условие оптимальности выполняется для всех j.
Длина пути l( 37)= 7=11.
Путь : 37=(3,1,4,6,7)