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. 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:

${\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 minimizará (llamada 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 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 restricciones. La solución del problema de optimización restringida 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 puntonose puede 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 cumple como desigualdad estricta en el punto óptimo (es decir, no se cumple con 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. 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 cumple en un punto determinado, se dice que ese 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 requiere, que se cumplan ciertas restricciones; Estas restricciones no obligatorias se conocen como restricciones suaves . Las restricciones suaves 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 en una serie de variables, tomadas en conjunto. Algunas de ellas, como la restricción de todos los diferentes, se pueden reescribir como una conjunción de restricciones atómicas en un lenguaje más simple: la alldifferentrestricción se cumple 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 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, se pueden ver situaciones inviables en una etapa más temprana del proceso de resolución. . Muchas de las limitaciones globales están referenciadas en un catálogo en línea.

Ver también

• Álgebra de restricciones
• Condiciones de Karush-Kuhn-Tucker
• Multiplicadores de Lagrange
• Ajuste de nivel
• Programación lineal
• Programación no lineal
• Restricción
• Teorías del módulo de satisfacción

Referencias

1. Takayama, Akira (1985). Economía Matemática (2ª ed.). Nueva York: Cambridge University Press. pag. 61.ISBN​ 0-521-31498-4.
2. Rossi, Francesca; Van Beek, Peter; Walsh, Toby (2006). "7". Manual de programación de restricciones (1ª ed.). Ámsterdam: Elsevier. ISBN 9780080463643. OCLC  162587579.
3. Rossi, Francesca (2003). Principios y práctica de programación de restricciones CP 2003 00: 9ª Conferencia Internacional, CP 2003, Kinsale, Irlanda, 29 de septiembre 3 de octubre de 2003. Actas . Berlín: Springer-Verlag Berlín Heidelberg. ISBN 9783540451938. OCLC  771185146.

Otras lecturas

• Beveridge, Gordon SG; Schechter, Robert S. (1970). "Funciones esenciales en 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.