dynamic_programming (Лекции ЮКР)

ЗАНЯТИЕ №1.

Общее понятие о методе динамического программирования.

Учебные вопросы:

1. Сущность метода динамического программирования.

2. Задача об оптимальном управлении.

3. Алгоритм численного метода решения задачи.

ЗАНЯТИЕ №2.

Вычислительная схема динамического программирования.

Учебные вопросы:

1. Задача об оптимальном распределении ресурсов.

2. Алгоритм решения задачи.

СОДЕРЖАНИЕ ЗАНЯТИЯ №1.

Учебный вопрос №1. СУЩНОСТЬ МЕТОДА ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ.

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

Найти --число.

1. Параметризуем задачу и вместо одной будем решать целый класс задач: --параметр.

2. Представим как функцию параметра :

и напишем для рекуррентное соотношение. Так как , то, положив , где --малая величина, получим:

(*)

1. Если непрерывно дифференцируема, то

, откуда

Очевидно, , тогда . В частном случае ,

Заметим, что для решения задачи можно непосредственно воспользоваться соотношением (*), последовательно полагая

.

Учебный вопрос №2. ЗАДАЧА ОБ ОПТИМАЛЬНОМ УПРАВЛЕНИИ.

Дан функционал

при условии , и -заданные функции; -управление; и --заданные числа; --определенная область.

В общем случае -мерный, а -m-мерный векторы.

1. Параметризуем задачу:

варьируемые параметры.

В каждый изменяемый момент времени t будет рассматриваться множество возможных начальных состояний .

1. Введем функцию Беллмана.

Установим для нее рекуррентное соотношение

Применим к этому равенству оператор ,

, где

.

Функциональное уравнение (**) называется уравнением Беллмана. Заметим, что , т. к. .

Учебный вопрос №3. АЛГОРИТМ ЧИСЛЕННОГО РЕШЕНИЯ ЗАДАЧИ.

Разобьем отрезок на интервалы .

Положим

Во введенных обозначениях уравнение Беллмана запишется:

.

Таким образом, непрерывный управляемый процесс мы заменили дискретным.

t

0

Поскольку , т. к. , то при имеем:

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

Далее проведем те же вычисления для и т. д. до некоторого .

Когда , то

Построим таблицу:

При начальное значение нам задано, поэтому варьировать не надо и таблица вырождается в строку:

Найдем , как и раньше, и будет искомым значением функционала. Теперь можно построить оптимальную траекторию фазовой координаты и найти оптимальное управление .

, по соответствующей таблице находим

Для данной задачи принцип Беллмана (необходимое условие оптимальности) можно сформулировать следующим образом:

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

СОДЕРЖАНИЕ ЗАНЯТИЯ №2.

Учебный вопрос №1. ЗАДАЧА ОБ ОПТИМАЛЬНОМ РАСПРЕДЕЛЕНИИ РЕСУРСОВ.

Пусть требуется распределить выстрелов по единицам рассредоточенной ГЦ, чтобы обеспечить

,

где --вероятность поражения k-й единицы при одном выстреле.

В общем случае

при ограничениях (могут быть целочисленными); --доход от i-го ресурса.

1. Параметризуем задачу:

-параметр, ; -параметр.

1. Введем функцию Беллмана:

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

Если выбирается также из условия оптимальности, то получим:

, начальное условие .

Учебный вопрос №2. АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ.

При имеем:

При : и т. д.

При : .

Составим следующую таблицу:

Покажем, что , где

. При имеем

При

и т. д.

Для заданного по таблице найдем:

и есть решение задачи.

Лекции составил

подполковник В. Ярошенко