9900

Динамическая оптимизация

Реферат

Математика и математический анализ

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

Русский

2013-03-18

97 KB

12 чел.

Динамическая оптимизация

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

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

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

Строгая формулировка задачи

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

Время t измеряется как непрерывная величина. Предполагается, что t изменяется в некотором фиксированном промежутке: от начального момента t0, который обычно известен, до конечного момента t1, который часто требуется определить. Следовательно, время задано на промежутке

t0  t  t1.

Состояние системы в любой момент времени t из указанного промежутка характеризуется с помощью n вещественных чисел x1(t), x2(t), …, xn(t), называемых фазовыми координатами. Составленный из фазовых координат n-мерный вектор

x(t) = (x1(t), x2(t), …, xn(t))',   (1)

называемый фазовым вектором (фазовой точкой), можно геометрически интерпретировать как точку в n-мерном евклидовом пространстве Еn. Каждая фазовая координата считается непрерывной функцией времени, поэтому фазовая траектория

  {x(t)} = {x(t)Еn t0  t  t1}

представляет собой непрерывную вектор-функцию времени, значениями которой в каждый данный момент времени t из указанного промежутка являются фазовые векторы (1). С геометрической точки зрения фазовая траектория представляет собой некоторую кривую, состоящую из точек пространства Еn. Началом этой кривой является фиксированное начальное состояние

x(t0) = x0,      (2)

а окончанием – конечное состояние

x(t1)= x1,

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

Выборы (решения), которые нужно осуществлять в каждый данный момент времени t из указанного интервала, характеризуются с помощью r вещественных чисел  u1(t), u2t), …, ur(t), называемых управляющими параметрами. Составленный из управляющих параметров r-мерный вектор-столбец

u(t) = (u1(t), u2t), …, ur(t))',   (3)

называемый управляющим вектором, можно интерпретировать геометрически как точку в Er. Управлением ("траекторией управления") называется функция

{u(t)}= {u(t)Еr t0  t  t1}.   (4)

Требуется, чтобы каждый управляющий параметры являются кусочно-непрерывной функцией времени. Поэтому управление представляет собой кусочно-непрерывную функцию времени. Значениями этой функции в каждый данный момент времени t из указанного промежутка времени являются управляющие векторы (3). С геометрической точки зрения управление представляет собой некоторую кривую, состоящую из точек пространства, причем эта кривая непрерывна всюду, за исключением, возможно, некоторого конечного числа точек разрывов первого рода.

Предполагается, что возможные значения управляющих параметров удовлетворяют некоторым ограничениям. Эти ограничения в общей форме состоят в том, что управляющий вектор в каждый момент времени из интервала t0  t  t1 должен принадлежать некоторому фиксированному непустому подмножеству  r-мерного евклидова пространства

u(t) , t0  t  t1.

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

u(t)U.

Фазовая траектория {x(t)} определяется из уравнений движения, т.е. из системы дифференциальных уравнений, в которых скорость изменения каждой фазовой координаты представлена в виде функции фазовых координат, управляющих параметров и времени

x' = f(x(t), u(t), t),

или в развернутом виде

 fj(x1(t), x2(t), …, xn(t); u1(t), u2(t), …, ur(t); t),

 j=1,2, …, n.             (5)

Предполагается, что каждая из заданных функций f1(), f2(), …, fn() является непрерывно дифференцируемой. Если дифференциальные уравнения (5) не зависят явно от времени, то уравнения движения называются автономными. Важным примером такой системы уравнений являются линейные автономные уравнения движения

x' = Ax + Bu,

где А – фиксированная матрица размерности nn, а B – фиксированная матрица размерности nr.  

Фиксированные начальные значения фазовых координат (2) являются граничными условиями для уравнений движения. Если заданы начальные значения и управление {u(t)}, то существует единственная фазовая траектория {x(t)}, удовлетворяющая уравнениям движения и граничным условиям. Эту траекторию можно найти интегрированием дифференциальных уравнений при данных начальных условиях x(t0) = x0. Фазовая траектория, найденная в результате решения уравнений движения при данном начальном состоянии с использованием допустимого управления, называется допустимой, а любая фазовая точка на фазовой траектории, которую можно достичь за конечное время, называется достижимой.

