dynamic_programming (1156058)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

ЗАНЯТИЕ №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. АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ.

При имеем:

При : и т. д.

При : .

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

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

. При имеем

При

и т. д.

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

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

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

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

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

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

Список файлов лекций