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

Цель задания - закрепление теоретического материала, составление алгоритмов и программ для решения задач оптимизации

¦(x) extr

^{xÎ [a.b]}

Варианты индивидуальных заданий приведены в табл3

Порядок выполнения задания :

1. Представить геометрическую интерпретацию предложенного вам метода.

22

Таблица 3

Варианты индивидуального заданий 3

Номер варианта	Исследуемая функция	a	b	Вид экстремума (min,max)	Метод поиска экстремума
1	2	3	4	5	6
1		-1.0	1.0	max	“Золотого сечения”
2	-	-2.0	0.66	extr	Секущих
3	2 x sin(x) - cos(x)	-1.0	1.0	extr	Половинного деления
4	x2 + 4e-0.25 x	-1.2	1.5	min	“Золотого сечения”
5	x2 + 6e-0.15 x	-2.0	1.0	min	“Золотого сечения”
6	x4 - 0.3 arctg(3.5x)	-1.0	1.0	extr	Итераций
7		-2.0	2.0	extr	Половинного деления
8	-	-2.5	1.5	min	“Золотого сечения”
9	x (3 + sin(3.6x2)) + 2	0.0	2.0	extr	Итераций
10	sin(x2) + cos(x2) - 10x	-1.0	1.0	extr	Секущих
11		-1.0	1.0	min	Половинного деления
12	x4 - 1.4 arctg(1.5x)	-1.1	1.5	min	“Золотого сечения”
13	tg(0.5x) - ctg(0.5x) + x2	0.0	1.0	extr	Половинного деления
14	x4 - 0.9 arctg(2x)	-1.0	1.0	min	“Золотого сечения”
15	1 - x + sin(x) - ln(1 + x)	0.0	1.0	extr	Половинного деления

23

Окончание таблицы 3

1	2	3	4	5	6
16	-e-x ln(x) + 5x	1.0	5.0	max	“Золотого сечения”
17	ln(x) - x + 1.8	1.0	3.0	max	Половинного деления
18		3.0	4.0	extr	Итераций
19	x2 tg(x) -1/3	0.0	1.0	extr	Ньютона
20		0.0	2.0	extr	Секущих
21	x4 - ln(1+x2) + tg(x)	-3.0	3.0	min	“Золотого сечения”
22	cos(2/x) - 2sin(1/x) + 1/x	0.5	3.0	max	Половинного деления
23	e-2x th(0.5x)	-2.0	2.0	min	“Золотого сечения”
24		0.0	3.0	max	Половинного деления
25	x4 - 14x3 + 60x2 -70x	5.0	7.0	extr	Итераций
26	x (x-1) 2	-1.0	1.0	extr	Ньютона
27	3 ln2(x) + 6 ln(x) - 5	-1.0	4.0	extr	Секущих
28	0.4 + e|x-3.4|	-1.0	1.0	min	“Золотого сечения”
29	0.6 + e|x+0.28|	-1.0	1.0	min	“Золотого сечения”
30	x2 + 10 e0.95x	-1.0	1.0	min	“Золотого сечения”

24

2. Составить алгоритм вычисления оптимального значения функции с точностью E=10^-4

3. Составить программу на алгоритмическом языке, оформив вывод результата на печать с соответствующими комментариями.

4. Ввести программу в ЭВМ и получить результат.

5. Оформить отчет и представить его к защите.

Краткие сведения из теории и основные алгоритмы.

На практике часто надо найти экстремум некоторой целевой функции F(x₁...x_n) n переменных x₁ (проектных параметров).

При формулировке задачи оптимизации должны быть определены следующие компоненты:

a) набор (вектор) переменных x^T = (x₁...x_n) оптимальные значения которых подлежат вычислению в процессе решения задачи оптимизации (иногда вектор x называют планом задачи);

б) целевая функция (критерий оптимизации) F(x), численное значение которой отражает основную цель производства (связана с экономическими показателями исследуемого процесса);

в) ограничения задачи оптимизации, которые связаны как с ограничениями на переменные x^T=(x₁...x_n), т.е. с ограничениями на ресурсы, так и с функциональными ограничениями, отражающими связи в объекте.

