Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 94
Текст из файла (страница 94)
Применить метод барьерных фуннций к задачам: а) 7(п) = х + у -+ш1; в ~а 77 (и = (х, у) зи Ез: у~(о) = хз — у < О, уз(в) = — х ( О); б) 1(о) = у -+ !п1; и ш У = (в = (х, у) ш Е; у(в) = з!и х + х — у < 0); в) Цп) (и — 1)з-+ !п1; и ~и 77 = (в зи Е ! у(в) = — в — 1 ( 0); г) к задачам иа упражнения 14А; д) к задачам ив примеров 2.2.2 и 2.2.4, считая, что множество 7 совка. Лает с границей множества К 2. Сформулировать и доказать аналог теоремы 14.7 для описанных выше вариантов метода барьерных функций.
$16. Метод нагруженных функций 1. Будем рассматривать задачу 1(и) — !п1; (7 = (и зи Е": и еи 17„ Е(и)(0, 1=1, ..., ги; д(и)=0, (=т+1, ..., г). (Ц В методе нагруженных функций исходная задача (Ц сво. дится к аадачам минимизации некоторых вспомогательных функ. ций на множестве У, и к поиску минимального решения (корня) некоторого уравнения.
Но, в отличие от метода штрафных функций, в нем нет неограниченно возрастающих козффпциен тов, аналогичных штрафным козффицнентам, и кроме того, метод нагруженных функций применим к более широкому классу задач, чем метод модифицированных функций Лагранжа. Введем семейство функций Ф(и, !)=Ышах(з'(и) — 1; 0)( з+МР(и), ишь (2) зависящее от скалярного параметра 1, — се (1(, где ~п 3 Р(и) = ~з (шах (дз(и); 01) ~+,з, )Е!(и)( 1, величины р< ~ 1, ! = 1, ..., г, Е ) О, М > 0 фиксированы и являются параметрами метода.
Положим р(!) = тп1 Ф(и, !). (4) 1нпо $1б! метОд ИАггуженных Функций Поскольку Ф(и, ))>0 при всех ) и пш 1Х,, то р())> 0 при любом й Предположим, что в задаче (1) Хз) — оо, ПзФ 8 Возьмем проиавольную точку и„ ее 1Х . Тогда Р(из) = 0 и Ф (из, Хз) = О. Следовательно, р(Х ) = 0„ т. е.
Хз является корнем уравнения р(б) О. (5) С другой стороны, Ф(и, б)>0 при всех иби 1Х, и всех 8 <Х„„ и поэтому можно ожидать, что для широкого класса задач будет выполняться неравенство р()))0 при всех 1<Х„. Если это в самом деле так, то задача поиска Хэ сведется к поиску мини- мального корня уравнения (5). Такое сведение задачи миними- зации привлекательно тем, что для поиска минимального корня уравнения (5) с одной неизвестной могут быть использованы такие широко известные методы решения уравнений, как мето- ды деления отрезка пополам, простой итерации и т.п. (4, 39, 54].
Основная идея метода нагруженных функций описана. Заметим, что в этом методе могут быть использованы и дру- гие конструкции функции Ф(и, )), отличные от (2). Наприбгер, можпо принять Ф(и,б) = Ь~Х(и) — $( б+ МР(и), не- :1Хб, — со <) < со, (6) где функция Р(и) взята иа (3), Ь) О, М) О, р1> 1. Повторив предыдущие рассуждения для функции р(б), определяемой из условий (4), (6), можно показать, что здесь также р(Хэ) = О, и высказать гипотезу о том, что для п1нрокого класса задач (1) число Хб, по-видимому, будет минимальным корнем уравнения (5) 2.
Прежде чем переходить к формулировке условий, прн ко- торых высказанная гипотеза в самом деле будет справедлива, рассмотрим примеры. Во всех примерах ограничимся рассмотре- нием функций Ф(и, б) из (2) и (6) при Ь =М = р, = ... = р. 1. Пример 1. Пусть Х(п)= -и; 1Х= ЬбиЕ11 д(и)= и < 0), Здесь Хз = О, и„= О. Функция (2) здесь имеет вид Ф(и, ))=шах( — и — ); 0)+шах(и; 0), пш П, Е'. Если ) > О, то Ф (О, )) = 0 = )п) Ф (и, )) - р (б). Если же ) < О, то е1 Ф(п, г)=и при и> — б, Ф(и, 1)=* — б при 0<я~ — б; Ф(и, )) = — и — ) при и~О (нарисуйте график функции Ф(и, )) при различных б). Поэтому )п1Ф(и,б) = р()) = — ) при )( О.
Таким е1 образом, р()) = шах ( — ); 0). Очевидно, минимальный корень урав- пения (5) здесь совпадает с Х = О. Функция (6) будет иметь вид Ф (и, 1) = ~ — и — )! + шах (и; 0), и ~ Е1, 398 мвтоды минимизации Функция многих пвгвмвнных (гл, з Если 1>0, то взяв и= — т, получим Ф( — (; ()= О =р(1). Если же ! <О, то Ф(и, !)=2и+1 при и> — 1; Ф(и, 1)= — 1 прн 0< = и< — (; Ф(и, 1)= — и — 1 при и <О, и следовательно, р(1)= — 1 при 1< 0.
В рассматриваемой задаче функции р(1), построенные на основе функций (2) и (6), совпали. Пример 2. Пусть 1(и)=и, У=(и1иЕ'. д(и)=и' — 1<01. Ясно, что здесь У= (и1нЕ'. — 1<и<11, Уз = — 1, из = — 1, Если согласно (2) принять Ф(и, 1)=шах(и — 1; 01+шах(и' — 1; 01, и~У,=Е', то нетрудно показать, что р(8) = ш1Ф(и,() = шах( — 1 — 1; 0). Е1 Если же за основу взять функцию (6), то Ф(и,г) = (и — !)+ шах(и' — 1; 0), иенЕ', р (1) = 1п( Ф (и, !) = гпах (( г ! — 1; О). Е1 В рассматриваемой задаче функции р(!), построенные с помощью функций (2) и (6), оказались разными, но минимальный корень уравнения (5) в обоих случаях совпадает с Хз = — 1. Пример 3. Пусть У(и)=и, У=(и1иЕ'.
д(и)=и'=01. Тогда У=(01, У„= О, и„= О. Для функции (2) Ф(и, 8) шах(и — 1; 01+ и', и 1и У, =Е' получим О, ()О, р(() = гз, — 112<1 <о, — ! — 1!4, 1 ( — 112. Если взять функцию (6), то Ф(и, 1) = ~и — (|+ и', и1вЕ', и 11, /(!<1,'2, (!(( — 1!4, (8!) 1!2. Здесь также минимальный корень уравнения (5) совпадает с У =О. Однако нетрудно привести примеры задач (1), когда мини- мальный корень уравнения (5) строго меньше Уз.
Пример 4. Пусть У(и)=и, У (и~Е': 4'(и)=(и' — 1)Х Х(и'+1) '<01. Здесь У=(и1иЕ'. — 1<и<11 и, очевидно, Уз= — 1„ие = — 1. Если согласно (2) примем Ф(и, !)=шах(и — (; 01+шах(д(и); 0), и1н У,=Е', то при 1> — 1 получим Ф ( — 1, () = 0 = !п1 Ф (и, !) = р (Г). Е1 Прн ! < — 1, ваяв и„= -й < (, также будем иметь 1!ш Ф ( — в, г) ~ ь =!пид( — й) = 0= !п(Ф(и,!) = р((). Таким образом, в раса Ез сматриваемом случае р(!) = О при всех й Если в качестве мини- 9 свС метОд наггускенньгх Функции 399 мального решения уравнения (5) здесь взять С = — оо, то полу- чим с (Х = — 1.
Рассмотрим функцию (6) Ф(и, С) = ~ и — И + шах (д(и); 0), и си У, = Ед. Если Ш ~1, то при и=с получим Ф(с, с)=0 р(с). Пусть Ы >1. Введем множества Ад= ~иен Е'д ~и — С(< — с, Ав= ~с~ — с) = (иен Е: ~и — С~> — с. Так как А,ОА, = Е', АдП Ав = Яс с. сс! — П то р(с) = (п1Ф(и, с) = ш(п)1п1Ф(и,С); 1п1Ф(и,с)1)ш(п(ш(пд(и)С ед (~с ~ — 1)с2~) 0 при всех с, !с1>1. На первый взгляд создается впечатление, что здесь| = — 1 — минимальный корень уравне- ния (5).
Однако 0(р(с) < Ф(с, с) =-д(с) при !И > 1 и 11ш р(С) = 1пп д(С) = О. Поэтому есть основания считать, что с— с-~— минимальный корень уравнения (5) и в этом случае равен сэ = = — оо (Х,„, Любопытно сравнить задачи из примеров 2 и 4. В них функ- ции У(и) и множества У совпадают. Но эти задачи отличаются способом задания множества У. Это различие приводит к тому, что в примере 2 минимальный корень Св уравнения (5) совпа- дает с Х„, а в примере 4 С (У .
Отсюда можно сделать вывод: для выполнения равенства Сэ = У„, лежащего в основе метода нагруженных функций, исходные данные задачи (1) должны удовлетворять некоторым дополнительным условиям, они должны быть как-то согласованы. Для формулировки этих условий нам прежде всего нужно уточнить, что понимать под минимальным корнем уравнения (5).
Определение 1. Число Сэ назовем минимальным корнем уравнения (5), если р(св) = О, р(с)>0 при всех с(св и 11ш р (С)) О. Если же 1пп р(С) = О, то примем Св = — со. Если -|О с— р(с)>0 при всех с>0 и 11ш р(с))0, то по определению с-~- ю положим С = со. Чтобы показать, что все указанные в определении 1 возмож- ности в самом деле могут реализоваться, рассмотрим еще не- сколько примеров. Пример 5. Пусть и, и) — 2, У(и) = — йв, — (й+1)(и( — й, й=2,3,...; и' — 1, )и~(2, (7) 6ССИ~, /и~)2с 400 мктоды мвниыиэАции с»ункций многих пкггашнных [гл. ь 77=(п~нЕ'=77,: я(и)<0). Тогда 7„= — 1, и = — 1.
Рассмотрим функцию (6) Ф(и, 1)= (7(и) — 7!+ шах(я(и); 0), и мЕ'. Покажем, что р( — й' — й)> й (й = 2, 3, ...). В самом деле, если и ) — 2, то Ф(и, -й' — й) ~ (и+ й'+ й! й'+ й+ и ~ й' ~ й при всех й=2, 3, ... Если — (7+1)<и< — 1 (2~1< й), то Ф(и, — й» вЂ” й) ) ! — Р+ й'+ й! й* — Р+ й ) й, а если - (1 + 1) < и < < — г, М > й+ 1, то Ф (и, — й» вЂ” й) э ! — 1»+ й'+ й! = Р— (й+ 1)'+ + й+ 1) й+1~й. Таким образом, Ф(и, — й* — й)> й для всех и ж Е', поэтому р( — й' — й)> й (й = 2, 3, ...).
Следовательно, Пш р(г) — Ншр( йз й) — со.С дРУгой стоРоны, 0<Р( — й»)~ з— ь»» =-Ф( — й, — й')=я( — й) 6й ' (й=2, 3, ...), так что 1(ш р(1)= = Вш р( — й') = О. Согласно определению 1 тогда г = — со( ь-~оа <У, = — 1. Остановимся также на функции (2) Ф(и, 7)=шах(У(и) — 7; 0)+шах(77(и); 0), ижЕ'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
