Vés al contingut

Problema d'optimització

De la Viquipèdia, l'enciclopèdia lliure
Un altre problema d'optimització típic, excepte que es requereix una calculadora per resoldre el problema. Maximitzar és el que volem determinar.

En matemàtiques, informàtica i economia, un problema d'optimització és el problema de trobar la millor solució entre totes les solucions factibles.[1]

Els problemes d'optimització es poden dividir en dues categories, depenent de si les variables són contínues o discretes:

La forma estàndard d'un problema d'optimització contínua és [2]on

Si m = p = 0, el problema és un problema d'optimització sense restriccions. Per convenció, la forma estàndard defineix un problema de minimització. Un problema de maximització es pot tractar negant la funció objectiu.[3]

En el camp dels algorismes d'aproximació, els algorismes estan dissenyats per trobar solucions gairebé òptimes a problemes difícils. La versió de decisió habitual és llavors una definició inadequada del problema, ja que només especifica solucions acceptables. Tot i que podríem introduir problemes de decisió adequats, el problema es caracteritza de manera més natural com un problema d'optimització.[4]

Referències[modifica]

  1. «Optimization Problems: Meaning & Examples | StudySmarter» (en anglès). https://www.studysmarter.us.+[Consulta: 1r gener 2023].
  2. Boyd, Stephen P. Convex Optimization (pdf) (en anglès). Cambridge University Press, 2004, p. 129. ISBN 978-0-521-83378-3. 
  3. «4.7: Optimization Problems» (en anglès). https://math.libretexts.org,+27-04-2017.+[Consulta: 1r gener 2023].
  4. Ausiello, Giorgio, Complexity and Approximation (Corrected ed.), ISBN 978-3-540-65431-5