1. Анализ модели и алгоритм решения задачи
Многомерная оптимизация заключается в поиске экстремумов функции многих переменных F(x1,x2,x3). Наиболее простым является метод покоординатного спуска, и его разновидность спиральный покоординатный спуск.
Метод покоординатного спуска заключается в поочередном поиске минимума по координате х1, затем х2 и т.д. После нахождения точки минимума по координате х1 переходим к нахождению точки минимума по координате х2 и т.д. Поиск ведется с одинаковым шагом, который уменьшается после нахождения всех значений . Таким образом, алгоритм реализации этого метода подобен алгоритму метода поразрядного приближения и лишь дополняется циклом задания переменных х1,х2 и т.д., внутри которого оценивается погрешность нахождения для каждой переменной.
Метод спирального покоординатного спуска отличается от рассмотренного выше лишь тем, что шаг H меняется каждый раз при переходе от поиска минимума по одной переменной к поиску минимума по другой переменной. В трехмерном пространстве это напоминает спуск во впадину по спирали. Обычно этот метод дает некоторое сокращение времени поиска.
Алгоритм решения:
Метод покоординатного спуска
N-количество переменных
E-точность результата
H- начальный шаг поиска
A[i]- массив начальных значений X[i]
B,C,L-вспомогательные переменные.
Func- заданная функция
Блок-схема: ??????
Реализация задачи в Turbo Pascal:
Этапы решения:
· создание UNIT- модуля
· создание рабочей программы.
UNIT –модуль состоит из трех функций и двух процедур. Процедуры реализуют алгоритм поиска минимума функции многих переменных методом покоординатного спуска (pmmks) и методом спирального покоординатного спуска(pmmsks). Функции (f1,f2,f3) возвращают значения:
Программа представлена в виде меню выбора метода поиска и функции:
После выбора метода появляется меню выбора функции
Далее, в зависимости от выбранного метода и функции идет запрос начальных значений, точности и т.п., а также поиск минимума функции в отдельном окне.
Например: поиск минимума методом покоординатного спуска функции №1
Тестирование программы:
Функция
Метод покоординатного спуска:
Начальный шаг поиска 0,5
Точность 0,0001
х1=х2=х3=0,5
Fmin:=3.735451794
X1m:=0.999974
X2m:=1.999997
X3m:=2.99999
Метод спирального покоординатного спуска:
Начальный шаг поиска 0,5
Точность 0,0001
х1=х2=х3=0,5
Fmin:=3.735451794
X1m:=1.000032
X2m:=2.000032
X3m:=3.000032
Код программы:
Модуль PMIN
unit PMIN;
interface
uses CRT;
type
mas=array[1 20] of real;
function f1(a1,a2,a3:real):real;
function f3 (a1,a2:real):real;
function f2(a1,a2:real):real;
procedure pmmks(nom:integer);
procedure pmmsks(nom:integer);
implementation
function f1(a1,a2,a3:real):real;
begin f1:=exp(a1+a2+a3)/(a1*sqr(a2)*sqr(a3)*a3); end;
function f2(a1,a2:real):real;
begin f2:=sqr(sqr(a1)+sqr(a2)-1)+sqr(sqr(a1)*a1+a2); end;
function f3(a1,a2:real):real;
begin f3:=2*a1-3.5*a2+exp(sqr(a1)+sqr(a2)); end;
procedure pmmks(nom:integer);
label 1,2;
var a:mas; y,h,e,l,b,c:real; i,n:integer;
begin clrscr;
case nom of
1: n:=3;
2: n:=2;
3: n:=2; end;
writeln('введите начальный шаг поиска'); readln(h);
writeln('введите точность '); readln(e);
for i:=1 to n do begin
write('введите начальные x',i,'=');
readln(a[i]); end;
l:=h;
1: for i:=1 to n do begin b:=0.9E38;
2: a[i]:=a[i]+h;
case nom of
1:y:=f1(a[1],a[2],a[3]);
2:y:=f2(a[1],a[2]);
3:y:=f3(a[1],a[2]); end;
c:=b; b:=y;
if y-ch:=-h/3;
if abs(h)>=abs(l/3) then goto 2;
h:=l; end;
l:=l/9; h:=l;
if e/9writeln('fmin=',y:4:10);
for i:=1 to n do
writeln('x',i,'min=',a[i]:4:10); end;
procedure pmmsks(nom:integer);
label 1,2;
var
a:mas; y,h,e,b,c:real; i,n:integer;
begin clrscr;
case nom of
1: n:=3;
2: n:=2;
3: n:=2; end;
writeln('введите начальный шаг поиска'); readln(h);
writeln('введите точность'); readln(e);
for i:=1 to n do begin write('x',i,'=');readln(a[i]); end;
1:for i:=1 to n do begin b:=0.9E38;
2: a[i]:=a[i]+h;
case nom of
1: y:=f1(a[1],a[2],a[3]);
2: y:=f2(a[1],a[2]);
3: y:=f3(a[1],a[2]); end;
c:=b; b:=y;
if y-ch:=-h/5;
if abs(h)>e/5 then goto 1;
writeln('fmin=',y:4:10);
for i:=1 to n do
writeln(a[i]:4:10);
end;
end.
Программа
program kurs;
uses crt,pmin;
label 1,2,3,4,5;
type
mas=array[1 3] of string[31];
mas1=array[1 3] of string[42];
const
stor:mas=(' покоординатный спуск ',
'спиральный покоординатный спуск',
' выход ');
stor2:mas1=(' f(x1,x2,x3)=exp(x1+x2+x3)/(x1*x2^2*x3^3)',
' f(x1,x2)=(x1^2+x2^2-1)^2+(x1^3-x2)^2 ',
' f(x1,x2)=2*x1-3.5*x2+exp(x1^2 +x2^2) ');
var i,k,k1:integer; kod:char;
begin
textmode(co80); clrscr; window(10,10,40,15);
textbackground(1); textcolor(14); clrscr;
k:=1;
1: for i:=1 to 3 do begin
if i=k then begin textbackground(14); textcolor(1); end else
begin textbackground(1); textcolor(14); end;
gotoxy(1,i+2); write(stor[i]); end;
while true do begin
kod:=readkey;
sound(700); delay(500); nosound;
if kod=#13 then goto 2;
if kod=#0 then begin kod:=Readkey;
if kod=#72 then begin
if k>1 then k:=k-1
else k:=3; goto 1; end;
if kod=#80 then begin if kgoto 1; end;end;
2:if (k=1) or (k=2) then begin
clrscr; window(10,10,50,15); textbackground(1); textcolor(14);
clrscr; k1:=1;
4:for i:=1 to 3 do begin
if i=k1 then begin textbackground(14); textcolor(1); end else
begin textbackground(1); textcolor(14); end;
gotoxy(1,i+2); write(stor2[i]); end;
while true do begin
kod:=readkey; sound(700); delay(500); nosound;
if kod=#13 then goto 3;
if kod=#0 then begin
kod:=Readkey;
if kod=#72 then begin
if k1>1 then k1:=k1-1
else k1:=3; goto 4; end;
if kod=#80 then begin if k13:CASE k of
1: begin clrscr; window(10,10,50,20); pmmks(k1); end;
2: begin clrscr; window(10,10,50,20); pmmsks(k1); end;
end;
5: kod:=Readkey;
end.