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

1 2 3 4 5 6 7

Одномерная оптимизация.

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

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

R(x) → max / а £ х £ b/,

R(x) - критерий оптимизации,

х — аргумент, скалярная величина, а и b — соответственно минимальное и максимальное возможные значения аргумента х.

Рассматриваются алгоритмы, связанные с построением улучшающей последовательности величины R(x).

Решением задачи х * называется значение, при котором R (х *) ³ R(x) для любого значения а £ х £ b.

При практическом решении задач не будем различать два значения х _i и х _i₊₁, если ½ х _i - х _i₊₁ ½ £ ε, где ε — задаваемая погрешность решения.

Основные методы.

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

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

Экстремальные точки различаются на локальные и глобальные.

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

На практике можно реализовать одну из основных модификаций метода — последовательное уточнение решения, или сканирование с переменным шагом (рис. 3.1).

На первом этапе сканирование осуществляют с крупным шагом, затем отрезок, внутри которого получено наибольшее значение R(x) разбивается на более мелкие отрезки, ищется новый отрезок, внутри которого находится уточненное значение максимума. Он (новый отрезок) опять делится на более мелкие и т.д., до тех пор, пока величина отрезка, содержащего максимальное значение R(x), не будет меньше заданной погрешности. Главный недостаток этого варианта метода — возможность пропуска "острого" глобального максимума R(x).