Задача на условный экстремум 61 нелинейное программирование 72 метод Ньютона в нелинейном программировании 88 выпуклое программирование 96
 Скачать 0.96 Mb.
|
|
hb, µi ? min, c + A T µ ? 0, µ ? 0. (4) Для задачи (2) сформулируйте и докажите аналоги тео- рем 1315. џ6. Cимплекс-метод Как уже отмечалось ранее, решение задачи линейного про- граммирования достигается в одной из вершин многогранного множества. С другой стороны, предложение 1 позволяет отыс- кать такую вершину посредством нахождения решения неко- торой системы линейных уравнений. Поскольку число таких вершин конечно, то решение задачи линейного программиро- вания, вообще говоря, можно найти за конечное число шагов путем перебора вершин. При этом каждый из шагов вклю- чает в себя составление некоторой системы линейных уравне- ний (отыскание вершины) с последующим отысканием реше- ния этой системы. Симплекс-метод использует ту же идею, но реализует ее гораздо более тонко. Во-первых, просмотр вершин ведется та- ким образом, что значения целевой функции монотонно убы- вают. Это позволяет сразу существенно сократить перебор, по- скольку отбрасываются вершины со значением целевой функ- ции, большим уже найденного. Во-вторых, перебор ведется по соседним вершинам. Поэтому система линейных уравнений на новом шаге мало чем отличается от предыдущей. Последнее позволяет существенно сократить вычисления посредством ис- пользования специальных экономичных методов решения по- добных систем. џ6. Симплекс-метод 119 Общие положения. Симплекс-метод всегда применяют для задач линейного программирования, записанных в кано- нической форме hc, xi ? min, Ax = b, x ? 0, (1) где, как и ранее, x ? R n , A прямоугольная (m Ч n)-матрица, c и b вектора в пространствах R n и R m соответственно. Обозначим через Q многогранное множество Q = {x ? R n : Ax = b, x ? 0}. Тогда, используя технику выпуклого анализа, несложно дока- зать следующее предложение, весьма важное для реализации симплекс-метода. Предложение 3. Предположим, что многогранное мно- жество Q непусто. Тогда Q не содержит прямых, вершина- ми множества Q являются те точки x = (x 1 , . . . , x n ), для которых выполнено неравенство x i > 0, а соответсвующие столбцы a i матрицы A линейно незави- симы. Доказательство предложения 3 можно найти, например, в книге [16]. Из предложения 3 же следует, что в каждой вер- шине множества Q могут быть положительны не более, чем m компонент вектора x. Назовем точку x невырожденной вер- шиной, если число положительных компонент в ней равно m. При этом везде в дальнейшем будем считать, что множество Q непусто, а все его вершины невырождены. Заметим теперь, что в симплекс-методе исторически сло- жилась весьма специфическая терминология, с небольшими изменениями используемая в различных руководствах по ли- нейному и выпуклому программированию. Именно, допусти- мую точку часто называют планом, вершину опорным пла- ном или допустимым базисным решением, а решение зада- чи (1) оптимальным планом. Столбцы матрицы A, соот- ветствующие положительным компонентам опорного плана в 120 Гл. 2. Математическое программирование этом случае называют базисом. В дальнейшем, однако, следуя книге [16] мы не будем чрезмерно злоупотреблять такой тер- минологией, по возможности стараясь сохранить прежнюю допустимая точка, вершина и т.д. Описание симплекс-метода. Предполжим, что на k-ом шаге симплекс-метода получена точка x k = (x 1 k , . . . , x n k ) , явля- ющаяся невырожденной вершиной многогранного множества Q . При этом положим I k = {i : x i k > 0}. Согласно принятой невырожденности точки x k множество I k содержит ровно m элементов. Разобъем вектор x k на две группы x k = {u, v}, где u ? R m соответствует компонентам x i k с индексами из I k , а v ? R n?m компонентам x i k с индексами, не принадлежащими I k . Тогда система Ax = b может быть переписана в следующем виде A 1 u + A 2 v = b, (2) где A 1 (m Ч m)-матрица, столбцы которой являются столб- цами a i матрицы A с индексами из I k , а A 2 (m Ч (n ? m))- матрица, составленная из остальных столбцов матрицы A. Поскольку по предположению x k невырожденная вер- шина, то в силу предложения 1 матрица A 1 невырождена. По- этому, разрешая систему (2), имеем u = A ?1 1 (b ? A 2 v). (3) Заметим теперь, что целевая функция в задаче (1) может быть записана в следующем виде: hc, xi = hc 1 , ui + hc 2 , vi, где c 1 ? R m вектор с компонентами c i вектора c, соответ- ствующими i ? I k , а c 2 ? R n?m вектор с компонентами c i вектора c, соответствующими i /? I k . Тогда в силу равенства џ6. Симплекс-метод 121 (3) целевая функция может быть выражена только через v. Тогда имеем hc 1 , A ?1 1 (b ? A 2 v)i + hc 2 , vi = = hc 2 ? A T 2 (A ?1 1 ) T c 1 , vi + hc 1 , A ?1 1 bi, где T операция транспонирования. Таким образом, исходная задача (1) теперь эквивалентна задаче hc 2 ? A T 2 (A ?1 1 ) T c 1 , vi ? min, A ?1 1 (b ? A 2 v) ? 0, v ? 0. (4) В задаче (4) вершине x k соответствует вектор {u k , v k } , в котором u k > 0 (5) и v k = 0. (6) При этом точка (6) является допустимой точкой для задачи (4), а ограничение A ?1 1 (b ? A 2 v) ? 0 (7) удовлетворяется как строгое неравенство, поскольку A ?1 1 (b ? A 2 v k ) = A ?1 1 b = u k > 0. Следовательно, ограничение (7) может быть отброшено как неактивное при анализе точки v k на оптимальность. Но в за- даче hd, vi ? min, v ? 0, (8) где d = c 2 ? A T 2 (A ?1 1 ) T c 1 , минимум, очевидно, достигается тогда и только тогда, когда d ? 0 , причем hd, vi = 0. Таким образом, если d = c 2 ? A T 2 (A ?1 1 ) T c 1 ? 0, то точка v является решением задачи (8) и, следовательно, за- дачи (4). Тогда точка x k является решением задачи (1). Если 122 Гл. 2. Математическое программирование же среди компонент вектора d имеются отрицательные (на- пример, d j ), то точка v = 0 не является решением задачи (8), поскольку увеличение v j влечет за собой уменьшение целевой функции в (8). Рассмотрим случай, когда d j < 0. Пусть при этом e j j-й орт в пространстве R n?m . Вычислим новый вектор v k+1 по формуле v k+1 = v k + ? k e j , где ? k некоторое действительное число, выбираемое из сле- дующих соображений. С увеличением ? k целевая функция уменьшается. При этом, однако, может нарушиться ограничение A ?1 1 (b ? A 2 v) ? 0, которое при v = v k было неактивным. Поэтому ? k следует определять из условия ? k = max{? ? 0 : A ?1 1 (b ? ?A 2 e j ) ? 0}. Если окажется, что ? k = ?, то, очевидно, задача не имеет решения, поскольку в этом слу- чае inf x?Q hc, xi = ??, Если же ? k < ?, то получаем новую точку x k+1 = {u k+1 , v k+1 }, где u k+1 = A ?1 1 (b ? ? k A 2 e j ) и v k+1 = v k + ? k e j . Вновь полученная точка x k+1 является допустимой вер- шиной, поскольку она имеет m положительных компонент (j џ6. Симплекс-метод 123 компонента из вектора v k стала положительной в то время как одна из компонент вектора u k+1 обратилась в нуль). Поэтому в этой точке можно повторить всю процедуру заново. При этом поскольку hc, x k+1 i = hd, v k+1 i = hd, v k i + ? k hd, e j i = hc, x k i + ? k d j , где по построению ? k > 0 и d j < 0 , то hc, x k+1 i < hc, x k i. Таким образом, симплекс-метод обладает свойством мо- нотонности значений целевой функции при переборе вершин. Следовательно, возврат в какую-либо из ранее пройденных вершин здесь невозможен. Но так как число вершин конеч- но, симплекс-метод сходится за конечное число шагов. Реализация симплекс-метода. Приведенное выше опи- сание симплекс-метода не претендует на полноту. Чтобы пе- рейти от этого описания к четкому алгоритму нужно, вообще говоря, уточнить ряд вопросов. A) Прежде всего, рассмотрим вопрос о выборе начально- го приближения для симплекс-метода. Начальную точку x 0 , являющуюся вершиной многогранного множества Q, можно найти с помощью следующего приема, называемого методом искусственного базиса. Введем дополнительные переменные z = (z 1 , . . . , z m ) , иг- рающие роль невязок в ограничениях, и рассмотрим задачу их минимизации m X i=1 z i ? min (9) при ограничениях ha i , xi + z i = b i , i = 1, . . . , m (10) и x ? 0, z ? 0. (11) В этой задаче искомым является вектор {x, z} размерно- сти n+m, а точка {0, b} в пространстве R n+m является верши- ной. Последнее объясняется тем, что всегда можно принять b ? 0, 124 Гл. 2. Математическое программирование чего можно добиться, изменив знак ограничения ha i , xi = b i ; при этом будем считать, что среди компонент вектора b нет нулевых. Таким образом, для отыскания решения задачи (9)(11) можно применить симплекс-метод с начальным приближени- ем {0, b}. В результате получится либо точка {x 0 , 0} , где x 0 вершина в исходной задаче (1), либо точка, удовлетворяющая условию z 6= 0. Замечание. Во многих практических ситуациях введе- ние описанного выше дополнительного этапа можно избежать. Например, пусть исходная задача линейного программирова- ния имеет вид hc, xi ? min, Ax ? b, x ? 0, (12) где b > 0. Переводя задачу (12) в каноническую форму, можем записать hc, xi ? min, Ax + z = b, x ? 0, z ? 0. (13) Тогда точка {0, b} является невырожденной вершиной в задаче (13) и, таким образом, применять здесь метод искусственного базиса излишне. B) Второй вопрос связан с численной реализацией симп- лекс-метода. Вообще говоря, существует несколько способов хранения и преобразования используемых в симплекс-методе матриц и векторов. В основном численном варианте, где использует- ся метод обратной матрицы, вычисляется и хранится матри- ца A ?1 1 . Выражения же типа A T 2 (A ?1 1 ) T c 1 вычисляются пу- тем умножения этой матрицы на соответствующие вектора; при вычислении обратной матрицы A ?1 1 здесь используется то обстоятельство, что на последовательных итерациях соот- ветствующие матрицы A 1 получаются заменой лишь одного џ6. Симплекс-метод 125 столбца. Поэтому можно обращать эти матрицы рекурентно, используя различные соотношения, хорошо известные специа- листам по численным методам линейного программирования. При этом начальное приближение для A ?1 1 b в методе искус- ственного базиса не требует вычисления обратной матрицы, поскольку в этом случае A 1 единичная матрица. Приводить подробные формулы какой-либо реализации симплекс-метода представляется бессмысленным, поскольку в настоящее время соответсвующие программы, написанные профессионалами высшей квалификации, достигли совершен- ства с программистской и вычислительной точки зрения. Бо- лее того, эти программы сейчас стали общедоступными благо- даря компьютерной сети INTERNET. Принимая во внимание тот факт, что в современном мире задачи линейного програм- мирования приходится решать достаточно редко, можно сме- ло утверждать, что простому пользователю вряд ли придется когда-либо заниматься программной реализацией алгоритма симплекс-метода. Что же касается ситуации, когда решение задачи линейного программирования во что бы то ни стало нужно найти вручную, то в этом случае можно воспользо- ваться одним из многочисленных руководств, в том числе и специальных. 7 C) Существенные трудности при реализации симплекс- метода связаны с проблемой вырождения. При описании метода выше делалось предположение о невырожденности всех вершин. Отказ от этого предположе- ния может привести к невозможности обращения матрицы A 1 . Опасность подобной ситуации, главным образом, состо- ит в том, что при вычислениях некоторые компоненты точки x , характеризующей невырожденную вершину, могут оказать- ся достаточно близкими к нулю. На практике, к счастью, это случается довольно редко. Замечание. Необходимо отметить, что еще недавно сим- плекс-метод часто рассматривали как универсальное средство, позволяющее легко найти решение любой задачи линейного 7 См., например, [1, 9, 12, 27]. 126 Гл. 2. Математическое программирование программирования. Этим и объясняется стремление во что бы то ни стало научиться (чаще научить) решать такие задачи вручную. В настоящее время (во многом в связи с упомянутой проблемой вырождения вершин) данная точка зрения, однако, перестала быть общепринятой. Глава 3 Основы оптимального управления Настоящая глава посвящена изучению видимой части айс- берга: только так можно говорить о приведенных ниже эле- ментарных основах самого сложного и наиболее интенсивно развивиающегося раздела теории экстремальных задач оп- тимального управления. Формально общие математические основы оптимального управления заложены в середине прошлого века в трудах ака- демика Л.С. Понтрягина и его учеников (см. [18]). Известно, что в этот период жизни Л.С. Понтрягин занимался только ма- тематическими задачами, имеющими реальное практическое значение. И, хотя, можно лишь догадываться какая из реаль- ных задач привела к принципу максимума, фактически чело- век начал решать задачи оптимального управления в незапа- мятные времена. Открывает главу џ1, в котором рассматривается простей- шая задача вариационного исчисления. Данная задача имеет исключительно методическое значение, однако именно с нее начинаются многие современные курсы оптимального управ- ления. Объясняется это тем, что простым и естественным об- разом вводятся основные понятия и приемы, составляющие прообраз общего метода решения других уже реалистичных задач. Одной из важнейших особенностей простейшей задачи ва- риационного исчисления является то, что здесь почти сразу приходиться говорить о существовании решения этой задачи. Даная проблема в вариационном исчислении и теории опти- мального управления всегда стояла чрезвычайно остро и в на- ше время не потеряла своей актуальности. 127 128 Гл. 3. Основы оптимального упраления Непосредственным продолжением џ1 стал џ2, посвящен- ный изучению вариационных задач с ограничениями. Приме- няемый здесь метод восходит еще к Лагранжу и хорошо изве- стен нам по главе 2: с помощью некоторых множителей, на- зываемых множителями Лагранжа, задача с ограничениями сводится к задаче без таковых простейшей задаче вариаци- онного исчисления. При этом общая задача вариационного ис- числения остается здесь не рассмотренной, поскольку она свя- зывается в дальнейшем с задачей оптимального управления и обратно. Изложению основ математической теории оптимального управления в посвящен џ3. Здесь рассмотрена задача опти- мального управления в форме Л.С. Понтрягина и ее важней- ших частный случай, известный как задача об оптимальных быстродействиях. Необходимое условие в этих задачах зна- менитый принцип максимума Понтрягина остался в настоя- щей книге недоказанным. Причина для этого достаточно ува- жительная: приводить не совсем строгое доказательство авто- рам не хотелось, а более или менее простое и полностью кор- ректное доказательство (насколько нам известно) в настоящее время не найдено. В џ4 рассмотрены две частные задачи о линейных опти- мальных быстродействиях. Задачи эти выбраны не случайно, поскольку метод их решения весьма и весьма поучителен, по- сколку содержит много тонкостей, знание которых способству- ет выработке навыков обращения с более реалистичными зада- чами. Поэтому еще ни один учебник оптимального управления не прошел мимо них. Задача об оптимальных быстродействиях является одной из первых из дошедших до нас вариационных задач: доста- точно вспомнить задачу о брахистохроне Иоганна Бернулли. В наши дни актуальность этой задачи не снизилась. Более того, быстродействия в линейных системах оказались вполне доступными для подробного и продвинутого изучения и по- лученные здесь результаты в известной мере пригодны для практического использования. В џ5 достаточно полно изложе- на общая теория таких задач, включающая в частности про- стейшую теорему существования и единственности. џ1. Вариационное исчисление 129 џ1. Простейшая задача вариационного исчисления Как следует из названия, џ1 настоящей главы посвящена изучению простейшей задачи вариационного исчисления. Эта задача не является первой из известных вариационных задач: уже упоминавшаяся задача Дидоны появилась гораздо рань- ше. Вместе с тем, эта задача действительно проста, довольно точно отражает принципы решения вариационных задач и со- держит в себе достаточно много тонкостей, знакомство с кото- рыми весьма полезно при изучении вариационного исчисления и оптимального управления. Постановка задачи. Как вариационное исчисление, так и оптимальное управление оперируют в основном с функцио- налами, которым, вообще говоря, называется любое отбраже- ние J произвольного множества M на действительную ось R. Так, если f некоторая непрерывная числовая функция, то простейший пример функционала имеет вид J(y) = 1 Z 0 f (x, y(x)) dx, где y любая функция, определенная и непрерывная на от- резке [0, 1]. Замечание. Иногда в определении функционала требу- ют, чтобы множество M обязательно было функциональным пространством. Последнее излишне, поскольку приводит к за- мене определения примером. Простейшая задача вариационного исчисления заключа- ется в минимизации функционала J(y) = x 1 Z x 0 f (x, y(x), y 0 (x)) dx (1) в классе C 1 (x 0 , x 1 ) функций, определенных и непрывно диф- ференцируемых на отрезке [x 0 , x 1 ] . При этом дополнително бу- дем считать, что y(x 0 ) = x 0 , y(x 1 ) = x 1 . (2) 130 Гл. 3. Основы оптимального упраления Таким образом, принципиальное отличие простейшей задачи вариационного исчисления от задачи на условный экстремум состоит в том, что минимум следует искать среди функций, причем специально оговоренного класса. Пример 1. Рассмотрим задачу о минимизации функцио- нала J(y) = x 1 Z x 0 p 1 + y 02 dx. (3) Функция f здесь представляет собой длину кривой y, проходя- щей через точки (2), т.е. задача о минимизации функционала (3) является задачей об определении кратчайшего расстояния между двумя точками на плоскости. Пример 2. Рассмотрим задачу о минимизации функцио- нала J(y) = x 1 Z x 0 p 1 + y 02 ? y dx. Данная задача является первой из дошедших до нас про- стейших задач вариационного исчисления. Она восходит еще к Иоганну Бернулли и называется задачей о брахистохроне. Смысл ее состоит в следующем: какую форму должна иметь проволочка, чтобы кольцо соскальзывало по ней поддействи- ем только силы тяжести из одной заданной точки в другую за наименьшее время. Уравнение Эйлера. Пусть y и Їy две функции, опре- лененные на отрезке [x 0 , x 1 ] . Разность ?y = y(x) ? Ї y(x) называется вариацией. При этом говоря о вариации специ- ально оговаривают класс функций, в котором изменяется y. В дальнейшем, пока особо не будет оговорено противное, бу- дут рассматриваться функции класса C 1 (x 0 , x 1 ) . Соответству- ющая этому классу функций вариация ?y называется слабой вариацией. џ1. Вариационное исчисление 131 Если ?y некоторая вариация, то вариацией функционала называется разность ?J = J(y + ?y) ? J(y). Функцию y будем называть слабой минималью функцио- нала J, если для всех вариаций ?y, для которых величина max x 0 ?x?x 1 (|?y(x)| + |?y 0 (x)|) достаточно мала, выполнено неравенство J(y) ? J(y + ?y). В этом случае будем говорить о слабом минимуме функцио- нала J. Замечание. Легко видеть, что приведенное определения минимума функционала полностью аналогично определению минимумам функции, введенного в џ4. И в том, и в другой случае говориться о локальности минимума. Что касается до- бавления слова слабый в отношении минимума функционал, то это обстоятельство связано с тем, что пока исследование ведется на слабых вариациях. При этом необходимо отметить, что слабую вариацию легко перепутать с дамой, приятной во всех отношениях: все, казалось бы, прекрасно, однако слабый минимум может быть весьма далек от минимума вообще (см. пример 5). Переходя теперь к выводу необходимых условий слабого минимума в простейшей задаче вариационного исчисления, обозначим через y некоторую минималь, а через ?y соот- вествующую вариацию. Тогда имеем ?J = x 1 Z x 0 [f (x, y + ?y, y 0 + ?y 0 ) ? f (x, y, y 0 )] dx (4) Предположив, что функция f дифференцируема по y и y 0 , можем записать f (x, y + ?y, y 0 + ?y 0 ) ? f (x, y, y 0 ) = = f 0 y ?y + f 0 y 0 ?y 0 + o( p (?y) 2 + (?y 0 ) 2 ). (5) 132 Гл. 3. Основы оптимального упраления Тогда, объединив равенства (4) и (5), с учетом того, что y минималь, имеем неравенство x 1 Z x 0 [f 0 y ?y + f 0 y 0 ?y 0 ] dx ? 0. (6) Предположив теперь, что функция f дважды дифференци- руема по совокупности переменных, проинтегрируем второе слагаемое в (6) по частям. Проделав это, с учетом условия (2) окончательно получаем x 1 Z x 0 · f y ? d dx f y 0 ё ?y dx ? 0. (7) Поскольку неравенство (7) выполняется для всех вариа- ций ?y, для которых величина max x 0 ?x?x 1 |?y(x)| достаточно мала, то рассуждая по аналогии с доказательством теоремы Ферма (см. џ4), имеем уравнение d dx ?f ?y 0 x = ?f ?y x , (8) которому с необходимостью должна удовлетворять слабая ми- нималь. Уравнение (8) называется уравнением Эйлера. Относи- тельно y это уравнение второго порядка. Таким образом, за- дача отыскания функции, подозрительной на минималь, пред- ставляет собой двухточечную краевую задачу (8), (2). Любое решение уравнения Эйлера называется экстрема- лью (если угодно, слабой экстремалью). При этом легко ви- деть, что экстремаль обращает в нуль вариацию ?J функцио- нала J(y) и обратно (см. упражнение 2). Замечание. Сравнивая доказательство теоремы Ферма и вывод уравнения Эйлера несложно заметить, что идея до- казательства полностью совпадает с идеей вывода. Последнее весьма красноречиво говорит о целесообразности (и возмож- ности) единого подхода к экстремальным задачам. џ1. Вариационное исчисление 133 Примеры. Не вдаваясь в детали существования миниму- ма в задачах о кратчайшем расстоянии и брахистохроне, най- дем экстремали в этих задачах. Пример 3. Экстремали функционала (3) находятся со- всем тривиально. В самом деле, уравнение Эйлера в данном случае имеет вид d dx y 0 p 1 + y 02 = 0 или, что эквивалентно, y 00 = 0. Поэтому y = C 1 x + C 2 , что и следовало ожидать. Пример 4. Обратившись теперь к задаче о брахистохроне, прежде всего, перепишем уравнение Эйлера в следующем раз- вернутом виде: ?f ?y ? ? 2 f ?x?y 0 ? y 0 ? 2 f ?y?y 0 ? y 00 ? 2 f ? 2 y 0 = 0 или, что в данном случае эквивалентно, ?f ?y ? y 0 ? 2 f ?y?y 0 ? y 00 ? 2 f ? 2 y 0 = 0. (9) Заметим теперь, что d dx µ f ? y 0 ?f ?y 0 ¶ = y 0 ?f ?y ? y 02 ? 2 f ?y?y 0 ? y 0 y 00 ? 2 f ? 2 y 0 . Поэтому, умножив уравнение (9) на y 0 , видим, что уравнение Эйлера здесь приводит к уравнению d dx µ f ? y 0 ?f ?y 0 ¶ = 0. Таким образом, окончательно получаем, что f ? y 0 ?f ?y 0 = C. (10) 134 Гл. 3. Основы оптимального упраления Для удобства направим ось Ox плоскости R 2 как обычно, а ось Oy вертикально вниз. Тогда в силу (10) уравнение Эйлера в задаче о брахистохроне приводит к уравнению p 1 + y 02 ? y ? y 02 p y(1 + y 02 ) = C или, что эквивалентно, 1 p y(1 + y 02 ) = C. Поэтому y(1 + y 02 ) = C 1 . (11) Положим y 0 = ctg t. (12) Тогда из (11) следует, что y = C 1 1 + ctg 2 t = C 1 sin 2 t = C 1 2 (1 ? cos 2t). (13) Действуя формально, запишем dx = dy y 0 , откуда в силу (12) и (13) имеем dx = 2C 1 sin t cos t ctg t dt. Поэтому x = C 1 2 (2t ? sin 2t) + C 2 . (14) Несложно заметить, что соотношения (13), (14) дают урав- нения семейства циклоид. Таким образом, экстремалями в за- даче о брахистохроне являются циклоиды. Существование решений. Следуя [28], позволим себе привести небольшую математическую шутку. Парадокс Перрона. Пусть N наибольшее положитель- ное целое число. Тогда для N 6= 1 справедливо неравенство N 2 > N . Последнее, однако, противоречит определению числа N как наибольшего положительного целого. Другими слова- ми, N = 1. џ1. Вариационное исчисление 135 Несколько ранее по этому поводу великий Кун-цзы заме- тил: Очень сложно искать черную кошку в темной комнате. Особенно, если там ее нет. В главах 1 и 2 неоднократно гово- рилось о том, что прежде чем искать черную кошку, следует позаботиться о ее существовании (по крайней мере в темной комнате). В вариационном исчислении ситуация становиться еще более жесткой. В частности, экстремали могут не иметь к минимуму функционала никакого отношения. Чтобы пояснить эту мысль, процетируем теперь А. Лебега (см. [28]): Все мои статьи [по этому предмету] связаны с одной школьной шуткой. В колледже Бове мы часто доказыва- ли, что в треугольнике одна сторона равна сумме двух дру- гих. Рассмотрим треугольник ABC (см. рис. 1). Если точки A 1 , B 1 , C 1 середины сторон этого треугольника, то BA + AC = BC 1 + C 1 A 1 + A 1 B 1 + B 1 C. С каждым из треугольников BC 1 A 1 , A 1 B 1 C поступим так же, как с труегольником ABC. Мы получим ломанную линию, об- разованную восемью отрезками и равную BA + AC. Продол- жая этот процесс, мы получим последовательность ломаных линий, которые все меньше и меньше удаляются от стороны BC и имет длину, равную сумме двух сторон первоначально взятого треугольника. Ученики колледжа Бове заключали от- сюда, что отрезок BC, являющийся геометрическим пределом ломаных линий, имеет длину, равную сумме длин двух других сторон BA + AC. Данная история непосредственно говорит о том, что дли- на не является непрерывной функцией. Поэтому уже сейчас довольно наивно было бы утверждать, что уравнение Эйле- ра является типическим приемом решения подобных задач. Но гораздо более важным представляется то обстоятельство, что на горизонте появляется бесконечно мелкий зигзаг, значе- ние которого для вариационного исчисления и оптимального управления трудно переоценить. 136 Гл. 3. Основы оптимального упраления Ў Ў Ў Ў Ў Ў Ў Ў Ў Ў Ў Ў @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ Ў Ў Ў Ў Ў Ў @ @ @ Ў Ў Ў @ @ @ Ў Ў Ў @ @ ЎЎ @ @ ЎЎ @ @ ЎЎ @ @ ЎЎ B B 1 A 1 A C C 1 Рис. 1 Пример 5. Следуя [28], рассмотрим задачу о минимиза- ции функционала J(y) = 1 Z 0 (1 + y 2 )(1 + (y 02 ? 1) 2 ) dx (15) при ограничениях y(0) = y(1) = 0. (16) Вдоль оси Ox разобьем отрезок [0, 1] на четное число от- резков длины ? и построим на [0, 1] ломаную, поочередно при- няв либо y 0 = 1 , либо y 0 = ?1 (см. рис. 2). Соответствующая функция y принимает значения на отрезке [0, ?]. Поэтому зна- чение интеграла (15) не превосходит величины 1 + ? 2 С другой стороны, для любой кусочно-дифференцируемой на отрезке [0, 1] функции y, удовлетворяющей уловиям (16), для всех значений 0 ? x ? 1 справедливо неравенство (1 + y 2 (x))(1 + (y 02 (x) ? 1) 2 ) ? 1, где равенство имеет место тогда и только тогда, когда одно- временно y(x) = 0 (17) џ1. Вариационное исчисление 137 - 6 Ў Ў @ @ ЎЎ @ @ ЎЎ @ @ ЎЎ @ @ O 1 y x Рис. 2 и y 0 (x) = ±1. (18) Отсюда следует, что точная нижняя грань интеграла (15) рав- на единице и что достигается она на ломаной y, удовлетворя- ющей условиям (17) и (18), при ? ? 0. Описанная в примере 5 кривая y собственно и называет- ся бесконечно мелким зигзагом. Очевидно, что даже в про- стейшей задаче вариационного исчисления класс допустимых функций должен содержать такой зигзаг. Но как быть тогда с уравнением Эйлера? Упражнения. (1) Докажите лемму Дюбуа Раймона: Если для каждой непрерывной функции ? x 1 Z x 0 ?(x)?(x) dx = 0, где ? некоторая фукнция, определенная и непрерывная на отрезке [x 0 , x 1 ] , то ?(x) ? 0 на этом отрезке. (2) Покажите, что функция y является экстремалью тогда и только тогда, когда она обращает в нуль вариацию ?J функционала J(y). Указание: Используйте лемму Дюбуа Раймона. 138 Гл. 3. Основы оптимального упраления (3) Пусть y = (y 1 , . . . , y n ) векторная функция скалярного перменного x. Покажите, что в этом случае уравнения Эйлера для задачи (1), (2) представляют собой систему d dx ?f ?y i x 0 = ?f ?y i x , i = 1, . . . , n, называемую системой Эйлера. џ2. Вариационные задачи с ограничениями Как уже отмечалось, Дидона умела решать задачу более сложную, чем простейшая задача вариационного исчисления. Более того, считается, что задача, которую на самом деле ре- шала Дидона, была еще сложней (чем упомянутая в преди- словии), поскольку тирийцы столько купили земли, ... сколь- ко воловьей шкурой могли окружить на прибрежьи исходя из того, что построенный на этой земле Карфаген должен лежать на берегу моря. Для решения вариационной задачи, содержащей в себе за- дачу Дидоны, Лагранж предложил свой знаменитый метод множителей, описание которого приводится ниже. Кроме того, ниже оговариваются детали применения метода множителей Лагранжа, аналогичные тем, что и в главе 2, а также другие, более тонкие. Задача Лагранжа. Поскольку задача Лагранжа уже со- всем близка к современной задаче оптимального управления, будем в дальнейшем использовать соответствующие обозначе- ния. Пусть t независимое действительное переменное, име- ющее, вообще говоря, физический смысл времени, и пусть x(t) = (x 1 (t), . . . , x n (t)) n-мерная действительная функция t. В процессе своего движения точка с координатами (x 1 , . . . , x n ) описывает в пространстве R n некоторую кривую, называемую траекторией. Скорость движения точки будем обозначать че- рез ?x, понимая, естественно, что ?x = dx dt . џ2. Задачи с ограничениями 139 В этом случае пространство R n будем называеть фазовым про- странством, а координаты (x 1 , . . . , x n ) фазовыми координа- тами. В этих обозначениях задача Лагранжа представляет собой вариационную задачу о минимизации функционала J(x) = t 1 Z t 0 f (t, x, ?x) dt (1) при ограничениях g(t, x, ?x) = 0 (2) и t 1 Z t 0 h(t, x, ?x) dt = ?, (3) где g = (g 1 , . . . , g m ) и h = (h 1 , . . . , h r ) соответствующие век- торные функции, а ? заданный вектор. Если ограничение (2) отсутствует, то задача Лагранжа превращается в изопериметрическую задачу, являющуюся тривиальным обобщением задачи Дидоны. В любом случае ре- шение задачи (1)(3) будем искать в классе C 1 (t 0 , t 1 ) вектор- ных функций, определенных и непрывно дифференцируемых на отрезке [t 0 , t 1 ] . При этом (как и ранее) дополнительно будем считать, что x(t 0 ) = x 0 , x(t 1 ) = x 1 . (4) Метод множителей Лагранжа. Для решения задачи (1)(3) Лагранж собственно и ввел свой метод множителей, ко- торый, как он считал, может свести задачу с ограничениями к задаче без таковых. Трудно сказать, о чем думал Лагранж, но рассуждения здесь ничем не отличаются от соответствующих рассуждений в задаче на условный экстремум. Действуя как и в џ1 гл. 2 введем в рассмотрение новую функцию I(y) = f (t, x, ?x) + h?(t), g(t, x, ?x)i + h?, h(t, x, ?x) ? ? ?(t)i, в которой ? = (? 1 , . . . , ? m ) и ? = (? 1 , . . . , ? r ) действительные векторные функции времени t, а ? = (? 1 , . . . , ? r ) r-мерный 140 Гл. 3. Основы оптимального упраления действительный вектор. Определенную таким образом функ- цию L будем называть функцией Лагранжа. При этом вектора ? и ? здесь играют роль множителей Лагранжа, а функция ? удовлетворяет условию ?(t 0 ) = 0, ?(t 1 ) = ?. Для дальнейшего удобства введем в рассмотрение новую функцию Лагранжа L(t, x, ?x, ?, ?, ?) = = f (t, x, ?x) + h?(t), g(t, x, ?x)i + h?(t), h(t, x, ?x) ? ? ?(t)i в фазовом пространстве, расширенном добавлением соответ- ствующих новых переменных, с дополнительным ограничени- ем ?? = 0 (5) и рассмотрим простейшую задачу вариационного исчисления, заключающуюся в минимизации функционала t 1 Z t 0 L(t, x, ?x, ?, ?, ?) dt. Есди в последней задаче не принимать во внимание огра- ничения, то, как заметил Лагранж, уравнения Эйлера для этой задачи дадут систему d dt ?L ? ?x i = ?L ?x i , i = 1, . . . , n, d dt ?L ? ?? i = ?L ?? i , i = 1, . . . , m, d dt ?L ? ?? i = ?L ?? i , i = 1, . . . , r, d dt ?L ? ? ? i = ?L ?? i , i = 1, . . . , r, называемую системой Эйлера Лагранжа (см. џ1, упражне- ние 3). При этом в системе Эйлера Лагранжа последние три уравнения приводят к уравнениям (2), (5) и ? ? = h(t, x, ?x). џ2. Задачи с ограничениями 141 Замечание. Если вывод уравнения Эйлера аналогичен (по крайней мере идейно) доказательству теоремы Ферма, то внешний вид системы Эйлера Лагранжа весьма напоминает один из вариантов записи необходимого условия в задаче на условный экстремум в случае, когда в точке минимума выпол- нено условие регулярности. Пример 6. Помня о парадоксе Перрона и черной кошке, почему-то убежавшей из темной комнаты, рассмотрим задачу о минимизации функционала (1) при ограничениях (2) и (4) в следующих предположениях (см. [28]). Пусть размерность n фазового пространства R n равна двум. В пространстве R 3 переменных (t, x 1 , x 2 ) ось Ox 2 рас- положим вертикально, а оси Ot и Ox 1 горизонтально. Возь- мем произвольную точку P = (t 0 , x 1 0 , x 2 0 ) пространства R 3 и рассмотрим кривую x(t) = (x 1 (t), x 2 (t)) , проходящую че- рез P , имеющую кусочно-непрерывные производные ?x(t) = ( ?x 1 (t), ?x 2 (t)) , удовлетворяющие условию ?x 2 = p 1 + ( ?x 1 ) 2 . (6) Для фиксированной точки P любую такую кривую мож- но определить, если известна ее проекция на плоскость (t, x 1 ) При этом в силу (6) несложно заметить, что разность коори- нат x 2 в концах этой кривой совпадает с длиной ее проекции (см. пример 1). Следовательно, если принять, что проекция является отрезком, то через второй конец Q = (t 1 , x 1 1 , x 2 1 ) этой кривой, удовлетворяющей условию (6), нельзя провести ника- кую другую кривую, удовлетворяющую (6). Положим g(t, x 1 , x 2 , ?x 1 , ?x 2 ) = ?x 2 ? p 1 + ( ?x 1 ) 2 . Тогда для произвольной функции f в функционале (1) функ- цию Лагранжа рассматриваемой задачи можно записать в сле- дующем виде: L(t, x 1 , x 2 , ?x 1 , ?x 2 , ?) = (7) = f (t, x 1 , x 2 , ?x 1 , ?x 2 ) + ?(t) і ?x 2 ? p 1 + ( ?x 1 ) 2 ґ . Как было отмечено выше, в рассматриваемой задаче суще- ствует только одна кривая, удовлетворяющая условию (2) и 142 Гл. 3. Основы оптимального упраления соединяющая точки (4). В силу едиственности этой кривой именно на ней и только не ней и должен достичаться минимум. Поэтому можно было бы утверждать, что для произвольной функции f с функцией L, заданой равенством (7), с необхоли- мостью выполняются уравнения Эйлера Лагранжа. Послед- нее, однако, представляется более, чем сомнительным. В самом деле, заметим, что ?g ?x 1 = ?g ?x 2 = 0, ?g ? ?x 1 = ? ?x 1 p 1 + ( ?x 1 ) 2 и ?g ? ?x 2 = 1. Поэтому кривая x(t) = (x 1 (t), x 2 (t)) , проекция которой на плоскость (t, x 1 ) является отрезком, удовлетворяет системе Эйлера d dt ?g ? ?x i = ?g ?x i , i = 1, 2, для функции g, но не для функции L. Таким образом, в рассматриваемом примере функция f оказывается не у дел, что весьма красноречиво говорит о кор- ректности формального использования метода множителей. Поняв теперь (казалось бы), что нужно сделать прежде, чем искать черную кошку в темной комнате, запишем моди- фицированную функцию Лагранжа ?L в следующем виде ? L(t, x, ?x, ?, ?, ?) = = ? 0 f (t, x, ?x) + h?(t), g(t, x, ?x)i + h?(t), h(t, x, ?x) ? ? ?(t)i, где ? 0 уже знакомое нам по главе 2 действительное число, принципиально такое, что либо ? 0 = 0 , либо ? 0 = 1 . При этом в силу уравнения (5) и четвертого из уравнений системы Эйлера Лагранжа можем ввести в рассмотрение более естественную модификацию ЇL функции Лагранжа Ї L(t, x, ?x, ?, ?, ?) = (8) = ? 0 f (t, x, ?x) + h?(t), g(t, x, ?x)i + h?, h(t, x, ?x)i, џ2. Задачи с ограничениями 143 где ? 0 имеет прежний смысл, а ? некоторый вектор в про- странстве R r Определенную таким способом функцию ЇL будем назы- вать расширенной функцией Лагранжа. Теперь можно было бы сфофмулировать необходимые условие для задачи Лагран- жа, использующие как модифицированную, так и расширен- ную функции Лагранжа и аналогичные теореме 1 главы 2. Этого, однако, здесь делать не будем потому, что (к сожале- нию) не все еще ясно с черной кошкой. Общая задача вариационного исчисления. Как уже фактически отмечалось ранее, ограничение (3) в задаче Ла- гранжа не имеет самостоятельного значения, поскольку оно эквивалентно ограничениям ? ? = h(t, x, ?x) и ?(t 0 ) = 0, ?(t 1 ) = ?. Поэтому естественым обобщением задачи Лагранжа мож- но считать задачу о минимизации функционала J(x) = t 1 Z t 0 f (t, x, ?x) dt (9) при ограничениях g(t, x, ?x) = 0 (10) и h(t, x, ?x) ? 0, (11) где g = (g 1 , . . . , g m ) и h = (h 1 , . . . , h r ) соответствующие век- торные функции. Решение этой задачи будем искать в клас- се C 1 (t 0 , t 1 ) кусочно-дифференцируемых векторных функций, определенных отрезке [t 0 , t 1 ] . При этом дополнительное усло- вие x(t 0 ) = x 0 , x(t 1 ) = x 1 (12) можем опустить, включив его (если это необходимо) в ограни- чение (10). Сформулированную таким образом задачу будем назы- вать общей задачей вариационного исчисления. По сравнению 144 Гл. 3. Основы оптимального упраления с задачей Лагранжа эта задача имеет два принципиальных отличия: (1) Имеется ограничение (11). (2) Класс функций C 1 (t 0 , t 1 ) заменен классом C 1 (t 0 , t 1 ) Первое из этих отличий определяет собственно рассмат- риваемую задау. При этом оказывается, что второе отличие непосредственно связано с первым. В самом деле, как уже отмечалось ранее (см. пример 5), минимум функционала даже в простейшей задаче вариацион- ного исчисления совсем не обязан достигаться на слабых вари- ациях. В этом смысле второе отличие означает естественный отказ от обязательного использования слабых вариаций. Го- раздо более существенным представляется то обстоятельство, что наличие ограничения (11) в задаче (9)(12) фактически требует отказа от слабых вариаций. Именно, если функция x, минимизирующая функционал (9) при каком-либо значении t 0 ? ? ? t 1 удовлетворяет по крайней мере одному из условий h i (?, x(? ), ?x(? ) = 0, i = 1, . . . , n, то использование слабых вариаций здесь становиться невоз- можным. Рассмотреть задачу (9)(12) на всем множестве возмож- ных вариаций в настоящее время, насколько нам известно, неудалось. Однако уже к середине прошлого века была описа- на некоторая вариация, позволяющая свободно оперировать с ограничениями вида (11) и названная впоследствии вариацией Мак-Шейна. Построение вариации Мак-Шейна опишем на следующем тривиальном примере. Пример 7. Рассмотрим задачу о минимизации функцио- нала (9) при ограничениях x 0 ? x ? x 1 и (12). Пусть x(t) некоторая кривая и пусть ?x(t) вариация, определяемая равенством ?x(t) = x(t) ? Ї x(t), џ2. Задачи с ограничениями 145 6 - s s t 0 t 1 t x 0 x 1 x x(t) Ї x(t) Рис. 3 в котором Їx(t) кривая, полученная из x(t) протыканием последней иголкой до достижения ею ограничения (см. рис. 3). Такая вариация и называется вариацией Мак-Шейна. При этом о величине малости вариации Мак-Шейна судят по ма- лости интеграла t 1 Z t 0 |?x(t)| dt. В общем случае вариация Мак-Шейна получается имен- но протыканием абсолютно непрерывной функции иголками, причем обязательно до ограничения. Поэтому эту вариацию иногда называют также игольчатой вариацией. Формулировка необходимого условия минимума в задаче (9)(12) здесь опускается, поскольку ее всегда можно свести к задаче оптимального управления, изучению которой посвяща- ется оставшаяся часть главы 3. Упражнения. (1) Выведите аналог системы Эйлера Лагранжа для задачи (1)(4), взятой с расширенной функцией Лагранжа (8). 146 Гл. 3. Основы оптимального упраления (2) Решите задачу Дидоны в предположении, что: (a) Карфаген предполагается построить в пустыне; (b) Карфаген предполагается построить на берегу мо- ря (уравнение линии берега считается известным, а усло- вие (4) заданным). Указание: Используйте построения примера 4. (3) Рассмотрим задачу о минимизации функционала (1) при ограничениях g(t, x) = 0 (13) и (4). Докажите следующую теорему о методе множите- лей Лагранжа: Пусть x ? (t) минималь в задаче (1), (13), (4) и пусть вектора ?g i (t, x ? (t)), i = 1, . . . , m линейно независимы для всех значений t ? [t 0 .t 1 ] . Тогда x ? (t) удовлетворяет системе Эйлера Лагранжа d dt ?L ? ?x i = ?L ?x i , i = 1, . . . , n, d dt ?L ? ?? i = ?L ?? i , i = 1, . . . , m, где L(t, x, ?x, ?) = f (t, x, ?x) + h?(t), g(t, x)i. Указание: Используйте теорему о неявной функции. (4) Докажите теоремы 2 и 4 главы 2 с использованием теоре- мы о неявной функции. џ3. Принцип максимума Понтрягина Задача оптимального управления представляет собой со- временный вариант общей задачи вариационного исчисления. Изначально эта задача возникла из потребностей инженеров и военных и только потом, когда уже была заложены основы математической теории оптимального управления, было уста- новлено, что это задачи именно вариационного исчисления. В основе теории оптимального управления лежит знаме- нитый принцип максимума, высказанный в середине прошло- го века академиком Л.С. Понтрягиным в качестве гипотезы. Ниже в џ3 излагается элементарное введение в принцип мак- симума Понтрягина. џ3. Принцип максимума Понтрягина 147 Постановка задачи. Рассмотрим динамическую систе- му S, состояние которой в любой момент времени t характери- зуется точкой x(t) фазового пространства R n . Будем считать, что эволюция состояний системы S происходит во времени под действием управлений u(t), прилагаемых к S в момент време- ни t. При этом для простоты будем считать, что пространтсво управлений представляет собой пространство R m Предположим, что эволюция состояний системы S описы- вается нормальной системой обыкновенных дифференциаль- ных уравнений, векторная запись которой имеет вид ?x = f (t, x, u), (1) где f = (f 1 , . . . , f n ) некоторая векторная функция. Задача управления системой S заключается в минимизации функци- онала J(u) = t 1 Z t 0 f 0 (t, x, u) dt, (2) в котором f 0 заданная числовая функция. Предположим теперь, что все функции f 0 , f 1 , . . . , f n опре- делены и непрерывны по совокупности переменных вместе со своими частными производными ?f i ?t , i = 0, 1, . . . , n и ?f i ?x j , i = 0, 1, . . . , n, j = 1, . . . , n. При этом считается, что функция управления u принимает значения в некотором подмножестве U пространства R m В таких условиях формулированную выше задачу будем называть задачей оптимального управления в форме Л.С. Понтрягина, а множество U допустимым множеством. На практике множество U чаще всего бывает компактным множе- ством, например, m-мерным кубом; объясняется это тем, что физически обычно U шкала управления на пульте какого- либо прибора. 148 Гл. 3. Основы оптимального упраления Принцип максимума Понтрягина. Прежде всего, еще раз коротко обсудим вопрос о пребывании черной кошки в тем- ной комнате. Пусть U(t 0 , t 1 ) множество кусочно-непрерывных функ- ций, определенных на отрезке [t 0 , t 1 ] и принимающих зна- чения в множестве U. Тогда будем говорить, что U(t 0 , t 1 ) множество допустимых управлений, если каждой функции u ? U(t 0 , t 1 ) соотвествует единственное решение системы (1), принадлежащее к классу C 1 (t 0 , t 1 ) и удовлетворяющее некото- рому начальному условияю x(t 0 ) = x 0 . Определенную таким образом функцию u будем называть функцией управления, а соотвествующую ей кривую x тра- екторией. Очевидно, что говорить о существовании решений x ? C 1 (t 0 , t 1 ) задачи (1), (2) можно говорить только в том слу- чае, когда множество U(t 0 , t 1 ) непусто, что и предполагается. Этого, однако, недостаточно. Функция u ? класса U(t 0 , t 1 ) называется оптимальным управлением, если для любой другой функции u ? U(t 0 , t 1 ) выполнено неравенство J(u ? ) ? J(u). При этом траекторию x ? , соответсвующую оптимальному уп- равлению u ? , будем называть оптимальной траекторией. Легко видеть, что данное определение говорит о глобаль- ном минимуме функционала (2), что говорит о еще одном принципиальном отличии задачи оптимального управления от задачи Лагранжа. Если множество U(t 0 , t 1 ) непусто, оно, очевидно, совсем не обязано содержать оптимальное управление u ? . Чтобы га- рантировать это, нужно сформулировать для рассмативаемой задачи теорему, аналогичную теореме 7 главы 1. Последнее, однако, далеко выходит за рамки вводного курса. Поэтому в дальнейшем будем считать выполненным некоторое условие существования u ? џ3. Принцип максимума Понтрягина 149 Наряду с фазовым вектором x введем вектор канониче- ских переменных ? = (? 1 , . . . , ? n ) , сопряженных к x. Для это- го положим H(t, x, ? 0 , ?, u) = n X i=0 ? i f i (t, x, u), (3) где ? 0 некоторое действительное число, а ? 1 , . . . , ? n (как функции времени t) удовлетворяют сопряженной системе ? ? i = ? ?H ?x i , i = 1, . . . , n. Определенная таким способом функция H называется уравля- емой функцией Гамильтона. При этом функцией Гамильтона называется функция H, удовлетворяющая условию H(t, x, ? 0 , ?) = max u?U H(t, x, ? 0 , ?, u), где по предположению максимум достигается в некоторой точ- ке u ? допустимого множества U. В силу равенства (3) несложно заметить, что функции x и ? удовлетворяют каноноческой или гамильтоновой системе ?x i = ?H ?? i , ? ? i = ? ?H ?x i , i = 1, . . . , n. (4) Тогда имеет место следующая Теорема 1 (принцип максимума Понтрягина). Если u ? оптимальное управление в задаче (1), (2) и x ? (t) = (x ?1 (t), . . . , x ?n (t)) соответствующая траектория, то найдется такое дей- ствительное число ? ? 0 ? 0 и такая векторная функция ? ? (t) = (? ? 1 (t), . . . , ? ? n (t)), что: (1) Для всех значений t 0 ? t ? t 1 все величины ? ? 0 и ? ? 1 (t), . . . , ? ? n (t) не равны нулю одновременно. (2) Для всех значений t 0 ? t ? t 1 H(t, x ? (t), ? ? 0 , ? ? (t), u ? (t)) = H(t, x ? (t), ? ? 0 , ? ? (t)). 150 Гл. 3. Основы оптимального упраления (3) Функции x ? и ? ? удовлетворяют канонической си- стеме (4). (4) На концах траектории x ? выполнено условие транс- версальности " n X i=1 ? ? i ?x ?i ? H?t # t 1 t 0 = 0. Доказательство теоремы 1 совсем нетривиально и, потому, здесь опускается (см., например, [18]). Отметим только, что в любом случае оно (доказательство) осуществляется с исполь- зованием вариаций Мак-Шейна. Отметим также следующие важнейшие обстоятельства. A) В условиях теоремы 1 величина ? ? 0 не определена и, если принципиально нельзя принять ? ? 0 = ?1, то ? ? 0 = 0. B) Если концы P = (t 0 , x 0 ) и Q = (t 1 , x 1 ) траектории x ? закреплены, то условие трансверсальности заменяется услови- ями x ? (t 0 ) = x 0 и x ? (t 1 ) = x 1 . C) Если точки x 0 и x 1 закреплены, а время перехода из конца P в конец Q свободно, то условие трансверсальности принимает вид [H?t] t 1 t 0 = 0. В частности, если конец P закреплен, а конец Q нет, то H(t 1 , x ? (t 1 ), ? ? 0 , ? ? (t 1 )) = 0. D) Если конец P закреплен, а в конце Q время t 1 свобод- но и точка x 1 лежит на гиперповерхности M, имеющей в x 1 касательную гиперплоскость T x 1 M , то H(t 1 , x ? (t 1 ), ? ? 0 , ? ? (t 1 )) = 0, џ3. Принцип максимума Понтрягина 151 а вектор ? ? (t 1 ) ортогонален к T x 1 M E) Если конец P закреплен, а в конце Q точка x 1 свободна и время t 1 закреплено, то ? ? (t 1 )) = 0. Пример 8. Рассмотрим задачу о минимизации функцио- нала J(u) = t 1 Z t 0 f 0 (t, x 1 , x 2 , u) dt (5) при условии, что эволюция состояний системы S характеризу- ется уравнениями ?x 1 = u (6) и ?x 2 = p 1 + (u) 2 . (7) Предположим, что концы P и Q в задаче (5)(7) закреп- лены. Тогда, как легко видеть, эта задача представляет собой частный случай задачи, описанной ранее в примере 6. Поэтому здесь, вообще говоря, ? ? 0 = 0. В самом деле, управляемая функция Гамильтона в задаче (5)(7) имеет вид H(t, x 1 , x 2 , ? 0 , ? 1 , ? 2 , u) = = ? 0 f 0 (t, x 1 , x 2 , u) + ? 1 u + ? 2 p 1 + (u) 2 , где канонические переменные ? 1 и ? 2 удовлетворяют уравне- ниям ? ? 1 = ?? 0 ?f 0 ?x 1 (8) и ? ? 2 = ?? 0 ?f 0 ?x 2 . (9) Более того, для всех значений t 0 ? t ? t 1 , x 1 , x 2 , ? 1 и ? 2 опти- мальное управление u ? должно удовлетворять условию ?H ?u = 0 152 Гл. 3. Основы оптимального упраления в развернутом виде имеющему вид ? 0 ?f 0 ?u + ? 1 + ? 2 u p 1 + (u) 2 = 0. (10) Согласно примеру 6 при закрепленных концах P и Q су- ществует единственная кусочно-непрерывная функция u, для которой кривая x(t) = (x 1 (t), x 2 (t)) является соответствую- щим решением системы (6), (7). Поэтому система (8), (9) так- же имеет единственное решение ?(t) = (? 1 (t), ? 2 (t)) , соответ- ствующее всем возможным u(t) и x(t), переводящим систему из точки P в точку Q. Поэтому из условия (10) следует, что для всех значений t 0 ? t ? t 1 ? 0 ?f 0 ?u = ?(t), (11) где ? фиксированная функция, определенная и непрерывная на отрезке [t 0 , t 1 ] Таким образом, окончательно получаем, что при всех зна- чениях t 0 ? t ? t 1 равенство (11) выполняется с произвольной функцией f 0 и фиксированной функцией ?. Поэтому остается принять ? 0 = 0. Замечание. Несложный анализ примера 8 показывает, что замена ?x = u всегда позволяет свести общую задачу вариационного исчисле- ния к некоторой задаче оптимального управления. Эта задача (в отличие от задачи (1), (2)), вообще говоря, может содер- жать дополнительные ограничения на фазовые координаты и управления. Подобные задачи, называемые задачами опти- мального управления со смешанными ограничениями, чрез- вычайно сложны и, потому, здесь только упоминаются (см., например, [7]). Задача о оптимальном быстродействии. Рассмотрим частный случай задачи оптимального управления, в которой проблема выбора ? ? 0 отсутствует. Для этого, прежде всего, предположим, что все функции f 0 и f явно не зависят от t џ3. Принцип максимума Понтрягина 153 и будем называть соответствующую задачу (1), (2) автоном- ной. Одна из основных особенностей автономных задач состоит в том, что в случае, когда левый конец P закреплен, а время работы системы свободно H(x ? (t), ? ? 0 , ? ? (t)) ? 0. (12) Это следует из того, что в рассматриваемом случае H(x ? (t 1 ), ? ? 0 , ? ? (t 1 )) = 0 и того факта, что здесь при доказательстве принципа макси- мума неизбежно появляется тождество H(x ? (t), ? ? 0 , ? ? (t)) ? const (см., например, [18]). Замечание. Принятое выше требование автономности не накладывает на нас каких-либо существенных ограничений, поскольку введение нового пременного ?x n+1 = 1, x n+1 (0) = t 0 всегда приводит неавтономную задачу к автономной. Более то- го, большинство встречающихся на практике задач оптималь- ного управления являются автономными. Предположим теперь, что в автономной задаче с закреп- ленным левым концом и свободным временем перехода f 0 (x(t), u(t)) ? 1. Любую такую задачу называют задачей об оптимальном бы- стродействии. Смысл такого названтя вполне понятен, по- скольку в этом случае фунцкионал (2) представляет собой вре- мя перехода из точки P в точку Q, а простейшим (и древней- шим) примером такой задачи является уже упоминавшаяся ранее задача о брахистохроне. Согласно принципу максимума Понтрягина в этой задаче функция Гамильтона H удовлетворяет тождеству (12), а вели- чины ? ? 0 , ? ? 1 (t), . . . , ? ? n (t) не обращаются в нуль одновременно. Поэтому для всех значений t 0 ? t ? t 1 |? ? (t)| 6= 0, (13) 154 Гл. 3. Основы оптимального упраления так как в противном случае наряду с равенством |? ? (t)| = 0 выполняется также равенство ? ? 0 = 0. Поэтому удалим из задачи ? 0 (и, соответственно, ? ? 0 ), положив ? H(x, ?, u) = H(x, ? 0 , ?, u) ? ? 0 и ? H(x, ?) = H(x, ? 0 , ?) ? ? 0 . Тогда в качестве тривиального следствия теоремы 1 имеет ме- сто следующая Теорема 2. Если u ? оптимальное управление в задаче быстродействии и x ? (t) = (x ?1 (t), . . . , x ?n (t)) соответствующая траектория, то найдется такая век- торная функция ? ? (t) = (? ? 1 (t), . . . , ? ? n (t)), что: (1) Для всех значений t 0 ? t ? t 1 выполнено условие (13). (2) Для всех значений t 0 ? t ? t 1 имеет место равен- ство ? H(x ? (t), ? ? (t), u ? (t)) = ? H(x ? (t), ? ? (t)). |