Transporte

PROBLEMA DUAL

Para Todo problema de programación lineal, existe otro problema denominado dual. Las relaciones entre el problema dual y el original (denominado primal) son extremadamente útiles en gran variedad de soluciones; por ejemplo se verá que la solución óptima del problema dual es la que proporciona los precios sombra ya descritos anteriormente.
Supongamos el problema primal de laforma que se muestra en la izquierda, su problema dual se representará en la forma que se muestra a su derecha:

Problema Primal Problema Dual




Ejemplos:





Problema Dual cuando el Primal está en forma estándar

Problema Primal estándar Problema Primal canónica






Entonces el problema dual será:





Por tanto, el problema dual queda de la siguientemanera:



Reglas para la construcción de un problema dual:
1. EL número de variables del problema dual, es igual al número de restricciones del problema original y viceversa.
2. Los coeficientes de la FO en dual será el vector de disponibilidad de recursos del problema original.
3. Si el problema original es Máx, entonces el dual será Min; si el problema original es Min, entonces el dual seráMáx.
4. Los coeficientes de la primera función de restricción del problema dual, serán los coeficientes de la variable en las restricciones del problema original, y en forma análoga para las otras restricciones.
5. Los segundos miembros de las restricciones duales, son los coeficientes del a función objetivo del problema primal.
6. El sentido de la i-ésima restricción dual, es igual, si y sólosi la ´-ésima variable del problema original no tiene restricción de signo.
7. Si el problema original es un problema de Máx (Min), entonces luego de aplicar la regla 6, asigne a las restricciones duales, el sentido opuesto a la variable correspondientes del problema original.
8. La i-ésima variable del problema original, no tendrá restricción de signo, si y sólo si, la i-ésima restricción delproblema original es una igualdad.
9. Si el problema original es Máx (Min), entonces luego de aplicar la regla 8 asigne a las demás variables el signo contrario (el mismo signo) que la restricción correspondiente en el problema original.

Problema Primal o Dual
Maximizar Z ó
Problema Dual o Primal
Minimizar ó Z
Restricción
Forma
Forma
Forma
Variable ó

Irrestricta en signoVariable ó

Irrestricta en signo

Restricción
Forma
Forma
Forma

Ejemplo:



Solución:

1. N° variables del dual = N° restricciones del primal
2.
3. Máx Dual = Min

4., 5.,6.y 7. Restricciones:

8. irrestricta en signo.
9.







La solución óptima Dual en la tabla simplex

Relación entre los valores óptimos del primal y dual:

Propiedades:

1.Supongamos que los problemas Primal y Dual están en la forma canónica o en la forma estándar. Los valores objetivos de estos problemas son e para el primal y dual respectivamente; entonces:

a. Para soluciones factibles cualesquiera, no necesariamente básicas,
b. Si la solución óptima de ambos problemas es alcanzada los valores objetivos del primal y el dual serán iguales:
2. Consideremos elproblema primal (maximización) en forma canónica, cuyas restricciones son: ; multiplicamos ambos miembros por sumando sobre :
… (1)
3. Consideremos el problema dual asociado (minimización) cuyas restricciones son: ; multiplicamos por y sumamos sobre :
… (2)

Por tanto de (1) y (2) tenemos:

Reglas generales para determinar la solución óptima de un problema:

1. Si la variable dualcorresponde a la variable de holgura inicial en el primal, su valor óptimo está dado directamente por el coeficiente de esta variable de holgura en la ecuación óptimo.
2. Si la variable dual corresponde a una variable artificial inicial en el problema primal, su valor óptimo está dado por el coeficiente de esta variable artificial en la ecuación óptimo después de eliminar la constante . Eliminar...