• Author / Uploaded
• erick mauricio suarez sigg

Citation preview

Método Simplex de Dos Fases Karla Johanna Guevara Panamá, Isaura Melany Jingo Cevallos, Blanca Luciana Segovia Rosero, Facultad de Ingeniería en Ciencias Aplicadas Carrera de Ingeniería en Electrónica y Redes de la Comunicación Universidad Técnica del Norte Ibarra-Ecuador [email protected], [email protected], [email protected]

Resumen- Este documento explica el método simplex de dos fases que consiste en una estrategia algorítmica que se aplica cuando luego de llevar un modelo de programación lineal a su forma estándar no se dispone de una solución básica factible inicial, examinando intervalos de factibilidad e intervalos de optimalidad. Análisis de dualidad, análisis de sensibilidad y modelos de programación lineal (MPL) primal y dual.

X1+X2 +X5 Xi>= 0i = 1, 2,3,4,5

=10

Donde X3 es variable de exceso y X4 y X5 son variables artificiales de la restricción 1 y 2 respectivamente. Luego estaos en condiciones de confeccionar la tabla inicial de la Fase I donde las variables auxiliares X4 y X5 tienen costo reducido igual a uno (dado sus respectivos coeficientes en la función objetivo de dicha fase).

Palabras Clave- fenómenos de electrización, carga eléctrica, aislantes, conductores. INTRODUCCIÓN En muchas ocasiones nos encontraremos con modelos donde el conjunto de soluciones factibles no consideran al origen como una de ellas, por lo cual sera imposible utilizar el método simplex Para este tipo de casos se han creado muchas metodologías que buscan resolver este tipo de problemáticas buscando la solución a través de diversos procesos. Una de estas alternativas es el método de las dos fases, el cual, como su nombre lo indica, trabaja por medio de 2 fases o procedimientos, con el objetivo de encontrar primeramente una solución factible inicial y después pasar a resolver el modelo a través del método simplex. Para utilizar este método se deber tener el modelo en su forma ampliada, las variables de decisión deben de ser reales y mayores a cero. [1] MÉTODO SIMPLEX DE DOS FACES

El Método Simplex de Dos Fases permite abordar la resolución de aquellos modelos de Programación Lineal que luego de ser llevados a su forma estándar no permite obtener una solución básica factible inicial en las variables del modelo. Para enfrentar esta situación existen distintas estrategias algorítmicas entre las que destacan el Método Simplex de Dos Fases y el Método de la M Grande, las cuales suelen ser discutidas en cursos de Investigación Operativa (Investigación de Operaciones). En el siguiente artículo nos concentraremos en el análisis de la primera alternativa a través de un enfoque teórico – práctico. Ejemplo Método Simplex de Dos Fases Considere el MPL usando el Método Simplex de Dos Fases. Max Z = X1+3X2 S.A. X1-X2 ≤ -2 X1+X2 = 10 X1,X2 ≥ 0 Fase I (Método Simplex de Dos Fases) En este caso resulta conveniente multiplicar por -1 la primera restricción de modo que el lado derecho sea positivo, lo cual tiene como efecto adicional que cambia el sentido de la desigualdad. En consecuencia el problema que define la Fase I del Método Simplex de Dos Fases es: MIN X4+X5 S.A. -X1+X2-X3+X4

=2

Tabla 1 A continuación se llevan a cero los costos reducidos de X4 y X5. Para ello se realizan operaciones filas, por ejemplo, primero multiplicando por -1 la fila 1 y sumándola a la fila 3, para luego multiplicar por -1 la fila 2 y sumarla a la fila 3.

Tabla 2 Notar ahora que las variables básicas son X4 y X5 y las variables no básicas son X1, X2 y X3. Entre las variables no básicas la que tiene costo reducido negativo es X2, por tanto dicha variable entra a la Base y mediante el criterio de factibilidad o mínimo cuociente se determina aquella variable básica que deja la base. Esto se obtiene de Min{2/1; 10/1}=2. Por tanto X4 sale de la base y se realiza una iteración.

Tabla 3 Luego de concluir la iteración se dispone ahora de dos variables no básicas con costo reducido negativo: X1 y X3. Teniendo en consideración un criterio de rapidez de convergencia se privilegia la entrada a la base de X1 al tener ésta el costo reducido más negativo. La variable básica que deja la base se obtiene de Min{8/2}=4, determinando que X5 sale de la base. Para actualizar la tabla sumamos la fila 2 a la fila 3 (de modo que el costo reducido de X1 se transforme en cero) y luego multiplicamos por 1/2 la fila 2 y la sumamos a la fila 1 (para que de esta forma X1 sea básica asociada a la fila 2, tomando la estructura de la variable básica saliente X5).

