Задача на условный экстремум 61 нелинейное программирование 72 метод Ньютона в нелинейном программировании 88 выпуклое программирование 96
 Скачать 0.96 Mb.
|
|
(3) Функция ? H удовлетворяет условию ? H(x ? (t), ? ? (t)) ? const ? 0. џ5. Линейные оптимальные быстродействия 175 (4) Функции x ? и ? ? удовлетворяют канонической систе- ме ?x = Ax + Bu, ? ? = ?A 0 ?. (5) В конечный момент времени t 1 выполнено условие x(t 1 ) = 0. (17) Таким образом, для отыскания u ? требуется, прежде всего, о максимизации функции h?, Ax + Bui (18) при ограничении u ? U. (19) Задача (18), (19) представляет собой обычную задачу линей- ного программироваия. Как отмечалось в главе 2, эта задача (с заменой максимума на минимум и обратно) имеет решение, например, если многогранник U ограничен и имеет непустую внутренность. Более того, решение всегда лежит в одной из вершин многогранника U, т.е. любом фиксированном t значе- ние u ? (t) лежит в одной из вершин U. При этом оказывается, что максимум достигается именно в этой вершине, если только ни на одном из проходящих через нее ребер скалярное произ- ведение h? ? (t), Ax ? (t) + Bu ? (t)i не равно постоянной. В самом деле, если принять противное, то вычитанием немедленно получаем, что направление w такого ребра удо- влетворяет условию h?(t), Bwi = 0. (20) Далее, так как Bw вектор общего положения, то согласно предложению 3 равенство (20) может выполняться только для конечного множества T значений времени t, лежащих между t 0 и t 1 . Следовательно, дополнение к T на (t 0 , t 1 ) представляет собой конечное множество попарно непересекающихся интер- валов ? 1 , . . . , ? k . (21) Поэтому в силу непрерывности функции ? решение задачи (18), (19) лежит только в одной вершине, когда t принадлежит 176 Гл. 3. Основы оптимального упраления к каждому из интервалов множества (21). При этом, очевид- но, все моменты переключения оптимального управления u ? лежат в множестве T . Замечание. Если матрица A имеет только действительне собственые числа, то солгасно предложению 4 оптимальное управление u ? имеет не более чем (n ? 1) моментов переклю- чения, в которые значения u ? (t) функции u ? перескакавают с одной вершины многогранника U на другую вболь ребра, соединяющего эти вершины и имеющего фиксированное на- правление w. Таким образом, общее число переключений не превышает произведения числа (n ? 1) на число непаралелльных ребер многогранника U. В частности, если U куб, то число пере- ключений не превосходит m · (n ? 1). При этом следует иметь ввиду, что в подавляющем большинстве практических ситуа- ций приведенная выше оценка числа переключений оказыва- ется весьма завышенной. Получить же более тонкие оценки (насколько нам известно) пока не удалось. Существование и единственность оптимального уп- равления. Любое управление, удовлетворяющее теоремам 1 и 2, будем в дальнейшем называть подозрительным. Для уста- новления более тонкой связи между подозрительными и опти- мальными управлениями, прежде всего, сформулируем и до- кажем следующее Предложение 5. Пусть u подозрительное в зада- че о линейных оптимальных быстродействиях управление и пусть ?u произвольное управление класса U(t 0 , t 1 ) , переводя- щее систему (11) из точки (12) в точку (17). Тогда u(t) = ? u(t) (22) при всех значениях t 0 ? t ? t 1 за исключением, может быть, некоторого конечного множества. Доказательство. Для простоты обозначений положим v(t) = Bu(t) и ? v(t) = B ? u(t) џ5. Линейные оптимальные быстродействия 177 Обозначим через ?(t) (n Ч n)-матричную функцию времени, определенную на отрезке [t 0 , t 1 ] , равную единичной матрице при t = t 0 , и удовлетворяющую матричному дифференциаль- ному уравнению ?? = ??A. Аналогичным образом, через ? 0 (t) обозначим (n Ч n)-матрич- ную функцию времени, также определенную на отрезке [t 0 , t 1 ] , также равную единичной матрице при t = t 0 , но удовлетворя- ющую матричному дифференциальному уравнению ?? 0 = A? 0 . Тогда поскольку d dt (?? 0 ) = (??A)? 0 + ?A? 0 и ?(t 0 )? 0 (t 0 ) единичная матрица, то для всех значений t 0 ? t ? t 1 матрица ? 0 (t) является обратной матрицей для ?(t). Заметим теперь, что решение системы ? ? = A ? ? с начальным условием ?(t 0 ) = x 0 имеет вид ?(t) = ? 0 (t)x 0 . (23) Принимая во внимание принятые выше обозначения, перепи- шем систему (11) в следующем эквивалентном виде ?x = Ax + v(t) (24) Тогда в силу метода вариации произвольного постоянного и равенства (23) решение уравнения (24) с начальным условием (12) будем искать в виде x(t) = ? 0 (t)?(t), где ?(t 0 ) = x 0 и ? 0 ?? = v. (25) 178 Гл. 3. Основы оптимального упраления Умножив обе части равенства (25) на G(t) слева, получим ??(t) = ?(t)v(t), откуда следует, что решение системы (24) с начальным усло- вием (12) имеет вид x(t) = ? 0 (t) ? ?x 0 + t Z t 0 ?(? )v(? ) d? ? ? . (26) Заметим теперь, что по аналогии с (26) решение системы ??x = A?x + v(t) с начальным условием ? x(t 0 ) = x 0 имеет вид ? x(t) = ? 0 (t) ? ?x 0 + t Z t 0 ?(? )? v(? ) d? ? ? . Но так как по условию предложения 5 x(t 1 ) = ? x(t 1 ) отсюда получаем, что t 1 Z t 0 ?(t)v(t) dt = t 1 Z t 0 ?(t)? v(t) dt. (27) Умножим скалярно обе части равенства (27) на постоян- ный вектор ? 0 . Тогда, принимая во внимание тот факт, что каждое решение ?(t) системы (16) с начальным условием ?(t 0 ) = ? 0 имеет вид ?(t) = ? 0 ?(t), получим t 1 Z t 0 [h?(t), v(t)i ? h?(t), ? v(t)i] dt = 0. (28) џ5. Линейные оптимальные быстродействия 179 Поскольку по предположению u подозрительное управ- ление, оно максимизирует функцию (18) при ограничении (19). Поэтому возьмем в качестве ?(t) векторную функцию, сопря- женную к траектории x(t), задаваемой равенством (26); в этом случае ? H(x(t), ?(t), u(t)) = h?(t), Ax(t) + Bu(t)i = ? H(x(t), ?(t)), где ? H(x, ?) = max u?U h?, Ax + Bui. Заметим теперь, что подинтегральное выражение в (28) может быть записано в виде ? H(x(t), ?(t), u(t)) ? ? H(x(t), ?(t), ? u(t)), (29) причем по построению ? H(x(t), ?(t), u(t)) ? ? H(x(t), ?(t), ? u(t)) ? 0. Следовательно, равенство (22) выполняется почти всюду на [t 0 , t 1 ] . При этом на множестве значений времени t, для кото- рого разность (29) обращается в нуль, а u(t) 6= ? u(t), максимум в (18) при ограничении (19) достигается не в одной точке. Более того, для этих значений t справедливо равенство (20). Последнее, однако, возможно только лишь для конечного множества значений t. ¤ Теперь в задаче о линейных оптимальных быстродействи- ях оказывается возможным очертить ситуацию, когда доста- точно усердные поиски черной кошки в темной комнате могут привести успеху. Теорема 3. Пусть u подозритаельное управление, пе- реводящее систему (11) из точки (12) в точку (17). Тогда u оптимальное управление, причем единственное. Доказательство. Прежде всего, заметим, что в форму- лировке теоремы 3 отождествляются все управления, отлича- ющиеся лишь на некотором конечном множестве значений вре- мени t. 180 Гл. 3. Основы оптимального упраления Пусть ?u произвольное управление, определенное на от- резке [t 0 , t 2 ] , которое переводит систему (11) из точки (12) в точку x(t 2 ) = 0. Предположим, что t 2 ? t 1 , т.е. что управление ?u переводит систему (11) в начало координат не медленнее, чем управле- ние u. Продолжим, если потребуется, управление ?u на отрезок [t 0 , t 1 ] , положив ? u(t) = 0 при t 2 ? t ? t 1 ; последнее действие вполне корректно, по- скольку множество U по условию содержит начало координат пространства R m . Тогда согласно предложению 5 данное про- должение при всех значениях t 0 ? t ? t 1 (за исключением, может быть, некоторого конечного множества) удовлетворяет условию (22). ¤ Замечание. Теорема 3 дает одно из простейших усло- вий существования минимума, которое одновременно является и условием его единственности. Здесь невольно вспоминается умилительная ситуация, когда некая старушка неуверенными шаркающими шагами спускается в темный подвал, пытаясь найти своего ненаглядного угольного-черного Пушка. Если в подвале еще осталась сметана, весьма возможно, что Пушок окажется единственным его обитателем, ибо, как поется в из- вестной песенке, уже в те стародавние времена ... кота нена- видел весь дом. 1 Если же подходить к обсуждению этого вопроса более формально, то о силе теоремы 3 достаточно красноречиво го- ворит весь џ4, особенно упражнение 1 (см. также приводимое ниже упражнение 2). Упражнения. (1) Предположим, что многогранник U задается системой неравенств |u i | ? 1, i = 1, . . . , m. 1 За исключением, разумеется, старушки! џ5. Линейные оптимальные быстродействия 181 Рассматрите задачу об оптимальном быстродействии, за- ключающуюся в переводе системы ?x = f (x) + G(x)u из точки (12) в точку (17); здесь f = (f 1 , . . . , f n ) некото- рая векторная, а G действительная (n Ч m)-матричная функции, причем и f, и G, считаются определенными и непрерывно дифференцируемыми в пространстве R n (2) Предположим, что в задаче о линейных оптимальных бы- стродействиях все собственые значения матрицы A имеют неотрицательные действительные части. Покажите, что в этом случае для каждой точки x 0 ? R n оптимальное по быстродействию управление существует. Предметный указатель Аппроксимация квадратичная, 50 линейная, 35, 41 Базис в линейном программиро- вании, 120 Дифференциал, 36 Дифференцируемость по Фреше, 40 по Гато, 38 Двойственность в линейном про- граммировании, 115 Экстремаль, 132 Фазовые координаты, 139 Фазовое пространство, 139 Формула Тейлора с остаточным членом в форме Лагранжа, 48 с остаточным членом в форме Пеано, 48 Функционал, 129 Функция Гамильтона, 149 Гамильтона управляемая, 149 Лагранжа, 64, 79, 100, 140 модифицированная, 142 расширенная, 62, 143 числовая, 35 дифференцируемая, 35, 37, 41 непрерывная, 29 равномерно непрерывная, 29 управления, 148 выпуклая, 55 выпуклая на множестве, 97 Глобальный максимум, 55 минимум, 54, 98 Градиент, 35, 36 Грань множества, 112 точная нижняя, 23 точная верхняя, 22 Каноническая форма задачи ли- нейного программирования, 116 Канонические переменные, 149 Касание порядка (k ? 1), 170 Критерий ковариантности, 168 общего положения, 170 Линия переключения, 158, 165 Локальный максимум, 51 минимум, 51, 62, 73 Матрица Гессе, 47 Якоби, 41 Метод Ньютона, 90, 91 множителей Лагранжа, 64 штрафных функций, 68, 93 Минималь слабая, 131 182 Предметный указатель 183 Минимум функционала глобальный, 148 слабый, 131 Множество допустимых управлений, 148 допустимое, 147 компактное, 27 многогранное, 112 ограниченное, 22 открытое, 19 выпуклое, 96 замкнутое, 19 Неравенство Иенсена, 56 Коши Буняковского, 17 треугольника, 17 Норма матрицы, 43 Ограничение активное, 78, 101 неактивное, 78, 101 типа неравенств, 72 типа равенств, 72 Окрестность, 19 Парадокс Перрона, 134 Переменные двойственные, 100 прямые, 100 Пересечение порядка k, 170 План опорный, 120 оптимальный, 120 Подпространство ковариантное, 168 непрерывно дифференцируе- мое, 167 Последовательность ограниченная, 22 сходящаяся, 22 Принцип максимума Понтрягина, 149 обратной связи, 158 Производная Гато, 38 по направлению, 38 Ребро, 173 Симплекс, 112 Симплекс-метод описание, 120 реализация, 123 Система Эйлера, 138 Эйлера Лагранжа, 140 гамильтонова, 149 каноническая, 149 сопряженная, 149 Шар, 19 Теорема Больцано Вейерштрасса, 23 Ферма, 51 Каруша Джона, 73 Куна Таккера, 99, 109 Вейерштрасса, 33 двойственности, 104, 115 о методе множителей Лагран- жа, 64, 146 о непрерывности и равномер- ной непрерывности, 30 о седловой точке, 102 об ограниченных множествах и последовательностях, 25 Точка допустимая, 62, 73, 100 крайняя многогранного мно- жества, 112 максимума, 51 минимума, 51, 62, 73 минимума невырожденная, 54 минимума регулярная, 63, 101 множества граничная, 97 предельная, 19 седловая, 102 Траектория, 138, 148 оптимальная, 148 Управление оптимальное, 148 подозрительное, 176 Уравнение Эйлера, 132 Условие 184 Предметный указатель Липшица, 43, 44 Слейтера, 98 глобального минимума, 57 регулярности первое, 80 регулярности второе, 81 трансверсальности, 150 Условия дополняющей нежесткости, 78 регулярности, 80 Вариация, 38, 130 Мак-Шейна, 144 функционала, 131 игольчатая, 145 слабая, 130 Вектор общего положения, 170 Вершина, 113 невырожденная, 120 Внутренность множества, 97 Задача Дидоны, 10, 138 Лагранжа, 139 двойственная, 104, 115 изопериметрическая, 139 о быстродействии, 153 о брахистохроне, 130 о линейных оптимальных бы- стродействиях, 173 оптимального управления автономная, 153 со смешанными ограниче- ниями, 152 в форме Л.С. Понтрягина, 147 прямая, 104 регулярная, 101 вариационного исчисления общая, 143 простейшая, 129 Зигзаг бесконечно мелкий, 135 Литература [1] Абрамов Л.М., Капустин В.Ф. Математическое программирование. Л.: ЛГУ, 1976. [2] Алексеев В.М., Тихомиров В.М., Фомин С.В. Оптимальное управ- ление. М.: Наука, 1979. [3] Александров П.С. Введение в теорию множеств и функций. М.: ОГИЗ Гостехиздат, 1948. [4] Аоки М. Введение в методы оптимизации. М.: Hаука, 1977. [5] Архипов Г.И., Садовничий В.А., Чубариков В.Н. Лекции по матема- тическому анализу. М.: Дрофа, 2003. [6] Атанс М., Фалб П. Оптимальное управление. М.: Машинострое- ние, 1968. [7] Афанасьев А.П., Дикусар В.В., Милютин А.А., Чуканов С.В. Hе- обходимое условие в оптимальном управлении. М.: Наука, 1990. [8] Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1980. [9] Васильев Ф.П. Методы решения экстремальных задач. М.: Наука, 1981. [10] Галеев Э.М., Тихомиров В.М. Краткий курс теории экстремальных задач. М.: МГУ, 1989. [11] Зангвилл У. Нелинейное программирование. Единый подход. М.: Сов. радио, 1973. [12] Зуховицкий С.И., Авдеева Л.И. Линейное и выпкулое программиро- вание. М.: Наука, 1969. [13] Иоффе А.Д., Тихомиров В.М. Теория экстремальных задач. М.: Наука, 1974 [14] Карманов В.Г. Математическое программирование. М.: Наука, 1975. [15] Полак Э. Численные методы оптимизации. М.: Мир, 1974. [16] Поляк Б.Т. Введение в оптимизацию. М.: Hаука, 1983. [17] Понтрягин Л.С. Обыкновенные дифференциальные уравнения. М.: Наука, 1965. [18] Понтрягин Л.С., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко С.В. Математическая теория оптимальных процессов. М.: Физмат- гиз, 1961. 185 186 Литература [19] Пуанкаре А. Избранные научные труды. Т. II. М.: Наука, 1972. [20] Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. М.: Наука, 1980. [21] Рокафеллар Р. Выпуклый анализ. М.: Мир, 1973. [22] Сеа Ж. Оптимизация. Теория и алгоритмы. М.: Мир, 1973. [23] Федоренко Р.П. Приближенное решение задач оптимального управ- ления. М.: Наука, 1978. [24] Хеммильблау Д. Прикладное нелинейное программирование. М.: Мир, 1975. [25] Шварц Л. Анализ. Т. 1. М.: Мир, 1972. [26] Шилов Г.Е. Математический анализ. Функции нескольких веще- ственных переменных. Ч. 1, 2. М.: Наука, 1972. [27] Юдин Д.Б., Гольдштейн Е.Г. Линейное программирование. Теория и конечные методы. М.: Физматгиз, 1963. [28] Янг Л. Лекции по вариационному исчислению и теории оптималь- ного управления. М.: Мир, 1974. |