реферат Динамическое программирование
Курсовая работа по теории оптимального управления экономическими системами.
Тема : Задача динамического программирования.
I.Основные понятия и обозначения.
Динамическое программирование – это математический метод поиска
оптимального управления, специально приспособленный к многошаговым
процессам. Рассмотрим пример такого процесса.
Пусть планируется деятельность группы предприятий на N лет. Здесь шагом
является один год. В начале 1-го года на развитие предприятий выделяются
средства, которые должны быть как-то распределены между этими
предприятиями. В процессе их функционирования выделенные средства частично
расходуются. Каждое предприятие за год приносит некоторый доход, зависящий
от вложенных средств. В начале года имеющиеся средства могут
перераспределяться между предприятиями : каждому из них выделяется какая-то
доля средств.
Ставится вопрос : как в начале каждого года распределять имеющиеся
средства между предприятиями, чтобы суммарный доход от всех предприятий за
N лет был максимальным?
Перед нами типичная задача динамического программирования, в которой
рассматривается управляемый процесс – функционирование группы предприятий.
Управление процессом состоит в распределении (и перераспределении) средств.
Управляющим воздействием (УВ) является выделене каких-то средств каждому из
предприятий в начале года.
УВ на каждом шаге должно выбираться с учетом всех его последствий в
будущем. УВ должно быть дальновидным, с учетом перспективы. Нет смысла
выбирать на рассматриваемом шаге наилучшее УВ, если в дальнейшем это
помешает получить наилучшие результаты других шагов. УВ на каждом шаге надо
выбирать “c заглядыванием в будущее”, иначе возможны серьезные ошибки.
Действительно, предположим, что в рассмотренной группе предприятий одни
заняты выпуском предметов потребления, а другие производят для этого
машины. Причем целью является получение за N лет максимального объема
выпуска предметов потребления. Пусть планируются капиталовложения на первый
год. Исходя их узких интересов данного шага (года), мы должны были бы все
средства вложить в производство предметов потребления, пустить имеющиеся
машины на полную мощность и добиться к концу года максимального объема
продукции. Но правильным ли будет такое решение в целом? Очевидно, нет.
Имея в виду будущее, необходимо выделить какую-то долю средств и на
производство машин. При этом объем продукции за первый год, естественно,
снизится, зато будут созданы условия, позволяющие увеличивать ее
производство в последующие годы.
В формализме решения задач методом динамического программирования будут
использоваться следующие обозначения:
N – число шагов.
[pic]– вектор,описывающий состояние системы на k-м шаге.
[pic]– начальное состояние, т. е. cостояние на 1-м шаге.
[pic]– конечное состояние, т. е. cостояние на последнем шаге.
Xk – область допустимых состояний на k-ом шаге.
[pic]– вектор УВ на k-ом шаге, обеспечивающий переход системы из
состояния xk-1 в состояние xk.
Uk – область допустимых УВ на k-ом шаге.
Wk – величина выигрыша, полученного в результате реализации k-го шага.
S – общий выигрыш за N шагов.
[pic]– вектор оптимальной стратегии управления или ОУВ за N шагов.
Sk+1([pic]) – максимальный выигрыш, получаемый при переходе из любого
состояния [pic][pic]в конечное состояние [pic] при оптимальной стратегии
управления начиная с (k+1)-го шага.
S1([pic]) – максимальный выигрыш, получаемый за N шагов при переходе
системы из начального состояния [pic] в конечное [pic] при реализации
оптимальной стратегии управления [pic]. Очевидно, что S = S1([pic]), если
[pic] –фиксировано.
Метод динамического программирования опирается на условие отсутствия
последействия и условие аддитивности целевой функции.
Условие отсутствия последействия. Состояние [pic], в которое перешла
система за один k-й шаг, зависит от состояния [pic] и выбранного УВ [pic] и
не зависит от того, каким образом система пришла в состояние [pic], то есть
[pic]
Аналогично, величина выигрыша Wk зависит от состояния [pic] и выбранного
УВ [pic], то есть
[pic]
Условие аддитивности целевой функции. Общий выигрыш за N шагов
вычисляется по формуле
[pic]
Определение. Оптимальной стратегией управления [pic] называется
совокупность УВ [pic], то есть [pic], в результате реализации которых
система за N шагов переходит из начального состояния [pic] в конечное [pic]
и при этом общий выигрыш S принимает наибольшее значение.
Условие отсутствия последействия позволяет сформулировать принцип
оптимальности Белмана.
Принцип оптимальности. Каково бы ни было допустимое состояние
системы[pic][pic] перед очередным i-м шагом, надо выбрать допустимое УВ
[pic] на этом шаге так, чтобы выигрыш Wi на i-м шаге плюс оптимальный
выигрыш на всех последующих шагах был максимальным.
В качестве примера постановки задачи оптимального управления продолжим
рассмотрение задачи управления финансированием группы предприятий. Пусть в
начале i-го года группе предприятий [pic] выделяются соответственно
средства: [pic][pic]совокупность этих значений можно считать управлением
на i-м шаге, то есть [pic]. Управление [pic] процессом в целом представляет
собой совокупность всех шаговых управлений, то есть [pic].
Управление может быть хорошим или плохим, эффективным или неэффективным.
Эффективность управления [pic] оценивается показателем S. Возникает
вопрос: как выбрать шаговые управления [pic], чтобы величина S обратилась
в максимум ?
Поставленная задача является задачей оптимального управления, а
управление, при котором показатель S достигает максимума, называется
оптимальным. Оптимальное управление [pic] многошаговым процессом состоит из
совокупности оптимальных шаговых управлений:
[pic]
Таким образом, перед нами стоит задача: определить оптимальное управление
на каждом шаге [pic](i=1,2,...N) и, значит, оптимальное управление всем
процессом [pic].
II. Идеи метода динамического программирования
Мы отметили, что планируя многошаговый процесс, необходимо выбирать УВ на
каждом шаге с учетом его будущих последствий на еще предстоящих шагах.
Однако, из этого правила есть исключение. Среди всех шагов существует один,
который может планироваться без "заглядыва-ния в будущее". Какой это шаг?
Очевидно, последний — после него других шагов нет. Этот шаг, единственный
из всех, можно планировать так, чтобы он как таковой принес наибольшую
выгоду. Спланировав оптимально этот последний шаг, можно к нему
пристраивать предпоследний, к предпоследнему — предпредпоследний и т.д.
Поэтому процесс динамического программирования на 1-м этапе
разворачивается от конца к началу, то есть раньше всех планируется
последний,
N-й шаг. А как его спланировать, если мы не знаем, чем кончился
предпоследний? Очевидно, нужно сделать все возможные предположения о том,
чем кончился предпоследний, (N — 1)-й шаг, и для каждого из них найти такое
управление, при котором выигрыш (доход) на последнем шаге был бы
максимален. Решив эту задачу, мы найдем условно оптимальное управление
(УОУ) на N-м шаге, т.е. управление, которое надо применить, если (N — 1)-й
шаг закончился определенным образом.
Предположим, что эта процедура выполнена, то есть для каждого исхода
(N — 1)-го шага мы знаем УОУ на N-м шаге и соответствующий ему условно
оптимальный выигрыш (УОВ). Теперь мы можем оптимизировать управление на