Цлаф - Вариационное исчисление и интегральные уравнения (947328), страница 18
Текст из файла (страница 18)
ВАРИАИИОИИОЕ ИЕЧИСНЕИИЕ и.!т.а что прн й — 0 нрнвгяпи ь !Рамн ньио в члсппи нронзводных -- -- = пил ~у(а, с, о! + о д/ . г д/"! дя а ~ ' ' ' дс~' (1,12.10) /(й,с)=0 лая всех с,а -.й /'(х., у) =-пт!и ~l'(х, ай тг) л+/(х,у)+ лг+ у'д+...~ д/ д/ д.с ' ду о!к) да 0 =- и! )и ~ /е (х, у, у) . ! . / ! .
у' ~ д/ д/ ду. я, с.!словате. ы!о, д/ д/, д/ Рд — —. !..у' — — - О д.' ' ду ( 1, ! 2. 1 ! ) (1. 1'2. 12) Нз (!.!211) н (112.!2! след!'ст травнсннс Эйлера — Лагранка. Г!научен!!е необходниых тсловнй тппаямт.ма для нгходного фтнкпнонала понведено к нолученню необходимых условнй мнпнмума функция от уй Ф (У ) = г (х, у, у ) Ч- Д- + )- У'. (1.1 .
13) д/ д/ Необходимое условие мнннмума Ф" (у)-.0 преврагцаетгя в условие Леткандра Ру „ О. (1,12.14) йслн К',~ у', то д/ д/..., д/, „д/ р (х, у, у ) + — + —, у =.=-. р (х, у, у ) + —. + ) дх ду. ' ' . ' д.г ду' Требуется определить нензвесп!ую функцию а (управление) так, чтобй минимизировать время, требуемое для переходл системы что дает условие Вес!срп!трасса Е (х, у, у', !' ! = — Г(г,зь )") — Р(х,у,у) — (У" — у) /с!, ~0 (1,12,!5) Л!стол Беалмана распространяется н на все остальные лапа !н варнацнонного нсчнслення, рассмотренные ранее. 1.12.6. Связь динамического программирования с задачами условного экстремума и принципом максимума. Пусть дана система дкффг.рснцнальных уравнений — †' =- д! (у„ уа, ..., у ; з; Г), У; (0) = с; (! = 1, , ..., Ф).
и. Опт>>мял>н>ые пн1>пц>1пы 1.1».6! в состоЯние (Дн 1>н ..., 1> .), т, е. фУнкЦнонал Т= Т(з) онРеДсляется >словнямн ут (Т) = 1>; (1 =' 1, 2,, >т>). Это — задача об оптнмалььом быстродействии. Если У(у, 1) — времн, требуемое дзя перевода системы из состояния у в момент 1 в желаемое конечное состояние, то нз нр>шпнпа онтнмззьностп сзедтет Т (у, 1> =- ш>п ] л + у (у -!- я 1 1+ .1)] + о (з) »Ф откуда .т. 0= — >п!п]1+ ~ >т>Ь+у> г (!.12.!6> Из (!.12.16) следует, что -"; >>з ' 0 — !+ У Д+Т>.
1=- ! (1.12.17) по определению функции т(у, 1) имеем Л=О при >= т, слс.ч донзтезьно, ~"„,~ (Т) д> (Т) =- — 1, Если ТП не зависит от 1.=- ! К иэ>еет место пеРвый интегРзл системы ~Д ~/»б7= — ! вдоль оп!=! тимальной траектории. Для функций у, значения которых в точке Т не определены, Ут (Т) =- О. Если нзвестнь> У! то из "! 1 (1,12.17) находится з.
Дла отыскапиз Ууа называемых ФУЯкционпльныл>п л»нонсил!елями (з в работах, связанных с принципом максимума, — импульсами), в тех случаях, когда а> не зависят от г, служат дифференциальные уравнения, получаемые нз 11.12.17): з — Ут + ~ — 'Ут = 0 (! = 1, 2, ..., >>'), 1> ът Оа, и совпадающие с урзвнениями для функций ф; в принципе максим) ма. Последняя системз вместе с нгходной и первым >равнением (1.12.17) определяет >т! функциональных множителей, >)> величин у>, у», ..., у,, и Т(у, Г). Рассмотренные в этой главе задачи являются общими задачами условного экстремума (Лагранжа, Маайср, Больца) и, как указывалось ранее, из принципа максим)ма и принципа оптимальности следуют все необходимые условия экстремумл в этих задачах.
вв ГЛ. 1. ВАРИАЦИОННОЕ ИСЧИСЛЕНИИ Н.сзл см. всллмвн и дрейфус [г). о вопросу аб евтимвльаьп принципах сл. сгвтьм Л н то не ел во )гр е вопросу а леоблаллмоетн н лоствточноств принципе млнсамулв и принципе оптлмвльноств см. Велтяисниа (г). (Л). ф 13. Линейное прогрймулироваиие 1.13.1. Постановка задачи. Разнообразные вопросы, возникающие в экономике, военном и инженерном деле, часто приводят к следующей задаче. Найти максимум линейной формы (целевой фуккцаи) =р,х, +рь'. + ... +р„'„ (133. 1) при условиях агсх, + а;лл", +... —;-а;„л„. а; (1=1, 2, ..., ви туг~ и) илн, что то же, при !ставнях уг = — ат,х, — амлт †... — асях„+ аг «О (! =- 1, 2, ..., гп; лг)п).
(1.13,2) Ниже, в п. 1.!ЗЛ, приведена в качестве примера задача линейного программирования, частный случай так называемой транспортной задачи. 1.13.2. Геометрическая интерпретация. Из аналитической геометрии известно, что геометрическое место точен, координзгьг которых удовлетворяют неравенству Ал, + Вх, + С ли О, есть полуплоскость, лежащая по одну сторону прямой Ах, +Вл;+ + С = О, причем для точки (хг, х,) число Ах, + Вх„+ С, назы- ваемое уклокенпем этоус точки от указанной прямой, с точ- ностью до множителя равно расстоянию от точки (хн л;) до прямой Ах, + Вх, + С = О. Задание неравенств Л,х, + В х, + С, ) О, А,х, + В,х, -(-Ссси о, (1.1 З.З) А„х, +Вахт+ СлгмО, определяет некоторую ныпукаую многоугольную область, кото- рую будем называть просто .многоугольником.
Задача линейного программирования может быть сформули- рована пан отыскание точки, принадлежащей многоугольнику (1.13.3) и наиболее уклоняющейся ог прямой г=р,х, +р,х, = О, В зависимости ог расположения многоугольнина (1.13.3) и пря- мой р,х, +р,х, =0 задзчз имеет единственное решение, беско- нечное множество решений илв совсем не имеет решения. В данном плоском случае ясно, гго решения задачи, если они существуют, даготся точкзми, лежащими либо в вершинах мно- гоугольника (1.13.3), называемого тлкже мкогоугольялкам регае- миа", либо на его сторонах.
!.)з.з) й гд пинг пнон п рогрлммпровлпнп 89 Пусть, например, требуется максим~тзвравать цшеяую фрнсцию г=- — Шх, +3. при ограиикенняз !) У! = — хг+2хв+ зеив, )й Гз хл+ лз)- ! — О, .Щ) уз= зх,— х ! О, )Р) Уя= — 2х! — 4тя+ )О О, !') ун=- — 2тг+ хе+ Ю О. пи зд) Многотгольняк рещенил, являющнйсв пересечено ° полтплоскостей (!.)3.4), показан на рпс, !.)3.!.
Перейдем от пркмоггольнык декартозыз коорлинат (хг. хз) к косоугольной системе «оордииат (уг, уз) по формулаи ут — хг+гхя+3, уз=я!+ха+ ! Уг нли ! 2 хг = — — у!+ — уз+ 2, 3 з ! ! х. — Уг + — уз — 3. 3 3 Н втой косоугольной снстеме координат асями координат являются прямые у! =.О и уз = О, а накалом коорлииат — одна из нержин многа)гольника ретвений.
Стщественным обстолтельсгном яв. веток то, *по координаты !Уг, уз) всея точек Рнс. !.)3.), много гольника решещцй нсотрицатсльны. 6 слезая функция л =- — )2х! + Зхе пронимает япд з =- бу! — тут — 33, причем - — зз. )лг-О 1)з=о Целевая функция валрастащ при движоинн точки гуг, ут) н паложвтельиом направлении оси у! (Уз О). В частности, когда многоугольник (1,!З.З) имеет сторону, параллельную прямой р,х, +рзх, = О и содержащую хотя бы одну точку, дающую решение задачи, то любая точка уназанной стороны также дает решение этой зздачи.
Если же много)гозьннк (1.133) бесконечен или же система неравенств (1.13.2) противоречива, то задача не имеет решения. Аналогичные соображения распространятотся на общий случай, в котором вместо многоугольника (1,13.3) будет фигурировать некоторый выпуклый многогранннк, а вместо прямой — плоскость. 1.13.3. Симплекс-метод. Первым этапом решения задачи линейного программирован)щ является отыскание наной-либо вершины многограннина решений. Решение системы (113.2), соответствующее вершине, называется опорямж; имен опорное решение и отвечающее ему зна !ение пе:)свой функции, находят направление к другой вершине многогранника, в котором целевая функция возрастает и,таким образом, приходят ко второму опорному решению. Повторение этого процесса приводит к оптпмзльному решению (если таковое существует) поставленной задачи. ГЛ.
1. ВАРНЛЦНОННОВ НСЧИСЛЕННС И, 1з.т та и обрез , ияйдспо вер ое опорное решение н нзорзядение опиям яппи пс.е» й фувкцыи решен а зздачн усеагнпизось бм, если зз осп навои с1шгенм коардиизг бмя бгя язяити прнч, с 11- —.т, +Й.г,+8, уз Зкг — х» — 1 Начзяо павой снегами координат в этом случае хе кит янс многоугазьникз репгс: ий и первьш этапа» резне о!я задвчн гганоннгся прибзнженпс к одной из верошн: ногоугооьвикя решений, лиле чего протее асуп! сгвяяется по укяязнначу пиша п.шну.
Б общем слт'шс, когда зздзп мног ог рзннпх, в вершинзх которого гца ребрах нли грзнях) оть1скнвсстся рсшсгше звдзчи лянейного программнровзння, производится переход от исходной декартовой прямоугольной системы координат к косоугольной, в которой в кзчсстве координатных плоскостей используются и нсноторыс нз !ипсрплоскостей, ограничивающих унаэзнный многогранник. Прн этом ноорднннты всех точек лгногогрзнница становятся неотрицзтельнымн. После этого отыскивается первое опорное ретнение и направление, в котором целевзя функция возрастзет.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
