PROGRAMARE NELINIARĂ: METODE ȘI EXERCIȚII - MATEMATICA - 2025

Programarea neliniară este procesul de optimizare a unei funcții care depinde de mai multe variabile independente, care , la rândul lor , sunt supuse unor restricții.

Dacă una sau mai multe dintre restricții sau dacă funcția trebuie maximizată sau minimizată (numită funcție obiectivă), nu este exprimată ca o combinație liniară a variabilelor, atunci aveți o problemă de programare neliniară.

Figura 1. Problema de programare neliniară (NLP). unde G este funcția (neliniară) de optimizare în regiunea verde, determinată de constrângeri. Sursa: F. Zapata.

Prin urmare, procedurile și metodele de programare liniară nu pot fi utilizate.

De exemplu, binecunoscuta metodă Simplex nu poate fi utilizată, care se aplică numai atunci când funcția obiectivă și constrângerile sunt toate combinații liniare ale variabilelor din problemă.

Metode de programare liniară

Pentru problemele de programare neliniare, principalele metode care trebuie utilizate sunt:

1.- Metode grafice.

2.- Multiplicatori Lagrange pentru a explora limita regiunii soluției.

3.- Calculul gradientului de a explora extremele funcției obiective.

4.- Metoda de coborâre a pașilor, pentru a găsi punctele de gradient nul.

5.- Metoda modificată a multiplicatorilor Lagrange (cu condiția Karush-Kuhn-Tucker).

Exemplu de soluție cu metodă grafică

Un exemplu de soluție cu metoda grafică este cel care poate fi văzut în figura 2:

Figura 2. Exemplu de problemă neliniară cu restricții neliniare și soluția sa grafică. Sursa: F. Zapata.

Exerciții

- Exercițiul 1 (Metoda grafică)

Profitul G al unei anumite companii depinde de cantitatea vândută a produsului X și de cantitatea vândută a produsului Y, în plus, profitul este determinat după următoarea formulă:

G = 2 (X - 2) ² + 3 (Y - 3) ²

Sumele X și Y sunt cunoscute ca având următoarele restricții:

X≥0; Y≥0 și X + Y ≤ 7

Determinați valorile X și Y care produc câștigul maxim.

Figura 3. Profitul unei companii poate fi modelat matematic pentru a găsi profitul maxim utilizând o programare neliniară. Sursa: Pixabay.

Soluţie

În această problemă funcția obiectivă este neliniară, în timp ce inegalitățile care definesc constrângerile sunt. Aceasta este o problemă de programare neliniară.

Pentru soluția acestei probleme se va alege metoda grafică.

În primul rând, se va determina regiunea soluției, care este dată de restricții.

Ca X≥0; Y≥0, soluția trebuie să fie găsită în primul cadran al planului XY, dar din moment ce trebuie să fie adevărat și că X + Y ≤ 7, soluția se află în jumătatea inferioară a planului liniei X + Y = 7.

Regiunea soluției este intersecția primului cadran cu jumătatea inferioară a planului liniei, ceea ce duce la o regiune triunghiulară în care se găsește soluția. Este identică cu cea indicată în figura 1.

Pe de altă parte, câștigul G poate fi reprezentat și în planul cartezian, deoarece ecuația sa este aceea a unei elipse cu centru (2,3).

Elipsa este prezentată în figura 1 pentru diferite valori ale lui G. Cu cât este mai mare valoarea lui G, cu atât este mai mare câștigul.

Există soluții care aparțin regiunii, dar nu dau valoarea maximă G, în timp ce altele, precum G = 92,4, se află în afara zonei verzi, adică a zonei de soluție.

Apoi, valoarea maximă a lui G, astfel încât X și Y aparțin regiunii soluției corespunde:

G = 77 (câștig maxim), care este dat pentru X = 7 și Y = 0.

Interesant este că profitul maxim apare atunci când cantitatea de vânzări a produsului Y este zero, în timp ce cantitatea de produs X atinge cea mai mare valoare posibilă.

- Exercițiul 2 (Metoda analitică: multiplicatori Lagrange)

Găsiți soluția (x, y) care face ca funcția f (x, y) = x ² + 2y ^{2 să fie} maximă în regiunea g (x, y) = x ² + y ² - 1 = 0.

Soluţie

