Метод динамического программирования

1.

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

2.

Многостадийный процесс
x ( 0)
x (1)
1
x ( 2 ) x ( i 1)
2
u (1)
x (i )
i
u(2)
x ( N 1)
u (i )
k - количество переменных состояния,
N
u( N )
xk( i ) k( i ) ( xk( i 1) ,..., xm( i 1) , u1( i ) ,..., ur( i ) ) k 1...., m
где
x( N )
i 1...., N
N - количество стадий
В векторной форме
x(i ) (i ) (x(i 1) , u(i ) )
(i )
u
U
где x
( x , x ,..., x ), u (u , u ,...., u ), x X ,
(i )
(i )
1
(i )
2
(i )
m
(i )
(i )
1
(i )
2
ri r (x , u )
(i )
(i )
или
RN ( u N )
ri ri (x
( i 1)
N
RN ri (x ( i 1) , u( i ) )
(i )
,u )
i 1
где
(i )
Эффективность всего процесса
(критерий оптимизации)
Эффективность стадии
i
(i )
r
u N (u(1) , u( 2 ) ,...., u( N ) )
- стратегия управления процессом
Задача оптимизации – отыскание оптимальной стратегии
при которой критерий оптимальности
RN
(1)
( 2)
N
u Nopt (uopt
, uopt
,...., uopt
)
принимает экстремальное значение.

3.

Принцип оптимальности
Оптимальная стратегия обладает тем свойством, что каковы бы ни
были начальное состояние x
( 0)
многостадийного процесса и
управление на первой стадии u(1) , последующие управления на всех
стадиях u(i ) (i 2,..., N ) должны составлять оптимальную
стратегию u N 1 относительно состояния x(1) первой стадии,
определяемого начальным состоянием процесса x
( 0)
и управлением
на первой стадии u(1).
Оптимальная стратегия u N 1 - это стратегия управления процессом,
включающим N 1 последних стадий исходного процесса, придающая
N
критерию
RN 1 ri (x ( i 1) , u( i ) )
i 2
оптимальное значение.

4.

Комбинаторная задача о пешеходе
Необходимо найти маршрут минимальной длины для перехода из точки 1 в точку 5.
(1)
(9)
(6)
(5)
Комбинаторный метод:
(1)
(7)
(5)
(8)
(3)
(2)
(2)
(4)
1
(4)
5
(4)
(3)
(2)
(6)
(1)
(9)
(3)
(7)
(2)
(7)
2
1
N =(1+3+3+3+3+3)+
(1+3+3+3+3)+
(1+3+3+3+3)=42
(10)
3
5
4
Метод динамического
программирования
стадии
Оптимальный маршрут
Длины маршрутов:
(3)+(1)+(1)+(5)=10
(1)
(1)+(6)+(2)+(5)=14
(5)
(2)+(2)+(7)+(4)=15
1
5
(1)
(3)
Количество расчетов
N = 3+9+9+3 = 24

5.

Построение оптимальной схемы ректификации
четырехкомпонентной идеальной смеси ABCE
aAD > aBD > aCE > 1
Критерий оптимальности – суммарный поток пара U
ABCE
7
6
2
AB
1
BCE
ABC
1
3
4
BC
5
CE
Uj = Dj*(Rj + 1)

6.

Последовательность решения задачи методом динамического
программирования
1 - UAB + UCE + UABCE->AB, CE
2 - UAB + UABC->AB
3 - UBC + UABC->BC
Umin*
4 - UBC + UBCD->BC
5 - UCE + UBCE->CE
6 – Umin* + UABCE->ABC
7 – Umin* + UABCE->BCE
1 - UAB + UCE + UABCE->AB, CE
Umin