16.5. Задача динамического программирования в терминах теории графов.

На языке теории графов принцип оптимальности Беллмана можно сформулировать следующим образом. Предположим, что уже были найдены длины Zi+1, Zi+2,..., Zn оптимальных путей из вершин si+1, si+2,..., sn соответственно, а множество D-(si) состоит из дуг (si, ), (si, ), …, (si, ). Тогда Zi равно наибольшей (наименьшей) из сумм

+, +, …, +,

т. е. Zi=, где ехtr обозначает максимум или минимум в зависимости от того, являются ли веса fik доходами или затратами соответственно. Рассмотрим применение описанного метода к решению некоторых экономических задач.