Teorema de Holguras complementarias
Enviado por Braulio RIvera • 31 de Enero de 2019 • Documentos de Investigación • 299 Palabras (2 Páginas) • 1.162 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.
...