37. Общая постановка задач динамического программирования.

Динамическое программирование - метод оптимизации задач (процессов, операций), решение которых может быть разбито на несколько этапов, а целевая функция является, соответственно, аддитивной (или мультипликативной).

Основные свойства задач, которые могут быть решены методами динамического программирования.

1). Задача должна допускать интерпретацию в виде n-этапного (шагового) процесса принятия решения. Решение начинается с последнего n-го этапа и продолжается до 1-го. В процессе решения происходит переход от k-го этапа к k-1-му.

2). Должны быть заданы:

а) Zk - вектор переменных, описывающих возможные состояния системы (процесса) на каждом этапе - вектор фазовых состояний системы, k =1,n,

zi,k∈ Zk , i-ое - одно из возможных состояний системы на k-ом этапе;

б). Xi,k - вектор управлений - набор возможных управлений при нахождений системы на k-м этапе в i-м состоянии, x_l,i,k - l-ое, одно из возможных, управлений;

3). Выбор управления (решения) на каждом этапе не должно влиять на состояние системы на предыдущих этапах

Целевая функция - суммарный выигрыш в задаче на максимум (суммарные потери в задаче на минимум) запишется в виде: W=∑ _k=1 ⁿ ∆Wk, где ∆Wk - выигрыш (потери) на k- этапе.

Таким образом, на каждом k-м этапе система (процесс) может находиться в одном возможном для этого этапа состояний - i,k Zk z ∈ . В каждом состоянии системы может быть принято одно из возможных, согласно условиям задачи (операции), решений (управлений). В результате принятия решения система (процесс) переходит в одно из

Zk+1 состояний - zk+1,p(xl,i,k), при этом имеет место приращение выигрыша

(потерь), равное W (x ) ∆ k l,i,k

38. Принцип оптимальности динамического программирования.

Основной принцип динамического программирования заключается в

следующем. На каждом k-м этапе процесса для системы (процесса),

находящейся в одном из возможных для этого этапа состояний,

необходимо так выбрать управление, чтобы минимизировать суммарные

потери в задаче на минимум (максимизировать суммарный выигрыш в

задаче на максимум), состоящие из приращения потерь (выигрыша) на k-м

этапе и на всех предыдущих, начиная с k+1-го, этапах. Полученный таким

образом результат является условным оптимумом - т.е полученным при

условии нахождения системы в конкретном состоянии.

После нахождения условных оптимумов для всех состояний системы

на всех этапах от n-го до 1-го определяется безусловный оптимум, для чего

необходимо пройти последовательно по всем этапам в обратном

направлении от 1-го этапа до последнего.

39. Принцип оптимальности Беллмана.

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

Из принципа оптимальности следует, что оптимальную стратегию управления можно получить, если сначала найти оптимальную стратегию управления на n-м шаге, затем на двух последних шагах, затем на трех последних шагах и т. д., вплоть до первого шага. Таким образом, решение рассматриваемой задачи динамического программирования целесообразно начинать с определения оптимального решения на последнем, n-м шаге. Для того чтобы найти это решение, очевидно, нужно сделать различные предположения о том, как мог окончиться предпоследний шаг, и с учетом этого выбрать управление обеспечивающее максимальное значение функции дохода   Такое управление, выбранное при определенных предположениях о том, как окончился предыдущий шаг, называется условно оптимальным. Следовательно, принцип оптимальности требует находить на каждом шаге условно оптимальное управление для любого из возможных исходов предшествующего шага.