Teoría de Dualidad
 

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.

Análisis de Sensibilidad.

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:

CAMBIOS EN EL SEGUNDO MIEMBRO DE LAS RESTRICCIONES.

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).

CAMBIOS EN LOS COEFICIENTES DE LA FUNCION OBJETIVO.

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.

Resolución por Computador
  1. El programa requiere que todas las variables sean NO NEGATIVAS, debido a esto, las modificaciones que se ameriten, deben ser hechas antes de ingresar los datos al programa.
  2. Todas las Variables de las restricciones deben aparecer en el primer miembro, en tanto que todos los términos constantes aparecerán a la derecha.
  3. En la columna de holgura o superfluas vienen los resultados de esas variables (por restriccion), las de valor cero indicarán que son restricciones activas y las de valor positivo restricciones inactivas.
  4. El número de variables positivas (DECISION + HOLGURA) al finalizar el Simplex deben ser igual al número de restricciones, de lo contrario el problema es Degenerado.
  5. El Precio Dual para la restricción n muestra la mejoría del valor óptimo de Z cuando el segundo miembro de la restricción aumenta una unidad, con los demás datos fijos. Si se observa el vector de Disponibilidad de Recursos se tendrá un rango admisible para la restricción que nos indica que por cada unidad que se aumente, la mejoría en la función objetivo será igual al Precio Dual.
  6. Pequeños cambios en una restricción inactiva no afectan a Z, por lo que su Precio Dual será siempre CERO.
  7. La información de sensibilidad del vector de Disponibilidad de Recursos NO nos dice cuanto valdrán las Variables de Decisión, solo nos dice como cambia la Función Objetivo.
  8. La solución óptima permanece vigente en tanto el incremento (disminución) de un coeficiente, en la función objetivo, de cierta variable no se exceda del intervalo de rangos de los coeficientes para esa variable, mientras los demás datos se conservan constantes.
  9. 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.

  10. El cambio en los coeficientes de la Función Objetivo altera la pendiente de los contornos de ésta, esto puede afectar o no, a la solución óptima de la Función Objetivo.
  11. En un modelo de Maximización el aumento en la reditualibilidad de una actividad, conservando inveriables los demás datos, NO puede aumentar el nivel óptimo de dicha actividad.
  12. En un modelo de Minimizacion el aumento en el costo de una actividad conservando invariable los demás datos, NO puede aumentar el nivel óptimo de la Función Objetivo.
  13. Si el coeficiente es aumentado hasta la frontera del entorno de variación, habrá una solución óptima alterna con un valor óptimo mejor ( Mayor en MAX y menor en MIN).
  14. Si el Coeficiente es disminuido hasta la otra frontera, habrá una solución alterna en el que la variable afectada tendrá un valor óptimo desmejorado.
  15. Si una de las fronteras es cero se sabe que hay por lo menos una solución óptima alterna para el problema que se está manejando. Por ejemplo, que la función de contorno sea paralela a una de las restricciones activas. El algoritmo que emplea la computadora para resolver el problema encontrará sólo uno de los vértices como solución óptima.
  16. Entenderemos por Costo Reducido de cualquier variable de decisión a:
  1. Cantidad en que debe cambiar el coeficiente de esa variable en la función objetivo para tener un valor óptimo positivo para esa variable (Si una variable es ya positiva en el punto óptimo, su costo reducido será cero).
  2. Tasa de decrecimiento de la función objetivo en cuanto una variable que es cero en el punto óptimo, es forzada inicialmente a ser positiva.
  1. Para una solución degenerada las señales dadas para la alternativa óptima deben pasarse por alto y mientras el coeficiente de una función objetivo varíe dentro del rango indicado, la solución óptima no cambiará, incluso, es factible que cambie por encima de los valores admisibles sin modificarse el valor óptimo.
Resumiendo Tenemos
  1. La solución del problema vendrá dada por los valores óptimos de las variables que aparecen en la columna ACTIVITY LEVEL con un Valor Optimo de Z. en VALUE OBJECTIVE FUNCTION.
  2. El Significado de las Variables de Holgura diferentes de cero representan normalmente la cantidad sin uso de los recursos (caso <= ) o el exceso de suministros ( caso >=). En caso de ser Cero, indican que el recurso se usa todo (caso <=) o que la mezcla óptima tendrá exactamente esa cantidad para satisfacer determinado requerimiento. Aparecen en la columna de SLACK OR SURPLUS y las que sean CERO nos señalaran las RESTRICCIONES ACTIVAS.
  3. Para mejorar el V.O. debemos modificar los RECURSOS o REQUERIMIENTOS (bi) que intervienen en las restricciones de holgura cero. Para saber cuales, analizamos la columna de SHADOW PRICES, la cual nos da la Razón de Mejora de la FUNCION OBJETIVO cuando el Vector Disponibilidad de Recursos (Requerimientos) es aumento (disminuido) unitariamente. Para saber CUANTO podemos, debemos analizar el Rango del Vector de Disponibilidad de la Restricción escogida, que se consigue en CONSTRAINT ALLOWED INTERVAL.
  4. Para saber cuanto mejorará, multiplicamos la cantidad que puede cambiar por el precio dual correspondiente (SHADOW PRICES).
  5. En caso de querer empeorarla, se haría lo contrario al punto anterior.
  6. Si cambiamos los COEFICIENTES DE LA FUNCION OBJETIVO pueden suceder 3 cosas:
  1. Si lo hacemos dentro del intervalo permitido, el cual se puede ver en la columna VARIABLE ALLOWED INTERVAL, no influirá en la Mezcla Optima, alterándose el V.O, aumentado su valor original en el producto del INCREMENTO POR EL VALOR DE LA VARIABLE BASICA CORRESPONDIENTE.
  2. Si lo hacemos hasta el límite de los intervalos, aparecen soluciones óptimas alternativas.
  3. Si lo hacemos más allá del entorno, puede suceder cualquier cosa.
 
  1. Finalmente, si queremos que una variable entre como BASICA, es decir, que resulte una decisión óptima su uso, debemos analizar la columna del Costo Reducido, REDUCED COST, que es solo significativa para las variable de decisión cuyos valores óptimos sean cero. Dicho valor, nos dirá cuanto puede ser modificado (aumentado o disminuido, según el caso) sin que el valor óptimo de la variable se vuelva positivo, si excede esa cantidad, habrá una solución óptima con dicha variable mayor que cero.
 Copyright Daniel Redondo