stringtranslate.com

Restricción (matemáticas)

En matemáticas , una restricción es una condición de un problema de optimización que la solución debe satisfacer. Existen varios tipos de restricciones: principalmente restricciones de igualdad , restricciones de desigualdad y restricciones de números enteros . El conjunto de soluciones candidatas que satisfacen todas las restricciones se denomina conjunto factible . [1]

Ejemplo

El siguiente es un problema de optimización simple:

sujeto a

y

donde denota el vector ( x 1 , x 2 ).

En este ejemplo, la primera línea define la función que se debe minimizar (llamada función objetivo , función de pérdida o función de costo). La segunda y la tercera líneas definen dos restricciones, la primera de las cuales es una restricción de desigualdad y la segunda es una restricción de igualdad. Estas dos restricciones son restricciones duras , lo que significa que se requiere que se cumplan; definen el conjunto factible de soluciones candidatas.

Sin las restricciones, la solución sería (0,0), donde tiene el valor más bajo. Pero esta solución no satisface las restricciones. La solución del problema de optimización con restricciones planteado anteriormente es , que es el punto con el valor más pequeño de que satisface las dos restricciones.

Terminología

Restricciones duras y blandas

Si el problema exige que se cumplan las restricciones, como en la discusión anterior, a veces se hace referencia a las restricciones como restricciones duras . Sin embargo, en algunos problemas, llamados problemas de satisfacción de restricciones flexibles , se prefiere, pero no se exige, que se cumplan ciertas restricciones; dichas restricciones no obligatorias se conocen como restricciones blandas . Las restricciones blandas surgen, por ejemplo, en la planificación basada en preferencias . En un problema MAX-CSP , se permite violar una serie de restricciones y la calidad de una solución se mide por la cantidad de restricciones satisfechas.

Restricciones globales

Las restricciones globales [2] son ​​restricciones que representan una relación específica sobre un número de variables, tomadas en conjunto. Algunas de ellas, como la restricción alldifferent, se pueden reescribir como una conjunción de restricciones atómicas en un lenguaje más simple: la alldifferentrestricción se cumple sobre n variables y se satisface si las variables toman valores que son diferentes por pares. Es semánticamente equivalente a la conjunción de desigualdades . Otras restricciones globales extienden la expresividad del marco de restricciones. En este caso, generalmente capturan una estructura típica de problemas combinatorios. Por ejemplo, la restricción expresa que una secuencia de variables es aceptada por un autómata finito determinista . regular

Las restricciones globales se utilizan [3] para simplificar el modelado de problemas de satisfacción de restricciones , para ampliar la expresividad de los lenguajes de restricciones y también para mejorar la resolución de restricciones : de hecho, al considerar las variables en conjunto, las situaciones inviables se pueden ver antes en el proceso de resolución. Muchas de las restricciones globales están referenciadas en un catálogo en línea.

Véase también

Referencias

  1. ^ Takayama, Akira (1985). Economía matemática (2.ª ed.). Nueva York: Cambridge University Press. pág. 61. ISBN 0-521-31498-4.
  2. ^ Rossi, Francesca; Van Beek, Peter; Walsh, Toby (2006). "7". Manual de programación con restricciones (1.ª ed.). Ámsterdam: Elsevier. ISBN 9780080463643.OCLC 162587579  .
  3. ^ Rossi, Francesca (2003). Principles and Practice of Constraint Programming CP 2003 00 : 9th International Conference, CP 2003, Kinsale, Irlanda, 29 de septiembre al 3 de octubre de 2003. Actas . Berlín: Springer-Verlag Berlin Heidelberg. ISBN 9783540451938.OCLC 771185146  .

Lectura adicional

Enlaces externos