Численные методы решения одномерных задач оптимизации

ОДНОМЕРНАЯ ОПТИМИЗАЦИЯ

В данном разделе не делается упор на поиск именно минимума, тем более что практически все методы могут искать и минимум, и максимум при незначительных изменениях в алго­ритмах. Действительно для того, чтобы найти максимум (минимум) функции нужно искать минимум (максимум) целевой функции с противоположным знаком.

В данном разделе рассматриваются методы решения одно­мерных задач оптимизации вида

R(x) -> max, , где х — скаляр, а и b — соответственно нижняя и верхняя граница значения переменной x.В основном рассматриваются алгоритмы, связанные с по­строением улучшающей последовательности. Решением задачи называется х*, при котором R(x*) > R(x) для любого значения . При практическом решении задач не будем различать два значениях и , ecли , где — задаваемая по­грешность решения.

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

Метод заключается в последовательном переборе всех значений с шагом (погрешность решения) с вычислением крите­рия оптимальности R в каждой точке. Путем выбора наибольшего из всех вычисленных значений R и находится решение задачи х *.

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

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

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

 

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

Иллюстрация метода половинного деления

Процесс поиска завершается при достижении отрезком [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.

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

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

 

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

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

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

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

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

Новый отрезок снова делится на неравные части по правилу золотого сечения. Следует отметить, что точка c и в том и другом случаях входит в интервал поиска. Поэтому на каждой следующей итерации (кроме " запуска" метода на исходном отрезке) нужно вычислять только одно зна­чение критерия оптимальности.

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

Условие окончания поис­ка — величина отрезка, содер­жащего максимум, меньше за­данной погрешности.

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

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

Пример. Дана функция R(x)=sin(x+1). Найти макси­мум на интервале: [-1, 2]. Ошибка задается по х: e =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

⇐ Предыдущая12345Следующая ⇒

Поделиться:

Популярное:

1. E) тело, размерами которого можно пренебречь в условиях данной задачи
2. I. ОСНОВНЫЕ ЗАДАЧИ ВНЕШНЕЙ ПОЛИТИКИ
3. II. Основные цели и задачи Совета
4. II. Цели и задачи выпускной квалификационной работы
5. II. Цели и задачи настоящей Концепции
6. III. Задачи, определяемые возрастом воспитанников
7. III. Решение логических задач с помощью рассуждений
8. PR – отношения с общественностью. Цели, задачи, функции, методы
9. Авторитарно-ориентированный менеджер, который прежде всего концентрирует свое внимание на решении производственных задач.
10. Адлер выделил три основные жизненные цели (задачи): работу, дружбу и любовь.
11. Активное использование речевых средств и средств информационно- коммуникационных технологий (далее – ИКТ) для решения коммуникативных и познавательных задач.
12. Алгоритм решения задач динамического программирования.