En matemáticas , una restricción es una condición de un problema de optimización que la solución debe satisfacer. Hay 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
dónde denota el vector (x 1 , x 2 ).
En este ejemplo, la primera línea define la función que se minimizará (denominada función objetivo , función de pérdida o función de costo). La segunda y tercera líneas definen dos restricciones, la primera de las cuales es una restricción de desigualdad y la segunda de las cuales es una restricción de igualdad. Estas dos restricciones son restricciones estrictas , 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 limitaciones. La solución del problema de optimización restringida indicado anteriormente es, que es el punto con el menor valor de que satisface las dos restricciones.
Terminología
- Si una restricción de desigualdad se mantiene con igualdad en el punto óptimo, se dice que la restricción esvinculante , ya que el puntono sepuede variar en la dirección de la restricción aunque hacerlo mejoraría el valor de la función objetivo.
- Si una restricción de desigualdad se mantiene como una desigualdad estricta en el punto óptimo (es decir, no se cumple con la igualdad), se dice que la restricción esno vinculante , ya que el puntopodríavariar en la dirección de la restricción, aunque no sería óptimo hacerlo. Bajo ciertas condiciones, como por ejemplo en la optimización convexa, si una restricción no es vinculante, el problema de optimización tendría la misma solución incluso en ausencia de esa restricción.
- Si una restricción no se satisface en un punto dado, se dice que el punto no es factible .
Restricciones duras y blandas
Si el problema exige que se satisfagan las restricciones, como en la discusión anterior, las restricciones a veces se denominan restricciones estrictas . Sin embargo, en algunos problemas, denominados problemas de satisfacción de restricciones flexibles , se prefiere, pero no se requiere, que se satisfagan ciertas restricciones; estas restricciones no obligatorias se conocen como restricciones suaves . 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 el número de restricciones satisfechas.
Restricciones globales
Las restricciones globales [2] son restricciones que representan una relación específica en una serie de variables, tomadas en conjunto. Algunos de ellos, como la alldifferent
restricción, se pueden reescribir como una conjunción de restricciones atómicas en un lenguaje más simple: la alldifferent
restricción se mantiene en 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 amplían la expresividad del marco de restricciones. En este caso, suelen capturar una estructura típica de problemas combinatorios. Por ejemplo, la regular
restricción expresa que una secuencia de variables es aceptada por un autómata finito determinista .
Las restricciones globales se utilizan [3] para simplificar el modelado de problemas de satisfacción de restricciones , para extender la expresividad de los lenguajes de restricciones y también para mejorar la resolución de restricciones : de hecho, al considerar las variables en su conjunto, las situaciones no factibles se pueden ver antes en el proceso de resolución. . Muchas de las limitaciones globales están referenciadas en un catálogo en línea.
Ver también
Referencias
- ^ Takayama, Akira (1985). Economía Matemática (2ª ed.). Nueva York: Cambridge University Press. pag. 61 . ISBN 0-521-31498-4.
- ^ Rossi, Francesca; Van Beek, Peter; Walsh, Toby (2006). "7". Manual de programación de restricciones (1ª ed.). Amsterdam: Elsevier. ISBN 9780080463643. OCLC 162587579 .
- ^ Rossi, Francesca (2003). Principios y práctica de la programación de restricciones CP 2003 00: Novena Conferencia Internacional, CP 2003, Kinsale, Irlanda, 29 de septiembre al 3 de octubre de 2003. Actas . Berlín: Springer-Verlag Berlin Heidelberg. ISBN 9783540451938. OCLC 771185146 .
Otras lecturas
- Beveridge, Gordon SG; Schechter, Robert S. (1970). "Funciones esenciales en optimización" . Optimización: teoría y práctica . Nueva York: McGraw-Hill. págs. 5-8. ISBN 0-07-005128-3.