Формулировка принципа оптимальностиБелмана

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

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

При подходе к решению задач оптимизации методом динамического программирования необходимо обращать внимание на следующее:

a) оптимизируемый процесс должен быть дискретно-распределённым во времени или пространстве (многостадийный процесс);

b) отдельные стадии процесса должны обладать относительной независимостью, т.е. вектор выходных параметров любой стадии должен зависеть только от вектора входных параметров на эту стадию и управлений на ней;

c) критерий оптимальности процесса должен быть сформулирован как аддитивная функция критериев оптимальности каждой стадии;

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

• параметры, характеризующие состояние каждой стадии;

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

• ограничения, которые накладываются на параметры состояния процесса и управляющие параметры.

Необходимо составить:

1. математическое описание для каждой стадии (рис.1.7.4);

2. критерий оптимальности.

Рис.1.7.4. Стадии процеса

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

её состоянием:

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

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

Первый этап решения

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

критерий оптимальности r_N был

экстремальным (например, максимальным):

Используя уравнение математической модели для данной стадии, получим:

 

откуда определяется оптимальное

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

предыдущей стадии

Переходя к стадии N – 1, получим условие выбора оптимального уравнения:

где математическая модель предыдущей стадии

имеет вид:

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

Поскольку f ₁ уже выбрано, определение f ₂ даёт возможность выбора оптимального управления на стадии N – 1. Подставляя уравнение математической модели

для данной стадии, получим:

откуда определяется оптимальное управление

Проводя аналогичный анализ, для стадии i можно записать:

 

С учётом φ _i получим математическую формулировку принципа оптимальности, являющуюся рекуррентной формулой,

позволяющей выполнять

решение задачи оптимизации

последовательно:

где f_{N -(i -1)} – значение суммы критериев оптимальности последних N -i стадий, откуда определяется оптимальное управление

Для первой стадии имеем:

откуда определяется оптимальное управление (А) или наряду с оптимальным управлением и оптимальные входные переменные (В):

А)или В)                 более сложная задача (большей размерности).

На этом завершается 1-этап решения задачи ДП.

Второй этап решения

Для реализация 2-этапа на основе знания и по соотношениям, приведенным ниже, последовательно определяются   (i=1,…N)

и      (i=2,…N):

Произвольная стадия каскада

 

Пример 1.

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

Задана конечная концентрация A:

Число реакторов в каскаде N.

Задача оптимизации: выбрать объёмы реакторов так, чтобы суммарный объём всех реакторов был минимальным.

Нетрудно видеть, что в поставленной задаче оптимизации выполнены условия a, b и с: оптимизируемый процесс является дискретно-распределённым в пространстве; отдельные стадии процесса обладают относительной независимостью (выход каждого реактора зависит только от входящих переменных и управлений на нём) и критерий оптимальности всего процесса является аддитивной функцией частных критериев (критерий оптимальности - объём каскада реакторов, частные критерии - объёмы каждого аппарата).

Запишем сведения о процессе, необходимые для решения задачи оптимизации:

Параметрами, характеризующими состояние каждой стадии являются концентрации продукта реакции или исходного реагента - x_i.

Управляющие параметры - объёмы каждого реактора или, что то же самое, время пребывания смеси в каждом реакторе U _i (при постоянной нагрузке).

На параметры состояния процесса на каждой стадии

наложены ограничения:

на параметры управления процесса на каждой стадии наложены ограничения:или

Составляем математическое описание каждой i-ой стадии (уравнение материального баланса):

или

Откуда имеем:

 

Составляем критерий оптимальностиили

Пример 1.

ПЕРВЫЙ ЭТАП решения выглядит следующим образом:

где

 

Концентрация реагента A на выходе из реактора N однозначно определяет время пребывания в нём, поэтому именно её можно взять в качестве управляющего параметра.

