5.8.1. Теория динамического программирования

Иснользованный выше процесс последовательной оптимизации можно применить для большого класса задач. При этом функция, которую нужно оптимизировать, должна удовлетворять нескольким условиям самого общего характера.

Определение. Функция от трех действительных переменных, принимающая действительные значения, называется разложимой (представимой в виде суперпозиции функций от двух переменных), если

1) существуют две функции и такие, что можно записать

2) функция является монотонно неубывающей по отношению ко второй переменной:

Динамическое программирование основано на следующей теореме.

Теорема оптимальности. Для любой разложимой функции от трех переменных, удовлетворяющей соотношению справедливо выражение

По этой теореме подсчет оптимума некоторой функции от трех переменных сводится к последовательному вычислению двух оптимумов функций от двух переменных. (Ее доказательство можно найти в работе (Lauriere, 1979)). Чаще всего эта теорема используется для функций оптимизации от переменных вида

где — разложимая функция, относится к тому же типу функций, что и т. е. также является разложимой. Следовательно, можно написать

что соответствует схеме динамического программирования, которое обычно называют методом оптимизации, основанным на рекуррентных соотношениях. Исходные предположения легко, в частности, проверить, когда является суммой элементарных значений одной переменной, как в приведенном выше примере.

В настоящее время данный метод успешно применяется в управлении складами, ракетами, технологическими процессами (особенно в химии), в экономическом планировании, в теории игр и в теории вероятностей.