Variable de holgura

Concepto matemático

En un problema de optimización , una variable de holgura es una variable que se agrega a una restricción de desigualdad para transformarla en una restricción de igualdad. También se agrega una restricción de no negatividad sobre la variable de holgura. ^{[1] : 131}

Las variables de holgura se utilizan en particular en la programación lineal . Al igual que con las otras variables en las restricciones aumentadas, la variable de holgura no puede tomar valores negativos, ya que el algoritmo simplex requiere que sean positivos o cero. ^[2]

• Si una variable de holgura asociada con una restricción es cero en una solución candidata particular , la restricción es vinculante allí, ya que restringe los posibles cambios desde ese punto.
• Si una variable de holgura es positiva en una solución candidata particular, la restricción no es vinculante allí, ya que la restricción no restringe los posibles cambios desde ese punto.
• Si una variable de holgura es negativa en algún punto, el punto no es factible (no está permitido), ya que no satisface la restricción.

Las variables de holgura también se utilizan en el método Big M.

Ejemplo

Al introducir la variable de holgura , la desigualdad se puede convertir en ecuación . ${\displaystyle \mathbf {s} \geq \mathbf {0} }$ ${\displaystyle \mathbf {A} \mathbf {x} \leq \mathbf {b} }$ ${\displaystyle \mathbf {A} \mathbf {x} +\mathbf {s} =\mathbf {b} }$

Incrustación en orthant

Las variables de holgura dan una incorporación de un politopo en el forthant estándar , donde es el número de restricciones (facetas del politopo). Este mapa es uno a uno (las variables de holgura se determinan de forma única) pero no (no se pueden realizar todas las combinaciones) y se expresa en términos de restricciones (funcionales lineales, covectores). ${\displaystyle P\hookrightarrow (\mathbf {R} _{\geq 0})^{f}}$ ${\displaystyle f}$

Las variables de holgura son duales a las coordenadas baricéntricas generalizadas y, dualmente a las coordenadas baricéntricas generalizadas (que no son únicas pero todas pueden realizarse), están determinadas de forma única, pero no todas pueden realizarse.

Dualmente, las coordenadas baricéntricas generalizadas expresan un politopo con vértices (dobles a facetas), independientemente de la dimensión, como la imagen del estándar -simplex, que tiene vértices- en el mapa está: y expresa puntos en términos de los vértices (puntos, vectores ). El mapa es uno a uno si y sólo si el politopo es simplex, en cuyo caso el mapa es un isomorfismo; esto corresponde a un punto que no tiene coordenadas baricéntricas generalizadas únicas . ${\displaystyle n}$ ${\displaystyle (n-1)}$ ${\displaystyle n}$ ${\displaystyle \Delta ^{n-1}\twoheadrightarrow P,}$

Referencias

1. Boyd, Stephen P.; Vandenberghe, Lieven (2004). Optimización convexa (PDF) . Prensa de la Universidad de Cambridge. ISBN 978-0-521-83378-3. Consultado el 15 de octubre de 2011 .
2. Gartner, Bernd; Matoušek, Jiří (2006). Comprensión y uso de la programación lineal . Berlín: Springer. ISBN 3-540-30697-8.^{: 42}

enlaces externos

• Tutorial sobre variables de holgura: resuelva problemas de variables de holgura en línea