Сравнение методов численного решения задач оптимизации

Результаты расчетов. Первая аппроксимирующая парабола строится по точкам:

х1 =-1, R(-1)=0; х2=0,5 R(0,5)=0,9975; х3=2,0, R(2,0)=0,141120.

Запишем систему уравнений для нахождения коэффициентов параболы:

1*С2+(-1)С1+Со=0,

0,25С2 + 0,5C1 + С0 = 0,9975,

4C2+2C1+C0=0,14112.

Решением этой системы является

С2=-0,41197, С1=0,459012, С0=0,87089.

Находим х, при котором парабола имеет максимум:

х=-С1/2С2=- (-0,41197)/(2*0,459012)=0,55709139,

при этом R=0,99990609. По этой точке, а также по второй и третьей исходным точкам, лежащим по обе стороны от точки максимума параболы, аналогично строится вторая парабола, максимум которой оказывается в точке

х =0,57823785, а R =0,99997231. Разница между двумя точками максимума менее заданной погрешности, следовательно, можно заканчивать поиск.

В этом методе всего четыре раза вычислялся критерий оптимальности.

Как уже сказано выше в программе присутствует главное меню - в котором всего два пункта: Файл и Справка.

Пункт меню Файл содержит следующие подпункты (рис. 10):

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

2. Метод деления пополам

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

4. Метод параболической аппроксимации

5. Выход

Выбирая один из первых четырех пунктов пользователь выбирает один из методов - после чего он может нажать кнопку Вычислить для получения ответа. Если пользователь выберет пятый пункт - Выход - то произойдет выход из программы.

Пункт меню Справка содержит один подпункт - Вызов справки, при выборе этого пункта появится диалоговое окно которое состоит из двух вкладок - Разработчик и О программе, на рис. 11 приведены эти вкладки.

Рис 10. Пункт меню «Файл»

Рис 11. Справка в программе (две вкладки - Разработчик и О программе)

Текст программы с описанием

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, Buttons, ExtCtrls, Menus;

type

TForm1 = class(TForm)

GroupBox1: TGroupBox;

Edit1: TEdit;

Label1: TLabel;

Label2: TLabel;

Label3: TLabel;

Label4: TLabel;

Edit2: TEdit;

Edit3: TEdit;

Edit4: TEdit;

Label5: TLabel;

Edit5: TEdit;

Edit6: TEdit;

Label6: TLabel;

Edit7: TEdit;

SpeedButton1: TSpeedButton;

Label7: TLabel;

GroupBox2: TGroupBox;

RadioButton1: TRadioButton;

RadioButton2: TRadioButton;

BitBtn1: TBitBtn;

RadioButton3: TRadioButton;

RadioButton4: TRadioButton;

Label8: TLabel;

Bevel1: TBevel;

MainMenu1: TMainMenu;

N1: TMenuItem;

N11: TMenuItem;

N21: TMenuItem;

N31: TMenuItem;

N41: TMenuItem;

N2: TMenuItem;

N3: TMenuItem;

N4: TMenuItem;

procedure SpeedButton1Click(Sender: TObject);

procedure N3Click(Sender: TObject);

procedure N4Click(Sender: TObject);

procedure N11Click(Sender: TObject);

procedure N21Click(Sender: TObject);

procedure N31Click(Sender: TObject);

procedure N41Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

max, min: real; // Переменные используемые в программе

A,B,C,D,ep,int,per,maxmn,newP,R: real;

R0,R1,R2,ser,dlt,dltX,dltY,dltZ,C0,C1,C2: real;

x,mass: array [1..25] of real;

parab: array [0..99] of real;

G,H,J,K: real;

R_Lev, R_Prav: real;

implementation

uses Unit4;

{$R *.dfm}

function Scan(A,B,C,D,x: real): real; // Вычисляется функция вида

//R(x)=D sin(AxB + C)

var PRM: real;

i: integer;

begin

PRM:=1;

for i:=1 to trunc(B) do PRM:=PRM*x;

Scan:=D*sin(A*PRM+C);

end;

procedure TForm1.SpeedButton1Click(Sender: TObject); // Действие при нажатии

// кнопки Вычислить

var i,k,it: integer; // Переменные используемые в программе

m,n,Lev,Prav: real;

begin

try;

ep:=strtofloat(Edit7.Text); // ep (погрешность) из строки переводится в число

if ep<0 then exit;

A:=strtofloat(Edit1.Text); // А из строки переводится в число

