Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 16
Текст из файла (страница 16)
Один двумерный расчет даст доходы и оптимальные политики для всех комбинаций значений х и у, не превосходящих своих верхних границ. В процессе такого решения мы вычисляем значения функции двух переменных в некоторой ойлалпп плоскости (х, у). Используя метод множителей Ла!ранжа, мы находим пространственную кривую, которая дает доходы и политики в точках !гривой на плоскости (х, у) для каждого конкретного Х.
Несколько значений 1. дают несколько таких кривых в пространстве. По этим кривым можно получить общий вид функции двух переменных. Этот метод будет проиллюстрирован в следующем параграфе. 29. РЕЗУЛЬТАТЫ ВЫЧИСЛЕНИЙ Рассмотрим сначала простейший тип процесса динамического программирования, обсуждавшегося в 9 21, — процесс с одним видом ресурса. Программирование тзкой задачи для быстродействующей цифровой машины, такой как Пжонниак или ИБМ-709, может быть с использованием языка Фортран выполнено за пару дней.
Блок-схема программы для этой задачи показана на рис. 21. Оптимальное распределение !00 единиц ресурса по 20 процессам потребует около 10 мину~ машинного времени. Результаты распределения для случая, когда максимальные возможные доходы от каждого процесса тй (1 = 1, 2, ..., 20) принимают значения 1, 2, ..., 20 (определяемые потенциальным рынком) и конкуренция пропорциональна объему рынка (ат =ттт = !), приведены в таблице 2.3. Таблица 2.3 !О 11 12 13 14115 16 17 Пргшесс 18 19 20 от 1 до 9 Распределение О МПОГОМВРНЫВ ПРОИЕССЫ РАСПРВДВЛВВИЯ ГГЛВ. !Л Иьюислипгь (или свесит/ эг(лч ~2(Х~/гг-г(Х ин/ //ет /г/' // х~ =Ху л/+/ лг //гт г2а /1 /,' (Х/ Ю а,(Х/ Х+1 Х //ет Х=.гмьг г'г 1 г' //ергйти е слгйугощеггу праигссу Рнс. 21.
Блок-схема программы для одномерной задачи распределения ресурсов. /Гьщислить гиагеьив /,'(Х/ йлл слгйующего гпопеиип Х //оисимиэироеапэь сумму прибили ьт г-го проиесса и прибщ/ги тп остольпмг (/ -// прас/всвое йапомпить тпеепг и сготеепгстеуп/щу ьэ г птимольпуле палигп//иу (/гпа~пь Оптимольпщй йогой ///(Х/ Расорсделепиеа (Х //ет Яа ь юоп 23) ппзтльтлты вычислвний Рис. 22 показывае~, что хотя индивидуальные функции дохода в высшей степени пелинейны, оптимальная функция дохода для 20 процессов является почти линейной функцией от суммарного производства. Рассмотрим теперь модель производства — рекламы Я 21 — 22. Используя л~етод множителей Лагранжа, мы получим для каждого фиксированного л одномерную задачу.
~п г00 ч+ ': ч100 есФ 07 йй ф ~~ л0 о и 0 ар 40 00 00 Г00 Коплглгтва рогллг0глмеми испол рссуглл Рис. 22. Общая прибыль как функция количества ресурсов при использовании опти- мальной политики. При этом для 0(х(200 вычисления занимают около двух минут на один процесс.
Переписывая уравнение (2.63) в виде .10 (х) = шах ~ тпах (гл. (хлл ух) — Хул) -Г +ут,(х — х,))= шах ял,(х )+1 ~(х — х )), "гг " (2,64) мы видим, что можно сначала получить доход в виде функции от х,, а затем максимизировать по х,. В следующем параграфе мы разовьем эту идею в деталях. Время вычислений значительно сокращается за счет доказательства того, что если у, ) 0 максимизирует г, — лу , для х= х , то для х) е, максимизирующее значение у будет меньше, челт ул в) *) Это — следствие знания структуры функции, вхбдящей ° (2.63).
Сьь приложение! О. Гросса. МНОГОМЕРНЫЕ ПРОНЕССЫ РАСПРЕДЕЛЕНИЯ [ГЛ. Н На Рис. 23 нзобРажена фУнкциа гм(х ., Ул) — ХУМ как функция у при двух фиксированных значениях х ., хмг)хЯ'. ф ч ьч !т х гст уо хо" Финсирована хгю н Финсиравано хна хсн хоа .т а Рис. 23. Лля фиксированного ! оптимальные ассигнования нв рекламу ул усыаают, когда ассигнования на произволе!вол!с возрастают.
На рис. 24 мы видим, как с изменением х изменяется х ут для оптимально выбранных у; при фиксированном 1. Разрывы происходят за счет того, что при малых х увеличение х имеет результагом оптимальное распределение, включаюшее дополнительный процесс с ненулевой ин1енсивностью и скачок в ассигнованиях на рекламу. Лля каждой точки кривой в плоскости (х, у), аналогичной приведенной на рис. 24, носинсааоо виттсосннас ос косов в вычисления дзют также доход, связанный с оптичальныч рас- Рис. 24. Расходы на рекламу, если вспользтется оптимальная прсделениемхединнц для пелен политика,при фиксированном у., производства и у единиц для целей реклзмы.
После того как получено несколько кривых для различных )., Мы можем начертить двумерную функцию дохода (рис. 25). Мы проанализировали двумерный процесс. Прямой анализ ~акого процесса методом двумерного динамического программирования потребовал бы таблиц функции из 200'с(600 = = 120 000 значений и, следовательно, сотен часов машинного времени. Применение метода множителей Лагранжа позволило нам получить эквивалентный результат приблизительтю за три часа. При этом было использовано 1000 ячеек памяти.
241 ВЫЧИСЛЕНИЕ МНОЖИТЕЛЕЙ ЛАГРАНЖА 24. ВЫЧИСЛЕНИЕ МНОЖИТЕЛЕЙ ЛАГРАНЖА В случаях, когда множитель Лагранжа разумно интерпретировать как цену и когда целевая функция н управляемая переменная заданы в денежном выражении, приближенное значение безразмерного множителя часто можно найти с помощью методов анализа цены, не прибегая к быстродействующим' машинам Ч "~Г777 77777 7777Р77лллху»тллл Рис. 25.
Общая прибыль, получаемая при оптимальном распределении Различных комбинаций начальных ресурсов, Однако в большинстве случаев множитель, будучи все же сценой», измеряет обмен на первыЙ взгляд несоизмеримых количеств. Например, в задаче о запасных частях для самолета с ограничениями по об»ему н по весу груза исключение ограничений по объему с помощью множи~еля Лагранжа приводит к тому, что этот множитель приобре~аег невол образимую размерность «стоимость просгоя7'кубическиЙ фут». Чтобы определить априори числовое значение множителя, нам нужно было бы узнать, насколько дополнительная единица объема уменьшит ожидаемые издержки от нехватки при оптнмальнои политике.
Очевидно, знание этого позволило бы Решить исходную зздзчу. 94 многомвиныв пвоцяссы ялспгвдвлвния [гл. и ~ и,(х;) (2.66) по всем хн удовлетворяюшим условиям Л' ;5', х,.=х, ! ! (2.66) (2.67) Предположим далее, что очевидная двумерная постановка (х, й)=шах[у(хн)+Ум,(х — х, Ь вЂ” Ь(х,))], (2,68) где 0(хм(х и йч(хм)-%.й, заменена одномерным вариантом: (х) = шах [д (х,) — Цг .
(х ) + Ум, (х — х )), (2.69) Я где ),— множитель Лагранжа, который надо определить так, чтобы для максимизируюших х; выполнялось условие (2,70) Никаких определенных рецептов для первоначального выбора ), нет. Разумное угадывание должно быть основано Мы разрешим эту дилемму итеративным способом.
Будем последовательно угадывать значение множителя, пока не найдем правильного. Это истинное значение является ценой, приводяшей к оптимальному решению, в точности удовлетворяюшему ограничению задачи. Рассмотрим процесс фактического угадывания множителя. Так как каждое угадывание означает полное решение задачи динамического программирования, то полезно затратить некоторые усилия на априорный анализ этой операции.
Чтобы сделать рассмотрение конкретным, предположим, что мы решаем задачу максимизации функции 24) Вы'(виляния множитвлви лАГРАнжА на специфике задачи. Однако во многих случаях существует эффективная схема для третьего и последующих приближений. Она основана на ннтерполяционной формуле. Если уже испробованы два значения )ч то можно вычислить два множества значений по таблице 2.4. Таблица 2.4 оптинальнаа палатина 1к.т тт ГА,~М Еигкр Тогда, зная ), Х, и соответствующие значения 2; 7т(хт), можно попытаться использовать эти данные, чтобы вычислить для которого ~Ч~ лт (хт) будет равна л.
Если значения ~Ч'„)тт(хт) обозначены соответственно через ло и ттт, то формула для расчета имеет вид (2.71) Если вычислены более чем два значения Х, то можно использовать два последних из них или воспользоваться более точной интерполяционной формулой. Обычно оказывается возможным априори определить результат выбора Х= О. Эту информацию можно использовать, чтобы не тратить времени и сил на фактическое вычисление. Если такой возможности нет, может оказаться необходимым начать вычисление с двух произвольно выбранных значений.
После того как использовано линейное приближение для нахождения т,а, может оказаться удобным употребить все тРи РезУльтата дла нахождениа Аа с помощью кУбического уравнения. Оправдано или нет дополнительное программирование, требуемое для этой весьма сложной интерполяции,— должно определяться объемом задачи. Наконец, оказалось удобным не хранить информацию о политике, полученную при предварительных вычислениях, имеющих целью определить истинное значение множителя. После того, как истинный множитель найден, вычисление 96 многомввныв пвоцвссы Рлспведвления (гл. и повторяют, записывая на магнитной ленте или перфокар!ах таблицы оптимальных политик. Так как вывод результагсв, лаже на ленту, страшно замелляет работу вычислительной машины, необходимость повторения одного вычисления не превращает эту схему в неэффективную.
Во время вычисления при фиксированном ) строится таблица оптимальных зна» чений ~ 7»!(х;) = Н»(х), так же как и обычная таблица„у»(х). 1=! Эта таблица »кумулятивная», она пополняется на каждом шаге с помощью формулы Н» (х) = Ь» (х») + Н„, (х — х„), (2.72) где х„, — как обычно, макснмизнрующая политика, связанная 9 рекуррентным соотношением у»(х)=шах!в»(х»)+~» !(х — х»)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
