CÓMO FUNCIONA EL SIMPLEX Y ALGORITMO

CÓMO FUNCIONA EL SIMPLEX INVESTIGACIÓN DE OPERACIONES I DOCENTE: NATALIA BOHÓRQUEZYa estudiamos cómo resolver en forma gráfica problemas de programación lineal (PL) con dos o tres variables. Sinembargo la mayor parte de los PL de la vida cotidiana tiene muchas más variables. El algoritmo Simplex se usa pararesolver PL grandes que incluso pueden tener miles de restricciones y variables, lo cual es común en los modelos para laindustria. A continuación un ejemplo: Welch’s, Inc. es el procesador de uvas Concord y Niágara más grande del mundo, con ventas que sobrepasan 550 millones de dólares al año. Tales productos como la mermelada y el jugo de uva Welch han sido disfrutados por generaciones de consumidores estadounidenses. Cada septiembre, los agricultores comienzan a entregar sus cosechas a las plantas de procesamiento que después exprimen las uvas crudas para obtener jugo. Debe pasar un tiempo, antes de que el jugo esté listo para convertirlo en mermelada, jugos y concentrados. La decisión de cómo usar la cosecha de uva es una tarea compleja dada la demanda cambiante y la calidad y cantidad inciertas de la cosecha. Las decisiones típicas incluyen cuáles plantas deben usarse para elaborar los grupos de productos más importantes, la transferencia de jugo de uva entre las plantas de producción y el modo de transporte para esta transferencia. Debido a que Welch’s no tenía un sistema formal para optimizar el movimiento de materia prima y las plantas usadas para la producción, un equipo de IO desarrolló un modelo de programación lineal. Éste fue un modelo grande con 8000 variables de decisión que se enfocaba en el nivel de detalle de los componentes. Las pruebas a pequeña escala probaron que el modelo funcionaba. Para que el modelo fuera más útil, el equipo lo modificó agregando la demanda por grupo de productos en vez de por componentes individuales. Esto redujo su tamaño a 324 variables de decisión y 361 restricciones. Después el modelo se incorporó a una hoja de cálculo de Excel para darle solución. La compañía ha utilizado de manera continua la versión actualizada de este modelo de programación lineal cada mes desde 1994 para proporcionar a la alta administración información sobre el plan logístico generado por el Solver. Los ahorros por usar y optimizar este modelo fueron de aproximadamente 150000 dólares sólo en el primer año. Fuente: E.W. Schuster y S. J. Allen, “Raw Material Managementat Welch’s, Inc.”, en Interfaces, 28(5): 13-24, septiembre-octubre, 1998.El algoritmo Simplex primal fue desarrollado por el matemático norteamericano George Dantzig en 1947, y procedeexaminando vértices adyacentes de la región factible (recordar el teorema del punto extremo). En lugar de enumerartodas las soluciones posibles (puntos extremos o vértices) del modelo, el método Simplex resuelve sólo “algunas”de estas soluciones.En el método gráfico el espacio de soluciones es la intersección de los semiplanos querepresentan las restricciones, y en el método Simplex, el espacio de soluciones estárepresentado por m ecuaciones lineales simultáneas y n variables no negativas. Paratener alguna idea de la complejidad, a medida que crece el tamaño del modelo de PL,calculemos la cantidad MÁXIMA de vértices que puede tener un modelo con restricciones m=10 y variables n=20,utilizando la siguiente ecuación de combinaciones:ESCRIBA LAS IDEAS PRINCIPALES DE LO QUE ENTENDIÓ

