branca de les matemàtiques From Wikipedia, the free encyclopedia
En matemàtiques, estadística, ciències empíriques, ciències de la computació o economia, l'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]
![]() |
Aquest article o secció necessita l'atenció d'un expert en la matèria. |
![]() |
Aquest article o secció no cita les fonts o necessita més referències per a la seva verificabilitat. |
L'optimització intenta donar solució a una sèrie de problemes que es caracteritzen per buscar 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 representa un vector. L'expressió f(x) és la funció objectiu, la que s'ha d'optimitzar, que mesura la qualitat de les decisions. A més a més la x ha de complir les restriccions que té el problema o bé ha de pertànyer al conjunt de decisions factibles, .
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.
Pierre de Fermat i Joseph Louis Lagrange van trobar fórmules basades en el càlcul per identificar valors òptims, mentre que Isaac Newton i Carl Friedrich Gauss van proposar mètodes iteratius per aproximar l'optimització. Històricament, el terme programació lineal per referir-se a certs problemes d'optimització es deu a George B. Dantzig, encara que gran part de la teoria havia estat introduïda per Leonid Kantorovich el 1939. Dantzig va publicar l'algoritme símplex en 1947 i John von Neumann va desenvolupar la teoria de la dualitat en el mateix any.
El terme programació en aquest context no es refereix a la programació d'ordinadors. Més aviat, el terme ve de l'ús de programa per l'exèrcit de Estats Units en referir-se a la proposta d'entrenament i planificació logística, el qual va ser el problema estudiat per Dantzig en aquell temps.
Altres investigadors importants en el camp de l'optimització matemàtica van ser els següents:
|
|
La resolució que es plantegi dependrà del nivell de la generalitat que prengui el problema.
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.
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:
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:
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ó.
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ó.
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.
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:
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.
Quan les variables del problema (funció objectiu i/o restriccions) són variables aleatòries, es realitza optimització estocàstica.
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.