Динамическое программирование. Понятие задачи динамического программирования

Рассмотрим работу некоторой системы.

В результате управления система последовательно переводится из начального состояния S_o в конечное S_n. Предположим, что управление можно разбить на п шагов и решение принимается последователь­но на каждом шаге, а управление представляет собой совокуп­ность п пошаговых управлений.

На каждом шаге необходимо определить два типа переменных - переменную состояния систе­мы S_k и переменную управления х_k. Переменная S_k определяет, в каких состояниях может оказаться система на рассматриваемом k-м шаге. В зависимости от состояния S на этом шаге можно при­менить некоторые управления, которые характеризуются переменной x_k, которые удовлетворяют определенным ограничениям и называются допустимыми.

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

При использовании ДП многошаговая задача решается дважды: от конца к началу (определение условно-оптимального решения) и от начала к концу (определение безусловно-оптимального решения).

Первый этап длительный и трудоемкий, второй – короткий и уточняет решения первого этапа.

Недостатки ДП - прежде всего в нем нет единого универсального метода решения, длительность и трудоемкость.

Достоинства ДП – можно проследить результат на каждом шаге.