B:=strtofloat(Edit2.Text); // B из строки переводится в число

C:=strtofloat(Edit3.Text); // C из строки переводится в число

D:=strtofloat(Edit4.Text); // D из строки переводится в число

min:=strtofloat(Edit5.Text); // min из строки переводится в число

max:=strtofloat(Edit6.Text); // max из строки переводится в число

if min>max then exit;

except

ShowMessage('Некорректное значение!');

exit;

end;

If RadioButton1.Checked then // Вычисляется "Метод Сканирования"

begin

it:=0; // Количество итераций равно 0

repeat

Int:=(max-min)/4; // Отрезок разбивается на 4 части

PER:=min; // Некоторой переменной присваивается значение минимума

for i:=1 to 3 do // Находим массив чисел x[i]

begin

PER:=PER+Int;

x[i]:=PER;

end;

for i:=1 to 3 do MASS[i]:=(Scan(A,B,C,D,x[i])); // На каждом интервале находим

// значение функции

maxmn:=mass[1];

k:=1;

for i:=2 to 3 do

if maxmn<mass[i] then // Находим максимальное значение

begin

maxmn:=mass[i];

k:=i; // Индекс максимального значения

end;

newP:=x[k];

min:=newP-int; // Находим минимум

max:=newP+int; // Находим максимум

it:=it+1; // Считается количество итераций

until (max-min)<ep; // Условие окончания вычислений

Label7.Caption:='Ответ: x = '+ floattostr(newP) + #10#13 +

'R =' + floattostr(mass[k]); // Выводится ответ

Label8.Caption:= 'Количество итераций = '+inttostr(it); // Выводится

// количество итераций

end;

If RadioButton3.Checked then // Вычисляется "Метод деления пополам"

begin

it:=0; // Количество итераций равно 0

repeat

ser:=(max+min)/2; // Вычисляется середина отрезка (ser) и точки

// стоящие от середины отрезка на еp/2 (G и H)

G:=(ser+ep/2);

H:=(ser-ep/2);

R0:=scan(A,B,C,D,ser); // вычисляется критерий оптимальности в точке

// ser

R1:=scan(A,B,C,D,G); // вычисляется критерий оптимальности в точке

// G

R2:=scan(A,B,C,D,H); // вычисляется критерий оптимальности в точке

// H

if R1>R2 then begin // Условие при котором середина равняется

// минимуму

min:=ser;

end;

if R1<R2 then begin // Условие при котором середина равняется

// максимуму

max:=ser;

end;

it:=it+1; // считается количество итераций

until (max-min)<ep; // условие окончания вычислений

Label7.Caption:='Ответ: x = '+floattostr(ser)+#10#13+

'R = '+Floattostr(R0); // На экран выводится ответ (ser, R0)

Label8.Caption:= 'Количество итераций = '+inttostr(it); // Выводится

// количество итераций

end;

If RadioButton4.Checked then // Вычисляется метод "Золотого сечения"

begin

it:=2; // Количество итераций равно 2 (т.к. две точки даны)

repeat

m:=min; // m приравнивается к минимуму

n:=max; // n приравнивается к максимуму

Lev:=m+(n-m)*((sqrt(5)-1)/2); // Отрезок делится на неравные части по

Prav:=n-(n-m)*((sqrt(5)-1)/2); // Правилу золотого сечения (точки Lev и

// Prav)

R_Lev:=scan(A,B,C,D,Lev); // Вычисляется критерий оптимальности в

// точке Lev

R_Prav:=scan(A,B,C,D,Prav); // вычисляется критерий оптимальности в

//точке Prav

if R_Lev>R_Prav then // Условие при котором минимум отрезка

// принимает значение Prav

begin

min:=Prav;

Label7.Caption:='Ответ: x = '+floattostr(Lev)+#10#13+

'R = '+Floattostr(R_Lev); // На экран выводится ответ (Lev, R_Lev)

end;

if R_Lev<R_Prav then // Условие при котором максимум отрезка

// принимает значение Lev

begin

max:=Lev;

Label7.Caption:='Ответ: x = '+floattostr(Prav)+#10#13+

'R = '+Floattostr(R_Prav); // На экран выводится ответ (Prav, R_Prav)

end;

it:=it+1; // Считается количество итераций

until (max-min)<ep; // Условие окончания вычислений

Label8.Caption:= 'Количество итераций = '+inttostr(it); // Выводится

