Найти наиболее экономный маршрут доставки груза методом динамического программирования

На данной сети дорог имеется несколько маршрутов, по которым можно доставить груз из пункта 1 в пункт 10. Известны стоимости с_ij перевозки единицы груза между пунктами сети.

Требуется методом динамического программирования найти на сети наиболее экономный маршрут доставки груза из пункта 1 в пункт 10 и соответствующие ему затраты.

Введем обозначения:

• ... номер этапа
• ... пункт, из которого осуществляются перевозки
• ... пункт, в который доставляется груз (от 2 до 10)
• ... стоимость перевозки единицы груза из пункта в пункт
• ... минимальные затраты на перевозку груза из пункта в конечный пункт, если до него осталось этапов

Весь процесс доставки груза из 1 в 10 разбиваем на этапы:

На 1-ом этапе транспорт с грузом из пункта 1 перемещается в пункты ...

На 2-ом этапе из ...

Задача решается, начиная с пункта ... Запишем функциональное уравнение для ...

Таким образом, оптимальный маршрут ... с наименьшими затратами ... единиц.