Restricción (matemáticas)

Condición de un problema de optimización que la solución debe satisfacer

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:

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

sujeto a

${\displaystyle x_{1}\geq 1}$

y

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

donde denota el vector ( x ₁ , x ₂ ). ${\displaystyle \mathbf {x} }$

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. ${\displaystyle f(\mathbf {x} )}$ ${\displaystyle \mathbf {x} =(1,1)}$ ${\displaystyle f(\mathbf {x} )}$

Terminología

• Si una restricción de desigualdad se cumple con igualdad en el punto óptimo, se dice que la restricción esvinculante , ya que el puntono se puedevariar 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 cumple 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íavariarse en la dirección de la restricción, aunque no sería óptimo hacerlo. En 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 es inviable .

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 . ${\displaystyle x_{1}...x_{n}}$ ${\displaystyle x_{1}\neq x_{2},x_{1}\neq x_{3}...,x_{2}\neq x_{3},x_{2}\neq x_{4}...x_{n-1}\neq x_{n}}$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

• Álgebra de restricciones
• Condiciones de Karush-Kuhn-Tucker
• Multiplicadores de Lagrange
• Conjunto de niveles
• Programación lineal
• Programación no lineal
• Restricción
• Teorías de satisfacibilidad módulo

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

• Beveridge, Gordon SG; Schechter, Robert S. (1970). "Características esenciales de la optimización". Optimización: teoría y práctica . Nueva York: McGraw-Hill. págs. 5-8. ISBN 0-07-005128-3.

Enlaces externos

• Preguntas frecuentes sobre programación no lineal Archivado el 30 de octubre de 2019 en Wayback Machine
• Glosario de programación matemática Archivado el 28 de marzo de 2010 en Wayback Machine.