Optimització matemàtica

De Viquipèdia
Salta a: navegació, cerca

En matemàtiques, estadística, ciències empíriques, ciències de la computació o economia, la optimització matemàtica (també dita optimització o programació matemàtica) és la selecció del millor element (respecte d'un criteri determinat) entre un conjunt d'elements disponibles.[1]

L'optimització intenta donar solució a una sèrie de problemes. Aquests es caracteritzen pel fet que busquen quin és el màxim i/o el mínim d'una funció, suposant que n'hi hagi. S'entén per un màxim el valor més gran que pot atènyer la funció, ja sigui en un domini limitat (es parla de màxim relatiu) o bé en la totalitat del seu domini (es parla de màxim global). De la mateixa manera es té el mínim que és el valor més petit que pot prendre la funció, mínim global si es tracta del valor més petit de tot el seu domini o mínim relatiu si el domini d'aquesta funció ve delimitat .

Per tant, la programació matemàtica intenta donar resposta als problemes que segueixen l'esquema següent:

on la x equival a un vector. L'expressió f(x) és la funció objectiu, la que volem optimitzar, que mesura o bé representa la qualitat de les decisions. A més a més la x ha d’estar dintre les restriccions que et dóna el problema o bé ha de pertanyé al conjunt de decisions factibles, equival a:

Problemes d'optimització[modifica]

Per resoldre un problema d'optimització de funcions, un dels procediments a seguir és: d'entrada, plantejar la funció que es vol maximitzar o bé minimitzar. S'ha de plantejar una equació que relacioni les diverses variables del problema (suposant que hi hagi més d'una variable). Continuant amb la suposició, es pot aïllar una variable d'una equació i així substituir-la en l'altra funció, de manera que queda una sola variable. Ara, ja es pot derivar la funció i igualar-la a zero per trobar els punts estacionaris o extrems locals. Aquests punts tendeixen a ser màxims, mínims o bé punts de sella. Tot i això, la funció pot tenir més màxims i mínims que s'acostumen a trobar als extrems del domini i als punts on la funció no es pot derivar. No obstant això, a vegades, per solucionar aquest tipus de problemes amb restriccions es pot trobar amb un sistema d'igualtats o desigualtats que s'ha de resoldre per poder arribar a la solució del problema d'optimització.

Per tant, aquests tipus de problemes tracten de prendre una decisió òptima per tal de maximitzar o minimitzar un criteri determina. És per aquest motiu, que s'utilitza sovint en l'àmbit de les ciències socials i concretament l'econòmic. Els economistes, l'utilitzen per trobar els màxims beneficis davant d'una producció, com poder augmentar la velocitat i l'eficiència, així com reduir costos, temps, riscs... A més a més, utilitzen restriccions, ja que les empreses no acostumen a tenir una llibertat total a l'hora d'actuar, estan regides per un pressupost, per unes capacitats financeres, un espai físic... Per tant, qualsevol decisió no és possible. Les restriccions ajuden a predir els comportaments que duran a terme els empresaris. Un dels exemples més senzills, per començar amb l'optimització i les restriccions és la programació lineal.

Tipus d'optimitzacions[modifica]

La resolució que es plantegi dependrà del nivell de la generalitat que prengui el problema.

Optimització clàssica o sense restriccions[modifica]

D'entrada cal derivar la funció que es vol optimitzar. Un cop derivada la funció presentada s'ha d'igualar a zero per tal de trobar un valor per a cada variable que es disposa.

∂f / ∂xi(a) = 0

Com a condició cal indicar que "i" pot ser qualsevol valor que estigui entre [0,∞).

Si la funció objectiu és d'una variable: primer es fa la seva derivada i després s'iguala a 0 per trobar allà on hi ha un punt estacionari. Per resoldre l'equació, cal aïllar la variable (es pot usar factor comú o haver de resoldre equacions de segon, tercer... grau). El punt que s'obtingui serà un possible punt estacionari.

