Programació no lineal

De Viquipèdia
Dreceres ràpides: navegació, cerca

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 | modifica el codi]

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 | modifica el codi]

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:

Exemples bidimensionals resolts amb el mètode gràfic[modifica | modifica el codi]

Representació gràfica del primer exemple.
Representació gràfica del segon exemple.

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 | modifica el codi]