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

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

Блочная схема (рис.1.7.1) многостадийного процесса

Рис.1.7.1. Многостадийный процесс

Условные обозначения на схеме каскада аппаратов:

число стадий процесса (аппаратов) N

вектор переменных состояния процесса на выходе из i -того аппарата и на входе в i +1 аппарат

вектор переменных управления i -том аппарате

частный критерий оптимальности в i -том аппарате

Критерий оптимальности всего процесса – аддитивная функция

Критерий оптимальности на каждой

стадии определяется её состоянием:

Уравнение математической модели для i –й стадии даёт связь между вектором входных параметров, вектором выходных

параметров и вектором управлений:

 

Рассмотрим задачу:

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

n – число оборотов мешалки

t_н – температура хладагента

G – расход хладагента

Каждому стационарному состоянию соответствует (рис.1.7.2) некоторый состав на выходе из аппарата.

Рис.1.7.2. Входные и выходные составы

Вектор искомых управляющих переменных на каждой стадии имеет вид:

n – число оборотов мешалки

t_н – температура хладагента

G – расход хладагента

Тогда задача оптимизации формулируется

 следующим образом:

Задача оптимизации ставится следующим образом:

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

В соответствии со схемой, решение задачи оптимизации методом перебора всех вариантов управлений, т.е.комбинаторным методом это означает такой выбор одной или нескольких ломаных линий из всей их совокупности, чтобы выполнилось следующее равенство:

 

Схематическое изображение (рис.1.7.3) процесса в рассматриваемом трехстадийном процессе:

Рис.1.7.3. Изображение схемы многостадийного процесса

Точка A изображает начальное состояние процесса, которое характеризуется начальным составом сырья, его температурой и т.д. В результате определённого набора управлений на первом реакторе (n ₁, t_{н 1}, G ₁) на выходе из него получается продукт с составом:

k – соответствует числу состояний (k =3),

реализуемых в каждом случае. Далее переработка сырья во втором реакторе осуществляется таким образом, что на выходе из него получается следующий состав продуктов:                   . Эти состояния изображаются точками C ₁, C ₂ и C ₃. Линии, соединяющие точки B_i и C_j, соответствуют тем наборам управлений на втором реакторе, которые используются при переводе системы из состояния B_i в состояние C_j.

Аналогично для третьего реактора точки D ₁, D ₂ и D ₃ соответствуют трём возможным стационарным состояниям на третьем реакторе, т.е. составам:                 . Линии, соединяющие точки C _i и D _j, соответствуют тем наборам управлений на третьем реакторе, которые используются при переводе системы из состояния C _i в состояние D _j.

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

r_i – значение критерия оптимальности

в i -ом реакторе

Проще всего эта задача может быть решена

обычным перебором (1-й способ решения),

т.е. сравнением между собой всех возможных

вариантов проведения процесса. Необходимо

определить значение R для всех ломаных

(здесь 27) схемы процесса:

 

Из всех полученных значений R

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

k – число возможных состояний на стадии

N – число стадий

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

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

2 этап: по известным значениям входных параметров, начиная с первой стадии определяются конкретные управляющие параметры последовательно на всех стадиях процесса до последней стадии, что и является решением задачи.

Если же задача решается изложенным методом динамического программирования (2-ой способ решения), необходимое количество вычислений (n’) составляет:

При k = 3 и N = 3 n’ = 21, в то время как в 1-ом способе - n = 27

При k = 3 и N = 5 n’ = 39, в то время, как в 1-м - n = 243.