Si la funció objectiu és de dues variables: d'entrada cal realitzar les derivades parcials respecte a cada una de les variables i s'ha d'igualar les dues parcials que surtin a 0. Aquest cop, usant el mètode de substitució es troba el punt o bé que s'hagi de resoldre un sistema de dues equacions amb dues incògnites. Per tant, et pot recórrer al mètode de reducció o igualació. Un cop igualat a zero i s'hagin trobat els possibles punts estacionaris cal comprovar si realment són òptims, ja que no pot afirmar que tot punt estacionari sigui un òptim (màxim o mínim), sinó que si la funció és derivable llavors es tindrà un punt que pot ser màxim o mínim. Per tant, cal estudiar les condicions que ho determinaran i classificar-los segons el tipus d'òptim que siguin:

  • Condició de primer ordre (segons la fórmula inicial): "a" serà un òptim de "f", per tant, serà un punt crític de "f". En el cas d'una funció objectiu amb dues variables es pot usar el que anomenem R². Donada una funció f(x,y) i un punt P=(x₀, y₀) serà :
    • "P" és un màxim local si f(x,y) és més petit o igual que f(x₀, y₀). Suposant que existeix un cercle de centre "P" i radi r>0 per a totes les "x" i "y" del cercle.
    • "P" és un mínim local si f(x,y) és més gran o igual que f(x₀, y₀). Suposant que existeix un cercle de centre "P" i radi r>0 per a totes les "x" i "y" del cercle.
    • "P" és un punt de sella, quan sigui un punt estacionari i no es pugui considerar ni màxim ni mínim.
  • Condició de segon ordre, seguint el Teorema 1 (tenint en compte que "a" és un punt crític de "f" i només és vàlid quan tenim una funció de dues variables o més i les seves derivades parcials de 1r i 2n ordre són contínues):
    • "a" serà un mínim local de "f" quan, la forma quadràtica que té per matriu associada a H(a)f és definida positiva (si i només si tots els valors propis de "x" i "y" són positius i diferents de 0,0), si surt semidefinida positiva (si els valors propis de "x" i "y" donen el valor 0,0 o un valor positiu) hem de mirar les definicions.
    • "a" serà un màxim local de "f" quan, la forma quadràtica que té per matriu associada a H(a)f és definida negativa (si i només si tots els valors propis de "x" i "y" són negatius i diferents de 0,0), si surt semidefinida negativa (si els valors propis de "x" i "y" donen el valor 0,0 o un valor negatiu) hem de mirar les definicions.
    • "a" serà un punt de sella de "f" quan, la forma quadràtica que té per matriu associada a H(a)f és indefinida.
  • Condició suficient de primer ordre: per determinar la concavitat o convexitat de la funció (partint de la base que a és un punt crític de "f"):
    • La funció (f) serà convexa si "a" és un mínim global de "f".
    • La funció (f) serà còncava si "a" és un màxim global de "f".

Optimització amb restriccions d'igualtat (no clàssica)[modifica]

Optimitzar f(x)
Subjecte a gi(x) = 0
Com a condició cal dir que "i" pot ser qualsevol valor que estigui entre [0,∞]

En aquest cas es tracta d'una funció objectiu que està subjecta o regida per una altra funció que li determina el domini. Aquest tipus d'optimització es pot resoldre de diverses maneres:

Mètode directe o substitució[modifica]

La resolució mitjançant el mètode directe o substitució tracta de transformar el problema original a un problema equivalent d'optimització però sense cap restricció.

Optimitzar f(x)
Subjecte x є M
Exemple:
Optimitzar (x-3)² + (y+6)²
Subjecte x + y = 7