Совокупность решений, удовлетворяющих всем ограничениям, называется допустимой областью (допустимым множеством задачи). В дальнейшем будем обозначать допустимую область через D. Тогда решение xÎD называется допустимым.

Совокупность перечисленных компонент и составляет математическую модель задачи оптимизации, которая может быть записана в виде:

_

F(x) = extr (1)

xÎD

Методы решения задачи оптимизации для функции одной переменной

1. Методы нулевого порядка или методы прямого поиска, основанные на вычислениях значений только целевой функции (метод дихотомии, ”золотого сечения”).

2. Методы первого порядка или градиентные методы , в которых при поиске экстремума функции используется точные значения ее первых производных. (метод простых итераций и метод хорд для уравнения F'(x) = 0, метод наискорейшего спуска).

25

3. Методы второго порядка, где наряду с производными первого порядка используются и вторые производные целевой функции (метод Ньютона).

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

Метод прямого поиска, основанный на вычислении самой целевой функции

F(x) - min (max)

xÎ[A,B]

A £ x £ B - прямые ограничения.

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

Рис.9

; x - точность определения экстремума ;

F1- значение функции в точке x-x ;

F2- значение функции в точке x+x ;

Новый интервал при поиске min выбирается из условия :

если F1<F2 (F1>F2), то новый интервал [А, В=х];иначе [А=х,В] [А, В=х] [А=х,В]. (рис 9 а)

Новый интервал при поиске max выбирается из условия:

26

если F1>F2 (F1<F2), то новый интервал [А, В=х] ([А=х,В]);иначе [А=х,В] ([А, В=х]) (рис 9 в)

Блок-схема алгоритма представлена на рис .10.

27

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

Отрезок [А,В] делится по правилу "золотого сечения" :отношение последующих интервалов постоянно

t (1)

L_j-1 = L _j + L _j+1

т. е. t

Таким образом t²-t-1=0 , откуда t»1,618033983

Название "золотое сечение" произошло от названия отношения в уравнении (1).Видно, что L_j-1 делится на две части так, что отношение целого к большей части к меньшей, т.е. равно так называемому "золотому отношению".

x₁ = A + B - x₂ x₁ = A + (B-A)(1-1/t)

обозначим 1-1/t через Т1;

Т1 = 0.3819660113 , тогда Т2 = 1 - Т1, (1/t)

х₁ = A + (B-A)Т1

х₂ = A + (B-A)Т2

Точки х₁ и х₂ отстоят на одинаковом расстоянии от концов интервала[А,В](рис 11)

Блок-схема представлена на рис 12

А,В - границы интервала

х₁ и х₂ - точки, которыми делится интервал А,В по правилу "золотого сечения"

x - точность, с которой вычисляется extr значение функции F(x)

Преимущество метода заключается в том, что вычисляется значение функции лишь в одной точке х1 или х2 .

28

Рекомендация.

Вычисление функции оформить в виде оператора определения функции пользователя, либо в виде процедуры FUNCTION .

Функция F(x) имеет локальный минимум в точке х₀, если существует некоторая положительная величина Е : если | х-х₀ | <E , то F(x) ³ F(x₀), т.е. если существует окрестность точки х₀ для всех значений х в этой окрестности F(x) больше F(x₀) .

29

В точке х₀ F'(x₀) =0 т.е. градиент функции равен нулю. Заметим, что в точке х₀ производная F'(x) меняет знак с отрицательго на положительный, т.е. производная в min является возрастающей функцией , а поскольку степень возрастания F'(x) измеряется второй производной, можно ожидать, что в точке max F''(x0)<0, а в точке min F''>0 (рис 13)

Метод Ньютона

Рис.13

Для функции одной переменной классический подход при поиске значений х в точках перегиба функции F(x) состоит в решении уравнения

F'(x)=0 F'(x)=j(x)

По знаку j'(x) судят о точке х как о max или min. Метод Ньютона основан на теореме , что если любые $А и В : F'(A) и F'(B) имеют противоположные знаки, то существует корень x₀ = [A,B]

Блок-схема представлена на рис 14

x - начальное приближение

х=А, если F'(A)F'''(A)>0 , иначе х=B

F1 - значение функции F'(x)

F2 - значение функции F''(x)

FM - значение функции F(x)

31