Условие:
В транспортной сети (рис. 1) имеется несколько маршрутов по проезду из начального пункта 1 в конечный пункт 11. Стоимость проезда между отдельными пунктами транспортной сети представлена в соответствующей таблице 12. Необходимо определить оптимальный маршрут проезда из пункта 1 в пункт 11 с минимальными транспортными расходами.
Рис. 1. Транспортная сеть
Таблица 12
Решение:
Уравнение Беллмана:
S пункт отправления, j пункт назначения, tsj стоимость проезда отправления в пункт назначения.
Этап 1. Условная оптимизация:
1-й шаг. F1(S) = ts11.
Заполняем таблицу 13 используя данные таблицы 12 и рис. 1. Из пункта 11 можно попасть в пункты 8, 9, 10 (первый столбец табл. 13), при этом расстояния до этих пунктов 9, 3, 11 берутся из таблицы 12 ...