Ingenieria Economica

INTRODUCCIÓN

El método simplex se aplica a los problemas que tienen factibilidad dual inicial, es decir, que son óptimos pero infactibles simples.

Un problema se puede resolver por el método dual-simplex, cuando después de igualar a cero la función objetivo y convertir las restricciones en ecuaciones, agregando las variables de holgura necesarias, al menos uno, cualquiera de los elementos del vector b (vector de disponibilidades) es negativo y la condición de optimalidad se satisface.

El método simplex es un algoritmo iterativo que iniciando en una solución básica factible pero no óptima, genera soluciones básicas factibles cada vez mejores hasta encontrar la solución óptima (sí esta existe). Nótese que la base de su lógica es mantener la factibilidad, mientras busca la optimalidad. Pero surge la posibilidad de usar otro esquema igualmente iterativo, que como contraparte del simplex, comienza en una solución básica óptima, pero no factible y mantiene la inmejorabilidad mientras busca la factibilidad. Con este procedimiento se llega igualmente a la solución óptima.

El nuevo algoritmo fue desarrollo en 1954 por C. E. Lemke y se conoce con el nombre de Método Dual-Simplex. A continuación se presenta su estructura y un ejemplo para ilustrar su aplicación.

OBJETIVO

Presentar la estrategia del método Dual-Simplex para la solución de modelos de Programación Lineal.

MÉTODO SIMPLEX DUAL Y SUS VARIABLES

El método dual simplex se presenta para hallar el valor mínimo de una función objetiva lineal sometida a restricciones lineales.

Un comparativo entre el método simplex y el método dual-simplex

El método dual-simplex requiere de la aplicación de dos criterios para su solución:

El criterio de optimalidad que asegura que la solución permanecerá óptima todo el tiempo.

el criterio de factibilidad que forza las soluciones básicas hacia el espacio factible. Criterio de Factibilidad.

La variable saliente será aquella variable básica que tenga el valor más negativo en el vector bi.

Si todas las variables básicas son positivas o sea ³0 se tiene la solución final, óptima y factible.

Criterio de optimalidad. La variable entrante se selecciona de entre las variables no-básicas como sigue:

Dividir los coeficientes de la ecuación cero entre los coeficientes de la ecuación asociada con la variable saliente, ignorando denominadores positivos y/oceros. La variable entrante será aquella cuyo cociente sea el menor, si el problema es de minimizar, ó el de menor valor absoluto si es de maximizar. Si todos los denominadores son ³0, el problema no tendrá solución factible.

IMPORTANCIA DE LA DUALIDAD EN PROGRAMACIÓN LINEAL

La resolución de los problemas duales respecto a los primales se justifica dada la facilidad que se presenta dados problemas donde el número de restricciones supere al número de variables. Además de tener gran aplicación en el análisis económico del problema.

Otra de las ventajas que presenta es que dado a que el número de restricciones y variables entre problema dual y primal es inverso, se pueden resolver gráficamente problemas que presenten dos restricciones sin importar el número de variables.

EJEMPLOS

PROBLEMA DE MINIMIZACIÓN

Considere el siguiente modelo de PL y determine su solución por el método dual-simplex.

Minimizar. Z= 2X1 + X2

S.A.

3X1 +X2 = 3

4X1 +3X2 =6

X1 +2X2 = 3

X1=0, X2=0, X3=0

Igualando a cero la función objetivo y agregando las variables de holgura para obtener ecuaciones de restricción.

Minimizar. Z-2X1 - X2 = 0

S.A.

-3X1 -X2 +X3 =-3

...