2. Задача должна допускать расширение на произвольное число шагов. При этом структура задачи не должна зависеть от числа шагов


Скачать 94.79 Kb.
Название2. Задача должна допускать расширение на произвольное число шагов. При этом структура задачи не должна зависеть от числа шагов
Дата публикации16.03.2013
Размер94.79 Kb.
ТипЗадача
userdocs.ru > Математика > Задача
Динамическое программирование
Рассмотрим задачи дискретного программирования, которые относятся к так называемому классу задач динамического программирования. Одним из наиболее часто применяемых и наиболее эффективных методов решения таких задач является метод динамического программирования Р. Беллмана, основанный на принципе оптимальности Беллмана. Изложение указанного метода удобно будет проводить применительно к задачам управления дискретными динамическими (многошаговыми) процессами (системами).

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

1. Задачу можно описать как многошаговый процесс принятия решений.

2. Задача должна допускать расширение на произвольное число шагов. При этом структура задачи не должна зависеть от числа шагов.

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

4. Выбор решения, принимаемого на некотором k-м шаге не должен влиять на решения, принятые на предыдущих шагах.

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

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

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

Итак, рассмотрим систему, изменение состояния которой происходит в дискретные моменты времени t = 1, 2, …, T за счет управляющих воздействий. Пусть x(t) – n-вектор-столбец переменных, описывающих состояние системы; начальное состояние системы задается вектором x(0) = x0; u(t) – m-вектор-столбец управляющих воздействий. Дискретный процесс описывается уравнением

(1)

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

(2)

Заметим, что обобщение на случай множества ^ U, зависящего от времени осуществляется достаточно просто.

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

Определение. Уравнение (1) вместе с начальным условием x(0) = x0 и условием (2) определяет так называемую дискретную управляемую динамическую систему.

Качество управления динамической системой характеризует аддитивный функционал вида

(3)

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

Оптимизационная задача формулируется следующим образом. Требуется при заданном начальном условии x(0) = x0 найти такое допустимое управление, то есть такую последовательность при которой достигается наибольшее (или наименьшее) значение функционала качества J. При этом будем называть оптимальным управлением, а соответствующую ему последовательность векторов состояния будем называть оптимальной траекторией движения динамической системы.

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

(4)

(5)
(6)

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

Определение. Будем называть (t, x)-задачей следующую задачу оптимального управления:

(7)

(8)

(9)

Сформулируем общую задачу: требуется решить (t, x)-задачи (7)-(9) для всех t = 0, 1, …, T.

Решение исходной задачи (4)-(6) получается как решение (t, x)-задачи при t = 0.
Функция Беллмана
Определение. Функцией Беллмана будем называть

(10)

то есть оптимальное значение показателя качества управления текущей (t, x)-задачи.

Легко заметить, что

1) ; (11)

2) значение функции Беллмана

(12)

соответствует решению исходной оптимизационной задачи (4)-(6), а соответствующие значения управляющих воздействий определяют оптимальное управление, последовательность векторов определяет оптимальную траекторию динамической системы.
^ Уравнение Беллмана
Выведем уравнение, которое является основой метода динамического программирования Беллмана. Предположим, что в момент времени s = t – 1 состояние системы было x = x(t – 1). Функционал качества управления



представим в виде



Далее вместо x(t – 1) будем писать просто x. Второе слагаемое в правой части равенства есть поэтому







Здесь во второй строчке преобразований учтено уравнение движения системы

Используя полученную формулу, запишем функцию Беллмана в следующем виде:









Для краткости запишем вместо u(t) просто u и придем к рекуррентному уравнению Беллмана:

(В)

Уравнение Беллмана это рекуррентное функциональное уравнение с параметром t, который пробегает значения T, T - 1, …, 1.
Решение уравнения Беллмана
I. Решение уравнения Беллмана в обратном времени. Найдем из рекуррентного уравнения (В) функции Беллмана при различных значениях параметра:

0)

1) t = T;



В результате поиска максимума по получается так называемое условно-оптимальное управление

2) t = T - 1;



- условно-оптимальное управление.

3) t = T - 2;



- условно-оптимальное управление.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

T – 1) t = 2;



- условно-оптимальное управление.

T) t = 1;



- условно-оптимальное управление.

II. Нахождение оптимального управления и оптимальной траектории. Условно-оптимальное управление имеет следующий смысл. Это оптимальное управление на шаге t в (t, x)-задаче, в которой состояние системы в предыдущий момент x(t – 1) является начальным условием. Этот факт используем для нахождения оптимального управления.

1) В момент t = 0 состояние системы известно (x(0) = x0), то оптимальное управление на шаге 1 будет иметь вид



Тогда состояние системы в момент 1 будет



2) Теперь в момент t = 1 состояние системы известно (x(1) = x*(1)), поэтому оптимальное управление на шаге 2 будет



а состояние системы в момент 2 будет



- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

^ Т) Аналогичным образом оптимальное управление на шаге Т будет



а состояние системы в момент Т



В результате мы получили оптимальное управление и оптимальную траекторию. Значение функционала качества при оптимальном управлении равно F(0, x0).
Алгоритм метода динамического программирования
1. Составляется уравнение Беллмана



2. Путем решения в обратном времени уравнения Беллмана («обратный ход») находятся условно-оптимальные управления u*(t, x), а также функции Беллмана F(t, x) (t = T, T – 1, …, 1).

3. С помощью рекуррентных уравнений «прямого хода»





определяются оптимальные управления u*(t) и оптимальная траектория движения дискретной динамической системы x*(t) (t = 1, 2, …, T).

