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 igualdad. La introducción de una variable de holgura reemplaza una restricción de desigualdad con una restricción de igualdad y 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 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 la restricción restringe los posibles cambios desde ese punto.
- Si una variable de holgura es positiva en una solución candidata en 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 momento, el punto es inviable (no permitido), ya que no satisface la restricción.
Ejemplo
Introduciendo la variable de holgura , la desigualdad se puede convertir a la ecuación .
Incrustar en orthant
Las variables de holgura dan una incrustación de un politopo en el estándar f - orthant , dondees 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 sobre (no se pueden realizar todas las combinaciones), y se expresa en términos de las restricciones (funcionales lineales, covectores).
Las variables de holgura son duales a coordenadas baricéntricas generalizadas y, de forma dual a coordenadas baricéntricas generalizadas (que no son únicas, pero pueden realizarse todas), 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 estándar-simplex, que tiene vértices - el mapa está en: y expresa puntos en términos de vértices (puntos, vectores). El mapa es uno a uno si y solo si el politopo es un simplex, en cuyo caso el mapa es un isomorfismo; esto corresponde a un punto que no tiene coordenadas baricéntricas generalizadas únicas .
Referencias
- ^ 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 .
- ^ Gärtner, 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