19. Метод сопряженных градиентов.

Метод является методом первого уровня. Предст собой модификацию метода наискорейшего спуска (подъема) и автоматически на каждой итерации учитывает особ-ти целевой ф-и, ускоряя сходимость. Описание метода:

Шаг 0.Выб-ся точка начального приближения х^→(0), точность решения ε>0, вычисл-ся направление поиска S^→(0)=▼f(х^→(0)).

Шаг к: а)находится min (max) ф-и f(х^→) на прямой, проведенной из точки х^→(к-1) по напр-ю S^→(к-1).Найденный min (max) опред-ет очередную точку к-го приближения х^→(к), после чего опред-ся напр-е поиска S^→(к) по ф-ле:

S^→(к)=(▼f(х^→(к)) + S^→(к-1)) (|▼^Тf(х^→(к))▼f(х^→(к))| / | ▼^Тf(х^→(к-1))▼f(х^→(к-1)) |).

Алгоритм завершает работу как только вып-ся | х^→(к)-х^→(к-1)|< ε

В кач-ве решения берется посл. приближение х^→(к).

23. Базовые условия для задачи Дин.П.

1. «Отсутствие последействия»-сост-е с-мы S_k в конце к-ого шага завис только от её сост-я в начале шага и управляющего воздействия на этом шаге:

S_k=φ_k(S_k-1,X_k),k=1,¯n, (1)

Ур-ние (1) наз. ур-ем состояний и д.б. задано или получено перед реш-ем задачи.

2. «Аддитивность целевой ф-ии». Эфф-ть проведения всей операции в целом = сумме эфф-тей ее элементарных операций:

W=F(S₀,X)=∑ⁿ_k=1w_k=∑ⁿ_k=1f_k(S_k-1,x_k), (2)

где w_k=f_k(S_k-1,x_k) – поазатель эфф-ти упр-я x_k на к-ом шаге.

20. Метод Ньютона.

Явл-ся.методом 2-го уровня. В основе метода лежит формула Тейлора и тот факт, что ▼f (х^→) в точке экстремума =0

Т.к.экстремум находится в стац.точке, то для его опред-я необх найти эту точку, решив с-му ур-ний,опред соотнош-м: ▼f (х^→)=0. это можно сделать методом Ньютона –Рафсона. Описание метода:

Шаг 0. Выбир-ся начальное приближение х^→(0), точность решения ε>0.

Шаг к: а) вычисляется очередное приближение х^→(к) по формуле:

х^→(к)= х^→(к-1)-Н^-1(х^→(к-1)) ▼f(х^→(к-1))

где Н – матрица Гессе f(х) в точке х^→(к-1).

Б)проверяется критерий останова: |х^→(к)-х^→(к-1)|<ε. Если кр.вып-ся, то алгоритм заканчивает свою работу и в кач-ве решения берется последнее приближение х^→(к)

21. Метод Ньютона-Рафсона.

Явл.методом 1-го пор. Предназначен для реш-я СНЛУ: g₁(x^→)=0, g₂(x^→)=0,….,g_n(x^→)=0,(1), в кот.число уравнений = числу неизвестных. В частности этот метод м.б.применен при поиске стац.точек целевой ф-и, когда необх решить сист.ур-ний, задаваемую соотн-ем: ▼f(х^→)=0. Обосн-е метода:

Шаг 0: Выб-ся точка начального приближения х^→(0), точность решения ε>0

Шаг к:

а)выч-ся очередное приближение: х^→(к)= х^→(к-1)-Rg^-1(х^→(к-1)) g^→ (х^→(к-1)), где Rg^-1(х^→(к-1))-матрица Якоби, g^→ (х^→(к-1)) – вектор ф-ии g(х^→) в точке х^→(к-1), компонентами кот.явл-ся ы-ии, заданные в левых частях исходной сис-мы уравнений

б) проверяется критерий останова: |х^→(к)-х^→(к-1)|<ε. Если кр.вып-ся, то алгоритм заканчивает свою работу и в кач-ве решения берется последнее приближение х^→(к)

22.Постановка задачи Динамического программирования (Дин.П.)

Дин.П.-совок. моделей и методов оптимизации сложных операций путем их разложений на сов-ти более простых операций.

Постановка задачи Дин.П.

Пусть операция над некот. сис-мой пред. собой совок. из n более простых операций. На к-ом шаге происх переход с-мы из состояния S_k-1 в состояние S_k под возд-ем x_k.

S_k-1→S_k

Начальное сост-е S₀ и конечное сост-е S_n с-мы заданы.

Треб-ся найти такое оптим упр-е X^*Т=(x^*_1,x^*_2,…,x^*_n) всей многошаговй операции в целом,т.е.решить задачу:

W=F(S₀,X)→ max, X€D

Где F(S₀,X)-показатель эфф-ти (целевая ф-я ) задачи Дин.П.

24. Принцип оптимальности Беллмана.

В усл-ях отсутствия последействия и аддитивности целевой ф-ии принцип Беллмана звучит след. образом: каково бы ни было сост. сис-мы перед очередным шагом, упавление на этом шаге выбир-ся так, чтобы суммарная эфф-ть данного шага плюс оптимальная эфф-ть всех последующих шагов в целом была бы max.