Este clar o problemă de programare neliniară, deoarece atât funcția obiectivă f (x, y) cât și restricția g (x, y) = 0, nu sunt o combinație liniară a variabilelor x și y.

Se va folosi metoda multiplicatorilor Lagrange, care necesită mai întâi definirea funcției Lagrange L (x, y, λ):

L (x, y, λ) = f (x, y) - λ g (x, y) = x ² + 2y ² - λ (x ² + y ² - 1)

Unde λ este un parametru numit multiplicator Lagrange.

Pentru a determina valorile extreme ale funcției obiective f, în regiunea soluției dată de restricția g (x, y) = 0, urmați acești pași:

-Caută derivatele parțiale ale funcției Lagrange L, în raport cu x, y, λ.

-Evaluați fiecare derivat la zero.

Aici secvența acestor operații:

1. ∂L / ∂x = 2x - 2λx = 0
2. ∂L / ∂y = 4y - 2λy = 0
3. ∂L / ∂λ = - (x ² + y ² - 1) = 0

Soluții posibile de sistem

O posibilă soluție a acestui sistem este λ = 1 astfel încât prima ecuație să fie satisfăcută, caz în care y = 0 astfel încât a doua să fie satisfăcută.

Această soluție presupune că x = 1 sau x = -1 pentru a treia ecuație să fie satisfăcută. În acest fel, au fost obținute două soluții S1 și S2:

S1: (x = 1, y = 0)

S2: (x = -1, y = 0).

Cealaltă alternativă este aceea că λ = 2 astfel încât a doua ecuație să fie satisfăcută, indiferent de valoarea y.

În acest caz, singura cale pentru a fi satisfăcută prima ecuație este pentru x = 0. Având în vedere a treia ecuație, există doar două soluții posibile, pe care le vom numi S3 și S4:

S3: (x = 0, y = 1)

S4: (x = 0, y = -1)

Pentru a afla care sau care dintre aceste soluții maximizează funcția obiectivă, procedăm la înlocuirea cu f (x, y):

S1: f (1, 0) = 1 ² + 2,0 ² = 1

S2: f (-1, 0) = (-1) ² + 2,0 ² = 1

S3: f (0, 1) = 0 ² + 2.1 ² = 2

S4: f (0, -1) = 0 ² + 2 (-1) ² = 2

Concluzionăm că soluțiile care maximizează f, când x și y aparțin circumferinței g (x, y) = 0 sunt S3 și S4.

Perechile de valori (x = 0, y = 1) și (x = 0, y = -1) maximizează f (x, y) în regiunea soluției g (x, y) = 0.

- Exercițiul 3 (gradient nul)

Găsiți soluții (x, y) pentru funcția obiectivă:

f (x, y) = x ² + 2 y ²

Fie maxim în regiunea g (x, y) = x ² + y ² - 1 ≤ 0.

Soluţie

Acest exercițiu este similar cu exercițiul 2, dar regiunea soluție (sau restricție) se extinde la regiunea interioară a circumferinței g (x, y) = 0, adică la cercul g (x, y) ≤ 0. Aceasta include la circumferința și regiunea sa interioară.

Soluția la frontieră a fost deja determinată în exercițiul 2, dar regiunea interioară rămâne de explorat.

Pentru a face acest lucru, gradientul funcției f (x, y) trebuie calculat și setat egal cu zero, pentru a găsi valori extreme în regiunea soluției. Acest lucru este echivalent cu calculul derivatelor parțiale ale f în raport cu x și y respectiv și a-l seta egal cu zero:

∂f / ∂x = 2 x = 0

∂f / ∂y = 4 y = 0

Acest sistem de ecuații are singura soluție (x = 0, y = 0) care aparține cercului g (x, y) ≤ 0.

Înlocuirea acestei valori în funcția f rezultă:

f (0, 0) = 0

În concluzie, valoarea maximă pe care o ia funcția în regiunea soluției este 2 și apare la limita regiunii soluției, pentru valorile (x = 0, y = 1) și (x = 0, y = -1) .

Referințe

1. Avriel, M. 2003. Programare neliniară. Editura Dover.
2. Bazaraa. 1979. Programare neliniară. John Wiley & Sons.
3. Bertsekas, D. 1999. Programare neliniară: ediția a II-a. Athena Științific.
4. Nocedal, J. 1999. Optimizare numerică. Springer-Verlag.
5. Wikipedia. Programare neliniară. Recuperat din: es.wikipedia.com