лекции по оптимизаци ТЕЛЕЖКИН

3.2.1. Метод сканирования

Метод заключается в последовательном переборе всех значений с шагом (погрешность решения) с вычислением критерия оптимальности R в каждой точке. Путем выбора наибольшего из всех вычисленных значений R и находится решение задачи х *. Достоинство метода в том, что можно найти глобальный максимум критерия, если R(x) — многоэкстремальная функция. К недостаткам данного метода относится значительное число вычислений R(x), что в случае сложной функции R(x) требует существенных затрат времени.

3.2.2.Метод деления пополам

Метод основан на (рис.1) делении текущего отрезка [a, b], где содержится искомый экстремум, на две равные части с последующим выбором одной из половин, в которой локализуется максимум в качестве следующего текущего отрезка. Экстремум локализуется путем сравнения двух значений критерия оптимальности в точках, отстоящих от середины отрезка на / 2, где — погрешность решения задачи оптимизации. Если R(x + /2) > R(x - /2), то максимум располагается на правой половине текущего отрезка [а, b],

Рис.1.

противном случае — на левой (рис.2).

Новый интервал поиска

Рис. 2.

Рис.2.

Процесс поиска завершается при достижении отрезком [a, b] величины заданной погрешности .К недостаткам метода относится его работоспособность только для одноэкстремальных функций R(x) (т.е. таких, которые содержат один экстремум того типа, который мы ищем в задаче),так как в других случаях при сравнении двух критериев в соседних точках невозможно правильно выбрать следующий интервал, где находится максимум. Пример. Дана функция R(x) = 100*sin(x+1). Найти максимум на интервале: [-1, 2]. Ошибка задается по х: =0,05.Результаты расчетов. Середина отрезка х= 0,5, значение критерия R =99.75, значение R(0,5 - /2) =R(0,475) = 97.92, значение R(0,5 + /2) =R(0,525) =99.89. Следовательно, искомый максимум лежит в правой половине отрезка, т.е. теперь отрезком является [0,5, 2J.

3.2.3. Метод золотого сечения

Метод основан на делении текущего отрезка [a, b] , где содержится искомый экстремум, на две неравные части, подчиняющиеся правилу золотого сечения, для определения следующего отрезка, содержащего максимум.

Рис. 3. Иллюстрация метода золотого сечения.

Золотое сечение определяется по правилу: отношение всего отрезка к большей его части равно отношению большей части отрезка к меньшей. Ему удовлетворяют две точки с и d, расположенные симметрично относительно середины отрезка.

Если ab=1, ad=x, тогда x=0.38197

Путем сравнения R(c) и R(d) определяют следующий отрезок, где содержится максимум. Если R(d) > R(c), то в качестве следующего отрезка выбирается отрезок [a, c],

Рис.4.

Если же R(d) < R(c), то — отрезок [a, c].

Рис.5.

Новый отрезок снова делится на неравные части по правилу золотого сечения. Следует отметить, что точка c и в том и другом случаях входит в интервал поиска. Поэтому на

каждой следующей итерации (кроме "запуска" метода на исходном отрезке) нужно вычислять только одно значение критерия оптимальности.

Существуют аналитические формулы для расчета новой точки на отрезке, где находится максимальное значение R(x), которую нетрудно получить:

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

Пример. Дана функция R(x)=sin(x+1). Найти максимум на интервале: [-1,2]. Ошибка задается по х:  =0,05.

Результаты расчетов. Для "запуска" метода найдем две симметричные точки золотого сечения для отрезка [-1, 2]: x1 =0,146, x2 =0,854.

Значения критериев в этих точках соответственно R(x1) =0,911, R(x2 =0,960. Следовательно, новым отрезком является [0,146,2], внутри которого находится максимальное из найденных значений R. Точка золотого сечения для нового отрезка будет x3 =0,583, a R(x3) =0,999

Содержание