Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Задачі оптимізації.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
Не вказано
Кафедра:
Програмного забезпечення (ПЗ)
Інформація про роботу
Рік:
2008
Тип роботи:
Лабораторна робота
Предмет:
Чисельні методи в інформатиці
Група:
КН-3
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА"
Інститут ІКНІ
Кафедра ПЗ
ЗВІТ
до лабораторної роботи № 6
На тему: “ Задачі оптимізації ”
З дисципліни: “ Чисельні методи в інформатиці ”
Виконав:
ст. гр. КН - 3
Львів – 2008
Мета роботи: навчитись чисельно розв’язувати задачу одновимірної оптимізації, застосовуючи один з класичних методів (метод бісекцій, метод золотого перетину або метод параболічної екстраполяції).
Теоретичні відомості
Задача одновимірної оптимізації
Надана функція 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,. У алгоритмі застосовується параметр , він дорівнює:
EMBED Equation.3
Схема алгоритму виглядає так.
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.
EMBED Equation.3 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.
Протокол роботи програми
Висновок: під час виконання лабораторної роботи я навчився чисельно розв’язувати задачу одновимірної оптимізації, застосовуючи один з класичних методів (метод бісекцій, метод золотого перетину або метод параболічної екстраполяції).
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора