Cea mai acceptabilă versiune a deciziei care se ia la nivel de management cu privire la orice problemă este considerată a fi optimă, iar procesul de căutare în sine este considerat optimizare.

Interdependența și complexitatea aspectelor organizaționale, socio-economice, tehnice și de altă natură ale managementului producției se rezumă în prezent la luarea unei decizii de management, care afectează un număr mare de tipuri diferite de factori strâns întrepătrunși între ei, ceea ce face imposibilă analizarea fiecăruia. separat folosind metode analitice tradiționale.

Majoritatea factorilor sunt determinanți în procesul de luare a deciziilor și ei (în esența lor) nu se pretează la nicio caracterizare cantitativă. Există și cele care sunt practic neschimbate. În acest sens, a devenit necesară dezvoltarea unor metode speciale capabile să asigure selecția unor decizii importante de management în cadrul unor probleme organizatorice, economice, tehnice complexe (evaluări de specialitate, cercetare a operațiunilor și metode de optimizare etc.).

Metodele care vizează cercetarea operațiunilor sunt utilizate pentru a găsi soluții optime în domenii precum organizarea proceselor de producție și transport, planificarea producției pe scară largă, aprovizionarea cu materiale și tehnică.

Metodele de optimizare a deciziei constau în studiul prin compararea estimărilor numerice ale unui număr de factori, a căror analiză nu poate fi efectuată prin metode tradiționale. Soluția optimă este cea mai bună dintre opțiunile posibile pentru sistemul economic, iar soluția cea mai acceptabilă pentru elementele individuale ale sistemului este suboptimă.

Esența metodelor de cercetare operațională

După cum am menționat mai devreme, ele formează metode de optimizare a deciziilor de management. Ele se bazează pe modele matematice (deterministe), probabilistice, care reprezintă procesul investigat, tipul de activitate sau sistemul. Modelele de acest fel oferă o caracterizare cantitativă a problemei corespunzătoare. Ele servesc drept bază pentru luarea unei decizii importante de management în procesul de căutare a opțiunii optime acceptabile.

Lista problemelor care joacă un rol semnificativ pentru managerii direcți de producție și care sunt rezolvate în cursul utilizării metodelor luate în considerare:

  • gradul de validitate al opțiunilor selectate pentru decizii;
  • cu cât mai bune decât cele alternative;
  • gradul în care sunt luați în considerare determinanții;
  • care este criteriul de optimizare a soluţiilor selectate.

Aceste metode de optimizare a deciziilor (managerial) au ca scop gasirea de solutii optime pentru cat mai multe firme, companii sau divizii ale acestora. Ele se bazează pe realizările existente ale disciplinelor statistice, matematice și economice (teoria jocurilor, coadă, diagrame, programare optimă, statistică matematică).

Metode de evaluare a experților

Aceste metode de optimizare a deciziilor manageriale sunt utilizate atunci când sarcina nu este parțial sau complet supusă formalizării și, de asemenea, soluția acesteia nu poate fi găsită prin metode matematice.

Expertiza este un studiu al unor probleme speciale complexe aflate în stadiul de elaborare a unei anumite decizii manageriale de către persoane adecvate, care au un depozit special de cunoștințe și o experiență impresionantă pentru a obține concluzii, recomandări, opinii, aprecieri. În procesul cercetării expertului, cele mai recente realizări atât ale științei, cât și ale tehnologiei sunt aplicate în cadrul specializării expertului.

Metodele luate în considerare de optimizare a unui număr de decizii manageriale (evaluări ale experților) sunt eficiente în rezolvarea următoarelor sarcini manageriale în domeniul producției:

  1. Studiul proceselor, fenomenelor, situațiilor, sistemelor complexe care se caracterizează prin caracteristici calitative, neformalizate.
  2. Clasificarea si determinarea, dupa un criteriu dat, a factorilor esentiali care sunt determinanti pentru functionarea si dezvoltarea sistemului de productie.
  3. Metodele de optimizare avute în vedere sunt deosebit de eficiente în prezicerea tendințelor de dezvoltare a sistemului de producție, precum și a interacțiunii acestuia cu mediul extern.
  4. Creșterea fiabilității evaluării de către experți a funcțiilor preponderent țintă, care sunt cantitative și calitative, prin medierea opiniilor specialiștilor calificați.

Iar acestea sunt doar câteva dintre metodele de optimizare a unui număr de decizii de management (evaluarea expertului).

Clasificarea metodelor luate în considerare

Metodele de rezolvare a problemelor de optimizare, pe baza numărului de parametri, pot fi împărțite în:

  • Metode de optimizare unidimensională.
  • Tehnici de optimizare multidimensională.

Ele sunt numite și „metode de optimizare numerică”. Pentru a fi precis, aceștia sunt algoritmii pentru găsirea acestuia.

În cadrul aplicării instrumentelor derivate, metodele sunt:

  • metode directe de optimizare (ordine zero);
  • metode de gradient (ordinul I);
  • metode de ordinul 2 etc.

Majoritatea metodelor de optimizare multidimensională sunt apropiate de problema celui de-al doilea grup de metode (optimizarea unidimensională).

Metode de optimizare unidimensională

Orice metode de optimizare numerică se bazează pe un calcul aproximativ sau exact al unor caracteristici precum valorile funcției obiectiv și ale funcțiilor care definesc mulțimea admisibilă și derivatele acestora. Deci, pentru fiecare problemă individuală, problema alegerii caracteristicilor pentru calcul poate fi rezolvată în funcție de proprietățile existente ale funcției luate în considerare, capacitățile disponibile și limitările în stocarea și procesarea informațiilor.

Există următoarele metode pentru rezolvarea problemelor de optimizare (unidimensionale):

  • metoda Fibonacci;
  • dihotomii;
  • ratia de aur;
  • dublarea pasului.

Metoda Fibonacci

Mai întâi, trebuie să setați coordonatele m. X pe interval ca un număr egal cu raportul dintre diferența (x - a) și diferența (b - a). Prin urmare, a are coordonata 0 în raport cu intervalul, iar b - 1, punctul de mijloc - ½.

Dacă presupunem că F0 și F1 sunt egale între ele și luăm valoarea 1, F2 va fi egal cu 2, F3 - 3, ..., atunci Fn = Fn-1 + Fn-2. Deci, Fn sunt numere Fibonacci, iar căutarea Fibonacci este strategia optimă a așa-numitei căutări maxime secvențiale datorită faptului că este destul de strâns legată de acestea.