Usant el mètode directe es pot aïllar una de les variables de la restricció (x = 7–y) i substituir a la funció inicial o objectiu [(7-y)-3]² + (y+6)². Ara ja es pot resoldre l'equació d'una variable de segon grau, llavors es pot trobar un valor de "y". Obtingut aquest valor, es substitueix a la restricció i ja es disposa del valor de "x" també "i" per tant, ja s'ha trobat el possible òptim. Ara tan sols, queda classificar-lo segons les condicions de primer o segon ordre, ara bé, sempre serà relatiu l'òptim trobat, ja que està condicionat a un domini de la funció.

Mètode dels multiplicadors de Lagrange[modifica]

La resolució mitjançant el mètode dels multiplicadors de Lagrange s'acostuma a utilitzar quan no es pot aïllar una de les variables de la restricció. Aquest mètode consisteix en plantejar la funció lagrangiana: "L (x,y) = f(x,y) – λ [g(x,y)-C)" on "λ" és una constant. Un cop feta la funció lagrangiana s'han de fer les derivades parcials respecte a les dues variables que conté la funció ("x" i "y") i igualar-les a 0. Amb aquestes dues equacions i la restricció es pot plantejar un sistema de tres equacions.

f'(x)= λg'(x)
f'(y)= λg'(y)
g(x,y)= C

Llavors queda resoldre el sistema per tal de trobar els valors que prenen "x", "y" i "λ". Un cop es disposi dels valors que poden prendre cada una de les variables, cal classificar-los segons quin tipus d'òptim siguin. Per tant, primer es substituiran els valors a la funció lagrangiana que s'ha creat només començar amb la resolució del problema. Una manera ràpida i senzilla per saber si es parla d'un mínim o un màxim és fixar-se en la funció lagrangiana. Si "f" i "g" són funcions convexes encara que hi hagi alguna funció lineal, la funció resultat serà convexa i per tant l'òptim trobat serà un mínim. No obstant això, si "f" i "g" són funcions còncaves encara que hi hagi alguna funció lineal el resultat serà còncava, i per tant, l'òptim trobat serà un màxim. Si d'aquesta manera no es pot saber el tipus d'òptim caldrà recórrer al menor orlat o ampliat. Si el resultat d'aquest és menor que 0, s'obté que és un mínim, mentre que, si és major que 0, es tracta d'un màxim.

Esquema d'estudi generals d'aquest tipus de problemes:

  1. D'entrada, cal formular el problema de manera que amb un costat es tingui la funció que es vol optimitzar, i a sota la restricció a la qual es troba sotmesa la funció.
  2. A continuació cal fer les derivades parcials i igualar-les a zero per trobar els punts crítics.
  3. Classificar els punts crítics en funció de la seva naturalesa, és a dir, si es tracta d'un mínim o d'un màxim.
  4. Comprovar els límits de la funció, és a dir, les fronteres i els vèrtexs on també i s'hi poden trobar possibles punts crítics.

Optimització amb restriccions de desigualtat[modifica]

En aquest tipus d'optimització existeixen les anomenades condicions de Kuhn-Tucker, les quals, en alguns casos, poden ser utilitzades per intentar trobar punts crítics (màxims o mínims). No obstant això, aquesta és una àrea molt poc desenvolupada de la matemàtica. Les condicions de Khun-Tucker fallen freqüentment o són insuficients per trobar l'existència d'extrems.

Optimització estocàstica[modifica]

Quan les variables del problema (funció objectiu i/o restriccions) són variables aleatòries, es realitza optimització estocàstica.

Optimització amb informació no perfecta[modifica]

En aquest cas, la quantitat de variables o la funció objectiu poden ser desconegudes o una variable més. La matemàtica coneguda com a matemàtica borrosa es troba actualment intentant resoldre aquest tipus de problemes, però el desenvolupament d'aquest camp de la matemàtica és encara massa incipient, i fins ara els resultats obtinguts han sigut escassos.

Vegeu també[modifica]

Referències[modifica]

  1. The Nature of Mathematical Programming, Mathematical Programming Glossary, INFORMS Computing Society.

Enllaços externs[modifica]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Optimització matemàtica Modifica l'enllaç a Wikidata