Решение многошаговых задач оптимизации методом динамического программирования — КиберПедия 

Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...

Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...

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

2018-01-07 478
Решение многошаговых задач оптимизации методом динамического программирования 0.00 из 5.00 0 оценок
Заказать работу

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

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

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

В уравнении в момент времени задается дискретными значениями.

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

Для многошаговых систем будем иметь

, где ; (11)

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

Блок-схема многошагового процесса имеет вид (Рис.2):

X(1)
X( -1)
X()
X(2)
X(0)

Рис.2

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

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

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

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

Первый подход.

Возьмем в качестве параметров многошаговой задачи оптимизации начальный момент времени и начальное состояние . Тогда функция оптимального поведения равна оптимальному значению целевой функции J задачи с начальным состоянием и начальным моментом времени . Тогда оптимальное значение целевой функции исходной задачи равно: . Согласно принципу оптимальности Беллмана:

, где , .

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

.

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

Второй подход.

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

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

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

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

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

.

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

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

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

.

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

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


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

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

Постановка задачи.

Найти ,

при ограничениях

Решение:

Будем решать данную задачу методом динамического программирования. В данной задаче можно интерпретировать постоянную как общий уровень имеющихся ресурсов и рассматривать ее в качестве параметра задачи. Обозначим через – функцию оптимального поведения для процесса развертывания в момент времени с общим запасам ресурсов .

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

.

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

Общее рекуррентное соотношение имеет вид

Решение задачи отыскивается с помощью общего рекуррентного соотношения, последовательно начиная с граничного условия , вплоть до шага (длина шага ) (C).



Поделиться с друзьями:

Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...

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

Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...

Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.027 с.