 | Aquest article o secció necessita l'atenció d'un expert en la matèria.Si us plau, ajudeu a trobar-ne un omilloreu aquesta pàgina vosaltres mateixos si podeu. (Vegeu ladiscussió). |
Enmatemàtiques,estadística,ciències empíriques,ciències de la computació oeconomia, l'optimització matemàtica (també ditaoptimització oprogramació 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 que es caracteritzen per buscar quin ésel 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 undomini 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 unaequació que relacioni les diversesvariables 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 potderivar 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 lesciè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 unpressupost, 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 elsempresaris. Un dels exemples més senzills, per començar amb l'optimització i les restriccions és laprogramació lineal.
Pierre de Fermat iJoseph Louis Lagrange van trobar fórmules basades en elcàlcul per identificar valors òptims, mentre queIsaac Newton iCarl Friedrich Gauss van proposar mètodes iteratius per aproximar l'optimització. Històricament, el termeprogramació lineal per referir-se a certs problemes d'optimització es deu aGeorge B. Dantzig, encara que gran part de la teoria havia estat introduïda perLeonid Kantorovich el 1939. Dantzig va publicar l'algoritme símplex en 1947 iJohn von Neumann va desenvolupar la teoria de ladualitat en el mateix any.
El termeprogramació en aquest context no es refereix a laprogramació d'ordinadors. Més aviat, el terme ve de l'ús deprograma per l'exèrcit deEstats 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:
- Programació convexa estudia el cas en què la funció objectiu ésconvexa (minimització) ocòncava (maximització) i el conjunt de restriccions ésconvex. Aquest pot ser vist com un cas particular de la programació no lineal o com la generalització de la programació lineal o de la convexa quadràtica.
- Programació lineal (PL): és un tipus de programació convexa, en què la funció objectiuf és lineal i el conjunt de restriccions s'especifica usant només equacions i inequacions lineals. Aquest conjunt és anomenatpoliedre opolítop si està fitat.
- Programació cònica: és una forma general de la programació convexa. PL, PCSO i PSD poden tots són vists com a programes cònics amb el tipus de con apropiat.
- Programació de con de segon ordre (PCSO): és un tipus de programació convexa i inclou certs tipus de problemes de programació quadràtica.
- Programació semidefinida (PSD): és un subcamp de l'optimització convexa on les variables fonamentals sónmatrius semidefinides. És una generalització de la programació lineal i la programació quadràtica convexa.
- Programació geomètrica: és una tècnica per mitjà de la qual l'objectiu i les restriccions de desigualtat expressats com apolinomis i les restriccions d'igualtat com amonomis, poden ser transformats en un programa convex.
- Programació amb enters oProgramació entera: estudia programes lineals en els quals algunes o totes les variables estan obligades a prendre valorsenters. Aquesta no és convexa i, en general, és molt més complexa que la programació lineal regular.
- Programació quadràtica: permet a la funció objectiu tenir termesquadràtics, mentre que el conjunt factible pot ser especificat amb equacions i inequacions lineals. Per a formes específiques del terme quadràtic, aquesta és un tipus de programació convexa.
- Programació fraccionària: estudia l'optimització de raons de dues funcions no lineals. La classe especial de programes fraccionaris còncaus es pot transformar a un problema d'optimització convexa.
- Programació no lineal: estudia el cas general en què la funció objectiu, o les restriccions, o tots dos, contenen parts no lineals. Aquest pot ser un programa convex o no. En general, si el programa és convex, afecta la dificultat de resolució.
- Programació estocàstica oOptimització estocàstica: estudia el cas en què alguna de les restriccions o paràmetres depèn devariables aleatòries.
- Programació robusta: com la programació estocàstica, és un intent per capturar la incertesa en les dades fonamentals del problema d'optimització. Això es fa mitjançant l'ús de variables aleatòries, però en canvi, el problema es resol tenint en compte imprecisions a les dades d'entrada.
- Optimització combinatòria: es preocupa dels problemes on el conjunt de solucions factibles ésdiscret o pot ser reduït a un.
- Optimització dimensional-infinita: estudia el cas on el conjunt de solucions factibles és un subconjunt d'un espai dedimensió infinita, per exemple un espai de funcions.
- Heurístiques iMetaheurístiques: fan suposicions sobre el problema que s'optimitza. Les heurístiques no solen pas garantir que qualsevol solució òptima sigui trobada. Després, les heurístiques es fan servir per trobar solucions aproximades per a molts problemes d'optimització complicats.
- Satisfacció de restricció: estudia el cas en què la funció objectiuf és constant (aquesta és usada enintel·ligència artificial, particularment enraonament automatitzat).
- Programació disjuntiva: s'usa quan almenys una restricció pot ser satisfeta però no totes. Aquesta és d'ús particular en la programació en un nombre de subcamps. Les tècniques són dissenyades principalment per a l'optimització en contextos dinàmics (és a dir, presa de decisions amb el transcurs del temps).
- Càlcul de variacions: cerca optimitzar un objectiu definit sobre molts punts amb el temps, considerant com la funció objectiu canvia si el canvi és petit en el camí d'elecció. La tècnica del control òptim és una generalització d'aquest.
- Programació dinàmica estudia el cas en què l'estratègia d'optimització es basa en la divisió del problema en subproblemes més petits. L'equació que descriu la relació entre aquests subproblemes s'anomenaequació de Bellman.
- Programació matemàtica amb restriccions d'equilibri és on les restriccions inclouen desigualtats variables o complementàries.
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 resoldreequacions 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 lesderivades parcials respecte a cada una de les variables i s'ha d'igualar les dues parcials que surtin a 0. Aquest cop, usant elmètode de substitució es troba el punt o bé que s'hagi de resoldre unsistema de dues equacions amb dues incògnites. Per tant, et pot recórrer almè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 unmàxim local si f(x,y) és més petit o igual que f(x₀, y₀). Suposant que existeix un cercle decentre "P" iradi r>0 per a totes les "x" i "y" del cercle.
- "P" és unmí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 unpunt 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, laforma quadràtica que té permatriu 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 laconcavitat oconvexitat 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:
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 delsmultiplicadors 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 lafunció lagrangiana: "L (x,y) = f(x,y) – λ [g(x,y)-C)" on "λ" és unaconstant. 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ónfuncions convexes encara que hi hagi algunafunció lineal, la funció resultat serà convexa i, per tant, l'òptim trobat serà un mínim. No obstant això, si "f" i "g" sónfuncions 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:
- 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ó.
- A continuació cal fer les derivades parcials i igualar-les a zero per trobar els punts crítics.
- 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.
- Comprovar els límits de la funció, és a dir, les fronteres i elsvè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 anomenadescondicions 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ónvariables 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 amatemà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.