Конечный момент времени t1 определяется условием

(x(t), t)  T  при  t = t1,

где Т – заданное подмножество в En+1, называемое конечной поверхностью. Важными частными случаями задачи управления являются задача с фиксированным временем, когда конечный момент времени t1 задан в явной форме как параметр задачи, и задача с закрепленным концом, когда x(t1) задан в явной форме как вектор параметров задачи.

Целевой функционал, максимум или минимум которого требуется найти, представляет собой отображение управлений (функций времени) на точки вещественной прямой. Этот функционал будет рассматриваться, как правило, в следующей форме:

J = J{u(t)} =  + F(x1, t1). (6)

Подынтегральная функция I() показывает, что функционал зависит от фазовых координат и управляющих параметров, являющихся функциями времени, и от времени, т.е.

I(x, u, t) = I(x1(t), x2(t), …, xn(t); u1(t), u2(t), …, ur(t); t),

где t0  t  t1.

Второе слагаемое F() в выражении для функционала, которое мы назовем функцией конечных параметров, показывает, что функционал зависит от конечного состояния и от конечного момента времени:

F(x1, t1) = F(x1(t1), x2(t1), …, xn(t1); t1).

Предполагается, что как I(), так и F() являются фиксированными непрерывно дифференцируемыми функциями. Целевой функционал записан в (6) как функционал, зависящий от управлений, потому что если вектор-функция f() и вектор x0 заданы, то управление {u(t)} определяет фазовую траекторию {x(t)}.

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

J = ,    (7)

то такую задачу называют задаче Лагранжа. Задачу, в которой подынтегральная функция равна нулю, так что

    J = F(x1, t1),     (8)

называют обычно задаче Майера. Может показаться, что задача Больца является более общей, нежели задачи Лагранжа или задача Майера, однако на самом деле все три задачи эквивалентны, что можно доказать с помощью соответствующих преобразований переменных. Так, например, всякую задачу Больца можно свести к задаче Майера, определив следующим образом дополнительную фазовую координату xn+1:

(t) = I(x, u, t),  xn+1(t0) = 0.

Тогда выражение (6) принимает вид

J = xn+1(t1) + F(x1, t1),

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

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

требуется найти   

=  + F(x1, t1)  (9)

при условии, что x' = f(x(t), u(t), t), t0 и x(t0) = x0 фиксированы, (x(t), t)T  при  t = t1, {u(t)}U.

Отметим, что стандартные обозначения в задаче управления отличаются от обозначений в задачах математического программирования. Динамическим аналогом вектора объектных переменных  x  из теории математического программирования является управление {u(t)}, а не фазовая траектория {x(t)}.

Геометрическая интерпретация задачи управления: из множества допустимых фазовых траекторий, начало которых соответствует заданному начальному состоянию x0 в начальный момент времени t0, требуется выбрать определенную фазовую траекторию, при этом необходимо учитывать, что каждая допустимая фазовая траектория осуществляется при использовании некоторого допустимого управления {u(t)}. Оптимальной траекторией {x*(t)} является такая допустимая фазовая траектория, заканчивающаяся на конечной поверхности, на которой достигается максимум целевого функционала.


Частные случаи

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

J = - (t1t0).

Тот же вид имеет функционал в задаче Лагранжа, в которой I() = -1. Так как время t0 задано, то в эквивалентной задаче Майера функция F() = - t1. Классическим примером задачи о минимальном времени перехода, относящимся еще к XVII столетию, является задача о брахистохроне. В этой задаче рассматривается движение материальной точки, которая под действием силы тяжести скатывается без трения вдоль некоторой кривой из фиксированной верхней точки в фиксированную нижнюю точку. Требуется определить кривую, соответствующую минимальному времени перехода. Другим примером может служить задача управления кораблем, когда требуется достичь места назначения за минимальное время.

