Cea mai simplă problemă de a găsi maximul unei funcții este rezolvată de următorul algoritm:
1. Se definesc limitele a și b, în care există o funcție maximă.
2. Intervalul [a, b] este împărțit într-un număr de pași.
3. Funcția este tabelată în intervalul specificat și fiecare valoare calculată a funcției este comparată cu valoarea maximă (specificată înainte de începerea tabulației).
4. Se găsește și se imprimă valoarea maximă a funcției la un anumit interval cu un anumit pas.
BLOG-SCHEMA ALGORITMUL VIZUALIZEAZĂ:
Fig. 4. Diagrama bloc a unui algoritm pentru găsirea maximului unei funcții
Firește, cu o scădere a pasului de a schimba argumentul, precizia de calcul a maximului crește.
Puteți utiliza următorul algoritm:
1. Gasiti valoarea maxima prin algoritmul prezentat mai sus.
2. Pentru o analiză suplimentară, selectați segmentul [xmax-dx, xmax + dx] și calculați maximul în pași, de exemplu, dx / 10.
3. Comparați cele două valori găsite.
max1 este valoarea maximă cu pasul dx și max2 este valoarea maximă cu pasul dx / 10. Dacă | max2-max1 | <=E (где Е – заданная степень точности вычисления), то закончить решение задачи и max2 вывести на печать, если нет, то вычисление продолжить дальше, повторяя п.2.
Este mai convenabil să rezolvați o astfel de problemă folosind procedura de identificare a valorii maxime a unei funcții.
Diagrama bloc a soluției problemei are forma:
Fig. 5. Diagrama bloc a unui algoritm pentru găsirea maximului unei funcții
Metode de optimizare a funcțiilor unei variabile
Metoda de căutare uniformă
Această metodă se bazează pe faptul că variabilei x îi sunt atribuite valorile x + # 8710; x în incremente # 8710; x = const și se calculează valorile lui F (x). Dacă F (x n + 1)> F (xn), variabila x primește o nouă creștere. De îndată ce F (xn + 1) devine mai mică decât F (x), căutarea se oprește. Cu o eroare mică predeterminată, această metodă nu este economică din punct de vedere al timpului calculatorului.
Metoda de aproximare bivalentă
Această metodă este o variantă a metodei de căutare uniformă și este implementată de următorul algoritm:
1. Definiți aproximația inițială x = x # 8320; la stânga maximului F (x) și calculați F (x # 8320;). Setați D = h, unde h = # 8710; x este pasul inițial de căutare.
2. Presupunem că G = F (xn), unde F (xn) = F (x # 8320;), am setat x = x + D și calculam F (x n + 1) = F (x).
3. Verificăm condiția F (x n # 8330; # 8321;)> G; dacă este, treceți la pasul 2, dacă nu, apoi la pasul 4.
4. Am stabilit D = -D / 4. Verificăm condiția | D |> E / 4, unde E este o eroare dată în calculul xn la punctul maxim. Dacă acest lucru se face, mergeți la pasul 2, adică Oferim o căutare maximă în cealaltă direcție cu un pas de 4 ori mai mic decât cel precedent. Dacă această condiție este îndeplinită, calculul este terminat.
Metoda de dihotomie (împărțirea intervalului de căutare [a, b] în jumătate) se realizează prin următorul algoritm:
1. Verificăm condiția | b-a |<2E, где E – заданная погрешность вычисления xn. Если это условие выполняется, идём к п.6; если не выполняется, идём к п.2.
2. Împărțiți intervalul de căutare [a, b] în jumătate și calculați două abscisuri dispuse simetric în jurul punctului
3. Pentru aceste valori ale lui x, calculăm F (x # 8321;)> F (x # 8322;).
4. Verificăm condiția F (x # 8321;)> F (x # 8322;). Dacă este satisfăcut, setați b = x # 8322; și treceți la pasul 1. Dacă nu, treceți la pasul 5.
5. Am setat a = x # 8321; și treceți la pasul 1.
6. Imprimați xn = (a + b) / 2 și calculați F (xn).
În metoda Fibonacci, punctul de divizare al intervalului de studiu este determinat cu fiecare nou calcul (în metoda dihotomiei, trebuie efectuate două calcule la fiecare pas). În intervalul de studiu, calculul anterior va cădea și pentru a continua căutarea este suficient să se efectueze un calcul simetric disponibil.
Să presupunem că este dat numărul de calcule (etape) N. Este necesar să le facem astfel încât intervalul în care se află optimul să fie minim. Numerele Fibonacci utilizate în această metodă sunt definite după cum urmează:
Algoritmul metodei Fibonacci constă în următoarele etape:
1) Schimbați scara intervalului inițial, în care se află optimul. Unitatea de măsură este 1 = X # 8320; / FN. sau dacă lungimea l este dată în care se află optimul, găsiți-o pe intervalul inițial de lungime X # 8320; Pentru aceasta, împărțind X # 8320; la 1, găsiți cel mai apropiat număr Fibonacci mai mare FN,
și determină N - numărul de calcule necesare pentru a determina intervalul.
2) Aranjați primele două puncte și în intervalul de studiu X0 la o distanță FN-2 de la capătul b.
3) Calculați valoarea funcției obiective în aceste puncte pentru a reduce intervalul de studiu. Să presupunem că>. apoi intervalul [. FN] este exclusă din considerente.
4) La un nou interval de cercetare, două puncte sunt plasate din nou. dar în una dintre ele valoarea funcției obiective = este deja cunoscută.
5) Mergeți la Pasul 3, etc. până la atingerea intervalului dorit, în care se găsește valoarea variabilei, care maximizează funcția obiectivă.
În Fig. 6 prezintă procesul de micșorare a intervalului de studiu:
Fig. 6. Procesul de reducere a intervalului de studiu.
Ultimul calcul N definește un interval de lungime l în care este localizat extremul funcției obiectiv.
Metoda secțiunii de aur
Secțiunea de aur împarte segmentul AB în două părți inegale, astfel încât raportul să fie valabil (Figura 7).
Metoda secțiunii de aur ne permite să restrângem intervalul [a, b] de fiecare dată prin calcularea unei singure valori a lui F (x) și nu a două, ca în metoda dihotomiei.
Această metodă este implementată de următorul algoritm:
1. Gasiti coeficientul de fragmentare k = (√5-1) / 2 al intervalului [a, b].
2. Gasiti abscisa x1 = a + (1-k) * (b-a) si calculati F (x1).
3. Gasiti abscisa x2 = a + k * (b-a) si calculati F (x2).
4. Verificăm dacă condiția | x2 -x1 | 5. Verificăm condiția F (x1)