Некрасова М.Г. Методы оптимизации - файл n1.doc

приобрести
Некрасова М.Г. Методы оптимизации
скачать (3013.5 kb.)
Доступные файлы (1):
n1.doc3014kb.22.08.2012 14:29скачать

n1.doc

1   2   3   4   5   6   7   8   9   ...   12

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


 

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

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

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

На первом этапе сканирова­ние осуществляют с крупным шагом, затем отрезок, внутри которого получено наибольшее значение f(х), разбивается на более мелкие отрезки, ищется новый отрезок, внутри которого уточненное значение максимума. Он (новый отрезок) опять

делится на более мелкие и т. д., тех пор, пока величина отрезка, содержащего максимальное значение f(x), не будет меньше заданной погрешности. Главный недостаток этого варианта метода – возможность пропуска «острого» глобального максимума f(x).

Пример 11. Найти минимальное значение f* и точку минимума х* функции f(x)=x4+8x3-6x2-72х на отрезке [1.5; 2]. Точку х* найти с погрешностью =0,05.

Решение. Будем разбивать первоначальный и новый, удовлетворяющий нас, интервал на 4 части, при этом новый шаг рассчитываем по формуле:



где n – количество частей деления интервала,

ai, bi – концы интервала, в котором содержится максимальное значение функции,

погрешность , где  i - номер итерации.

                                                                                                                                                             Таблица 3

Номер

п.

Шаг

Концы

новых

интервалов

Значение функции

Погрешность

Примечание

1

2

3

4

5

6

1.

0,1250

1,5000

-89,4375

0,2500

Точность не достигнута

1,6250

-91,5427

1,7500

-92,1211

1,8750

-90,9998

2,0000

-88,0000

2.

0,0625

1,6250

-91,5427

0,1250

Точность не достигнута

1,6875

-92,0334

1,7500

-92,1211

1,8125

-91,7839

1,8750

-90,9998

3.

0,0313

1,6875

-92,0334

0,0625

Точность не достигнута

1,7188

-92,1290

1,7500

-92,1211

1,7813

-92,0070

1,8125

-91,7839

Продолжение табл. 3

1

2

3

4

5

6

4.

0,0156

1,6875

-92,0334

0,0313

Точность  достигнута

1,7031

-92,0940

1,7188

-92,1290

1,7344

-92,1381

1,7500

-92,1211

 

Итак,

Пример 12. Найти точку минимума х* функции

 на отрезке [0.5; 1] с точностью =0,05.

Решение. Будем разбивать первоначальный и новый, удовлетворяющий нас, интервал на 4 части.

                                                                                                            Таблица 4

Номер п.

Шаг

Концы

новых

интервалов

Значение функции

Погрешность

Примечание

1.

0,1250

0,5000

-3,5907

0,1250

Точность не достигнута

0,6250

-3,1328

0,7500

-2,4389

0,8750

-1,5512

1,0000

-0,5000

2.

0,0313

0,5000

-3,5907

0,0313

Точность  достигнута

0,5313

-3,5014

0,5625

-3,3946

0,5938

-3,2715

0,6250

-3,1328

 

Итак,

Пример 13. Дана функция f(x) = sin (x+1). Найти максимум на интервале [-1; 2] с точностью =0,05.

Решение. Будем разбивать первоначальный и новый, удовлетворяющий нас, интервал на 4 части, при этом новый шаг рассчитываем по формуле:



где n – количество частей деления интервала, ai, bi – концы интервала, в котором содержится максимальное значение функции, погрешность , где  i - номер итерации.

                                                                                                                      Таблица 5

п.

Шаг

Концы новых интервалов

Значение функции

Погрешность

Примечание

 

 

1

2

3

4

5

6

1

0,75

-1,0000

0

1,5000

Точность не достигнута

 

-0,2500

0,6816

 

0,5000

0,9975

 








































Продолжение табл. 5

1

2

3

4

5

6

 

 

1,2500