// количество итераций

end;

if RadioButton2.Checked then // Вычисляется метод "Параболической

// аппроксимации"

begin

it:=0; // Количество итераций равно 0

i:=0;

ser:=(max-min)/2+min; // Рассчитывается середина отрезка

repeat

R0:=scan(A,B,C,D,min); // Вычисляется критерий оптимальности в точке min

R1:=scan(A,B,C,D,ser); // Вычисляется критерий оптимальности в точке ser

R2:=scan(A,B,C,D,max); // Вычисляется критерий оптимальности в точке max

dlt:=(sqr(min)*(ser-max)-min*(sqr(ser)-sqr(max))+(sqr(ser)*max-ser*sqr(max)));

// Находим общий делитель

dltX:=R0*(ser-max)-min*(R1-R2)+(R1*max-R2*ser);

dltY:=sqr(min)*(R1-R2)-R0*(sqr(ser)-sqr(max))+(sqr(ser)*R2-R1*sqr(max));

dltZ:=sqr(min)*(ser*R2-max*R1)-min*(sqr(ser)*R2-R1*sqr(max))+R0*(sqr(ser)*max-ser*sqr(max));

// Методом Крамера находим X, Y, Z.

C2:=dltX/dlt; // Находим коэффициенты параболы C0, C1, C2

C1:=dltY/dlt;

C0:=dltZ/dlt;

i:=i+1;

min:=ser;

Parab[i]:=-C1/(2*C2); // Значение при котором парабола имеет максимум

ser:=Parab[i];

if i=1 then Parab[i-1]:=-Parab[i];

it:=it+1; // Считается количество итераций

until abs(Parab[i]-Parab[i-1])<ep; // Условие окончания вычислений

R:=Scan(A,B,C,D,Parab[i]);

Label7.Caption:='Ответ: x = '+floattostr(Parab[i])+#10#13+'R = ' + floattostr(R);

Label8.Caption:= 'Количество итераций = '+inttostr(it); // Выводится количество итераций

end;

end;

procedure TForm1.N3Click(Sender: TObject);

begin

Close; // Выход

end;

procedure TForm1.N4Click(Sender: TObject);

begin

PagesDlg.Show; // Вызов справки

end;

procedure TForm1.N11Click(Sender: TObject);

begin

RadioButton1.Checked:=true; // Выбирается "Метод сканирования"

end;

procedure TForm1.N21Click(Sender: TObject);

begin

RadioButton3.Checked:=true; // Выбирается "Метод деления пополам"

end;

procedure TForm1.N31Click(Sender: TObject);

begin

RadioButton4.Checked:=true; // Выбирается "Метод золотого сечения"

end;

procedure TForm1.N41Click(Sender: TObject);

begin

RadioButton2.Checked:=true; // Выбирается "Метод параболической аппроксимации"

end;

end.

2.4 Описание процесса отладки программы

Отладка программы представляет собой нахождение ошибок используя контрольные примеры. В данной программе ошибки могут быть если введены неточные (некорректные) значения в полях ввода, чтобы этого не произошло используется система try…except…end.

begin

try;

ep:=strtofloat(Edit7.Text); // ep (погрешность) из строки переводится в число

if ep<0 then exit;

A:=strtofloat(Edit1.Text); // А из строки переводится в число

B:=strtofloat(Edit2.Text); // B из строки переводится в число

C:=strtofloat(Edit3.Text); // C из строки переводится в число

D:=strtofloat(Edit4.Text); // D из строки переводится в число

min:=strtofloat(Edit5.Text); // min из строки переводится в число

max:=strtofloat(Edit6.Text); // max из строки переводится в число

if min>max then exit;

except

ShowMessage('Некорректное значение!');

exit;

end;

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

В процессе отладки возникали следующие ошибки:

- Undeclared identifier - используется переменная, не объявленная в разделе var;

- Missing operator or semicolon - после инструкции не поставлена точка с запятой;

- ”)” expected - забыл закрыть скобку;

- Incompatible types - несоответствие типов и т.д.

 БЛОК-СХЕМЫ

1. Блок-схема function Scan

function Scan(A,B,C,D,x: real): real - Вычисляется функция вида

R(x)=D sin(AxB + C)

2. Блок-схема procedure TForm1.SpeedButton1Click procedure TForm1.SpeedButton1Click(Sender: TObject);

//Действие при нажатии кнопки "Вычислить"



ЗАКЛЮЧЕНИЕ

