Скачать:  laba-2-fibonachchi.zip [297,76 Kb] (cкачиваний: 32)

Оптимизация технологического процесса

Метод поиска с использованием чисел Фибоначчи

                Показано, что свойства последовательности чисел Фибоначчи, описываемой рекуррентным соотношением

F_k= F_k-1+ F_k-2                 F₀= F₁=1              (1)

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

Доказывается, что если требуется найти положение экстремума функции R(х), определённой на интервале [a,b] с абсолютной ошибкой, не превышающей:

D= (b-a)/F_s                    (2)

где F_s – s-е число Фибоначчи, то для отыскания положения экстремума достаточно вычислить не более s значений функции R(x). Так, например, при выполнении s=21 расчетов определения экстремума состоит:

D/(b-a)=1/F_s≈0,56∙10^-4

Рассмотрим теперь алгоритм поиска, использующий числа Фибоначчи. Порядок его выполнения при поиске максимума складывается из следующих этапов:

1. По заданной точности D, с которой необходимо найти положение экстремума функции R(x) в интервале [a,b], рассчитывается вспомогательное число N:

N=(b-a)/D                    (3)

1. Для полученного значения N находится такое число Фибоначчи F_s, чтобы выполнялось неравенство:

F_s-1 <N<F_s                   (4)

1. Определяем минимальный шаг поиска по формуле:

D_m=(b-a)/F_s                    (5)

1. Рассчитываем значения на функции R(x) в начале интервала, т.е. R(a).
2. Следующая точка, в которой вычисляется значение R(x), находится по формуле:

x⁽¹⁾= a+D_mF_s-2               (6)

1. Если этот шаг оказался удачным, т.е. R(x⁽¹⁾)<R(a), то следующая точка определяется как

x⁽²⁾= x⁽¹⁾+D_mF_s-3                      (7)

При R(x⁽¹⁾)>R(a) (шаг неудачный)

x⁽²⁾= x⁽¹⁾ - D_mF_s-3                 (8)

1. Последующие шаги выполняются с уменьшающейся величиной шага, которая для i-го шага будет равна

Dx⁽ⁱ⁺¹⁾= ­±D_mF_s-i-2                 (9)

в соответствии со следующим правилом. Если при выполнении шага Dx⁽ⁱ⁾ значение функции в точке

x⁽ⁱ⁺¹⁾= x⁽ⁱ⁺¹⁾+Dx⁽ⁱ⁾                 (10)

оказывается больше, т.е. R(x⁽ⁱ⁺¹⁾)<R(x⁽ⁱ⁾) (шаг удачный), то следующий (i+1)-й шаг выполняется из точки x⁽ⁱ⁺¹⁾:

x⁽ⁱ⁺²⁾= x⁽ⁱ⁺¹⁾+Dx⁽ⁱ⁺¹⁾                        (11)

Если же i-й шаг оказался неудачный, т.е. R(x⁽ⁱ⁺¹⁾)>R(x⁽ⁱ⁾), то следующий (i+1)-й шаг выполняется из точки x⁽ⁱ⁾:

x⁽ⁱ⁺²⁾= x⁽ⁱ⁺¹⁾-Dx⁽ⁱ⁺¹⁾               (12)

Указанный процесс продолжается до тех пор, пока не будут исчерпаны все числа Фибоначчи в убывающей последовательности:

F_s-i-2= F_s-I – F_s-i-1                 i=0,1,2…             (13)

Задача:

Найти минимум функции y=x⁴-14x³+60x²-70x на интервале ( 5 ; 7) с точностью до 0,01. Сколько раз необходимо вычислить функцию?

Решение:

Найдем решение с помощью программы написанной на языке программирования Delphi 7, мнемоника выглядит так :

unit Unit1;

interface

uses

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

  Dialogs, Grids, StdCtrls, ComCtrls, TabNotBk, Buttons ,Math, ExtCtrls;

type

  TForm1 = class(TForm)

    Label1: TLabel;

    Label4: TLabel;

    Label5: TLabel;

    Label6: TLabel;

    Edit3: TEdit;

    Edit4: TEdit;

    Edit5: TEdit;

    BitBtn1: TBitBtn;

    Label7: TLabel;

    BitBtn2: TBitBtn;

    Label2: TLabel;

    procedure BitBtn1Click(Sender: TObject);

  private

    { Private declarations }

  public

    { Public declarations }

  end;

var

  Form1: TForm1;

   i,j,s,n,e:integer;

  G:array[1..100]of real;

  F:array[1..100] of real;

  Q:array[1..100] of real;

  dx:array[1..100] of real;

  d,x1,x2:real;

  dl,H:real;

  optim,Qoptim:real;

implementation

{$R *.dfm}

procedure TForm1.BitBtn1Click(Sender: TObject);

begin

x1:=StrToFloat(Edit3.Text);

x2:=StrToFloat(Edit4.Text);

d:=StrToFloat(Edit5.Text);

F[1]:=1; F[2]:=2;

For i:=3 to 100 do F[i]:=F[i-1]+F[i-2];

H:=(x2-x1)/d;

i:=1;

While F[i]<H do i:=i+1;

e:=i;

dl:=(x2-x1)/F[e];

G[1]:=x1;

  j:=0;

  n:=0;

  s:=e;

  optim:=0;

  for i:=1 to (e) do begin

                         n:=s-2-j;

                         j:=j+1;

                         dx[j]:=dl*F[n];

                     end;

  G[2]:=G[1]+dx[1];

  for i:=1 to (e-1) do begin

  Q[i]:=G[i]*G[i]*G[i]*G[i]-14*G[i]*G[i]*G[i]+60*G[i]*G[i]-70*G[i];

  Q[i+1]:=G[i+1]*G[i+1]*G[i+1]*G[i+1]-14*G[i+1]*G[i+1]*G[i+1]+60*G[i+1]

  *G[i+1]-70*G[i+1];

                   if Q[i+1]<Q[i] then

G[i+2]:=G[i+1]+dx[i+1];

            if Q[i+1]>Q[i] then G[i+2]:=G[i+1]-dx[i+1];

                   end ;

Qoptim:=G[e]*G[e]*G[e]*G[e]-14*G[e]*G[e]*G[e]+60*G[e]*G[e]-70*G[e];

Label7.Caption:= ‘Минимальное значение y= '+FloatToStr(RoundTo(Qoptim,-4))+

'  при x= '+FloatToStr(RoundTo(G[e],-4)) ;

Label2.Caption:=’Количество шагов = '+IntToStr(e) ;

end;

end.

Визуально программа выглядит так:

Для решения задачи  заполним поля программы и нажмем кнопку «Рассчитать»:

Оптимальное значение х=6,0558

 Проверим это с помощью программы MathCad:

Задача решена.