Принцип - оптимальность - беллман
Cтраница 2
Алгоритмы динамического программирования применительно к решению задачи с критерием (5.66) и условиями (5.65) базируются на принципе оптимальности Беллмана, который формулируется следующим образом. [16]
Рассуждения, которые мы провели, показывают глубокую связь между марковскими процессами и процессами, удовлетворяющими принципу оптимальности Беллмана. Уравнение (1.9) является выражением этого принципа для аддитивных функций. Однако метод, использовавшийся для вывода этого уравнения, может быть применен и к немарковским процессам-тем, которые в своей исходной постановке не удовлетворяют принципу оптимальности. [17]
 |
Сетка, используемая при поиске оптимальной трассы. [18] |
Эта задача в сеточной постановке относится к задачам динамического программирования, а оптимальная трасса определяется в соответствии с принципом оптимальности Беллмана: оптимальное поведение обладает тем свойством, что, каково бы ни было первоначальное решение, последующие решения должны составлять оптимальное поведение относительно состояния, получающегося в результате нового решения. [19]
 |
Схема к выбору оптимальною трассы с использованием последовательного анализа вариантов. [20] |
Действительно, так как на каждом шаге процесса осуществляется отбраковка бесперспективных или неконкурентоспособных пробных путей в соответствии с принципом оптимальности Беллмана, то и конечной точки трассы достигнут только оптимальные или же близкие к ним по стоимости пути. Достоинством изложенного метода является то, что надстройка пробных путей проводится в соответствии с расположением группы узлов. [21]
Для ее решения применим метод последовательного анализа вариантов, основанный на следующем принципе оптимальности [82, 84], представляющем собой обобщение принципа оптимальности Беллмана [ 12J в динамическом программировании. [22]
Представ-ление об этом классе задач, в настоящее время уже достаточно полное, складывалось главным образом по мере накопления опыта практического применения наиболее распространенных методов оптимального управления - принципа максимума Понтрягина, принципа оптимальности Беллмана и модификаций классических методов - к разнообразным задачам из техники, экономики и других областей. При этом трудности, возникавшие в тех или иных ситуациях, таких как отсутствие искомого оптимального режима в классе сравниваемых, множественность решений, отвечающих необходимым у слови-ям, неприменимость известных достаточных условий, казались первоначально случайными и легко устранимыми путем несущественных количественных изменений в постановке задачи. Однако частое повторение подобных ситуаций позволило выявить определенные закономерности их возникновения и соответствующие им внешние признаки в постановках задач, которые делают эти задачи нерегулярными с точки зрения общих методов. Эти трудности имеют глубокие причины: присутствие в системе основных связей - дифференциальных уравнений или дискретных цепочек - скрытых пассивных связей, исключение которых не меняет искомого решения. В таких случаях, как говорят, задача переопределена, т.е. в определенном смысле некорректна. Оказалось, что подобные задачи - далеко не экзотика, а, напротив, столь же типичны, если не более, для практики, как и регулярные задачи, и поэтому требуют специальных подходов для их эффективного исследования. [23]
Представление об этом классе задач, в настоящее время уже достаточно полное, складывалось главным образом по мере накопления опыта практического применения наиболее распространенных методов оптимального управления - принципа максимума Понтрятина, принципа оптимальности Беллмана и модификаций классических методов - к разнообразным задачам из техники, экономики и других областей. При этом трудности, возникавшие в тех или иных ситуациях, таких как отсутствие искомого оптимального режима в классе сравниваемых, множественность решений, отвечающих необходимым условиям, неприменимость известных достаточных условий, казались первоначально случайными и легко устранимыми путем несущественных количественных изменений в постановке задачи. Однако частое повторение подобных ситуаций позволило выявить определенные закономерности их возникновения и соответствующие им внешние признаки в постановках задач, которые делают эти задачи нерегулярными с точки зрения общих методов. Эти трудности имеют глубокие причины: присутствие в системе основных связей - дифференциальных уравнений или дискретных цепочек - скрытых пассивных связей, исключение которых не меняет искомого решения. Оказалось, что подобные задачи - далеко не экзотика, а, напротив, столь же типичны, если не более, для практики, как и регулярные задачи, и поэтому требуют специальных подходов для их эффективного исследования. [24]
Методы анализа и решения подобного типа задач называются динамическим программированием. Принцип оптимальности Беллмана обычно реализуется в виде рекуррентного функционального уравнения, решение ( Которого позволяет получить и решение исходной задачи. [25]
В основе метода динамического программирования лежат принцип оптимальности Беллмана и вытекающее из него функциональное уравнение, позволяющее свести решение многомерной задачи оптимизации к решению последовательности одномерных оптимизационных задач. Принцип оптимальности Беллмана формулируется следующим образом. Оптимальное поведение обладает тем свойством, что, каково бы ни было первоначальное состояние и решение в начальный момент, последующие решения должны составлять оптимальное поведение относительно состояния, полученного в результате первого решения. [26]
Вместо того чтобы оптимизировать сразу весь реактор по всем переменным, можно провести оптимизацию отдельно по слоям, начиная с последнего, при условии, что каждый слой содержит лишь несколько варьируемых переменных. Воспользуемся принципом оптимальности Беллмана [11] и поясним его сначала на примере че-тырехслойного реактора, а затем сформулируем в общем виде. [27]
Оптимальное значение управляющей переменной определяется состоянием системы в начале этого этапа и конечной целью управления и не зависит от эволюции системы на предыдущих этапах. Последнее условие соответствует принципу оптимальности Беллмана и является условием применимости динамического программирования. Динамическое программирование не является методом в строгом смысле, а является некоторой общей стратегией, заключающейся в том, что исходная задача становится задачей многоэтапной оптимизации, каждый этап которой, начиная с конечного, использует информацию об оптимальном решении на предыдущем этапе. Эта информация в наиболее явном виде может быть представлена в виде функционального уравнения, связывающего значение критерия качества на оптимизируемом этапе с оптимальным значением критерия качества на предыдущем этапе. Управляющие переменные могут быть векторными величинами. [28]
В комбинированных алгоритмах могут применяться как общие правила отсева, применяемые в методе ветвей и границ ( при поиске точных и приближенных решений), так и правила отсева, использующие специфику задачи. Примером может служить отсев с использованием принципа оптимальности Беллмана для задачи коммивояжера. Разумеется, применение отсева с учетом специфики задачи требует дополнительных вычислительных ресурсов. [29]
 |
Расчетная сеть, используемая при поиске оптимальной трассы. [30] |
Страницы: 1 2 3