Metode de optimizare neconstrânse. Metode de optimizare necondiționată și condiționată. Lista metodelor de optimizare fără restricții

din setul total de opțiuni, puteți construi o histogramă, puteți evalua cât de des sunt găsite opțiuni bune și, în sfârșit, puteți lua o decizie - să continuați căutarea sau să vă limitați la soluția găsită.

În ciuda versatilității și simplității procedurii de sondare aleatorie, aceasta nu poate fi limitată din cauza complexității computaționale semnificative. Prin urmare, metodele căutare țintită solutii.

4.5.3. Tehnici de optimizare neconstrânse

Condițiile necesare pentru atingerea unui extrem în toate formele considerate mai sus duc la rezolvarea unui sistem de ecuații neliniare - o problemă foarte complexă și laborioasă (chiar și în matematica computațională, soluția ecuațiilor neliniare se reduce adesea la o anumită problemă 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 cele ce urmează, aici vom vorbi despre minimizare, deci un extremum este un 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 multi-extremale. și așa mai departe. Aceeași metodă, care este eficientă pentru rezolvarea problemelor de un tip, se poate dovedi a 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. Mai multe informații pot fi obținute la

exemplu, c.

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 neconstrânsă 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 X, cu toate acestea, ei tind 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 din punct NS;

– determinarea pasului pe 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.

Metodele de descendență sunt descrise matematic 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 - lungimea pasului.

Diferitele metode de coborâre diferă unele de altele prin modul în care aleg 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 punctul minim sau pentru a ajunge suficient de aproape de acesta. Calitatea metodelor iterative convergente este estimată prin rata de convergență.

Teoretic, metodele de descendență rezolvă problema într-un număr infinit de iterații. În practică, calculele sunt încheiate atunci când sunt îndeplinite anumite criterii (condiții) pentru oprirea procesului iterativ. De exemplu, poate fi condiția pentru micimea

	argument		X [k] - X [k - 1]

f (X [k]) - f (X [k - 1])< γ . Здесь k – номер итерации; ε , γ – задан-

valorile acurateței soluționării problemei.

Metodele pentru găsirea punctului minim sunt numite deterministe dacă ambii parametri ai tranziției de la X la X (direcția mișcării și dimensiunea pasului) sunt selectați în mod unic din informațiile disponibile la punctul X. Dacă se folosește vreun mecanism aleatoriu în timpul tranziției, atunci algoritmul de căutare se numește căutare aleatorie pentru minimum.

Algoritmii determiniști pentru minimizarea neconstrânsă 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 calculul primelor derivate ale funcției de minimizat, atunci există metode de ordinul întâi,

dacă este necesar să se calculeze suplimentar derivatele secunde - metode de ordinul doi.

Trebuie remarcat faptul că, la rezolvarea problemelor de minimizare neconstrânsă, metodele de ordinul întâi și al doilea au, de regulă, o rată de convergență mai mare decât metodele de ordin zero. Cu toate acestea, în practică, calcularea primei și a doua derivate ale unei funcții a unui număr mare de variabile este foarte laborioasă. În unele cazuri, acestea nu pot fi obținute sub formă de funcții analitice. Derivatele sunt determinate prin diverse metode numerice cu erori care pot limita aplicarea 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, cele mai detaliate aici sunt metodele de ordinul zero.

Metode de căutare unidimensionale. Lista metodelor de căutare unidimensională - căutare numerică pentru extremul unei funcții a unui argument f (x ) Este suficient de larg și bine acoperit în literatură. Prin urmare, aici ne vom limita la a lua î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 succesiv intervalul de incertitudine - intervalul de valori ale argumentului x care conține punctul minim necesar - la o lungime care să nu depășească

eroare admisibilă a rezultatului ε. Ca interval inițial, intervalul admisibil de valori ale argumentului specificat de condițiile problemei sau, în cazul în care acesta din urmă nu are granițe stânga și (sau) dreaptă, o regiune în cadrul admisibilului, la care minimul necesar. este indicată prin analiză preliminară.

Orice interval conține două puncte x = y 0 și x = z 0, care își îndeplinesc „rația de aur” - o împărțire în două părți inegale, astfel încât raportul dintre cea mai mare parte și lungimea întregului interval să coincidă cu raportul dintre partea mai mică spre cea mai mare. Evident, aceste puncte sunt situate simetric în jurul centrului 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 urmare, obținem cotele relative care determină „secțiunea de aur” a intervalului: δ = 0,618, 1 – δ = 0,382. „Secțiunea de aur” are o 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. Acest lucru se va asigura

un calcul simplu așteaptă: 0,382 / 0,618 = 0,618 și (0,618–0,382) / 0,618 = = 0,382.

Algoritmul de găsire a minimului, construit pe baza metodei „secțiunii de aur”, prevede la fiecare iterație alegerea ca una dintre limitele intervalului redus al punctului din stânga sau din dreapta „secțiunii de aur”, astfel încât minim necesar rămâne în interiorul acestuia:

1. Setați k = 0, intervalul inițial de incertitudine, eroarea admisibilă a rezultatului ε.

2. Calculați coordonatele punctelor „secțiunii de aur”:

y k = a k +0,382 (b k –a k), z k = 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, a), 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 obiective.

