8. Модели динамического программирования

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

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

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

В динамическом программировании можно выделить следующие аспекты: теоретический (доказательство теорем существования, единственности, сходимости), прикладной (построение моделей для конкретных задач оптимизации) и вычислительный. Для нас решающим является второй и в некоторой степени третий аспект.

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

< Предыдущая		Следующая >