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 en la variable de holgura. ^{[1] : 131}

Las variables de holgura se utilizan en particular en la programación lineal . Al igual que con las demás 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 a partir de ese punto.
• Si una variable de holgura es positiva en una solución candidata particular, la restricción no es vinculante allí, ya que no restringe los posibles cambios a partir de ese punto.
• Si una variable de holgura es negativa en algún punto, el punto es inviable (no permitido), ya que no satisface la restricción.

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

Ejemplo

Introduciendo la variable holgura , la desigualdad se puede convertir en la 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 proporcionan una incrustación de un politopo en el f - orthant estándar , donde es el número de restricciones (facetas del politopo). Este mapa es biunívoco (las variables de holgura se determinan de forma única) pero no suprayacente (no se pueden realizar todas las combinaciones) y se expresa en términos de las restricciones (funcionales lineales, covectores). ${\displaystyle P\hookrightarrow (\mathbf {R} _{\geq 0})^{f}}$ ${\displaystyle f}$

Las variables de holgura son duales con respecto a las coordenadas baricéntricas generalizadas y, dualmente con respecto a las coordenadas baricéntricas generalizadas (que no son únicas pero todas pueden realizarse), se determinan de forma única, pero no todas pueden realizarse.

Dualmente, las coordenadas baricéntricas generalizadas expresan un politopo con vértices (dual a facetas), independientemente de la dimensión, como la imagen del símplex estándar, que tiene vértices – la función es sobreyectiva: y expresa puntos en términos de los vértices (puntos, vectores). La función es biunívoca si y solo si el politopo es un símplex, en cuyo caso la función 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) . Cambridge University Press. ISBN 978-0-521-83378-3. Recuperado 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 de variables de holgura: resuelva problemas de variables de holgura en línea