22.18 А 47 УДК 519.6 Сборник задач по оптимизации. Теория. Примеры. Задачи. Учебное пособие. Алексеев В. М., Галеев Э. М., Тихомиров В. М.—М.: Наука. Главная редакция физико-математической литературы, 1984.— 288 с. В книге собрано примерно 700 задач на отыскание экстрему- мов для конечномерного случая, для задач классического вариа- ционного исчисления, оптимального управления и выпуклого про- граммирования. Содержатся элементы функционального анализа, дифференциального исчисления и выпуклого анализа. В книге приведены теория, необходимая для решения задач, и примеры. Основу решения всех задач составляет единый прин- цип, восходящий к Лагранжу. Часть задач приведена с решения- ми. Имеется большое количество трудных задач, которые могут быть использованы в качестве курсовых и дипломных работ. Для студентов вузов по специальностям «Математика» и «При- кладная математика», а также для аспирантов и научных работ- ников. Владимир Михайлович Алексеев, Эльфпт Михайлович Галеев, Владимир Михайлович Тихомиров СБОРНИК ЗАДАЧ ПО ОПТИМИЗАЦИИ Редактор И. Д. Григоренко Техн. редактор Л. В. Лихачева. Корректор Г: В. Подеольская ИБ М 12229 Сдано в набор 14.06.83. Подписано к печати 31.01.84. Формат 84х108'/.,2. Бумага тип М 3. Обыкновенная гарнитура. Высокая печать. Условн. печ. л' 1512 Условн. кр.-отт. 15,12. Уч.-изд. л. 17,9. Тираж 18000 экз. Заказ J\i 677. Цена 90 коп. Издательство «Наука» Главная редакция физико-математической литературы 117071, Москва, В-71, Ленинский проспект, 15 4-я типография издательства «Наука» 630077, Новосибирск, 77,-Станиславского, 25 д 1702070000-042 g-g„ 053(02)-84 (р\ Издательство «.Наука». vS' Главная редакция физико-математической литературы, 1984 ОГЛАВЛЕНИЕ Предисловие Введение. Принцип Лаграцжа в теории экстремальных задач ....,,.,,.,..., 9 0.1. Основные понятия, связанные с экстремальными за- дачами (9). 0.2. Принцип Лагранжа исследования задач с ограничениями (13). Упражнения (19).. Глава I. Предварительные сведения и задачи с ограниче- ниями .............. 21 § 1. Элементы функционального анализа и дифференциаль- ного исчисления ............ 21 1.1. Нормированные и банаховы пространства (21). Уп- ражнения (23). 1.2. Некоторые теоремы из геометрии и фунКЦйовального анализа (24). Упражнения (26). 1.3. Леммы (27). 1.4. Определения производных (28). Упражнения (30). 1.5. Основные теоремы дифференци- ального исчисления в нормированных пространствах (31). Задачи ................ 35 § 2. Гладкие задачи ............ 38 2.1. Элементарные задачи (38). 2.2. Гладкая конечно- мерная задача с ограничениями типа равенств. (40). 2.3. Гладкая задача с равенствами и неравенствами (об- щий случай) (43). 2.4 Примеры (45). 2.5. Необходимые условия высших порядков. Достаточные условия (47). 2.6. Примеры (51). 2.7. О методе Ньютона (52). Задачи ................ 53 § 3. Элементы выпуклого анализа ....... 58 3.1, Основные понятия (58). 3.2. Основные теоремы и формулы выпуклого анализа (60). Упражнения (65). Задачи ............... 66 § 4. Выпуклые задачи ........... 68 4.1. Принцип Лагранжа в выпуклом программировании (68), 4.2. Теория двойственности (70). 4.3. Линейное программирование (73). 4.4. Выпуклый анализ и теория экстремальных задач (74). Задачи ............... 82 Глава II. Классическое вариационное исчисление . . 84 § 5. Простейшие задачи классического вариационного ис- числения .............. 84 5.1. Задача Больца (84). 5.2. Простеишая задача клас- сического вариационного исчисления (90). 5.3. Приме- ры (93). 5.4. Задачи с подвижными концами (97). 5.5. Необходимые условия высших порядков и достаточ- ные условия. Теорема Боголюбова (102). 5.6. Теория по- ля. Уравнение Гамильтона — Якоби (107). 5.7, Приме- ры (111). Задачи ............... 113 § 6. Изопериметрические задачи ........ 123 6.1. Принцип Лагранжа для изопериметрических задач (123). 6.2. Необходимые условия высших порядков и достаточные условия (129). Задачи ............... 132 § 7. Задачи со старшими производными ...... 135 7.1. Необходимое условие первого порядка (135). 7.2. _, Необходимые условия высших порядков и достаточные условия (139). Задачи ............... 143 Глава III. Задача Лагранжа и оптимальное управление 147. § 8. Задача Лагранжа ........... 147 8.1. Принцип Лагранжа для задачи Лагранжа (147). Задачи . . . . . . .......... 155 § 9. Ляпуновские задачи .... ..... 157 9.1. Элементарная задача оптимального -управления (157). 9.2. Принцип Лагранжа для ляпуновских задач (158). Задачи . . . , . . ......... 161 . § 10. Задачи оптимального управления ...... 162 10.1. Принцип максимума Понтрягпна (1U2). 10.2. Прин- цип максимума и необходимые условия минимума в классическом вариационном исчислении (180). 10.3. До- статочные условия минимума в классическом вариа- ционном исчислении (187). Задачи ............... 200 4 Глава IV. Сводный отдел и приложения . . . . .205 § 11. Сводный отдел ........... 205 § 12. Разные задачи . . . . ....... 218 12.1. Некоторые теоремы анализа и алгебры (218). 12.2. Некоторые неравенства (222). 12.3. Неравенства для производных (226). 12.4. Геометрические неравен- ства (229). 12.5. Полиномы наилучшего приближения (231). Ответы, указания и решения ......... 234 Литература .............. 285 Список обозначений ............ 286 Предметный указатель ........... 287 ПРЕДИСЛОВИЕ Роль методов оптимизации в экономике, технике, естествознании и самой математике огромна. Поэтому в паше время математическое образование немыслимо без элементов т.еории оптимизации. Теория оптимизации переживает период бурного раз- вития. Всего лишь четверть века тому назад в курсах математики касались лишь двух ее разделов — экстрему- мов функции многих переменных и вариационного ис- числения. За эти годы сформировались новые дисципли- ны — выпуклый анализ, линейное и нелинейное програм- мирование, оптимальное управление. Ныне они находят свое место в курсах высшей математики втузов и универ- ситетов. Создание этих дисциплин должно, без сомнения, внести новое в преподавание как традиционных разделов теории экстремальных задач, так и некоторых частей классического и функционального анализа. Цель этой книги — способствовать тому, чтобы мето- ды теории экстремальных задач заняли достойное место в современном математическом образовании. Мы рассчитываем на то, что задачник будет исполь- зован и в обычных технических вузах, и в технических вузах с углубленным курсом математики, и в универси- тетах. Нам представляется, что при любом уровне пре- подавания математики должно найтись место для элемен- тов теории экстремальных задач. В нашем задачнике представлены важные разделы этой теорий: в § 2 — мате- матическое программирование, в §§ 5—7—классическое вариационное исчисление, в § 10 — оптимальное управле- ние. Эти параграфы являются основными в задачнике. Пункты «Постановка задачи») и «Правило решения» на- званных параграфов, а также примеры, разобранные в них, не требуют для своего понимания никаких специаль- ных знаний, кроме основ математического анализа. Вместе с тем они дают возможность решать большую часть задач этой книги. Таким образом, решать основную массу за- дач можно, опираясь лишь на обычный втузовский курс дифференциального ц интегрального исчисления. 6 В вузах с углубленным изучением математики могут быть использованы теоретические разделы перечислен- ных параграфов, относящиеся к необходимым условиям экстремума. Этот материал мы старались тщательно от- работать методически. При доказательствах используют- ся лишь основополагающие факты классического анали- за, среди которых важнейшее место занимают теоремы об обратной и неявной функции. Все остальное в теоретической части книги рассчита- но на преподавание в университетах. § 1 посвящен ба- зовым понятиям и теоремам функционального анализа, с помощью которых доказываются важнейшие теоремы теории экстремальных задач. На них же основывается выпуклый анализ. Основам выпуклого анализа посвящен § 3. Роль выпуклого анализа в общей теории экстремаль- ных задач, раскрывается в §§ 4, 9. Этот материал можно использовать в специальных курсах. § 8 посвящен общей задаче классического вариационного исчисления — задаче Лаграпжа. Материал § 12 призван показать, как можно исполь- зовать элементы теории экстремалвйых задач в курсах алгебры, анализа, геометрии, а также в различных ис- следованиях теоретического и прикладного характера. Несколько слов об особенностях этой книги. Главная ее особенность состоит в том, что она построена на еди- ной методологии, основывающейся па общем принципе исследования экстремальных задач, восходящем к Лагран- жу. Сам принцип излагается во введении. Освоив его, можно приступать сразу к решению задач любого разде- ла. Сводный отдел (§ 11) как раз и приспособлен для такой методики решения экстремальных задач. Вторая важная особенность состоит в том, что мы стре- мились дать исчерпывающее исследование задач. Поэто- му в задачнике большее, чем обычно, внимание уделено достаточным условиям. И наконец, мы всюду, где это возможно, старались подчеркивать плодотворность новых методов теории — вы- пуклого анализа, выпуклого программирования и опти- мального управления. В задачнике около 700 задач. Практически все они снабжены ответами. Часть задач приведена с решениями. При написании книги нашел отражение опыт препо- давания курсов оптимизации на механико-математиче- ском факультете МГУ. Задачник примыкает к учебному пособию «Оптимальное управление», написанному В. М. Алексеевым, В. М. Тихомировым и С. В. Фоминым (Наука, 1979 г.). Но, в отличие от этого пособия, задач- ник рассчитан на более широкую аудиторию. Поэтому в важнейших частях изложение материала независимо от упомянутого пособия. Работа над задачником едва лишь началась, когда в расцвете своих творческих сил скончался В. М. Алексе- ев, очень много сил отдавший разработке и постановке на механико-математическом факультете лекционных кур- сов и семинарских занятий. Общий замысел этой книги и ее план принадлежат В. М. Тихомирову, теоретические разделы явились плодом нашего совместного труда, в со- ставлении и подборе задач большая доля принадлежит Э. М. Галееву. При работе над разделом «Задачи» мы использовали материалы из архива В. М. Алексеева, «Сборник задач по оптимальному управлению», написанный Э. М. Гале- евым, А. Г. Кушниренко и В. М. Тихомировым (рота- принтное издание МГУ, 1980 г.), сборник из 100 задач, подготовленный В. М. Алексеевым и В. М. Тихомировым для французского издания учебного пособия, материалы некоторых учебников и задачников (из тех, что приведе- ны в списке литературы в разделе «Учебники и учебные пособия») и некоторые ротапринтные издания по оптими- зации, любезно присланные нам их авторами, в частно- сти, пособия Казахского, Киевского и Ярославского уни- верситетов. Мы рады выразить свою благодарность сотрудникам кафедры общих проблем управления механико-матема- тического факультета за большую .и разностороннюю по- мощь, особенно — М. И. Зеликпну, С. В. Конягину и А. В. Фурсикову. Мы благодарны также студентам и ас- пирантам кафедры — настоящим и бывшим — способство- вавшим улучшению книги. И в первую очередь — Ю. А. Александрову, С. А. Аюнцу, А. П. Буслаеву, Динь Зупгу, Б. Лудереру, Г. Г. Магарил-Ильяеву, Е. Б. Пекарю и А. А. Петросяну. Мы будем очень признательны за любые замечания и предложения, относящиеся к замыслу, плану и содер- жанию книги. Э. М. Г-алевв, В. М. Тихомиров Введение ПРИНЦИП ЛАГРАНЖА В ТЕОРИИ ЭКСТРЕМАЛЬНЫХ ЗАДАЧ 0.1. Основные понятия, связанные с экстремальными задачами. С задачами на максимум и минимум мы стал- киваемся еще в школе. Рассмотрим для примера две планиметрические задачи. Задача 1. Найти на данной прямой такую точку, чтобы сумма расстояний от нее до двух заданных точек была минимальна (рис. 1). Задача 2. Вписать в круг прямоугольник наиболь- шей площади (рис. 2). Рис. 1. Рис. 2. Первая задача — это задача на минимум, вторая — на максимум. Слово maximum по латыни означает «наиболь- шее», слово minimum — «наименьшее». Оба эти поня- тия — максимум и минимум, наибольшее и наименьшее — объединяются единым термином экстремум (от латинско- го extremum, означающего «крайнее»). Иногда употреб- ляют слово оптимальный, от латинского optimus, что оз- начает наилучший, совершенный. Таким образом, задачи 1 и 2 — это экстремальные задачи, или задачи оптимиза- ции. Теорию задач на отыскание наибольших и наимень- ших величин называют или теорией экстремальных задач, или теорией оптимизации, или иногда теорией оптималь- ного управления. При употреблении последнего термина обычно предполагается связь задач с практическими при- ложениями. Задача 1 и 2 сформулированы словесно, без формул. Экстремальные задачу, возникающие в естественных нау- ках или на практике, обычно ставятся именно так — сло- весно, в содержательных терминах той области, где дан- ная задача возникла. Чтобы можно было воспользоваться теорией, необходим перевод задач на математический язык. Этот перевод называется формализацией. Одна и та же задача может быть формализована разными спо- собами, и простота решения зачастую сильно зависит от того, насколько удачно она формализована. Осуществим формализации задач 1 и 2. Начнем с за- дачи 1. Направим ось Ох по заданной прямой, а ось Оу проведем через точку А (см. рис. 1). Пусть координаты точек А и В таковы: А == (0, а) и В = (d, b); координата точки С=(х, 0). Тогда мы приходим к следующей зада- че: найти минимум функции }(х) = Уа2 4- х2 + У&2 + (d - xY по всем х <=• R. Формализуем задачу 2. Пусть окружность описывает- ся уравнением ж2 4- у2 =° г2. Направим осп Ох и Оу парал- лельно сторонам прямоугольника и обозначим через (а", у) координаты вершины прямоугольника, лежащей в первом квадранте (см. рис. 2). Тогда площадь прямо- угольника равна 4a'y. Получаем такую задачу: найти мак- симум функции fi)(x, у) == ^ху при условиях f,(x, y)=xгi-yг-r2^0, f,(x, у) == х > О, , f,(x,y)^y^0. Нетрудно убедиться, что условия х ^ 0, у > 0 излиш- ни, и задача найти максимум 4жг/ при условии ж2 +- г/2 == = г2 эквивалентна задаче с неравенствами. Любая формализованная задача устроена аналогично. Она включает в себя следующие элементы: функционал }: Х ->• R {X — область определения функционала /) и ограничение, т. е. подмножество С с: X. Поясним некоторые встретившиеся здесь обозначения и термины: R — это расширенная действительная (веще- ственная) прямая, т. е. совокупность всех действитель- ных чисел, дополненная значениями +°° и —°0; запись F: Х -> Y означает, что отображение F имеет область определения X, a F(x) для каждого элемента а- из Х ле- 1U жит в множестве У; слово «функционал» мы употреб- ляем для отображений в расширенную прямую R. Таким образом, формализовать экстремальную задачу — это зна- чит точно описать ее элементы /, Х и С. Для формализованной задачи употребляется запись }(х)^Ы (sup), xe=C. (з) •X, то Точки ж е С называются допустимыми. Если С задача называется задачей без ограничений. Задачу на максимум всегда можно свести к задаче на минимум, заменив задачу f(x) -> sup, ж е С, задачей f(x) ->- inf, xc=C, где f(x) == —f(x). И, наоборот, задачу на минимум можно аналогичным образом свести к зада- че на максимум. Для определенности в тех случаях, когда формулировки необходимых условий экстремума в зада- чах на минимум и максимум разные, будем выписывать их только для задачи на минимум. Если необходимо ис- следовать обе задачи, то будем писать /(ж) -^ extr, ж е С. Приведем формализованные записи задач 1 и 2. Зада- ча 1 (Х= С ==R): inf. (з,) f(y;)^^ai+xг+nг+(d-x)г Задача 2 (X ~ здесь двумерная плоскость, обознача- емая R2): 4жг/ -> sup; ж2 + г/2 = г2, ж^О, у Э? 0. (зг) Для задачи 2 имеется, как было сказано выше, другая формализация: 4жг/ ->• sup; х2 + у2 = г'. Зада-ча (3i) — задача без ограничений, задача (з;) — с ограничением С = {(ж, у) е y\x2 4- г/2 == г2, х S? О, у ^ 0}, задаваемым в виде равенств и неравенств, задача (за) — с ограничением типа равенства. Допустимая точка х называется абсолютным (или еще говорят глобальным) минимумом (максимумом) в задаче (з), если f(x)^f(x) для любого хеС (соответственно f(x) ^ fCx) для любого х s С). При этом мы пишем х е sabsmins (аЬзшахз). Абсолютный минимум (максимум) задачи будем называть решением задачи. Величина f(x), где х — решение задачи, называется численным значе- нием задачи (иногда для сокращения говорим просто значение задачи). Эту величину будем обозначать 5'э или "Ш1П\"Щ«1/' 11 В задаче 1 абсолютный минимум х, определяющий искомую точку С ==- (х, 0), характеризуется, как извест- но из геометрии, тем, что острые углы, образованные отрезками [АС] и [СВ] с осью Ох, равны («угол па- дения равен углу отражения»); значение задачи Sy^= - Y\a + &)2 + d\ В задаче 2 искомым прямоугольником является квад- рат (попробуйте доказать это геометрически); это соот- ветствует решению ж=г/У2, у==г/^2, Sа^==2r'i. Кроме глобальных экстремумов будем также рассмат- ривать локальные экстремумы. Дадим их строгое опреде- ление. Пусть в задаче (з) Х — нормированное простран- ство. Говорят, что точка х доставляет в (з) локальный минимум (максимум}, и пишут а'е1осюшз (1остахз), если х е С и существует б > 0 такое, что для любой до- пустимой точки х, для которой Ид; — ж11 < 6, выполняется неравенство f(x) ^ f(x) (}(х) ^/(ж)). Иными словами, ес- ли ;ге1осшшз (locmaxa), то существует окрестность ^ точки х такая, что ж е abs min з' (abs max з') в задаче f(x) -> inf (sup), жеСП^. .(з') Теория экстремальных задач дает правила нахожде- ния решений экстремальных задач. В большинстве своем эти правила выделяют некоторое подмножество точек, среди которых должно содержаться решение задачи. Это множество точек, которое мы называем критическим, возможно, несколько шире, чем множество абсолютных и даже локальных экстремумов. После нахождения всех критических точек надо выделить из них решения. Найдем критические точки, локальные и абсолютные экстремумы в следующей задаче. Задача 3. /(aO^.r'^-D-^extr, -i^x^2 (33) (рис. 3). Абсолютный экстремум в задаче может достигаться на концах отрезка или во внутренней точке. Если экстре- мум достигается во внутренней точке, то в этой точке производная должна равняться нулю, т. е. f(x) == 0 ^ 5а-4 - Зж2 = 0 ^ х е {-У375, 0, УЗТб). Таким образом, имеем 5 критических точек: ,i'i==—l, a's =« —УЗ/5, .Гз = 0, Xi = УЗ/5, a-s = 2, из которых точки 12 Рис. 3. а-2, х„ а-4 являются стационарными. Из графика функ- ции / (см. рис. 3) видно, что a"i, х,, е loc min Зз; Хг, Xs^ s loc шах Зз; a-te abs min Зз; х., е abs max За. 0.2. Принцип Лагранжа исследования задач с ограни- чениями. Сущность принципа Лагранжа состоит в редук- ции задач с ограничениями к ряду задач более простой структуры (в большинстве случаев — к задачам без огра- ничений). Прежде чем переходить к описанию этого принципа, покажем на примере задачи 1 (п. 0.1), как следует по- ступать с задачами без .ограничений. Функция / в фор- мализации (3i) из п. 0.1 задачи 1 дифференцируема. Из курса дифференциального исчисления известна теорема Ферма, согласно которой, если точка х доставляет локаль- ный экстремум дифференцируемой функции /, то выпол- нено соотношение f'(x) == 0. Имеем ,' , . х d — х f W= Va2-}-^ 'Y^+(d-x)2' Уравнение / (х) = 0 имеет единственное решение х, при котором как раз и выполнено соотношение «угол падения равен углу отражения» (см. рис. I): —г = , -<=> cos (pi = cos (pa <=»- (г, = (р,. У.а^У Уь2+(d-^)2 . Из сказанного вытекает, что если абсолютный мини- мум существует, то им может быть лишь точка х', другие 13 точки по могут быть даже локальными минимумами. Можно доказать, что в задаче (з,) минимум действитель- но существует. (Доказательство «теоремы существова- ния» решения в (з») осуществляется, как и в большинстве подобных случаев, с помощью теоремы Вейерштрасса — см. далее п. 1.2.1.) Таким образом, задача (з,) решена и х есть ее решение. Все вышесказанное дает повод • наметить план дей- ствий для решения задач без ограничений и при наличии некоторых простейших ограничений (такого рода задачи мы далее называем элементарными). 1. Формализовать задачу. 2. Выписать необходимые условия экстремума. 3. Найти все критические точки. 4. Отыскать решения среди критических точек (на- пример, доказав, что решение существует, и перебрав значения функционала в критических точках) или пока- зать, что решения нет, Принцип Лагранжа — это правило исследования задач с ограничениями путем сведения первоначальной задачи к отысканию и исследованию критических точек неко- торой элементарной задачи. Покажем, в чем состоит принцип Лагранжа, на примере конечномерных задач с ограничениями типа равенств. Рассмотрим задачу (X=R") /о(ж) -> extr; /,(ж) =0, .... /,(ж) == 0, (з) где х = (a-i, ..., Хп\. Здесь ограничение задается системой равенств С = {х <= К"|/,(ж) = 0, г==1, ..., т}. Функционал /о и функции /г, задающие уравнения связи /,(,г') = 0, бу- дем предполагать непрерывно дифференцируемыми (ина- че говоря, такими, что все их частные производные пер- вого порядка непрерывны). Посмотрим, как предлагал решать эту задачу сам Ла- гранж. Он нишет: «Можно высказать следующий общий принцип. Если ищется максимум или минимум некоторой функции многих переменных при условии, что между этими переменными имеется связь, задаваемая одной или несколькими функциями, то нужно прибавить к функции, экстремум которой ищется, функции, задающие уравне- ния связи, умноженные на неопределенные множители, и искать затем максимум или минимум построенной сум- мы, как если бы переменные были независимы. Полу- ченные уравнения, присоединенные к уравнениям связи, послужат для определения всех неизвестных». 14 Воспользуемся правилом Лагранжа (несколько уточ- нив его). Первое, что нужно сделать согласно Лагранжу, это «прибавить к функции, экстремум которой ищется, -функции, задающие уравнения связи, умноженные на неопределенные множители». Составим функцию т S^S{x,^ SVi(^), ^=(^, ....Ц, i=0 которую будем называть функцией Лагранжа. Числа X; называются множителями Лагранжа. Первое уточнение состоит в том, что и функция, экстремум которой ищет- ся, домножепа на неопределенный множитель. Если не сделать этого уточнения, то рецепт Лагранжа может оказаться неверным (см. далее пример 1). При этом в задаче на минимум следует брать ^.о 2s 0, в задаче на мак- симум брать Хо ^ 0. Второе, чте необходимо сделать согласно Лагранжу, это «искать максимум или минимум построенной суммы, как если бы переменные были независимы». По замыслу Лагранжа, следовательно, надо рассмотреть задачу 3(.х, К) -> extr (по х) (з„) (мысленно зафиксировав К). Задача (зэ) проще, чем исходная, так как здесь огра- ничений нет. Она относится к классу элементарных. Не будем искать ее максимумы и минимумы (ибо может ока- заться, что ее максимумы и минимумы не имеют отно- шения к максимуму и минимуму исходной задачи — см. далее пример 2). Поступим несколько иначе, будем искать стационарные точки в задаче (зэ), т. е. напишем для эле- ментарной задачи (зд) необходимое условие минимума или максимума, выражающееся все в той же самой тео- реме Ферма. Согласно этой, теореме должны удовлетво- ряться уравнения 2» {х, К} = 0 ^ 3^, (a-i, .. ., Хц, ?.о, • • •, U = О, (в которых не все множители Лагранжа равны нулю). Полученные га уравнений, дополненные m уравнениями связи, и «послужат для определения всех неизвестных». В самом деле, хотя неизвестных (.с, ?i) на одно больше, чем количество уравнений, но надо учесть то обстоятель- ство, что множители Лагранжа можно умножать на лю- бое число, отличное от нуля. И именно в силу этого чис- 15 ло уравнений равно числу неизвестных. В подобных случаях мы будем говорить о полноте набора условий для определения стационарных точек. Надо иметь в виду, что наибольший интерес имеют те случаи, когда К» ?- О, ибо при \ц == 0 соотношения принципа Лагранжа указы- вают лишь на некоторую вырожденность ограничений (от которой зачастую легко избавиться) и оказываются не связанными с функционалом. Решения полученных урав- нений {3s, =0, i == 1, ..., n, f, {x) == 0, 7 = 1, .. . ,m) и образуют совокупность стационарных точек. Таким образом, для решения задачи (з) следует: 1. Составить функцию Лагранжа: m 2 w. {х). г=о . 2 {X, К) 2. Выписать необходимые условия экстремума: V 9f • (-с) .2^ 1=0 ^(^Д)=о^2^—— дх, 3. Найти стационарные точки, т. е. допустимые точки, являющиеся решениями уравнений п. 2, в которых не все К<, i=0, I, ..., m, равны нулю. При этом бывает полезно рассмотреть отдельно случаи Хо = 0 и Ко •?= 0. Во втором случае можно в задаче на минимум положить Ко равным единице или любой другой положительной константе, в задаче на максимум — равным минус единице или лю- бой другой отрицательной константе. 4. Отыскать решения среди всех стационарных точек или доказать, что решений нет. Описанная процедура и называется принципом Ла- гранжа. Этот принцип применим не только к задаче (з), но и к очень широкому кругу экстремальных задач. Боль- шинство задач из этого задачника можно решить с по- мощью этого принципа. Но при этом важно иметь в виду следующее: а) Принцип Лагранжа применим, вообще говоря, не всегда. В примере 3, приведенном ниже, решение задачи существует, но принцип Лагранжа к нему не приводит. б) Сфера применимости принципа Лаграпжа доста- точно широка. Иногда к задаче нельзя применить имею- щуюся теорему, однако принцип Лагранжа (примененный без обоснования) тем не менее приводит к некоторым точкам, подозрительным на экстремум, из которых мож- но выделить решение. 16 Решим теперь с помощью принципа Лагранжа зада- чу 2 п. 6.1. 1. Рассмотрим более простую формализацию (за) (где множитель'4 при функционале отброшен): ху -> sup; x2 + у2 — г2 = 0. Составим функцию Лагранжа: 2'='k,xlJ-!rK,(x2+yг-rг). 2. Выпишем необходимые условия: 2^ = 0, 2 у = 0 ^ -К,у + 2^х = 0, К,х + 2Kiy == 0. 3. Найдем стационарные точки. Если ^о =0, то Ki ^ О (ибо не все множители Лагранжа равны нулю) и, значит, х == у = 0. Но тогда условие ж2 + у2 == г2 не удовлетворя- ется. Следовательно, в случае Ко == 0 стационарных точек нет. Положим 7.о==—1. Необходимые условия переписы- ваются в виде У-2^х, х=2К,у. Из этих уравнении определяются 4 стационарные точки: i (г/П, г/У2), (г/УГ, -г/У2), (-г/У 2, ?-/У2"), (-г/У 2^ -г/У2)_. 4. Максимальное значение доставляют точки (г/У2, г/У2) и (—г/У2, —г/У2). Соответствующие прямоугольни- ки являются квадратами. Обе точки действительно явля- ются решениями, по это необходимо еще обосновать. Для обоснования можно сослаться на теорему Вейерштрасса о существовании решения в задаче. Можно поступить и по-другому. Пусть х = (/•/У2 4- к), у == (г/У2 4- р) и х2 + + у2 = г2. Тогда к2 + ^2 =—2(су. + р)г/У2 и, следовательно, ху = (г/У2+ к) (г/У2 + ^ == rV2 + ^ - а-/2 - У/2 «S гУ2, т. е. (х\ у) == (г/У2, г/У2) есть решение задачи. Аналогич- ные рассуждения можно провести и для второй точки. Ответ. Решением задачи является квадрат. В общем случае принцип Лагранжа применяется так: 1. Формализовать задачу к виду f(x, и) -> inf; F(x, и) =0, и^ ^/, /: X X ^U -> R, F: XX^U-^Y, где Х и У — нормирован- ные пространства. Это — задача с ограничениями типа равенств, параметризованных некоторым множеством °U. Еще можно сказать, что это задача с ограничениями типа равенств и включений, 2 в, м. Алексеев и др. 17 Составить функцию Лагранжа: 3 == 2'(х, и, у*, А») = Хо/(ж, и) + (у*, F{x, и)>, где у* — элемент сопряженного пространства У*. В функцию Лагранжа ограничения типа включений и <= 'и не входят. 2. Для задач 2'(х, и, у*, Ко) ->- inf (по х), 2 {х, и, у*, /U-^ini, us-^inf выполнено необходимое условие ми- нимума 3?{х, Кц, у*) (теорема Ферма), то S', (х, Хо, у*) == 0 -^ ^о == — У\, ••; ^о == — Уп, ..., где у* == (уь ..., i/n, ...) е ?2, поскольку ^ изоморфно ;2 (КФ, с. 177). Но эти условия противоречивы: либо ^.о ^ 0, тогда у* = . = (?.о, • • ^ ^о. • • •) Ф- г2; либо \о = 0, тогда у* == 0, т. е. оба мно- жителя Лагранжа равны нулю. Здесь Is — пространство всех по- следовательностей х == (.с,, ..., хп, •••), Для которых || х ||== (оо \ 1/2 = Sl-^nll <00' ^ —пространство, сопряженное к h (КФ, n=i / с. 177). Упражнения. В упр. 1—8 привести примеры задач без ограничении об экстремуме бесконечно дифференци- руемых функций одной или двух переменных, в которых выполняются указанные ниже требования. 1. Абсолютные максимум и минимум достигаются в бесконечном числе точек. 2. Функционал ограничен, абсолютный максимум до- стигается, минимум — нет. 2* 19 3. Функционал ограничен, но абсолютные минимум и п максимум не достигаются. 4. Функционал ограничен, имеет критические точки, но абсолютные минимум и максимум не достигаются. 5. Функционал ограничен, имеет локальные максиму- мы и минимумы, но глобальные максимум и минимум не достигаются. 6. Имеется единственный локальный экстремум, не являющийся глобальным. 7. Имеется бесконечное число локальных максимумов, но пет ни одного локального минимума. 8. Ограничение функции, заданной на плоскости, на любую прямую, проходящую через начало координат, xiivieeT в нуле локальный минимум, но вместе с тем нача- ло координат не является точкой локального минимума. 9. Можно ли утверждать, что если функция одной переменной имеет в какой-либо точке локальный мини- мум, то в некоторой достаточно малой окрестности этой точки слева от точки функция убывает, а справа возра- стает? 10. Пусть функция / определена и дифференцируема на R", удовлетворяет условию Ию f(x) == +00 и f'(x) \Х\->00 имеет единственный нуль х. Доказать, что х является точкой абсолютного минимума функции /. 11. Пусть каждый функционал на некотором множе- стве Х достигает своего абсолютного минимума. Доказать, что Х — конечное множество. Формализовать упр. 12—17. 12. Найти кратчайшее расстояние от заданной точки (1, 2) на плоскости до прямой 2xi + Зд-г =1. 13. Найти кратчайшее расстояние от заданной точки в трехмерном пространстве до заданной плоскости. 14. Вписать в круг треугольник с наименьшей сум- мой квадратов сторон. 15. Найти на плоскости точку, сумма расстояний от которой до трех заданных точек минимальна. 16. Разделить заданное положительное число на две части так, чтобы произведение произведения этих частей на их разность было максимальным. 17. Среди полиномов степени п со старшим коэффи- циентом, равным единице, найти полином, имеющий наи- меньшую норму в L,.([—i, 1]). Глава I ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ И ЗАДАЧИ С ОГРАНИЧЕНИЯМИ § 1. ЭЛЕМЕНТЫ ФУНКЦИОНАЛЬНОГО АНАЛИЗА И ДИФФЕРЕНЦИАЛЬНОГО ИСЧИСЛЕНИЯ Многие факты, отмеченные в этом параграфе, содер- жатся в книге АТФ. Поэтому мы будем иногда ограничи- ваться лишь формулировками теорем. 1.1. Нормированные и банаховы пространства. 1.1.1. Основные определения. Линейное пространство Х называется нормированным, если на Х определен функ- ционал II •11: Х -> R, называемый нормой и удовлетворя- ющий условиям: а)||ж[|>0 УжеХ и \\х\\= 0 ^-х == 0; б) || сеж ||== | к II а: ]| УстгВ, Ухе=Х; в) || а-1 + а"2 [К || a"i Ц + | х^ || Va;i, 3-2 e ^- Иногда, чтобы подчеркнуть, что норма задана именно на X, мы пишем II-Ид:. Две нормы в Х ll-lli и II-Иг называ- ются эквивалентными, если существуют такие положи- тельные константы Ci и Сг, что CilMliOMIa^Hi УжеХ. Всякое нормированное пространство становится мет- рическим, если в нем ввести расстояние p(a"i, Хг) == == ll.fi — Хг\\. Полное относительно введенного расстояния пространство называется банаховым пространством. 1.1.2. Примеры банаховых пространств. Пример 1. Конечномерное пространство R", состо- ящее из векторов x==(xi, ..., а-,,), с нормой \х[== 1 " М/2 =- 1 У г21 ^-J Xi I . \i=l / Пример 2. Пространство С(К, R") непрерывных вектор-функций .»•(•): К — R", заданных на компакте К, с нормой 11а-(-)11о == max \x(t)\. t<=K 21 Пример 3. Пространство C''([te, ti], R") г раз непре- рывно дифференцируемых вектор-функций ж(-): [to, ti] ->- -> R", заданных на конечном отрезке [to, ti] <=R^ с нормой 11.ж(.)1].=тах{Ы.)11о, ..., b^Ullo). Пример 4. Пространство /а, состоящее нз последо- 00 вательностей ж = (a-i,,.., ж,,,...), для которых 2 я';2 < 001 г=1 / с» М/2 с нормой, задаваемой формулой || х || == S ж?) » \i=i / 1.1.3. Произведение пространств. Пусть Х и У—нор- мированные пространства. Декартово произведение XXY можно превратить в нормированное пространство, введя норму "(ж, ^llxxr-maxdIA, Ц\\у} (легко проверить, что все аксиомы нормы выполняются). Возможны и другие эквивалентные нормировки (см. далее упр. 8). Отметим очевидное утверждение: декартово произве- дение банаховых пространств банахово. , 1.1.4. Сопряженное пространство и сопряженный опе- ратор. Совокупность Х * всех линейных непрерывных функционалов на Х образует сопряженное к Х простран- ство. Оно является банаховым пространством относитель- но нормы ||ж*|„*= sup <;<•*, ;г>,где <а'*,а-> означает дей- Мд:<1 ствие на х функционала х* (КФ, с. 171). Пространство, сопряженное к конечномерному пространству R", изоморф- но R". Скалярное произведение двух векторов у = =•'(!/!) • •., '/J^R" и x==(x,i, ..., а-„) <= R" представляется • п п в виде суммы <у, а-> == 2 Уг^г Та же сумма 2 Vi^i будет i--l ~ i=l обозначаться нами просто как ух, если у s R" , же R"; при этом следует х считать столбцом, у—строкой (и тог- да ух есть не что иное, как произведение матриц). Пусть Х и Y —• нормированные пространства н Л s ^2'{Х, У)—линейный непрерывный оператор нз Х в У. Тогда можно определить сопряженный оператор Л*: У* ->- -^Х* такой, что <у*, Ах) =-= <Л*у*, ;г> Уж <== Х (КФ, с. 217). Для линейного непрерывного функционала на произве- дении пространств имеет место следующая очевидная Лемма. Всякий функционал Ле(ХХУ)* однознач- но представим в виде <Л, СУ, у)> ^ <х*, х) + <у*, у>, где х* е X* и у* е У*. Угера-жмеммл. 1. Какие из перечисленных ниже функций двух пере- менных и при каких значениях параметров задают нор- му в R2: а) N(x)^(\x^+\x,\p)^/p, р>0; б) N(x) = lan-Ci + а^Хг\ 4- \a^Xi + а^Хг\; в) N(x) == тах {\anXi + ащ-Гг!, lazi-Ci + Я223'21}; г) ^ (ж) = (дц^ + 2ai2.cia:a + a22^)l/2? 2. Доказать, что нормы | х \ = (а^ + а"^) п ИжИс» = =max(|a'i!, |a'J) эквивалентны. 3. Доказать, что если 11 •II —норма в R", то единичный шар в этой норме B=={.rsR" На;!! s^ 1} является замкну- тым выпуклым ограниченным центрально-симметричным множеством, для которого центр — начало координат — является внутренней точкой. 4. Доказать, что если множество В является замкну- тым выпуклым ограниченным центрально-симметричным мпо/кеством в R",. для которого центр — начало коорди- нат — является внутренней точкой, то существует такая норма, при которой В будет единичным шаром. 5. Доказать, что все нормы в R2 эквивалентны. 6. Доказать, что все конечномерные нормированные -пространства банаховы. 7. Построить пример нормированного, но не банахова пространства. 8. Доказать, что .если (Х,\\-\\х) и (У, 11-lly) — нормп- рованные пространства, то Ц х \х + || У НУ п (|| ж Hi- + + Я^Н^)1'2 ~ эквивалентные нормы в XX У. 9. Пусть нормированное пространство Х состоит из непрерывных на отрезке [0, !]• функций с нормой 11;г(-)11 = 1 f = J | x (t) [ dt. Принадлежит ли линейный функционал о (х*, .)"(•)> =хЮ) пространству Х*7 10. Чему равна норма lla-ll, х<=У, если единичный шар задается неравенствами: а) В=« {(ж,, Xi)\ — ffi ^Xi sS 0.1, —Язs^ Xi ^ Яг?; б) В^{(х„х,) -+ —< i.-b^x^b^-b^x^b.^ ?3 11. Привести пример двумерного подпространства С([0, 1]), единичным шаром которого является единич- ный круг (или иначе: рассечь единичный шар простран- ства C(l0, 1]) плоскостью так, чтобы в сечении был круг). 12. Пусть Х = R2. Найти норму пространства, сопря- женного к (X, II •11), если норма в Х задается соотноше- ниями: а) N(x) = (\х,\2 + \х^)1'2; б) N(x)=max(\Xi\, l^l); в) M.^d^+la-^)1^, р>1; г) N(x) = {a^xl + 2а^х^ + а^х^2, "11 > °, ЙцЯ22 — ^12 > 0. 1.2. Некоторые теоремы из геометрии и функциональ- ного анализа. 1.2.1. Теоремы Вейерштрасса о достижении максиму- ма и минимума. Чаще всего будет использована следую- щая основная Теорема Вейерштрасса. Непрерывная функ- ция на непустом ограниченном замкнутом подмножестве конечномерного пространства достигает своих абсолют- ных максимума и минимума (Н, т. 1, с. 235). '• Выделим простое следствие из этой теоремы, которое часто будем использовать. Следствие. Если функция f непрерывна на R" и lim f(x) •= + оо ! lim f (x) == — оо\, то f достигает |эс)->.оо \|х1-»оо ) своего абсолютного минимума (максимума) на любом замкнутом подмножестве R". Напомним, что множество А в метрическом простран- стве называется компактом, если из всякой последова- тельности элементов из А можно выбрать сходящуюся к элементу из А подпоследовательность или (равносильное определение) если из всякого покрытия А открытыми множествами можно выбрать конечное подпокрытие. Ограниченное и замкнутое подмножество конечномерно- го пространства является компактом. Функция /: Х -> R, заданная па метрическом про- странстве X, называется полунепрерывной снизу (сверху), если для любого С множество {x^X\f(x) г$С} ({.re s= X\ f(x) > О) замкнуто. Следующая обобщенная теорема Вейерштрасса приме- нима ко многим задачам вариационного исчисления и оп- тимального управления. 24 Теорема Вейерштрасса (обобщенная). Полу- непрерывная снизу (сверху) функция f, заданная в мет- рическом пространстве X, достигает минимума (максиму- ма) на всяком компакте, содержащемся в X. В частно- сти, f достигает своего минимума (максимума) на всем X, если для некоторого С множество {x\f(x) < С} ({x\f(x)~> ^ С}) непусто и компактно (АТФ, с. 251). Теорема Вейерштрасса и следствие из нее сразу вы- текают из этой обобщенной теоремы. 1.2.2. Теоремы отделимости. Введем понятия отдели- мости и строгой отделимости двух множеств. Пусть А и В — некоторые подмножества нормированного простран- ства X, X* — сопряженное к Х пространство (простран- ство линейных непрерывных па Х функционалов). Гово- рят, что функционал x* s X* разделяет множества А и В, если <ж*,ж>«ж*,;/> УжеАиУуеД. Функционал x* е X* строго разделяет множества А и В, если существует е > 0 такое, что (x*, x) ^ <ж*, г/> — в Ух е А и Vу е. В. В первом случае множества Л н В называются отдели- мыми, во втором случае — строго отделимыми. В конечномерном случае функционал x* можно отож- дествить с вектором из R". Равенство (x*, х> == ?, где x* ^ О, Р е R, определяет в R" гиперплоскость, т. е. ли- нейное многообразие размерности га—1. Поэтому отдели- мость множеств А и В означает существование гиперпло- скости, делящей R" на две части (полупространства), в одной из которых находится множество А, а множество В расположено в другой. Сформулируем теоремы отдели- мости для конечномерного случая. Теорема 1 (первая теорема отделимости в конечно- мерном случае). Пусть А—непустое выпуклое множе- ство в R", не содержащее точки b е R". Тогда точку b можно отделить от множества А. Теорема 2 (вторая теорема отделимости в конеч- номерном случае). Пусть А —непустое замкнутое выпук- лое множество в R" и b — точка, не принадлежащая А. Тогда точку b можно строго отделить от А. Из теоремы Хана — Банаха (КФ, с. 127) выводятся следующие теоремы отделимости в произвольном норми- рованном пространстве. Теорема Г (первая теорема отделимости). Пусть Х — нормированное пространство. Если множества А с Х 25 и В <= Х выпуклы, непусты, не пересекаются между собой и при этом А открыто, то существует ненулевой функци- онал х* s X*, разделяющий множества А и В (КФ, с. 130; АТФ, с. 124). Теорема 2' (вторая теорема отделимости). Пусть Х — нормированное пространство, А с: X — непустое замк- нутое выпуклое подмножество и х е Х — точка, не при- надлежащая А. Тогда найдется ненулевой функционал х*еХ*, строго разделяющий х и А, т. е. такой, что sup <ж*, х> < <х*, ж>. (АТФ, с. 126). жел Упражнения. 1. Привести пример ограниченной непрерывной функ- ции на ограниченном подмножестве прямой, для которой нижняя и верхняя грани не достигаются. 2. Привести пример ограниченной непрерывной функ- ции па замкнутом подмножестве прямой, для которой нижняя и верхняя грани не достигаются. 3. Пусть Х — некоторое подмножество прямой, не яв- ляющееся компактом. Доказать, что найдется такая не- прерывная па Х функция, нижняя грань которой не достигается, 4. Привести пример функции, полунепрерывной снизу, . но не непрерывной. 5. Являются ли компактами следующие множества: а) полуинтервал [а, Ь); б) последовательность точек на прямой Хп ^ 1/га, п = =1,2,...; 00 в) подмножество прямой В= [} [п, п + Ип]; п=1 г) в пространстве ?з эллипсоид Э == \х = {xh}k^i s е= h I .2 ^ < i}7 ft=i J 6. Привести пример ограниченного замкнутого множе- ства, не являющегося компактом. 7. Привести пример нормированного пространства Х и непрерывного функционала /: Х -^ R такого, что f(x) -- -> +оо при 1Ы1 ->- оо, но нижняя грань функционала не достигается. 8. Доказать, что в конечномерном пространстве задача о кратчайшем расстоянии от точки до замкнутого мно- жества всегда имеет решение. 9. Привести пример банахова пространства X, его замкнутого подпространства L и точки х, не принадле- жащей этому подпространству, таких, чю задача о наи- кратчайшем расстоянии от точки до подпространства не имеет решения. 10. Отделить точку (2, 3) от эллипсоида a:V4 +• i/79 == 1. 11. Доказать, что в первой теореме отделимости мож- но взять выпуклые непустые множества А и В такие, что mtA?'0 п hit А ПВ=0. 12. Показать, что в первой теореме отделимости усло- вие открытости отбросить нельзя. 1.3. Леммы. В теории экстремальных задач весьма часто применяются следующие четыре леммы, являющиеся следствиями из теорем отделимости и теоремы Банаха об обратном операторе (КФ, с. 213). 1.3.1. Лемма о нетривиальное™ аннулятора. Напом- ним, что аннулятором А-1- подмножества А линейного пространства Х называется множество тех линейных функционалов I на X, для которых <,l, a;>==0 V.tSA. Отметим, что 4^ всегда содержит 0 е X*. Лемма. Пусть L—замкнутое подпространство нор- мированного пространства X, причем L ~^ X. Тогда анну- лятор L1- содержит ненулевой элемент (АТФ, с. 127). В конечномерном случае эта лемма означает, что если L — собственное подпространство в ft" (т. е. L^R'1), то существуют числа di, ..., вд, не равные одновременно ну- лю и такие, что e^+ ... + Яп^п ^ 0 Уж == (л^, ..., x,i) е G.L. 1.3.2. Лемма о правом обратном операторе. Пусть Х и Y—банаховы пространства, А—непрерывный линейный эпиморфизм Х на Y (А^2'{Х, У), 1шЛ==У). Тогда су- ществуют отображение М: Y -»- X (вообще говоря, нели- нейное и разрывное) и константа С > 0, удовлетворяю- щие условиям; ЛМ==/у, ИМг/11 ^ С\\у\\ для всех у <= Y (АТФ, с. 128). 1.3.3. Лемма о замкнутости образа. Пусть X, Y, Z— банаховы пространства, А: Х -*• Y п В: X-^-Z—линей- ные непрерывные операторы. Равенство Сх == [Ах, Вх) определяет линейный непрерывный оператор С: Х ->- ^ YXZ. Лемм а. Если подпространство Im А замкнуто в Y и подпространство В Кег А замкнуто в Z, то подпростран- ство Im С замкнуто в YXZ (АТФ, с. 129). 27 J (x 2 - хг + хг) dt = j (ж + ^ + -г)2 ^ + (^ (0) + х (0)\\ о о ' ' / а затем вместо x(t) подставить у (at), а > 0. 11.141. При • ге=1 x(t)=.e-'; при п=2 "?(<):= -V/T < —е "^тТТ' ри "Р^Э^ДЬНОМ п функция ^(•) имеет'вид S ".in6 J ' ^e /с.» —корни уравнения А:2" = (— 1)"+1, лежащие ;=i в левой полуплоскости, а <х;п являются решением некоторой сис- темы линейных уравнений. 11.142. Функция х(-) симметрична относительно прямой t= =1/2; на отрезке [0,1/2] эта функция является обратной кфунк- ции f = j г z —' Ч == 1——' й константа k определяется из условий задачи. 11.143. Решения задачи не существует. Если наложить «при- нудительное» ограничение | и \ ss. А, то при Л > я2 решение бу- дет иметь вид - (<- _ _ 0<^<т(Л), У Л cos (У1 (t - 1/2)), т (Л)< <<1 - т (А\, ^ - t' 1 - т (А) < f < 1. Переходя к пределу при Л-^+оо, получим, что численное значе- ние задачи равно четырем и обобщенное управление есть йоб(<) == ==46 (t— 1/2)^ а обобщенным решением будет Xoe(t) == t при 0< ^<^1/2 и ^oe(t) =1—гпри 1/2s^ts^l, ~" «АЛЛ J. А^А П. Л «7 J. ^1. Уч"ебники и учебные пособия АТФ. Алексеев В. М., Тихомиров В. М., Фомин С. В. Оптимальное управление.— М.: Наука, 1979. КФ. Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа.— М.: Наука, 1981. Зор. Зори ч В. А. Математический анализ, часть I.—М.: Нау- ка, 1981. Н. Н и к о л ь с к и и С. М. Курс математического анализа, т. 1 и 2.— М.: Наука, 1975. 1. А х и е з е р Н. И. Вариационное исчисление.— Харьков: Нзд- во Харьк. ун-та, 1981. 2. А х и е з е р Н. И. Лекции по вариационному исчислению.— М.: Наука, 1965. 3. Б л и с с Г. А. Лекции по вариационному исчислению.— М.: ИЛ, 1950. 4. Буслаев В. С. Вариационное исчисление.—Л.: Изд-во ЛГУ, 1980. 5. В а с и л ь е в Ф. П. Лекции по методам решения экстремаль- ных задач.— М.: Изд-во МГУ, 1974. 6. Г а б а с о в Р., Кириллова Ф. М. Методы оптимизации.— Минск: Изд-во БГУ, 1981. 7. Г а с с С. Линейное программирование.— М.: Физматгиз, 1961. 8. Гельфанд И. М., Фомин С. В. Вариационное исчисле- ние.— М.: Физматгиз, 1961. 9. Г ю н т е р Н. М., Кузьмин Р. О. Сборник задач по выс- шей математике, т. 1 и 2.— М.: ГИТТЛ, 1957. 10. Д е м и д о в и ч Б. П. Сборник задач и упражнений по мате- матическому анализу.— М.: Наука, 1968. 11. Еремин II. И., А с .т а ф ь е в Н. Н. Введение в теорию линейного и выпуклого программирования.— М.: Наука, 1976. 12. 3 а с л а в с к и и Ю. Л. Сборник задач по линейному програм- мированию.—М.: Наука,1969. 13. Иоффе А. Д., Тихомиров В. М. Теория экстремаль- ных задач.— М.: Наука, 1974. 14. Краснов М. Л., Макаренко Г. П., Киселев А. И. Вариационное исчисление.— М.: Наука, 1973. 15. Карманов В. Г. Математическое программирование.—М.: Наука, 1975, 16. П о и т р я г и н Л. С. и др. Математическая теория оптималь- ных процессов.—М.: Наука, 1976. 17. Р о к а ф е л л а р Р. Выпуклый анализ.— М.: Мир, 1973. 18. Т и х о м и р о в В. М. Некоторые вопросы теории приближе- ний,—М.: Изд-во МГУ, 1976. 19. Х а р д и Г. Г., Л и т т л ь в у д Дж. Е., П о л и а Г. Неравен- ства.—М.: ИЛ, 1948. 20. Э к л а н д И.. Темам Р. Выпуклый анализ и вариационные проблемы.— М.: Мир, 1979. 21. Я н г Л. Лекции по вариационному исчислению и теории опти- мального управления.— М.: Мир, 1974. 285 СПИСОК ОБОЗНАЧЕНИЙ {х\Р(х}} — множество элементов х,_ обладающих свойст- вом Р(х) х (•) — обозначение, которым подчеркивается, что ;;•(•) являет- ся элементом функционального пространства FoG—суперпозиция отображений G и F: (FoG)(x) ==F(G(x)) R = R U {—oo, +oo}—расширенная числовая прямая R!L— неотрицательный ортант eR"|^>o,^=i, ...,п) Б [х, г). == {у [|[ х— у || Е$ г] — открытый шар с центром х ра- диуса г о В{х, г) == [у \\\х — у 11 sg: r} — открытый шар с центром а; ра-' диуса г T^M^T'^M')— множество касательных (односторонних каса- тельных) векторов к множеству М в точке х X* — пространство, сопряженное с Х (х*, а") — значение линейного функционала х* на элементе х А1- == {х* е X* | (х*, -с) == 0 у3' е А} — аннулятор множе- ства А 3 (X, Y) — пространство линейных непрерывных отображений пространства Х в пространство У; отображения из S'(R", R"1) могут отождествляться, с матрицами этих отображений I — единичный оператор (матрица) Л* — оператор, сопряженный с оператором Л, <Л*у*, -с) == = <г/*, Лж> 'U е О (X) — множество 'U открыто в пространстве Х °и е О (х, X) — множество 'U, содержащее элемент х, откры- то в Х С ([to, ti})—пространство непрерывных функций на отрезке [to, ti] с нормой Я.с(-)11о= юах I ^(t} I <еГ'о,<,] С'(.[to, ti}) —пространство г раз непрерывно дифференцируе- мых функций на отрезке [to, ti} с нормой [|.с(-)1|г == шах {II .с MIL ^(•)11о, .... 11;^)(-)11о} КС ([to, ti]) — пространство кусочно-непрерывных на отрезке [to, ti} функций, т. е. имеющих не более конечного числа разрывов первого рода (в точках разрывов существуют конечные пределы слева и справа) 6F(x, •) —вариация по Лагранжу отображения F в точке х F е О6 (х) — отображение F дифференцируемо по Фреше Л- раз (k> i) ' F e SD (ж) — отображение F строго дифференцируемо по Фре- ше в точке х 9F (х) — субдифференппал функции F в точке х х е abs min (abs max, abs extr) — х доставляет абсолютный ми- нимум (максимум, экстремум) в задаче х е 1ос min (1ос шах, 1ос extr) — S доставляет локальный мини- мум (максимум, экстремум) в задаче 5з — численное значение задачи (з) (Р) —задача,, приведенная с решением ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Аннулятор 27 Вариация по Лагранжу 29 Вектор касательный 34 — односторонний (полукаса- тельный) 34 Дифференцируемость по Гато 29 — по Фреше 28 — строгая 29 Задача Аполлония 56 — Архимеда 56 — Больца 84 — выпуклого программирова- ния 68 — двойственная 71 — Дидоны 134, 162 — Евклида 54 — изопериметрическая 123 — Кеплера 54 — Лаграыжа 147 — линейного программирования 73 — ляпуновокая 159 — Ньютона аэродинамическая 204 — о быстродействии 177 — оптимального управления '157 — о центре тяжести 229 — простейшая классического вариационного исчисления 90 — со старшими производными 135 — с подвижными концами 97 — Тартальи 54 — Ферма 54 — Шеннона 162 Иголка элементарная 167 Игольчатая вариация управле- ния 163 — — функции 163 Интеграл импульса 93 — энергии 93 Интегрант квазирегулярный 104 —— регулярный 104 Конволюция 61 Конус сопряженный 59 Критерий Сильвестра 50, 219 Лагранжиан 124 Лемма Дюбуа — Реймона 87 — — — усиленная 136 '— об аннуляторе ядра регуляр- ного оператора 27 — об игольчатой вариации 171 — о замкнутости образа 27 — о минимаксе 78 w- о нетривиальности аннулято- ра 27 — о правом обратном операторе 27 — о приращении функционала 168 — о сопряженном конусе 76 — о центрированной системе 169 — Хоффмана 77 Максимум (минимум) 9 — абсолютный 11 — локальный 12 — сильный '90 — слабый 84 Метод Ньютона 52 — — модифицированный 53 Множество выпуклое 58 — эффективное 58 Множители Лагранжа 15 Падграфик 58 Неравенство Адамара 229 — Бернштейна 226 — Вейля 222 — Гельдера 57 — Гильберта 216 — для производных на полу- прямой 226 — для средних степенных 57 — Иенсена 65 — Карлсона 162 — Маркова 226 — между средним арифметиче- ским и средним геометриче- ским 57 287 Неравенство Минковского 57 — Харди 217 — Харди — Литтльвуда — По- лиа 218 — Юнга 59 Оболочка выпуклая, коническая 58 Оператор пнволютивный 60 — регулярный 28 — сопряженный 22 Пакет иголок 170 Поле экстремалей 107 — — центральное 107 Полиномы Лежандра 54, 231 — Чебышева 231 — Чебышева второго рода 231 Поляра 59 Преобразование Лежандра — Юнга — Фенхеля 59 Принцип Лагранжа 12, 16 — максимум Понтрягина 165 Субдифференциал 59 Теорема Боголюбова 106 — Вейерштрасса 24 — двойственности 72, 160 — Дубовицкого — Милютина 61 — Куна — Таккера 69 — Моро — Рокафеллара 61 — об альтернансе 232 — об очистке 61 — основная алгебры 218 — отделимости вторая 25 — — первая 25 Теорема существования 198 — Фенхеля — Моро 60 — Ферма 39 — Эйлера — Лагранжа 150 — Якоби 140 Терминант 84 Точки допустимые 11 — критические 12 — сопряженные 104 —'стационарные 13 Уравнение Гамильтона — Якоби 110 — Эйлера 85 — Эйлера — Пуассона 136 Условие дополняющей нежест- кости 40 — Лежандра 103 — неотрицательности 40 — Слейтера 69 — стационарности 89 — трансверсальности 85 — Якоби 104 Формула Вейерштрасса основ- ная 109 Функция Вейерштрасса 108- — выпуклая 59 — — однородная 58 — замкнутая 59 — индикаторная 60 — Лагранжа 15 — Минковского 60 — наклона поля 107 — опорная 60 — полунепрерывная снизу 24 — собственная 58 5-|функция 107 В.М.АЛЕКСЕЕВ Э. М. ГАЛЕЕВ В. М. ТИХОМИРОВ СБОРНИК ЗАДАЧ по ОПТИМИЗАЦИИ ТЕОРИЯ • ПРИМЕРЫ • ЗАДАЧИ Допущено Министерством высшего и среднего образования СССР в -качестве учебного''пособия для студентов математических специальностей высших учебных заведений МОСКВА «НАУКА» ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ t 98 4