Programació no lineal
La programació no lineal consisteix a optimitzar una funció objectiu sotmesa a unes restriccions. A diferència de la programació lineal estàndard, la funció objectiu i les restriccions poden ser funcions no lineals.
Formulació[modifica]
Un problema de la programació no lineal es podria enunciar de manera simplificada com:
Sigui una funció z = f(x,y) la qual es vol maximitzar o minimitzar.
Aquesta funció està sotmesa a un seguit de restriccions (tantes com sigui necessari): g = f(x,y)
Mètodes[modifica]
A continuació trobareu dos exemples de programació no lineal bidimensional amb la seva corresponent representació gràfica.
Cal remarcar que hi ha dos tipus de solucions: la solució gràfica i la solució analítica. Si es vol resoldre analíticament, es poden emprar diferents mètodes:
- Optimització
- Ramificació i poda
- Condicions de Karush-Kuhn-Tucker
- La funció de Lagrange
- Condició del punt estacionari
Exemples bidimensionals resolts amb el mètode gràfic[modifica]
El primer exemple:
La funció objectiu a estudiar és: x²+y²-5
I les seves restriccions són: –x+y²≤0 i x+y≤2.
Donada una funció objectiu amb les seves corresponents restriccions, per poder dibuixar-les es pot fer ús del programa Geogebra.
El que es busca és trobar quina és la regió factible per a la funció objectiu que es pretén estudiar. Com ja s'ha dit abans, es pot fer de diferents formes, la que s'explica a continuació, és el mètode gràfic.
Representem les funcions (funció objectiu i restriccions), que en el gràfic es poden trobar pintades amb diferents colors (funció objectiu de color lila i restriccions de color blau i vermell).
Per saber quina és la regió factible, agafem qualsevol punt del pla, per exemple, el (0,0). A continuació, el substituïm a les restriccions, per tal de comprovar si aquest punt respecta les desigualtats i així poder saber quina és la seva zona factible.
Un cop fet això, es determina la zona comuna per a les diferents restriccions i s'obté la regió factible de la funció objectiu a estudiar (marcada en color groc). Després, per poder determinar el màxim o el mínim de la funció objectiu, s'ha de recórrer als mètodes analítics esmentats anteriorment.
Un altre exemple per al que utilitzem el mateix mètode, és el de maximitzar la funció objectiu x²+ x.y +y²+ x+ y - 20, marcada amb el color lila.
Amb les restriccions: x+y ≤ 6,x ≤ 4 i ½.x+y ≥ -3 de color vermell, blau i verd.
Aquest cop, es tracta d'una el·lipse i s'han de seguir els mateixos passos explicats previàment.
Referències[modifica]
- Programación no lineal. Ejercicios resueltos Arxivat 2010-04-07 a Wayback Machine.
PDF (castellà) - Programación no lineal con restricciones en desigualdad Arxivat 2010-01-06 a Wayback Machine.PDF (castellà)
