Решение многошаговых (многоэтапных) задач оптимизации методом динамического программирования.

Во многих задачах динамического программирования время рассматривается непрерывно или как дискретная величина. Задачи такого типа называются многошаговыми (многоэтапными) задачами оптимизации. Их можно решать методом динамического программирования.

В многошаговых задачах оптимизации время принимает дискретные значения: .

Состояние системы в момент времени задается вектором: , где , .

В уравнении в момент времени задается дискретными значениями. Рассмотрим простейшую многошаговую систему (одношаговая система). Начальное состояние системы записывается известным вектором . Выбор некоторого управления определяет переход системы из в состояние . Этот переход описывается соотношениями: .

На рисунке 2 показан пример дискретной одномерной системы.

Для многошаговых систем:

, где ; , (11)

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

,

,

.

Блок схема многошагового процесса показана на рисунке 3:

Предполагаем, что задано начальное состояние . Требуется найти такую последовательность векторов фиксированной области управления , где . Эта последовательность, которая максимизирует целевую функцию:

, (A)

Таким образом, данная задача аналогична задачи оптимального управления (с непрерывным временем), (Смотри(11)).

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

Пункт А:

Возьмем в качестве параметров многошаговой задачи оптимизации начальный момент времени и начальное состояние . Тогда ФОП равна оптимальному значению целевой функции (A)задачи с начальным состоянием и начальным моментом времени , ( ). Тогда оптимальное значение целевой функции рассматриваемой задачи равно: . Согласно принципу оптимальности Беллмана:

, где , .

Это означает, что оптимальное значение целевой функции задачи с начальным состоянием и начальным моментом времени оптимальному максимальному значению суммы двух слагаемых функции в момент времени и оптимальному значению в момент времени . Используя уравнение (11)можно представить:

.

Граничное условие будет: – показывает, что оптимальное значение целевой функции с начальным состоянием в момент времени равно (совпадает) со значением функции конечных параметров, рассчитанных при . Данная задача аналогична задачи оптимального управления с непрерывным временем.

Пункт В:

Другой подход при решении многошаговых задач оптимизации состоит в том, что в качестве характеристических параметров выбираются не начальные состояния и не начальный момент времени, а начальное состояние и промежуток времени, остающийся до конечного момент времени. Тогда ФОП – которая представляет собой оптимальное значение целевой функции с начальным состоянием , разворачивающаяся в промежутке протяженностью .Оптимальное значение целевой функции исходной задачи (A)соответственно равно: – когда . В этом случае последовательность решений определяется методом динамического программирования в порядке, обратном тому, который рассматривается до сих пор. Первым членом этой последовательности является: , то есть оптимальное значение целевой функции с временным промежутком нулевой протяженности, начинающейся (и заканчивающейся) в . Оптимальное значение целевой функции этой задачи равно функции конечных параметров: .

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

Оптимальное значение в этой задачи определяется как максимум значения суммы той части целевой функции, которая соответствует указанному времени, и оптимальное значение задачи с моментом времени с управляющим вектором :

.

Используя уравнение перехода: , получаем:

.

Данный выбор управления на первом шаге согласуется с принципом оптимальности Беллмана.

Аналогично этому, на втором шаге (в задаче с промежутком равным двум промежуткам времени) получим:

.

Общее рекуррентное соотношение на шаге с номером выглядит следующим образом:

.

В рассмотренной задаче, оптимальное значение равно: – является оптимальным значением последней задачи в последовательности одношаговых задач оптимизации, описываемых функциональным уравнением, при , с граничным условием: . Вместо того, что бы решать эту задачу методом НЛП (выбирать сразу ), то здесь мы решаем последовательность многошаговых задач оптимизации.

Не нашли, что искали? Воспользуйтесь поиском по сайту: