В.М. Алексеев, Э.М. Галеев, В.М. Тихомиров, Сборник задач по оптимизации (теория, примеры, задачи) (1155771), страница 2
Текст из файла (страница 2)
И. Зеликину, С. В. Конягину и А. В. Фурсикову. Мы благодарны также студентам и аспирантам кафедры — настоящим и бывшим — способство-. вавшим улучшению книги. И в первую очередь— Ю. А. Александрову, С. А. Аюнцу, А. П. Буслаеву, Динь Зунгу, Б. Лудереру, Г. Г. Магарил-Ильяеву, Е, Б, Пекарю и А. А.
Петросяну, Мы будем очень признательны за любые замечания и предложения, относящиеся к замыслу, плану и содержани|о книги. Э. М. Галеев, В. ЛХ. Тихомиров Введение 11РИНЦИП ЛАГРАНЖА В ТЕОРИИ ЭКСТРЕМАЛЬНЫХ ЗАДАЧ 0.1. Основные понятия, связанные с зкстремальнымп задачами. С задачами на максимум и минимум мы сталкиваемся еще в школе. Рассмотрим для примера дзе планиметрические задачи. 3 а д а ч а 1.
Найти на данной прямой такую точку, чтобы сумма расстояний от нее до двух заданных точек была минимальна (рис. $). 3 а д а ч а 2. Вписать в круг прямоугольник наибольшей площади (рис. 2). вы,ь~ Рис. 2. Ряс. 1. Первая задача — это задача на минимум, вторая — на максимум. Слово тахиппт по латыни означает «наибольшее», слово ш1п1шшп — «наименьшее».
Оба эти понятия — максимум и минимум, наибольшее и наименьшее— объединяются единым термином экстремум (от латинского ех1гетпт, означающего «крайнее»). Иногда употребляют слово оптимальный, от латинского орМпшз, что означает наилучший, совершенный. Таким образом, задачи $ и 2 — это экстремальные задачи, или задачи оптимизации. Теорию задач на отыскание наибольших и наименьших величин называют или теорией экстремальных задач, или теорией оптимизации, или иногда теорией оптимального управления. При употреблении последнего термина обычно предполагается связь задач с практическими приложениями.
Задачи 1 и 2 сформулированы словесно, без формул. Экстремальные задачи, возникающие в естественных науках или на практике, обычно ставятся именно так — словесно, в содержательных терминах той области, где данная задача возникла. Чтобы можно было воспользоваться теорией, необходим перевод задач на математический язык. Этот перевод называется формализацией. Одна и та же задача может быть формализована разными способами, и простота решения зачастую сильно зависит от того, насколько удачно она формализована. Осуществим формализации задач 1 и 2. Начнем с задачи 1. Направим ось Ох по заданной прямой, а ось Оу проведем через точку А (см.
рис. 4). Пусть координаты точек А и В таковы: А = (О, а) и В = Ы, Ь); координата точки С=(х, 0). Тогда мы приходим к следующей задаче: найти минимум функции ~(х) = Уа'+ х'+ УЬ'+ Ы вЂ” х)' по всем хвзН. Формализуем задачу 2. Пусть окружность описывается уравнением х'+ у' г'.
Направим оси Ох и Оу параллельно сторонам прямоугольника и обозначим через (х, у) координаты вершины прямоугольника, лежащеи в первом квадранте (см. рис. 2), Тогда площадь прямоугольника равна 4ху. Получаем такую задачу: найти максимум функции ~,(х, у) =4ху при условиях ~,(х, у) =х' ~-у' — г'=О, Дх, у) =х=-О, ~,(х, у) = у~О.
Нетрудно убедиться, что условия х ~ О, у ~ 0 излишни, и задача найти максимум 4ху при условии х'+ у'= = г' эквивалентна задаче с неравенствами. Любая формализованная задача устроена аналогично. Она включает в себя следующие элементы: функционал )': Х-»- Й (Х вЂ” область определения функционала ~) и ограничение, т. е. подмножество Сс=Х, Поясним некоторые встретившиеся здесь обозначения и термины: Н вЂ” это расширенная действительная (вещественная) прямая, т. е. совокупность всех действительных чисел, дополненная значениями + и —; запись Г: Х вЂ” У означает, что отображение Е имеет область определения Х, а Г(х) для каждого элемента х иэ Х ле- ~0 жпт в множестве У; слово «функционал» мы употребляем для отображепнй в расширенную прямую Й.
Таким образом, формализовать экстремальную задачу — это значит точно описать ее элементы ~, Х и С. Для формализованнои задачи употребляется запись 1(х) — 1п1 (зпр), х «= С. (з) Точки х «з С называются допустимыми, Если С = Х, то задача называется задачей без ограничений. Задачу на максимум всегда можно свести к задаче на минимум, заменив задачу 1(х) — зпр, х я С, задачеи )'(х) — 1пГ, хя С, где ~(х) = — ~(х), И, наоборот, задачу на минимум можно аналогичным образом свести к задаче на максимум. Для определенности в тех случаях, когда формулировки необходимых условий экстремума в задачах на минимум и максимум разные, будем выписывать их только для задачи на минимум. Если необходимо исследовать обе задачи, то будем писать ~(х) — ех1г, хяС.
Приведем формализованные записи задач 1 и 2. Задача 1 (Х=С=Н): ~(х) = уа'+ х'+ )'б'+ Ы вЂ” х)' — пй. (з,) Задача 2 (Х вЂ” здесь двумерная плоскость, обозначаемая В'): 4ху- зпр; х'+ у'=т', хъ0, у~0. (з,) Для задачи 2 имеется, как было сказано выше, другая формализация: 4ху — зпр; х'+ у' = т'. (з,) Задача (з1) — задача без ограничений, задача (з,)— с ограничением С=((х,у) яй'!х'+ у'= т', х ~0, у ~0), / '~ задаваемым в виде равенств и неравенств, задача (,з»)— с ограничением типа равенства. Допустимая точка х называется абсолютным (или еще говорят глобальным) минимумом (максимумом) в задаче (з), если ~(х) ~ 1(х) для любого х ~ С (соответственно 1(х) <~(х) для любого х<з-'С), При этом мы пишем хе-= «е аЪзшйпз (аЪз шах з).
Абсолютный минимум (максимум) задачи будем называть решением задачи. Величина ~(х), ° ~ где х — решение задачи, называется численным значением задачи (иногда для сокращения говорим просто значение задачи). Эту величину будем обозначать Яз илп 8в1п (8ват) ° В задаче 1 абсолютный минимум х, определяющий искомую точку С = (х, 0), характеризуется, как известно из геометэии, тем, что острые углы, образованные отрезками 1АС1 и 1СВ1 с осью Ох, равны («угол падения равен углу отражения»); значение задачи Ю~ = = ~(а+ Ь)»+ Ы'. В задаче 2 искомым прямоугольником является квадрат (попробуйте доказать это геометрически); это соответствует решению х = г/У2, у = г/У2, Б,,= 2г'.
Кроме глобальных экстремумов будем также рассматривать локальные экстремумы. Дадим их строгое определение. Пусть в задаче (з) Х вЂ” нормированное пространство. Говорят, что точка т доставляет в (з) локальный минимум (максимум), и пишут х«з1осш(пз (1остахз), если х «з С и существует б = 0 такое, что для любой допустимой точки х, для которой зх — хц (д, выполняется неравенство ~(х) > /Й) (/(х) ~ /(х)). Иными словами, если х «з 1ос ш(п з (1ос шах з), то существует окрестность Я точки х такая, что тя аЬз пппз' (аЬз шахз') в задаче /(х) - 1п1 (зпр), х«зСПЖ (з') Теория экстремальных задач дает правила нахождения решений экстремальных задач.
В большинстве своем эти правила выделяют некоторое подмножество точек, среди которых должно содержаться решение задачи. Это множество точек, которое мы называем критическим, возможно, несколько шире, чем множество абсолютных и даже локальных экстремумов. После нахождения всех критических точек надо выделить из них решения. Найдем критические точки, локальные и абсолютные экстремумы в следующей задаче. Задача 3. ~(х) =х'(х' — 1) ех(г, — 1 =х ='2 (з,) (рис. 3).
Абсолютныи экстремум ' в задаче может достигаться па концах отрезка или во внутренпей точке. Если экстремум достигается во внутренней точке, то в этой точке производная должна равняться нулю, т. е. ~'Ь) 0 с=~ 5х' — Зх' = 0 ~=». х «з ( — УЗ/5, О, УЗ/5). Таким образом, имеем 5 критических точек: х, = -1, х, — — УЗ/5, х, =О, х, = УЗ/5, х, =2, из которых точки 12 х„х„х, являются стационарными. Из графика функЦии ) (см. Рис. 3) ВиДно, что хо хг, е- =1ос Й1п зз' хз~ х~ ~-= ~1осшахз,; х,~ аЬВ ш)пз,; х,~ аЬВ шахз,.
0.2. Принцип Лагранжа исследования задач с ограничениями. Сущность принципа Лагранжа состоит в редукции задач с ограничениями к ряду задач более простой структуры (в большинстве случаев — к задачам без ограничений). Прежде чем переходить к описанию этого принципа, покажем на примере задачи 1 (п. 0.1), как следует поступать с задачами без ограничений. Функция 1 в формализации (з,) из п. ОЛ задачи 1 дифференцируема. Из курса дифференциального исчисления известна теорема Ферма, согласно которой, если точка х доставляет локальный экстремум дифференцируемой функцпи ~, то выполнено соотношение ~ (х) = О. Имеем ~/ь2 1,~ )х / Уравнение ~ (х) = О имеет единственное решение х, при котором как раз и выполнено соотношение «угол падения равен углу отражения» 1см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
