Стохастические задачи динамического программирования
Показывает, что будущие решения основываются только на состоянии системы в данный момент и не зависят от ее предыстории. Где (j=1,2,…, m) — вероятности m возможных дискретных состояний, которые может принимать случайный вектор. Для стохастического процесса можно схематично записать последовательность преобразований: Позволяет упростить функциональное уравнение, описывающее процесс, а свойство… Читать ещё >
Стохастические задачи динамического программирования (реферат, курсовая, диплом, контрольная)
В практике планирования довольно часто встречаются задачи, в которых на состояние системы и на значение критерия заметное влияние оказывают случайные факторы. В таких задачах управляемый процесс не полностью определяется начальным состоянием системы и выбранным управлением, а в какой-то мере зависит от случая. Такие задачи называются стохастическими и вероятностными.
Для нахождения оптимального решения многоэтапных экстремальных стохастических задач с аддитивным критерием можно использовать метод динамического программирования. В стохастической модели преобразование от i-го этапа к (i-1)-му содержит некоторую неопределенность. В результате преобразования известный вектор состояния переходит в случайный вектор состояния с функцией распределения, которая зависит от известного состояния, случайного состояния и управления. Поэтому, прежде чем принять решение на (i-1)-м этапе, необходимо положить, что действительное значение вектора состояния наблюдалось и известно.
Для стохастического процесса можно схематично записать последовательность преобразований:
.
.
.
Но нельзя с помощью обратной подстановки выразить конечное состояние как функцию начального. Это обусловлено тем, что результаты преобразований известны только после непосредственных наблюдений.
Величины являются случайными, поэтому управления также случайны в том смысле, что их применение дает неопределенный результат для величины критерия.
Критерий.
как функция случайных величин также является случайной величиной, поэтому говорить о его оптимальном значении не имеет смысла. В связи с этим в роли меры качества проведения используют среднюю характеристику возможных результатов. Такой характеристикой является среднее арифметическое, т. е. математическое ожидание. Свойство линейности.
M (X1+X2+…+Xn)=M (X1)+M (X2)+…+M (Xn).
Позволяет упростить функциональное уравнение, описывающее процесс, а свойство линейности.
M[M (X1)+M (X2)+…+M (Xn)]= M (X1)+M (X2)+…+M (Xn).
Показывает, что будущие решения основываются только на состоянии системы в данный момент и не зависят от ее предыстории.
Пусть — максимум математического ожидания величины критерия по в N-этапном процессе, начинающемся с состояния, при использовании оптимальной стратегии; тогда.
.
Откуда для дискретного случая получаем.
Где (j=1,2,…, m) — вероятности m возможных дискретных состояний, которые может принимать случайный вектор
0<=<=1, .