4. Находится оптимальное значение показателя качества управления F(0, x0).

Замечание. Так как аналитические выражения для условно-оптимальных управлений u*(t, x) при решении практических задач получаются редко, то их обычно табулируют, используя некоторую сетку по переменной х. А при вычислении оптимальных управлений при необходимости, применяют один из алгоритмов интерполяции.
^ Пример применения метода динамического программирования
Пусть имеется фирма, состоящая из двух предприятий. Рассмотрим задачу оптимального распределения средств фирмы на протяжении Т лет. На начало планового периода фирма располагала средствами x(0) = x0.

Деятельность предприятий организована таким образом, что средства u, вложенные в предприятие i (i = 1, 2), приносят в течение года доход fi(u), причем часть дохода поступает в централизованный фонд фирмы. Средства из этого фонда x(t – 1) (t = 1, 2, …, T) в начале года t определенным образом перераспределяются между предприятиями и идут на их развитие. Обозначим через ui(t) (i = 1, 2) cредства, выделяемые для развития предприятиям в начале года t. Предполагается, что средства централизованного фонда полностью расходуются:



Состоянием фирмы будем считать переменную x(t), в качестве управляющих переменных возьмем u1(t) и u2(t). Тогда изменение состояния фирмы будет описываться уравнением



Управляющие воздействия удовлетворяют ограничению



Показателем качества управления является суммарный доход, полученный от деятельности предприятий в течение Т лет:



Приходим к следующей задаче оптимального управления:









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

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



Тогда мы можем переписать задачу оптимального управления в виде:







В модифицированной задаче оптимального управления одна переменная состояния и одна управляющая переменная. Уравнение состояния является нелинейным разностным уравнением 1-го порядка.

Предполагаем, что сформулированная задача имеет решение. Для этого достаточно, чтобы функции были непрерывными и начальное состояние не было нулевым: х0 > 0.

Для решения задачи используем метод динамического программирования Беллмана. Построим функцию Беллмана для рассматриваемой задачи:



Уравнение Беллмана имеет вид:

В дальнейшем конкретизируем вид фигурирующих в задаче функций.

Положим Т = 4; х0 = 10000;



Для простоты в дальнейшем будем употреблять обозначение u = u1.

Уравнение движения будет иметь вид:



С учетом конкретного вида функций уравнение Беллмана выглядит так:



Решаем уравнение Беллмана в обратном времени и находим условно-оптимальные управления:

0)

1)



2)





3)





4)





Теперь, используя условно-оптимальные управления и уравнение движения, найдем оптимальные управления и оптимальную траекторию:

1)



2)



3)



4)



Итак, оптимальное управление имеет вид:



Оптимальная траектория



Максимальный доход от деятельности фирмы равен


Похожие:

2. Задача должна допускать расширение на произвольное число шагов. При этом структура задачи не должна зависеть от числа шагов iconЛ. Г. Попова десять шагов к себе
Попова Л. Г. Десять шагов к себе: Методические материалы по курсу «Имидж специалиста социально-культурной сферы». — М., 2004
2. Задача должна допускать расширение на произвольное число шагов. При этом структура задачи не должна зависеть от числа шагов icon1 глава. Новый Мятежник
Пройдя по нему несколько шагов, я дошел до входной черной двери и открыл ее. Передо мной был пустой и грязный дворик, я двинулся...
2. Задача должна допускать расширение на произвольное число шагов. При этом структура задачи не должна зависеть от числа шагов iconПрограмма и их Добрая Книга, доктор боб и ответ «доброй книги1»
Шагов. Я не выдумывал эту Программу и не изобретал 12 Шагов. Основные идеи этой программы, хотя и не в столь сжатой и четкой форме,...
2. Задача должна допускать расширение на произвольное число шагов. При этом структура задачи не должна зависеть от числа шагов icon7 шагов к успеху
...
2. Задача должна допускать расширение на произвольное число шагов. При этом структура задачи не должна зависеть от числа шагов icon1. Расчет расходов теплоносителя по участкам тепловой сети
Схема должна обеспечивать надежность и экономичность эксплуатации; протяженность сети должна быть минимальной, а конфигурация по...
2. Задача должна допускать расширение на произвольное число шагов. При этом структура задачи не должна зависеть от числа шагов iconНедружелюбный Можайск «Нужный человек не в том месте может изменить мир»
Пройдя по нему несколько шагов, я дошел до входной черной двери и открыл ее. Передо мной был пустой и грязный дворик, я двинулся...
2. Задача должна допускать расширение на произвольное число шагов. При этом структура задачи не должна зависеть от числа шагов icon«Землеустройство и кадастры» и «Геодезия и дистанционное зондирование»
Каждый современный абитуриент выбирает будущую профессию, руководствуясь следующим: выбранная профессия должна быть востребована...
2. Задача должна допускать расширение на произвольное число шагов. При этом структура задачи не должна зависеть от числа шагов iconНил Барнард, доктор медицины, основатель и президент Комитета врачей...
Скрытые причины пищевых пристрастий и 7 шагов к естественному освобождению от них
2. Задача должна допускать расширение на произвольное число шагов. При этом структура задачи не должна зависеть от числа шагов icon«Организационное поведение»
Структура организации определяет, каким образом должны быть распределены задачи, какой должна быть субординация, как организована...
2. Задача должна допускать расширение на произвольное число шагов. При этом структура задачи не должна зависеть от числа шагов icon«Теория организации»
Структура организации определяет, каким образом должны быть распределены задачи, какой должна быть субординация, как организована...
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2015
контакты
userdocs.ru
Главная страница