Metoda de căutare directă (metoda Hook-Jeeves). niste

al doilea punct de plecare X. Prin schimbarea alternativă a componentelor vectorului X se examinează vecinătatea acestui punct, în urma căruia se găsește un punct (nouă bază) care determină direcția în care funcția minimizată f (X) scade. Coborârea se efectuează în direcția selectată, 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 de coordonate inițiale

∆ X = (∆ x 1, ∆ x 2, ..., ∆ xn) în timpul sondajului cartierului, cea mai mică valoare admisă ε a componentelor ∆ 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 = X. calculati

valoarea f (X b).

3. Schimbați alternativ fiecare coordonată x b i, i = 1,2, ... n,

punctează X b cu valoarea ∆ x i, adică luăm x i = x b i + ∆ x i, atunci

x i = x b i –∆ x i. Calculați valorile f (X) la punctele eșantionului obținute și comparați-le cu valoarea f (X b). Dacă f (X)< < f (X б ), то соответствующая координата х i приобретает новое значение, вычисленное по одному из приведенных выражений. В противном случае значение этой координаты остается неизменным. Если после изменения последней n -й координаты f (X )

4. Efectuați coborârea în direcția de la baza „veche” la baza „nouă” prin ultima, adică calculați coordonatele noului punct

X: x i = x i + λ (x i –x bi), i = 1,2,… n. Calculați valoarea f (X). Dacă condiția f (X)

Baza „nouă” este considerată „veche” (X b = X, f (X b) = f (X)) și treceți la pasul 5. În caz contrar, x i = x i, i = 1,2, ... n ...

5. Ca la p. 3, schimbați alternativ fiecare coordonată a punctului X, comparând valorile 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ția f (X) cu valoarea f (X b) obținută în secțiunea 4. Dacă f (X)

6. Dacă pentru tot i ∆ x i<ε , вычисления прекращаются. В противном случае уменьшают значения ∆ х i в d раз и переходят к п. 3.

Funcționarea algoritmului este ilustrată în Fig. 27. Afișarea liniilor

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 așa 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âre), linie întreruptă - 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ță constrângerile asupra variabilelor individuale, precum și constrângerile complexe asupra domeniului de căutare.

Dezavantajul metodei de căutare directă este că, în cazul liniilor puternic alungite, curbe sau cu unghiuri ascuțite ale nivelului funcției obiectiv, este posibil să nu poată asigura progresul către 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 vârf. Evident, fiecare vârf îi corespunde unui vector Xi ... Calculați valorile funcției obiectiv 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 de proiecție, pe care se află punctul Xq cu o valoare a funcției obiectiv mai mică decât la vârf Xh (Fig. 28, a ). Apoi excludeți partea de sus Xh ... Din vârfurile și punctele rămase Xq se construiește un nou poliedru, cu care se repetă procedura descrisă. În procesul de efectuare a unor astfel de operații, poliedrul își schimbă dimensiunea, motiv pentru care metoda a fost numită.

