Решение многошаговых (многоэтапных) задач оптимизации методом ДП.

Во многих динамических задачах время рассматривается не как непрерывная, а как дискретная величина. Задачи такого типа называются многошаговыми (многоэтапными) задачами оптимизации, которые можно решать методом ДП. В многошаговых задачах оптимизации время принимает значение . Состояние системы в момент времени задаётся вектором . Рассмотрим простейшую многошаговую систему-одношаговую. X( ) илиx( ) выбор некоторого вектора управления U(0) определяет переход системы x(0)→x(1). Этот переход описывается состоянием или .

Это блок схема дискретной одношаговой системы.

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

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

Предполагаем, что задано начальное состояние ; требуется найти такую последовательность векторов , принадлежащие .

(А)

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

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

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

Граничное условие:

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

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

.

В этом случае последовательность решений определяется методом ДП в порядке обратном тому, который рассматривали до сих пор.

Первым членом этой последовательности будет , то есть оптимальное значение с временным промежутком нулевой протяженности начинающейся (и заканчивающейся) в . Оптимальное значение этой задачи равно функции конечных параметров. Рассмотрим -оптимальное значение целевой функции задачи с промежутком, равным 1 единице времени ( =1), начинающимся в . Эта задача называется первым шагом. Оптимальное значение в этой задаче определяется как максимальное значение суммы той части целевой функции, которая соответствует указанному времени и оптимальное значение задачи с моментом времени с управляющим вектором :

.

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

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

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

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

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

Задача.

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

Решение.

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

Можно интерпретировать постоянную С, как общий уровень имеющихся ресурсов и рассматривать её в качестве параметра задачи. Обозначим, через ФОП для процесса, развёртывающегося в момент времени с общим запасом ресурсов равным С.

Дата добавления: 2015-12-08