Второй частный случай задач управления связан с работой автоматических следящих устройств (сервомеханизмов). В задачах такого рода известны желательные состояния объекта x0(t) в каждый момент времени определенного промежутка времени и требуется обеспечить, чтобы фактические значения фазового вектора в каждый момент времени были достаточно близкими к желательным состояниям. Например, при отапливании дома фазовой координатой является температура в помещении, которую желательно поддерживать на уровне, достаточно близком к заданному. Целевой функционал в этом случае имеет вид

J =

где () – функция, измеряющая отрицательный эффект от различия между фактическим и желательным состоянием.

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

Виды управления

В задачах управления встречаются два вида управления. Один из них – управление по разомкнутому контуру. В этом случае оптимальное управление, являющееся решением (9), определяется как функция времени

{u*(t)}.

Управление по разомкнутому контуру полностью определяется в начальный момент t0, а фазовая траектория {x(t)} отыскивается в результате интегрирования уравнений движения при фиксированных начальных условиях.

Другой вид управления – управление по замкнутому контуру (с обратной связью). В этом случае оптимальное управление определяется как функция текущих фазовых координат и времени

{u*(x(t), t)}.

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

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

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


Задача управления как задача программирования в бесконечномерном пространстве

Задачу управления можно считать задачей математического программирования в бесконечномерном пространстве. Рассмотрим следующую задачу управления:

= , x' = f(x, u),   (12)

t0 и x(t0)=x0 фиксированы, t1 фиксирован, {u(t)} U.

Эта задача отличается от (9) следующими свойствами: она автономна, т.е. уравнения движения и целевой функционал не зависят явно от времени; данная задача относится к классу задач Лагранжа, так как целевой функционал не зависит от конечного состояния или от конечного момента времени; эта задача с фиксированным временем, так как t1 задано, а x(t1) произвольно; задача содержит только один управляющий параметр и одну фазовую координату.

Заданный промежуток времени (t0  t  t1) можно разбить на N интервалов равной длины

= .

Время измеряется в дискретных единицах

t = T0+q,

где индекс q изменяется от 0 (что соответствует t = t0) до N (что соответствует t = t1). Состояния и управления замеряются в отмеченные дискретные моменты времени

xq = x(t0+q),     uq = u(t0+q).

Рассмотрим теперь задачу математического программирования с N+1 переменной  u0, u1, …, uN :

JN = ,  

xq+1xq = f(xq, uq),     (13)

q = 0, 1, …, N-1, x0 = x0,  uq,

где - фиксированный положительный параметр. Пределом целевой функции этой задачи при N, стремящимся к бесконечности, и , стремящемся к 0, и при фиксированной величине N равной (t1 - t0), является целевой функционал задачи (12), т.е.

JN = J.

При указанном переходе к пределу разностные уравнения в (13) превращаются в дифференциальные уравнения задачи (12). Таким образом, задачу управления можно считать задачей математического программирования в бесконечномерном пространстве. Этим пространством является множество всех кусочно-непрерывных вещественных функций u(t), определенных на промежутке t0  t  t1.

Основная теорема математического программирования – теорема  Вейерштрасса, указывает условия, достаточные для существования экстремума. Эти условия состоят в том, что целевая функция должна быть непрерывной, а допустимое множество – компактным.

Теорема Вейерштрасса. Пусть допустимое множество X является компактным (т.е. ограниченным и замкнутым) и непустым. Тогда непрерывная целевая функция f(x), определенная на этом множестве, достигает глобального максимума на внутренней или граничной точке множества X.

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

F(X) = {zE  z = F(x)  для  xX},

которое является компактным. Всякое компактное множество действительных чисел имеет верхнюю грань. Таким образом, если F* является верхней гранью F(X), то существует x*X, удовлетворяющий условию F(x*) = F*, а так как F(X)  F(x*) для всех xX, то точка x* является глобальным максимумом.

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

Обобщенная теорема Вейерштрасса. Решение общей задачи управления (9) существует, если целевой функционал J{u(t)} является непрерывным функционалом от функций управления и подмножество U бесконечномерного пространства, к которому принадлежат управления, является компактным.

Для доказательства теоремы обозначим символом J* точную верхнюю границу функционала J{u(t)} по всем {u(t)}U, т.е. J{u(t)}  J* при всех {u(t)}U. Возьмем некоторую последовательность управлений {up}, такую что

