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

Метод сканирования может использоваться как при одномерном, так и многомерном поисках. Суть метода сканирования для одномерной функции R = f(x)сводится к следующему: 1) определяется интервал поиска по аргументу x; 2) выбирается шаг движения по аргументу; 3) задается наихудшее значение критерия оптимальности, обозначаемое переменной М; 4) производится последовательный расчет критерия оптимальности во всех точках разбиения интервала поиска и сравнение его значения со значением переменной М; 4) если значение R в данной точке лучше чем М, то осуществляется присвоение М = R, в противном случае расчет продолжается без присвоения. Недостатки метода сканирования — большое количество вычислений и низкая точность расчета.

Рис. 3.11. Возможные случаи сужения интервала исследования

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

На рис. 3.12 приведена блок-схема метода сканирования для случая, когда целевая функция унимодальная на интервале неопределенности [a, b].

Рис. 3.12. Блок-схема метода сканирования для унимодальной функции

Пример 3.2. Найти максимум функции на интервале [2,5] c точностью вычисления e = 0.01.

Решение. Зная, что функция унимодальная, можно вычисления целевой функции производить не во всех точках разбиения интервала, а только до точки, в которой функция начинает убывать (определяется максимум). На первом этапе сканирование производим с шагом h =1 и, сделав три шага, получаем следующие результаты: в точке значение целевой, в точке =3 — , в точке = 4 — . Выбираем отрезок интервала, содержащий точку с наибольшим значением функции. Второй этап сканирования начинаем с координаты = 2 с меньшим шагом h = 0.333333. В табл. 3.12 приведены результаты всех этапов вычислений, указаны величина шага h, номер итерации k, координаты точек разбиения x и значения функции f в этих точках.

Таблица 3.12

Максимум функции = 14.8148 в точке = 3.34568 был получен методом сканирования за 28 шагов.