Naturaleza iterativa del método simplex (Ejemplo tomado del libro Investigación de Operaciones de Hamdy Taha.) La figura muestra el espacio de soluciones del modelo de programación lineal Maximizar Z = 2X1 + 3X2 s.a. 2X1 + X2 ≤ 4 X1 + 2X2 ≤ 5 X1, X2 ≥ 0 Por lo común, el método simplex se inicia en el origen (punto A), donde X1 = 0, X2 = 0, y el valor objetivo, Z, es cero. La pregunta lógica es ¿un incremento en X1 y/o X2 (o ambas) por encima de sus valores actuales de cero puede mejorar (en este caso incrementar) el valor de Z?. Podemos responder esta pregunta investigando la función objetivo: Maximizar Z = 2X1 + 3X2 El diseño del método simplex no permite el incremento simultáneo de las variables,incrementa una a la vez. La variable que va a aumentar es la que tenga mayor grado de mejora en Z.En el ejemplo presente, el grado de mejora del valor de Z para X1 es de ___ unidades y para X2 de ___. Por lo tantoelegimos X2 para que crezca Z. La figura muestra que el valor de X2 debe incrementarse hasta que se llegue al punto deesquina B (recordemos que no llegar al punto extremo B no es una opción porque un candidato para el óptimo debeser un punto extremo). Luego, en el punto B, el método simplex incrementará el valor de X1 para llegar al punto extremomejorado C, el cual es el óptimo. Para este caso la trayectoria del algoritmo simplex es A B C.Cada punto de esquina a lo largo de la trayectoria está asociado con una iteración. Es importante hacer notar que elmétodo simplex se mueve a lo largo de los bordes del espacio de soluciones, lo cual significa que el método no puedecruzarlo, es decir, irse directamente de A  C.EJERCICIO 1. Considere el espacio de soluciones PL tridimensional que se muestra en la figura, cuyos puntos extremos factibles son A, B,…, y J. (a) ¿Cuáles de los siguientes pares de puntos de esquina no pueden representar iteraciones sucesivas del algoritmo Simplex: (A, B), (B, D), (E,H) y (A, I)? Explique la razón. (b) Suponga que las iteraciones simplex se inician en A y que el óptimo ocurre en H. Indique si alguna de las siguientes trayectorias son no legítimas para el algoritmo simplex, y explique la razón. a) ABGH b) AEIH c) ACEBADGH 2. Para el espacio de soluciones en la figura todas las restricciones son del tipo ≤, y todas las variables X1, X2 y X3 son no negativas. Suponga que s1, s2, s3 y s4 (≥ 0) son las holguras asociadas con las restricciones representadas por los planos CEIJF, BEIHG, DFJHG e IJH, respectivamente. Identifique las variables básicas y no básicas asociadas con cada punto extremo factible del espacio de soluciones.

ALGORITMO SIMPLEX- INVESTIGACIÓN DE OPERACIONES I DOCENTE: NATALIA BOHÓRQUEZ1. Estandarizar el modelo: consiste en transformar las restricciones y la función objetivo en igualdades.2. Obtener una solución factible básica (sfb) a partir de la estandarización (una sfb es un punto extremo).3. Determinar si la solución factible básica actual es óptima: TODOS LOS COEFICIENTES DEL RENGLÓN DE Z SONPOSITIVOS.4. Si la solución factible básica no es óptima (hay valores negativos), entonces determinar cuál variable no-básica sedebe transformar en variable básica y cuál variable básica se debe transformar en no-básica con el objeto de hallar unanueva solución factible básica con un mejor valor de la función objetivo Z.5. Aplicar Operaciones Elementales entre Renglones (OER) (recordar álgebra lineal) para encontrar una nueva soluciónfactible básica con el mejor valor de Z y regresar al paso 3.¿CÓMO ESTANDARIZAR EL MODELO DE PL?1. ESTANDARIZAR RESTRICCIONES (Casos A-B-C-D) X2 – X1 ≥ 1 A. Para lados derechos negativos Ejemplo: X1 – X2 ≤ -1 multiplicar por (-1) B. Para restricciones de ≤Se adiciona una variable de holgura Si en la restricción (la variable de holgura es la cantidad de recursossin usar en la restricción i-ésima). Y añadir al final la restricción de no negatividad para esa nueva variableSi ≥0. Ejemplo: X1 + X2 ≤ 40  X1 + X2 + S1 = 40 Z= c1X1 + c2X2 – MA1≥C. Para restricciones deSe utiliza el Método de la Gran M. En la restricción se adiciona una variable artificial Ai y se resta unavariable de superávit Si. También se resta MAi en la función objetivo. Y se añaden las restricciones de nonegatividad de Si ≥0, Ai ≥0. M es un número positivo muy grande. Ejemplo: X1 + X2 ≥ 20  X1 + X2 +A1 – S2 = 20D. Para restricciones de =Se utiliza el método de la gran M. Se adiciona en la restricción una variable artificial Ai y se resta MAi enla función objetivo. Y se añade la restricción Ai ≥0 Ejemplo: X1 + X2 = 10  X1 + X2 +A2 = 10 FUNCIÓN OBJETIVO Z= c1X1 + c2X2 – MA1 –MA22. ESTANDARIZAR FUNCIÓN OBJETIVO Z= c1X1 + c2X2 + … + cnXn  Z- c1X1 – c2X2 - … - cnXn = 0La función objetivo se debe transformar así:NOTA: antes de iniciar las iteraciones el simplex se deben eliminar todas las variables artificiales de la función objetivo con Operaciones Elementales entre Renglones (OER) del sistema de ecuaciones.

