Основные понятия и обозначения

ТЕМА 4.1 МОДЕЛИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ.

Динамическое программирование – это математический метод поиска оптимального управления, специально приспособленный к многошаговым процессам. Рассмотрим пример такого процесса.

Пусть планируется деятельность группы предприятий на N лет. Здесь шагом является один год. В начале 1-го года на развитие предприятий выделяются средства, которые должны быть как-то распределены между этими предприятиями. В процессе их функционирования выделенные средства частично расходуются. Каждое предприятие за год приносит некоторый доход, зависящий от вложенных средств. В начале года имеющиеся средства могут перераспределяться между предприятиями: каждому из них выделяется какая-то доля средств.

Ставится вопрос: как в начале каждого года распределять имеющиеся средства между предприятиями, чтобы суммарный доход от всех предприятий за N лет был максимальным?

Перед нами типичная задача динамического программирования, в которой рассматривается управляемый процесс – функционирование группы предприятий. Управление процессом состоит в распределении (и перераспределении) средств. Управляющим воздействием (УВ) является выделение каких-то средств каждому из предприятий в начале года.

УВ на каждом шаге должно выбираться с учетом всех его последствий в будущем. УВ должно быть дальновидным, с учетом перспективы. Нет смысла выбирать на рассматриваемом шаге наилучшее УВ, если в дальнейшем это помешает получить наилучшие результаты других шагов. УВ на каждом шаге надо выбирать “c заглядыванием в будущее”, иначе возможны серьезные ошибки.

Действительно, предположим, что в рассмотренной группе предприятий одни заняты выпуском предметов потребления, а другие производят для этого машины. Причем целью является получение за N лет максимального объема выпуска предметов потребления. Пусть планируются капиталовложения на первый год. Исходя их узких интересов данного шага (года), мы должны были бы все средства вложить в производство предметов потребления, пустить имеющиеся машины на полную мощность и добиться к концу года максимального объема продукции. Но правильным ли будет такое решение в целом? Очевидно, нет. Имея в виду будущее, необходимо выделить какую-то долю средств и на производство машин. При этом объем продукции за первый год, естественно, снизится, зато будут созданы условия, позволяющие увеличивать ее производство в последующие годы.

В формализме решения задач методом динамического программирования будут использоваться следующие обозначения:

N – число шагов.

– вектор, описывающий состояние системы на k-м шаге.

– начальное состояние, т. е. состояние на 1-м шаге.

– конечное состояние, т. е. состояние на последнем шаге.

X_k – область допустимых состояний на k-ом шаге.

– вектор УВ на k-ом шаге, обеспечивающий переход системы из состояния x_k-1 в состояние x_k.

U_k – область допустимых УВ на k-ом шаге.

W_k – величина выигрыша, полученного в результате реализации k-го шага.

S – общий выигрыш за N шагов.

– вектор оптимальной стратегии управления или ОУВ за N шагов.

S_k+1() – максимальный выигрыш, получаемый при переходе из любого состояния в конечное состояние при оптимальной стратегии управления начиная с (k+1)-го шага.

S₁() – максимальный выигрыш, получаемый за N шагов при переходе системы из начального состояния в конечное при реализации оптимальной стратегии управления. Очевидно, что S = S₁(), если –фиксировано.

Метод динамического программирования опирается на условие отсутствия последействия и условие аддитивности целевой функции.

Условие отсутствия последействия. Состояние, в которое перешла система за один k-й шаг, зависит от состояния и выбранного УВ и не зависит от того, каким образом система пришла в состояние, то есть

Аналогично, величина выигрыша W_k зависит от состояния и выбранного УВ, то есть

Условие аддитивности целевой функции. Общий выигрыш за N шагов вычисляется по формуле

Определение. Оптимальной стратегией управления называется совокупность УВ, то есть, в результате реализации которых система за N шагов переходит из начального состояния в конечное и при этом общий выигрыш S принимает наибольшее значение.

Условие отсутствия последействия позволяет сформулировать принцип оптимальности Белмана.

Принцип оптимальности. Каково бы ни было допустимое состояние системы перед очередным i-м шагом, надо выбрать допустимое УВ на этом шаге так, чтобы выигрыш W_i на i-м шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным.

В качестве примера постановки задачи оптимального управления продолжим рассмотрение задачи управления финансированием группы предприятий. Пусть в начале i-го года группе предприятий выделяются соответственно средства: совокупность этих значений можно считать управлением на i-м шаге, то есть. Управление процессом в целом представляет собой совокупность всех шаговых управлений, то есть.

Управление может быть хорошим или плохим, эффективным или неэффективным. Эффективность управления оценивается показателем S. Возникает вопрос: как выбрать шаговые управления, чтобы величина S обратилась в максимум?

Поставленная задача является задачей оптимального управления, а управление, при котором показатель S достигает максимума, называется оптимальным. Оптимальное управление многошаговым процессом состоит из совокупности оптимальных шаговых управлений:

Таким образом, перед нами стоит задача: определить оптимальное управление на каждом шаге (i=1,2,...N) и, значит, оптимальное управление всем процессом.

Дата добавления: 2014-01-15