МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА" Інститут ІКНІ Кафедра ПЗ ЗВІТ до лабораторної роботи № 6 На тему: “ Задачі оптимізації ” З дисципліни: “ Чисельні методи в інформатиці ” Мета роботи: навчитись чисельно розв’язувати задачу одновимірної оптимізації, застосовуючи один з класичних методів (метод бісекцій, метод золотого перетину або метод параболічної екстраполяції). Теоретичні відомості Задача одновимірної оптимізації Надана функція F(x) . Треба знайти мінімум (максимум) цієї функції на наданому інтервалі [a,b] з наданою точністю (. У більшості чисельних методів розв’язання цієї задачі вважається, що функція F(x) є унімодальною, тобто має єдиний екстремум на [a,b]. Далі, у методах, що розглянуті нижче, вважається, що розв’язується задача на мінімум. Метод рівномірного пошуку Виконується табуляція функції F(x) із деяким кроком змінювання x і визначається її найменше (найбільше) значення. Метод рівномірного пошуку – це найбільш непродуктивний метод розв’язання задачі оптимізації. Метод ділення відрізку пополам Цей метод дозволяє виключити рівно половину поточного інтервалу на кожній ітерації. Схема методу має такий вигляд. 1. Ввести значення a, b, ( . 2. Обчислити xm = (a+b)/2 . 3. Обчислити значення функції fm = F(xm) . 4. Обчислити значення L = b-a . 5. Якщо L < ( процес завершити, за точку мінімуму вважати xm . 6. Обчислити значення x1 = a+L/4 , x2 = b-L/4 , f1 = F(x1) , f2 = F(x2) . 7. Якщо f1 < fm , тоді b = xm , xm = x1 , fm = f1 ; перейти до п.4. Якщо f2 < fm , тоді a = xm , xm = x2 , fm = f2 ; перейти до п.4. 8. Виконати a = x1 , b = x2 ; перейти до п.4. Метод дихотомії Вихідними даними для цього методу є: цільова функція F(x), інтервал оптимізації [a,b], точність розв’язку (. Крім того обирається параметр диференціювання h, значення якого пропонується обирати по правилу: h = 10-d/2 , де параметр d є кількість десяткових розрядів мантиси числового значення для того типу, який застосовується. Наприклад, якщо для розрахунків застосовано тип double, то d = 16, h = 10-8. Параметр точності ( не повинен бути менше, ніж h. Схема алгоритму наведена нижче. 1. Обчислити x = (a+b)/2 . 2. Якщо b-a < ( процес завершити, значення x є шуканий результат. 3. Якщо F(x-h) < F(x+h) , тоді b = x ; перейти до п.1. Якщо ні, тоді a = x ; перейти до п.1. Метод золотого перетину Цей метод є найбільш ефективним: для досягнення заданої точності він потребує найменшої кількості обчислень цільової функції F(x). Параметри, що надаються: a,b,(. У алгоритмі застосовується параметр (, він дорівнює:
Схема алгоритму виглядає так. 1. Обчислити l = b-a . 2. Якщо l < ( , то завершити процес. За точку мінімуму вважати значення x = (a+b)/2 . 3. Обчислити x1 = a+(1-()l , x2 = a+(l . 4. Обчислити нове значення l по правилу: l = (l . 5. Якщо F(x1) < F(x2), тоді b = x2 , x2 = x1, x1 = a+(1-()l , якщо ні , тоді a = x1 , x1 = x2 , x2 = a+(l . 6. Перейти до п.2. Завдання Протабулювати вказану функцію f(x) на інтервалі [a,b] та побудувати її графік. За допомогою графіку наближено знайти точку мінімуму функції. Чисельно розв’язати задачу одновимірної оптимізації, застосовуючи один з класичних методів (метод бісекцій, метод золотого перетину або метод параболічної екстраполяції). Визначити мінімуму функції на інтервалі [a,b] із точністю 10-4.
a = -0.5 , b = 0.5 Текст програми unit Unit1; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, XPMan, ExtCtrls, Grids, ValEdit,math, TeEngine, Series, TeeProcs, Chart; type TForm1 = class(TForm) Edit1: TEdit; Label1: TLabel; Button1: TButton; GroupBox1: TGroupBox; Label2: TLabel; Edit2: TEdit; Image1: TImage; Bevel1: TBevel; Label6: TLabel; ValueListEditor1: TValueListEditor; Button2: TButton; Chart1: TChart; Series1: TLineSeries; XPManifest1: TXPManifest; procedure Button1Click(Sender: TObject); procedure Button2Click(Sender: TObject); private { Private declarations } public { Public declarations } end; var Form1: TForm1; k:real; const a:real = -0.5; b:real = 0.5; implementation {$R *.dfm} function F(x:real):real; begin result:=5*ln(1+x)+2/x*x*x-5; end; function GoldenSectionOptimize2(var e : real):double; var z,a2,b2,x1,x2,l :double; begin a2:=a; b2:=b; z:=(sqrt(5)-1)/2; l:=b2-a2; while l>=e do begin x1:=a2+(l-z)*l; x2:=a2+z*l; l:=z*l; if f(x1)<f(x2) then begin b2:=x2; x2:=x1; x1:=a2+(l-z)*l; end else begin a2:=x1; x1:=x2; x2:=a2+a2*l; end; end; result:=(a2+b2)/2; end; procedure TForm1.Button1Click(Sender: TObject); begin k:=StrToFloat(Edit1.Text); Edit2.Text:= FloatToStr(GoldenSectionOptimize2(k)); end; procedure TForm1.Button2Click(Sender: TObject); var x,y:real; begin Series1.Clear; ValueListEditor1.Strings.Clear; x:=a; while x<=b do begin y:= RoundTo(f(x),-5); ValueListEditor1.InsertRow(FloatToStr(RoundTo(x,-2)),FloatTostr(y),true); Series1.AddXY(x,y,'',clYellow); x:=x+0.01; end; end; end. Протокол роботи програми
Висновок: під час виконання лабораторної роботи я навчився чисельно розв’язувати задачу одновимірної оптимізації, застосовуючи один з класичних методів (метод бісекцій, метод золотого перетину або метод параболічної екстраполяції).