PROGRAMACIÓ NO LINEAL: MÈTODES I EXERCICIS - MATEMÀTIQUES - 2025

La programació no lineal és el procés d'optimitzar una funció que depèn de diverses variables independents, les quals al seu torn estan sotmeses a restriccions.

Si una o més de les restriccions, o si la funció a maximitzar o minimitzar (anomenada funció objectiu), no està expressada com una combinació lineal de les variables, llavors es té un problema de programació no lineal.

Figura 1. Problema de programació no lineal (PNL). en el qual G és la funció (no lineal) a optimitzar a la regió verd, determinada per les restriccions. Font: F. Zapata.

I per tant no poden emprar-se els procediments i mètodes de la programació lineal.

Per exemple, no pot usar-se el conegut mètode Simplex, el qual només s'aplica quan la funció objectiu i les restriccions són totes combinació lineal de les variables d'el problema.

Mètodes de programació lineal

Per als problemes de programació no-lineal els principals mètodes a ser usats són:

1.- Mètodes gràfics.

2.- Multiplicadors de Lagrange per explorar la frontera de la regió de solució.

3.- Càlcul de la gradient per explorar extrems de la funció objectiu.

4.- El mètode dels passos descendents, per trobar els punts de gradient nul.

5.- Mètode modificat dels multiplicadors de Lagrange (amb la condició de Karush-Kuhn-Tucker).

Exemple de solució amb mètode gràfic

Un exemple de solució amb el mètode gràfic és el que pot apreciar-se en la figura 2:

Figura 2. Exemple de problema no-lineal amb restriccions no-lineals i la seva solució gràfica. Font: F. Zapata.

exercicis

- Exercici 1 (Mètode gràfic)

El guany G de certa empresa depèn de la suma venut del producte X i la suma venut del producte I, a més el guany es determina per la següent fórmula:

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

Se sap que les sumes X i Y tenen les següents restriccions:

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

Determineu els valors de X i Y que produeixen la màxima guany.

Figura 3. El guany d'una empresa pot modelar matemàticament per trobar el guany màxim mitjançant programació no lineal. Font: Pixabay.

solució

En aquest problema la funció objectiu és no lineal, mentre que les desigualtats que defineixen les restriccions sí que ho són. Es tracta d'un problema de programació no lineal.

Per a la solució d'aquest problema s'optarà pel mètode gràfic.

En primer lloc s'ha de determinar la regió de solució, la qual està donada per les restriccions.

Com X≥0; Y≥0, la solució s'ha de buscar en el primer quadrant de el pla XY, però com addicionalment s'ha de complir que X + I ≤ 7, la solució està en el semiplà inferior de la recta X + I = 7.

La regió de solució és la intersecció del primer quadrant amb el semiplà inferior de la recta, el que dóna lloc a una regió triangular on es troba la solució. És la mateixa que s'indica a la figura 1.

D'altra banda, el guany G també pot representar-se al pla cartesià, ja que la seva equació és la d'una el·lipse amb centre (2,3).

L'el·lipse es mostra a la figura 1 per a diversos valors de G. A major valor de G, major guany.

Hi ha solucions que pertanyen a la regió, però no donen el màxim valor G, mentre que altres, com G = 92.4, estan fora de la zona verda, és a dir la zona de solució.

Llavors, el màxim valor de G, tal que X i Y pertanyi a la regió de solució correspon a:

G = 77 (guany màxim), la qual es dóna per X = 7 i Y = 0.

Curiosament, la màxima guany passa quan la suma de vendes del producte I és nul, mentre que la suma del producte X aconsegueix el seu major valor possible.

- Exercici 2 (Mètode analític: multiplicadors de Lagrange)

Trobar la solució (x, y) que fa que la funció f (x, y) = x ² + 2y ² sigui màxima en la regió g (x, y) = x ² + i ² - 1 = 0.

solució

Es tracta clarament d'un problema de programació no-lineal, ja que tant la funció objectiu f (x, y) com la restricció g (x, y) = 0, no són combinació lineal de les variables xi y.

Es farà servir el mètode dels multiplicadors de Lagrange, el qual requereix en primer lloc definir la funció de Lagrange L (x, i, λ):

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

On λ és un paràmetre anomenat multiplicador de Lagrange.

Per determinar els valors extrems de la funció objectiu f, a la regió de solució donada per la restricció g (x, y) = 0, se segueixen aquests passos:

-Trobar les derivades parcials de la funció de Lagrange L, respecte de x, i, λ.

-Igualar a zero cada derivada.

Aquí la seqüència d'aquestes operacions:

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

Solucions possibles de sistema

Una solució possible d'aquest sistema és λ = 1 perquè es satisfaci la primera equació, en aquest cas i = 0 perquè es compleixi la segona.

Aquesta solució implica que x = 1 o x = -1 perquè es satisfaci la tercera equació. D'aquesta manera s'han obtingut dues solucions S1 i S2:

S1: (x = 1, y = 0)

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

L'altra alternativa és que λ = 2 per a que es satisfaci la segona equació, sense importar el valor i.

En aquest cas, l'única forma perquè es satisfaci la primera equació és que x = 0. Considerant la tercera equació, només hi ha dues solucions possibles, les quals anomenarem S3 i S4:

S3: (x = 0, i = 1)

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

Per saber quina o quines d'aquestes solucions maximitzen la funció objectiu, es procedeix a substituir en 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

Concloem que les solucions que maximitzen af, quan xiy pertanyen a la circumferència g (x, y) = 0 són S3 i S4.

Els parells de valors (x = 0, i = 1) i (x = 0, i = -1) maximitzen f (x, y) a la regió de solució g (x, y) = 0.

- Exercici 3 (Gradient nul)

Trobar solucions (x, i) perquè la funció objectiu:

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

Sigui màxima en la regió g (x, y) = x ² + i ² - 1 ≤ 0.

solució

Aquest exercici és similar a l'exercici 2, però la regió de solució (o restricció) s'estén a la regió interior de la circumferència g (x, y) = 0, és a dir a l'cercle g (x, y) ≤ 0. Això inclou a la circumferència i la seva regió interior.

La solució a la frontera ja va ser determinada en l'exercici 2, però falta explorar la regió interior.

Per a això s'ha de calcular la gradient de la funció f (x, y) i igualar-la a zero, per buscar valors extrems a la regió de solució. Això és equivalent a calcular les derivades parcials de f respecte de x i respectivament i igualar a zero:

∂f / ∂x = 2 x = 0

∂f / ∂y = 4 i = 0

Aquest sistema d'equacions té com a única solució (x = 0, i = 0) que pertany a l'cercle g (x, y) ≤ 0.

Substituint aquest valor en la funció f resulta:

f (0, 0) = 0

En conclusió, el valor màxim que pren la funció en la regió de solució és 2 i passa a la frontera de la regió solució, per als valors (x = 0, i = 1) i (x = 0, i = -1).

referències

1. Avriel, M. 2003. Nonlinear Programing. Dover Publishing.
2. Bazaraa. 1979. Nonlinear Programing. John Wiley & Sons.
3. Bertsekas, D. 1999. Nonlinear Programing: 2nd edition. Athena Scientific.
4. Nocedal, J. 1999. Numerical Optimization. Springer-Verlag.
5. Wikipedia. Programació no lineal. Recuperat de: es.wikipedia.com