0,7781

 

 

2,0000

0,1411

2

0,375

-0,2500

0,6816

0,75

Точность не достигнута

0,1250

0,9023

0,5000

0,9975

0,8750

0,9541

1,2500

0,7781

3

0,188

0,1250

0,9023

0,375

Точность не достигнута

0,3125

0,9668

0,5000

0,9975

0,6875

0,9932

0,8750

0,9541

4

0,094

0,3125

0,9668

0,1875

Точность не достигнута

0,4063

0,9865

0,5000

0,9975

0,5938

0,9997

0,6875

0,9932

5

0,047

0,5000

0,9975

0,0938

Точность не достигнута

0,5469

0,99971

0,5938

0,99973

0,6406

0,9976

0,6875

0,9932

6

0,023

0,5469

0,9997

0,0469

Точность достигнута

0,5703

1

0,5938

0,9997

0,6172

0,9989

0,6406

0,9976

 

Итак,

4.1.2. Метод деления отрезка пополам

Метод деления отрезка пополам является простейшим последовательным  методом минимизации. Он позволяет для любой функции f(x)Q[a, b] построить последовательность вложенных отрезков      [a, b] [a1,b1] [an-1, bn-1] [an, bn],  каждый из которых содержит хотя бы одну из точек оптимума х* функции  f(x).

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

Если f(х + /2) > f(х - /2), то максимум располагается на пра­вой половине текущего отрезка [а, b] , в противном случае — на левой.

Процесс поиска завершается при достижении отрезком [а, b]  величины заданной погрешности  .

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

На рис. 17 приведены три этапа метода половинного деле­ния. Сплошными вертикальны­ми линиями отмечены середины отрезков, а пунктирными — вы­числяемые значения критерия оптимальности слева и справа на /2 от середин.

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

Существует и другой вари­ант алгоритма, заключающийся в следующем. После нахожде­ния середины отрезка (напри­мер, точка с1) в одной из полови­нок (допустим, в левой) находят среднюю точку (точка с2) и, срав­нивая значения функции в этих точках, определяют, в какой из половинок находится экстремум. Если f(c1)<f(c2), то в качестве следующего отрезка выбираем отрезок [а, с1], если же f(c1)>f(c2), то берут новую точку в середине правой половины (точка с3) и в ней вычисляют функцию. В зависимости от сравнения зна­чений функции в точках с3 и с1 выбирают новый отрезок 1, b] или 2, с3] и т.д.

Второй вариант метода не имеет с точки зрения эффективно­сти принципиального отличия от первого, так как эффективность принято оценивать по наихудшему варианту (т.е. по двум вычис­лениям f(x) на каждом шаге). В первом варианте метода есть одна особенность, которая его делает очень эффективным при экспериментальном отыскании экстремума (например, при авто­матической настройке технических систем или при практическом поиске наилучших условий деятельности экономического объек­та). Малые отклонения от текущей точки обеспечивают в процес­се поиска отсутствие "шараханий", сопровождающихся резкими отклонениями состояния системы.

Пример 14. Найти минимальное значение f* и точку минимума х* функции

f(x)=x4+8x3-6x2-72х на отрезке [1.5; 2]. Точку х* найти с погрешностью =0,05.

Решение. 1 способ. Вычисления представим в виде табл. 6.

                                                                                                                                                       Таблица 6

n

an

bn

f(an)

f(bn)

cn

f(cn)

|an-bn|

0

1,500

2,000

-89,438

-88,000

1,750

-92,121

0,500

1

1,500

1,750

-89,438

-92,121

1,625

-91,543

0,250

2

1,625

1,750

-91,543

-92,121

1,688

-92,033

0,125

3

1,688

1,750

-92,033

-92,121

1,719

-92,129

0,063

4

1,719

1,750

-92,129

-92,121

1,734

-92,138

0,031
1   2   3   4   5   6   7   8   9   ...   12


4.1.1. Метод сканирования
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации