Динамическое программирование. Принцип Белмана
Введем некоторые обозначения и сделаем необходимые для дальнейшего предположения.
Будем считать, что состояние рассматриваемой системы S на k-ом шаге ( 
) определяется совокупностью чисел x = ( 
,…, 
), которые получены в результате реализации управления uk, обеспечивающего переход системы S из состояния х(k-1) в состояние х(k)
Будем предполагать, что состояние х(k), в которое перешла система S, зависит от данного состояния х(k-1)- и выбранного управления Uk и не зависит от того, каким образом система S перешла в состояние х(k-1).
Далее, будем считать, что если в результате реализации k-го шага обеспечен определенный доход, также зависящий от исходного состояния системы x(k-1) и выбранного управления Uk, равный Wk(х(k-1); uk), то общий доход за n шагов составляет
где u = (u1, u2,…, uп).
Таким образом, сформированы два условия, которым должна удовлетворять рассматриваемая задача динамического программирования. Первое условие обычно называют условием отсутствия последействия, а второе - условием аддитивности целевой функции задачи.
Задача состоит в нахождении оптимальной стратегии управления, т.е. такой совокупности управлений u* = ( 
), в результате реализации которых система S за n шагов переходит из начального состояния х(0) в конечное х(n) и при этом функция дохода W(u) принимает наибольшее значение.
Принцип оптимальности Беллмана. Каково бы ни было состояние системы перед очередным шагом, надо выбрать управление на этом шаге так, чтобы доход на данном шаге плюс оптимальный доход на всех последующих шагах был максимальный.
|
|
|
Из принципа оптимальности следует, что оптимальную стратегию управления можно получить, если сначала найти оптимальную стратегию управления на n-м шаге, затем двух последних шагах, затем на трех последних шагах и т.д., вплоть до первого шага. Таким образом, решение рассматриваемой задачи динамического программирования целесообразно начинать с определения оптимального решения на последнем, n-м шаге. Для того чтобы найти это решение, очевидно, нужно сделать различные предположения о том, как окончиться предпоследний шаг, и с учетом этого выбрать управление 
, обеспечивающее максимальное значение функции дохода 
. Такое управление, выбранное при определенных предположениях о том, как окончился предыдущий шаг, называется условно оптимальным управлением. Следовательно, принцип оптимальности требует находить на каждом шаге условно оптимальное управление любого из возможных исходов предшествующего шага.
Чтобы построить алгоритм решения задач, дадим математическую формулировку принципа оптимальности. Для этого введем некоторые дополнительные обозначения. Обозначим через F0(х(о)) максимальный доход, получаемый за n шагов при переходе системы S из начального состояния х(о) в конечное состояние х(n) при реализации оптимальной стратегии управления u* = ( 
,…, 
), а через Fk(х(k)) - максимальный доход, получаемый при переходе из любого состояния х(n) в конечное состояние х(n) при оптимальной стратегии управления на оставшихся (n-k) шагах. Тогда
|
|
|
, (2.8)
, (2.9)
при 
.
Выражение (2.9) представляет собой математическую запись принципа оптимальности Беллмана и носит название основного функционального уравнения Беллмана. Используя уравнение (2.9) находится решение рассматриваемой задачи динамического программирования. Рассмотрим этот процесс более подробно. Полагая k = n - 1 в уравнении Беллмана (2.9), получим следующее функциональное уравнение:
(2.10)
В уравнении (2.10) Fп(х(n)) можно считать известным. Используя теперь уравнение (2.10) и рассматривая всевозможные допустимые состояния системы S на (n-1) - ом шаге 
, 
,…, 
,… находим условные оптимальные решения
, 
, …, 
,…
и соответствующие значения функции (2.10)
, 
,…, 
,…
Таким образом, на n-ом шаге находим условно оптимальное управление при любом допустимом состоянии системы S после (n-1) - го шага, т.е. в каком бы состоянии система оказалась после (п-1) - го шага, нам уже известно, какое следует принять решение на n-м шаге.
|
|
|
Перейдем теперь к рассмотрению функционального уравнения при k= n-2:
. (2.11)
Решая функциональное уравнение (2.11) при различных состояниях на (n-2) - ом шаге, получим условно оптимальные управления 
, i =1,2,… Каждое из этих управлений совместно с уже выбранным управлением на последнем обеспечивает максимальное значение дохода на двух последних шагах.
Последовательно осуществляя описанный выше итерационный процесс, дойдем, наконец, до первого шага. На этом шаге известно, в каком состоянии может находиться система. Поэтому уже не требуется делать предположений о допустимых состояниях системы, а остается лишь только выбрать управление, которое является наилучшим с учетом условно оптимальных управлений, уже принятых на всех последующих шагах.
Чтобы найти оптимальную стратегию управления, определить искомое решение задачи, нужно теперь пройти всю последовательность шагов, только на этот раз от начала к концу. А именно: на первом шаге в качестве оптимального управления возьмем найденное условно оптимальное управление 
. На втором шаге найдем состояние 
, в которое переводит систему управление . Это состояние определяет найденное условно оптимальное управление 
, и которое теперь будем считать оптимальным. Зная 
, находим 
, а значит, определяем 
и т.д. В результате этого находим решение задачи, т.е. максимально возможный доход и оптимальную стратегию управления, включающую оптимальные управления на отдельных шагах.
|
|
|
Из изложенного видно, что этот процесс является довольно громоздким. Однако использование ЭВМ позволяет находить на основе метода динамического программирования решение и более сложных практических задач.
Список литературы
модель уравнение солоу полезность
1. Андрейчиков А.В., Андрейчикова О.Н. «Анализ. Синтез. Планирование решений в экономике» - М.: Финансы и статистика, 2002.
. Бережная Е.В., Бережной В.И. «Математические методы моделирования экономических систем» М.: Финансы и статистика, 2001.
3. Большаков А.С. «Моделирование в менеджменте» - М.: Филинь, 2000.
4. Жданов С.А. «Экономические модели и методы в управление» - М.: Дело и сервис, 1998.
5. Канторович Л.В., Горстко А.Б. «Оптимальные решения в экономике» - М., Наука, 1998.
6. Колемаев В.А. Математическая экономика: Учебник для вузов. - 2-е издание, - М.: ЮНИТИ, 2003.
7. Конюховский П. «Математические методы исследования операций в экономике: Учебное пособие» - Спб: Питер, 2000.
. Моисеев Н.Н. «Человек, среда, общество. Проблемы формализованного описания» - М.: Наука, 1998.
. Лабскер Л.Г. и др. «Игровые методы в управлении экономикой и бизнесом: Учебное пособие» - М.: Дело, 2001.
. «Математические методы принятия решений в экономике». Под ред. Колемаева В.А.М.: ЗАО «Финстатинформ», 1999.
Дата добавления: 2021-01-20; просмотров: 107; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!