Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 14
Текст из файла (страница 14)
9 19 главы!) и дает решение задачи. !3. МНОЖИТЕЛЬ ЛАГРАНЖА Обсуждение вопроса о множителе Лагранжа мы начнем с описания того, как он появляется в задачах анализа, свя- занных с разысканием максимума функции нескольких пере- менных при наличии ограничений.
Как мы увидим дальше, метод имеет простое геомегрическое происхождение и является, таким образом, гораздо более общим. Чтобы свес~и к минимуму математические детали, мы бу- дем рассматривать задачу отыскания максимума функции двух переменных Р (х,у) по всем точкам (х, у), лежащим на кривой 0(х, у) = О. Денствуя формально, обозначим че- рез (х„ ув) точку экстремума и положим х=х,+ вя, (2.17) у=у.+в! где а и 7 — вещественные параметры, а а — бесконечно малая. Тогда условие того, что точка (х„ уо) дает экстремум, 76 МНОГОМВРНЫВ ПРОЦВССЫ РДСПРВДВЛВНИЯ !"ГЛ. и множнтвль ллгглнжл приводит, как обычно, к соотношению з — +1 — =О, дг" дР дхе ' дуо (2.18) а условие того, что точка (х,, уе) лежит на кривой 01(м,у) = О, аналогично приводит к соотношению з — +1 — =О.
д6 д0 (2.19) ' дхо ' дуе Поскольку этн два урзвнения должны выполняться для всех з и 1, имеет место рзвенство дР дг дл'а д12 д0 д0 для дУе (2.20) Отсюда следует, что существует такая величина Л, что имеют место два совместных уравнения дР д0 дхо дхо +-л — =о, — =е.
~ дР, д0 дуо ' ду (2.21) Но они в точности совпадают с вариапионными уравнениями, которые мы получили бы, если бы разыскивали эксгремальные точки новои функции Н(х, у) = гч (х, у) + 10 (х, у), (2.22) *) См. обсуждение конкретного примера в 9 5 главы 1.
не принимая во внимание ограничения 0 (х, у) = О. Параметр Х называется ларалгетром Лагранжа. Чтобы определить параметр )ч мы поступаем следующим образом и). Из (2.21) находим значения х, и уе через У„ а затем используем соотношение 0(х, у)=0 для определения 1. В отдельных благоприятных случаях этот метод работает хорошо. Но в общем мы сталкиваемся здесь со многими трудностями. Нетрулно видеть, что этот метод можно использовать нри решении задачи отыскания максимума функции Р(хи х„... ..., хл) при ограничениях 0;(хих,, „хл)=0, 1=1,2,...
'е. 78 многомегпыя пяопкссы Рзспгвдвлзния [Гл. н !4. ГЕОМЕТРИЧЕСНОЕ ПРОИСХОЖДЕНИЕ В предшествующем параграфе мы вкратце описали, каким образом появляется множитель Лагранжа при изучении методами анализа вариационных задач с непрерывно меняющимися независимыми переменными. Поскольку мы хотим рассматривать более общие вариационные задачи, важно дать более широкое толкование этого множителя.
Рассмотрим задачу определения максимума функции Р(хь хэ ..., хм) по всем хп принадлежащим некоторому множеству о и удовлетворяющим соотношению вида 0(хн х,, ..., хм)~1, Будем вычислять значения величин у, =Р(хь хм..., хх) у„= О(хь х,, ..., хм), (2,23) когда х; пробегают все множество о. Это дзет отображение подмножества дг-мерного хкпространства нз часть двумерного унпрострзнства. Область в Рис. !8. у;-пространстве часто называется прогтранслтвом моментоа по причинам, которые взвели бы нас в слишком далекие детали.
Чтобы объяснить простой геометрический метод, который мы будем применять, допустим, что множество точек (ун у,), которое получается, когда (хь х,,...,хх) пробегает 8, образует выпуклое множество в у;-плоскости. Мы можем мыслить это множесзво как внутренность овала вместе с его грзницей. Чтобы решить исходную задачу, состоящую в отыскании экстремального значения у, при фиксированном (или ограниченном сверку или снизу) у,, мы должны определить точки границы овала (рис. 18).
Следовательно, исходная задача 79 гвомвтгичвсков пгоисхождвнив разыскания максимума эквивалентна задаче определения границы овала. Эту границу можно найти геометрически следуюшим образом. Возьмем на плоскости (уь у,) прямую, скажем ау, + Ьуя = А, (2.24) и будем сдвигать ее параллельно самой себе до тех пор, пока она не станет касательной к овалу. Эта геометрическая дуг =А Рис. 19. операция, очевидно, эквивалентна аналитической операции изменения А на некотором интервале. Точки касания в точности совпадают с граничными точками овала, как показано на рис.
19. Если эту операцию повторить прн разных значениях а и Ь,которые соответствуют прямым всех направлений,мы охватываем всю границу. Заметим,что мы использовали фундаментальное понятие двойственности двумерных фигур: геометрическое место точек можно рассматривать как огибаюшую касательных. Для того чтобы использовать эту идею конструктивно для получения конкретных аналитических результатов, мы заметим, что точки касательной определяются условием, что расстояние прямой ау, + Ьу, = й от начала имеет экстремальное значение (максимум или минимум). Для фиксированных а и Ь расстояние от начала пропорционально А.
Таким образом, максимизация или минимизация величины й, определяемой равенством ау, +Ьуя=аЕ(хи х„..„хн)+Ь0(хп хм ..., хн), (2.25) дает граничные точки. 80 МНОГОМЕРНЫЕ ПРОГ1ЕССЫ РЛСПРЕДЕЛЕНИЯ [ГЛ. и Если а не равно О, мы можем поделить на него и рассматривать эквивалентную задачу определения экстремальных значений выражения Р (хн хя ..., хл) + >,О (хь х„..., хл), (2.26) где Ь|а=>,. Теперь мы видим истинное происхождение множителя Лагранжа, а также то, каким образом обобщить эти идеи на случаи, когда имеется несколько ограничений.
Хотя эти идеи совсем просты, некоторые дегалн строгого их осущесгвления опираются на весьма глубокое понятие, именно, на понятие вылуклостгк Поэтому мы будем следова1ь формальному, интуитивному пути, а читателя, интересующегося доказательствами и обобщениями этих идей, будем отсылать к некоторым работам. |б. МНОЖИТЕЛЬ ЛАГРАНЖА В КАЧЕСТВЕ ЦЕНЫ Если считать, что функция Р'(хп х„, ..., хл) характеризует наш «доход», обусловленный «распределением» (хь хя... ..., хх), а функция 6(х„х«,..., хм) характеризует «издержки», соответствующие этому распределению, то >„ или — >„ имеет смысл цены.
Это интуитивное понятие можно сделать совершенно точным. Оно имеет важное значение в математической экономике вообще и в теории линейного программирования в час~ности. В приложении || в конце книги эти идеи рассмотрены более детально. 16. ПРИМЕНЕНИЕ МНОЖИТЕЛЯ ЛАГРАНЖА — | Вернемся теперь к задаче максимизации, разобранной в й 2, и выясним, как ее можно было бы рассматривать с помощью множителя Лагранжа.
Вместо задачи отыскания максимума функпии «т(х|,...,хл', Уь ..., Ул)=81(хг, У|)+к«(х«, У«)+... ... + л'м(хл; ул) (2,27) при ограничениях (а) х1+х«+...+хм='х, х,)0, ~ (2.28) (Ь) у+у+ "+ух=>» у;-0 ~ пвимвнвнив множителя лагианжл — г 81 16] мы рассмотрим задачу отыскания максимума видоивмененной функции ач (хь у,)+д,(хм у,)+. „ "+Их(хго ух) — Л(уг+уа+...1-уй (229) при ограничениях (а) х,— 'х,+...+хх=х, х;)О, (Ь) уг О, (2.30) где Л предполагается на время фиксированным параметром. Максимизацию по у; можно выполнить независимо от максимизации по хп Введем функцию )гг (хп Л) = !О (х;) = шак (с; (хп у;) — Лу~]. (2.3 !) л. о 3 Для того чтобы это определение имело смысл, будем предполагать, что " ач — 0 при у; — со. (2.32) Если дело обстоит не так, то этот метод не годится. Поскольку в приложениях результат (2.32) является следствием «закона убывающих доходовач мы будем исходить из допущения, что он имеет место.
Задача сводится к аадаче максимизации функции Й, (х,) + !г, (х,) +... + Йх (хх) (2.33) при ограничении (2.30,а). Эта задача легко решается методом функциональных уравнений, изложенным в главе !. Решение х;(Л; х), 1=1, 2,, И, этой задачи оптимизации будет, естественно, зависеть от Л; значения у;=у;(Л), которые будут давать функцию и; (хг), определяемую формулон (2.31), также зависят от Л. Будем далее менять Л.до тех пор, пока не удовлетворим условию Ху! (Л) =у (2.34) 1=! Ниже, в 8 !9.
мы исследуем законность и осушествимость этого подхода. А теперь продолжим наше рассмотрение формальнои процедуры. многомгРные пРоцессы Распгеделения [гл. 11 17. ПРИМЕНЕНИЕ МНОЖИТЕЛЯ ЛАГРАНЖА — П Таким же обычным путем мы рассматриваем задачу отыскания максимума функции тг1(х1)+па(ха)+...+ух(х ) (2.35) при ограничениях (а) агх1+ пах„+... + аххх( х, (2.36) (Ь) Ь1х,+ Ьахт+...+ Ьнхх(у, х ) О, ) Строим новую функцию й (хг) + уь (хя) +... + Кх (хл) — Л [Ь гх1 + Ьахз +... " + Ьххл) (2.37) и рассматриваем задачу нахождения ее максимума в обласги, определяемой условием (2.36,а). Соответствующее рекуррентное соотношение имеет вид Решение х;=х;(Л; х) зависит от Л так же, как и функции дохода гм(х).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
