Método Simplex Dual

MÉTODO SIMPLEXDUAL

¿En qué consiste?

El método simplex dual ofrece una alternativa algorítmica para la resolución de modelos de Programación Lineal. Este modelo se puede utilizar cuando luego de llevar a la forma estándar de un modelo de programación lineal no se dispone de una solución básica factible inicial con la cual se puede dar nicio a las iteracionesa del algoritmo. Además este método se aplica a problemas infactibles. En esos casos las restriciciones se exprean en forma canónica.

¿Qué ocurre con la función Objetivo?

La función objetivo puede estar en la forma de maximización o minimización.

La variable de holgura

Luego de asignar las variables de holgura y realizar la tabla, si algún elemento del lado derecho es negativo y si la condición de optimidad está satisfecha, el problema puede resolverse por el metedo dual simplex.

Nota

Si un elemento es negativo del lado derecho significa que el problema comienza óptimo pero de manera infactible como se requiere en el método simplex dual. En la iteración donde la solución básica llega a ser factible esta se convertirá en la solución óptima del problema.

MÉTODO SIMPLEXDUAL

Condición de Factibilidad y Optimidad

La variable la básica es la que sale y tiene el valor más negativo La variable que entra se elige entre las variables básicas tomando los cocientes entre la función objetivo y la variable que sale. Algo importante es que se ignoran por completo los valores positivos incluyendo el 0. En caso de que los valores sean positivos o 0, el problema no tiene ninguna solucion factible

Diferencias entre Simplex y Dual Simplex

Algunas ventajas del Método Simplex Dual

* Permite resolver problemas de programación lineal de manera sencilla y rápida. * Es una alternativa para resolver un problema de programación lineal. * El número de restricciones y variables entre el problema dual y el primal es inverso, se pueden resolver gráficamente problemas que presenten 2 restricciones sin importar el número de variables.

MÉTODO SIMPLEXDUAL

El método de solución para problemas de maximización se aplica por medio de las reglas de equizalencia Min (Z) = Max (-Z). Método Dual-Simplex empieza con una solución óptima, pero no factible. La cual se hace óptima mediante iteraciones que mejoran su factibilidad conservando su optimalidad.

EJEMPLO SIMPLEX DUAL

La función óptima es: Las restricciones son:

1) Se convierte el problema de minimización en maximización. La función objetivo y las restricciones se multiplican por -1.

MÉTODO SIMPLEXDUAL

EJEMPLO SIMPLEX DUAL

2) En cuanto a la función objetivo se la convierte en ecuación. Y por otra en las restricciones se convierten las inecuaciones en ecuaciones.

3) Determinar las variables básicas y no básicas. 4) Elaborar la tabla inicial simplex.

5) Determinar la variable que sale (fila pivote)El cual se encuentra dado por el número más negativo de la solución de las restricciones. fila de S2. 6) Determinar la variable que entra (columna pivote) Razón = Coeficiente de Z / coeficiente fila pivote Razón Mayor = Columna X2 (-12 / 2)

MÉTODO SIMPLEXDUAL

EJEMPLO SIMPLEX DUAL

7) Elaborar una nueva tabla Simplex a) Nueva fila pivote = Fila pivote / elemento pivote b) Nuevas filas = fila anterior - coeficiente de columna pivote x nueva fila pivote

La nueva Tabla Simplex es la siguiente: 8) Se realizan nuevamente del 5 al 7 obteniendo como solución final:

NOTA: No hay más iteraciones cuando no existan soluciones con coeficientes negativos. R// El valor mínimo se alcanza para para Adicional a este ejemplo se anexa un ejemplo con un video de youtube.

Fuente del ejercicio: Hiller, Frederick. "Introducción a la investigación de Operaciones". Editorial Mc. Graw Hill. México, 1997 Pág. 265