¿CÓMO CONSTRUIR LA TABLA INICIAL DEL SIMPLEX?La tabla inicial contiene el modelo estandarizado.FILAS: crear un renglón para los nombres de las variables, otro para la Z y otros renglones para cada una de lasrestricciones fundamentales del modelo (se excluyen las de no negatividad). En cada renglón, en la primera columna seubican las variables artificiales (Ai) y de holgura (Si) que se adicionaron para estandarizar el modelo, se coloca unavariable por cada restricción, si hay variable artificial y de holgura en la restricción se elige la artificial. Las variablesque están en esa primera columna son las Variables Básicas. En el renglón de Z va la función objetivo y en el resto derenglones van las restricciones estandarizadas del modelo, en un esquema similar al trabajado en Excel o en QM en elque solo se ponen los coeficientes.COLUMNAS: se adicionan todas las variables involucradas en el modelo, tanto las originales como las artificiales y deholgura que se tuvieron que adicionar.Variables básicas= toman valor en la solución.Las Variables No Básicas valen 0.BASE (LADO DERECHO COEFICIENTES RESTO DEL MODELO ESTANDARIZADO RESTRICCIONES) A1 S1 S2 S3Vb b (vector X1 X2(Variables recursos)básicas)ZA1S2S3Note que en la tabla inicial del Simplex las variables Xj no están en la Base, ya que todas valen 0 para iniciar el simplex en el origen. ¿CÓMO DETERMINAR QUÉ VARIABLE ENTRA Y QUÉ VARIABLE SALE DE LA BASE?3. Criterio para entrar a la base Es el mínimo valor en el renglón de Z (el más negativo / el que más se aleja del cero por la izquierda). Cuando haya empate entre las variables a entrar, se prefiere que entre la variable de decisión Xj sobre las artificiales y las de holgura. Cuando hay empate entre variables de la misma naturaleza el empate se rompe arbitrariamente.4. Criterio para salir de la base Es el mínimo de la división de la columna bi/ai (ai= los coeficientes de la columna de la variable que va a entrar a la base, exceptuando aquellos coeficientes negativos. El renglón de Z no entra en el concurso). Si hay empate entre las variables a salir de la base, se prefieren las artificiales, cuando el empate es entre variables de la misma naturaleza, se rompe arbitrariamente.5. Pivote: Valor en la intersección entre el renglón (variable que sale) y la columna (variable que entra). ¿CÓMO SE CALCULAN LOS DATOS DE LAS NUEVAS TABLAS?6. Columna variable que entra: se pone 1 en la posición pivote y cero en las demás posiciones.7. Renglón variable que sale: se pone 1 en el elemento pivote y el resto se recalcula dividiendo cada valor del renglón de la tabla anterior entre el pivote.8. Resto de posiciones: ������������ = ������������ − (���������1���������������������������������������������2) dn=dato nuevo da= dato antiguo P= Proyección en la columna pivote (horizontal) y en el renglón pivote (vertical)