Всем привет! ✌
Динамическое программирование – один из наиболее мощных методов оптимизации. С задачами принятия рациональных решений, выбора наилучших вариантов, оптимального управления имеют дело специалисты разного профиля. Среди методов оптимизации динамическое программирование занимает особое положение. Этот метод исключительно привлекателен благодаря простоте и ясности своего основного принципа – принципа оптимальности. Сфера приложения принципа оптимальности чрезвычайно широка, круг задач, к которым он может быть применен, до настоящего времени еще полностью не очерчен. Динамическое программирование с самого начала выступает как средство практического решения задач оптимизации. Главным недостатком метода является, говоря словами Беллмана, «проклятие размерности» – его сложность катастрофически возрастает с увеличением размерности задачи.
Рассматривается управляемая система, которая под влиянием управления переходит из начального состояния ε ̅_0 в конечное состояние ε ̅_n. Предположим, что процесс управления системой можно разбить на n шагов. Пусть ε ̅_(0,) ε ̅_1,ε ̅_2,… ε ̅_n – состояния системы после 1-го, 2-го, …, n-го шагов (рис. 1). Состояние ε ̅_k системы после k-го шага k=1,…,n характеризуется параметрами ε_k^1,ε_k^2,…,ε_k^s, которые называются фазовыми координатами. Состояние можно изобразить точкой s-мерного пространства, называемого фазовым. Последовательное преобразование системы (по шагам) достигается с помощью некоторых мероприятий u ̅_1,u ̅_2,… u ̅_n, которые составляют управление системой U=(u ̅_1,u ̅_2,… u ̅_n), где u ̅_n – управление на n-м шаге, переводящее систему из состояния ε ̅_(k-1) в состояние ε ̅_k. Управление u ̅_n на n-м шаге заключается в выборе значений определенных управляющих переменных u_k^1,u_k^2,…,u_k^s. Предполагаем, что состояние системы в конце k-го шага зависит только от предшествующего состояния системы ε ̅_(k-1) и управления u ̅_n на данном шаге. Такое свойство получило название отсутствие последействия. Запишем эту зависимость в виде
Равенства (1) получили название уравнений состояний.
Рисунок 1.
Варьируя управление U, получим различную эффективность процесса, которую будем оценивать количественно целевой функцией
Показатель эффективности n-го шага процесса управления, который зависит от состояния ε ̅_(k-1) в начале этого шага и управления u ̅_n, выбранного на этом шаге, обозначим через f_k (ε ̅_(k-1),u ̅_n ),. В рассматриваемой задаче пошаговой оптимизации целевая функция (16.2) полагается аддитивной, т. е.
Обычно условиями процесса на управление на каждом шаге u ̅_n накладываются некоторые ограничения. Управления, удовлетворяющие этим ограничениям, называются допустимыми.
Задачу пошаговой оптимизации можно сформулировать следующим образом. Определить совокупность допустимых управлений u ̅_1,u ̅_2,… u ̅_n, переводящих систему из начального состояния ε ̅_0 в конечное состояние ε ̅_n и максимизирующих или минимизирующих показатель эффективности (3). В дальнейшем будем рассматривать задачу на максимум.
Начальное состояние ε ̅_0 и конечное состояние ε ̅_n могут быть заданы однозначно или могут быть указаны множество S_0 начальных состояний и множество S_n конечных состояний так, что ε ̅_0∈ S_0 , ε ̅_n∈ S_0. В последнем случае в задаче пошаговой оптимизации требуется определить совокупность допустимых управлений, переводящих систему из начального состояния ε ̅_0∈ S_0 в конечное состояние ε ̅_n∈ S_0 и максимизирующих целевую функцию (3). Управление, при котором достигается максимум целевой функции (3), называется оптимальным управлением и обозначается через U^=(u_1^,u_2^,…,u_n^).
Метод динамического программирования состоит в том, что оптимальное управление строится постепенно. На каждом шаге оптимизируется управление только этого шага. Вместе с тем на каждом шаге управление выбирается с учетом последствий, так как управление, оптими-зирующее целевую функцию только для данного шага, может привести к неоптимальному эффекту всего процесса. Управление на каждом шаге должно быть оптимальным с точки зрения процесса в целом.
Каково бы ни было начальное состояние системы перед очередным шагом, управление на этом этапе выбирается так, чтобы выигрыш на данном шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным.
Так, если система в начале k-го шага находится в состоянии ε ̅_(k-1) и мы выбираем произвольное управление u ̅_k, то она придет в новое состояние ε_k= F_k (ε ̅_(k-1),u ̅_n) , и последующие управления u ̅_(k+1),u ̅_(k+2),… u ̅_n должны выбираться оптимальными относительно состояния ε_k. Последнее означает, что при этих управлениях максимизируется величина,
т. е. показатель эффективности на последующих до конца процесса шагах k=1…n. Обозначим через
Выбрав оптимальное управление U_k^=(u_1^,u_2^,…,u_n^). на оставшихся шагах, получим величину Z_k^*=maxZ_k, которая зависит только от ε_k, т. е.
Назовем величину Z_k^* (ε_(k-1)) условным максимумом. Если мы теперь выберем на k-м шаге некоторое произвольное управление u ̅_k, то система придет в состояние ε ̅_k (рис. 2). Согласно принципу оптимальности, необходимо выбирать управление u ̅_k так, чтобы оно в совокупности с оптимальным управлением на последующих шагах (начиная с (k+1)-го) приводило бы к общему показателю эффективности на n-k+1 шагах, начиная с k-го и до конца. Это положение в аналитической форме можно записать в виде следующего соотношения:
получившего название основного функционального уравнения динамического програм-мирования, или основного рекуррентного уравнения Беллмана.
Из уравнения (4) может быть получена функция Z_(n-1)^* (ε_(n-2)), если известна функция Z_n^* (ε_(n-1)). Аналогично можно получить Z_(n-2)^* (ε_(n-3)), если найдена Z_(n-1)^* (ε_(n-2)) и т. д., пока не будет определена величина Z_1^* (ε_0), представляющая по определению максимальное значение показателя эффективности процесса в целом:
Решая уравнение (4) для определения условного максимума показателя эффективности за n-1+k шагов, начиная с k-го, мы определяем соответствующее оптимальное управление u ̅_k, при котором этот максимум достигается. Это управление также зависит от ε ̅_(k-1); будем обозначать его через u_k^* (ε_(k-1)), и называть условным оптимальным управлением на k-м шаге. Основное значение уравнения (4), в котором реализована идея динамического программирования, заключается в том, что решение исходной задачи определения максимума функции (3) n переменных u ̅_1,u ̅_2,… u ̅_n сводится к решению последовательности n задач, задаваемых соотношениями (4), каждое из которых является задачей максимизации функции одной переменной u ̅_k.
В результате последовательного решения n частных задач на условный максимум определяют две последовательности функций: Z_k^* (ε_(k-1)), – условные максимумы и соответствующие им u_k^* (ε_k) – условные оптимальные управления. Указанные последовательности функций в дискретных задачах получают в табличной форме, а в непрерывных моделях – аналитически. После выполнения первого этапа (условной оптимизации) приступают ко второму этапу – безусловной оптимизации.
Если начальное состояние ε_0^* задано ε_0=ε_0^*, то непосредственно определяют максимум целевой функции
а затем – искомое безусловное оптимальное управление по цепочке
Если задано множество S_0 начальных состояний ε_0∈S_0, то дополнительно решают еще одну задачу на максимум
откуда находят ε_0^*, а затем по цепочке (5) – безусловное оптимальное управление.
В рассмотренных рекуррентных соотношениях предписывают начинать вычисления с последнего этапа и затем передвигаться назад до этапа 1. Такой метод вычислений известен как алгоритм обратной прогонки. Если расчеты осуществляются в естественном порядке следования этапов, то такой метод вычислений известен как алгоритм прямой прогонки.
Приведем рекуррентные соотношения для этого случая. Уравнения состояний для прямого хода удобно записывать в виде
Введем в рассмотрение условные максимумы показателя эффективности за k шагов, от 1-го до k-го включительно, – величину Z_k^* (ε_k). Повторив приведенные рассуждения, придем к следующей системе уравнений Беллмана:
В результате решения этих уравнений получим последовательности
Далее определим безусловное оптимальное управление по цепочке
Особенность динамического программирования в том, что сложную программу можно разбить на несколько подзадач тем самым скорость расчета значительно можно увеличить.
Параллельно с выполнением домашнего задания я решил провести эксперимент. Он заключается в том, что я решаю задачу двумя способами, а именно: в прямом, т.е. вычисляю функцию Беллмана n-раз, запоминаю все значения и использую уже эти значения в следующей итерации; в параллельном, т.е. вычисляю функцию Беллмана один раз, далее уже зная это значение функции я вычисляю функцию на следующем шаге и т.д. Суть эксперимента заключается в том, чтобы оценить в каком из случаев время выполнение программы на расчет будет минимальным.
Многократно проделывая опыт я получил следующие данные:
- Время выполнения программы в прямом ходе составляет 0.019 секунд.
- Время выполнения программы в параллельном ходе составляет 0.015 секунд.
Можно сделать вывод: решение задачи методом динамического программирования в параллельном ходе занимает меньше времени и тратит меньше памяти ЭВМ.
Warning
ВНИМАНИЕ! Это мой первый опыт ведения подобного дневника. Есть замечания - пишите! Есть предложения - пишите! Я вас слушаю и слышу! Спасибо за внимание!
Ссылка с консольными: Консольные