Optimization Toolbox – Оптимизация

Вид материала

Документы

Содержание 4. Динамическое программирование Принцип оптимальности

Подобный материал:

• Окно элементов управления toolbox окно элементов управления ToolBox, 76.09kb.
• Обзор средств matlab и ToolBox'ов для приближения данных, 622.57kb.
• Особенности программной реализация задачи целочисленного программирования, 102.66kb.
• Isbn 5-7262-0634 нейроинформатика 2006, 93.81kb.
• Місця збереження документів, 153.78kb.
• Учебная программа по дисциплине: «Оптимизация налогообложения» Специальность: 080105, 151.71kb.
• Basic Search Engine Optimization. Dave Collins, SharewarePromotions Ltd, 231.08kb.
• Оптимизация производственной программы предприятия Выбор портфеля финансовых активов, 75.23kb.
• Моделирование и оптимизация систем с распределенными параметрами, 14.61kb.
• Search Engine Optimization означает один из самых главных и эффективных инструментов, 80.67kb.

^

4. Динамическое программирование

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



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

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

x_k⁽ⁱ⁾  _k⁽ⁱ⁾(x₁^(i-1), …, x_m^(i-1), u₁⁽ⁱ⁾, …, u_r⁽ⁱ⁾),

k 1, ..., m; i 1, ..., N,

связывающей выходные параметры i-й стадии x_k⁽ⁱ⁾ с выходными параметрами предыдущей стадии x_k^(i-1) и управлением и_l⁽ⁱ⁾ (l 1, ..., r), используемым на i-й стадии.

Систему уравнений удобно также представить в векторной форме

x⁽ⁱ⁾  ⁽ⁱ⁾(x^(i-1)_, u⁽ⁱ⁾),

причем x⁽ⁱ⁾ вектор совокупности переменных состояния (или выход) i-й стадии;

x⁽ⁱ⁾ (x₁⁽ⁱ⁾, x₂⁽ⁱ⁾, …, x_m⁽ⁱ⁾),

a u⁽ⁱ⁾ - вектор совокупности управляющих воздействий (управление) на i-й стадии:

u⁽ⁱ⁾ (u₁⁽ⁱ⁾, u₂⁽ⁱ⁾, …, u_r⁽ⁱ⁾).

Размерности векторов состояния x⁽ⁱ⁾ и управления и u⁽ⁱ⁾ в общем случае могут быть различными для разных стадий процесса. Однако далее, не нарушая общности, можно принять, что размерности m и r векторов состояния и управления для всех стадий процесса одинаковы.

В реальных процессах на значения переменных состояния x⁽ⁱ⁾ и управляющих воздействий u⁽ⁱ⁾ могут быть наложены ограничения, определяющие диапазон изменения или взаимосвязь указанных переменных. Математически это находит выражение в появлении дополнительных условий в виде равенств или неравенств

F_j(x⁽¹⁾, …, x^(N), u⁽¹⁾, …, u^(N)),

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

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

,

Смысл записи заключается в том, что значения переменных x⁽ⁱ⁾ и u⁽ⁱ⁾ принадлежат к допустимым областям их изменения Х и U, ограниченным соответствующими соотношениями.

Предполагается, что эффективность каждой стадии процесса оценивается некоторой скалярной величиной

r_i r_i^*(x⁽ⁱ⁾, u⁽ⁱ⁾).

заданной в виде функции от переменных состояния стадии x⁽ⁱ⁾ и принятого на ней управления u⁽ⁱ⁾.

С учетом математического описания стадии функциональная зависимость эффективности может быть представлена также как

r_i r_i(x^(i-1), u⁽ⁱ⁾).

т. е. как функция состояния входа x^(i-1) на i-й стадии и используемого на ней управления u⁽ⁱ⁾

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



Естественно, что значение критерия оптимальности R_N зависит от совокупности u⁽ⁱ⁾_N управляющих воздействий на всех стадиях процесса, которые представляет собой набор значений векторов u⁽ⁱ⁾ для всех стадий:

u_N (u⁽¹⁾, u⁽²⁾, …, u^(N)).

Совокупность управлений для всех стадий процесса u_N будем называть в дальнейшем стратегией управления многостадийным. процессом или просто стратегией управления.

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

(u_опт⁽¹⁾, u_опт⁽²⁾, …, u_опт^(N)),

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

^ Принцип оптимальности

В основу метода динамического программирования положен принцип оптимальности, который в переложении для много-, стадийного процесса может быть сформулирован следующим образом. Оптимальная стратегия обладает тем свойством, что каковы бы ни были начальное состояние x⁽⁰⁾ многостадийного процесса и управление на первой стадии u⁽¹⁾, последующие управления на всех стадиях u⁽ⁱ⁾ (i 2, ..., N) должны составлять оптимальную стратегию и_N-1 относительно состояния x⁽¹⁾ первой стадии, определяемого начальным состоянием процесса x⁽⁰⁾ и управлением на первой стадии u⁽¹⁾.

В приведенной формулировке принципа оптимальности под оптимальной стратегией и_N-1 понимается стратегия управления многостадийным процессом, включающим N-1 последних стадий исходного процесса, придающая критерию



оптимальное значение.

Другими словами, оптимальная стратегия и_N-1 находится для (N-1)-стадийного процесса, для которого величина является начальным состоянием.

Таким образом, если известна оптимальная стратегия управления и_N-1 для любого возможного состояния x⁽¹⁾ первой стадии N-стадийного процесса, то уже не составляет труда выбрать оптимальное управление и на первой стадии u_опт⁽¹⁾, поскольку на последующих стадиях оно определяется только состоянием выхода первой стадии:

и_N-1 и_N-1 (x⁽¹⁾).

Процедура применения принципа оптимальности для оптимизации N-стадийного процесса, очевидно, должна начинаться с последней стадии процесса, для которой не существует последующих стадий, могущих повлиять согласно принципу оптимальности на выбор управления u_опт^(N) на этой стадии. После того как оптимальное управление u_опт^(N) найдено для всех возможных состояний входа последней стадии x^(N-1) X, можно приступить к определению оптимального управления для предыдущей (N-1)-стадии, для которой оптимальная стратегия управления на последующих стадиях (т. е. на последней N-й стадии) известна, и т. д.

В результате может быть найдена оптимальная стратегия управления для всего многостадийного процесса, являющаяся функцией начального состояния процесса u_N^(x(0)). Если начальное состояние x⁽⁰⁾ известно (задано или выбрано из условия оптимума критерия R), то его значение определяет оптимальные управления для всех стадий процесса.


Список литературы

1. Аоки М. Ведение в методы оптимизации. М.: Наука. 1977. 344с.
   
2. Бояринов А.И., Кафаров В.В. Методы оптимизации в химической технологии. М.: Химия. 1975. 576с.
   
3. Гольштейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. - M.: Наука, 1969. - 382с.
   
4. Фурунжиев Р.И., Бабушкин Ф.М., Варавко В.В. Применение математических методов и ЭВМ: Практикум. Мн.: Выш.шк. 1988. 191с.