Todo problema de P.L. lleva asociado un segundo problema con propiedades tales, que la solución óptima de uno de ellos produce información sobre la solución óptima del otro. A uno de los problemas se le conoce como problema primal (primario) y al otro se le llama el problema dual.
Primal:
Max Zx= C1X1 + C2X2 + ... + CnXn
Sujeto
A11X1 + a12X2 + ... + a1nXn <= b1
A21X1 + a22X2 + ... + a2nXn <= b2
Am1X1 + am2X2 + ... + amnXn <= bm
Xi>=0
Dual:
Min Zy = bly1 + b2y2 + ... + bmym
Sujeto:
A11y1 + a21y2 + ... + am1ym >= C1
A12y1 + a22y2 + ... + am2ym >= C2
A1ny1 + a2ny2 + ... + amnym >= CN
Yj >= 0
Notemos:
1.- El problema Primario tiene "n" variables y "m" restricciones y el Dual "m" variables y "n " restricciones.
2.-Los coeficientes de la función objetivo del Dual son los términos independientes de las restricciones del Primal y viceversa.
3.-Si el problema Primal es una MAX. el Dual será una Min. y viceversa.
4.-La fila "j" de la matriz del Dual es la columna "j" del Primal y viceversa.
5.-El Dual del Dual es el Primal.
6.-Si una de las restricciones del Primal esta dada en forma de igualdad, la variable correspondiente del Dual será irrestricta en signo y viceversa. (Ejm 18-19-20).
El teorema fundamental de la Dualidad establece que si uno de dos problemas, Primal o Dual, tiene una solución óptima, entonces el otro también tiene una solución óptima y los valores de esos óptimos son iguales.
El teorema indica, además, que podemos encontrar una solución óptima del problema del Dual, observando la tabla final del SIMPLEX obtenida en la resolución del Primal. En efecto el valor óptimo de la variable Y1 se encuentra en la fila de la ecuación 0 bajo el vector de holgura H1; el de la variable Y2, bajo el vector de holgura H2, ETC. Una de las principales ventajas se puede inferir del teorema en cuestión ya que podremos encontrar la solución óptima de un problema con pocas variables y muchas restricciones, hallando la solución óptima del Dual con pocas restricciones.
Existen otros dos teoremas muy importantes que se pueden resumir como :
En cada par formado por una variable Primal y su correspondiente variable Dual, al menos una de ellas debe ser igual a cero(0).
Otro aspecto importante de resaltar es que cuando el problema Primal no es óptimo el Dual no es factible y viceversa. En general el problema Primal comienza siendo factible pero no óptimo y continua así hasta que se llegue a la solución óptima, es decir en el problema Primal se persigue llegar al óptimo mientras que el Dual se busca la factibilidad.
En cada iteración del SIMPLEX hallaremos una solución factible básica para el problema Primal, que corresponderá a una solución básica para el Dual; si la solución para el Primal no es óptima, al menos uno de los coeficientes en la función objetivo será negativo, por lo que la solución correspondiente al Dual no será factible, ya que al menos una de las variables básicas será negativa.
Esa solución básica no factible para el Dual será "más que óptima’ para él, aunque sea menos que óptima para el Primal, luego , a medida que apliquemos el SIMPLEX al Primal, moviéndonos a través de soluciones factibles básicas hasta llegar a la solución óptima, el Dual se mueve a través de soluciones no factibles" más que óptimas" hasta llegar a una solución factible, que por ende, será lógica.
Es posible obtener importante información económica acerca del valor de los recursos escasos que se utilizan examinando el problema Dual. (Ejm 16).
En efecto una interpretación económica de las variables duales se obtiene de la función objetivo dual. Como en la solución óptima el máximo valor de Zx es igual al mínimo de Zy, las variables duales Yi pueden ser interpretadas como la contribución unitaria del recurso i al valor de la función objetivo cuando las disponibilidades de recursos aumentan ( o disminuyen en una minimización ) por unidad ( el precio dual nos dirá que eso ocurre a razón de "N" Bs/unidad ). Es decir, cada una de las variables duales equivale a la utilidad adicional que puede obtenerse de una unidad adicional del recurso correspondiente. Desde el punto de vista de la toma de decisiones las variables duales indican la cantidad extra que se estaría en disponibilidad de pagar por unidad adicional de recurso específico ( independientemente de su valor real ). En otras palabras, estaríamos dispuestos a pagar un precio más elevado por un recurso escaso, hasta por el valor de la variable dual.
Siempre tendremos:
En un problema de Maximización....... Precio Dual en los Resultados = Variable Dual.
En un problema de Minimización ...... Precio Dual en los Resultados = - Variable Dual.
Otro importante aspecto económico que se sabe del problema, es lo referente a la columna de Costo Reducido, la cual, solo es significativa para las variables de decisión cuyo valor óptimo sea cero (Xi=0), la misma nos dice cuánto del costo por unidad de las variables, puede ser reducido sin que el valor óptimo de las variable se vuelva positivo.
Una vez que se ha obtenido la solución óptima de un problema de P.L. es muchas veces necesario realizar un Análisis de Sensibilidad, esto es, estudiar como cambia la solución del problema por cambios que se introduzcan en los distintos coeficientes del mismo. Los cambios en esos coeficientes pueden o no afectar la condición de Factibilidad (Xb >= 0) y la llamada condición de Optimalidad. Veamos:
Solo pueden afectar la factibilidad del problema Primal o, lo que es lo mismo, la "Optimalidad del Dual", es decir, puede ocurrir que alguna de las variables tomen un valor < 0 (solución no factible), en este caso se trataría de restablecer la factibilidad (por ejemplo usando el método Dual – Simplex).
Solo pueden afectar los coeficientes de la ecuación de Z y, por consiguiente, la optimalidad del Primal, que es equivalente a la factibilidad del Dual.
Para la resolución algebraica de cada caso existen ciertos algoritmo, en su mayoría parten de la forma matricial del Simplex (Simplex Revisado y Dual – Simplex). Como nos preocupa más su análisis que el proceso de resolución, lo haremos a través de la computadora.
Si la modificación es menor que el radio del entorno de variación, la solución óptima del momento permanece como única solución óptima del modelo.