Цель данной диссертационной работы была создать программу «Сравнение методов оптимизации» предназначенную для решения задач оптимизации численными методами. Всего в программе представлено четыре метода:

1. метод сканирования,

2. метод деления пополам,

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

4. метод параболической аппроксимации.

В ответе выводятся: середина отрезка, критерий оптимальности и количество итераций.

Для реализации этой программы был использован язык Delphi 7, который комбинирует в себе несколько важнейших технологий: высокопроизводительный компилятор в машинный код, объектно-ориентированная модель компонент и визуальное построение приложений из программных прототипов.

ЛИТЕРАТУРА

1. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах упражнениях. - М.: Наука,1991.

2. Никита Культин - «Основы программирования в Delphi 7», С.- П.: «БХВ Санкт-Петербург», 2003 г.

3. Шауцукова Л.З. - «Информатика», М.: Просвещение, 2000.

4. Васильков Ю. В., Василькова Н. Н. «Компьютерные технологии вычислений», М.: Финансы и статистика, 1999 г.

5. Бережная Е. В., Бережной В. И. «Математические методы моделирования в экономических системах»

6. Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. - М.: Изд-во Бином. Лаборатория знаний, 2011. - 640 с.

7. Бахвалов Н. С., Корнев А. А., Чижонков Е. В. Численные методы. Решения задач и упражнения. - М.: Изд-во Дрофа, 2009. - 400 с.

8. Бахвалов Н. С., Лапин А. В., Чижонков Е. В. Численные методы в задачах и упражнениях. - М.: Изд-во Бином. Лаборатория знаний, 2010. - 240 с.

9. Вержбицкий В. М. Основы численных методов. - М.: Высшая школа, 2009. - 848 с.

10. Волков Е. А. Численные методы. - М.: Изд-во Лань, 2004. - 256 с.

11. Жидков В.Н. Вычислительная математика. - М, Академия, 2010. - 208 с.

12. Зализняк В.Е. Основы научных вычислений. Введение в численные методы для физиков. - Изд-во Едиториал УРСС, 2002. - 296 с.

13. Калиткин Н.Н. Численные методы. - С.Пб.: Изд-во БХВ-Петербург, 2011. - 592 с.

14. Лапчик М. П., Рагулина М. И., Хеннер Е. К. Численные методы. - М.: Академия, 2009. - 384 с.

15. Марчук Г.И. Методы вычислительной математики. - М.: Изд-во Лань, 2010. - 608 с.

16. Панокова Т.А. Численные методы. - М.: Изд-во Либроком, 2010. - 226 с.

17. Пантина И. В., Синчуков А. В. Вычислительная математика. - М, 2010. - 176 с.

18. Петров И. Б., Лобанов А. И. Лекции по вычислительной математике. - М.: Изд-во Бином. Лаборатория знаний, Интернет-университет ин., 2009. - 528 с.

19. Протасов И. Д. Лекции по вычислительной математике. - М.: Изд-во Гелиос АРВ, 2004. - 184 с.

20. Рено Н.Н. Численные методы. - М.: Изд-во КДУ, 2007. - 100 с.,

21. Рябенький В.С. Введение в вычислительную математик. - М,: Изд-во ФИЗМАТЛИТ, 2008. - 286 с.

22. Самарский А.А. Введение в численные методы. - М.: Изд-во Лань, 2009. - 288 с.

23. Самарский А. А., Вабищевич П. Н., Самарская Е. А. Задачи и упражнения по численным методам. - М.: Изд-во Либроком, 2009. - 208 с.

24. Срочко В.А. Численные методы. Курс лекции. - М.: Изд-во Лань, 2010. - 208 с.

25. Турчак Л. И., Плотников П. В. Основы численных методов. - М.: ФИЗМАТЛИТ, 2002. - 304 с.

26. Ульяницкий И.В. Введение в численные методы. - М., 2005.

27. Фаддеев М. А., Марков К. А. Основные методы вычислительной математики. - М.: Изд-во Лань, 2008. - 160 с.

28. Численные методы. Сборник задач. Под редакцией У. Г. Пирумова. - М.: Изд-во Дрофа, 2007. - 144 с.

29. Шахов Ю. Н., Деза Е. И. Численные методы. - М.: Изд-во Либроком, 2010. - 248 с.

30. www.ziyonet.uz

31. www.samdu.uz

32. www.edu.uz

Размещено на Allbest.ru

...