Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 7
Текст из файла (страница 7)
! ! функция г (х) выражает оптимальный доход почучаемый от распределения количества ресурсов х по М процес- В двух частных случаях элементы последовательности й' одномвгиые пгоцвссы Рлспеедвления !гл. ! !г .(х)) принимают особенно простои вид. Очевидння Ум (0) = О, Аг = 1, 2, ..., (1.19) если д;(0)=0 для лк.бого 1, что является разумным предположением.
Также, очевидно, Д (х) = д, (х) (1.20) для х) О. Легко найти рекуррентное соотношение, связывающее (х) и ~л, (х) для произвольных Х и х. Пусть х „ 0 «= х ( х, — количество ресурсов, назначенное для М-го процесса. Тогда, каково бы ни бьио точное значение х ., мы знзем, что остающееся количество ресурсов х — х будет использовано так, чгобы получить максимзльныи доход от остающихся Х вЂ” 1 процессов. Так как этот оптимальный доход от распределения количества ресурсов х — х, по Аг — 1 процессам по определению есть Г ч ,(х — х ,), назначение х . для АГ-го процесса приводит к общему доходу д (х, ) + г ч, (х — х,) (1.21) для модели с М процессами.
ясно, что оптимальным будет таков выбор х „когорыи максимизирует эту функцию. Таким образом, мы получаем основное функциональное уравнение; (х)= так [у (хм)+У~,(х — х .)) (1.22) 0 к я для %=2, 3, ..., хтьО, причем г,(х) определяется согласно (1,20). 1!.
ПРИНЦИП ОПТИМАЛЬНОСТИ В ходе предшествующего изложения мы применили очень общий метод, известный под названием принципа оптимальности. Принцип оптимальности. Оптимальное поведение обладает тем свойством, что, каковы бы ни были первоначальное 12] пгямой вывод Огнкционлльного гилвнвния зт состояние и решение в начальный момент, последующие решения должны составлять оптимальное поведение относительно состояния, получающегося в результате первого решения. Вся наша дальнейшая работа будет основана иа применении этого простого свойства многошаговых процессов решения. В этом частном случае принцип без труда устанавливается путем соединения индукции и доказательства от про!ивного.
!2,Г1РЯМОЙ ВЬ~ВОД ООНОВНОГО ФУНКЦИОНАЛЬНОГО УРАВНЕНИЯ Лля тех, кто поначалу не склонен доверять принципу о!пимальности, дадим следующий вывод (1.22). Замечая, что шах = и!ах [ п!ах ], (1 23) к!+«я+...+х =к О к к к!+«х-(-.,-1-х =х — к х О 4 х!)О мы можем написать цепочку равенств Гх(х) = шах [д,(х, )+д,„!(х,,)+ .к!+хг+, +х =х хгМО +...
+ д! (х,)] = щах [ шах (д,(х )+ Вах х к!+«О+...х =х — х лг- Х вЂ” 1 Л' «!~о тКм !(хл !)+ +зг(х!))]= шах [д,(х )+ О к х + шах (дм ! (хм !) -]-... + д(х!))]= «1+Ох+...+.к =х —.к м — 1= х к,.>О щах [д (хх)+~х !(х — х )], О х, к что и дает требуеяаый результат, 38 одномввныв пяоцяссы влспввдзлвния [гл, ~ 13. ОБСУЖДЕНИЕ Рекуррентное соотношение (1.22) дает теоретический метод для индуктивного получения последовательности [ум(х)[, если только у,(х) известна. Действительно, у, (ж) определяет уя(х) и т.
д. Важный вопрос, который мы должны поставить в первую очередь, заключается в оценке выполнимости нового метода; затем нужно установить, преодолевает ли он затруднения, на которые наталкиваются обычные методы. Как мы увидим, новый метод является гибким и действенным. Его силу мы продемонстрируем на примерах. Известный опыт позволяет, таким образом, утверждать, что метод динамического программирования дает быстрое, простое и правильное решение обшей задачи, поставленной в $ 3. 14. ВЫЧИСЛИТЕЛЬНАЯ СХЕМА Рассмотрим теперь внимательно вычислительную сторону использования рекуррентного соотношения (1.22) для определения последовательности [у .(х)[. Хотя вначале мы будем обсуждать совсем наивные и прямые методы, впоследствии мы изложим ряд более тонких подходов.
Так как мы отказались от классического анализа и тем самым от аналитических представлений, мы должны сначала уяснить, что значит знать функции л,(х), 1 = 1, 2.. ., и что значит вычислять элементы последовательности [/ (х)[. Под функцией, определенной при х ~ О, например под д;(х) или у;(х), мы будем понимать множество значений, принимаемых, когда х пробегает все неотрицательные значения.
Это — обычное определение. Разумеется, невозможно протабулировать все значения функции и даже достаточно большое конечное множество значений. Следовательно, остается использова~ь какой-нибудь тип интерполяционной схемы, которая позволит нам восстанавливать общее значение, исходя из немногих аккуратно выбранных значений. Искажение, связанное с выбором значений, которые мы будем табулировать, чтобы изобразить функцию, очень мало.' Практический опыт, требования к памяти и точности, наконец, стоимость вычислений играют важную роль прн этом выборе. Первоначально мы рассмотрим одну прошую и очевидную идею, а позже обсудим более совершенный метод.
14) вычислитвльнля схимА Чтобы задагь в интервале 1О, х„! все множество значений Г (х), воспользуемся значениями, принимаемыми в конечном числе точек решетки х=О,Ь,2Ь,...,Ю вЂ” х, (1.24) 3атем постулируем, что каждый элемент последовательности (х)) вычисляется и табулируется в каждой из этих точек и только в этих точках.
3начення Уч(х) для ж, отличных ог точек решетки, будут получзться и~перполяггией. '1'ип используемой интерполяции будет зависеть от точности, которая требуется, и от времени, необходимого для достижения этой точности. Если /7Ь ( х ( (тг + 1) Ь, (1.25) то простейшее приближенное значение Г (х) получается в виде (х) =У, (ГгЬ). (1.26) Следуюшее простейшее приближение доставляется линейной интерполяционной формулой Ум(х) =у (Ггд)+(х — УгЬ) . (1.27) В нужных случаях можно использовать более точные интерполяционные формулы, основанные на полиномах более высокой степени. ( В задаче распределения, сформулированной выше, вполне разумно разрешить переменной х изменяться на том же самом множестве точек, на котором изменяется х.
Г!оэтому в процессе максимизации х может принимать только зна- Ю чения, указанные в (1.24). Максимизация в (1.22) выполняется путем непосредственного перебора случаев и сравнения величин без каких-либо услуг со с~проны обычного анализа. В последуюших главах мы обсудим методы, которые нередко дают громадное упрогцение процедуры поиска и, следовзтельно, большую экономию вычислительного времени. В данный момент, однако, мы исследуем общий случай, в котором рассматриваемые функции не обладают той особой структурой, которая может быть использована для облегчения поиска. 40 одномвяныв ппоцвссы ялсппидвлвния [гл.
> Обсудим нзши действия более обс>оя~ельно. Когда %= 1, функция у>(х) немедленно определяется равенством (1.28) у'> (х) = и> (х). Множество значений [у>(>тЛ)[, /»=0,1,...,)с,'с этого момента хранится в паня~и вычислительной машины *), и мы в состоянии вычислить т» (х) с помощью условия (1.22) для %=2, именно: .г» (х) = п>ад [~» (х,) +г > (х — х,)[, (1.29) О х» х где х принимает только значения О, Ь, 2Л..,,.
Щ. Так как никакой процесс перебора не может осуществить максимизапию на непрерывной области значений, мы долн<ны заменигь отрезок [О, х[ дискретным множеством. Тогда соотношение (1.29) заменится аппроксимирующим соопю>пением г»(х) = шад [д»(Ы) — ';- г>(х — Ут а)[. (1.30) >а.=о, >, ..., Я1 Функция д» (х) в виде последовательности >8» (Ы)[ также крацится в памяти вычислительной машины. Процесс л>аксимизации начинается с того, что машина вычисляет нелнчины >(» (О) -~- У> (х) и д» (Ь) —',-У> (х — Ь) и затем сравнивает их, удерживая ббльшую в памяти.
Далее вычисляется у»(2Ь)+ +г>(х — 2Ь) и сравнивается с большей из этих величин. Новую ббльшую величину снова сохраняем в памяти, и т. д. Процесс продолжается до тех пор, пока >т не примет все допустимые значения. В результате мы получим у»(х) для данного з>»ачения. х. В ходе этого процесса поиска вычислительная машина определяет не только значения у»(х) при х=О, »а, ..., )с»ч но также значение (или значения) х„при котором в (1,29) достигается максимум. Предположим пока, что абсолютный максимум принимается только при одном значении х.
Общий случай мы обсудим ниже. Так как это единственное значение будет зависе>ь от х, обозначим его х,(х). Вычислительная машина запоминает как х,(х), так и у»(х) для каждого х. х) Если нс оговорено противное, «память» бтдет отождествлиться с «быстродействующей памятью» (оперативной памнтью). нввдинстввнность максимгиа 16) Таблица 1,! я,оо ~ /а|.н А(ю хню О а 2Л В этом случае у,(х) =д,(х) и х,(х)=х, Указанная таблица дает решение двухшаговой задачи максимизации в следующем смысле. Если задано частное значение х, мы просматриваем столбец значений х„(х) до тех пор, пока не наткнемся на соответствуюгцее вяз~ение ха.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