J* - < J{up}  J*.

Так как множество U  компактное, то эта последовательность содержит подпоследовательность  {u }, сходящуюся к некоторому управлению {u*}U. Тогда

J* - < J{u }  J*

и следовательно,

J{u } = J*.

Но так как функционал J непрерывен, т.е.

J{u } = J{u*},

то оптимальным является управление {u*}U, для которого

J{u*} = J*.

Источник:

Интриллигатор М. Математические методы оптимизации и экономическая теория. – М.: Айрис-пресс, 2002. – 576 с.


ВАРИАЦИОННОЕ ИСЧИСЛЕНИЕ

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

= ,  x(t0) = x0,  x(t1) = x1,  

где J(x, x', t) – фиксированная непрерывно дифференцируемая функция, а t0, t1, x0, x1 – фиксированные параметры.

Эта задача является частным случаем общей задачи управления:

найти   

=  + F(x1, t1)

при условии, что x' = f(x(t), u(t), t), t0 и x(t0) = x0 фиксированы, (x(t), t)T  при  t = t1, {u(t)}U.

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

x' = u,

так, что x' в I() заменяет u, а управляющий параметр может принимать любое значение, т.е.

U = E.

Следовательно, управление должно отвечать единственному условию – быть кусочно-непрерывной функцией времени. Любая траектория {x(t)} называется допустимой, если она удовлетворяет граничным условиям из (1) и следующему условию непрерывности: x(t) – непрерывная, а x'(t) – кусочно-непрерывная функция времени.

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

Вариационное исчисление основано в XVIII веке Л. Эйлером и Ж. Лагранжем, значительно развито в XIX веке в трудах ряда математиков и в настоящее время превратилось в один из важнейших разделов теоретической и прикладной математики, дающих пути к единообразной трактовке различных физических и прикладных задач и общие подходы к их исследованию, эффективные в качественном и количественном отношении.


 

А также другие работы, которые могут Вас заинтересовать

74259. ВНУТРИБОЛЬНИЧНАЯ ИНФЕКЦИЯ: РАБОТА С КРОВЬЮ И БИОЛОГИЧЕСКИМИ ЖИДКОСТЯМИ 269 KB
  В качестве самостоятельной работы рекомендуется составить тематический кроссворд; написать реферат на тему «Роль медицинской сестры в профилактике и контроле распространения ИСМП», «Масштаб проблемы ИСМП»; составить схему «Способы передачи инфекции в лечебно-профилактических учреждениях»
74260. ВНУТРИБОЛЬНИЧНАЯ ИНФЕКЦИЯ: ОБРАБОТКА РУК ПЕРСОНАЛА 655.3 KB
  Структура занятия с планом объяснения учебного материала и хронометражем. Манипуляции: № 2 Обработка рук медицинского персонала № 3 Использование перчаток надевание стерильных перчаток снятие использованных перчаток Ситуационные задачи. На занятии студенты изучают обработку рук медицинского персонала и правила пользования медицинскими перчатками.
74261. ВНУТРИБОЛЬНИЧНАЯ ИНФЕКЦИЯ: ПРОФИЛАКТИКА ПАРЕНТЕРАЛЬНЫХ ИНФЕКЦИЙ СРЕДИ МЕДПЕРСОНАЛА 72.25 KB
  О профилактике профессионального инфицирования медицинских работников вирусом иммунодефицита человека вирусных гепатитов В и С учете аварийных ситуаций и постконтактной профилактике. Вирусные гепатиты большая группа антропонозных инфекций с различными механизмами заражения и путями передачи инфекции и преимущественным поражением функциональных клеток печени гепатоцитов с возможным развитием в дальнейшем хронического поражения печени последствием чего...
74262. ДЕЗИНФЕКЦИЯ. ПРАВИЛА ОБРАЩЕНИЯ С МЕДИЦИНСКИМИ ОТХОДАМИ 183.5 KB
  Медицинские отходы – это материалы, вещества, изделия, лекарства, частично или полностью утратившие свои первоначальные потребительские свойства при осуществлении деятельности в медицинских учреждениях.