|
|
Статьи Соросовского Образовательного журнала в текстовом формате
Краткий очерк истории возникновения и развития экстремальных задач с ограничениями: математическое программирование, вариационное исчисление и оптимальное управление. Обсуждаются постановки задач.
ЗАДАЧИ НА ЭКСТРЕМУМПРИ НАЛИЧИИ ОГРАНИЧЕНИЙ
В. В. ДИКУСАР
Московский физико-технический институт,
Долгопрудный Московской обл.
ВВЕДЕНИЕ
В математике исследование задач на максимум и минимум началось давно, примерно 25 веков назад. Но только 300 лет назад были созданы первые общие методы решения и исследования задач на экстремум [1, 2].
Интенсивное развитие вариационного исчисления привело к созданию стройной теории для определенного класса задач. Однако потребности практической жизни, особенно в области экономики и техники, в последнее время выдвинули такие новые задачи, которые в большинстве случаев не удавалось решать старыми методами. Необходимость решения новых задач (в частности, космос, авиация и т.д.) привела к созданию новой теории, получившей название теории оптимального управления.
Основы теории оптимального управления были заложены академиком Л.С. Понтрягиным и группой его сотрудников в 50-60-е годы. В 1961 году вышла в свет первая монография [3], в которой излагались математические основы неклассического вариационного исчисления. Основным элементом в задаче Понтрягина выступает ограничение на управляющие воздействия. Кроме того, Л.С. Понтрягин указал новую форму необходимых условий экстремума.
Сегодня даже трудно поверить, насколько привычным и необходимым для теоретиков и прикладников стал аппарат теории управления. Достаточно только перечислить некоторые монографии, чтобы оценить практическое применение теории оптимального управления: "Ядерные реакторы и принцип максимума Понтрягина", "Оптимальное управление нагревом металла", "Оптимальное управление электромеханическими устройствами" и т.д.
Параллельно с принципом максимума Понтрягина происходило дальнейшее развитие классического вариационного исчисления для нового класса задач с ограничением на управление и фазовые координаты.
В 1963 году А.А. Милютин, используя идеи и методы функционального анализа, получил уравнение Эйлера для общей задачи оптимального управления (совместное ограничение на фазовые координаты и управления) и указал связь уравнения Эйлера с принципом максимума [4].
В 1966 году автор впервые в СССР и за рубежом решил задачу входа аппарата в атмосферу с учетом ограничений на величину полной перегрузки. Данное ограничение относится к классу нерегулярных смешанных ограничений. В 1968 году А.Я. Дубовицкий и А.А. Милютин опубликовали статью о нерегулярном принципе максимума [4]. Анализ перехода от уравнения Эйлера к принципу максимума называется расшифровкой. Задача расшифровки является довольно трудной для нерегулярных смешанных ограничений.
Следует заметить, что наличие нерегулярной ситуации в практических задачах означает по существу локальную неуправляемость в определенных точках оптимальной траектории.
Особенно много нерегулярных смешанных ограничений возникает в экономике, динамике полета и т.д. Возможность продолжения траектории через нерегулярную точку означает, что нужно заранее выбрать необходимое управление, чтобы гладко пройти критическую точку.
Подобного рода задачи получили название узких мест в управлении реальными процессами. Согласно табелю о рангах, по степени трудности задачи с нерегулярными смешанными ограничениями занимают первое место в теории оптимального управления. Обсуждая свою знаменитую программу, Д. Гильберт высказал надежду, что в XX веке математики овладеют способами решения оптимизационных задач. Это действительно проблема, ибо в вычислительном плане задачи управления на порядок более трудоемкие, чем все те задачи, с которыми до сих пор сталкивались исследователи.
Цель данной статьи - познакомить читателя с кругом идей и постановками основных задач вариационного исчисления и оптимального управления при наличии ограничений.
ФУНКЦИИ НЕСКОЛЬКИХ ПЕРЕМЕННЫХ
Совокупность n чисел называется упорядоченной, если указано, какое из этих чисел считается первым, какое - вторым и т.д. Произвольную упорядоченную совокупность n чисел часто записывают в виде x = (x1 , x2 , _, xn). Такую форму записи называют векторной.
Множество всевозможных упорядоченных совокупностей n чисел называется n-мерным координатным пространством и обозначается Rn.
Расстоянием между двумя произвольными точками M1(x1 , x2 , _, xn) и M2(y1 , y2 , _, yn), M1 k Rn, M2 k Rn, где символ k означает "принадлежит", называется число r(M1 , M2), определяемое формулой
Координатное пространство Rn с введенным расстоянием называется n-мерным евклидовым пространством и обозначается En.
Пример. E1 - числовая прямая (множество всех вещественных чисел), E2 - плоскость, E3 - трехмерное пространство.
Множество точек {M }, удовлетворяющих условию r(M, A ) # R, называется n-мерным шаром радиуса R с центром в точке A.
Множество {M } считается ограниченным, если оно целиком содержится в шаре радиуса R.
Точка A называется пределом последовательности точек {Mn }, если
Функция u = f (M ), M k Rn, называется непрерывной в точке A, если
Частной производной функции u = f (M ) по аргументу xk в точке M называется если он существует, где
Duk = f (x1 , x2 , _, xk - 1, xk + Dxk , xk + 1 , _, xn) -
- f (x1 , x2 , _, xk , _, xn).
Обозначается указанный предел через
Из определения частной производной функции многих переменных следует, что при этой операции остальные переменные остаются фиксированными. Последнее означает, что мы фактически вычисляем обыкновенную производную для функции одного переменного. В таком случае для вычисления частных производных не требуется новых правил дифференцирования и все операции сводятся к вычислению производной по известным правилам для функции одного переменного.
Пример.
БЕЗУСЛОВНЫЙ ЭКСТРЕМУМ
Пусть функция u = f (M ) = f (x1 , x2 , _, xn) определена в некоторой окрестности точки M0 .
Определение. Функция u = f (M ) имеет в точке M0 локальный минимум (максимум), если существует такая окрестность точки M0 , в которой при M ? M0 выполняется неравенство f (M ) $ f (M0) (f (M ) # f (M0)).
Точки локального максимума или минимума называют точками локального экстремума.
Теорема 1 [5] (необходимое условие экстремума). Если функция f (M) имеет в точке M0 локальный экстремум и в этой точке существуют частные производные функции по соответствующим аргументам, то
Система уравнений (1) определяет точки возможного экстремума функции u = f (M ). Точки, в которых частные производные равны нулю, называются стационарными.
Пример. Найдем стационарные точки функции
Уравнения (1) имеют вид
В результате получаем четыре стационарные точки
Какие из найденных точек действительно являются точками экстремума, устанавливается по достаточным условиям экстремума. Заметим, что M1 - точка минимума, M2 - точка максимума, а точки M3 и M4 не являются точками экстремума.
Достаточные условия экстремума для функций нескольких переменных имеют значительно более сложный характер, чем для функций одной переменной. Соответствующие условия можно найти в работах [5, 6].
УСЛОВНЫЙ ЭКСТРЕМУМ
Рассмотрим функцию
u = f (M )
при условии, что ее аргументы связаны между собой k соотношениями (k < n)
Fi(M ) = 0, i = 1, 2, _, k.
Соотношения (3) называют условиями связи.
Определение. Функция (2) имеет в точке M0 условный минимум (максимум) при условиях связи (3), если существует такая окрестность точки M0 , что для любой точки M этой окрестности из условий Fi(M ) = 0, Fi(M0) = 0, i = 1, 2, _, k, следует f (M ) $ $ f (M0) (f (M ) # f (M0)).
МЕТОД ИСКЛЮЧЕНИЯ ПЕРЕМЕННЫХ
Проиллюстрируем применение метода исключения переменных для функции u = f (x, y) при условии связи j(x, y) = 0. Если из уравнения связи y можно выразить явно через x: y = y(x), то, подставляя в u = f (x, y) вместо y функцию y(x), получим функцию одной переменной
u = f (x, y(x)) = F(x).
Из этого примера видно, что метод исключения переменных сводит задачу на условный экстремум к задаче на безусловный экстремум.
Пример. Найти стационарные точки функции
при условии x + y - 1 = 0.
Из условий связи имеем y = 1 - x. Отсюда
Легко проверить, что u(x) достигает максимума при x = 0,5. Из уравнения y = 1 - x получаем y = 0,5.
Если уравнения связи имеют более сложный вид и нам не удается явно выразить одни переменные через другие, то задача отыскания условного экстремума становится более трудной.
МЕТОД ЛАГРАНЖА
Задача об условном экстремуме функции (2) при условиях связи (3) эквивалентна задаче об условном экстремуме функции Лагранжа:
L(M ) = f (M ) + l1F1(M ) + l2F2(M ) + _ + lkFk(M ),
где li - произвольные числа при условиях связи (3), поскольку в точках M, удовлетворяющих уравнениям (3), справедливо равенство L(M ) = f (M ).
Теорема 2 [5] (необходимое условие Лагранжа условного экстремума). Если функция f (M ) имеет в точке M0 условный экстремум при наличии связей (3), и в этой точке существуют частные производные функции L(M ) по соответствующим аргументам, то тогда существуют числа l1 , l2 , _, lk такие, что
Система уравнений (3), (5) определяет точки возможного относительного экстремума функции u = = f (M ).
Пример 1. Среди всех треугольников с заданным периметром определить треугольник наибольшей площади.
Пусть стороны треугольника суть x, y, z. Тогда
где h1 , h2 , h3 - высоты треугольника. Для нахождения максимума S составим функцию Лагранжа
Согласно теореме 2, имеем
Отсюда следует h1 = h2 = h3 . По известной теореме из геометрии получаем x = y = z, то есть треугольник является равносторонним.
Пример 2. Найти прямоугольный параллелепипед наибольшего объема, если его полная поверхность равна заданной величине S.
Обозначим стороны параллелепипеда через x, y, z. Тогда получаем задачу о максимуме функции V = = xyz при условии связи
Функция Лагранжа имеет вид
Уравнение для отыскания точек экстремума получаем из теоремы 2:
yz + l(y + z) = 0,
xz + l(x + z) = 0,
xy + l(x + y) = 0.
Из этих уравнений следует x = y = z, то есть искомый параллелепипед - это куб.
ЗАДАЧИ ВАРИАЦИОННОГО ИСЧИСЛЕНИЯ
Первичным понятием вариационного исчисления является функционал. Например, важнейшие критерии качества систем управления - быстродействие, расход энергии или топлива - являются функционалами.
Функционал можно рассматривать как обобщение понятия функции, как функцию, в которой роль независимой переменной играет другая функция.
В классическом вариационном исчислении основным объектом исследования является функционал
Требуется найти минимум функционала (6) среди всех гладких линий y(x), соединяющих точки A(a, y0) и B (b, y1), a # x # b. Здесь гладкость y(x) означает непрерывность функции и непрерывность первой производной.
Подынтегральная функция F предполагается непрерывной и имеющей непрерывные частные производные по всем переменным до второго порядка включительно.
В качестве необходимого условия для задачи (6) выступает уравнение Эйлера
Пример. На каких кривых может достигать экстремума функционал
Уравнение Эйлера имеет вид y" + y = 0; его общим решением является функция y(x)= C1 cos x + + C2 sin x, где C1 и C2 - произвольные постоянные.
Используя граничные условия, получаем C1 = 0 и C2 = 1, следовательно, экстремум может достигаться лишь на кривой y = sin x.
ИЗОПЕРИМЕТРИЧЕСКАЯ ЗАДАЧА
Изопериметрическая задача сводится к отысканию экстремума функционала
при условии
Задача такого типа была известна еще древним грекам под названием задачи Дидоны. По преданию, легендарная основательница Карфагена царица Дидона покупала у туземцев землю, на которой должен быть основан город. Ей соглашались продать только участок, который можно охватить лишь бычьей шкурой. Тогда Дидона разрезала шкуру на тонкие ремни и расположила их так, чтобы охватить наибольшую площадь.
В современном математическом изложении Дидона решила именно изопериметрическую задачу, выбирая функцию y(x), доставляющую максимум интегралу
(площади, охваченной ремнем) при заданном значении интеграла (длине ремня)
Для решения задачи составляется функция Лагранжа
и для нее решается уравнение Эйлера. Ответ: окружность.
Рассмотрим более элементарное решение задачи Дидоны, предложенное автором. Пусть искомая фигура является выпуклой и представляет собой многоугольник со сторонами x1 , x2 , _, xn . Выберем в этом многоугольнике внутреннюю точку и разобьем многоугольник на треугольники с общей вершиной в выбранной точке. Суммарная площадь S равна
где h1 , h2 , _, hn суть соответствующие высоты треугольников.
По предположению, x1 + x2 + _ + xn = l. Составим функцию Лагранжа
Из необходимых условий получаем h1 = 2l, h2 = = 2l, _, hn = 2l, то есть h1 = h2 = h3 = _ = hn = h. Отсюда следует
S = (x1 + x2 + _ + xn)h = lh.
Из равенства высот треугольников следует равенство их оснований. Около правильного многоугольника можно описать окружность радиуса R. Увеличивая мелкость разбиения на треугольники, получим
Из условия l = 2pR получаем радиус окружности R = = , искомая площадь
ЗАДАЧА О ГЕОДЕЗИЧЕСКИХ ЛИНИЯХ
Требуется определить линию наименьшей длины, соединяющую две заданные точки А (x0 , y0 , z0) и B (x1 , y1 , z1) на поверхности j(x, y, z) = 0. Такие кратчайшие линии называются геодезическими. Мы имеем типичную вариационную задачу на связанный или условный экстремум.
Эта задача была решена в 1698 году Я. Бернулли, но общий метод решения задач такого типа был дан лишь в работах Л. Эйлера и Ж. Лагранжа.
Расстояние между двумя точками на поверхности определяется, как известно, по формуле
В данном случае надо найти минимум l при условии j(x, y, z) = 0. Эта задача решается с помощью функции Лагранжа
для которой уравнение Эйлера имеет вид
Из этих трех уравнений определяются искомые функции y = y(x), z = z(x), l = l(x).
Для случая сферы j(x, y, z) = x2 + y2 + z2 - R 2 = 0 геодезическими являются большие круги, получающиеся в пересечении сферы и плоскости, проходящей через начало координат z = ax + by. Коэффициенты a и b определяются из условия прохождения плоскости через центр сферы и точки А (x0 , y0 , z0), B (x1 , y1 , z1).
ПРИНЦИП МАКСИМУМА (ЗАДАЧА ПОНТРЯГИНА)
Пусть движение управляемого объекта описывается системой обыкновенных дифференциальных уравнений
Здесь x1(t), x2(t) называются фазовыми переменными, а u(t) - функция управления. На управляющую функцию u(t) наложено ограничение вида | u(t) | # 1, которое можно записать в виде системы двух неравенств:
j1(u) = -1 - u # 0,
j2(u) = u - 1 # 0.
Для системы (7) заданы начальные и краевые условия
x1(0) = а1 , x2(0) = а2 ,
x2(t1) = b2 .
Ставится задача максимизировать x1(t1) (x1(t1) ╦ ╦ max) при условиях (7)-(9). Поставлена задача, эквивалентная задаче определения необходимых условий экстремума для функционала от функции Лагранжа L,
где функции l1(t), l2(t), m1(t), m2(t) представляют собой множители Лагранжа.
Необходимое условие экстремума для функции u (t) имеет вид
m1(t) $ 0, m2(t) $ 0,
причем для m1(t) и m2(t) выполнено условие дополняющей нежесткости
m1(t)j1(u) = 0, m2(t)j2(u) = 0.
Из условия (12) следует, что максимум достигается на границе области, то есть u = ?1. Действительно, при l2(t) $ 0 имеем m2(t) = l2(t), что влечет за собой u = 1; при l2(t) < 0 получим m1(t) = - l2(t), то есть u = -1.
В принципе максимума принят другой формализм определения оптимального управления. Вместо вспомогательной функции Лагранжа L вводят в рассмотрение функцию Понтрягина
Здесь сопряженные функции y1(t), y2(t) играют роль множителей Лагранжа l1(t) и l2(t) (10). Они определяются системой уравнений
откуда следует, что y1 = C1 ; y2 = C2 - C1t, где C1 и C2 - произвольные постоянные.
Основное необходимое условие, которому должно удовлетворять управление u (t), чтобы быть оптимальным, можно записать в виде теоремы о максимуме: если u0(t) - оптимальное управление, то оно доставляет максимум функции P (13), то есть
Обычно для сопряженной переменной y1(t), соответствующей функционалу x1(t1) ╦ max, полагают y1(t1) = 1, откуда следует y1(t) ╞ 1. Таким образом, мы получаем однопараметрическую краевую задачу по выбору произвольной постоянной C2 , чтобы удовлетворить краевому условию x2(t1) = b2 .
Отметим, что принцип максимума сводит исходную задачу к решению краевой задачи для системы обыкновенных дифференциальных уравнений.
Сравнение принципа максимума и классического вариационного исчисления для систем линейных по управлению u(t) показывает их эквивалентность. Этот результат верен и для выпуклой области управления u(t).
Во всех других случаях принцип максимума позволяет определить экстремум в более широком классе функций u(t) для произвольной ограниченной области управления (в классическом вариационном исчислении рассматриваются кусочно-гладкие функции).
Общая формулировка задачи Понтрягина и принципа максимума приведена в работе [6]. Там же рассмотрены вопросы решения краевых задач на базе принципа максимума.
ЗАДАЧИ СО СМЕШАННЫМИ ОГРАНИЧЕНИЯМИ
Для системы (7) задано совместное ограничение типа неравенства (смешанное ограничение) на фазовую координату x1(t) и управление u(t)
Рассматривается задача о максимуме x1(t1), если выполнены ограничения (7)-(9), (16).
Если на оптимальной траектории при любом t k k [0, t1] выполнено условие j(x1 , u) < 0, то рассматриваемая задача сводится к задаче Понтрягина. В противном случае получаем задачу Дубовицкого-Милютина (задача DМ) [6].
Пусть на оптимальной траектории в какой-то момент времени t0 k [0, t1] выполнено соотношение j(x1 , u) = 0. Тогда из уравнения (16) имеем
Необходимый знак перед корнем определяется из условия максимума функции P (13), а именно
В этом случае сопряженные переменные удовлетворяют системе
где L = P - l(t)j(x, u) представляет собой функцию Лагранжа. Множитель Лагранжа l(t) определяется из условия
Траектория считается регулярной, если
Таким образом, в регулярном случае при движении по ограничению j(x1 , u) = 0 изменяются правые части системы сопряженных дифференциальных уравнений
а оптимальное управление вычисляется из условия связи j(x1 , u) = 0 согласно процедуре (17).
Основная трудность в решении поставленной задачи связана с определением момента схода с ограничения j(x1 , u) = 0. Дополнительный анализ показывает, что в регулярном случае оптимальная траектория будет находиться на ограничении на отрезке [t0 , t1]. В этом случае решение краевой задачи сводится к выбору начальных значений y1(0), y2(0) таким образом, чтобы удовлетворить краевым условиям y(t1) = 1, x2(t1) = b2 . Полученная краевая задача будет в этом случае двухпараметрической.
В нерегулярном случае существует такая точка t, что u(t) = 0, t k [0, t1]. В такой точке связь j(x1 , u) не будет нарушена, если Однако здесь появляются трудности в определении множителя Лагранжа
Вопросы построения нерегулярных траекторий рассмотрены в [6].
ЗАКЛЮЧЕНИЕ
Рассмотрение задач оптимизации с ограничениями типа равенств и неравенств на уровне необходимых условий сводится к проблеме безусловного экстремума с помощью принципа Лагранжа. Оказывается, что этот принцип распространяется на задачи довольно сложной природы, в том числе и на уравнения с частными производными. Однако каждый раз такой принцип требует обоснования. Указанное обстоятельство связано с появлением анормальных или вырожденных задач, для исследования которых требуются другие методы.
Основной проблемой при решении задач с фазовыми и смешанными ограничениями является исследование геометрии оптимальной траектории. Под геометрией понимается тип контакта фазовой траектории с ограничениями, а также определение моментов схода с ограничений типа неравенств. До сих пор этот вопрос в общем случае не решен. В работе [6] приведены примеры исследования геометрии оптимальной траектории для линейных задач.
В последнее время в России и за рубежом большое внимание уделяется алгебро-дифференциальным уравнениям при рассмотрении вопроса интегрирования обыкновенных дифференциальных уравнений с разнотемповыми процессами. Подчеркнем, что такие уравнения являются частным случаем в задаче Дубовицкого-Милютина.
Следует отметить также связь между теорией оптимального управления и задачами механики при наличии связей.
Задачи управления с ограничениями общего вида тесно связаны с многокритериальными задачами управления и являются более продвинутыми в смысле результатов и корректности постановки исходной задачи.
В теории оптимального управления принцип максимума - единственный аппарат, при помощи которого можно находить решение задачи или описывать его свойства, если, конечно, не принимать во внимание приближенные вычисления.
Не следует думать, что принцип максимума играет в оптимальном управлении гораздо большую роль, чем в вариационном исчислении. Строго говоря, не существует четкой границы между задачами оптимального управления и задачами вариационного исчисления.
ЛИТЕРАТУРА
1. Габасов Р.Ф. Экстремальные задачи в современной науке и приложениях // Соросовский Образовательный Журнал. 1997. ╧ 6. С. 115-120.
2. Колмановский В.Б. Задачи оптимального управления // Там же. 1997. ╧ 6. С. 121-127.
3. Понтрягин Л.С., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф. Математическая теория оптимальных процессов. М.: Физматгиз, 1961.
4. Дубовицкий А.Я., Милютин А.А. Необходимые условия слабого экстремума в задачах оптимального управления со смешанными ограничениями типа неравенства // Журн. вычисл. математики и мат. физики. 1968. Т. 8, ╧ 4. С. 725-779.
5. Бутузов В.Ф., Крутицкая Н.Ч., Медведев Г.Н., Шишкин А.А. Математический анализ в вопросах и задачах: Функции нескольких переменных: Учеб. пособие для студентов вузов. М.: Высш. шк., 1988. 288 с.
6. Афанасьев А.П., Дикусар В.В., Милютин А.А., Чуканов С.В. Необходимое условие экстремума. М.: Наука, 1991. 320 с.
* * *
Василий Васильевич Дикусар, доктор физико-математических наук, профессор кафедры высшей математики МФТИ, ведущий научный сотрудник Вычислительного центра РАН. Область научных интересов - теория управления, численные методы, финансовая математика. Автор более 80 научных статей, двух изобретений и трех монографий.