Să introducem următoarea notație: X este vectorul de coordonate al vârfului i al poliedrului la pasul de căutare k, i = 1,2,… n +1, k = 1,2,…; h - numărul vârfului în care se află valoarea țintei

cauciucuri, cu excepția X. Coordonatele centrului de greutate al calculului

	xj [n + 2, k] =		n + 1
sunt calculate după formula			∑ xj [i, k] - xj [h, k]		J = 1,2, ... n.
			j = 1

Un algoritm aproximativ pentru metoda poliedrului deformabil este următorul:

1. Stabiliți prin coeficienți de reflexieα, tensiune γ> 1, compresie β<1 , допустимой погрешностью определения координат

puncte de minim ε. Sunt selectate coordonatele vârfurilor poliedrului original X, i = 1,2, ... n +1, k = 1.

2. Calculați valorile funcției obiectiv la toate vârfurile f (X), i = 1,2, ... n + 1 și găsiți punctele X, X (în Fig. 28, punctele b, respectiv, X 2 și X 1), precum și X.

3. Efectuați proiecția punctului X prin centrul

foaie: X = X + α (X –X).

4. Dacă f (X) ≤ X, efectuați operația de întindere.

niya: X = X + γ (X –X). În caz contrar, treceți la punctul 6.

5. Se construiește un nou poliedru: dacă f (X)

prin înlocuirea X cu X, în caz contrar, prin înlocuirea X cu X. Calculele sunt continuate de la punctul 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). Un nou politop este construit prin înlocuirea X cu X și calculele sunt continuate de la punctul 2 pentru k = k +1.

7. Dacă f (X)> X, atunci, păstrând vârful X, construiți un nou poliedru asemănător celui actual prin înjumătățirea lungimii tuturor muchiilor: X = X +0,5 (X –X) și continuați calculele de la item. 2 pentru k = k +1.

În pp. 6, 7, înainte de a trece la punctul 2, este necesar să se verifice dacă este îndeplinită condiția de finalizare a căutării minimului, de exemplu, conform condiției

vizualizare max n ∑ + 1 (x j [i, k] - x j [n + 2, k]) 2< ε 2 .

i j = 1

CU Folosind operația de întindere și comprimare, dimensiunile și forma poliedrului deformabil sunt adaptate la topografia funcției obiectiv. Ca urmare, poliedrul se întinde de-a lungul suprafețelor lungi înclinate, își schimbă direcția în văile curbe și se contractă în vecinătatea minimului, ceea ce determină eficacitatea metodei luate în considerare.

α = 1, 2≤ y ≤3, 0,4≤β ≤0,6.

Metoda coordonatelor rotative (metoda 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 – în direcții 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 lui un nou sistem de direcții de căutare

puncte minime X.

V Spre deosebire de alte metode de ordin zero, metoda lui Rosenbrock se concentrează pe găsirea punctului optim în fiecare direcție, nu doar a unei deplasări fixe î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 pasului face ca metoda lui Rosenbrock să fie eficientă în rezolvarea problemelor complexe de optimizare.

V Î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 puternic alungite), deoarece direcția de căutare rezultată tinde să fie situată de-a lungul axei „gârpă”.

Metoda tangentei paralele (metoda lui Powell). Esența sa constă în efectuarea secvenţială a unei căutări unidimensionale a minimului funcţiei obiectiv în raport cu n + 1 direcție din metodele unidimensionale binecunoscute. La prima iterație, ca prima n direcțiile sunt coordonate selectate, ca(n + 1) mie direcţii se foloseşte primul dintre ele (fig. 30). La fiecare iterație ulterioară, căutarea începe din a doua direcție a iterației precedente, respectiv numerele de direcție scad cu unu;(n + 1) mie 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.

