Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 15
Текст из файла (страница 15)
Величина Л теперь меняется в пределах, допускаемых ограничением (2.36, Ь). 18. ПОНИЖЕНИЕ РАЗМЕРНОСТИ Прежде чеи приступить к теоретическому обоснованию, а затем и к некоторым приложениям, остановимся на возможности понижения размерности, которую позволяет осуществить наш метод. Пусть рассматривается задача отыскания максимума функции д1 (х,) + ет (х,) +... + а ч (х;ч) по множеству значений хи удовлетворяющих условиям (2.39) ~Ч ', а11хт ( сг 1 = 1, 2,..., гИ, 1 ! (2.40) тх(х) = шах [дх(хх) — ЛЬмхх+1л — 1(х — аххл)]. о хх хгах .
(2.38) 83 зкзизллвнтпогть вляилпионных злдлч и, возможно, другим условиям видз (а) х,=0,1,2, (Ь) а! ( х! -= Ьн 1= 1, 2,..., Аг. (2.41) Мы можем свести эту задачу к задаче определения последовательности функций (!л (с!, см ..., см)) от М переменных гь с„ , с,и, к которой применим обычный алгоритм. Вводя а множителей Лагранжа, можно сформулировать новую задачу максимизации функции л Ф л ~Х ! с (х,) — ~~Л! ( ~~а!1хт) ! ! 1=! 1=! при М вЂ” а о!рапичениях л ~ а!тх, ( с!, 1= л+ 1, л+ 2,, М.
1= ! (2.43) !9 ЭКВИВАЛЕНТНОСТЬ ВАРИАЦИОННЫХ ЗАДАЧ Теперь мы хотим исследовать связь между вариационной задачей в ее первоначальном виде и задачей, возникающей при применении множителя Лагранжа. Чтобы выяснить характер результатов, которые здесь можно получать, достаточно рассмотреть частную задачу. Таким образом, задача сводится к определению последовательности функпий от М вЂ” л переменных вместе с поиском по л.мерному пространству переменных Л!.
Ограничения на обьем памяти вычислительных машин таковы, что легче иметь дело с большим числом одномерных задач, нежели с одной многомерной задачей, а потому указанная здесь пропедура очень часто дает нам возможность рассматривать задачи, которые другими способами не удалось бы решить. Кроме того, во многих случаях оказывается, что параметрическое представление решения через 1ч (янезы») является столь же ценным, как и его представление в терминах ресурсов се Вопрос о выборе л зависит от конкретной задачи, от типа имеющейся вычислительной мзшины и от времени, выделенного на вычисления.
84 ь!ПогомеРные пРОцессы РаспРРделения [гл. и при ограничениях (а) х, +ха+...+хл=х, х; — О, (Ь) у! О. (2.45) Пусть х;(Л), у;(Л), !=1, 2,, !Лà — множество макснмизирующих значений в предыдущей задаче. Мы хотим показать, что эти значения доставляют максимум функции л!(х!, у!)+й(х! у!)+,+ух(х!г ул) (246) при условиях х,+ха+...+хх=х, ~ У!+Уз+ ° ° .+Уз! =У ! (а) (Ь) (2.47) где у= ~у!(Л). 3=! Ценность это~о результата состоит в том, что ни одно вычисление не пропадает даром. Каждый раз, когда задача (2.44) решается для конкреююго значения Л, тем самым решается исходная вариационная задача для соответствующего значения у.
)токазательство ведется от противного. Предположим, что существует точка (хо у!), удовлетворяющая условиям (2.47), для которой ~ Л!(Хн У!)) ~ю ~а(Х„У!). (2.48) г=! Тогда, так как л Л ХУ = Сл У!=У (2.49) ! ! мы получим: Ф !г н х ~ К (хн У) — Л ~, У; ) ~к~ ~,(.Е„У!) — Л 'Ч,' У,. (2,69) ! ! ! ! Рассмотрим задачу отыскания максимума функции )С(х„х„...,хк', у!, Уь. Ул)=д!(х!, у!)+ая(хя уя)+ .. "+да(хм ул) — Л(у!+уз+ .+ух) (244) монотонность по Л 201 По э!о противоречпг предположенн!о о том, что.
1х! х! " -сад у» у! " ул1 является л!акснмизнруюшим множеством для функции (2.44) при условиях (2.4о). 20. МОНОТОННОСТЬ ПО Л Положим ил=~ч~ д,(хл(Л), Рл(Л)), ! ! ел= Х уг(Л). (2.51) г=! Тогда, если 0(Л(р, то в силу своасгв максимизации (а) ил — Лпл)п — Лв, 1 (2.52) (Ь) ", — рп, — ил — рзл ) Следовательно, используя обе части неравенств (2.52,а) и (252,Ь), будем иметь: и, — Лел)гг„— глп. +(!л — Л) и,, ) (2.53) и — р +(р — Л), ) Поэтому Ь вЂ” Л)ел=.Ь вЂ” Чт, (2.54) Во всех приложениях следует ожидать, что, когдз Л пробегает интервал (О, со), у ведет себя подобным же образом.
Однако строгое доказательство этого факта требует известных усилий и некоторых предположений относительно функции д,(х, у). Покажем совсем просго, что при возрастании Л от 0 до и со сумма т,' у, (л) убываег лгонотонно.,'-)того следовало г= ! ожидать, исходя нз лого, что Л может рассматриваться как цена. Однако, посколы<у мы наложили очень слабые ограниченна на множество значений х! и уп мы не можем ожидать Л строгой монотонности ~ уг(Л) или непрерывности ее по Л.
г= ! 8В многомвяныя пяоттвссьт Рхспявдвлнния (гл. и Так как Р— Л)0, то мы получаем требуемый результат: (2.55) чул ~п . Комбинируя этот результат с (2Л2,а), получим: ил — Лил ) и — Лп„, Лил ) Лпю (2.56) откуда (2.57) пл )!та Эта монотонность значительно упрощает определение значения Л, соо~ветс~вующего данному значению у. Для сокращения времени, требуемого для решения конкретной задачи, можно использовать методы поиска, которые будут рассмотрены в главе 1Лт, или какие-либо более простые методы. 21. ПРИМЕНЕНИЕ МЕТОДА МНОЖИТЕЛЕЙ ЛАГРАНЖА— РЕКЛАМНАЯ КАМПАНИЯ Рассмотрим ситуацию, в которой средства предприятия делятся между различными производственными отделами.
Каждый из этих отделов представляет свою оценку возможной прибыли в виде функции от производства своего индивидуального продукта. В таких случзях можно встретиться с кривыми индивидуального дохода, имеющими типичную Б-образную фор. му, приведенную на рис. 20. '1т обы получить функцию полезности нужного вида, используем урзвнение ту Прппввпвантввннтнв впмнпмнпаатп х г;(х)=п;11 — (1 — е р )н], Рис. 20. (2.58) Здесь пт — максимально возможнын доход *), которыя может быть получен на рынке, а а; — уровень рыночной конкуренции. Малые ассигнования дают небольшие шансы на *) Имеется в виду доход прн наличии неограниченно больших средств. (Прим. рвд,) 21] НРименение метОдА множителен лАТРАнжа Ят где к — расходы на производство и у — расходы по рекламе.
Из свойств этого уравнения вытекает, что без производства не может быть получена никакая прибыль, каковы бы ни были расходы на рекламу; но в сочетании с производством, чем больше реклама, тем больше прибыль. Наша задача; выбрать х; и ун 1=1, '2... Ф, так, чтобы максимизировать функцию )с = Х~ г; (хн у,) (2.60) по всем хг н ум удовлетворяющим условиям ~ хг(х, л ,У, Уг ~У (2.61) хп уг )О. 1 успех, в то время как выделение большого количества производственных средств приводит рынок в состояние насыщения. Обсуждение связанных с решением такой задачи вычислительных вопросов и числовые результаты содержатся в 223.
Мы видели, как задача максимизации, включающая один тип ресурсов и Д1 технологических процессов, приводится к последовательности одномерных задач максимизации. Но представим себе, что надо распределить несколько типов ресурсов; это означает, что общие затраты являются функциеи нескольких переменных. Тогда мы должны иметь дело с последовательностью функций нескольких переменных и встретиться со всеми вычислительными трудностями, которые естественно при этом возникают.
В качестве примера такого процесса рассмотрим следующую ситуацию. Пусть упомянутое выше предпоиятие наряду с ограниченным производственным оборудованием имеет также ограничение на расходы по рекламе. Лоход от конкретного распределения ресурсов принимается равным г;(х, у)=О;[1 — (! — е 'гл"+")л], (2.О9) 88 многомвяныв пяоцвссы глсппввдвлвния [гл. и Полагая гл(х, у) равной максимуму гсл в этой обласги, обычным путем получим функциональное уравнение гм(»' У)= шах [гм(»л' Ул)+ гм !(» л!т У Ул)!. 22.
МЕТОД МНОЖИТЕЛЕЙ ЛАГРАНЖА Как извеспю, задачи с большим числом измерений легко исчерпывзют возможности пзмяти вычислительной машины и требуют чрезмерно большого времени. Хотя достоинством метода динамического программирования является существенное понижение размерности, мы видели, что трудное.!и, сопутствующие функциям большого числа переменных, все же могут оказаться непреодолимыми.
Использование множителей Лагранжа приводит во многих случаях эти задачи к доступному для расчетов виду. Предположим, что мы имеем неограниченные возможности расходования средств на рекламу, что каждый доллар, затрзченный на рекламу, имеет результатом Л долларов, вычитаемых из нашего общего дохода. Ясно, что, если Л равно нулю, мы будем рекламировать безудержно, в то время как если Л велико, мы вовсе откажемся от рекламы.
Каждый выбор Л м дает некоторое значение ~у; между 0 и со, гдеу;=у;(Л) г= ! представляет собой максимизирующий выбор Ун Если мы выберем Л так, чтобы ~у!=у, то, как указывзлось выше, мы решим тем самым исходную задачу с двумя условиями без явного рассмотрения второго условия.
функциональное уравнение, связанное с задачей максимизации функции м Ф ~ гг(хн у;) — Л~~ уь имеет теперь вид !=-! !=! (х)= шах [гм(х у ) — ЛУ, +гт !(х — х )[. (2.63) а у (со Исходная задача решается по следующей схеме; фиксируем Л, решаем одномерную задачу, проверяем полученное значение Ч'Ун подбиРаем Л так, чтобы сделать !"У! пРиблизи- 23) Рвзультлты Вычислвннй тельно равной у, решаем задачу для нового значения л.
По!Поряем этот цикл, пока не найдем !, для которого ~',у; =у. Обычно бывает достаточно трех или четырех итераций, в зависимости от усилий, затрачиваемых для определения 1. на каждой итерации. Подробно этот итеративный процесс будет обсуждаться в следующем параграфе.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
