6. Численное решение задач оптимизации.

6.1. Общие положения.

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

1. По размерности решаемой задачи: одномерные и многомерные.

2. По способу формирования шага многомерные методы делятся на градиентные, безградиентные и случайные.

3. По наличию активных ограничений: безусловные и условные.

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

Рассмотрим задачу вида:

Решением задачи называется х*, при котором R(х*)≥R(x) для

При практическом решении задач не будем различать два значения х_i и х_i+1, если где ε – заданная погрешность решения.

Если возникает задача нахождения минимума R, то всегда можно перейти к новому критерию R₁=–R, который необходимо максимизировать.

Метод сканирования заключается в последовательном переборе всех значений х на [a,b] с шагом ε и вычислении критерия оптимальности R в каждой точке. Точка, в которой R принимает максимальное значение, принимается за решение задачи оптимизации.

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

Главный недостаток метода – возможность пропуска «острого» глобального максимума.

Метод дихотомии (половинного деления) заключается в делении заданного отрезка на две равные части с последующим выбором одной из них, в которой локализуется экстремум. Выбор отрезка осуществляется путем сравнения двух значений критерия оптимальности в точках, отстоящих от середины отрезка на ε/2.

Пусть х – середина [a,b]. Если R(x+ ε/2)=R(x- ε/2), то максимум достигается в точке х. Если R(x+ ε/2)>R(x- ε/2), то максимум располагается на правой половине текущего отрезка и для дальнейшего поиска выбирается отрезок [x- ε/2, b], в противном случае – [a, x+ ε/2].

Процесс поиска завершается при достижении отрезком, на котором находится экстремум, величины ε.

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

Золотое сечение определяется по правилу: отношение всего отрезка к большей части равно отношению большей части к меньшей. Этому правилу удовлетворяют две точки c и d , расположенные симметрично относительно середины отрезка: . Если R(c)>R(d), то для поиска максимума выбирается [a,d], в противном случае – [c,b]. Процесс поиска завершается при достижении отрезком, на котором находится экстремум, величины ε.

Найдем золотое сечение ξ на отрезке [0,1]: ξ²-3ξ+1=0 На отрезке существуют две точки золотого сечения. Получим аналитические формулы для расчета точек золотого сечения отрезка [a,b]:

.

ЗАДАЧА 6.1. Найти максимум функции y=x³–x на [-1,0]:

РЕШЕНИЕ.

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

x	-1	-0,9	-0,8	-0,7	-0,6	-0,5	-0,4	-0,3	-0,2	-0,1	0
y	0	0,171	0,288	0,357	0,384	0,375	0,336	0,273	0,192	0,099	0

Максимальное значение находится на отрезке [-0,7; 0,5]:

Уточним значение, уменьшив интервал сканирования до 0,01

x	-0,7	-0,69	……	-0,64	-0,63	-0,62	-0,61	-0,6	-0,59	-0,58	-0,57
y	0,36	0,361		0,378	0,38	0,382	0,383	0,384	0,3846	0,38489	0,38481

С точностью 0,01 максимум у=0,3849 достигается в точке х=-0,58

2)Метод дихотомии

Выберем точность е=0,05

a	b	x=(a+b)/2	x-e/2	x+e/2	y(x-e/2)	y(x+e/2)
-1	0	-0,5	-0,55	-0,45	0,38363	0,35888
-1	-0,45	-0,725	-0,775	-0,675	0,30952	0,36745
-0,755	-0,45	-0,6025	-0,653	-0,553	0,37469	0,38385
-0,653	-0,45	-0,5515	-0,602	-0,502	0,38388	0,37537
…

3) метод золотого сечения

a	b	c	d	y©	y(d)
-1	0	-0,618	-0,382	0,382	0,3263
-1	-0,382	-0,764	-0,618	0,318	0,382
-0,764	-0,382	-0,618	-0,528	0,382	0,3808
…

Задание 6.1.

Продолжить вычисления в задаче 6.1 по методам дихотомии и золотого сечения