Problema d'optimisació

En matemàtiques, ciències de la computació i economia, un problema d'optimisació és el problema de trobar la millor solució a partir de totes les solucions factibles.

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

Un problema d'optimisació en variables discretes es coneix com optimisació discreta, en la que un objecte com un número entero, una permutació o un gràfic es deu trobar en un conjunt contable.
Un problema en variables contínues es coneix com optimisació contínua, en la que es deu trobar un valor òptim d'una funció contínua. Poden incloure problemes restringits i problemes multimodales.

Problema d'optimisació contínua

La forma estàndar d'un problema d'optimisació contínua és^[1]

\begin{matrix} \underset{x}{minimizar} & f (x) \\ s u j e t o a & g_{i} (x) \leq 0, i = 1, \dots, m \\ h_{j} (x) = 0, j = 1, \dots, p \end{matrix}

a on

$f : ℝ n \to ℝ$ és la funció objectiu a minimisar sobre el vector $x$ de $n$ -variables,
$g i (x) \leq 0$ es denominen restriccions de desigualtat
$h j (x) = 0$ es denominen restriccions d'igualtat, i
$m \geq 0$ i $p \geq 0$ .

Si $m = p = 0$ , el problema és un problema d'optimisació sense restriccions. Per convenció, la forma estàndar definix un problema de minimisació. Un problema d'maximización pot tractar-se negant la funció objectiu.

Problema d'optimisació combinatòria

Formalment, un problema d'optimisació combinatòria $A$ és un cuádruple $(I, f, m, g)$ , a on

$I$ és un conjunt d'instàncies;
donada una instància $x \in I$ , $f (x)$ és el conjunt de solucions factibles;
donada una instància $x$ una solució factible $i$ de $x$ , $m (x, i)$ denota la mida de $i$ , que generalment és un real positiu.
$g$ és la funció objectiu, i és $min$ o $max$ .

L'objectiu és llavors trobar per a algun cas $x$ una solució òptima, és dir, una solució factible $i$ en

m (x, y) = g {m (x, y^{'}) ∣ y^{'} \in f (x)} .

Per a cada problema d'optimisació combinatòria, hi ha un problema de decisió corresponent que pregunta si existix una solució factible per a alguna mida particular $m 0$ . Per eixemple, si hi ha un gràfic $G$ que conté els vèrtiços $o$ i $v$ , un problema d'optimisació podria ser "trobar una ruta de $o$ a $v$ que use la menor cantitat d'arestes". Este problema podria tindre una resposta de, digam, 4. Un problema de decisió corresponent seria "¿hi ha una ruta de $o$ a $v$ que use 10 arestes o menys?" Este problema es pot respondre en un simple 'sí' o 'no'.

En el camp dels algoritmes d'aproximació, els algoritmes estan dissenyats per a trobar solucions casi òptimes a problemes difícils. La versió de decisió habitual és llavors una definició inadequada del problema, ya que solament especifica solucions acceptables. Encara que podríem introduir problemes de decisió adequats, el problema es caracterisa més naturalment com un problema d'optimisació.^[2]

Vore també

Problema de conteo (complexitat)
Optimisació del disseny
Problema de funcionament
Investigació d'operacions
Satisfactori: no és necessari trobar l'òptim, solament una solució "suficientment bona".
Problema de busca
Programació semi-infinita

Referències

↑ Boyd; Vandenberghe, Lieven (2004). Convex Optimization (pdfpdf), Cambridge University Press, p. 129. ISBN 978-0-521-83378-3.
↑ Erro en la seqüencia d'órdens: no existix el mòdul «Citas».

Referències

Este artícul conté una traducció derivada de «Problema de optimización» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] Boyd; Vandenberghe, Lieven (2004). Convex Optimization (pdfpdf), Cambridge University Press, p. 129. ISBN 978-0-521-83378-3.

[Ausiello03-2] Erro en la seqüencia d'órdens: no existix el mòdul «Citas».

[1]

[2]