Варіанти індивідуального завдання 3

Номер варіанту	Досліджувана функція	а	b	Вид екстремуму (min,max)	Метод пошуку екстремуму
		-1.0	1.0	max	“Золотого перетину”
	-	-2.0	0.66	extr	Січних
	2 x sin(x) - cos(x)	-1.0	1.0	extr	Половинного розподілу
	x2 + 4e-0.25 x	-1.2	1.5	min	“Золотого перетину”
	x2 + 6e-0.15 x	-2.0	1.0	min	“Золотого перетину”
	x4 - 0.3 arctg(3.5x)	-1.0	1.0	extr	Ітерацій
		-2.0	2.0	extr	Половинного розподілу
	-	-2.5	1.5	min	“Золотого перетину”
	x (3 + sin(3.6x2)) + 2	0.0	2.0	extr	Ітерацій
	sin(x2)+ cos(x2) - 10x	-1.0	1.0	extr	Січних
		-1.0	1.0	min	Половинного розподілу
	x4 - 1.4 arctg(1.5x)	-1.1	1.5	min	“Золотого перетину”
	tg(0.5x) - ctg(0.5x)+ x2	0.0	1.0	extr	Половинного розподілу
	x4 - 0.9 arctg(2x)	-1.0	1.0	min	“Золотого перетину”
	1 - x + sin(x) - ln(1 + x)	0.0	1.0	extr	Половинного розподілу
	-e-x ln(x)+ 5x	1.0	5.0	max	“Золотого перетину”
	ln(x) - x + 1.8	1.0	3.0	max	Половинного розподілу
		3.0	4.0	extr	Ітерацій
	x2 tg(x) -1/3	0.0	1.0	extr	Ньютона
		0.0	2.0	extr	Січних

	x4 - ln(1+x2)+ tg(x)	-3.0	3.0	min	“Золотого перетину”
	cos(2/x) - 2sin(1/x)+ 1/x	0.5	3.0	max	Половинного розподілу
	e-2x -й(0.5x)	-2.0	2.0	min	“ Золотого перетину”
		0.0	3.0	max	Половинного розподілу
	x4 - 14x3 + 60x2 -70x	5.0	7.0	extr	Ітерацій
	x (x-1) 2	-1.0	1.0	extr	Ньютона
	3 ln2(x)+ 6 ln(x) - 5	-1.0	4.0	extr	Січних
	0.4 + e|x-3.4|	-1.0	1.0	min	“ Золотого перетину”
	0.6 + e|x+0.28|	-1.0	1.0	min	“ Золотого перетину”
	x2 + 10 e0.95x	-1.0	1.0	min	“ Золотого перетину”

Короткі відомості з теорії і основні алгоритми

На практиці часто треба знайти екстремум деякої цільової функції F(x1...xn) n змінних (проектних параметрів).

При формулюванні задачі оптимізації повинні бути визначені наступні компоненти:

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, метод найшвидшого спуску).

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

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

Метод прямого пошуку, заснований на обчисленні самої цільової функції F(x) - min (max)

xÎ[A,B]

А £ x £ B - прямі обмеження.

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

Рис.9

; x - точність визначення екстремуму;

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

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

Новий інтервал при пошуку min вибирається з умови: якщо F1<F2 (F1>F2), то новий інтервал [А, В=х]; у іншому випадку [А=х,В] [А, В=х] [А=х,В]. (Рис. 9 а)

Новий інтервал при пошуку max вибирається з умови: якщо F1>F2 (F1<F2), то новий інтервал [А, В=х] ([А=х,В]); у іншому випадку [А=х,В] ([А, В=х]) (Рис. 9 в)

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

Параметр С визначає слідуюче:

Рис.10

Метод "золотого перетину"

Відрізок [А, В] ділиться за правилом "золотого перетину": відношення подальших інтервалів постійно

t (1)

Lj-1 = L _j + L _j+1

тобто t

Таким чином t²-t-1=0, звідки t»1,618033983

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

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

позначимо (1-1/t) через Т1;

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

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

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

Крапки х₁ і х₂ відстоять на однаковій відстані від кінців інтервалу[А, В](Рис.. 11). Блок-схема алгоритму методу представлена на Рис. 12.

А, В - межі інтервалу;

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

x - точність, з якою обчислюється extr значення функції F(x)

Перевага методу полягає в тому, що обчислюється значення функції лише в одній крапці х₁ або х₂.

Рекомендація

Обчислення функції оформити у вигляді оператора визначення функції користувача.

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

Рис.11

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

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

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

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

Рис.13

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

Блок-схема алгоритму представлена на Рис. 14. Змінні, які використані:

x - початкове наближення;

х=А, якщо F'(А)F'''(А) >0, інакше х=B;

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

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

FM - значення функції F(x)

Приклад 1. Пошук екстремуму функції в MathCad

Пошук мінімуму функції однієї змінної (для трьох початкових значень х)

Пошук максимуму функції однієї змінної

Рис. 14.

Рис.15