Por tanto se concluye la Fase II del Método Simplex de Dos Fases con solución óptima X1=0, X2=10 y X3=8 y valor óptimo V(P)=30. [2] Tabla 5 Se verifica que se concluye la Fase I del Método Simplex de Dos Fases. Esta situación se detecta cuando se dispone de una solución básica que satisface las condiciones de no negatividad, donde las variables no básicas tienen costos reducidos mayores o iguales a cero y el valor de la función objetivo es igual a cero. Fase II (Método Simplex de Dos Fases) A continuación se da inicio a la Fase II del Método Simplex de Dos Fases. En esta etapa se elimina las columnas asociadas a las variables auxiliares utilizadas en la Fase I del método (en el ejemplo las variables X4 y X5) y se actualiza el vector de costos reducidos considerando la función objetivo del problema original en formato de minimización, esto es MIN -X1–3X2.

Tabla 5 Cabe recordar que las variables básicas finalizadas la Fase I son X2 y X1 y luego de la actualización de la fila de costos reducidos (fila 3) será necesario llevar sus respectivos costos reducidos a cero, para lo cual se suma la fila 2 a la fila 3 y luego se multiplica por 3 la fila 1 y se suma a la fila 3, obteniéndose lo siguiente:

Tabla 6 Del procedimiento anterior resulta que la variable no básica X3 tiene costo reducido y por tanto ingresa a la base. La variable básica que deja la base se obtiene de Min {4/1/2} =8 y por tanto X1 abandona la base. Con ello se realiza una iteración Del método obteniendo la siguiente tabla:

Tabla 7 Observar que la variable no básica X1 tiene costo reducido igual a 2 (que satisface las condiciones de no negatividad), además de enfrentarnos a una solución básica factible para X2 y X3.

III.

DUALIDAD

Todo problema de optimización (primal), tiene un problema asociado (dual) con numerosas propiedades que los relacionan y nos permiten hacer un mejor análisis de los problemas. La dualidad resulta de buscar relaciones que permitan obtener información adicional de un problema de optimización general. Esto en relaciones de programación lineal nos conduce a relaciones primal – dual. Esta relación consiste en que todo problema de optimización primal tiene un problema asociado dual. La teoría de la dualidad es importante, tanto desde el punto de vista teórico como del practico. [3] IV.

MODELO DE PROGRAMACIÓN LINEAL PRIMAL

Los cambios que se hacen en el modelo original de programación lineal afectan a los elementos de la tabla optima ´ actual (el que se tenga en el momento), que a su vez puede afectar la optimalidad y/o la factibilidad de la solución actual. Por esta razón estudiaremos como se recalculan los elementos de la tabla simplex optima ´ para reflejar los nuevos cambios. La relación entre el problema Dual y su asociado, es decir el problema original llamado primal, presenta varias utilidades como, por ejemplo: - Aporta elementos que aumentan sustancialmente la comprensión de la PL - El análisis de la dualidad es una herramienta útil en la solución de problemas de PL - El problema dual tiene interpretaciones e informaciones importantes. [3] V.

MODELO DE PROGRAMACIÓN LINEAL DUAL

El problema dual es una programación lineal definida en forma directa y sistemática a partir del modelo original (o primal) de programación lineal. Los dos problemas están relacionados en forma tan estrecha que la resolución optima ´ de un problema produce en forma automática la resolución optima del otro. El modelo dual se define para varias formas del primal, dependiendo del sentido de la optimización (maximización o mini-minimización) que se le vaya a dar, tipos de restricciones (≤, ≥ o =), y la orientación de las variables (no negativa o no restringida). Este tipo de tratamiento puede confundir por esta razón se presenta una sola definición que comprenda en forma

automática a todas las formas del primal. La definición del problema dual requiere expresar el problema primal en forma de ecuaciones, tal que todas las restricciones son ecuaciones, con lado derecho no negativo y todas las variables son no negativos. Este requisito es consistente con el formato de la tabla de inicio simplex. En consecuencia, todo resultado obtenido a partir de la solución primal optima se aplican en forma directa al problema dual asociado. [3] Para mostrar como se forma el problema dual, se define el primal en forma de ecuación así: Maximizar o minimizar = Esto está sujeto a:

Las variables xj, j = 1, 2, . . ., n, incluyen las variables excedentes, holguras y artificiales. La tabla 1 muestra cómo se construye el problema dual a partir del primal y se tiene que:

Ilustración 1. CONSTRUCCION DEL MODELO DUAL A PARTIR DEL MODELO PRIMAL La ilustración 2 indica las reglas para construir el modelo dual Las reglas para determinar el sentido de la optimización (maximización o minimización), el tipo de restricción (≤, ≥ o =), y el signo de las variables duales (siempre no restringido) se resumen en la siguiente tabla:

Ilustración 2. REGLAS PARA CONSTRUIR EL MODELO Nótese que el sentido de la optimización en el dual siempre es el opuesto al del primal. Una forma fácil de recordar el tipo de restricción (es decir, ≤ o ≥) en el dual es que si el objetivo del dual es minimización (es decir, “apunta hacia abajo”), las restricciones son todas del tipo ≥ (es decir, “apuntan hacia arriba”). Cuando el objetivo del dual es maximización lo contrario es válido. [3] Pasos

Para la resolución de este modelo los pasos a seguir son los siguientes: Si el primo es un problema de Maximización, el dual es un problema de Minimización y viceversa por lo cual: 1. Se define una variable dual por cada ecuación primal (restricción). 2. Se define una restricción dual por cada variable primal. 3. Los coeficientes de restricción (columna) de una variable primal definen los coeficientes en el lado izquierdo de la restricción dual, y su coeficiente objetivo define el lado derecho. 4. Los coeficientes objetivo del dual son iguales al lado derecho de las ecuaciones de restricción primal como en la tabla que se muestra en la parte superior. 5. Se procede de la misma manera que en el método simplex VI.

TEOREMAS

TEOREMA DE DUALIDAD DÉBIL: En general, el valor de cualquier solución factible del problema de minimización provee una cota superior del valor óptimo del problema de maximización. Análogamente, el valor de la función objetivo de cualquier solución factible del problema de maximización es una cota inferior del valor óptimo del problema de minimización. TEOREMA DE DUALIDAD FUERTE: En el óptimo el valor de la función objetivo del problema primal será igual al valor de la función objetivo del problema dual evaluada en la solución dual óptima. Si el problema primal es no acotado, entonces el dual es infectable. Alternativamente si el problema primal es infactible, entonces el dual es no acotado. COMPLEMENTARIAS: Una variable en el primal está asociada a una restricción en el dual (y viceversa). En este sentido si en el primal existe una variable no básica (valor igual a cero), en el dual la restricción asociado no está activa, es decir, no se cumple en igualdad. Análogamente, si la variable es básica en el primal, la restricción asociada en el dual se cumple en igualdad. Este resultado teórico es útil toda vez que simplifica la forma de obtener la solución óptima dado que como en un problema lineal la solución óptima (en caso de existir) está en un vértice, esto implica resolver un sistema de ecuaciones (con restricciones de igualdad). [4] VII.

USO DEL SOFTWARE PARA DUALIDAD WinQSB

Para la solución de problemas en WinQSB se procede de la misma manera que con los anteriores problemas que se resuelven. Planteando desde un principio el tema, el número de variables y la función a realizar en este caso si el problema es de maximizar o minimizar. Como es de conocimiento nuestro resolvemos el problema por medio del método simplex del programa para así tener de forma rápido los resultados del problema. Al resolver el simplex, daremos un clic sobre la ficha de “Results” donde podemos observar las opciones para el análisis de sensibilidad para la función objetivo y para la función sombra Al dar clic sobre el análisis de la función objetivo, se despliegan las variables de decisión y los cambios posibles de ellas y de igual manera se da para la función sombra, etc. También hay que señalar que existe la herramienta de reporte combinado, en la cual despliega los cambios posibles en una misma tabla. VIII.

ANÁLISIS DE SENSIBILIDAD

Intervalo de factibilidad. Es el intervalo de variabilidad de un lado derecho de una restricción. Procedimiento para el análisis de sensibilidad: Revisión del modelo. Revisión de la tabla simplex final. Conversión a la forma apropiada. Prueba de factibilidad. Prueba de optimalidad. Re optimización. Ejercicio1: Una empresa que se dedica a la fabricación de dos tipos de correas económicas una de cuero y otra de lona, da a conocer la ganancia máxima que se obtiene de la producción de las dos clases de correas, la ganancia de una correa de cuero es de 4 dólares y la de lona es de 6 dólares. Se cuenta con una disponibilidad de 120 horas para la producción y 100h para la inspección y empaque. Una correa de cuero requiere 2h de producción y 2h de empaque. Una correa de lona requiere 4h de producción y 3h de empaque[5].

El análisis de sensibilidad consiste en determinar cuál es el rango de variación de los parámetros del problema de modo que la base óptima encontrada siga siendo óptima. El objetivo es identificar los parámetros sensibles. Por ejemplo, los parámetros cuyos valores no pueden cambiar sin que cambie la solución óptima. Es importante porque nos permite investigar el efecto que tendría la solución óptima proporcionada por el método simplex en el hecho de que los parámetros (datos de entrada) tomaran otros valores posibles [5].

Variables X1= correas de cuero X2=correas de lona

Mediante el análisis de sensibilidad pueden existir diferentes tipos de cambios en el modelo original como:

Paso1 Construir las restricciones y función objetivo igualándola a cero, con sus respectivas variables de holgura. Z-4X1-6X2+OS1+OS2=0 R1 2X1+4X2+S1 +OS2