Dualidad en problemas de programación lineal.
La dualidad en problemas de programación lineal!
Para cada problema de programación lineal, hay un problema único correspondiente que involucra los mismos datos y también describe el problema original. El problema original se llama programa primario y el problema único correspondiente se llama programa dual. Los dos programas están muy estrechamente relacionados y la solución óptima de doble proporciona información completa sobre la solución óptima de primaria y viceversa.
Diferentes aspectos útiles de esta propiedad son:
(a) Si primal tiene un gran número de constricciones y un pequeño número de variables, el cálculo se puede reducir considerablemente al convertir el problema a Dual y luego resolverlo.
(b) La dualidad en la programación lineal tiene ciertas consecuencias de largo alcance de la naturaleza económica. Esto puede ayudar a los gerentes a responder preguntas sobre cursos de acción alternativos y sus valores relativos.
(c) El cálculo del doble verifica la precisión de la solución primaria.
(d) La dualidad en la programación lineal muestra que cada programa lineal es equivalente a un juego de suma cero para dos personas. Esto indica que existen relaciones bastante cercanas entre la programación lineal y la teoría de los juegos.
1. Formación dual cuando Primal está en forma canónica:
De los dos programas anteriores, los siguientes puntos son claros:
(i) El problema de maximización en lo primario se convierte en el problema de minimización en lo dual y viceversa.
(ii) El problema de maximización tiene () restricciones.
(iii) Si el primario contiene n variables y m restricciones, el dual contendrá m variables y n restricciones.
(iv) Las constantes b 1 b 2, b 3 ……… b m en las restricciones de lo primario aparecen en la función objetivo del dual.
(v) Las constantes c 1, c 2, c 3 c n en la función objetivo del primal aparecen en las restricciones del dual.
(vi) Las variables en ambos problemas son no negativas.
Las relaciones de restricción de lo primordial y dual se representan a continuación.
Ejemplo 1:
Construye el dual al problema primordial
Solución:
En primer lugar, la restricción ≥ se convierte en una restricción ≤ al multiplicar ambos lados por -1.
Ejemplo 2:
Construye el dual al problema primordial
Solución:
Sean Y 1, Y 2, V 3 y V 4 las variables duales correspondientes, entonces el problema dual viene dado por
Como el problema dual tiene menos restricciones que el primario (2 en lugar de 4), requiere menos esfuerzo y esfuerzo para resolverlo. Esto se deduce del hecho de que la dificultad de cálculo en el problema de la programación lineal está asociada principalmente con el número de restricciones en lugar del número de variables.
Ejemplo 3:
Construye el dual del problema.
Solución:
Como el problema dado es de minimización, todas las restricciones deben ser de tipo. Multiplicando la tercera restricción por - 1 en ambos lados obtenemos.
-8x 1 + 2x 2 + 2x 3 ≥ -10
El dual del problema dado será
donde y 1, y 2, y 3, y 4 y y 5 son las variables duales asociadas con la primera, segunda tercera, cuarta y quinta restricción respectivamente.
