Teorema de Holguras complementarias
Braulio RIveraDocumentos de Investigación31 de Enero de 2019
299 Palabras (2 Páginas)1.275 Visitas
Teorema de Holguras Complementarias.
El teorema de holgura complementaria permite calcular la solución óptima del dual a partir de la solución óptima del primal y viceversa.
Teorema de Holgura complementaria: Dados los vectores y , soluciones óptimas de los problemas primal y dual respectivamente, se cumple: [pic 1][pic 2]
[pic 3][pic 4]
[pic 5][pic 6]
Donde:
-ésima fila de la matriz [pic 7][pic 8]
-ésima columna de la matriz [pic 9][pic 10]
DEMOSTRACION. Al demostrar el resultado de dualidad débil se tiene que . Esto implica:[pic 11]
[pic 12]
[pic 13]
O, equivalentemente:
[pic 14]
[pic 15]
Las implicaciones de este teorema pueden verse en las siguientes tablas.
Si se cumple: | Entonces: |
[pic 16] | [pic 17] |
[pic 18] | [pic 19] |
Donde:
-ésima columna de la matriz .[pic 20][pic 21]
Es decir, en el óptimo, a una variable primal positiva le corresponde una restricción dual saturada y, análogamente, a una restricción dual con holgura le corresponde una variable primal nula.
Si se cumple: | Entonces: |
[pic 22] | [pic 23] |
[pic 24] | [pic 25] |
Donde:
-ésima fila de la matriz . [pic 26][pic 27]
Es decir, en la solución óptima, las variables duales positivas se corresponden con restricciones primales saturadas y, análogamente, a una restricción primal con holgura le corresponde una variable dual nula.
Ejemplo. Dado el problema lineal
[pic 28]
Sujeto a
[pic 29]
[pic 30]
[pic 31]
Cuya solución óptima es [pic 32]
El problema dual correspondiente es:
[pic 33]
Sujeto a
[pic 34]
[pic 35]
[pic 36]
[pic 37]
Añadiendo variables de holgura
[pic 38]
Sujeto a
[pic 39]
[pic 40]
[pic 41]
[pic 42]
Utilizando el teorema de holgura complementaria, calculamos la solución óptima del problema dual.
Variables del primal | Restricciones del dual |
[pic 43] | [pic 44] |
[pic 45] | [pic 46] |
[pic 47] | [pic 48] |
Restricciones del primal | Variables del dual |
[pic 49] | Calcular el valor de [pic 50] |
[pic 51] | Calcular el valor de [pic 52] |
Sustituyendo en el sistema de restricciones duales los valores cero para las variables de holgura y , se tiene el sistema [pic 53][pic 54]
[pic 55]
[pic 56]
[pic 57]
Resolviendo el sistema se obtiene la solución óptima del modelo dual.
[pic 58]
Como se puede observar, este teorema ayuda como método de comprobación a la solución óptima de un problema primal. Es su aplicación más común.
Bibliografía:
Villaba Vilá, D. and Bueno Hernández, Y. (2012). Decisiones empresariales con hoja de cálculo. 1st ed. Madrid: Ediciones Pirámide, pp.171-177, 200-202.
Ocw.ehu.eus. (2018). [online] Available at: https://ocw.ehu.eus/file.php/19/3._dualidad.pdf [Accessed 1 Dec. 2018].
...