Цлаф - Вариационное исчисление и интегральные уравнения (947328), страница 19
Текст из файла (страница 19)
Отыскание второго опорного решения и повторение процесса отыскания последующих опорных решений приводит и по- ЛУЧЕННЮ О1ПИМаЛЬНОГО РЕШЕНИЯг ССЛН ТОЛЬКО ЗаДаЧа РЗЭРСШИМа. Описанный способ решения эздачи линейно! о программирования носят название си.нплзкс-жетадп данцига. В последние годы в качестве алгебраической основы симплекс-мстодз успешно применяется указанный Штифелем аппзрзт жордзновых исключений. Дэ )ьггейшая рнзрвбатна и гео стриэзция етого аппарата содержится в книге Эухопипкого и АвдеевОЙ )1). 1.13/1.
Связь с динамическим программированием. Сообрзженин, приведенные в п. 1.13.2, покаэывлют, что методы дифференцизльного нсчисзения неприменимы для решения эздач линейного программирования, в которых решение всегдз нзходится нз границе облзсти определения функции (1ЛЗ.)). Однзло зздачи линейного программирования можно формулировать язц задачи динами:еского прогрзммировання, кав это будет показано ниже, следуя Беллмзну и Дрейфусу, на примере одной трписпортяай задачи. Имсютсн нве скса/н, содержащие саошегсгвенна х! и х некоторого ресурса, н // пунктов оатребзения с патребностя.
и соогвстствеяяо г, г,..., г , 1' З'"" л' в зтач ресурсе. Общий зэпзс равен общему спросу: х +х =. +г +...+г,. з 1 з "' А" Пуст х ° — натичесгва 'ресурсов, отпрзшяемыз нз !.го склада з рй пункт г/ нотр бдения и л .=-с!.,х..— стоимость осу цествдсния ясак операции. треб!ется минимизировать функцию 1 а.,х.. !в рэссиатризасмам сдучзс ! — \, 2; /=-1, ..., Ф) г/ !/ т,/ при усзозинз Л лт х,.:б. ~" к,. =-х! ~' х! -г/. /=1 !=-1 о( 1.14.11 й 14.
ПРЯМЫЕ МЕТОДЫ Пусть у, гт, т т — в зпч! . л ввтрвт прп ис! .! зоваи !и о тимвяыкгй позотнин, Л'1 1' !) «ог.!в нвчи!зюг соотяетсгионно «количеств хг, х ° при фиксировяиныз потреб. ! ! Удаелетеораше первого спроса в Лдм п>икте потребления ласт затраты л!м(х!л)+лам( е(у) И УМС гЬ:Наес РЕСГРСЫ На СК Еда! ДО Х! — Х(Д( В Хз Хеб. ИЗ ПРИННИПа Овптма ьпосп! слюуег пр! ЛГ.О (О( (лт, хт) пнп (Лтм (х(Л>+ хан (т!Л)-!- (Л ! (хт — х!Л, ха — хял)), (я,> ) тле я — дв>мерная об.!всть, опредезяемея ус.!аенямн гч О.. х, 1Л ' ЕЛГ Х' ' 1Л' 1' ЗЛГ З при и 1 имеем дхг, х >=к!! (хг> — 'лш (то Испозьзоеанне >елозин хг+.тз —..— > г позволяет исключить параметр г хя: тогда ля ун(х, х )шу (х ) имеет место соотношение Л' УЛ( 1) .
"1!Л!Л( (М)под!у('Л х!Л)+(М ("1 ">м))' 1Л О г — х > г — х, Л !Л' 1 1' и О св х. 1 .~ !' 1=1 1 *1Лс В книге Веюмвпя и Дрейфуса (11 приведены вычвсления лля случв» кнут силадов и десяп п нктов потреблении, а также для трех складов и десяти пунктов потребления. В приведеииом причере Л..можно ряссмвгриввть и в виде нелинейной г! фуккиви х., о' Возможност! формулирования задач линейного программирования как залач динамического программирования не означает, что это необходимо делать, поскольку во многих случаях вычислительные методы линейного программировании оказываются достаточно зффективными.
.тиырвтура по линейному программированию весьма обширна. Для студентов агузов и нн>кенерои можно рекомендовать слелуюшие книга! Керпелевнч и Садовский (11; Зуяовипкнй и Лвдеена (!(; Юлин и Гольштейн 1!1. ф 14. Прямые методы варианнонного исчисления 1.14.1. Постановка задачи.
Обычные методы варивционного исчисления, прн которых задача минимизации функционала сводится к интегрированию уравнений Эйлера — Лагранжи, часто приводят н очень трудоемким вычислениям, что делает зтн методы мало эффективными. Большим распространением при решении теоретических и прикладных задач пользуютсл прямые методы, заключающиеся в следующем. 92 ГЛ. 1. ВАРНАБИОННОЕ ИСЧИСЛЕНИЕ Н.!Аэ Птсть требуется цайтн минимум некоторого функционала у(у), о котором известно, что точная нижняя грань его значений гн1 У(у) = и ) — ОЭ. Пусть удалось найти последовательность допустимых ф)'нкцнй у„у„..., у„, ..., такую, что !!ш Х(ун) = ю. Во многих ваткных слтчаях нрн этом ггказывается, что мянцмнзнрующая последовательность (уэ) схолцлся к функция у, для которой у(у) = ю, н тем самым вариационная задача решена.
С другой стороны, прямые методы вариацнонного исчисления доставляют решение тех краевых задач дифференциальных уравнений, которые могут рассматриваться кан совокупность уравнений Эйлера — Лат'ранжа и нраевых услоний в задаче минимизации некоторого функционала. 1.14.2.
Метод Рнтца. Примеры. Пусть требуется найти минимум функционала Х(у) = ~ Р(х, у,у) дх, у(х) =а, у(х )=а, (1.141) 21 в некотором нлассе функций. Рассматривается и-параметрическое семейство фуннцнй у (и, х) э,(х) + ~ сгф (х), (1.14.2) где у, (х,) = ао Р, (х,) = а,; эг (х), уг (хг) = — эг (х,) = О (! = О, 1, ... ..., я,...) — последовательность линейно независимых функций. Взятые функции называют коордннатнымн. Па функциях (1,!4.2) данный фуннционал превращается в функцию а переменных у (у (н, х)) = Ф (сн см ..,, с„).
(!.!4.3) Выбираготся те значения сн см..., сгн которые доставляют функции Ф минимум. при найденных сг (г= 1, 2, ..., а) функция (1,142) обозначается через у„(х), Во многих прантически важных случаях последовательность найденных таким образом функций у„(х) (а = 1, 2,...) является минимизирующей и дающей решение поставленной задачи.
Указанный метод принадлежит Ритцу (1908 4.). Существование абсолютного минимума функционала (1.14.1) в достижение этого минимума посредством построения минимизирующей последовательности функций обеспечивается выполнением следующих условий, Обозначим через 0 замннутую область плоскости х, у, в которой лежат линии уя (х). Функция Р'(х, у, а) непрерывна но совокупности своих аргументов при (х, у) ~ П и любом конечном л. Е14.2) 5 !4 ПРЯМЪ|Е МЕТОДЫ Существуют константы с ) О, р) ), б, длл которыл Г(х, у, а) ) и ' а(а+3, каково бы ни было а н длн любой точки (.к, у) ц сг. Функция с'(х, у, а) имеет непрерывную производную ! з (х, у, а) н дзя любой точки (х, у) ц Ст зта производная есть неубывающая функция от а( — оо а сор).
При атом интегрирование понимается в смысле Лебега (см. и. '2.0.3), а функционал рассматривается в классе абсолютно непрерывныл функций. Уьажнные условна выполняются, а чзстностн, для функционалов вида хз ~ (р(х) ум+ д(х)уе — 2д(х) у) дх, у (х) =от, у(зз) = не зч где )т(х) ) О, с) (г)- О и 4 (х) — известные непрерывные функции в конечном интервале (ло хз). См. Лтиезер (1). Важное значение для применений имеют линейные вариационные задачи, т.
е. задачи о минимизации функционалов, уравнснил Эйлера — Лагранжа которых линейны. Условием применимости метода Ритка к минимизации таких функционалов является ил положительная опредезенность, т, е. существование положительной константы у такой, что х. х. ~ с' (х, у, у') лх = ) ') уг г(х тз и соответственно Г(х, у, и, и, н ) с(х с(у»у Ц лз сзхс(у, П в классе функций, непрерывно дифференцируемых достаточное число раз и удовлетворяющих крзевым условиям задача, Цолробиов рвссмотреиие итого вопросе см.
и и з з и и О). (4). П р и м е р К\4Д. Минимизировать фуииниаисз (Ом +Уз+ахр)Л., у(О)=уй) — О. о Пусть т (х)=0, т (т)=хз — х. т (х)=х — х,...,р (х)=х — х, з 3 лет л Прил 2 Х (2, «).= ст (хз †.4)+ се (хз — хе), у' (2, х) = се Пх — 1) + се (ахе — 24), П,.П ,Г (у (2, х)) = В (с, с ) = — се + -- с с -, '-- сз — -- с — — с 1' 3 Зо т" ао т 3 7 з б ! ГО З' ув ! ВдРИДНИОННОЕ ИСЧИСЛЕНИЕ !!.14,2 94 ОФ Нсп ьзу» условия 'Сг получи И =с, 13 П 2 '30 ."- Сг+ —. Сд— Отсгода 69 с,= —, 473' 7 сз= .,- 41 77хз — бхз — 69х у !2 х)= 473 В дангю» случае модна 1квзеть ~очное ре~пе!гие! 1' =- — „(г — е ) — х.
ез 1 Нюхесзедующае гэбтг~ця дает сапастаз.ыпие точного п прибзименного реищннй: Пример 1.142. Модификации метода Р итца. Пусть требуется минимизировать фунхноогыз 1 ./(у)=) еру Нх, у(О)=0, у(1)=2!п2. О Рещение этой задзчн обычнымн методами приводит к фуакппи у= 2(п П +х1, Лзв приближенного решення еьгбирается последова еяьиос ь, конструируемая из многочленав третьей степени следующпч образа 1-е приближение. Ивагочгены грозней степени, дз» которых у ну' принимают при х=о и х=( ааданные значения.
2-е п р и 6 ли ж ее ие. Функции класса Сг (О, 1) с задаинынн значениями у н тс нрн х=-о, х 1)2, «=1 и кубвческнк в каждом вз двух и1ыервалов. а-е приближение, Функции класса Сг (О, 1) с заданными значениями 7 а — 1 для у и у' прн х = — †;- () = О, 1,...) н кубических в ка кдон ин 2 налык = ой=! и~стервенев. Лля кажлого а фуннципнала у(у) заменяется значением 7 (у), которое вычисляется н каждом интервале по правилу Симпсона, прнче» иеобсолнмые дзн етого срелнпе значения у и у' находятся по формула» 1 и у= — (у +у) — — (у' — у'), 2 1 ' з 4 з 1' 3 у'=- — (у -)' ) — — Ст,'+у'). 4й -3 1 4 з 1' выражающим нх через значения ур у' на левом н у„, у' иа правач копнах ин- 1 з' з терна!а длины О. Так как значения у заданы пря х=п и х=(, то фумкцни ив первого приближения полностью определяются их производиымн у' при х =0 н х 1 Эти знаяенив.
умноженные на постоянные множители, обозначены через тю и О, и ирин ты в качестве нева ис мых переменных в первом приближенна ОФ О,—. О, ' доз 11 1 + — сз 30 6' х У 0,0 0,0000 0,2 — О,ОИ7 0,4 — Оо пб О,б — О.(966 О 6 — 0,0688 0.8 — 0,0444 10 О,ОПОО )'(2 х) О,ООЮ вЂ” 0',028з — О,особ — 0.0163 — О,обне — 0,0442 О,ОООО % 14 ПРЯМЫЕ Х1ГТОДЫ 1.1!.2! 1!ЕРВОЕ нрггбзс ксао ". .с 0; х = О Ч! х„ = 1.О. Д =- 0.6: У = 0: У, 2 1 п 2; « Д !' (1 = О, 1. 2). ~, (У) -.— (У„'+ 4 -"УЯ) =-3 0-10" ,ф~ У',;-+~~$ 1 1 У! = Оо+зЫ вЂ” — (8 —,о)= О 69316+О.М)э — О 23 ш 2 3 1 — (Уз — Уо1 — -- (Ге + че1 = 1,03972Π— 0,20 и — Озфг 4 4 Берем ю и, аэ названо«мыс пере ениыс н ршпаем ураннен и ='и — =26 +суг,— — Осу!, =20 — Π— 0 10 .г =О, с.! ! Д=-Зд —. 81,— еуг,— — 2еугб 6 — (2+0 ) 0 ау!=О.
з ! Овх - ! 0! з Решения последней системы (методом Ншотоаа) дают ,о 1,006, Чг =.О 669. ,я = О 601. у! О 8!9, тогда как точное решение лает ы= ! 0)0, си =ОД67, (з.=0500, у! =08(9 Подробюе решение этой з дачи вместе са егорыч приближением см. Мор~ей (1). Пример 1.14.3. Найти функцию и — --и(х, 11. гарнапическую н области О: х>0, у)О, х-1-т(1 и удовтетворнюигую на границе Г: х О, у=о, .!+у=( условию: в = тв-г-УЦ Г Гармоннческаи фувкшгя удовлетворяет уравнению Лннласа, являюшемуся уравнением Эйзера — Остроградского взя и~гтеграла Дирнхле: филя -Р «уу Ох иУ. О (1.14.4) Выберем коардинатньш фуакции: ио (х, у) = хз +уз иг(х, у)-ху11 — х — у). ит (Х, У) - ХЗУ (1 — Х вЂ” У1, У)- "У(1 — — У) ~ (!.14Л) О методе Риша и других прямык методах см. М и х л и в )Ц (4), (6), а также Камторович и Крылов Н).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