În cadrul strategiei optime, se obișnuiește să se aleagă xn - 1 = Fn-2: Fn, xn = Fn-1: Fn. Pentru oricare dintre cele două intervale (sau), fiecare dintre ele poate acționa ca un interval de incertitudine restrâns, punctul (moștenit) relativ la noul interval va avea fie coordonate, fie. În plus, ca xn - 2, este luat un punct care are una dintre coordonatele prezentate relativ la noul interval. Dacă utilizați F (xn - 2), valoarea funcției, care este moștenită din intervalul anterior, devine posibilă reducerea intervalului de incertitudine și moștenirea unei valori a funcției.

La pasul final, se va dovedi a merge la un astfel de interval de incertitudine, în timp ce punctul de mijloc este moștenit de la pasul anterior. Ca x1, se stabilește un punct care are o coordonată relativă ½ + ε, iar intervalul final de incertitudine va fi sau [½, 1] în raport cu.

La primul pas, lungimea acestui interval a fost redusă la Fn-1: Fn (de la unu). La etapele de finisare, scurtarea lungimilor intervalelor corespunzătoare este reprezentată de numerele Fn-2: Fn-1, Fn-3: Fn-2,…, F2: F3, F1: F2 (1 + 2ε). Deci, lungimea unui astfel de interval ca versiunea finală va lua valoarea (1 + 2ε): Fn.

Dacă neglijăm ε, atunci asimptotic 1: Fn va fi egal cu rn, cu n → ∞, și r = (√5 - 1): 2, care este aproximativ egal cu 0,6180.

Trebuie remarcat că asimptotic pentru n semnificativ, fiecare pas ulterior al căutării Fibonacci restrânge semnificativ intervalul luat în considerare cu coeficientul de mai sus. Acest rezultat trebuie comparat cu 0,5 (coeficientul de îngustare a intervalului de incertitudine în cadrul metodei bisecției pentru a găsi zeroul funcției).

Metoda dihotomiei

Dacă vă imaginați o funcție obiectivă, atunci mai întâi trebuie să găsiți extremul acesteia pe intervalul (a; b). Pentru a face acest lucru, axa absciselor este împărțită în patru părți echivalente, apoi este necesar să se determine valoarea funcției luate în considerare în 5 puncte. Apoi este selectat minimul dintre ele. Extremul funcției trebuie să se afle în intervalul (a „; b”), care este adiacent punctului minim. Limitele de căutare sunt restrânse de 2 ori. Și dacă minimul este situat în punctul a sau b, atunci se îngustează de patru ori. Noul interval este, de asemenea, împărțit în patru segmente egale. Datorită faptului că valorile acestei funcții în trei puncte au fost determinate în etapa anterioară, atunci este necesar să se calculeze funcția obiectiv în două puncte.

Metoda secțiunii de aur

Pentru valori semnificative ale lui n, coordonatele unor puncte precum xn și xn-1 sunt apropiate de 1 - r, egale cu 0,3820 și r ≈ 0,6180. Impingerea de la aceste valori este foarte aproape de strategia optimă dorită.

Dacă presupunem că F (0,3820)> F (0,6180), atunci se conturează un interval. Cu toate acestea, deoarece 0,6180 * 0,6180 ≈ 0,3820 ≈ xn-1, atunci în acest punct F este deja cunoscut. În consecință, la fiecare etapă, începând din a 2-a, este nevoie de un singur calcul al funcției obiectiv, iar fiecare pas reduce lungimea intervalului considerat cu un factor de 0,6180.

Spre deosebire de căutarea Fibonacci, această metodă nu necesită fixarea numărului n înainte de a începe căutarea.

„Secțiunea de aur” a unei secțiuni (a; b) este o secțiune în care raportul dintre lungimea sa r și partea mai mare (a; c) este identică cu raportul dintre partea mai mare r și cea mai mică, adică , (a; c) la (c; b). Este ușor de ghicit că r este determinat de formula de mai sus. În consecință, pentru n semnificativ, metoda Fibonacci trece la cea dată.

Metoda de dublare a pașilor

Esența este căutarea direcției de scădere a funcției obiectiv, mișcare în această direcție în cazul unei căutări reușite cu pas treptat în creștere.

Mai întâi, determinăm coordonata inițială M0 a funcției F (M), valoarea minimă a pasului h0 și direcția de căutare. Apoi definim funcția în punctul M0. Apoi, facem un pas și găsim valoarea acestei funcție în acest moment.

Dacă funcția este mai mică decât valoarea care a fost în pasul anterior, ar trebui să faceți următorul pas în aceeași direcție, după ce a mărit-o anterior de 2 ori. Dacă valoarea sa este mai mare decât cea anterioară, va trebui să schimbați direcția de căutare și apoi să începeți să vă deplasați în direcția aleasă cu un pas h0. Algoritmul prezentat poate fi modificat.

Tehnici de optimizare multivariată

Metoda de ordin zero menționată mai sus nu ia în considerare derivatele funcției minimizate, prin urmare, utilizarea lor poate fi eficientă în cazul oricăror dificultăți în calcularea derivatelor.

Grupul de metode de ordinul I se mai numește și gradient, deoarece pentru a stabili direcția căutării se folosește gradientul funcției date - un vector, ale cărui componente sunt derivatele parțiale ale funcției minimizate în raport cu parametrii optimizați corespunzători.

În grupul metodelor de ordinul doi se folosesc 2 derivate (utilizarea lor este destul de limitată din cauza prezenței dificultăților în calculul lor).

Lista metodelor de optimizare fără restricții

Când utilizați căutarea multidimensională fără a utiliza derivate, metodele de optimizare neconstrânsă sunt următoarele:

  • Hook and Jeeves (implementarea a 2 tipuri de cautare - model si cercetare);
  • minimizarea în ceea ce privește simplexul corect (căutați punctul minim al funcției corespunzătoare comparând la fiecare iterație separată a valorilor sale la vârfurile simplexului);
  • coborare ciclică de coordonate (folosind vectori de coordonate ca puncte de referință);
  • Rosenbrock (bazat pe utilizarea minimizării unidimensionale);
  • minimizarea față de un simplex deformat (modificarea metodei de minimizare față de un simplex obișnuit: adăugarea unei proceduri de compresie, întindere).

În situaţia utilizării derivatelor în procesul de căutare multidimensională se distinge metoda de coborâre cea mai abruptă (procedeul cel mai fundamental de minimizare a unei funcţii diferenţiabile cu mai multe variabile).

De asemenea, există și astfel de metode care folosesc direcții conjugate (metoda Davidon-Fletcher-Powell). Esența sa este reprezentarea direcțiilor de căutare ca Dj * grad (f (y)).

