Optimizare conditionata si neconditionata, domenii de aplicare. Metode de optimizare necondiționată și condiționată Metode de evaluări ale experților
Din setul total de opțiuni, puteți construi o histogramă, puteți evalua cât de des sunt opțiunile bune și, în final, puteți decide dacă continuați căutarea sau vă limitați la soluția găsită.
În ciuda universalității și simplității procedurii de sondare aleatoare, aceasta nu poate fi limitată din cauza complexității computaționale semnificative. Prin urmare, metodele căutare dirijată solutii.
4.5.3. Metode de optimizare necondiționată
Condițiile necesare pentru atingerea unui extrem în toate formele considerate mai sus conduc la rezolvarea unui sistem de ecuații neliniare - o sarcină foarte complexă și consumatoare de timp (chiar și în matematica computațională, soluția ecuațiilor neliniare este adesea redusă la un fel de problema de optimizare). Prin urmare, în practică, sunt utilizate și alte abordări de optimizare a funcțiilor, a căror considerare va începe cu așa-numitele metode directe. În viitor, vom vorbi aici despre minimizare, deci extremul este minim.
În prezent, multe metode numerice au fost dezvoltate atât pentru problemele de optimizare necondiționată, cât și pentru cele condiționate. Calitatea unei metode numerice este caracterizată de mulți factori: rata de convergență, timpul de execuție a unei iterații, cantitatea de memorie de calculator necesară implementării metodei, clasa de probleme de rezolvat etc. Problemele de rezolvat sunt, de asemenea, foarte diverse: pot avea dimensiuni mari și mici, pot fi unimodale și multiextremale etc. Aceeași metodă care este eficientă pentru rezolvarea problemelor de un tip poate fi complet inacceptabilă pentru probleme de alt tip.
Mai jos este o prezentare generală a principalelor metode de rezolvare a problemelor de programare neliniară. Trebuie avut în vedere faptul că întreaga listă a unor astfel de metode este foarte largă și rămâne deschisă. În plus, sunt cunoscute diferite modificări pentru o serie de metode luate în considerare. Informații mai detaliate pot fi obținute la-
exemplu, în .
Să începem prin a lua în considerare metode directe de optimizare neconstrânsă atunci când nu există constrângeri.
Sensul metodelor directe de optimizare necondiționată este de a construi o succesiune de puncte X , X , ..., X , astfel
că f (X )>f (X )>… …>f (X ). Un punct arbitrar poate fi ales ca punct de plecare al lui X, cu toate acestea, se tinde să-l aleagă cât mai aproape de punctul minim. Tranziția (iterația) de la punctul X la punctul X , k =0,1,2,... constă în două etape:
– alegerea direcției de mișcare dintr-un punct X ;
– definirea pasului în această direcție.
Metodele de construire a unor astfel de secvențe sunt adesea numite metode de coborâre, deoarece se realizează tranziția de la valori mai mari ale funcției la cele mai mici.
Matematic, metodele de coborâre sunt descrise prin relație
X =X + a k p , k =0,1,2,...,
unde p este un vector unitar care determină direcția de coborâre;
a k este lungimea pasului.
Diferitele metode de coborâre diferă unele de altele prin modul în care sunt alese p și a k. În practică, se folosesc numai metode cu convergență. Ele permit un număr finit de pași pentru a obține un punct minim sau pentru a se apropia suficient de acesta. Calitatea metodelor iterative convergente este evaluată prin rata de convergență.
Teoretic, în metodele de descendență, problema se rezolvă într-un număr infinit de iterații. În practică, calculele sunt oprite atunci când sunt îndeplinite anumite criterii (condiții) pentru oprirea procesului iterativ. De exemplu, aceasta poate fi condiția naturii mici
argument |
X[ k] − X[ k − 1 ] |
||||||
f(X[k]) − f(X[k−1])< γ . Здесь k – номер итерации; ε , γ – задан-
nye valorile acurateței soluționării problemei.
Metodele de găsire a punctului minim sunt numite deterministe dacă ambii parametri ai tranziției de la X la X (direcția de mișcare și dimensiunea pasului) sunt aleși în mod unic în funcție de informațiile disponibile în punctul X. Dacă se folosește vreun mecanism aleatoriu în timpul tranziției, atunci algoritmul de căutare se numește căutare minimă aleatorie.
Algoritmii de minimizare neconstrânși determiniști sunt împărțiți în clase în funcție de tipul de informații utilizate. Dacă la fiecare iterație sunt folosite doar valorile funcțiilor minimizate, atunci metoda se numește metoda de ordinul zero. Dacă, în plus, este necesar să se calculeze primele derivate ale funcției care este minimizată, atunci există metode de ordinul întâi,
dacă este necesar, calcul suplimentar al derivatelor secunde - metode de ordinul doi.
Trebuie remarcat faptul că la rezolvarea problemelor de minimizare necondiționată, metodele de ordinul întâi și al doilea au de obicei o rată de convergență mai mare decât metodele de ordin zero. Totuși, în practică, calculul primei și a doua derivate ale unei funcții a unui număr mare de variabile este foarte laborios. În unele cazuri, acestea nu pot fi obținute sub formă de funcții analitice. Derivate prin diverse metode numerice sunt determinate cu erori care pot limita utilizarea unor astfel de metode. În plus, criteriul de optimitate poate fi specificat nu în mod explicit, ci printr-un sistem de ecuații. În acest caz, devine foarte dificil, și uneori imposibil, să găsiți derivatele analitic sau numeric. Prin urmare, metodele de ordinul zero sunt luate în considerare aici în cele mai multe detalii.
Metode de căutare unidimensională. Lista metodelor de căutare unidimensională - căutare numerică pentru extremul unei funcții a unui argument f(x ) este destul de larg și bine acoperit în literatură. Prin urmare, aici ne limităm să luăm în considerare o singură metodă, care, conform experienței autorilor, este una dintre cele mai eficiente, metoda „secțiunii de aur”.
Ideea metodei este de a reduce constant intervalul de incertitudine - intervalul de valori ale argumentului x care conține punctul minim dorit - la o lungime care să nu depășească
eroare de rezultat admisibilă ε . Ca interval inițial, intervalul de valori admisibil al argumentului specificat de condițiile problemei sau, în cazul în care acesta din urmă nu are limite stânga și (sau) dreaptă, o zonă în interiorul celei admisibile, la care minimul dorit este indicat printr-o analiză preliminară, poate fi luat în considerare.
În interiorul oricărui interval există două puncte x = y 0 și x = z 0 , care efectuează „secțiunea de aur” - împărțindu-se în două părți inegale, astfel încât raportul dintre partea mai mare și lungimea întregului interval să coincidă cu raportul dintre partea mai mică față de cea mai mare. Evident, aceste puncte sunt situate simetric în raport cu centrul intervalului (Fig. 26). Coordonatele punctelor „secțiunii de aur” pot fi găsite din proporțiile corespunzătoare:
b − y0 |
y0 − a |
= δ , |
z0 − a |
b − z0 |
= δ, |
||||
b - a |
de |
b - a |
− a |
||||||
de unde se obține ușor δ = (1–δ)/δ și se ajunge la ecuația: δ 2 + δ –1=0. Ca rezultat, obținem cotele relative care determină „secțiunea de aur” a intervalului: δ = 0,618, 1–δ = 0,382. Raportul de Aur are proprietate importantă: punctul y 0 este unul dintre punctele „secțiunii de aur” a intervalului , punctul z 0 este unul dintre punctele „secțiunii de aur” a intervalului . În această ucidere
Un calcul simplu vă așteaptă: 0,382/0,618 = 0,618 și (0,618–0,382)/0,618 = = 0,382.
Algoritmul de căutare minimă, construit pe baza metodei „secțiunii de aur”, prevede alegerea la fiecare iterație a punctului din stânga sau din dreapta „secțiunii de aur” ca una dintre limitele intervalului redus în așa fel încât minimul dorit este stocat în interiorul acestuia:
1. Setați k =0, intervalul inițial de incertitudine , eroarea rezultatului admisibil ε .
2. Calculați coordonatele punctelor „secțiunii de aur”:
y k \u003d a k +0,382 (b k - a k), z k \u003d a k +0,618 (b k - a k ).
3. Calculați valorile funcției obiectiv la punctele găsite
f (y k ) și f (z k ).
4. Dacă f (yk) ≤ f (zk) (Fig. 26, dar), atribuiți ak + 1 =ak, bk + 1 =zk, zk + 1 =yk, yk + 1 =ak +zk –yk, k =k+1. În caz contrar (Fig. 26, b) a k + 1 =y k, b k + 1 = b k, y k + 1 = z k, z k + 1 = y k + b k –z k, k = k +1.
5. Verificați îndeplinirea condiției de finalizare a căutării
b k + 1 − a k + 1 ≤ ε . Dacă este îndeplinită, se alege ca soluție punctul x = (y k + 1 + z k + 1 ) 2. În caz contrar, treceți la pasul 2.
Eficiența de calcul a metodei „secțiunii de aur” se datorează faptului că aici, la fiecare iterație, este necesar doar un singur calcul al valorii funcției obiectiv.
Metoda de căutare directă (metoda Hooke-Jeeves). niste
al doilea punct de plecare X . Schimbând alternativ componentele vectorului X, ei examinează vecinătatea acestui punct, în urma căruia găsesc un punct (nouă bază) care determină direcția în care funcția minimizată f(X) scade. Coborârea se efectuează în direcția aleasă, asigurându-vă că valoarea funcției scade. Procedura se repetă ciclic până când este posibilă găsirea direcției de coborâre, ținând cont de condiția de oprire acceptată.
Algoritmul metodei de căutare directă în forma sa cea mai generală poate fi formulat după cum urmează:
1. Setați prin valorile coordonatelor x i , i= 1,2,…n , punctul de plecare (k = 0), vectorul creșterilor inițiale de coordonate
∆ X = (∆ x 1 , ∆ x 2 ,…, ∆ xn ) în procesul de topografie a vecinătății, cea mai mică valoare admisă a componentei ε ∆ X , factorul de accelerare λ ≥ 1, care determină viteza de coborâre, factorul de scară d>1.
2. Luați X pentru „baza veche”: X b \u003d X. calculati
valoarea f (X b).
3. Schimbați alternativ fiecare coordonată x b i, i = 1,2, ... n,
punctele X b după valoarea ∆ x i, adică luați x i \u003d x b i + ∆ x i, atunci
x i \u003d x b i -∆ x i. Calculați valorile lui f (X ) în punctele de testare rezultate și comparați-le cu valoarea lui f (X b ). Dacă f(X)< < f
(X
б
), то соответствующая координата х
i
приобретает новое значение, вычисленное по одному из приведенных выражений. В противном случае значение этой координаты остается неизменным. Если после изменения последней n
-й координаты f
(X
) 4. Ei coboară în direcția de la baza „veche” la baza „nouă” prin aceasta din urmă, adică calculează coordonatele noului punct X: x i \u003d x i + λ (x i - x bi), i \u003d 1,2, ... n. Calculați valoarea lui f(X). Dacă condiția f (X) Baza „nouă” este acceptată ca fiind cea „veche” (X b \u003d X, f (X b) \u003d f (X)) și treceți la pasul 5. În caz contrar, iau xi \u003d xi, i \u003d 1.2, ... n . 5.
Ca și în paragraful 3, schimbați alternativ fiecare coordonată a punctului X prin compararea valorilor corespunzătoare ale funcției f (X) cu valoarea f (X) obținută la pasul 4. După modificarea ultimei coordonate, comparați valoarea corespunzătoare funcțiile f (X ) cu valoarea f (X b ) obținută la pasul 4. Dacă f (X ) 6. Dacă pentru tot i ∆ x i<ε
, вычисления прекращаются. В противном случае уменьшают значения ∆
х
i
в d
раз и переходят к п. 3. Funcționarea algoritmului este ilustrată în fig. 27. Liniile prezentate nivelul funcției minimizate f (x 1 ,x 2 ), adică liniile obținute din condițiile f (x 1 ,x 2 )=f 1 =const, f (x 1 ,x 2 )=f 2 =const și deci Mai departe. Aici f 1 >f 2 >f 3 . Liniile continue sunt rezultatele unei singure execuții de pași. 3...5 (căutați direcția de scădere a funcției și coborâți), linia punctată este următoarea coborâre. Avantajul metodei de căutare directă este simplitatea programării acesteia pe computer. Nu necesită cunoaștere explicită a funcției obiectiv și, de asemenea, ia în considerare cu ușurință restricțiile asupra variabilelor individuale, precum și restricțiile complexe privind domeniul de aplicare al căutării. Dezavantajul metodei de căutare directă este că, în cazul liniilor de nivel ale funcției obiective foarte alungite, curbe sau cu unghi ascuțit, este posibil să nu poată furniza progrese până la punctul minim din cauza numărului limitat de direcții analizate. Metoda poliedrului deformabil (metoda Nelder-Mead) este că pentru a minimiza funcția n variabile f(X) în n-dimensionale spațiu, se construiește un poliedru care conține n +1 de sus. Evident, fiecare vârf îi corespunde unui vector Xi . Calculați valorile funcției obiective f(Xi), i=1,2,…, n +1, la fiecare dintre vârfurile poliedrului, determinați maximul acestor valori și vârful corespunzător xh . Prin acest vârf și centrul de greutate al vârfurilor rămase se trasează o linie proeminentă, pe care se află punctul xq cu o valoare mai mică a funcţiei obiectiv decât în vârf Xh (Fig. 28, a ). Apoi eliminați vârful xh . Din nodurile și punctele rămase xq construiți un nou poliedru, cu care se repetă procedura descrisă. În procesul de efectuare a unor astfel de operații, poliedrul își schimbă dimensiunile, ceea ce a condus la denumirea metodei. Să introducem următoarea notație: X este vectorul de coordonate al i-lea vârf al poliedrului la k-a etapă de căutare, i= 1,2,…n +1, k= 1,2,…; h este numărul vârfului la care se află valoarea țintei cauciucuri cu excepția lui X . Se calculează coordonatele centrului de greutate xj[n + 2, k] = n+ 1 formulă ∑ xj[i, k] − xj[h, k] J= 1,2,...n. j=1 Un algoritm exemplificativ pentru metoda poliedrului deformabil este următorul: 1.
Specificată prin coeficienți de reflexieα , tensiuni γ >1, compresiuni β<1
, допустимой погрешностью определения координат puncte de minim ε . Alegeți coordonatele vârfurilor poliedrului original X , i= 1,2,…n +1, k= 1. 2.
Calculați valorile funcției obiective la toate vârfurile f (X ), i = 1,2,…n +1 și găsiți punctele X , X (în Fig. 28, b punctele X 2 și respectiv X 1 ), precum și X . 3.
Proiectarea unui punct X prin centrul lui staniu: X \u003d X + α (X -X). 4. Dacă f (X) ≤ X, efectuați o operație de întindere ion: X \u003d X + γ (X -X). În caz contrar, treceți la pasul 6. 5.
Construiți un nou poliedru: dacă f(X) prin înlocuirea X cu X , altfel prin înlocuirea X cu X . Continuați calculele cu elementul 2 pentru k =k +1. 6. Dacă X >f (X )>X pentru tot i nu este egal cu h , efectuați operația de compresie: X =X +β (X – X). Construiți un nou poliedru înlocuind X cu X și continuați calculele de la pasul 2 pentru k =k +1. 7. Dacă f (X)>X, atunci, păstrând vârful X, construiți un nou poliedru, similar celui actual, prin reducerea lungimii tuturor muchiilor la jumătate: X \u003d X +0,5 (X -X) și continuă calculele de la pasul 2 pentru k=k+1. În pp. 6, 7, înainte de a trece la pasul 2, este necesar să se verifice îndeplinirea condiției de finalizare a căutării pentru un minim, de exemplu, conform condiției vizualizare max n ∑ + 1 (x j [ i ,k ] − x j [ n + 2,k ] ) 2< ε
2
. i j = 1 DIN Cu ajutorul operațiilor de întindere și contracție, dimensiunile și forma poliedrului deformabil sunt adaptate topografiei funcției obiectiv. Ca urmare, poliedrul se întinde de-a lungul suprafețelor lungi înclinate, își schimbă direcția în depresiuni curbe și se micșorează în apropierea minimului, ceea ce determină eficiența metodei luate în considerare. α =1, 2≤ y ≤3, 0,4≤β ≤0,6. Metoda de rotație a coordonatelor (metoda lui Rosenbrock). Esența sa constă în rotații succesive ale sistemului de coordonate în conformitate cu schimbarea direcției celei mai rapide scăderi a funcției obiectiv (Fig. 29). Din punctul de plecare X coboara pana la punct X în direcţii paralele cu axele de coordonate. La următoarea iterație, una dintre axe trebuie să treacă în direcție x'1 = X–X, restul sunt in directii perpendiculare pe x'1 . Coborârea de-a lungul acestor axe duce la punct X , ceea ce face posibilă construirea unui nou vector x''1 = X– X și pe baza acestuia un nou sistem de direcții de căutare punctul minim al lui X. ÎN Spre deosebire de alte metode de ordin zero, metoda Rosenbrock se concentrează pe găsirea punctului optim în fiecare direcție, și nu doar pe o deplasare fixă în toate direcțiile. Dimensiunea pasului în procesul de căutare se modifică continuu în funcție de topografia suprafeței de nivel. Combinația de rotație a coordonatelor cu controlul pașii face ca metoda Rosenbrock să fie eficientă în rezolvarea problemelor complexe de optimizare. ÎN În special, această metodă, spre deosebire de multe altele, este eficientă în reducerea la minimum a așa-numitelor funcții „de râpă” (cu suprafețe de nivel foarte alungite), deoarece direcția de căutare rezultată tinde să fie situată de-a lungul axei „gârpă”. Metoda tangentelor paralele (metoda lui Powell). Esența sa este de a efectua secvențial o căutare unidimensională a minimului funcției obiectiv prin direcția n+1 din metodele unidimensionale cunoscute. La prima iterație ca prima n direcţiile sunt alese coordonate, ca(n+1)-lea directii, se foloseste primul dintre ele (Fig. 30). La fiecare iterație ulterioară, căutarea începe din a doua direcție a iterației anterioare, respectiv, numărul de direcții se reduce cu unul;(n+1)-lea direcția iterației ulterioare este dată de vector X–X[ n+1] – de la punctul minim găsit la primul pas al iterației anterioare, până la punctul minim găsit la ultimul pas. 5.
Optimizare multidimensională
Programare liniară
Optimizare
este o activitate cu scop, constând în obținerea celor mai bune rezultate în condiții adecvate. Se numește cuantificarea calității optimizate criteriul de optimitate
sau funcție obiectivă
.Se poate scrie ca: (5.1)
unde x 1 , x 2 , … , x nsunt câțiva parametri ai obiectului de optimizare. Există două tipuri de probleme de optimizare - necondiționate și condiționate. Sarcina necondiționată
optimizarea constă în găsirea maximului sau minimului funcţiei reale (5.1) anvariabilele reale și determinarea valorilor argumentului adecvate. Probleme de optimizare condiționată
, sau probleme cu restricții, sunt cele în formularea cărora se impun restricții asupra valorilor argumentelor sub formă de egalități sau inegalități. Rezolvarea problemelor de optimizare în care criteriul de optimitate este o funcție liniară a variabilelor independente (adică conține aceste variabile la gradul I) cu constrângeri liniare asupra lor este subiectul. programare liniară.
Cuvântul „programare” reflectă aici scopul final al studiului - de a determina planul optim sau programul optim, conform căruia cea mai bună, optimă, opțiune este aleasă dintre numeroasele opțiuni posibile pentru procesul studiat. Un exemplu
o astfel de sarcină este problema repartizării optime a materiilor prime
între diferite industrii la costul maxim de producţie. Să fie făcute două tipuri de produse din două tipuri de materii prime. Notați: x 1 , x 2 - numărul de unități de produse de primul și, respectiv, al doilea tip; c 1 , c 2 sunt prețuri unitare ale produselor de primul și, respectiv, al doilea tip. Atunci costul total al tuturor produselor va fi:
(5.2)
Ca rezultat al producției, este de dorit ca costul total de producție să fie maxim.R (x 1 , x 2 ) este funcția obiectivă în această problemă. b 1 , b 2 - cantitatea de materii prime de primul și al doilea tip disponibilă;aij- Număr de unități i
al-lea tip de materie primă necesară producerii unei unitățijal-lea tip de produs. Având în vedere că consumul acestei resurse nu poate depăși cantitatea sa totală, notăm condițiile restrictive pentru resurse: (5.3)
Referitor la variabile x 1, x 2 putem spune, de asemenea, că sunt nenegative și infinite.: (5.4)
Dintre mulțimea de soluții ale sistemului de inegalități (5.3) și (5.4), este necesară găsirea unei astfel de soluții ( x 1, x 2 ), pentru care funcțiaRatinge cea mai mare valoare. Așa-numitele sarcini de transport (sarcini de organizare optimă a livrării de mărfuri, materii prime sau produse din diverse depozite către mai multe destinații cu costuri minime de transport) și o serie de altele sunt formulate într-o formă similară. Metodă grafică pentru rezolvarea unei probleme de programare liniară.
Să fie necesar să se găsească x 1 și x 2 , satisfăcător sistem de inegalități: (5.5)
si conditii non-negativitatea:
(5.6)
pentru care functie (5.
7
)
atinge un maxim. Soluţie.
Să construim în sistemul de coordonate dreptunghiulare x 1 Ox 2 zona de soluții fezabile la problemă (Fig. 11). Pentru a face acest lucru, înlocuind fiecare dintre inegalitățile (5.5) cu o egalitate, construim relevante el o linie de hotar: (i = 1, 2, … ,
r)
Orez. unsprezece Această linie împarte întregul plan în două semiplane. Pentru coordonate x 1, x 2 orice punct DAR un semiplan, este valabilă următoarea inegalitate: și pentru coordonatele oricărui punct ÎN celălalt semiplan, inegalitatea opusă: Coordonatele oricărui punct al liniei de limită satisfac ecuația: Pentru a determina pe ce parte a liniei de frontieră se află semiplanul corespunzător inegalității date, este suficient să „testăm” un punct (cel mai simplu punct DESPRE(0;0)). Dacă, la înlocuirea coordonatelor sale în partea stângă a inegalității, aceasta este satisfăcută, atunci semiplanul este întors spre punctul de testare, dacă inegalitatea nu este satisfăcută, atunci semiplanul corespunzător este rotit în direcția opusă. Direcția semiplanului este prezentată în desen prin hașurare. Inegalități: corespund semiplanului situat în dreapta axei ordonatelor și deasupra axei absciselor. În figură, construim linii de limită și semiplanuri corespunzătoare tuturor inegalităților. Partea comună (intersecția) tuturor acestor semiplanuri va fi zona de soluții fezabile la această problemă. La construirea domeniului soluțiilor fezabile, în funcție de tipul particular de sistem de constrângeri (inegalități) asupra variabilelor, poate apărea unul dintre următoarele patru cazuri: Orez. 12. Zona soluțiilor fezabile este goală, ceea ce corespunde inconsecvenței sistemului de inegalități; Nici o soluție Orez. 13. Aria soluțiilor permise este reprezentată de un punct A, care corespunde singurei soluții a sistemului Orez. 14. Zona soluțiilor fezabile este limitată, reprezentată ca un poligon convex. Există un număr infinit de soluții posibile Orez. 15. Aria soluțiilor admisibile este nelimitată, sub forma unei zone poligonale convexe. Există un număr infinit de soluții posibile Reprezentarea grafică a funcției obiectiv la o valoare fixăRdefinește o linie dreaptă, iar la schimbareR- familie de linii paralele cu parametruR. Pentru toate punctele situate pe una dintre linii, funcția R ia o valoare definită, astfel încât aceste linii sunt numite linii de nivel
pentru funcția R. Vector gradient:
perpendicularla liniile de nivel, arată direcția de creștereR.
Problema găsirii unei soluții optime la sistemul de inegalități (5.5) pentru care funcția obiectivR(5.7) atinge un maxim, se reduce geometric la determinarea în regiunea soluțiilor fezabile a punctului prin care va trece linia de nivel, corespunzător celei mai mari valori a parametruluiR Orez. 16 Dacă domeniul soluțiilor fezabile este un poligon convex, atunci extremul funcțieiR
este atins cel puțin la unul dintre vârfurile acestui poligon. Dacă valoarea extremăReste atinsă la două vârfuri, atunci aceeași valoare extremă este atinsă în orice punct al segmentului care leagă aceste două vârfuri. În acest caz, se spune că sarcina are optim alternativ
.
În cazul unei regiuni nemărginite, extremul funcțieiRfie nu există, fie este atins la unul dintre vârfurile regiunii, fie are un optim alternativ. Exemplu.
Să fie necesar să se găsească valorile x 1 și x 2 , satisfacerea sistemului de inegalități: si conditii non-negativitatea:
pentru care functie: atinge un maxim. Soluţie.
Să înlocuim fiecare dintre inegalități cu o egalitate și să construim liniile de limită: Orez. 17 Să determinăm semiplanurile corespunzătoare acestor inegalități „testând” punctul (0;0). Tinand cont non-negativitatea x 1 și x 2 obținem aria soluțiilor fezabile ale acestei probleme sub forma unui poligon convex OAVDE.
În zona soluțiilor fezabile, găsim soluția optimă prin construirea vectorului gradient arătândsens ascendentR.
Soluția optimă corespunde punctului ÎN, ale căror coordonate pot fi determinate fie grafic, fie prin rezolvarea unui sistem de două ecuații corespunzătoare liniilor de limită AB și VD: Răspuns:
x 1 = 2; x 2 \u003d 6; Rmax = 22.
Sarcini.
Aflați poziția punctului extremum și valoarea extremă a funcției obiectiv sub anumite restricții. Tabelul 9 Extremum M topor Max ;
;
;
;
Optimizarea este procesul de găsire a unui extremum (maxim sau minim global) al unei anumite funcții sau de alegere a celei mai bune opțiuni (optimale) dintr-o varietate de opțiuni posibile. Cea mai fiabilă modalitate de a găsi cea mai bună opțiune este o evaluare comparativă a tuturor opțiunilor posibile (alternative). Dacă numărul de alternative este mare, metodele de programare matematică sunt de obicei folosite pentru a găsi cea mai bună. Aceste metode pot fi aplicate dacă există o enunțare strictă a problemei: se stabilește un set de variabile, aria posibilei modificări ale acestora (se stabilesc limitări) și tipul funcției obiectiv (funcția al cărei extrem trebuie să fie găsit) dintre aceste variabile este determinată. Acesta din urmă este o măsură cantitativă (criteriu) de evaluare a gradului de realizare a scopului. Problema optimizării neconstrânse este de a găsi minimul sau maximul unei funcții în absența oricăror restricții. În ciuda faptului că majoritatea sarcini practice optimizarea conține limitări, studiul metodelor de optimizare neconstrânsă este important din mai multe puncte de vedere. Mulți algoritmi pentru rezolvarea unei probleme constrânse implică reducerea acesteia la o secvență de probleme de optimizare neconstrânse. O altă clasă de metode se bazează pe găsirea unei direcții adecvate și minimizarea ulterioară pe această direcție. Justificarea metodelor de optimizare neconstrânsă poate fi extinsă în mod firesc la justificarea procedurilor de rezolvare a problemelor cu constrângeri. Problema optimizării condiționale este de a găsi valoarea minimă sau maximă a funcției scalare f(x) a argumentelor vectoriale n-dimensionale. Rezolvarea problemei se bazează pe o aproximare liniară sau pătratică a funcției obiectiv pentru a determina incrementele x1, ..., xn la fiecare iterație. Există și metode aproximative pentru rezolvarea problemelor neliniare. Acestea sunt metode bazate pe metoda aproximării liniare pe bucăți. Acuratețea găsirii soluțiilor depinde de numărul de intervale în care găsim o soluție la o problemă liniară cât mai apropiată de una neliniară. Această metodă face posibilă efectuarea de calcule folosind metoda simplex. De obicei, în modelele liniare, coeficienții funcției obiectiv sunt constanți și nu depind de valoarea variabilelor. Cu toate acestea, există o serie de probleme în care costurile depind de volum în mod neliniar. Algoritm de rezolvare: Sarcină: optimizarea capacității. Obțineți costuri minime pentru fabricarea unui container de 2750 de litri pentru depozitarea nisipului. Z = C1X1 + C2X2 + C3X3 + C4X4 + C5X5 min; unde: X1 - cantitatea de metal necesară, kg; C1 - costul metalului, rub/kg; X2 - masa electrozilor necesari, kg; C2 - costul electrozilor, rub/kg; X3 - cantitatea de energie electrică consumată, kWh; C3 - costul energiei electrice, rub/kWh; X4 - timpul de lucru al sudorului, h; C4 - tariful sudorului, rub/h; X5 - timp de funcționare a liftului, h; C5 - plata pentru lift, frecare / h. 1. Găsiți suprafața optimă a containerului: F = 2ab+2bh+2ah min (1) unde V=2750 litri. x1=16,331; x2=10,99 Minimul funcției a fost obținut în procesul de optimizare prin metoda Box - 1196,065 dm2 În conformitate cu GOST 19903 - 74, vom accepta: h=16,50 dm, b=10,00 dm. Să exprimăm a din (1) și să obținem: Calculați grosimea optimă a tablei de metal Să alegem oțelul carbon obișnuit St2sp Pentru acest otel 320 MPa, ; Masa de nisip. Încărcare pe peretele rezervorului de cea mai mare suprafață: Calculăm sarcina pe 1 centimetru liniar al unei foi de 100 cm lățime: Determinăm grosimea peretelui în funcție de condiția: unde: l este lungimea foii (de preferință cea mai mare pentru a pleca stoc suplimentar putere); q - sarcina la 1 centimetru liniar, kg/cm; Grosimea tablei de metal, m Tensiunea maximă admisă a metalului, N/mm2. Exprimăm din (2) grosimea peretelui: Având în vedere că 320 MPa = 3263 kg/cm2, Masa de metal unde: F - suprafata rezervorului, m2; Grosimea peretelui metalic, m; Densitatea metalului, kg/m3. Prețul oțelului St2sp este de aproximativ 38 de ruble/kg. 2. Lungimea sudurii: Să folosim electrozi pentru oțel inoxidabil „UONI-13/45” Preț 88,66 ruble / kg; unde: sudare - aria secțiunii transversale a îmbinării sudate, m2; l este lungimea sudurii, m; Densitatea metalului depus, kg/m3. 3. Timp de sudare: unde l este lungimea sudurii, m; v - viteza de sudare, m/h. Consum total de energie: Рsum = 5 17 = 85 kWh; Costul energiei electrice este de 5,7 ruble / kWh. 4. Pentru sudarea manuală cu arc, costul timpului și timpul auxiliar, pregătitor și final pentru întreținerea locului de muncă este în medie de 40 - 60%. Să folosim valoarea medie de 50%. Timpul total: Plata pentru un sudor din categoria VI - 270 de ruble / oră. Plus un coeficient tarifar de 17% pentru lucru într-un spațiu închis, slab ventilat: Salariul asistentului va fi de 60% din salariul sudorului: 8055 0,6 = 4833 ruble. Total: 8055 + 4833 = 12888 ruble. 5. Va fi necesară o macara pentru a ține foile de metal în timpul sudării, încărcării și descărcarii foilor de metal și containerul finit în sine. Pentru a „prinde” întreaga structură, sudorul trebuie să aplice aproximativ 30% din cusături. Plata pentru macara - 1000 de ruble / oră. Costul total al containerului. Printre metodele de optimizare de ordinul zero din CAD se folosesc metodele Rosenbrock, configurațiile, poliedrul deformabil și metodele de căutare aleatoare. Metodele care utilizează derivate includ metode de coborâre abruptă, gradienți conjugați, metrici variabile. Metoda lui Rosenbrock este o versiune îmbunătățită a coborârii coordonate. Metoda coborării coordonate caracterizat prin alegerea direcțiilor de căutare la rândul lor de-a lungul tuturor axelor de coordonate, pasul este calculat pe baza optimizării unidimensionale, criteriul de terminare a căutării , unde este precizia specificată de determinare a extremului local, este dimensiunea spațiului de parametri controlați. Traiectoria de coborâre în funcție de coordonate pentru un exemplu de spațiu bidimensional de parametri controlați este prezentată în fig. 1, unde sunt punctele de pe traiectoria de căutare, sunt parametrii controlați. Funcția obiectiv este reprezentată de liniile sale de nivel egal, lângă fiecare linie se scrie valoarea corespunzătoare acesteia. Evident, există un punct minim. Orez. 1. Coordonează traiectoria de coborâre Când se folosește metoda de coborâre prin coordonate, există o mare probabilitate ca căutarea să se „blocheze” în partea de jos a râpei, departe de punctul extremum. Pe fig. 2 arată că după lovirea punctului situat în fundul râpei, pașii ulterioare sunt posibili numai în direcțiile sau , dar conduc la o deteriorare a funcției obiectivului. Prin urmare, căutarea se termină în punctul . Nota 1 O râpă este o parte a spațiului parametrilor controlați în care există modificări slabe ale derivatelor funcției obiectiv într-o direcție și modificări semnificative cu o schimbare de semn în alte direcții. Semnul derivatului se modifică în punctele aparținând fundului râpei. Orez. 3. Traiectorie de coborâre în coordonate cu o orientare favorabilă a axelor de coordonate metoda Rosenbrock constă într-o astfel de rotație a axelor de coordonate astfel încât una dintre ele să se dovedească a fi cvasi-paralelă cu fundul râpei. O astfel de rotație se realizează pe baza datelor obținute după o serie de pași de coborâre coordonate. Poziția noilor axe se poate obține printr-o transformare liniară a vechilor axe: axa coincide în direcție cu vectorul; axele rămase sunt alese din condiția de ortogonalitate între ele și unul față de celălalt. O altă modificare reușită a coborârii coordonate este metoda de configurare(Hook-Jeeves). În conformitate cu această metodă, se efectuează mai întâi seria obișnuită de pași de coborâre în coordonate, apoi se face un pas suplimentar în direcția vectorului , așa cum se arată în Fig. 4, unde se efectuează un pas suplimentar în direcția vectorului , care duce la punctul . Orez. 4. Ilustrație a metodei de configurare Găsirea unui extremum metoda poliedrului deformabil(Nelder-Mead) se bazează pe construcția unui poliedru cu vârfuri la fiecare pas de căutare, unde este dimensiunea spațiului parametrilor controlați. La începutul căutării, aceste vârfuri sunt alese în mod arbitrar; la pașii următori, alegerea este supusă regulilor metodei. Aceste reguli sunt ilustrate în Fig. 5 despre exemplul unei probleme de optimizare bidimensională. Se selectează vârfurile triunghiului original: , , . Noul vârf se află pe raza trasă din cel mai rău vârf (din vârful cu cea mai mare valoare funcţie obiectiv) prin centrul de greutate al poliedrului, şi se recomandă să alegeţi la o distanţă de , egală cu . Noul blat înlocuiește cel mai prost blat. Dacă se dovedește că are cea mai bună valoare a funcției obiectiv dintre vârfurile poliedrului, atunci distanța este mărită. În figură, exact aceasta este situația și creșterea dă un punct. Într-un nou poliedru cu vârfuri , , cel mai rău vârf este ; în mod similar, se obține vârf , apoi vârf și așa mai departe. Dacă noul vârf se dovedește a fi mai rău, atunci cel mai bun vârf ar trebui să fie păstrat în poliedru, iar lungimile tuturor muchiilor ar trebui reduse, de exemplu, la jumătate (contractând poliedrul la cel mai bun vârf). Căutarea se oprește atunci când este îndeplinită condiția de reducere a dimensiunii poliedrului la o anumită limită. pasul este ales să fie optim utilizând optimizarea unidimensională. Când se folosește cea mai abruptă metodă de coborâre, la fel ca majoritatea celorlalte metode, eficiența căutării este redusă semnificativ în situații de râpă. Traiectoria de căutare capătă o formă în zig-zag cu progres lent de-a lungul fundului râpei spre extremum. Pentru a crește eficiența metodelor de gradient, sunt utilizate mai multe trucuri. Una dintre metodele folosite în metoda gradientului conjugat(numită și metoda Fletcher-Reeves) se bazează pe conceptul de conjugație a vectorilor. Vectorii și se numesc -conjugate dacă , unde este o matrice pătrată definită pozitiv de același ordin cu dimensiunea vectorilor și (un caz special de conjugare este ortogonalitatea vectorilor când este o matrice de identitate de ordin ), este un vector rând , este un vector coloană. Particularitatea direcțiilor conjugate pentru , unde este matricea Hessian , în problemele cu o funcție obiectiv pătratică este următoarea: minimizarea unidimensională succesiv de-a lungul direcțiilor conjugate face posibilă găsirea punctului extrem în nu mai mult de pași. Nota 2 Matricea Hessiană este matricea derivatelor parțiale secundare ale funcției obiectiv în raport cu parametrii controlați. Motivul utilizării căutării în direcții adiacente este acela că pentru funcțiile () de formă generală se poate aplica o aproximare pătratică, care în practică are ca rezultat efectuarea căutării în mai mult decât pași. Căutarea unui extremum se efectuează în conformitate cu formula Deoarece pasul este calculat pe baza condiției de optimizare unidimensională, atunci, în primul rând, relația Algoritmul de căutare se reduce la aplicarea formulei (3) până când este îndeplinită condiția de încheiere a calculelor Pentru a determina coeficientul, rezolvați sistemul de ecuații (2)-(7) prin înlocuirea în (4) a valorilor din (3) și din (2): Dacă procesul converge, atunci soluția este atinsă într-un număr mic de iterații, al căror sfârșit este îndeplinirea condiției De aceea Se poate arăta că tinde spre , — la ca , unde este dimensiunea spațiului parametrilor controlați. După pași, trebuie să începeți din nou cu.
Restricții
; 
;
; ;
;
;
;
;
;
;
;
;
;
;
;
;
unde este un coeficient. În plus, se ține cont de condiția de conjugare
sau
Unde
și ținând cont de (6) și (7)
Expresia (10) este un sistem de ecuații algebrice liniare. Rădăcina sa este o altă aproximare a soluției
Unde
