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-c<0 then goto 2;

h:=-h/3;

if abs(h)>=abs(l/3) then goto 2;

h:=l; end;

l:=l/9; h:=l;

if e/9<=l then goto 1;

writeln('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-c<0 then goto 2; end;

h:=-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;