Metodo Dual Simplex
Páginas: 7 (1750 palabras)
Publicado: 29 de octubre de 2012
EL MÉTODO DUAL SIMPLEX
El método simplex dual resulta ser una estrategia algorítmica eficiente cuando luego de llevar un modelo de programación lineal a su forma estándar, la aplicación del método simplex no es inmediata o más bien compleja. También es un algoritmo iterativo que iniciando en una solución básica factible pero no óptima, genera soluciones básicas factibles cada vez mejores hastaencontrar 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 llegaigualmente a la solución óptima.
Fue desarrollo en 1954 por C. E. Lemke y se conoce con el nombre de Método Dual-Simplex.
ALGORITMO DUAL-SIMPLEX PARA UN MODELO DE MAXIMIZACIÓN
Primero se debe expresar el modelo en formato estándar, agregando las variables de holgura y de exceso que se requieran. Enseguida, en las ecuaciones que tengan variables de exceso (resultantes de restricciones de tipo >), sedebe multiplicar por (-1) en ambos lados, para hacer positivo el coeficiente de la variable de exceso, y formar así un vector unitario que nos permita tomar esta variable de exceso como una variable básica inicial. Sin necesidad de agregar una variable artificial en esa restricción.
Al hacer lo anterior se logra que debajo de las variables básicas aparezca una matriz identidad, que es la que elsimplex siempre toma como base inicial.
Obtendremos que los términos del lado derecho de las ecuaciones multiplicadas por (-1) queden con signo negativo, lo cual hace que la solución inicial sea infactible.
Es importante destacar que este proceso es muy útil ya que en muchos modelos evita la inclusión de variables artificiales en el momento de transformar un modelo a formato estándar
Elalgoritmo para resolver un modelo de maximización es el siguiente:
1: Hallar una solución básica inicial infactible e inmejorable.
Escribir el tablero inicial tomando a las variables de holgura y de exceso como variables básicas iniciales.
2: Prueba de factibilidad.
Si todas las variables básicas son no negativas, la actual solución es la óptima.
Si hay al menos una variable básica negativa,seleccionar como variable de salida, (llamémosla (XB) s), a aquella con el valor mas negativo. Los empates se pueden romper arbitrariamente.
3: Prueba de inmejorabilidad
Sí en el renglón de la variable básica de salida (XB)s todos los coeficientes de reemplazo con las variables no básicas son no negativos, la solución del modelo es óptima ¡limitada. Se termina el proceso.
Si en el renglónde la variable básica de salida (XB)s, hay al menos un coeficiente de intercambio negativo , se efectúan los cocientes entre el efecto neto de cada variable no básicas y su correspondiente coeficiente de intercambio negativo.
Es decir, siendo (XB) s la variable de salida se calculan todos los cocientes
Se toma como variable de entrada (llamémosla Xe) a aquella que corresponda al mínimo delos cocientes del anterior conjunto.
Si la variable de entrada es Xe el elemento pivote será el elemento (Se)s
El empate se puede romper arbitrariamente
Aplicar la operación de pivoteo para generar la nueva tabla, en la cual aparezca Xe como variable básica en lugar de la variable de salida (XB)s
Repetir el algoritmo a partir del paso 2.
1- EJEMPLO DE APLICACIÓN DEL MÉTODO DUALSIMPLEX
Sea el siguiente modelo:
Maximizar Z= -2X1 -2X2 -3X3
Sujeto a : 2X1 +4X2 +2X3 > 10
3X1 -3X2 +9X3 = 12
con X1, X2, X3 > 0
Expresemos el modelo en formato estándar
Maximizar Z= -2X1 -2X2 -3X3
Sujeto a : 2X1 +4X2 +2X3 -IE1 = 10
3X1 -3X2 +9X3 -IE2 = 12
Multipliquemos por (-1) en ambos lados de las ecuaciones, para formar los vectores unitarios,...
El método simplex dual resulta ser una estrategia algorítmica eficiente cuando luego de llevar un modelo de programación lineal a su forma estándar, la aplicación del método simplex no es inmediata o más bien compleja. También es un algoritmo iterativo que iniciando en una solución básica factible pero no óptima, genera soluciones básicas factibles cada vez mejores hastaencontrar 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 llegaigualmente a la solución óptima.
Fue desarrollo en 1954 por C. E. Lemke y se conoce con el nombre de Método Dual-Simplex.
ALGORITMO DUAL-SIMPLEX PARA UN MODELO DE MAXIMIZACIÓN
Primero se debe expresar el modelo en formato estándar, agregando las variables de holgura y de exceso que se requieran. Enseguida, en las ecuaciones que tengan variables de exceso (resultantes de restricciones de tipo >), sedebe multiplicar por (-1) en ambos lados, para hacer positivo el coeficiente de la variable de exceso, y formar así un vector unitario que nos permita tomar esta variable de exceso como una variable básica inicial. Sin necesidad de agregar una variable artificial en esa restricción.
Al hacer lo anterior se logra que debajo de las variables básicas aparezca una matriz identidad, que es la que elsimplex siempre toma como base inicial.
Obtendremos que los términos del lado derecho de las ecuaciones multiplicadas por (-1) queden con signo negativo, lo cual hace que la solución inicial sea infactible.
Es importante destacar que este proceso es muy útil ya que en muchos modelos evita la inclusión de variables artificiales en el momento de transformar un modelo a formato estándar
Elalgoritmo para resolver un modelo de maximización es el siguiente:
1: Hallar una solución básica inicial infactible e inmejorable.
Escribir el tablero inicial tomando a las variables de holgura y de exceso como variables básicas iniciales.
2: Prueba de factibilidad.
Si todas las variables básicas son no negativas, la actual solución es la óptima.
Si hay al menos una variable básica negativa,seleccionar como variable de salida, (llamémosla (XB) s), a aquella con el valor mas negativo. Los empates se pueden romper arbitrariamente.
3: Prueba de inmejorabilidad
Sí en el renglón de la variable básica de salida (XB)s todos los coeficientes de reemplazo con las variables no básicas son no negativos, la solución del modelo es óptima ¡limitada. Se termina el proceso.
Si en el renglónde la variable básica de salida (XB)s, hay al menos un coeficiente de intercambio negativo , se efectúan los cocientes entre el efecto neto de cada variable no básicas y su correspondiente coeficiente de intercambio negativo.
Es decir, siendo (XB) s la variable de salida se calculan todos los cocientes
Se toma como variable de entrada (llamémosla Xe) a aquella que corresponda al mínimo delos cocientes del anterior conjunto.
Si la variable de entrada es Xe el elemento pivote será el elemento (Se)s
El empate se puede romper arbitrariamente
Aplicar la operación de pivoteo para generar la nueva tabla, en la cual aparezca Xe como variable básica en lugar de la variable de salida (XB)s
Repetir el algoritmo a partir del paso 2.
1- EJEMPLO DE APLICACIÓN DEL MÉTODO DUALSIMPLEX
Sea el siguiente modelo:
Maximizar Z= -2X1 -2X2 -3X3
Sujeto a : 2X1 +4X2 +2X3 > 10
3X1 -3X2 +9X3 = 12
con X1, X2, X3 > 0
Expresemos el modelo en formato estándar
Maximizar Z= -2X1 -2X2 -3X3
Sujeto a : 2X1 +4X2 +2X3 -IE1 = 10
3X1 -3X2 +9X3 -IE2 = 12
Multipliquemos por (-1) en ambos lados de las ecuaciones, para formar los vectores unitarios,...
Leer documento completo
Regístrate para leer el documento completo.