Clasificarea metodelor de optimizare matematică

În mod convențional, pe baza dimensiunii funcțiilor (țintă), acestea sunt:

  • cu 1 variabilă;
  • multidimensionale.

În funcție de funcție (liniară sau neliniară), există un număr mare de metode matematice care vizează găsirea unui extremum pentru rezolvarea unei anumite probleme.

Conform criteriului de aplicare a derivatelor, metodele de optimizare matematică se subdivizează în:

  • metode de calcul a 1 derivată a funcției obiectiv;
  • multidimensional (prima derivată-vector mărime-gradient).

Pe baza eficienței calculului, există:

  • metode pentru calcularea rapidă a extremului;
  • calcul simplificat.

Aceasta este o clasificare condiționată a metodelor luate în considerare.

Optimizarea proceselor de afaceri

Aici pot fi folosite diferite metode, în funcție de problemele rezolvate. Se obișnuiește să se evidențieze următoarele metode pentru optimizarea proceselor de afaceri:

  • excepții (reducerea nivelurilor procesului existent, eliminarea cauzelor interferenței și controlului de intrare, reducerea rutelor de transport);
  • simplificare (facilitarea trecerii comenzii, complexitatea redusă a structurii produsului, distribuția muncii);
  • standardizare (utilizarea de programe speciale, metode, tehnologii etc.);
  • accelerare (inginerie paralelă, stimulare, proiectare prototip operațional, automatizare);
  • schimbare (modificări în domeniul materiilor prime, tehnologii, metode de lucru, aranjarea personalului, sisteme de lucru, volumul comenzilor, ordinea de procesare);
  • asigurarea interactiunii (in raport cu unitatile organizatorice, personalul, sistemul de munca);
  • selecția și includerea (în raport cu procesele, componentele necesare).

Optimizare fiscală: metode

Legislația rusă oferă contribuabilului oportunități foarte bogate pentru reduceri de impozite, motiv pentru care se obișnuiește să se evidențieze astfel de metode care vizează minimalizarea lor ca fiind generale (clasice) și speciale.

Metodele generale de optimizare fiscală sunt următoarele:

  • elaborarea politicii contabile a companiei cu utilizarea la maximum a oportunităților oferite de legislația rusă (procedura de anulare a IBE, alegerea metodei de calcul a încasărilor din vânzarea mărfurilor etc.);
  • optimizare prin intermediul unui contract (încheierea de tranzacții preferențiale, utilizarea clară și competentă a formulării etc.);
  • aplicarea diferitelor tipuri de beneficii, scutiri fiscale.

Al doilea grup de metode poate fi folosit și de toate firmele, dar au încă un domeniu de aplicare destul de restrâns. Metodele speciale de optimizare fiscală sunt următoarele:

  • înlocuirea relațiilor (o operațiune care prevede o impozitare oneroasă este înlocuită cu alta care vă permite să atingeți un obiectiv similar, dar să utilizați în același timp o procedură de impozitare preferențială).
  • separarea relațiilor (înlocuirea doar a unei părți a unei tranzacții comerciale);
  • amânarea plății impozitului (amânarea momentului în care obiectul impozitării apare la o altă perioadă calendaristică);
  • reducerea directă a obiectului impozitării (scăparea multor tranzacții sau proprietăți impozabile fără a afecta negativ activitatea principală a companiei).

5. Optimizare multidimensională

Programare liniară

Optimizare - este o activitate cu scop, care consta in obtinerea celor mai bune rezultate in conditiile corespunzatoare.

Se numește evaluarea cantitativă a calității optimizate criteriul de optimitate sau funcția țintă Se poate scrie ca:

(5.1)

unde x 1, x 2, ..., x n- unii parametri ai optimizării obiectului.

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) anvariabile valide și definirea valorilor argumentului corespunzătoare.

Probleme de optimizare condiționată , sau probleme cu constrângeri, sunt cele în formularea cărora se impun constrângeri 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 în gradul I) cu constrângeri liniare asupra acestora face obiectul programare liniară.

Cuvântul „programare” reflectă aici scopul final al studiului - determinarea planului optim sau programului optim, conform căruia cea mai bună, optimă, variantă este selectată din setul de variante posibile ale procesului studiat.

Un exemplu o astfel de sarcină este repartizarea optimă 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.

Să notăm: x 1, x 2 - numărul de unități de produse de primul și, respectiv, al doilea tip; c 1, c 2 –Unități de produse 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 maximizat.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ă;a ij- Număr de unități i -al-lea tip de materie prima necesara producerii unei unitatij-al-lea tip de produs.

Având în vedere că consumul unei anumite resurse nu poate depăși cantitatea ei totală, notăm condițiile restrictive pentru resurse:

(5.3)

Variabile x 1, x 2 putem spune, de asemenea, că sunt nenegative și nu sunt 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.