Тогда задача оптимизации на последней стадии состоит в выборе такой концентрации на выходе из N –го аппарата, при которой время пребывания в N –ом аппарате было бы минимальным. Однако в рассматриваемой задаче конечная концентрация x_N задана, поэтому задача какого-либо выбора исключается и остаётся только рассчитать время пребывания

при заданном значении x_N:

 

 

В соответствии с общей схемой переходим

к предпоследнему реактору:

Если вид выражения критерия

не сложен, а названное управление - это единственный управляющий параметр, то для определения экстремума r*_N на стадии можно пользоваться теоремами математического анализа.

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

В предпоследнем реакторе необходимо выбрать такое значение x_{N -1}, чтобы выражение в скобках имело минимум при любых значениях x_{N -2}. Это значение x_{N -1} можно найти,

воспользовавшись необходимым

условием существования экстремума

функции одной переменной:

Из последнего выражения следует:

Поскольку функция f ₂ дифференцируемая, легко проверить достаточное условие существования экстремума:

 

 

во всём диапазоне изменения x_{N -1},

следовательно в точке

Следовательно:

функция f ₂ принимает минимальное значение.

Чтобы получить минимальное

значение времени пребывания

в двух последних реакторах,

запишем рекуррентное соотношение:

Повторим рассмотренную процедуру для третьего от конца реактора. Запишем для него

рекуррентное соотношение:

Найдём минимум, воспользовавшись необходимым условием существования экстремума функции одной переменной:

Откуда получаем:

Проверим достаточное условие:

 

Подставив в

последнее выражение

полученное значение

оптимальной концентрации,

имеем:

 

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

Подставив значение оптимальной

концентрации в

рекуррентное соотношение,

получим:

 

или после преобразований:

 

Решение задачи выполняется таким же образом последовательно для всех реакторов до первого включительно.

Для произвольного реактора i, считая от конца процесса, получим аналогичные выражения

оптимальной концентрации:

и рекуррентного соотношения:

 

Для первого реактора:

 

 

Поскольку в условии задачи x ₀ и x_N заданы, k и N неизвестны, из последнего выражения рассчитывается

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

и для первого реактора:

 

ВТОРОЙ ЭТАП РЕШЕНИЯ

На втором этапе решения из полученных соотношений определяются:

 

Для второго реактора имеем:

Далее

определяется:

 

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

Далее определяется:

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

 

Пример 2

В каскаде реакторов идеального перемешивания проводится простая реакция 2-го порядка: A → P. Каждый из аппаратов каскада работает в изотермических условиях, причём температура реакционной массы во всех аппаратах одинакова. Требуется определить среднее время пребывания реакционной массы в каждом из аппаратов с тем, чтобы общее время пребывания реакционной массы в системе было минимальным.

Исходные данные: Число аппаратов N = 3

Начальная концентрация компонента Ax ₀ = 1 моль/литр

Конечная концентрация компонента A на выходе из каскада x ₃ = 0,2 моль/литр

Константа скорости реакции:

Решение

Критерий оптимальности процесса по условию задачи есть:

τ _i - среднее время пребывания в i – ом аппарате.

Из уравнения материального баланса

для i – го реактора имеем:

Первый этап решения

Записываем рекуррентное соотношение:

Поскольку x ₃ задано,

 

 

Функциональное уравнение будем решать (рис.1.7.5) графически:

Рис.1.7.5. Функциональное уравнение

Записываем рекуррентное

соотношение (рис.1.7.6.)

для f ₂:

Рис.1.7.6. Рекуррентное соотношение

Записываем рекуррентное

соотношение (рис.1.7.7.)

для f ₃:

 

Рис.1.7.7. Рекуррентное соотношение для f ₃.

Второй этап решения

Из графических построений определяется:

И оптимальное управление, соответствующее f ₃:

По найденному значению x _{1( opt )}

графически определяем x _{2( opt )}:

Рассчитываем время пребывания в каждом из аппаратов:

 

 

Небольшое расхождение τ = 6,7 часа с f ₃ = 6,5 часа объясняется погрешностью графического расчёта.