55.Градиентный метод решения задачи нелинейного планирования.
Пусть целевая функция имеет вид:
.
И задача оптимизации задана следующим образом:
Основная идея
метода заключается в том, чтобы идти в
направлении наискорейшего спуска, а
это направление задаётся антиградиентом
:
где λ[j] выбирается
-
постоянной, в этом случае метод может расходиться;
-
дробным шагом, т.е. длина шага в процессе спуска делится на некое число;
-
наискорейшим спуском:
Алгоритм
-
Задают начальное приближение и точность расчёта
-
Рассчитывают
,
где
-
П
роверяют
условие остановки:
-
Если
,
то j
= j
+ 1 и переход
к шагу 2. -
Иначе
и
останов.
Иллюстрация последовательных приближений к точке экстремума в направлении наискорейшего спуска (красн.) в случае дробного шага. Синим отмечены линии уровня.
56.Метод динамического планирования. Область применения и содержание.
57.Рекурентное соотношение методов динамического планирования.
58.Принцип оптимальности Белмана на примере задачи.
Смысл подхода, реализуемого в динамическом программировании, заключен в замене решения исходной многомерной задачи последовательностью задач меньшей размерности.
Перечислим основные требования к задачам, выполнение которых позволяет применить данный подход:
Ø объектом исследования должна служить управляемая система (объект) с заданными допустимыми состояниями и допустимыми управлениями;
Ø задача должна позволять интерпретацию как многошаговый процесс, каждый шаг которого состоит из принятия решения о выборе одного из допустимых управлений, приводящих к изменению состояния системы;
Ø задача не должна зависеть от количества шагов и быть определенной на каждом из них;
Ø состояние системы на каждом шаге должно описываться одинаковым (по составу) набором параметров;
Ø последующее состояние, в котором оказывается система после выбора решения на k-м. шаге, зависит только от данного решения и исходного состояния к началу k-го шага. Данное свойство является основным с точки зрения идеологии динамического программирования и называется отсутствием последействия.