6. Одномерный поиск экстремума целевой функции методом сканирования:

Состоит в последовательном исследовании значения критерия оптимальности в ряде точек, принадлежащих допустимой области управления. Среди этих точек выбирается та, которая принимает максимальное или минимальное значение.

Шаг Δ. Перебором с шагом Δ находим max или min значение Q.

Достоинства: всегда находим глобальный экстремум, поиск не зависит от вида критерия оптимальности, простота алгоритма поиска.

Недостатки: большое количество вычислении. Для уменьшения вычислении, вначале шаг Δ увеличивают, находят предполагаемую область , в котором находится экстремум . Потом уменьшают Δ.

Метод деления интервала поиска пополам:

Заключается в том, что в начале определяется значение целевой функции в граничных точках и в середине интервала поиска. Затем находится значение Q в серединах полученных интервалов. Далее локализуют экстремум по трем точкам

Вычисляем до тех пор пока интервал не станет в заданной точности.

Достоинства: гораздо меньше вычислении чем в предыдущем случае.

7. Одномерный поиск экстремума целевой функции методом золотого сечения:

Золотое сечение проводит деление отрезка таким образом, что отношение всего отрезка к большей части равно отношению большей части к меньшей части.

Алгоритм:

1.вычисление значения точки 0.38(b-a);

2. локализуем по трем точкам

4. выбираем новый интервал

5. получаем точку 0.38 от конца большого отрезка 0.38 (b-a¹) и т.д.

Заканчивается тогда, когда интервал в заданной точности.

8. Одномерный поиск экстремума целевой функции методом с использованием чисел Фибоначчи.

F₀=1

F₁=1

_Fi=Fi-1+Fi-2

N	0	1	2	3	4	5	6	7
F	1	1	2	3	5	8	13	21

По заданной точности определяется число N : N=(b-a)\Δ

По вспомогательному числу N выбираем число Фибоначчи: F_i<N<= F_i+1

Расчет уточненной значении точности: Δ_ь=(b-a)\F_s, s=i+1

Если Цел. Функция возрастает, то продолжаем считать :X_i+1=X_l±Δ_m*F_s-2-i

Если ухдшается, то считаем:

X1=Xl+(-1)sign ΔmFs-2-i

9. Исслед. Многомерной целевой функции методом классич. Анализа.

Для непрерывных функций многих переменных, имеющих непрерывные 1и 2 производные, необходимым условием экстремума есть равенство частных производных по всем производным.

решая систему уравнений получаем точку

проверим достаточное условие

если сохраняется знак, экстремум существует.

Разложим целевую функцию в ряд Тейлора в окрестности точки U _к подозревая на экстремум.

Правило Сильвестра:

Квадратичная форма будет положительно определенной, когда все главные миноры матрицы А были положительны. Для отрицательных: все нечетные главные миноры – отрицательные, все четные – положительные.

Опр.: если квадратичная форма положительна определена в точке, подозреваемой не экстремум, то функция имеет min и наоборот.

10. Решение многомерной задачи оптимизации на условный экстремум.

В классической дифф. исчислении существует задача на условный экстремум:

Н айти экстремум функции многих переменных, когда для переменных должно выполняться след. условие :

Q = Q ( U_1….U_к….U_к+1…U _к+м ) Имеем систему:

для этого случая : Q = x²+y² x + y =1

обычно ∂Q/∂x =0 x=0

∂Q/∂y =0 y=0, но у нас есть ограничения x + y =1. Выражаем одно, через другое.

Q = y²+(1-y) ² = y²+1+2y+ y²= 2 y²-2y+1 » Q = 2 y²-2y+1

11. Поиск экстремума функции многих переменных методом сканирования.

U₂

линии уровня или линии равного значения ф-ции

критерия оптимальности

U₁

Сущность: просмотр значений целевой функции в ряде точек в дополнительной области управления и выбор из них оптимальной (min max) причем распределение точек разнообразно (по секи, спирали ,как угодно).

Плюсы:

• получаем глобальный экстремум

• Не зависит от вида целевой функции

Минусы:

• Большой объем вычислений .

• выход: сначала сканирование с большим шагом, локализуем и уменьшаем шаг.