Э.М. Галеев, В.М. Тихомиров - Оптимизация - теория, примеры, задачи (2000) (1125255), страница 46
Текст из файла (страница 46)
В 1970 году Кли и Минти построили примеры, показывающие, что симплекс-метод в некоторых ситуациях требует экспоненциального числа шагов. Многие математики (в том числе и сам Данциг) не раз говорили, что воспринимают, как чудо пятидесятилетнюю триумфальную службу» симплекс-метода в бесчисленных 278 Глава 6. Общая теория экстремальных задач исследованиях прикладного характера (Данциг сказал: «Т1зе пешепдоца ровсег оу Фе эппр!ех шегпос! Ы а сопжап! аоцзпзе го ше»).
И лишь недавно были построены полнномнальные алгоритмы, сопоставимые с симлекс-методом по эффективности. Важный шаг был сделан Хачияном, который применил к решению задач линейного программирования метод зллипсондов. Но метод Хачияна на практике уступал симплекс-методу. Однако вскоре появились новые методы, которые во многих случаях оказались предпочтительнее симплекс-метода. Один из таких методов, получивших широкое распространение, стал метод, изобретенный индийским математиком Кармаркаром. Но потом выяснилось, что за много лет до работы Кармаркара ту же основную идею построения алгоритма, основанного на методе штрафа, выдвинул российский математик Дикин. Нет возможности здесь описать алгоритм Кармаркара — Дикнна (обо всех затронутых проблемах выпуклой оптимизации см.
Шор (1989)). Алгоритмы рещеяиа задач классического вариаииеиного исчисления и оптимального управления Одними из важнейших при решении задач вариационного исчисления являются методы, редуцирующие задачу к конечномерной. Впервые такой метод применил, как было уже сказано, Лейбниц, заменивший искомую кривую ломаной. Затем эту же идею разрабатывал Эйлер (метод ломаных Эйлера). Метод Бубнова — Галеркииа Необходимость решения задач вариационного исчисления, связанных с инженерными проблемами, стала особенно актуальной в начале века.
Среди конкретных алгоритмов, реализующих идею редукции бесконечномерной задачи к конечномерной, выделяется метод Ритца (1908), развитый Галеркиным (!915). Поясним суть метолов Ритца и Галеркина на примере простейшей (вообще говоря — многомерной) задачи. Пусть требуется найти минимум функционала ) Х (1, х(!), й(!)) !!1, при условии, что на границе области П о функция х(.) принимает заданные значения. Для нахождения функции близкой к минимальной, Ритц предложил рассматривать семейство фУнкций, зависащих от нескольких паРаметРов Ф(за), а = (б!,...,ая) такое, что при всех значениях параметра в граничные условия удовлетворяются.
Галеркин, конкретизируя эту идею, для решения уравнения Эйлера рассматриваемой здаачи, предлагал выбирать некоторое линейное пространство функций. Приведем пример применения метода Галеркина нахождения минимума квадратичной задачи классического вариационного уравнения, приводящее к приближенному решению уравнения Штурма — Лиувилля. д 5. Придел!ения обще» те!Янаи к решению коикречимх задач 279 Рассмотрим залачу: ( )) ( (йэ(!) 9(!)гсэ(!)) ги + 2((!)я(!) г!! — шш; о я(0) =а(Т) =0 (9) О) Уравнение Эйлера в этой задаче — одно из самых популярных в матема- тике и ее приложениях — уравнение Штурма — Лиувилля: й+ дх = /, я(0) = х(Т) = О.
Метод Галеркина (который конкретизировал идею Бубнова) состоит в том, что задавшись системой (сй())й !* сй() Е С ((О,!)) линейно- независимых функций, удовлетворяющих йулевым условиям на концах, ищем решение, минимизирующее функцию многих переменных: ш(х) = д(2 ' яйсй()), х = (х!,...,х„). Подставляя выражение аа() = 2, хйсй() й=! й=! в минимизируемый интеграл, получаем: с а .У(я ()) = ~~! ай!хйх! + 2~ Ьйхй, й,!= ! й=! т т где а = и = )'(гй(!)уг(!) — 9ЯдйЯ~гЯ) !!г, ьй — — э' 1(!)сй(!)ги. задача о свелась к конечномерной квадратичной задаче, которая обсуждалась выше. Упражнение. Вычислить по методу Галеркина приближенное решение рассматриваемой задачи при Т = д(!) = У(!) = 1, яэ(Ф) = !(1-Ю)(а!+аэ ).
ф 5. Приложения обшей теории к решению конкретных задач Ыатсматнкн прошлого сюдстнв со страстным рвением отдавались рсшснню отдсдьных трудных задач. Я напомню только поставаснную Иоганном бсрнудвн шддчу о браанстоаронс. Гнаьбсрт Сасдусг поставнть парад собоа падь нзмсвать способ рсвшннв асса швач...
овнам н пр!пон простым способом. ,!Ьыанбср О роли отдельных задач в истории нашей науки замечательно сказал Гильберт в словах, приведенных нами выше (и прн этом в качестве примера он привел задачу на экстремум!). Существует огромное число точно Глава 6. Общая теория экстремальных задач 280 решенных экстремальных задач — в классическом анализе, геометрии, алгебре... С точно решенными задачами на экстремум связаны имена многих крупнейших математиков всех времен. В этом параграфе приводится свыше сорока задач, поставленных и решенных в разные времена, начиная с классической изопериметрической задачи, обсуждавшейся в 1У веке до нашей эры (решение ее было предложено Зенодором) и кончая некоторыми задачами, ставшими актуальными в самые последние годы.
Решения этих задач связаны с именами Архимеда, Евклила, Ферма, Кеплера, Ньютона, Лейбница, братьев Бернулли, Лагранжа, Эйлера, Чебышева, Бернштейна, Гильберта, Ландау, Адамара, Юнга, Блашке, Харди, Литглвула, Пойа, Наля, Колмогорова, Вейля и многих других. Нам представляется важным подчеркнуть, что все эти задачи (как и подавляющее большинство других, которые могут быть решены «явно») допускают решения, полученные по единаиу методу, обсугкдавшемуся в этой части — методу Лагранжа.
А именно, всюду можно поступать единообразно и «просто» (как, собственно, и рекомендовал поступать Даламбер). Сначала следует формализовать задачу, затем применять принцип Лагранжа, далее решать (или исслеловать) получающиеся уравнения. В итоге нахолятся функции. подозреваемые на экстремум, и наконец (с помощью достаточных условий) слелует доказывать, что получено именно решение задачи. Не все задачи решаются здесь с полной подробностью, во многих случаях мы просто ссылаемся на решения, детально разобранные в книгах [ИТ[, [АТФ[, [АГГ[, [Т[, [ГТ[ или статье [МИ-Т], (а в ряде случаев— в первой части этой книги).
Этот параграф книги не предназначен лля легкого чтения. Почти каждая из предлагаемых задач — это отдельная тема, которая далеко не исчерпывается ее решением. Сами же решения могут слукить комментарием к методу Лагранжа, к полезности изучения теории экстремума, к истории математики, и могут быть использованы на лекциях, семинарских занятиях, а также на занятиях различных математических кружков Но вместе с тем большинство задач были в той или иной мере опробованы на семинарских занятиях или кружках (в частности, задачи 2, 6, 42 и 46 были прелложены студентам для решения вместо сдачи экзамена, они справились с заданием, и их решения были использованы в этом параграфе), так что все задачи б 5 интересны и доступны. Старинные задачи и ях обобщения 1. Классическая изоперимегрическая задача Среди плоских кривых заданной длины найти кривую, охватывающую наибольшую площадь.
Зто — одна из стариннейших задач на экстремум. Считается, что ответ в этой задаче был известен Аристотелю (1У век до н. э.). Об истории $ 5. Приложения общей теории к решению конкретны зада х ч 281 этой задачи и различных решениях ее, не опирающихся на теорию экс[Т[ ( ассказ второй). Решение обобщенной залачи о в книге АТФ, гтак называе ( а ываемой задачи Чаплыгина) полробно изложено в книге [А , в классической с.!07 †!10[. Как известно, начиная с !У в. до нашей эры, в класси изопериметрической задаче известен такой Ответ: решением задачи является круг.
2. Задача Архимела Среди шаровых сегментов в К" с заданным обьвмом (или — в дву- мерном случае — заданной площадью) боковой поверхности найти сегмент кааба«»щего обьема. При и = 3 эта задача была решена Архимедом (жившим в 1[1 в. до н.э.) в его сочинении «О шаре и цилиндре». Элементарное решение задачи Архимеда, основанное на идеях Архим да е см. в книге [Т, с. 31, 34[.
Предлагаемое ниже решение и-мерного варианта задачи получено сту- дентом мех-мата МГУ В. Тимориным. Шаровой сегмент п-мерного шара в " = х = х;бы, з пг К, 1 « ' 12 зададим в сферических координатах системой неравенств [[х[[ < Д, х„> Вз!пВ, где [[х[[ — евклидова длина век— "- < В < "-. Тогда, как известно, объем этого сегмента тора х, равен а„, «г, а Я"1 (В), а объем боковой поверхности этого сегмента равен «/2 (п — 1)а„|В" '1„2(В), где 1н(В) = [ соз" !од!о, а„— обьем и-мерного в единичного шара. !. Формилизацил: К«1„(В) гпах; К" '1„2(В) = !. Это конечномерная гладкая задача. Решение ее существует и принцип Лагранжа применим, Условие стационарности приводит к уравнениям; п1«1»(В) — Л(п !)1 -2(В), ««соз В = Л~ 2 откупа приходим к равенству (и — 1) соззВ1„2(В) = п1„(В) (1), 3.
Исследование. Если воспользоваться известной рекуррентной формулой -япВ сов В и — ! 1„(В) = + — 1„,(В), получаем: ВпВсоз" В = (и — 1)з!и В1„2(В). Это уравнение допускает очевидное решение В = О, Других решений нет. Действительно, любое другое решение удовлетворяло бы равенству ыпВ1„2,, = ' „, время, как, восп , воспользовавшись монотонностью синуса на отрезке [- -„-,], 282 получаем: »! ,у«(у( )) = ~й ~/! +1Г2 дх -'«ппп (3) у(х) = ~~у )х — х;! — ппп. (5) х = С~ + Су з( нп т дт, у = — —, 1 а о р = Сз!пт 1, Глава 6. О62цая теория экстремальяых задач т 2 соз" 'б Х„з(б)з!пб = / соо" ~уз!пбд92 ° / »-2„п и†! в г Еше надо проверить граничную точку б = -» и убедиться, что обье ша ра меньше объема полушара той же боковой поверхности. 2 м В частности стности, есои и = 3, то «из всех сфг!ичгских сеснгнтав, ограниченных равнмми наверююсними, наибольшим будет полушарие» (Архнмел, Сочинения.
Мл Физматлит, 1962). 3. Задача о брахистохроне и сходвме с ией В 'вертикальной плоскости даны две точки А и В. Определить путь АМВ, сиускаясв ио котороыу иад влиянием силы пи»кисти, тело М, начав двигаться из точки А. дойдет да точки В в кротчайаея аргмя». Питируется по статье И. Бернулли «Задача, к решению которой приглашаются математики», Асса Ешб!!огню, июнь 1696 г. Она обсуждалась 81 гл.3. Исто рня этой задачи, ее формализация и решение «в духе Лейбница читатель найдет в книгах [Т] (рассказ седьмой) и [АТФ, Обобщим несколько задачу И.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
