2014-02-09
296
Метод ДП (Р. Беллман, В.С. Михалевич, Н.З. Шор) можно трактовать как алгоритмическую версию рассуждений по индукции.
Пусть sk (y), 1 £ k £ n, 0 £ y £ Y, — оптимальное значение целевой функции задачи (1) – (3), где n заменено на k, Y заменено на y.
Требуется найти sn (Y) и набор переменных, на котором достигается это значение.
ТЕОРЕМА 1. Пусть f 1, …, fn —монотонно неубывающие функции. Тогда справедливы следующие рекуррентные соотношения:
| s 1(y) = f 1(y), 0 £ y £ Y; | (4) |
| sk (y) = max { sk- 1(y - x) + fk (x) | 0 £ x £ y }, 2 £ k £ n, 0 £ y £ Y, | (5) |
Доказательство: Соотношение (4)очевидно. По определению
sk (y) ³ max { sk- 1(y - x) + fk (x) | 0 £ x £ y }.
Пусть теперь 
— такой вектор, что 
и
.
Поскольку 
имеем
.
Алгоритм ДП вычисляет множество Sk ={ sk (y) | 0 £ y £ Y}, k =1,…, n с помощью соотношений (4) и (5), где на каждом шаге оптимизируется ровно одна переменная.
| Процесс вычисления S 1,…, Sn называется прямым ходом алгоритма. Число операций» Y 2 n Память» Y n. |
|
При обратном ходе алгоритма вычисляются значения 
, с учетом того, что уже известны Sk(y). Например, 
определяется из уравнения 
и так далее.
Число операций» Y n. Память» Y n.
