Dualidad y Sensibilidad

Procedimientos

Revision del modelo se hacen los cambios deseados en el modelo que se va a investigar.

Revision de la tabla simplex final Observación de cambios en la tabla simplex final.

Conversion a la forma apropiada de eliminación de Gauss: se convierte esta tabla en la forma apropiada para identificar y evaluar la solucion basica actual.

Prueba de factibilidad: Se prueba la factibilidad de esta solucion mediante la verificacion de que todas las variables basicas de la columna del lado derecho aun tengan valores no negativos.

Prueba de optimalidad: Se verifica si esta solucion es optima (Factible), mediante la comprobacion de que todos los coeficientes de las variables no basicas de la function objetivo continuen no negativos.

Reoptimizacion: Si esta solucion no pasa una de las pruebas, se puede obtener (si se desea) la nueva solucion optima a partir de la tabla actual como tabla simplex inicial (con las conversiones necesarias) por el metodo simplex o el simplex dual.

Problema primal

Se convierte en

Problema Dual

Llevandose de ciertas caracteristicas:

La Funcion objetivo cambia al convertirse el problema en dual (si en el primal es max, en el dual es min, y viceversa).

Los coeficientes de la funcion objetivo del problema primal son los lados derechos de las restricciones funcionales del problema dual.

Los lados derechos de las restricciones funcionales del problema primal son los coeficientes de la funcion objetivo del problema dual.

Los coeficientes de una variable de las restricciones funcionales del problema primal son los coeficientes de una restriccion funcional del problema dual.

Se debe ajustar el modelo dual para poder ser resuelto, determinandose la forma de las restricciones (emplear el metodo CER).

Propiedades

Propiedad de dualidad debil: Si x es una slucion factible para el problema primal y Y es una slucion factible para el problema dual, entonces cx<=Yb.

Propiedad de dualidad fuerte: Si x* es una solucion optima para el problema primal y y* es una solucion optima para el dual, entonces cx* = Y*b.

Propiedad de soluciones complementarias: Se halla de manera simultanea una solucion FEV, x, en el problema primal, y una complementaria, y, para el dual, donde cx = Yb.

Propiedad de soluciones complementarias optimas: Se identifica de manera simultanea una solucion optima x* para el problema primal y una solucion optima complementaria Y* para el dual, donde cx* = Y*b.

Propiedad de simetria: En el caso de cualquier problema primal y su dual, las relaciones entre ellos deben ser simetricas debido a que el dual de este problema dual es este problema primal.

Subtema

Si un problema tiene soluciones factibles y una funcion objetivo acotada, entonces ocurre lo mismo con el otro problema (Se aplica propiedades de la dualidad debil y fuerte).

Si uno de los problemas tiene soluciones factibles y una funcion objetivo no acotada (no tiene solucion optima), entonces el otro problema no tiene soluciones factibles.

Si un problema no tiene soluciones factibles, entonces el otro problema no tiene soluciones factibles o la funcion objetivo es no acotada.

Minimizar W = yb

Sujeta a

yA >= c

y

y >= 0

Maximizar Z = cx

Sujeto a

Ax <= b

y

x >= 0

W = b1 y1 + b2 y2+ ... + bm ym, cada biyi puede interpretarse como la contribucion a la ganancia por disponer de bi unidades del recurso i en el problema primal. Asi la variable yi se interpreta como la contribucion a la ganancia por unidad del recurso i (i =1,1,...,m), cuando se usa el conjunto actual de variables basicas para obtener la solucion primal.