Printre metodele de optimizare de ordin zero în CAD se folosesc metodele lui Rosenbrock, configurațiile, poliedrul deformabil și căutarea aleatorie. 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 alternativ de-a lungul tuturor axelor de coordonate, pasul se calculează 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 controlat. parametrii. Traiectoria de coborâre a coordonatelor 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 parametri controlați. Funcția obiectiv este reprezentată de propriile linii de nivel egal; valoarea corespunzătoare este scrisă lângă fiecare linie. Evident, există un punct minim.

Orez. 1. Traiectoria coborârii coordonate

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. În fig. 2, se poate observa că după lovirea unui punct situat în fundul râpei, pașii ulterioare sunt posibili doar în direcțiile sau, dar duc la o deteriorare a funcției obiectivului. Prin urmare, căutarea se oprește într-un punct.

Nota 1

O râpă este o parte a spațiului parametrilor controlați în care se observă modificări slabe ale derivatelor funcției obiectiv într-o direcție și modificări semnificative cu o schimbare a semnului în alte direcții. Semnul derivatului se modifică în punctele aparținând fundului râpei.

Orez. 3. Traiectoria coborârii coordonate cu o orientare favorabilă a axelor de coordonate

metoda lui 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. Acest viraj se efectuează pe baza datelor obținute după o serie de pași de coborâre în coordonate. Poziția noilor axe se poate obține prin transformarea liniară a vechilor axe: axa coincide în direcție cu vectorul; axele rămase sunt selectate din condiția de ortogonalitate 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 un punct.

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 explicate în Fig. 5 despre exemplul unei probleme de optimizare bidimensională. Se selectează vârfurile triunghiului original:,,. Noul vârf este situat pe raza trasă de la vârful cel mai prost (din vârful cu cea mai mare valoare a funcției obiectiv) prin centrul de greutate al poliedrului și se recomandă alegerea la o distanță 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ă, această situație are loc și creșterea dă un punct. Într-un poliedru nou cu vârfuri, cel mai rău este vârful, în mod similar, se obține un vârf, apoi un vârf etc. 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 marginilor ar trebui reduse, de exemplu, la jumătate (contracția poliedrului 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 ca optim folosind 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ă de zig-zag cu o mișcare lentă de-a lungul fundului râpei spre extrem. Mai multe tehnici sunt utilizate pentru a îmbunătăți eficiența metodelor de gradient.

Una dintre tehnicile folosite în metoda gradientului conjugat(numită și metoda Fletcher-Reeves), se bazează pe conceptul de conjugație vectorială. Vectorii și se numesc -conjugați 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 matricea de ordine unitară), 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ă secvențială de-a lungul direcțiilor conjugate permite găsirea punctului extrem în nu mai mult de pași.

Nota 2

Matricea Hessiană este matricea derivatelor a doua parțiale ale funcției obiectiv în raport cu parametrii controlați.

Motivul utilizării căutării în direcții -adiacente este că pentru funcțiile () de formă generală se poate aplica o aproximare pătratică, care în practică se traduce prin efectuarea unei căutări în mai mult decât pași.

Căutarea unui extremum se efectuează în conformitate cu formula

unde este coeficientul. În plus, ține cont de condiția de conjugație

Deoarece pasul este calculat pe baza condiției optimizării unidimensionale, 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 determinarea coeficientului, sistemul de ecuații (2) - (7) se rezolvă prin înlocuirea în (4) a valorilor din (3) și din (2):

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

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
Unde

De aceea

Se poate arăta că tinde spre, - la at, unde este dimensiunea spațiului parametrilor controlați. După pași, trebuie să începeți din nou cu.

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 de rezolvare a problemei de optimizare neconstrânsă.

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, adică. 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ă, în general, este imposibil să rezolvați acest sistem analitic; 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ă.

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				; ; ; ;
					; ;
					; ; ; ;
					; ; ; ;
					; ;