Д ИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ. П РИНЦИП Б ЕЛЛМАНА. - презентация

1 Д ИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ. П РИНЦИП Б ЕЛЛМАНА.

2 Многошаговые процессы решения. Система изменяется, переходит в разные состояния. Меняются значения параметров системы. Параметры меняются непрерывно или дискретно от этапа к этапу. Теория динамического программирования

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

4 Управление – распределение и перераспределение ресурсов. Эффективность операции в целом характеризуется показателем, который зависит от всей совокупности управлений и на каждом шаге операций

5 Постановка задачи требует: Критерий Стадии (состояния) во времени или пространстве Решение для каждого состояния, удовлетворяющее критерию

6 Терминология: а) стадия(состояние) – единичный элемент, на которые делится весь процесс во времени или в пространстве; б) состояние системы характеризуется совокупностью переменных, которые описывают состояние системы на любой стадии процесса; в) переход от стадии к стадии описывается функциональными уравнениями; г) стратегия определяется системой решений функционального уравнения.

7 Стадии могут быть разнородны. Состояние отдельной стадии характеризуется совокупностью величин, которые называются выходом или переменными состояния. Оптимальная стратегия выражается системой функций, максимизирующих (минимизирующих) правую часть уравнения.

8 Присутствуют управляющие переменные (управление), известно математическое описание каждой стадии. Многостадийный процесс

9

10

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

12

13

14

15 Метод вычислений с последнего этапа и до этапа 1 известен как алгоритм обратной прогонки. Расчеты в естественном порядке следования этапов называется алгоритмом прямой прогонки.

16

17

18

19