Într-o formă similară sunt formulate așa-numitele sarcini de transport (sarcini de organizare optimă a livrărilor 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.

O metodă grafică pentru rezolvarea problemelor de programare liniară.

Să fie necesar să 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.

Graficul într-un sistem de coordonate dreptunghiular x 1 Ox 2 zona de soluții fezabile la problemă (Fig. 11). Pentru aceasta, înlocuind fiecare dintre inegalitățile (5.5) cu egalitate, construim corespondența pentru 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 A un semiplan, este valabilă următoarea inegalitate:

și pentru coordonatele oricărui punct V celălalt semiplan este 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 unei inegalități date, este suficient să „testăm” un punct (cel mai simplu punct este O(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 semiplanurilor situate în dreapta ordonatei și deasupra abscisei.

În figură, construim linii de limită și semiplanuri corespunzătoare tuturor inegalităților.

Partea comună (intersecția) tuturor acestor semiplanuri va reprezenta regiunea soluțiilor fezabile ale acestei probleme.

La construirea regiunii soluțiilor fezabile, în funcție de tipul specific de sistem de constrângeri (inegalități) asupra variabilelor, poate apărea unul dintre următoarele patru cazuri:

Orez. 12. Regiunea soluțiilor fezabile este goală, ceea ce corespunde inconsecvenței sistemului de inegalități; Nici o soluție

Orez. 13. Regiunea soluțiilor fezabile este reprezentată de un punct A, care corespunde singurei soluții a sistemului

Orez. 14. Regiunea soluțiilor fezabile este mărginită, reprezentată ca un poligon convex. Există un set infinit de soluții fezabile

Orez. 15. Regiunea soluțiilor fezabile este nelimitată, sub forma unei regiuni poligonale convexe. Există un set infinit de soluții fezabile

Reprezentarea grafică a funcției obiective

cu o valoare fixăRdefinește o linie dreaptă, iar la schimbareR- o familie de linii paralele cu parametrulR. Pentru toate punctele situate pe una dintre linii, funcția R ia o valoare definită, prin urmare 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 soluției optime a sistemului de inegalități (5.5) pentru care funcția obiectivR(5.7) atinge un maxim, se reduce geometric la determinarea în regiunea soluțiilor admisibile a punctului prin care linia de nivel corespunzătoare celei mai mari valori a parametruluiR

Orez. 16

Dacă regiunea soluțiilor fezabile este un poligon convex, atunci extremul funcțieiR este atins cel puțin la unul dintre vârfurile acestui poligon.

Dacă valoare 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ă problema 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.

Înlocuim fiecare dintre inegalități cu egalitate și construim liniile de limită:

Orez. 17

Să definim semiplanurile corespunzătoare acestor inegalități „testând” punctul (0; 0). Tinand cont non-negativitatea x 1 și x 2 obținem regiunea soluțiilor fezabile ale acestei probleme sub forma unui poligon convex OAVDE.

În regiunea soluțiilor fezabile, găsim soluția optimă prin construirea vectorului gradient

arătândsens ascendentR.

Soluția optimă corespunde punctului V, ale cărui 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 = 6; R max = 22.

Sarcini. Aflați poziția punctului extremum și valoarea extremă a funcției obiectiv

sub restrictiile date.

Tabelul 9

Opțiunea nr.

Extremum
Restricții

M topor

; ;

; ;

Max

; ; ;

;

; ;

; ;

; ;

; ; ;

;

; ;


Metode clasice de optimizare neconstrânsă

Introducere

După cum știți, problema clasică a optimizării neconstrânse are forma:

Există metode analitice și numerice pentru rezolvarea acestor probleme.

În primul rând, să ne amintim metodele analitice pentru rezolvarea problemei optimizării neconstrânse.

Metodele de optimizare neconstrânse ocupă un loc semnificativ în cursul ML. Acest lucru se datorează aplicării lor directe în rezolvarea unui număr de probleme de optimizare, precum și în implementarea metodelor de rezolvare a unei părți semnificative a problemelor de optimizare condiționată (probleme MT).

1. Condiții necesare pentru punctul de minim local (maximum)

Fie m să livreze valorile minime ale funcției. Se știe că în acest moment incrementul funcției este nenegativ, adică.

Să găsim, folosind expansiunea funcției în vecinătatea lui m din seria Taylor.

unde, este suma membrilor seriei a căror ordine este relativă la incrementele (două) și mai mari.

Din (4) rezultă clar că

Să presupunem că, atunci

Ținând cont de (6) avem:. (7)

Să presupunem că este pozitiv, adică. ... Să alegem, deci, un produs, care contrazice (1).

Prin urmare, este cu adevărat evident.

Argumentând în mod similar față de alte variabile, obținem o condiție necesară pentru punctele de minim local ale unei funcție a mai multor variabile

Este ușor de demonstrat că condițiile necesare pentru punctul maxim local vor fi exact aceleași ca și pentru punctul minim local, i.e. condiţii (8).

Este clar că rezultatul demonstrației va fi o inegalitate de forma: - condiția pentru o creștere nepozitivă a unei funcții într-o vecinătate a unui maxim local.

Condițiile necesare obținute nu răspund la întrebarea: este punctul staționar un punct minim sau un punct maxim.

Răspunsul la această întrebare poate fi obținut examinând condițiile suficiente. Aceste conditii presupun studiul matricei derivatelor secunde ale functiei obiectiv.

2. Condiții suficiente pentru punctul de minim local (maxim)

Reprezentăm expansiunea unei funcții într-o vecinătate a unui punct dintr-o serie Taylor până la termeni patratici.

Extinderea (1) poate fi prezentată mai concis folosind conceptul: „produs punctual al vectorilor” și „produs vector-matrice”.

Matricea a doua derivate ale functiei obiectiv in raport cu variabilele corespunzatoare.

Incrementul funcției bazat pe (1 ") poate fi scris ca:

Având în vedere condițiile necesare:

Înlocuiți (3) sub forma:

Forma pătratică se numește formă pătratică diferențială (DKF).

Dacă DKF este definit pozitiv, atunci punctul staționar este, de asemenea, un punct minim local.

Dacă DKF și matricea care o reprezintă sunt definite negativ, atunci punctul staționar este și un punct maxim local.

Deci, condițiile necesare și suficiente pentru un punct de minim local au forma

(aceleași condiții necesare pot fi scrise după cum urmează:

Stare suficientă.

În consecință, condiția necesară și suficientă pentru maximul local are forma:

Să reamintim criteriul pentru a determina dacă forma pătratică și matricea care o reprezintă sunt definite pozitive sau definite negative.

3. Criteriul Sylvester

Vă permite să răspundeți la întrebarea: este forma pătratică și matricea care o reprezintă definită pozitiv sau definită negativă.

Se numește matricea Hesse.

Principalul determinant al matricei Hesse

iar DKF-ul pe care îl reprezintă va fi definit pozitiv dacă toți determinanții principali ai matricei Hessian () sunt pozitivi (adică, are loc următoarea schemă de semne:

Dacă există o schemă diferită de semne pentru determinanții principali ai matricei Hessian, de exemplu, atunci matricea și DKF sunt definite negativ.

4. Metoda lui Euler este o metodă clasică de rezolvare a problemelor de optimizare neconstrânsă

Această metodă se bazează pe condițiile necesare și suficiente studiate la 1.1 la 1.3; ne aplicăm numai pentru găsirea extremelor locale ale funcțiilor diferențiabile continue.

Algoritmul pentru această metodă este destul de simplu:

1) folosind condițiile necesare, formăm un sistem de ecuații neliniare în cazul general. Rețineți că este imposibil să rezolvați acest sistem analitic în cazul general; este necesar să se aplice metode numerice pentru rezolvarea sistemelor de ecuații neliniare (NE) (vezi „FM”). Din acest motiv, metoda lui Euler va fi o metodă analitico-numerică. Rezolvând sistemul de ecuații specificat, găsim coordonatele punctului staționar .;

2) investigăm DKF și matricea hessiană care o reprezintă. Folosind criteriul Sylvester, determinăm dacă punctul staționar este un punct minim sau un punct maxim;

3) calculați valoarea funcției obiectiv în punctul extrem

Folosind metoda Euler, rezolvați următoarea problemă de optimizare neconstrânsă: găsiți 4 puncte staționare ale unei funcții de forma:

Aflați natura acestor puncte, indiferent dacă sunt puncte minime sau puncte de șa (vezi). Construiți o afișare grafică a acestei funcții în spațiu și pe un plan (folosind linii de nivel).

5. Problema clasică a optimizării condiționate și metodele de soluționare a acesteia: Metoda eliminării și Metoda multiplicatorilor Lagrange (MLM)

După cum știți, problema clasică a optimizării condiționate are forma:

Grafic care explică enunțul problemei (1), (2) în spațiu.

Ecuații ale liniilor de nivel

Deci, ODR din problema luată în considerare este o anumită curbă reprezentată de ecuația (2").

După cum puteți vedea din figură, punctul este punctul maximului global necondiționat; punct - punctul minimului local condiționat (relativ); punct - punctul maximului local condiționat (relativ).

Problema (1"), (2") poate fi rezolvată prin metoda eliminării (substituirii), rezolvând ecuația (2") față de variabilă și înlocuind soluția găsită (1").

Problema inițială (1 "), (2") este astfel transformată într-o problemă de optimizare neconstrânsă a funcției, care poate fi rezolvată cu ușurință prin metoda Euler.

Metoda excluderii (substituirii).

Fie ca funcția obiectiv să depindă de variabile:

se numesc variabile dependente (sau variabile de stare); în consecință, putem introduce vectorul

Variabilele rămase se numesc variabile de decizie independente.

În consecință, putem vorbi despre un vector coloană:

și vectori.

În problema clasică de optimizare condiționată:

Sistemul (2), în conformitate cu metoda excluderii (substituirii), trebuie rezolvat în raport cu variabilele dependente (variabilele de stare), adică. trebuie obținute următoarele expresii pentru variabilele dependente:

Sistemul de ecuații (2) este întotdeauna rezolvabil în raport cu variabilele dependente - nu întotdeauna, acest lucru este posibil numai în cazul în care determinantul, numit iacobian, ale cărui elemente au forma:

nu este egal cu zero (a se vedea teorema corespunzătoare din cursul MA)

După cum puteți vedea, funcțiile trebuie să fie funcții diferențiabile continue, iar în al doilea rând, elementele determinantului trebuie calculate în punctul staționar al funcției obiectiv.

Înlocuind din (3) în funcția obiectiv (1), avem:

Funcția investigată pentru extremum poate fi produsă prin metoda Euler - metoda de optimizare neconstrânsă a unei funcții diferențiabile continuu.

Deci, metoda eliminării (substituirii) permite utilizarea problemei optimizării condiționale clasice pentru a se transforma într-o problemă de optimizare necondiționată a unei funcții - o funcție de variabile în condiția (4), ceea ce face posibilă obținerea unui sistem de expresii ( 3).

Dezavantajul metodei de eliminare: dificultăți, iar uneori imposibilitatea obținerii unui sistem de expresii (3). Liber de acest dezavantaj, dar care necesită îndeplinirea condiției (4), este MLM.

5.2. Metoda multiplicatorului Lagrange. Condiții necesare în problema clasică a optimizării condiționate. Funcția Lagrange

MLM permite problema originală a optimizării condiționale clasice:

Transformați o funcție special concepută - funcția Lagrange într-o problemă de optimizare neconstrânsă:

unde, - multiplicatori Lagrange;

După cum puteți vedea, este o sumă formată din funcția obiectiv originală și suma „ponderată” a funcțiilor - funcții reprezentând constrângerile lor (2) ale problemei inițiale.

Fie punctul punctul extremului necondiționat al funcției, atunci, după cum se știe, sau (diferența totală a funcției în punct).

Utilizarea conceptului de variabile dependente și independente - variabile dependente; sunt variabile independente, atunci reprezentăm (5) în formă extinsă:

Din (2) este evident că urmează un sistem de ecuații de forma:

Rezultatul calculului diferenţialului total pentru fiecare dintre funcţii

Reprezentăm (6) în formă „extinsă”, folosind conceptul de variabile dependente și independente:

Rețineți că (6"), spre deosebire de (5"), este un sistem format din ecuații.

Să înmulțim fiecare --a ecuație a sistemului (6") cu --lea multiplicator Lagrange corespunzător. Adunăm-le împreună și cu ecuația (5") și obținem expresia:

Să ordonăm multiplicatorii Lagrange în așa fel încât expresia dintre paranteze drepte sub semnul primei sume (cu alte cuvinte, coeficienții la diferențele variabilelor independente,) să fie egală cu zero.

Termenul „elimină” multiplicatorii Lagrange în modul de mai sus înseamnă că este necesar să se rezolve un anumit sistem de ecuații cu privire la.

Structura unui astfel de sistem de ecuații poate fi obținută cu ușurință prin echivalarea expresiei dintre paranteze drepte sub semnul primei sume la zero:

Rescriem (8) ca

Sistemul (8") este un sistem de ecuații liniare față de cele cunoscute:. Sistemul este rezolvabil dacă (de aceea, ca și în metoda eliminării în cazul în cauză, condiția trebuie îndeplinită). (9). )

Deoarece în expresia cheie (7) prima sumă este egală cu zero, este ușor de înțeles că și a doua sumă va fi egală cu zero, i.e. următorul sistem de ecuații este valabil:

Sistemul de ecuații (8) este format din ecuații, iar sistemul de ecuații (10) este format din ecuații; a tuturor ecuațiilor din două sisteme și a necunoscutelor

Ecuațiile lipsă sunt date de sistemul de ecuații de constrângeri (2):

Deci, există un sistem de ecuații pentru găsirea necunoscutelor:

Rezultatul obţinut este că sistemul de ecuaţii (11) constituie conţinutul principal al MLM.

Este ușor de înțeles că sistemul de ecuații (11) poate fi obținut foarte simplu prin introducerea în considerare a unei funcții Lagrange special construite (3).

Într-adevăr

Deci, sistemul de ecuații (11) poate fi reprezentat sub forma (folosind (12), (13)):

Sistemul de ecuații (14) reprezintă o condiție necesară în problema clasică a optimizării condiționate.

Soluția rezultată a acestui sistem, valoarea vectorului se numește punct condiționat staționar.

Pentru a afla natura punctului staționar condiționat, este necesar să se utilizeze condiții suficiente.

5.3 Condiții suficiente în problema clasică a optimizării condiționate. algoritm MML

Aceste condiții fac posibilă aflarea dacă un punct condiționat staționar este un punct al unui minim condiționat local sau un punct al unui maxim condiționat local.

Relativ simplu, așa cum s-au obținut condiții suficiente în problemă pentru un extremum necondiționat. Condiții suficiente pot fi obținute și în problema clasică de optimizare condiționată.

Rezultatul acestui studiu:

unde este punctul minimului condițional local.

unde este punctul maximului condițional local, este matricea hessiană cu elemente

Matricea Hesse are dimensiuni.

Dimensiunea matricei Hesse poate fi redusă folosind condiția de inegalitate la zero a jacobianului:. În această condiție, variabilele dependente pot fi exprimate în termeni de variabile independente, atunci matricea Hessiană va avea dimensiuni, i.e. este necesar să vorbim despre o matrice cu elemente

atunci condițiile suficiente vor fi următoarele:

Punctul minimului condiționat local.

Punctul maximului condițional local.

Dovada: Algoritm MML:

1) alcătuiți funcția Lagrange:;

2) folosind condițiile necesare, formăm un sistem de ecuații:

3) găsiți un punct din soluția acestui sistem;

4) folosind condiții suficiente, determinăm dacă punctul este un punct al unui minim sau maxim condiționat local, apoi găsim

1.5.4. O metodă grafo-analitică pentru rezolvarea problemei clasice de optimizare condiționată în spațiu și modificările acesteia la rezolvarea celor mai simple probleme de IP și AP

Această metodă utilizează o interpretare geometrică a problemei clasice de optimizare constrânsă și se bazează pe o serie de fapte importante inerente acestei probleme.

B este tangenta comună pentru funcția și funcția care reprezintă ODR.

După cum puteți vedea din figură, un punct este un punct al unui minim necondiționat, un punct este un punct al unui minim local condiționat, un punct este un punct al unui maxim local condiționat.

Să demonstrăm că în punctele extremelor locale condiționale curba și liniile de nivel corespunzătoare

Se știe din cursul MA că în punctul de tangență condiția

unde este panta tangentei trasată de linia de nivel corespunzătoare; este panta tangentei la funcție

Expresia (MA) pentru acești coeficienți este cunoscută:

Să demonstrăm că acești coeficienți sunt egali.

pentru că condițiile necesare „vorbesc” despre asta

Cele de mai sus ne permit să formulăm algoritmul HFA pentru metoda de rezolvare a problemei clasice de optimizare constrânsă:

1) construim o familie de linii ale nivelului funcției obiectiv:

2) construim un ODR folosind ecuația constrângerii

3) pentru a corecta cresterea functiei, gasim si clarificam natura punctelor extreme;

4) investighăm interacțiunea dreptelor de nivel și funcția, în timp ce găsim din sistemul de ecuații coordonatele punctelor staționare condiționat - minime condiționate locale și maxime condiționale locale.

5) calculează

Trebuie remarcat în mod special că etapele principale ale metodei HFA pentru rezolvarea problemei clasice de optimizare constrânsă coincid cu etapele principale ale metodei HFA pentru rezolvarea problemelor NP și LP, singura diferență este în ODR, precum și în găsirea localizarea punctelor extreme în ODR (de exemplu, în problemele LP, aceste puncte se găsesc în mod necesar la vârfurile poligonului convex care reprezintă ODR).

5.5. Despre sensul practic al MML

Să reprezentăm problema clasică a optimizării condiționate sub forma:

unde sunt cantităţi variabile reprezentând resurse variabile în probleme tehnice şi economice aplicate.

În spațiu, problema (1), (2) ia forma:

unde este o variabilă. (2")

Fie punctul extremului condiționat:

Când se schimbă, se schimbă

Valoarea funcției obiectiv se va modifica în consecință:

Să calculăm derivata:

De la (3), (4), (5). (6)

Înlocuiți (5 ") în (3) și obțineți:

Din (6) că multiplicatorul Lagrange caracterizează valoarea „reacției” (ortogonală cu valoarea funcției obiectiv) la modificările parametrului.

În general, (6) ia forma:

Din (6), (7), că factorul caracterizează schimbarea atunci când resursa -a corespunzătoare se modifică cu 1.

Dacă este profitul maxim sau costul minim, atunci, caracterizează modificările acestei valori la modificare, cu 1.

5.6. Problema clasică de optimizare constrânsă ca problema găsirii punctului de șa al funcției Lagrange:

O pereche se numește punct de șa dacă inegalitatea este valabilă.

Evident, de la (1). (2)

Din (2) că. (3)

După cum puteți vedea, sistemul (3) conține ecuații similare acelor ecuații care reprezintă condiția necesară în problema clasică a optimizării condiționate:

unde este funcția Lagrange.

În legătură cu analogia sistemelor de ecuații (3) și (4), problema clasică a optimizării condiționate poate fi considerată ca fiind problema găsirii punctului de șa al funcției Lagrange.

Documente similare

    Probleme de optimizare multidimensională în studiul proceselor tehnologice din industria textilă, analiza dificultăților emergente. Găsirea unui extremum, cum ar fi un extremum, valoarea funcției obiective a optimizării multidimensionale neconstrânse.

    test, adaugat 26.11.2011

    Caracterizarea metodelor clasice de optimizare neconstrânsă. Determinarea unei condiții necesare și suficiente pentru existența unui extremum de funcții a uneia și mai multor variabile. Regula multiplicatorului Lagrange. Condiții necesare și suficiente pentru optimitate.

    lucrare de termen adăugată la 13.10.2013

    Metode și caracteristici de rezolvare a problemelor de optimizare, în special, privind distribuția investițiilor și alegerea unei căi în rețeaua de transport. Specificul modelării folosind metodele Hamming și Brown. Identificarea, stimularea și motivarea ca funcții de management.

    test, adaugat 12.12.2009

    Enunț, analiză, rezolvare grafică a problemelor de optimizare liniară, metoda simplex, dualitate în optimizarea liniară. Formularea problemei transportului, proprietăți și găsirea unei soluții de referință. Optimizare condiționată sub constrângeri de egalitate.

    manual, adăugat la 07.11.2010

    Calea critică în grafic. Distributie optima a fluxului in reteaua de transport. Problemă de programare liniară rezolvată grafic. Provocare de transport dezechilibrată. Metode numerice de rezolvare a problemelor unidimensionale de optimizare statică.

    lucrare de termen, adăugată 21.06.2014

    O metodă grafică pentru rezolvarea problemei de optimizare a proceselor de producție. Aplicarea unui algoritm simplex pentru a rezolva o problemă de control al producției optimizată din punct de vedere economic. Metodă de programare dinamică pentru alegerea profilului optim al piesei.

    test, adaugat 15.10.2010

    Metode de optimizare pentru rezolvarea problemelor economice. Formularea clasică a problemei de optimizare. Optimizarea functiilor. Optimizarea functionalelor. Optimizare multi-criterii. Metode pentru reducerea unei probleme cu mai multe criterii la o problemă cu un singur criteriu. Metoda concesiunilor.

    rezumat, adăugat 20.06.2005

    Aplicarea metodelor de programare neliniară pentru rezolvarea problemelor cu funcții neliniare ale variabilelor. Condiții de optimitate (teorema Kuhn-Tucker). Metode de optimizare condiționată (metoda Wolfe); design gradient; funcții de pedeapsă și barieră.

    rezumat, adăugat 25.10.2009

    Concept, definire, evidențiere a trăsăturilor, posibilităților și caracteristicilor problemelor existente de optimizare multicriterială și modalități de rezolvare a acestora. Calculul metodei de abatere egală și minimă a optimizării multicriteriale și aplicarea acesteia în practică.

    lucrare de termen adăugată 21.01.2012

    Concepte de bază ale modelării. Concepte generale și definiție a modelului. Enunțul problemelor de optimizare. Metode de programare liniară. Sarcină generală și tipică în programarea liniară. Metoda simplex pentru rezolvarea problemelor de programare liniară.

Obiectivul 1. Găsi

Problema 1 se reduce la rezolvarea sistemului de ecuații:

și studiul valorii celei de-a doua diferențe:

în punctele de rezolvare a ecuaţiilor (8.3).

Dacă forma pătratică (8.4) este definită negativ într-un punct, atunci aceasta atinge valoarea maximă, iar dacă este definită pozitiv, atunci valoarea minimă.

Exemplu:

Sistemul de ecuații are soluții:

Punctul (- 1 / 3.0) este punctul maxim, iar punctul (1 / 3.2) este punctul minim.

Obiectivul 2. Găsi

in conditii:

Problema 2 este rezolvată prin metoda multiplicatorului Lagrange. Pentru aceasta, se găsește o soluție de sistem (m + n) ecuatii:

Exemplu. Aflați laturile unui dreptunghi de arie maximă înscris într-un cerc:. Aria A a unui dreptunghi poate fi scrisă astfel: A = 4hu, atunci

Obiectivul 3. Găsi:

in conditii:

Această sarcină acoperă o gamă largă de sarcini definite de funcții fși .

Dacă sunt liniare, atunci problema este o problemă de programare liniară.

Sarcină3 A.

in conditii

Se rezolvă prin metoda simplex, care, folosind aparatul algebrei liniare, realizează o enumerare intenționată a vârfurilor poliedrului definit de (8.13).

Metoda simplex (constă din două etape):

Etapa 1. Găsirea soluției suport x (0).

Soluția suport este unul dintre punctele politopului (8.13).

Etapa 2. Găsirea soluției optime.

Soluția optimă se găsește prin enumerarea secvențială a vârfurilor politopului (8.13), în care valoarea funcției obiectiv z nu scade la fiecare pas, adică:

Un caz special al unei probleme de programare liniară este așa-numita problemă de transport.

Problema transportului. Să fie depozite în puncte, în care mărfurile sunt depozitate în cantități, respectiv. În puncte sunt consumatorii care trebuie să furnizeze aceste bunuri în cantități, respectiv. Notăm c ij costul transportului unei unități de marfă între puncte

Să investigăm funcționarea transportului de către consumatori a mărfurilor în cantități suficiente pentru a satisface nevoile consumatorilor. Să notăm după cantitatea de mărfuri transportată din punct A i la punctul b j .

Pentru a satisface nevoile consumatorului este necesar ca valorile NS ij satisface conditiile:

Totodata dintr-un depozit; nu poți scoate produse în cantități mai mari decât există. Aceasta înseamnă că valorile căutate trebuie să satisfacă sistemul de inegalități:

Există nenumărate modalități de a satisface condițiile (8.14), (8.15), adică de a întocmi un plan de transport care să răspundă nevoilor consumatorilor. Pentru ca cercetătorul operațional să poată alege o soluție anume, adică să atribuie anumite NS ij, ar trebui formulată o anumită regulă de selecție, determinată folosind un criteriu care reflectă ideea noastră subiectivă a scopului.

Problema criteriului se rezolvă independent de studiul operației - criteriul trebuie specificat de partea operațională. În această problemă, unul dintre criteriile posibile va fi costul transportului. Este definită după cum urmează:

Apoi problema transportului este formulată ca o problemă de programare liniară: se determină mărimile care satisfac constrângerile (8.14), (8.15) și asigură funcția (8.16) o valoare minimă. Constrângerea (8.15) este o condiție de echilibru; condiția (8.14) poate fi numită scopul operațiunii, deoarece sensul operațiunii este de a asigura nevoile consumatorilor.

Aceste două condiţii constituie în esenţă modelul operaţiei. Implementarea operațiunii va depinde de criteriul prin care se va atinge scopul operațiunii. Criteriul poate apărea în diferite roluri. Poate acționa atât ca modalitate de formalizare a scopului, cât și ca principiu de alegere a acțiunilor dintre cele admisibile, adică satisfacerea restricțiilor.

Una dintre metodele cunoscute de rezolvare a problemei transportului este metoda potențială.

În prima etapă de rezolvare a problemei se întocmește un plan inițial de transport care să satisfacă

restricții (8.14), (8.15). Dacă (adică cerințele totale nu coincid cu stocurile totale de produse din depozite), atunci se introduce un punct de consum fictiv sau un depozit fictiv cu costuri de transport egale cu zero. Pentru o nouă sarcină, numărul total de mărfuri din depozite coincide cu cererea lor totală. Apoi, o metodă (de exemplu, cel mai mic element sau colțul de nord-vest) este planul original. La pasul următor din procedura planului rezultat, se construiește un sistem de caracteristici speciale - potențiale. O condiție necesară și suficientă pentru un plan optim este potențialul acestuia. Procedura de rafinare a planului se realizează până când acesta devine potențial (optim).

Problema 3b.În cazul general, problema (8.10 - 8.11) se numește problemă de programare neliniară. Să o considerăm într-o formă mai acceptată:

in conditii

Pentru a rezolva această problemă se folosesc așa-numitele metode de relaxare. Procesul de construire a unei secvențe de puncte se numește relaxare dacă:

Metode de coborâre (schemă generală)... Toate metodele de coborâre pentru rezolvarea problemei de optimizare neconstrânsă (8.17) diferă fie în alegerea direcției de coborâre, fie în modul de deplasare pe direcția de coborâre. Metodele de coborâre constau în următoarea procedură de construire a secvenței { X k }.

Un punct arbitrar este ales ca o aproximare inițială X 0 . Aproximațiile succesive sunt construite după următoarea schemă:

Punct X k este selectată direcția de coborâre - s k ;

Găsiți (k + 1) - aproximarea cu formula:

unde ca valoare se alege orice număr care satisface inegalitatea

unde număr este orice astfel de număr când

În majoritatea metodelor de coborâre, valoarea lui  k este aleasă să fie egală cu unu. Astfel, pentru a determina k, trebuie rezolvată problema minimizării unidimensionale.

Metoda de coborâre în gradient. Deoarece antigradientul - indică direcția celei mai abrupte scăderi a funcției f(X), atunci este firesc să trecem de la punct NS k in aceasta directie. Metoda de coborâre, care se numește metoda de coborâre în gradient. Dacă, atunci procesul de relaxare se numește cea mai abruptă metodă de coborâre.

Metoda direcțiilor conjugate.În algebra liniară, această metodă este cunoscută ca metoda gradientului conjugat pentru rezolvarea sistemelor de ecuații algebrice liniare AX =b, și prin urmare, ca metodă de minimizare a funcției pătratice

Diagrama metodei:

Dacă = 0, atunci această schemă se transformă într-o schemă de coborâre cea mai abruptă. Alegerea adecvată a valorii t k garantează convergența metodei direcției conjugate la o rată de același ordin de mărime ca în metodele de coborâre în gradient și asigură că numărul de iterații în coborârea pătratică este finit (de exemplu).

Coordonarea coborârii. La fiecare iterație, ca direcție de coborâre - s k este selectată o direcție de-a lungul uneia dintre axele de coordonate. Metoda are o rată de convergență a procesului de minimizare de ordinul 0 (1/m). Mai mult, depinde esential de dimensiunea spatiului.

Diagrama metodei:

unde vectorul de coordonate

Dacă la punct X k există informații despre comportamentul gradientului funcției f(X), de exemplu:

apoi ca direcţie de coborâre s k putem lua vectorul de coordonate e j . În acest caz, rata de convergență a metodei este de n ori mai mică decât în ​​cazul coborârii gradientului.

În etapa inițială a procesului de minimizare, poate fi utilizată metoda coborârii ciclice în coordonate, atunci când mai întâi coborârea este efectuată în direcția e 1 , apoi pe e 2 etc pana la e NS , după care se repetă din nou întregul ciclu. Mai promițătoare în comparație cu precedenta este coborârea coordonate, în care direcțiile de coborâre sunt alese aleatoriu. Cu această abordare a alegerii direcției, există estimări a priori care garantează funcția f(X) cu probabilitatea tinde spre unitate la, convergența procesului cu o rată de ordinul 0 (1 / m).

Diagrama metodei:

La fiecare pas al procesului, din n numere (1, 2, ..., n), un număr este selectat aleatoriu j(k) si ca s k, vectorul de coordonate unitar e j ( k ) , după care se efectuează coborârea:

Metoda de coborâre aleatorie.s k supus unei distribuții uniforme pe această sferă și apoi în funcție de elementul calculat la a k-a etapă a procesului NS La este determinat de:

Rata de convergență a metodei de coborâre aleatorie este de n ori mai mică decât cea a metodei de coborâre în gradient, dar de n ori mai mare decât cea a metodei de coborâre aleatorie în coordonate. Metodele de coborâre luate în considerare sunt aplicabile funcțiilor convexe opționale și garantează convergența acestora sub constrângeri foarte mici asupra acestora (cum ar fi absența minimelor locale).

Metode de relaxare a programării matematice. Să revenim la problema 36 ((8.17) - (8.18)):

in conditii

În problemele de optimizare cu constrângeri, alegerea direcției de coborâre este asociată cu necesitatea de a verifica constant dacă noua valoare NS k +1 ar trebui la fel ca și precedentul X k satisface un sistem de constrângeri X.

Metoda gradientului condiționat.În această metodă, ideea de a alege direcția de coborâre este următoarea: la punct NS La liniază funcția f(X), construirea unei funcții liniare și apoi minimalizarea f(X) pe platou NS, găsi un punct y k . După aceea, se presupune, iar mai departe pe această direcție, se efectuează coborârea, astfel încât

Astfel, pentru a găsi direcția - s k, ar trebui să se rezolve problema minimizării unei funcții liniare pe mulțime X. Dacă X la rândul său este dată de constrângeri liniare, apoi devine o problemă de programare liniară.

Metoda posibilelor direcții. Ideea metodei: printre toate direcțiile posibile la un punct NS La alegeți cel de-a lungul căruia funcția f(X) scade cel mai rapid și apoi coboară pe această direcție.

Direcție - s la punct NSX este numit posibil dacă există un astfel de număr încât pentru toți. Pentru a găsi o posibilă direcție, este necesar să se rezolve o problemă de programare liniară sau cea mai simplă problemă de programare pătratică:

In conditii:

Să fie soluția la această problemă. Condiția (8.25) garantează că direcția este posibilă. Condiția (8.26) asigură valoarea maximă a lui (, adică între toate direcțiile posibile - s, direcție - oferă cea mai rapidă decădere a funcției f(X). Condiția (8.27) elimină caracterul nelimitat al soluției problemei. Metoda direcțiilor posibile este rezistentă la posibile erori de calcul. Cu toate acestea, este dificil de estimat rata de convergență a acesteia în cazul general, iar această problemă rămâne încă nerezolvată.

Metoda de căutare aleatorie.În cazul general, implementarea metodelor de minimizare de mai sus este foarte laborioasă, cu excepția celor mai simple cazuri când setul de constrângeri are o structură geometrică simplă (de exemplu, este un paralelipiped multidimensional). În cazul general, metoda de căutare aleatorie, când direcția de coborâre este aleasă la întâmplare, poate fi foarte promițătoare. În acest caz, vom pierde semnificativ în rata de convergență, totuși, simplitatea alegerii direcției poate compensa aceste pierderi în ceea ce privește costurile totale cu forța de muncă pentru rezolvarea problemei de minimizare.

Diagrama metodei:

Un punct aleatoriu este selectat pe sfera unitară n-dimensională centrată la origine r k, supus unei distribuții uniforme pe această sferă, iar apoi direcția de coborâre este s k din conditii

Este aleasă ca aproximare inițială. Pentru punctul calculat la fiecare iterație X k în construcție ( k+ 1) al-lea punct X k +1 :

Ca calitate, este selectat orice număr din = care satisface inegalitatea:

Convergența acestei metode este dovedită sub restricții foarte libere asupra funcției f (convexitate) și multe restricții X (convexitate și închidere).