Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 8
Текст из файла (страница 8)
Как только это значение наидено, мы приходим к задаче определения оптимального распределения в одношаговом процессе с ресурсами х — ха(х). Вся эта операция поиска может бьжь, конечно, проделана самой вычислительнои машиноя. Продолжая процесс М шагов, можно получгпь решение или в виде аналогичной таблицы, или даже в виде выборов х ., х, н ..., ха хп связанных с каждым значением х. 15.
НЕЕДИНСТВЕННССТЬ МАКСИМУМА Числа, хранящиеся в памяти машины, обычно верны до десяти или более значащих десятичных цифр в зависимости от того, что требуется. Поэтому краине маловероятню, что два значениЯ ха когда-либо дадУт одно и то же максималыюе значение. Тем не менее реальный процесс решения может обладать несколькими оптимальными поведениями, исключающими прут друга.
В некоторых случаях нам необходимо знать лишь максимальный доход и одно из оптимальных повелений; в других случаях очень нужны все оптимальные поведения, дениз, и мы можем расценивать этот результат более высоко ч о, чем определение собственно максимального дохода. В итоге после двух шагов этого процессз мы можем заполнить таблицу, подобную таблице 1.1. 42 олномвеные пвоцвссы Рлспввдвлвння [гл.
~ Кроме того, приближенные оптимальные поведения, которые дают доходы, немного (скажем, на один процент) отличающиеся от действительного максимума, могуг оказаться столь же важными, как и точное решение. Они могут оказаться даже более важными, если нам нужны простые приближения в сложных сигуациях. Эти почти оптимальные поведения можно легко получигь, потребовав, чтобы вычислительная машина удерживала в памяти не только максимальное значение и значение хн которое его дает, но также хн дающие значения в некоторой окрестности максимума.
Это увеличивает требования к лама~и и время вычислений, но не до такой степени, чтобы не использовать идею совсем. 16. ЭФШЕКТИВНОСТЬ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ ПО СРАВНЕНИЮ С ПРЯМЫМ ПЕРЕБОРОМ Поскольку первоначальная непрерывная вариационная задача была заменена дискретной, мы можем разыскивать максимальное значение с помощью простого перебора случаев.
Особого изящества или привлекательности в таком подходе нет, но он может сослужить службу там, где более искусные методы не имеют успеха. Что касается ручных вычислений, условия времени и точности обычно исключают этот метод. Но раз есть цифровая вычислительная машина со своей удивительной скоростью счета, методы перебора оказываются в известной мере осуществимыми. Возьмем некоторые простые процессы распределения и посмотрим, с чем было бы связзно непосредственное освидетельствование всех возможностей. Вля начзла исследуем простую ситуацию, где кажлая из х; можег принимать десять различных значений.
Тогда процесс максимизации с Аг переменными привелег к !Ом различным множествам выборов. Но в этом процессе общее число возможностей в дейсгвительности значительно меньше, так как выбор х „немедленно ограничивает возможное изменение других хн Игнорируем временно этот пункт, Как мы увилим, это не изменит некоторые из наших основных заключений. Для десятишагового процесса мы должны будем тогда обслеловать 10га случаев. Возможно, это кажется не таким уж большим числом, но несложный расчет дает некоторое 16) эввпктнвность дйнамг~чяского пяогялммняовзння ЛВ представление об его истннной величине. Если каждую миллисекунду обследовалось бы одно множество значений хь то всего потребовалось бы 10' секунд, что более 2 1О' часов и, стало быть, есть величина порядка четырех месяцев *).
Это непомерно большое количество времени, чтобы тратить его на численное решение какой-либо задачи, которая представляет действительность так же грубо, как принятая нами. Г!редположим, что мы хотим рассмотреть несколько более сложную задачу, в которой имеется 20 различных процессов. Рассуждая по-прежнему нестрого, положим, что это влечет за собой 10" различных возможное~ей. Так как последняя величина в 10" раз больше 10'", мы видим, что, как бы ни удавалось сокрап1ать время процесса поиска, этот экспоненпиальный рост числа возможностей с возрастанием 1ызмерности процесса сделает перебор случаен невозможным.
Кроме того, мы видим, почему можно так вольно обращаться с общим числом случаев. Если допускается 1ОО нли 1000 выборов для каждой переменной, изменение в порядке величины числа возможностей для десятишагового процесса распределения посредством умножения на 1Ога не влияет существенно на силу нашей аргументации. Но довольно о наивных подходах к задачам оптимизации! Следует четко осознать, что процессы большого масштаба будут требовать как электронных, так и математических средств для своего исследования.
!!очечу же все-такн метод дннзмического программирования дает возможность легко н быстро решать задачи, намного более сложные, чем рассмотренная выше? Как подсказывают предыдущие рассуждения, объяснение этому нужно видеть з зом, что применение метода функциональных уравнений эквивалентно использованию некоторого процесса поиска, который является гораздо более эффективным,чем примитивное обследование всех случаев.
Ключ доставляется принципом оптимальности. Согласно этому принципу, выбрав некоторое начальное х ., мы затем отказываемся от обследования всех поведений, включающих этот частный выбор х „з рассматриваем только те поведения, которые оптимальны для ГДà — 1)-шагового процесса *) В оригинале здесь допущена ошибка, приводящая к оценке в 1О чет. (Прим.
ред.) 44 одномввныв пгоцвссы Рхгпяедялвния 1гл. 1 .с ресурсами х — х,. Згот магический способ позволяет сок. хранить аддитивность, а не мультипликативность числа операций. Время, требуемое для двадцатишагового процесса, теперь оказывается примерно вдвое больше времени, требуемого для десятишагового процесса. !7. НАИНЕ ТРУДНОСТИ МЫ ПРЕОДОЛЕЛИ? В ч 6 мы обсудили главные трудности на пути применения методов классического анализа к задачач максимизации.
Остается теперь рассмотреть, до какой степени метод динамического программирования устраняет эти препятствия. Во-первых, из простого индуктивного доказательства ясно, чго метод всегда дает абсолютный, а не относительный максимум. Во-вторых, заметим, что дополнительные условия того типа, которые мы ввели, скорее упроптают задачу, нежели усложняют ее. Любое условие вида а! =. х =' ди ограничивающее число возможностей на каждсм н!аге, упрощает процесс поиска и, следовательно, уменьшает вычислительные усилия. Другими словами, чем меньше поведений имеешься на каждом !паге, тем быстрее вычисления. Точно такие же доводы применимы к задачам максимизации по дискретным множествам.
Чем меньше число допустимых выборов, тем проще вычисления. Просзейшими задачами будут те задачи, где каждое х! может принимать только нем!огне значения, скажем, 0 или 1. Так как мы употребляем только табличные значения рассматриваемых функций, точная аналитическая структура последних не представляет для нас никакого и!переса. Это означает, что наличие и свойства проиаводных любого порядка не должны касаться нас вообще и линейность не должна быть нам помехой.
Вместе с тем обратим внимание, что, когда обнаруживаются некоторые струк~урные особенности, как, например, выпуклость, вою!утость, монотонность и т. д„ .они могут быть весьма эффективно использованы для упрощения процесса поиска. Вопросы этого рода будут всесторонне обсуждены в последующих главах.
11аконец, мы подходим к вопросу об анализе чувствительности, поднятому в ~ 8, Двумя весьма важными параметрами в процессах распределения знакомо~о нам типа являются количество наличных ресурсов и число процессов, которые 17) км<пв тяхдности мы ппподолвли? лб мы можем прнвлелагь. Наше решение, выражаемое при помощи двух функшщ У„(х) и х (х), получается именно как функпия этих основных параметров. Вопросы, которые естественно возникают в ходе теоретической постановки и регнения указанных задач распределения ресурсов, следующие: а) Как доход и поведение зависят от начальных условий? Ь) Каков результат изменения начального состояния при использовании некоторого оптимального поведения? с) Какова выгода от добавления еше одного способа или ог продолжения пронесса еше на один шаг? Не имея поста~очно прозрачного аналитического решения, довольно трудно извлечь из стандартной формулировки информацию этого типа.
Однако формулировка в терминах динамического программирования автоматически включает первоначальную задачу в семейство аналогичных задач, в которых основные параметры х и И принимают значения из некоторых множеств, и это позволяет нам ответи~ь на поставленные фундаментальные вопросы.
Например, в изучаемом пропессе распределения решения находятся для способов, число которых изменяется от 1 до ?тг, и для количеств ресурсов от 0 до х. Следовательно, после того как для Жппагового процессз было получено вычислительное решение, мы можем определить взаимо- обмен между параметром состояния х и числом шагов ?тгдля огромного ряда подзадач.
Так как оптимальныд доход дается как функция основных параметров х и 7!Г, анализ чувствительности автоматически сопутствует решению. Отсюда вытекает, что предложенный нами метод преодолевает все препятствия, о которых мы говорили. Ниже будет показано, почему наряду со всеми этими преимуществами мы тем не менее не имеем шаблонного решения для всех типов процессов распределения. Можно с уверенностью сказать, что все еше существует большая потребность в изобретательс~ве и что остается выполнить много интереснейших исследования, прежде чем можно будет достаточно эффек~ивно рассмотреть значительное число важных процессов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
