Constricció

En matemàtiques, una restricció o constricció és una condició que ha de satisfer una solució d'un problema d'optimització. Hi ha dos tipus de restriccions: Restriccions d'igualtat i restriccions de desigualtat. El conjunt de solucions que satisfan totes les restriccions s'anomena el conjunt de solucions possibles.

Exemple

A continuació un exemple senzill de problema d'optimització:

min f ( x ) = x 1 2 + x 2 4 {\displaystyle \min f(\mathbf {x} )=x_{1}^{2}+x_{2}^{4}}

subjecte a

x 1 ≥ 1 {\displaystyle x_{1}\geq 1}

i

x 2 = 1 , {\displaystyle x_{2}=1,\,}

on x {\displaystyle \mathbf {x} } fa referència al vector (x1, x₂).

En aquest exemple, la primera línia defineix la funció que cal minimitzar (anomenada funció objectiu). La segona i la tercera línia defineixen dues restriccions, la primera de les quals és una restricció de desigualtat i la segona és una restricció d'igualtat. Aquestes dues restriccions defineixen el conjunt de solucions possibles.

Sense restriccions, la solució seria ( 0 , 0 ) {\displaystyle (0,0)\,} on f ( x ) {\displaystyle f(\mathbf {x} )} té el valor més baix. Tanmateix, aquesta solució no satisfà les restriccions. La solució del problema d'optimització restringit anterior és x = ( 1 , 1 ) {\displaystyle \mathbf {x} =(1,1)} , que és el punt amb el valor de f ( x ) {\displaystyle f(\mathbf {x} )} més baix que satisfà les dues restriccions.

En forma canònica, les restriccions s'escriuen mitjançant funcions restricció a un costat de la igualtat o desigualtat i zero a l'altre costat. A l'exemple de més amunt, les restriccions es poden escriure en forma canònica de la següent manera:

c 1 ( x ) = 1 − x 1 ≤ 0 {\displaystyle c_{1}(\mathbf {x} )=1-x_{1}\leq 0}

i

c 2 ( x ) = 1 − x 2 = 0. {\displaystyle c_{2}(\mathbf {x} )=1-x_{2}=0.}

De la mateixa manera, les restriccions de desigualtat es poden escriure en forma canònica amb els signes oposats. En conseqüència, la primera restricció es pot escriure com

c 1 ( x ) = x 1 − 1. {\displaystyle c_{1}(\mathbf {x} )=x_{1}-1.}

Vegeu també

Enllaços externs

  • FAQ de programació no lineal Arxivat 2009-02-17 a Wayback Machine. (anglès)
  • Glossari de Programació matemàtica Arxivat 2010-03-28 a Wayback Machine. (anglès)