Investigar sobre; ¿quién y cuándo se propuso el método simplex para la resolución de problemas de programación lineal? ¿Y en qué casos de aplica este método, cite ejemplos?
METODO SIMPLEX El método Simplex: es un procedimiento algebraico, sus conceptos fundamentales son geométricos, por lo que la comprensión de estos conceptos geométricos nos proporciona una fuerte intuición sobre como opera el método Simplex y porque es tan eficiente y tambien, es un algoritmo que parte de una solución básica posible y encuentra otra que mejora el valor de la función objetivo. Este procedimiento se repite hasta que se alcanza el óptimo, si éste existe, o se arriba a una condición de final anormal. Quien invento el método simplex: este método fue inventado por GEORGE DANTZING en 1947. Cuando se aplicó dicho método: la primera formulación del método simplex fue en el verano de 1947, lel primer problema practico que se resolvió fue uno de nutrición, la primera implementación computacional del Método Simplex es el año 1952 para un problema de 71 variables y 48 ecuaciones. Su resolución tarda 18 horas. Luego, en 1956, un código llamado RSLP1, implementado en un IBM con 4Kb en RAM, admite la resolución de modelos con 255 restricciones. Donde se aplica dicho método: la aplicación del método simplex se utiliza cuando el problema es de tamaño suficientemente grande, también esta diseñado en la programación lineal cuando la matriz tiene propiedad de diseminación y esta relacionado en diversas clases especiales de poblemas de programación lineal (problemas de bosques , problemas de transporte y otros). EJEMPLO: Max 40*X1 + 60*X2 s.a. 2*X1 + 1*X2 <= 70 1*X1 + 1*X2 <= 40 1*X1 + 3*X2 <= 90 X1 >= 0 X2 >= 0 Para poder aplicar el Método Simplex, es necesario llevar el modelo a su formato estándar, para lo cual definimos X3, X4, X5 >= 0 como las respectivas variables de holgura para la restricción 1, 2 y 3. De esta forma queda definida la tabla inicial del método de la siguiente forma:
Luego, para escoger que variable básica deja la base debemos buscar el mínimo cuociente entre el lado derecho y los coeficientes asociados a la variable entrante en cada fila (para aquellos coeficientes > 0 marcados en rojo en la tabla anterior). El mínimo se alcanza en Min {70/1, 40/1, 90/3} = 30 asociado a la tercera fila, el cual corresponde a la variable básica actual X5, en consecuencia, X5 deja la base. En la posición que se alcanza el mínimo cuociente lo llamaremos "Pivote" (marcado con azul) el cual nos servirá para realizar las respectivas operaciones filas, logrando la siguiente tabla al cabo de una iteración.
La actual tabla no corresponde a la solución óptima del problema P) debido a que existe una variable no básica con costo reducido negativo, por tanto X1 entra a la base. Posteriormente, mediante el criterio del mínimo cuociente calculamos la variable que debe dejar la base: Min {40/(5/3), 10/(2/3), 30/(1/3)} = 15, asociado a la fila 2 (variable básica actual X4), por tanto X4 deja la base. Finalmente se alcanza la solución óptima del problema P) y se verifica que los costos reducidos asociados a las variables no básicas (X4 y X5 son mayores o iguals que cero). La solución alcanzada es X1* = 15, X2* = 25 con V(P*) = 2.100. Adicionalmente, los costos reducidos asociados a las variables no básicas definen el precio sombra asociado a las restricciones 1, 2 y 3, respectivamente, lo cual es equivalente a la obtención del precio sombra mediante el método gráfico, la forma de calcular el intervalo de variación para el lado derecho que permite la validez del precio sombra, utilizando la tabla final del Método Simplex.
El método Simplex es un procedimiento iterativo que permite mejorar la solución de la función objetivo en cada paso. El proceso concluye cuando no es posible continuar mejorando dicho valor, es decir, se ha alcanzado la solución óptima (el mayor o menor valor posible, según el caso, para el que se satisfacen todas las restricciones).
Partiendo del valor de la función objetivo en un punto cualquiera, el procedimiento consiste en buscar otro punto que mejore el valor anterior. Como se verá en el método Gráfico, dichos puntos son los vértices del polígono (o poliedro o polícoro, si el número de variables es mayor de 2) que constituye la región determinada por las restricciones a las que se encuentra sujeto el problema (llamada región factible). La búsqueda se realiza mediante desplazamientos por las aristas del polígono, desde el vértice actual hasta uno adyacente que mejore el valor de la función objetivo. Siempre que exista región factible, como su número de vértices y de aristas es finito, será posible encontrar la solución.
El método Simplex se basa en la siguiente propiedad: si la función objetivo Z no toma su valor máximo en el vértice A, entonces existe una arista que parte de A y a lo largo de la cual el valor de Z aumenta.
Será necesario tener en cuenta que el método Simplex únicamente trabaja con restricciones del problema cuyas inecuaciones sean del tipo "≤" (menor o igual) y sus coeficientes independientes sean mayores o iguales a 0. Por tanto habrá que estandarizar las restricciones para que cumplan estos requisitos antes de iniciar el algoritmo del Simplex. En caso de que después de éste proceso aparezcan restricciones del tipo "≥" (mayor o igual) o "=" (igualdad), o no se puedan cambiar, será necesario emplear otros métodos de resolución, siendo el más común el método de las Dos Fases.
Preparando el modelo para adaptarlo al método Simplex
La forma estándar del modelo de problema consta de una función objetivo sujeta a determinadas restricciones:
El objetivo consistirá en maximizar o minimizar el valor de la función objetivo (por ejemplo, incrementar ganancias o reducir pérdidas, respectivamente). Todas las restricciones deben ser ecuaciones de igualdad (identidades matemáticas). Todas las variables (xi) deben tener valor positivo o nulo (condición de no negatividad). Los términos independientes (bi) de cada ecuación deben ser no negativos. Hay que adaptar el problema modelado a la forma estándar para poder aplicar el algoritmo del Simplex.
QUIEN Y CUANDO SE INVENTO EL METODO SIMPLEX Este metodo fue inventado por George Dantzig en el 1947. La primera formulación del método simplex fue en el verano de 1947. El primer problema práctico que se resolvió con este método fue uno de nutrición.Es una técnica popular para dar soluciones numéricas del problema de la programación lineal. Es un método numérico para optimización de problemas libres multidimensionales perteneciente a la clase más general de algoritmos de búsqueda. Permite encontrar una solución óptima en un problema de maximización o minimización, buscando en los vértices del polígono. Es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución. Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución. Se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta.
MÉTODO SIMPLEX El Método Simplex es un método analítico de solución de problemas de programación lineal capaz de resolver modelos más complejos que los resueltos mediante el método gráfico sin restricción en el número de variables. El Método Simplex es un método iterativo que permite ir mejorando la solución en cada paso. La razón matemática de esta mejora radica en que el método consiste en caminar del vértice de un poliedro a un vértice vecino de manera que aumente o disminuya (según el contexto de la función objetivo, sea maximizar o minimizar). Quien invento el método simplex: Este método fue inventado por GEORGE DANTZING en 1947.La primera formulación del método simplex fue en el verano de 1947, del primer problema practico que se resolvió fue uno de nutrición, la primera implementación computacional del Método Simplex es el año 1952 para un problema de 71 variables y 48 ecuaciones. En qué caso se aplica El método simplex disminuye sistemáticamente un número infinito de soluciones hasta un número finito de soluciones básicas factibles. El método simplex utiliza el conocido procedimiento de eliminación en la solución de ecuaciones lineales de Gauss- Jordan y, además aplica los llamados criterios del simplex con los cuales se asegura mantener la búsqueda dentro de un conjunto de soluciones factibles al problema; así valora una función económica Z, exclusivamente en vértices FACTIBLES (posibles). Resolver el siguiente problema de Programación Lineal utilizando el Método Simplex: Max 40*X1 + 60*X2 s.a. 2*X1 + 1*X2 <= 70 1*X1 + 1*X2 <= 40 1*X1 + 3*X2 <= 90 X1 >= 0 X2 >= 0 Para poder aplicar el Método Simplex, es necesario llevar el modelo a su formato estándar, para lo cual definimos X3, X4, X5 >= 0 como las respectivas variables de holgura para la restricción 1, 2 y 3. De esta forma queda definida la tabla inicial del método de la siguiente forma: En esta situación, las variables de holgura definen una solución básica factible inicial, condición necesaria para la aplicación del método. Luego, se verifican los costos reducidos de las variables no básicas (X1 y X2 en la tabla inicial) y se escoge como variable que entra a la base aquella con el costo reducido "más negativo". En este caso, X2. X1 X2 X3 X4 X5 2 1 1 0 0 70 1 1 0 1 0 40 1 ..... 3 0 0 1 90 -40 -60 0 0 0 0
Luego, para escoger que variable básica deja la base debemos buscar el mínimo cociente entre el lado derecho y los coeficientes asociados a la variable entrante en cada fila (para aquellos coeficientes > 0 marcados en rojo en la tabla anterior). El mínimo se alcanza en Min {70/1, 40/1, 90/3} = 30 asociado a la tercera fila, el cual corresponde a la variable básica actual X5, en consecuencia, X5 deja la base. En la posición que se alcanza el mínimo cociente lo llamaremos "Pivote" (marcado con azul) el cual nos servirá para realizar las respectivas operaciones filas, logrando la siguiente tabla al cabo X1 X2 X3 X4 X5 5/3 0 1 0 -1/3 40 2/3 0 0 1 -1/3 10 1/3 1 0 0 1/3 30 -20 0 0 0 20 1.800 de una iteración.
La actual tabla no corresponde a la solución óptima del problema P) debido a que existe una variable no básica con costo reducido negativo, por tanto X1 entra a la base. Posteriormente, mediante el criterio del mínimo cociente calculamos la variable que debe dejar la base: Min {40/(5/3), 10/(2/3), 30/(1/3)} = 15, asociado a la fila 2 (variable básica actual X4), por tanto X4 deja la base. Obtenido lo anterior se aplica una iteración del método: X1 X2 X3 X4 X5 0 0 1 -5/2 1/2 15 1 0 0 3/2 -1/2 15 0 1 0 -1/2 1/2 25 0 0 0 30 10 2.100 Finalmente se alcanza la solución óptima del problema P) y se verifica que los costos reducidos asociados a las variables no básicas (X4 y X5 son mayores o igual que cero).
FORMA ESTÁNDAR DE UN MODELO DE PROGRAMACIÓN LINEAL
Consideremos un modelo de Programación Lineal en su forma estandar, que denotaremos en lo que sigue por:
Min c1x1 + c2x2 + ... + cnxn sa a11x1 + a12x2 + ... + a1nxn = b1 a21x1 + a22x2 + ... + a2nxn = b2 ... ... ... am1x1 + am2x2 + ... + amnxn = bm xi >= 0, i = 1, 2, ..., n y m <= n Matricialmente escrito como:
Min cTx s.a Ax = b x >= 0
No existe pérdida de generalidad en asumir que un modelo de PL viene dado en su forma estándar:
EJEMPLO P) Max 9u + 2v + 5z sa 4u + 3v + 6z <= 50 u + 2v - 3z >= 8 2u - 4v + z = 5 u,v >= 0 z e IR Siempre es posible llevar un problema de maximización a uno de minimización. Si f(x) es la función objetivo a maximizar y x* es la solución óptima f(x*) >= f(x), para todo x factible. -f(x*) <= - f(x), para todo x factible. En consecuencia: x* es también mínimo de -f(x) Cada restricción del tipo <= puede ser llevada a una ecuación de igualdad usando una (nueva) variable de holgura no negativa, con coeficiente nulo en la función objetivo. Cada restricción del tipo >= puede ser llevada a una ecuación de igualdad usando una (nueva) variable de exceso no negativa, con coeficiente nulo en la función objetivo. Siempre es posible escribir una variable libre de signo como la diferencia de dos variables no negativas. Considerando la siguiente notación: u = x1, v = x2, z = x3 - x4, s1 = x5 (holgura), s2 = x6 (exceso), el problema P) puede ser escrito en forma equivalente como:
¿Quién creo el método simplex? El método simplex fue creado por el matemático George Bernard Dantzig Ourisson ¿Cuándo se creó el método simplex? El método del simplex fue creado en 1947 por el matemático George Dantzig Origen del método simplex George Bernard Dantzig Ourisson nació el 8 de Noviembre de 1914 en Portland, en el estado de Oregon de los Estados Unidos de América. Hijo de Tobías Dantzig, matemático ruso, y Anja Ourisson, lingüista francesa especializada en idiomas eslavos, quienes emigraron a EEUU en 1910, después de casarse. George Bernard obtuvo su licenciatura en Matemáticas y Física en la Universidad de Maryland en 1936, su grado de máster en Matemáticas en la Universidad de Míchigan, y su doctorado en la Universidad de California, Berkeley en 1946. Recibió además un doctorado honorario de la Universidad de Maryland en 1976. Reconocido por desarrollar el método simplex y es considerado como el "padre de la programación lineal". Recibió muchos honores, tales como la Medalla Nacional de Ciencia en 1975 y el premio de Teoría John von Neumann en 1974. ¿Qué es el método simplex? Se refiere a un conjunto de métodos para resolver problemas de programación lineal, en los cuales se busca el máximo de una función lineal sobre un conjunto de variables que satisfaga un conjunto de inecuaciones lineales. ¿En qué caso se emplea el método simplex? Y cite ejemplos: Finanzas: el problema del inversor podría ser por ejemplo una selección de mix de su cartera de inversiones. El objetivo puede ser maximizar las ganancias totales cuando las ganancias de un producto determinado dependen del método de financiación. Por ejemplo, se puede financiar con fondos internos, con deuda a corto plazo o con financiación intermedia (créditos amortizados). Administración de Producción y Operaciones: muchas veces en las industrias de proceso, una materia prima en particular puede transformarse en una gran variedad de productos. Por ejemplo, en la industria petrolera, el crudo puede refinarse para producir nafta, kerosene, aceite para calefacciones y distintas clases de aceite para motor. Según el margen de ganancia actual de cada producto, el problema es determinar la cantidad que se debería fabricar de cada producto. Recursos Humanos: los problemas de planificación de personal también se pueden analizar con programación lineal. Por ejemplo, en la industria telefónica, la demanda de servicios de personal de instalación y reparación son estacionales. El problema es determinar la cantidad de personal de instalación y reparación de líneas que debemos tener incorporada en la fuerza laboral por cada mes a fin de minimizar los costos totales de contratación, despido, horas extras y salarios en horas ordinarias. Marketing: se puede utilizar la programación lineal para determinar el mix adecuado de medios de una campaña de publicidad. Por ejemplo que los medios disponibles son radio, televisión y diarios. El problema es determinar cuántos avisos hay que colocar en cada medio. Por supuesto que el costo de colocación de un aviso depende del medio elegido. El objetivo es minimizar el costo total de la campaña publicitaria, sujeto a una serie de restricciones. Distribución: otra aplicación es el área de la distribución. Por ejemplo una determinada fábrica podría realizar envíos a cualquier cantidad de depósitos. Dado el costo del envío de una unidad del producto de cada fábrica a cada depósito, el problema es determinar el patrón de envío (cantidad de unidades que cada fábrica envía a cada depósito) que minimice los costos totales.
George Bernard Dantzig Ourisson fue un profesor, físico y matemático estadounidense, reconocido por desarrollar el método simplex y es considerado como el "padre de la programación lineal".
Un hecho real en la vida de Dantzig dio origen a una famosa leyenda en 1939, cuando era un estudiante en Berkeley.
Al comienzo de una clase a la que Dantzig acudía con retraso, el profesor Jerzy Neyman escribió en la pizarra dos ejemplos famosos de problemas estadísticos aún no resueltos.
Al llegar Dantzig a clase, pensó que los dos problemas eran tarea para casa y los anotó en su cuaderno.
¿CUÁNDO SE PROPUSO EL METODO SIMPLEX?
En 1947 donde por primera vez presentó un problema de programación lineal, y propuso el Método Simplex para resolverlo. Cuando comenzó la Segunda Guerra Mundial, Dantzig interrumpió sus estudios en Berkeley para unirse a las Fuerza Aérea de los Estados Unidos como jefe de la Rama de Análisis de Combate de los Cuarteles Centrales Estadísticos, lo cual lo llevó a lidiar con las logísticas de la cadena de abastecimiento y gestión de cientos de miles de ítems y personas.
EN QUE CASOS SE APLICA EL METODO SINPLEX.
• Aplicación del método Simplex en investigación de operaciones y simulación.
• El método Simplex se implementa en programas de ordenador (software) y resulta transparente para el usuario, esto es, el usuario no precisa tener un conocimiento de cómo funciona.
- Logísticas de la cadena de abastecimiento y gestión de cientos de miles de ítems y personas.
VENTAJAS Y DESVENTAJAS DEL METODO SIMPLEX.
Ventajas del Método Simplex:
• Sirve para modelos con 4 o más incógnitas
Desventajas del Método Simplex:
• Difícil de aprender • Asume que todas las variables pertenecen a |R
EJEMPLO DE METODO SIMPLEX. Con miras a conocer la metodología que se aplica en el Método SIMPLEX, vamos a resolver el siguiente problema: Maximizar Z= f(x,y)= 3x + 2y sujeto a: 2x + y 18 2x + 3y 42 3x + y 24 x 0 , y 0 Se consideran las siguientes fases: 1. Convertir las desigualdades en igualdades Se introduce una variable de holgura por cada una de las restricciones, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales: 2x + y + h = 18 2x + 3y + s = 42 3x +y + d = 24 2. Igualar la función objetivo a cero - 3x - 2y + Z = 0 3. Escribir la tabla inicial simplex Tabla I . Iteración nº 1 Base Variable de decisión Variable de holgura Valores solución x y h s d H 2 1 1 0 0 18 S 2 3 0 1 0 42 D 3 1 0 0 1 24 Z -3 -2 0 0 0 0 4. Encontrar la variable de decisión que entra en la base y la variable de holgura que sale de la base A. Para escoger la variable de decisión que entra en la base, nos fijamos en la última fila, la de los coeficientes de la función objetivo y escogemos la variable con el coeficiente negativo mayor (en valor absoluto). En nuestro caso, la variable x de coeficiente - 3. La columna de la variable que entra en la base se llama columna pivote. B. Para encontrar la variable de holgura que tiene que salir de la base, se divide cada término de la última columna (valores solución) por el término correspondiente de la columna pivote, siempre que estos últimos sean mayores que cero. En nuestro caso: 18/2 [=9] , 42/2 [=21] y 24/3 [=8] C. En la intersección de la fila pivote y columna pivote tenemos el elemento pivote operacional, 3. 5. Encontrar los coeficientes de la nueva tabla. Tabla II. Iteración nº 2 Base Variable de decisión Variable de holgura Valores solución x y h s d h 0 1/3 1 0 -2/3 2 s 0 7/3 0 1 -2/3 26 x 1 1/3 0 0 1/3 8 Z 0 -1 0 0 1 24 Como en los elementos de la última fila hay uno negativo, -1, significa que no hemos llegado todavía a la solución óptima. Hay que repetir el proceso: A. La variable que entra en la base es y, por ser la variable que corresponde al coeficiente -1 B. Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote: 2:1/3 [=6], 26:7/3 [=78/7] y 8:1/3 [=8] y como el menor cociente positivo es 6, tenemos que la variable de holgura que sale es h. C. El elemento pivote, que ahora hay que hacer 1, es 1/3. Operando de forma análoga a la anterior obtenemos la tabla: Tabla III. Iteración nº 3 Base Variable de decisión Variable de holgura Valores solución x y h s d y 0 1 3 0 -2 6 s 0 0 -7 0 4 12 x 1 0 -1 0 1 6 Z 0 0 3 0 -1 30 Como en los elementos de la última fila hay uno negativo, -1, significa que no hemos llegado todavía a la solución óptima. Hay que repetir el proceso: A. La variable que entra en la base es d, por ser la variable que corresponde al coeficiente -1 B. Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote: 6/(-2) [=-3], 12/4 [=3], y 6:1 [=6] y como el menor cociente positivo es 3, tenemos que la variable de holgura que sale es s. C. El elemento pivote, que ahora hay que hacer 1, es 4. Obtenemos la tabla: Tabla IV. Final del proceso Base Variable de decisión Variable de holgura Valores solución x y h s d y 0 1 -1/2 0 0 12 d 0 0 -7/4 0 1 3 x 1 0 -3/4 0 0 3 Z 0 0 5/4 0 0 33 Como todos los coeficientes de la fila de la función objetivo son positivos, hemos llegado a la solución óptima. Los solución óptima viene dada por el valor de Z en la columna de los valores solución, en nuestro caso: 33. En la misma columna se puede observar el vértice donde se alcanza, observando las filas correspondientes a las variables de decisión que han entrado en la base: D(3,12) http://www.investigacion-operaciones.com/SIMPLEX_analitico.htm
EL MÉTODO SIMPLEX El Método Simplex es un método analítico de solución de problemas de programación lineal capaz de resolver modelos más complejos que los resueltos mediante el método gráfico sin restricción en el número de variables. El Método Simplex es un método iterativo que permite ir mejorando la solución en cada paso. La razón matemática de esta mejora radica en que el método consiste en caminar del vértice de un poliedro a un vértice vecino de manera que aumente o disminuya (según el contexto de la función objetivo, sea maximizar o minimizar), dado que el número de vértices que presenta un poliedro solución es finito siempre se hallará solución. Fue creado en año del 1947 por el estadounidense George Bernard Dantzig y el ruso Leonid Vitalievich Kantorovich, con el ánimo de crear un algoritmo capaz de solucionar problemas de m restricciones y n variables. EN QUÉ CASO SE EMPLEA EL MÉTODO DE SIMPLEX El algoritmo simplex utiliza el conocido procedimiento de eliminación en la solución de ecuaciones lineales de Gauss- Jordán y, además aplica los llamados criterios del simplex con los cuales se asegura mantener la búsqueda dentro de un conjunto de soluciones factibles al problema; así valora una función económica Z, exclusivamente en vértices FACTIBLES (posibles). También se consigue con eficiencia, debido a que se dirige la búsqueda haciendo cambios a una solución básica factible adyacente, que se distingue al tener m-1 variables básicas iguales; es decir, dos vértices adyacentes sólo difieren en una variable básica; seleccionando la ruta de mayor pendiente, para mejorar el valor de Z, o por lo menos conservarlo. Primero se presenta el método simplex, específico para un modelo de PL en forma canónica de máximo, aplicado con la conocida tabla matricial, (también identificada como tableau), lo cual se resume mediante el diagrama funcional que muestra los fundamentos del algoritmo contenidos en niveles o bloques numerados para la referencia en la descripción del mismo. o Forma estándar.-El modelo de PL en forma canónica de máximo que se desea resolver, tiene m ecuaciones obtenidas al convertir las restricciones de desigualdad a igualdad, agregando m variables de holgura, que sumadas a las n variables de decisión, hacen un total de (m + n) incógnitas. o Calcule una primera solución básica factible.- Del total, (m + n) variables, sólo n se igualan con cero ( n = 0 ), lo cual produce (sí existen), un número finito de soluciones básicas con un límite máximo de (m + n)! / m! n!. Estas pueden ser, factibles y no factibles; se consideran sólo las primeras. o Se toman en cuenta sólo las soluciones básicas factibles, esto es, las que tienen todas las variables básicas >= cero; es decir, con un número de iteraciones menor a (m + n)! / m! n!, se obtienen soluciones básicas factibles: no degeneradas, si todas las incógnitas básicas son positivas y soluciones degeneradas, si al menos una variable básica es igual a cero. Se aplican los criterios del algoritmo en forma iterativa para evaluar la función objetivo en puntos extremos adyacentes que potencialmente puedan mejorar el valor Z. o Se generan nuevas soluciones básicas factibles, tales que el valor de la función objetivo Z mejore; se repite el procedimiento (iteraciones) entre los niveles 3 y 4, hasta que ninguna solución básica factible adyacente resulte mejor; es decir, hasta que no haya incremento de valor, si el problema es de máximo, (hasta que no haya decremento, para el problema, no tratado ahora, de mínimo). Ejemplo: Minimizar Z = 4X1 + 12X2 + 18X3 SA: X1 + 3X3 > 3 2X2 + 2X3 > 5
¿Quién inventó el método simplex y en qué año? Fue el estadounidense George Bernard Dantzig Ourisson quien inventó el método simplex, fue un profesor, físico y matemático, reconocido por desarrollar este método y es considerado como el "padre de la programación lineal". El método simplex fue desarrollado en el verano del año 1947, durante una de sus clases Dantzig llego atrasado y vio dos ejemplos famosos de problemas estadísticos aún no resueltos, pensó que eran tarea y los anotó en su cuaderno, le parecieron más difíciles de lo usual y le tomo varios días resolverlos. Definición Es un método analítico e iterativo de solución de problemas de programación lineal, sus conceptos son básicamente geométricos siendo capaz de resolver modelos más complejos que los resueltos mediante el método gráfico sin restricción en el número de variables. Aplicación del método simplex Este método es importante en el área empresarial utilizada para obtener solución a los problemas en cuanto a inventario, ganancias y pérdidas permitiendo visualizar cuanto se debe vender, producir o comprar para que la empresa tenga las ganancias óptimas y suficientes para competir en el mercado. Se usa el método simplex en investigación de operaciones y simulación. Se implementa en programas de ordenador (software) y resulta transparente para el usuario, esto es, el usuario no precisa tener un conocimiento de cómo funciona. Logísticas de la cadena de abastecimiento y gestión de cientos de miles de ítems y personas. Se utiliza cuando el problema es de un tamaño suficientemente grande. Está diseñado para problemas de programación lineal cuya matriz tiene la propiedad de diseminación (el número de no-cero es pequeño). Hay implementaciones del método simple para la solución de problemas de programación lineal con las matrices de restricción escasa. Ejemplo de resolución de un problema con el método simplex Un agricultor tiene una parcela de 640m² para dedicarla al cultivo de árboles frutales: naranjos, perales, manzanos y limoneros. Se pregunta de qué forma debería repartir la superficie de la parcela entre las variedades para conseguir el máximo beneficio sabiendo que: cada naranjo necesita un mínimo de 16m², cada peral 4m², cada manzano 8m² y cada limonero 12m². Dispone de 900 horas de trabajo al año, necesitando cada naranjo 30 horas al año, cada peral 5 horas, cada manzano 10 horas, y cada limonero 20 horas. a causa de la sequía, el agricultor tiene restricciones para el riego: le han asignado 200m³ de agua anuales. Las necesidades anuales son de 2m³ por cada naranjo, 1m³ por cada peral, 1m³ por cada manzano, y 2m³ por cada limonero. los beneficios unitarios son de 50, 25, 20, y 30 € por cada naranjo, peral, manzano y limonero respectivamente. Se determinan las variables de decisión y se representan algebraicamente. En este caso: X 1 : número de naranjos X 2 : número de perales X 3 : número de manzanos X 4 : número de limoneros Se determinan las restricciones y se expresan como ecuaciones o inecuaciones de las variables de decisión. Dichas restricciones se deducen de las necesidades de cada árbol de terreno, horas de trabajo anuales, y necesidades de riego: Necesidades de terreno: 16•X 1 + 4•X 2 + 8•X 3 + 12•X 4 ≤ 640 Necesidades de horas anuales: 30•X 1 + 5•X 2 + 10•X 3 + 20•X 4 ≤ 900 Necesidades de riego: 2•X 1 + X 2 + X 3 + 2•X 4 ≤ 200 Se expresan todas las condiciones implícitamente establecidas por la naturaleza de las variables: que no puedan ser negativas, que sean enteras, que solo puedan tomar determinados valores. En este caso las restricciones son que el número de árboles no puede ser negativo y además debe ser un número entero: X i ≥ 0 X i son enteros Se determina la función objetivo: Maximizar Z = 50•X 1 + 25•X 2 + 20•X 3 + 30•X 4
NOMBRE: LUDYS ROJAS ¿QUIEN Y CUANDO SE PROPUSO EL METODO SIMPLEX? El Método Simplex publicado por George Dantzig en 1947 consiste en un algoritmo iterativo que secuencialmente a través de iteraciones se va aproximando al óptimo del problema de Programación Lineal en caso de existir esta última. La primera implementación computacional del Método Simplex es el ano 1952 para un problema de 71 variables y 48 ecuaciones. Su resolución tarda 18 horas. Luego, en 1956, un código llamado RSLP1, implementado en un IBM con 4Kb en RAM, admite la resolución de modelos con 255 restricciones. El Método Simplex hace uso de la propiedad de que la solución óptima de un problema de Programación Lineal se encuentra en un vértice o frontera del dominio de puntos factibles (esto último en casos muy especiales), por lo cual, la búsqueda secuencial del algoritmo se basa en la evaluación progresiva de estos vértices hasta encontrar el óptimo. Cabe destacar que para aplicar el Método Simplex a un modelo lineal, este debe estar en un formato especial conocido como formato estándar el cual definiremos a continuación. El Nacimiento de la Programación Lineal Cuando comenzó la Segunda Guerra Mundial, los estudios de Dantzig en Berkeley fueron suspendidos, y el se convirtió en la cabeza de la Rama de Análisis de Combate de los Cuarteles Centrales Estadísticos de Fuerza Aérea de los Estados Unidos, lo cual lo llevó a lidiar con las logísticas de la cadena de abastecimiento y gestión de cientos de miles de ítems y personas. El trabajo proporcionó los problemas del "mundo real" que la programación lineal vendría a resolver. George Dantzig recibió su doctorado en Berkeley en 1946. Él originalmente iba a aceptar un puesto como profesor en Berkeley, pero fue persuadido por su esposa y colegas del Pentágono para volver ahí como consejero matemático de la USAF. Fue ahí, en 1947 que el por primera vez presentó un problema de programación lineal, y propuso el Método Simplex para resolverlo. En 1952 se convirtió en un investigador matemático en la Corporación RAND, donde comenzó a implementar la programación lineal en los computadores de la corporación. En 1960 fue contratado por su alma máter, donde enseñó ciencias de la computación, eventualmente convirtiéndose en el presidente del Centro de Investigación de Operaciones. En 1966 tomó un cargo similar en la Universidad de Stanford. Se quedó en Standord hasta su retiro en los años 90. En adición a su trabajo significativo en el desarrollo del método simplex y la programación lineal, Dantzig también hizo avances en los campos de la teoría de la descomposición, análisis de sensibilidad, métodos de pívot complementarios, optimización a gran escala, programación no lineal, y programación bajo incertidumbre. El primer ejemplar del SIAM Jornal on Optimiza tión en 1991 fue dedicado a él. Una aplicación típica del método simplex dual es en la resolución de problemas con una función objetivo de minimización, con restricciones del tipo mayor o igual y donde las variables de decisión son mayores o iguales a cero.
Utilizado para determinar la nutrición, vitaminas, etc de una persona en general. EJEMPLO 1 Siendo Xi la cantidad a producir del producto i. Maximizar Z = X1 + X2 {Ganancia total en soles}
Los problemas de Maximización, con todas sus restricciones <= y con la condición de no negatividad, se le llama Forma Estándar ó Forma Normal
Aquí debemos conseguir una solución básica factible, empleando las variables de holgura y/o artificiales, quedando el sistema de ecuaciones así: Maximizar Z = X1 + X2 S.A. 5X1 + 3X2 + X3 = 15 3X1 + 5X2 + X4 = 15 Xj >= 0 ; j = 1,2,3,4
Las variables básicas son aquellas cuyos coeficientes forman la matriz unitaria. En este caos accidentalmente son las variables de holgura X3 y X4. A continuación construimos la siguiente tabla: Cj 1 1 0 0 b/a a>0 V.B. b X1 X2 X3 X4 0 X3 15 5 3 1 0 15/5=3 0 X4 15 3 5 0 1 15/3=5 Zj - Cj 0 -1 -1 0 0
El valor de la función objetivo Z, se encuentra frente a la casilla de Zj – Cj , en éste caso vale cero (0) y se calcula multiplicando el vector fila (en la tabla es la columna inmediatamente anterior a la de las variables básica V.B.) que contiene los coeficientes de las variables básicas en la función objetiva original por el vector columna de los términos independientes b CXB = Vector fila de los coeficientes en la función objetivo original de las variables básicas actuales, sus valores se encuentran en la primera columna del tablero. b = Vector columna de los términos independientes de las restricciones, que al mismo tiempo son los valores de las variables básicas actuales, sus valores se encuentran bajo la columna denominada b CXB = (0,0) ; b = (15,15)" Z = CXB * b = (0)(15) + (0)(15) = 0 El valor de los Zj – Cj se calcula multiplicado el vector fila CXB por el vector apuntador aj dela columna de la variable j-ésima, menos el Cj, esto es:
Zj – Cj = CXB. aj – Cj ;
Los cálculos se efectúan así:
Z1 – C1 = CXB a1 – C1 = (0,0).(5,3)" - 1 = (0)(5)+(0)(3) – 1 = -1 Z2 – C2 = CXB a2 – C2 = (0,0).(3,5)" - 1 = (0)(3)+(0)(5) – 1 = -1 Z3 – C3 = CXB a3 – C3 = (0,0).(1,0)" - 0 = (0)(1)+(0)(0) – 0 = 0 Z4 – C4 = CXB a4 – C4 = (0,0).(0,1)" - 0 = (0)(0)+(0)(1) – 0 = 0 La variable que tiene Zj-Cj más negativo es ó X1 ó X2. Se escoge al azar X1. En esta iteración b/a da: 15/5 = 3 y 15/3 = 5; Lo que significa que la variable básica X3 restringe el crecimiento de la variable que entra, X1, hasta 3 (no la deja tomar valores superiores a 3) y la variable básica X4 restringe el crecimiento de la variable que entra X1 hasta 5 (no la deja tomar valores superiores a 5).
Por supuesto la variable básica que restringe más el crecimiento de la variable que entra X1, es X3 , Por lo tanto, es la variable básica escogida para salir. La fila de la variable básica escogida para salir se divide por el elemento que se encuentra en la intersección de dicha fila con la columna de la variable que entra, la fila resultante es la fila pivote y se coloca en un nuevo tablero, desde el que se suman múltiplos de la fila pivote a las demás filas del tablero anterior de tal forma que se eliminen de cada una de ellas la variable escogida para entrar, en nuestro caso X1 , este procedimiento se denomina, hacer un uno (1) en la intersección y el resto de la columna ceros (0), por lo tanto en dicha columna aparecerá un vector unitario, el procedimiento se repite en cada iteración, hasta que todos los Zj – Cj sean mayores ó iguales a cero en el caso de maximizar ó menores ó iguales a cero en el caso de minimizar. A continuación se muestran todas las iteraciones y en cada fila los valores por los cuales fueron multiplicadas para ser sumadas a otras filas, ello se expresa como sumar múltiplos de una fila a otra. Fíjese que se suman múltiplos de las restricciones a la función objetivo para eliminar las variables básicas de ella.
Cj 1 1 0 0 b/a a>0 V.B. b X1 X2 X3 X4 1 X1 3 1 3/5 1/5 0 5 0 X4 6 0 16/5 -3/5 1 15/8
METODO SIMPLEX: El método simplex fue inventado por George Dantzig en 1947, fue en el verano de 1947. El primer problema práctico que se resolvió con este método fue uno de nutrición. El Método Simplex es una técnica popular para dar soluciones numéricas del problema de la programación lineal. Es un método numérico para optimización de problemas libres multidimensionales perteneciente a la clase más general de algoritmos de búsqueda, en el cual sirve para resolver problemas de programación lineal. El método Simplex se emplea en un procedimiento iterativo que permite mejorar la solución de la función objetivo en cada paso. El proceso concluye cuando no es posible continuar mejorando dicho valor, es decir, se ha alcanzado la solución óptima (el mayor o menor valor posible, según el caso, para el que se satisfacen todas las restricciones). Resolver mediante el método simplex el siguiente problema: Maximizar Z = f(x,y) = 3x + 2y sujeto a: 2x + y ≤ 18 2x + 3y ≤ 42 3x + y ≤ 24 x ≥ 0 , y ≥ 0 Se consideran las siguientes fases: Realizar un cambio de variables y normalizar el signo de los términos independientes. Se realiza un cambio en la nomenclatura de las variables. Estableciéndose la correspondencia siguiente: x pasa a ser X1 y pasa a ser X2 Como los términos independientes de todas las restricciones son positivos no es necesario hacer nada. En caso contrario habría que multiplicar por "-1" en ambos lados de la inecuación. Normalizar las restricciones. Se convierten las inecuaciones en ecuaciones agregando variables de holgura, exceso y artificiales según la tabla siguiente: Tipo de desigualdad Tipo de variable que aparece ≥ - exceso + artificial = + artificial ≤ + holgura
En este caso se introduce una variable de holgura (X3, X4 y X5) en cada una de las restricciones del tipo ≤, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales: 2•X1 + X2 + X3 = 18 2•X1 + 3•X2 + X4 = 42 3•X1 + X2 + X5 = 24 Igualar la función objetivo a cero. Z - 3•X1 - X2 - 0•X3 - 0•X4 - 0•X5 = 0 Escribir la tabla inicial del método Simplex. La tabla inicial del método Simplex está compuesta por todos los coeficientes de las variables de decisión del problema original y las de holgura, exceso y artificiales agregadas en el paso 2 (en las columnas, siendo P0 el término independiente y el resto de variables Pi coinciden con Xi), y las restricciones (en las filas). La columna Cb contiene los coeficientes de las variables que se encuentran en la base. La primera fila está formada por los coeficientes de la función objetivo, mientras que la última fila contiene el valor la función objetivo y los costes reducidos Zj - Cj. La última fila se calcula como sigue: Zj = Σ(Cbi•Pj) para i = 1..m, donde si j = 0, P0 = bi y C0 = 0, y en caso contrario Pj = aij. Aunque al tratarse de la primera tabla del método Simplex y ser todos los Cb nulos se puede simplificar el cálculo, y por esta vez disponer Zj = -Cj. Tabla I . Iteración nº 1 3 2 0 0 0 Base Cb P0 P1 P2 P3 P4 P5 P3 0 18 2 1 1 0 0 P4 0 42 2 3 0 1 0 P5 0 24 3 1 0 0 1 Z 0 -3 -2 0 0 0
Condición de parada. Si el objetivo es la maximización, cuando en la última fila (fila indicadora) no existe ningún valor negativo entre los costes reducidos (columnas P1 en adelante) se alcanza la condición de parada. En tal caso se llega al final del algoritmo ya que no existe posibilidad de mejora. El valor de Z (columna P0) es la solución óptima del problema. Otro caso posible es que en la columna de la variable entrante a la base todos los valores son negativos o nulos. Esto indica que el problema no se encuentra acotado y su solución siempre resultará mejorable. Ante esta situación no es necesario continuar iterando indefinidamente y también se puede dar por finalizado el algoritmo. De no ser así, se ejecutan los siguientes pasos de forma iterativa. Elección de la variable entrante y saliente de la base. Se determina en primer lugar la variable que entra en la base. Para ello se escoge la columna cuyo valor en la fila Z sea el menor de entre todos los negativos. En este caso sería la variable X1 (P1) de coeficiente -3. Si existiesen dos o más coeficientes iguales que cumplan la condición anterior (caso de empate), entonces se optará por aquella variable que sea básica. La columna de la variable que entra en la base se llama columna pivote.
Una vez obtenida la variable que entra en la base, se procede a determina cual será la variable que sale de la misma. La decisión se toma en base a un sencillo cálculo: dividir cada término independiente (columna P0) entre el elemento correspondiente de la columna pivote, siempre que ambos elementos sean estrictamente positivos (mayores que cero). Se escoge la fila cuyo resultado haya resultado mínimo. Si hubiera algún elemento menor o igual a cero no se realiza dicho cociente. En caso de que todos los elementos de la columna pivote fueran de ésta condición se habría cumplido la condición de parada y el problema tendría una solución no acotada. En este ejemplo: 18/2 [=9] , 42/2 [=21] y 24/3 [=8] El término de la columna pivote que en la división anterior dio lugar al menor cociente positivo indica la fila de la variable de holgura que sale de la base. En este caso resulta ser X5 (P5), de coeficiente 3. Esta fila se llama fila pivote. La intersección de la fila pivote y columna pivote marca el elemento pivote, en este caso el 3. Actualizar la tabla. Los nuevos coeficientes de la tabla se calculan de la siguiente manera: En la fila del elemento pivote cada nuevo elemento se calcula como: Nuevo Elemento Fila Pivote = Anterior Elemento Fila Pivote / Pivote En el resto de las filas cada elemento se calcula: Nuevo Elemento Fila = Anterior Elemento Fila - (Anterior Elemento Fila en Columna Pivote * Nuevo Elemento Fila Pivote) Con esto se normaliza el elemento pivote y su valor pasa a ser 1, mientras que el resto de elementos de la columna pivote se anulan. Se muestran a continuación los cálculos para la fila P4: Anterior fila P4 42 2 3 0 1 0 - - - - - - Anterior Elemento Fila en Columna Pivote 2 2 2 2 2 2 x x x x x x Nueva fila pivote 8 1 1/3 0 0 1/3 = = = = = = Nueva fila P4 26 0 7/3 0 1 -2/3 La tabla correspondiente a esta segunda iteración es: Tabla II . Iteración nº 2 3 2 0 0 0 Base Cb P0 P1 P2 P3 P4 P5 P3 0 2 0 1/3 1 0 -2/3 P4 0 26 0 7/3 0 1 -2/3 P1 3 8 1 1/3 0 0 1/3 Z 24 0 -1 0 0 1 Al comprobar la condición de parada se observa que no se cumple ya que entre los elementos de la última fila hay uno negativo, -1. Se continúa iterando nuevamente los pasos 4, 5 y 6. La variable que entra en la base es X2 (P2), por ser la variable que corresponde a la columna donde se encuentra el coeficiente -1. Para calcular la variable que sale, se dividen los términos de la columna P0 entre los términos correspondientes de la nueva columna pivote: 2 / 1/3 [=6] , 26 / 7/3 [=78/7] y 8 / 1/3 [=24]. Como el menor cociente positivo es 6, la variable que sale de la base es X3 (P3). El elemento pivote es 1/3. Actualizando nuevamente los valores de la tabla se obtiene: Tabla III . Iteración nº 3 3 2 0 0 0 Base Cb P0 P1 P2 P3 P4 P5 P2 2 6 0 1 3 0 -2 P4 0 12 0 0 -7 1 4 P1 3 6 1 0 -1 0 1 Z 30 0 0 3 0 -1
Una nueva comprobación de la condición de parada revela que entre los elementos de la fila indicadora vuelve a haber uno negativo, -1. Significa que aun no se ha llegado a la solución óptima y hay que seguir iterando (pasos 4, 5 y 6): La variable que entra en la base es X5 (P5), por ser la variable que corresponde al coeficiente -1. Se escoge la variable que sale calculando el cociente entre los términos de la columna de términos independientes y los términos correspondientes de la nueva columna pivote: 6/(-2) [=-3] , 12/4 [=3], y 6/1 [=6]. En esta ocasión es X4 (P4). El elemento pivote es 4. Después de actualizar todas las filas, se obtiene la tabla siguiente: Tabla IV . Iteración nº 4 3 2 0 0 0 Base Cb P0 P1 P2 P3 P4 P5 P2 2 12 0 1 -1/2 1/2 0 P5 0 3 0 0 -7/4 1/4 1 P1 3 3 1 0 3/4 -1/4 0 Z 33 0 0 5/4 1/4 0 Fin del algoritmo. Se observa que en la última fila todos los coeficientes son positivos cumpliéndose, por tanto la condición de parada. La solución óptima viene dada por el valor de Z en la columna de los términos independientes (P0), en este ejemplo: 33. En la misma columna se puede ver el punto donde se alcanza, observando las filas correspondientes a las variables de decisión que han entrado en la base: X1 = 3 y X2 = 12. Deshaciendo el cambio de variables se obtiene x = 3 e y = 12.
NOMBRE: VANESSA CALVO El Método Simplex consiste en un algoritmo iterativo que secuencialmente a través de iteraciones se va aproximando al óptimo del problema de Programación Lineal en caso de existir esta última, hace uso de la propiedad de que la solución óptima de un problema de Programación Lineal se encuentra en un vértice o frontera del dominio de puntos factibles (esto último en casos muy especiales), por lo cual, la búsqueda secuencial del algoritmo se basa en la evaluación progresiva de estos vértices hasta encontrar el óptimo. Cabe destacar que para aplicar el Método Simplex a un modelo lineal, este debe estar en un formato especial conocido como formato estándar el cual definiremos a continuación. FORMA ESTÁNDAR DE UN MODELO DE PROGRAMACIÓN LINEAL Consideremos un modelo de Programación Lineal en su forma estándar, que denotaremos en lo que sigue por: * Min c1x1 + c2x2 + … + cnxn * sa a11x1 + a12x2 + … + a1nxn = b1 * a21x1 + a22x2 + … + a2nxn = b2 * … … … * am1x1 + am2x2 + … + amnxn = bm * xi >= 0, i = 1, 2, …, n y m <= n * Matricialmente escrito como: Min cTx s.a Ax = b x >= 0 Aplicación del método simplex La aplicación del método simplex se utiliza cuando el problema es de un tamaño suficientemente grande está diseñado para problemas de programación lineal cuya matriz tiene la propiedad de diseminación
NOMBRE: VANESSA CALVO El Método Simplex publicado por George Dantzig en 1947 La primera implementación computacional del Método Simplex es el año 1952 para un problema de 71 variables y 48 ecuaciones. Su resolución tarda 18 horas.
QUIEN Y CUANDO CREO EL METODO SIMPLEX Fue creado por George Bernard Dantzig fue un profesor, físico y matemático estadounidense, reconocido por desarrollar el método simplex y es considerado como el "padre de la programación lineal". Recibió muchos honores, tales como la Medalla Nacional de Ciencia en 1975 y el premio de Teoría John von Neumann en 1974. El procedimiento de optimización, en el método Simplex, comienza por la elección de la n+1 puntos donde será hecha la evaluación de la respuesta. Este resultado será evaluado contra las demás respuestas para que el proceso pueda continuar, siendo que este tipo de desarrollo convierte al simplex en un método del tipo secuencial. El metodo simplex es un procedimiento es repetido sucesivamente, descartándose la peor respuesta. Por lo tanto, como vemos, el objetivo del método Simplex secuencial es forzar al simplex a moverse para la región de respuesta óptima. Las decisiones requeridas para que eso sea posible constituyen las llamadas "reglas" del procedimiento simplex. COMO SE UTILIZA EL MÉTODO SIMPLEX PARA LA SOLUCION DE PROBLEMAS DE PROGRAMACIÓN LINEAL Es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución. Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución.
El método del simplex se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta.
EJEMPLO Resolver el siguiente problema de Programación Lineal utilizando el Método Simplex: Max 40*X1 + 60*X2 s.a. 2*X1 + 1*X2 <= 70 1*X1 + 1*X2 <= 40 1*X1 + 3*X2 <= 90 X1 >= 0 X2 >= 0 Para poder aplicar el Método Simplex, es necesario llevar el modelo a su formato estándar, para lo cual definimos X3, X4, X5 >= 0 como las respectivas variables de holgura para la restricción 1, 2 y 3. De esta forma queda definida la tabla inicial del método de la siguiente forma: X1 X2 X3 X4 X5 2 1 1 0 0 70 1 1 0 1 0 40 1 3 0 0 1 90 -40 -60 0 0 0 0 En esta situación, las variables de holgura definen una solución básica factible inicial, condición necesaria para la aplicación del método. Luego, se verifican los costos reducidos de las variables no básicas (X1 y X2 en la tabla inicial) y se escoge como variable que entra a la base aquella con el costo reducido "más negativo". En este caso, X2. Luego, para escoger que variable básica deja la base debemos buscar el mínimo cuociente entre el lado derecho y los coeficientes asociados a la variable entrante en cada fila (para aquellos coeficientes > 0 marcados en rojo en la tabla anterior). El mínimo se alcanza en Min {70/1, 40/1, 90/3} = 30 asociado a la tercera fila, el cual corresponde a la variable básica actual X5, en consecuencia, X5 deja la base. En la posición que se alcanza el mínimo cuociente lo llamaremos "Pivote" (marcado con rojo) el cual nos servirá para realizar las respectivas operaciones filas, logrando la siguiente tabla al cabo de una iteración: X1 X2 X3 X4 X5 5/3 0 1 0 -1/3 40 2/3 0 0 1 -1/3 10 1/3 1 0 0 1/3 30 -20 0 0 0 20 1800 El valor de la función objetivo luego de una iteración ha pasado de 0 a 1.800. Se recomienda al lector hacer una representación gráfica del problema y notar como las soluciones factibles del método corresponden a vértices del dominio de puntos factibles. La actual tabla no corresponde a la solución óptima del problema P) debido a que existe una variable no básica con costo reducido negativo, por tanto X1 entra a la base. Posteriormente, mediante el criterio del mínimo cuociente calculamos la variable que debe dejar la base: Min {40/(5/3), 10/(2/3), 30/(1/3)} = 15, asociado a la fila 2 (variable básica actual X4), por tanto X4 deja la base. Obtenido lo anterior se aplica una iteración del método: X1 X2 X3 X4 X5 0 0 1 -5/2 1/2 15 1 0 0 3/2 -1/2 15 0 1 0 -1/2 1/2 25 0 0 0 30 10 2100 Finalmente se alcanza la solución óptima del problema P) y se verifica que los costos reducidos asociados a las variables no básicas (X4 y X5 son mayores o iguals que cero). Notése que la existencia de un costo reducido igual a cero para una variable no básica en esta etapa define un problema con "infinitas soluciones".
La solución alcanzada es X1* = 15, X2* = 25 con V(P*) = 2.100. Adicionalmente, los costos reducidos asociados a las variables no básicas definen el precio sombra asociado a las restricciones 1, 2 y 3, respectivamente, lo cual es equivalente a la obtención del precio sombra mediante el método gráfico. Dejaremos para una posterior presentación, la forma de calcular el intervalo de variación para el lado derecho que permite la validez del precio sombra, utilizando la tabla final del Método Simplex.
EJEMPLO Max 9u + 2v + 5z sa 4u + 3v + 6z <= 50 u + 2v - 3z >= 8 2u - 4v + z = 5 u,v >= 0 z e IR 1. Siempre es posible llevar un problema de maximización a uno de minimización. Si f(x) es la función objetivo a maximizar yx* es la solución óptima f(x*) >= f(x), para todo x factible. -f(x*) <= - f(x), para todo x factible. En consecuencia: x* es también mínimo de -f(x) 2. Cada restricción del tipo <= puede ser llevada a una ecuación de igualdad usando una (nueva) variable de holgurano negativa, con coeficiente nulo en la función objetivo. 3. Cada restricción del tipo >= puede ser llevada a una ecuación de igualdad usando una (nueva) variable de exceso no negativa, con coeficiente nulo en la función objetivo. 4. Siempre es posible escribir una variable libre de signo como la diferencia de dos variables no negativas. Considerando la siguiente notación: u = x1, v = x2, z = x3 - x4, s1 = x5 (holgura), s2 = x6 (exceso), el problema P) puede ser escrito en forma equivalente como: Min - 9x1 - 2x2 - 5x3 + 5x4 + 0x5 + 0x6 sa: 4x1 + 3x2 + 6x3 - 6x4 + x5 = 50 x1 + 2x2 - 3x3 + 3x4 - x6 = 8 2x1 - 4x2 + x3 - x4 = 5 xi >= 0, i=1,2,3,4,5,6.
¿QUIÉN Y CUÁNDO SE PROPUSO EL MÉTODO SIMPLEX PARA LA RESOLUCIÓN DE PROBLEMAS DE PROGRAMACIÓN LINEAL? ¿Y EN QUÉ CASOS SE APLICA ESTE MÉTODO, CITE EJEMPLOS? ¿Quién creo el método simplex? Fue George Bernard Dantzig, nació el 8 de Noviembre de 1914 en Portland, en el estado de Oregón de los Estados Unidos de América. ¿CUÁNDO SE PROPUSO EL MÉTODO SIMPLEX PARA LA RESOLUCIÓN DE PROBLEMAS DE PROGRAMACIÓN LINEAL? George Dantzig se doctoró en Berkeley en 1946. Inicialmente iba a aceptar un puesto como profesor en Berkeley, pero fue persuadido por su esposa y colegas del Pentágono para volver a las Fuerzas Aéreas como consejero matemático de la USAF. Fue ahí, en 1947 donde por primera vez presentó un problema de programación lineal, y propuso el Método Simplex para resolverlo. En 1952 se convirtió en investigador matemático en la Corporación RAND,en cuyos ordendadores comenzó a implementar la programación lineal. En 1960 fue contratado por su alma máter, donde enseñó ciencias de la computación, convirtiéndose en presidente del Centro de Investigación de Operaciones. ¿EN QUÉ CASOS DE APLICA ESTE MÉTODO? • La aplicación del método del Simplex, se utiliza cuando el problema es de un tamaño suficientemente grande. • Está diseñado para problemas de programación lineal cuya matriz tiene la propiedad de diseminación (el número de no-cero es pequeño). • Hay implementaciones del método simple para la solución de problemas de programación lineal con las matrices de restricción escasa. • Se han desarrollado diversas variantes del método simplex que tienen en cuenta las particularidades de las diversas clases especiales de problemas de programación lineal (problemas de bloque, los problemas de transporte y otros).
CONDICIONES • El objetivo es de la forma de maximización o de minimización. • Todas las restricciones son de igualdad. • Todas las variables son no negativas. • Las constantes a la derecha de las restricciones son no negativas.
EJEMPLO Un agricultor tiene una parcela de 640m² para dedicarla al cultivo de árboles frutales: naranjos, perales, manzanos y limoneros. Se pregunta de qué forma debería repartir la superficie de la parcela entre las variedades para conseguir el máximo beneficio sabiendo que: • cada naranjo necesita un mínimo de 16m², cada peral 4m², cada manzano 8m² y cada limonero 12m². • dispone de 900 horas de trabajo al año, necesitando cada naranjo 30 horas al año, cada peral 5 horas, cada manzano 10 horas, y cada limonero 20 horas. • a causa de la sequía, el agricultor tiene restricciones para el riego: le han asignado 200m³ de agua anuales. Las necesidades anuales son de 2m³ por cada naranjo, 1m³ por cada peral, 1m³ por cada manzano, y 2m³ por cada limonero. Los beneficios unitarios son de 50, 25, 20, y 30 € por cada naranjo, peral, manzano y limonero respectivamente
resolver el siguiente problema: Maximizar Z= f(x ,y)= 3x + 2y sujeto a: 2x + y 1 2x + 3y 42 3x + y 24 x 0 , y 0 Se consideran las siguientes fases: 1. Convertir las desigualdades en igualdades Se introduce una variable de holgura por cada una de las restricciones, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales: 2x + y + h = 18 2x + 3y + s = 42 3x +y + d = 24 2. Igualar la función objetivo a cero - 3x - 2y + Z = 0 3. Escribir la tabla inicial simplex Tabla I . Iteración nº 1 Base Variable de decisión Variable de holgura Valores solución x y h s d H 2 1 1 0 0 18 S 2 3 0 1 0 42 D 3 1 0 0 1 24 Z -3 -2 0 0 0 0 4. Encontrar la variable de decisión que entra en la base y la variable de holgura que sale de la base A. Para escoger la variable de decisión que entra en la base, nos fijamos en la última fila, la de los coeficientes de la función objetivo y escogemos la variable con el coeficiente negativo mayor (en valor absoluto). En nuestro caso, la variable x de coeficiente - 3. La columna de la variable que entra en la base se llama columna pivote. B. Para encontrar la variable de holgura que tiene que salir de la base, se divide cada término de la última columna (valores solución) por el término correspondiente de la columna pivote, siempre que estos últimos sean mayores que cero. En nuestro caso: 18/2 [=9] , 42/2 [=21] y 24/3 [=8] C. En la intersección de la fila pivote y columna pivote tenemos el elemento pivote operacional, 3.
5. Encontrar los coeficientes de la nueva tabla. Tabla II. Iteración nº 2 Base Variable de decisión Variable de holgura Valores solución x y h s d h 0 1/3 1 0 -2/3 2 s 0 7/3 0 1 -2/3 26 x 1 1/3 0 0 1/3 8 Z 0 -1 0 0 1 24 Como en los elementos de la última fila hay uno negativo, -1, significa que no hemos llegado todavía a la solución óptima. Hay que repetir el proceso: A. La variable que entra en la base es y, por ser la variable que corresponde al coeficiente -1 B. Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote:
Como en los elementos de la última fila hay uno negativo, -1, significa que no hemos llegado todavía a la solución óptima. Hay que repetir el proceso: A. La variable que entra en la base es d, por ser la variable que corresponde al coeficiente -1 B. Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote: 6/(-2) [=-3], 12/4 [=3], y 6:1 [=6] y como el menor cociente positivo es 3, tenemos que la variable de holgura que sale es s. C. El elemento pivote, que ahora hay que hacer 1, es 4. Obtenemos la tabla: Tabla IV. Final del proceso Base Variable de decisión Variable de holgura Valores solución x y h s d y 0 1 -1/2 0 0 12 d 0 0 -7/4 0 1 3 x 1 0 -3/4 0 0 3 Z 0 0 5/4 0 0 33 Como todos los coeficientes de la fila de la función objetivo son positivos, hemos llegado a la solución óptima. La solución óptima viene dada por el valor de Z en la columna de los valores solución, en nuestro caso: 33
¿QUIÉN Y CUÁNDO SE PROPUSO EL MÉTODO SIMPLEX PARA LA RESOLUCIÓN DE PROBLEMAS DE PROGRAMACIÓN LINEAL? Este modelo fue creado por George Bernard Dantzig nacido el 8 de noviembre de 1914. Inicialmente iba a aceptar un puesto como profesor en Berkeley, pero fue persuadido por su esposa y colegas del Pentágono para volver a las Fuerzas Aéreas como consejero matemático de la USAF. Fue ahí, en 1947 donde por primera vez presentó un problema de programación lineal, y propuso el Método Simplex para resolverlo. ¿Y EN QUÉ CASOS DE APLICA ESTE MÉTODO, CITE EJEMPLOS? 1. DEGENERACION En la aplicación de la condición de factibilidad, una coincidencia de la razón mínima se debe descomponer en forma arbitraria para los fines de determinar la variable que sale. Cuando suceda esto una o más veces de las variables básicas, será necesariamente igual a cero en la siguiente iteración. Ejemplo (Solución óptima degenerada) Maximizar z = 3x1 +9x2 Sujeto a x1 + 4x2 £ 8 x1 + 2x2 £ 4 x1,x2 ³ 0 2. OPCIONES ÓPTIMAS. Cuando la función objetivo es paralela a una restricción de enlace (o sea, una restricción que se satisface en el sentido de la igualdad a través de la solución óptima), la función objetivo tomara el mismo valor optimo en más de un punto de solución. Ejemplo (Infinidad de soluciones) Maximizar z = 2x1 + 4x2 Sujeto a x1 + x2 £ 5 x1 + x2£ 4 x1, x2³ 0
3. SOLUCION NO ACOTADA En algunos modelos de programación lineal los valores de las variables se pueden aumentar en forma indefinida sin violar ninguna de las restricciones, lo que significa que el espacio de soluciones es no acotado cuando menos en una dirección. Como resultado, el valor de la función objetivo puede crecer (caso de maximización) o de crecer (caso de minimización) en forma indefinida. En este caso decimos que el espacio de soluciones y el valor "óptimo" de la función objetivo son no acotados. La falta de explicación en un modelo puede señalar solo una cosa: el modelo está mal construido. Evidentemente resulta irracional hacer que un modelo produzca una ganancia " infinita". Las irregularidades más probables en estos modelos son: 1) No se toman en cuenta unas más restricciones redundantes, y 2) No se determinan correctamente los parámetros (constantes) de algunas restricciones. La regla general para reconocer la falta de acotación es la siguiente. Sien cualquier iteración los coeficientes de las restricciones de una variable no básica son no positivos, entonces el espacio de soluciones no está acotado en esa dirección. Además, si el coeficiente de la función objetivo de esa variable en el caso de la maximización o positivo en el caso de la minimización, entonces el valor de la función objetivo tampoco está acotado. Ejemplo (Función objetivo no acotada) Maximizar z = 2x1 + x2 Sujeto a x1 - x2 £ 10 2x1 £ 40 x1, x2 ³ 0 4. SOLUCION INFACTIBLE Si las restricciones no se pueden satisfacer en forma simultánea, se dice que el modelo no tiene solución factible. Esta situación nunca puede ocurrir si todas las restricciones son del tipo (suponiendo constantes no negativas en el segundo miembro) ya que la variable de holgura produce siempre alguna solución factible. Sin embargo, cuando empleamos los otros tipos de restricciones, recurrimos al uso de variables artificiales que, por su mismo diseño, no ofrecen una solución factible al modelo original. Aunque se toman medidas (a través del uso de la penalización) para hacer que las variables artificiales sean cero en el nivel óptimo, esto sólo puede ocurrir si el modelo tiene un espacio factible. Si no lo tiene, cuando menos una variable artificial será positiva en la iteración óptima. Esta es nuestra indicación que el problema no tiene solución factible. Desde el punto de vista práctico un espacio infectable apunta a la posibilidad de que el modelo no se haya formulado correctamente en virtud de que las restricciones estén en conflicto. También es posible que las restricciones no estén destinadas a cumplirse en forma simultánea, en este caso, quina se necesite una estructura del modelo totalmente deferente que no admita todas las restricciones al mismo tiempo. Ejemplo de espacio de (solución infactible) Maximizar z = 3x1 + 2x2 Sujeto a 2x1 + x2 £ 2 3x1 + 4x2 ³ 12 x1, x2 ³ 0
¿Quién fue el que invento el método simple para la resolución de los problemas de programación lineal? Fue George Bernard Dantzig, nació el 8 de Noviembre de 1914 en Portland, en el estado de Oregón de los Estados Unidos de América. ¿Cuándo se propuso el método simplex? En 1947, en EE.UU., George Datzing encuentra el método simplex para el problema de programación lineal. En la investigación de operaciones, las computadoras son la herramienta fundamental en la investigación de operaciones. En el verano de 1947 realizó la primera formulación del método Simplex. El primer problema práctico resuelto con este nuevo método fue el problema de nutrición que había planteado George Joseph Stigler a finales de la década anterior, debido al interés del ejército americano por encontrar una dieta equilibrada para alimentar a sus tropas, que cumpliera con unos requisitos mínimos de nutrición y fuese económica. El problema, que constaba de 9 ecuaciones y 77 incógnitas, fue resuelto manualmente tras 120 días de trabajo. Se demostró que el resultado obtenido apenas difería unos céntimos de la solución hallada anteriormente mediante métodos heurísticos, resultando el nuevo método Simplex todo un éxito. La primera implementación computacional del Método Simplex es el ano 1952 para un problema de 71 variables y 48 ecuaciones. Su resolución tarda 18 horas. Luego, en 1956, un código llamado RSLP1, implementado en un IBM con 4Kb en RAM, admite la resolución de modelos con 255 restricciones.
Nombre: LUIS CHANGO ¿Quien creó y en qué fecha el método simplex? El método simplex es un método que sirve para resolver problemas de programación lineal. Este método fue inventado por George Danzig en el 1947. La primera formulación del método simplex fue en el verano de 1947. El primer problema práctico que se resolvió con este método fue uno de nutrición. El método simplex: Disminuye sistemáticamente un número infinito de soluciones hasta un número finito de soluciones básicas factibles. Un modelo de programación lineal proporciona un método eficiente para determinar una decisión óptima, (o una estrategia óptima o un plan óptimo) escogida de un gran número de decisiones posibles. En todos los problemas de Programación Lineal, el objetivo es la maximización o minimización de alguna cantidad. “En que casos se emplea el método simplex” La aplicación del método del Simplex, se utiliza cuando el problema es de un tamaño suficientemente grande. Aspectos fundamentales del método simplex: Encuentra una solución óptima. Es un método de cambio de bases. Requiere que la función objetivo sea expresada de tal forma que cada variable básica tenga como coeficiente 0. Requiere que cada variable básica aparezca en una y solamente una ecuación de restricción. Dualidad.
¿En qué casos se aplica este método, cite ejemplos?
Con miras a conocer la metodología que se aplica en el Método SIMPLEX, vamos a resolver el siguiente problema: Maximizar Z= f(x,y)= 3x + 2y sujeto a: 2x + y 18 2x + 3y 42 3x + y 24 x 0 , y 0 Se consideran las siguientes fases: 1. Convertir las desigualdades en igualdades Se introduce una variable de holgura por cada una de las restricciones, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales: 2x + y + h = 18 2x + 3y + s = 42 3x +y + d = 24
2. Igualar la función objetivo a cero - 3x - 2y + Z = 0 3. Escribir la tabla inicial simplex En las columnas aparecerán todas las variables del problema y, en las filas, los coeficientes de las igualdades obtenidas, una fila para cada restricción y la última fila con los coeficientes de la función objetivo: Tabla I . Iteración nº 1 Base Variable de decisión Variable de holgura Valores solución x y h s d h 2 1 1 0 0 18 s 2 3 0 1 0 42 d 3 1 0 0 1 24 Z -3 -2 0 0 0 0 4. Encontrar la variable de decisión que entra en la base y la variable de holgura que sale de la base A. Para escoger la variable de decisión que entra en la base, nos fijamos en la última fila, la de los coeficientes de la función objetivo y escogemos la variable con el coeficiente negativo mayor (en valor absoluto). En nuestro caso, la variable x de coeficiente - 3. Si existiesen dos o más coeficientes iguales que cumplan la condición anterior, entonces se elige uno cualquiera de ellos. Si en la última fila no existiese ningún coeficiente negativo, significa que se ha alcanzado la solución óptima. Por tanto, lo que va a determinar el final del proceso de aplicación del método del simplex, es que en la última fila no haya elementos negativos. La columna de la variable que entra en la base se llama columna pivote (En color azulado).
B. Para encontrar la variable de holgura que tiene que salir de la base, se divide cada término de la última columna (valores solución) por el término correspondiente de la columna pivote, siempre que estos últimos sean mayores que cero. En nuestro caso: 18/2 [=9] , 42/2 [=21] y 24/3 [=8] Si hubiese algún elemento menor o igual que cero no se hace dicho cociente. En el caso de que todos los elementos fuesen menores o iguales a cero, entonces tendríamos una solución no acotada y no se puede seguir. El término de la columna pivote que en la división anterior dé lugar al menor cociente positivo, el 3, ya 8 es el menor, indica la fila de la variable de holgura que sale de la base, d. Esta fila se llama fila pivote (En color azulado). Si al calcular los cocientes, dos o más son iguales, indica que cualquiera de las variables correspondientes pueden salir de la base.
C. En la intersección de la fila pivote y columna pivote tenemos el elemento pivote operacional, 3. 5. Encontrar los coeficientes de la nueva tabla. Los nuevos coeficientes de x se obtienen dividiendo todos los coeficientes de la fila d por el pivote operacional, 3, que es el que hay que convertir en 1. A continuación mediante la reducción gaussiana hacemos ceros los restantes términos de su columna, con lo que obtenemos los nuevos coeficientes de las otras filas incluyendo los de la función objetivo Z. También se puede hacer utilizando el siguiente esquema: Fila del pivote: Nueva fila del pivote= (Vieja fila del pivote) : (Pivote) Resto de las filas: Nueva fila= (Vieja fila) - (Coeficiente de la vieja fila en la columna de la variable entrante) X (Nueva fila del pivote) Veámoslo con un ejemplo una vez calculada la fila del pivote (fila de x en la Tabla II): Vieja fila de s 2 3 0 1 0 42 - - - - - - Coeficiente 2 2 2 2 2 2 x x x x x x Nueva fila pivote 1 1/3 0 0 1/3 8 = = = = = = Nueva fila de s 0 7/3 0 1 -2/3 26
Tabla II . Iteración nº 2 Base Variable de decisión Variable de holgura Valores solución x y h s d h 0 1/3 1 0 -2/3 2 s 0 7/3 0 1 -2/3 26 x 1 1/3 0 0 1/3 8 Z 0 -1 0 0 1 24 Como en los elementos de la última fila hay uno negativo, -1, significa que no hemos llegado todavía a la solución óptima. Hay que repetir el proceso: A. La variable que entra en la base es y, por ser la variable que corresponde al coeficiente -1 B. Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote: 2:1/3 [=6] , 26:7/3 [=78/7] y 8:1/3 [=8] y como el menor cociente positivo es 6, tenemos que la variable de holgura que sale es h. C. El elemento pivote, que ahora hay que hacer 1, es 1/3. Operando de forma análoga a la anterior obtenemos la tabla: Tabla III . Iteración nº 3 Base Variable de decisión Variable de holgura Valores solución x y h s d y 0 1 3 0 -2 6 s 0 0 -7 0 4 12 x 1 0 -1 0 1 6 Z 0 0 3 0 -1 30 Como en los elementos de la última fila hay uno negativo, -1, significa que no hemos llegado todavía a la solución óptima. Hay que repetir el proceso: A. La variable que entra en la base es d, por ser la variable que corresponde al coeficiente -1 B. Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote: 6/(-2) [=-3] , 12/4 [=3], y 6:1 [=6] y como el menor cociente positivo es 3, tenemos que la variable de holgura que sale es s. C. El elemento pivote, que ahora hay que hacer 1, es 4. Obtenemos la tabla:
Tabla IV . Final del proceso Base Variable de decisión Variable de holgura Valores solución x y h s d y 0 1 -1/2 0 0 12 d 0 0 -7/4 0 1 3 x 1 0 -3/4 0 0 3 Z 0 0 5/4 0 0 33 Como todos los coeficientes de la fila de la función objetivo son positivos, hemos llegado a la solución óptima. Los solución óptima viene dada por el valor de Z en la columna de los valores solución, en nuestro caso: 33. En la misma columna se puede observar el vértice donde se alcanza, observando las filas correspondientes a las variables de decisión que han entrado en la base: D(3,12)
EJEMPLO 2 Resolver el siguiente problema de Programación Lineal utilizando el Método Simplex: • Max 40*X1 + 60*X2 • s.a. 2*X1 + 1*X2 <= 70 • 1*X1 + 1*X2 <= 40 • 1*X1 + 3*X2 <= 90 • X1 >= 0 X2 >= 0 Para poder aplicar el Método Simplex, es necesario llevar el modelo a su formato estándar, para lo cual definimos X3, X4, X5 >= 0 como las respectivas variables de holgura para la restricción 1, 2 y 3. De esta forma queda definida la tabla inicial del método de la siguiente forma: X1 X2 X3 X4 X5 2 1 1 0 0 70 1 1 0 1 0 40 1 3 0 0 1 90 -40 -60 0 0 0 0
En esta situación, las variables de holgura definen una solución básica factible inicial, condición necesaria para la aplicación del método. Luego, se verifican los costos reducidos de las variables no básicas (X1 y X2 en la tabla inicial) y se escoge como variable que entra a la base aquella con el costo reducido "más negativo". En este caso, X2.
Luego, para escoger que variable básica deja la base debemos buscar el mínimo cuociente entre el lado derecho y los coeficientes asociados a la variable entrante en cada fila (para aquellos coeficientes > 0 marcados en rojo en la tabla anterior). El mínimo se alcanza en Min {70/1, 40/1, 90/3} = 30 asociado a la tercera fila, el cual corresponde a la variable básica actual X5, en consecuencia, X5 deja la base. En la posición que se alcanza el mínimo cuociente lo llamaremos "Pivote" (marcado con rojo) el cual nos servirá para realizar las respectivas operaciones filas, logrando la siguiente tabla al cabo de una iteración: X1 X2 X3 X4 X5 5/3 0 1 0 -1/3 40 2/3 0 0 1 -1/3 10 1/3 1 0 0 1/3 30 -20 0 0 0 20 1800 El valor de la función objetivo luego de una iteración ha pasado de 0 a 1.800. Se recomienda al lector hacer una representación gráfica del problema y notar como las soluciones factibles del método corresponden a vértices del dominio de puntos factibles.
La actual tabla no corresponde a la solución óptima del problema P) debido a que existe una variable no básica con costo reducido negativo, por tanto X1 entra a la base. Posteriormente, mediante el criterio del mínimo cuociente calculamos la variable que debe dejar la base: Min {40/(5/3), 10/(2/3), 30/(1/3)} = 15, asociado a la fila 2 (variable básica actual X4), por tanto X4 deja la base. Obtenido lo anterior se aplica una iteración del método: X1 X2 X3 X4 X5 0 0 1 -5/2 1/2 15 1 0 0 3/2 -1/2 15 0 1 0 -1/2 1/2 25 0 0 0 30 10 2100 Finalmente se alcanza la solución óptima del problema P) y se verifica que los costos reducidos asociados a las variables no básicas (X4 y X5 son mayores o iguals que cero). Notése que la existencia de un costo reducido igual a cero para una variable no básica en esta etapa define un problema con "infinitas soluciones".
La solución alcanzada es X1* = 15, X2* = 25 con V(P*) = 2.100. Adicionalmente, los costos reducidos asociados a las variables no básicas definen el precio sombra asociado a las restricciones 1, 2 y 3, respectivamente, lo cual es equivalente a la obtención del precio sombra mediante el método gráfico. Dejaremos para una posterior presentación, la forma de calcular el intervalo de variación para el lado derecho que permite la validez del precio sombra, utilizando la tabla final del Método Simplex.
METODO SIMPLEX
ResponderEliminarEl método Simplex: es un procedimiento algebraico, sus conceptos fundamentales son geométricos, por lo que la comprensión de estos conceptos geométricos nos proporciona una fuerte intuición sobre como opera el método Simplex y porque es tan eficiente y tambien, es un algoritmo que parte de una solución básica posible y encuentra otra que mejora el valor de la función objetivo. Este procedimiento se repite hasta que se alcanza el óptimo, si éste existe, o se arriba a una condición de final anormal.
Quien invento el método simplex: este método fue inventado por GEORGE DANTZING en 1947.
Cuando se aplicó dicho método: la primera formulación del método simplex fue en el verano de 1947, lel primer problema practico que se resolvió fue uno de nutrición, la primera implementación computacional del Método Simplex es el año 1952 para un problema de 71 variables y 48 ecuaciones. Su resolución tarda 18 horas. Luego, en 1956, un código llamado RSLP1, implementado en un IBM con 4Kb en RAM, admite la resolución de modelos con 255 restricciones.
Donde se aplica dicho método: la aplicación del método simplex se utiliza cuando el problema es de tamaño suficientemente grande, también esta diseñado en la programación lineal cuando la matriz tiene propiedad de diseminación y esta relacionado en diversas clases especiales de poblemas de programación lineal (problemas de bosques , problemas de transporte y otros).
EJEMPLO:
Max 40*X1 + 60*X2
s.a. 2*X1 + 1*X2 <= 70
1*X1 + 1*X2 <= 40
1*X1 + 3*X2 <= 90
X1 >= 0 X2 >= 0
Para poder aplicar el Método Simplex, es necesario llevar el modelo a su formato estándar, para lo cual definimos X3, X4, X5 >= 0 como las respectivas variables de holgura para la restricción 1, 2 y 3. De esta forma queda definida la tabla inicial del método de la siguiente forma:
Luego, para escoger que variable básica deja la base debemos buscar el mínimo cuociente entre el lado derecho y los coeficientes asociados a la variable entrante en cada fila (para aquellos coeficientes > 0 marcados en rojo en la tabla anterior). El mínimo se alcanza en Min {70/1, 40/1, 90/3} = 30 asociado a la tercera fila, el cual corresponde a la variable básica actual X5, en consecuencia, X5 deja la base. En la posición que se alcanza el mínimo cuociente lo llamaremos "Pivote" (marcado con azul) el cual nos servirá para realizar las respectivas operaciones filas, logrando la siguiente tabla al cabo de una iteración.
La actual tabla no corresponde a la solución óptima del problema P) debido a que existe una variable no básica con costo reducido negativo, por tanto X1 entra a la base. Posteriormente, mediante el criterio del mínimo cuociente calculamos la variable que debe dejar la base: Min {40/(5/3), 10/(2/3), 30/(1/3)} = 15, asociado a la fila 2 (variable básica actual X4), por tanto X4 deja la base.
Finalmente se alcanza la solución óptima del problema P) y se verifica que los costos reducidos asociados a las variables no básicas (X4 y X5 son mayores o iguals que cero). La solución alcanzada es X1* = 15, X2* = 25 con V(P*) = 2.100. Adicionalmente, los costos reducidos asociados a las variables no básicas definen el precio sombra asociado a las restricciones 1, 2 y 3, respectivamente, lo cual es equivalente a la obtención del precio sombra mediante el método gráfico, la forma de calcular el intervalo de variación para el lado derecho que permite la validez del precio sombra, utilizando la tabla final del Método Simplex.
El método Simplex es un procedimiento iterativo que permite mejorar la solución de la función objetivo en cada paso. El proceso concluye cuando no es posible continuar mejorando dicho valor, es decir, se ha alcanzado la solución óptima (el mayor o menor valor posible, según el caso, para el que se satisfacen todas las restricciones).
ResponderEliminarPartiendo del valor de la función objetivo en un punto cualquiera, el procedimiento consiste en buscar otro punto que mejore el valor anterior. Como se verá en el método Gráfico, dichos puntos son los vértices del polígono (o poliedro o polícoro, si el número de variables es mayor de 2) que constituye la región determinada por las restricciones a las que se encuentra sujeto el problema (llamada región factible). La búsqueda se realiza mediante desplazamientos por las aristas del polígono, desde el vértice actual hasta uno adyacente que mejore el valor de la función objetivo. Siempre que exista región factible, como su número de vértices y de aristas es finito, será posible encontrar la solución.
El método Simplex se basa en la siguiente propiedad: si la función objetivo Z no toma su valor máximo en el vértice A, entonces existe una arista que parte de A y a lo largo de la cual el valor de Z aumenta.
Será necesario tener en cuenta que el método Simplex únicamente trabaja con restricciones del problema cuyas inecuaciones sean del tipo "≤" (menor o igual) y sus coeficientes independientes sean mayores o iguales a 0. Por tanto habrá que estandarizar las restricciones para que cumplan estos requisitos antes de iniciar el algoritmo del Simplex. En caso de que después de éste proceso aparezcan restricciones del tipo "≥" (mayor o igual) o "=" (igualdad), o no se puedan cambiar, será necesario emplear otros métodos de resolución, siendo el más común el método de las Dos Fases.
Preparando el modelo para adaptarlo al método Simplex
La forma estándar del modelo de problema consta de una función objetivo sujeta a determinadas restricciones:
Función objetivo: c1·x1 + c2·x2 + ... + cn·xn
Sujeto a: a11·x1 + a12·x2 + ... + a1n·xn = b1
a21·x1 + a22·x2 + ... + a2n·xn = b2
...
am1·x1 + am2·x2 + ... + amn·xn = bm
x1,..., xn ≥ 0
El modelo debe cumplir las siguientes condiciones:
El objetivo consistirá en maximizar o minimizar el valor de la función objetivo (por ejemplo, incrementar ganancias o reducir pérdidas, respectivamente).
Todas las restricciones deben ser ecuaciones de igualdad (identidades matemáticas).
Todas las variables (xi) deben tener valor positivo o nulo (condición de no negatividad).
Los términos independientes (bi) de cada ecuación deben ser no negativos.
Hay que adaptar el problema modelado a la forma estándar para poder aplicar el algoritmo del Simplex.
QUIEN Y CUANDO SE INVENTO EL METODO SIMPLEX
Este metodo fue inventado por George Dantzig en el 1947. La primera formulación del método simplex fue en el verano de 1947. El primer problema práctico que se resolvió con este método fue uno de nutrición.Es una técnica popular para dar soluciones numéricas del problema de la programación lineal. Es un método numérico para optimización de problemas libres multidimensionales perteneciente a la clase más general de algoritmos de búsqueda. Permite encontrar una solución óptima en un problema de maximización o minimización, buscando en los vértices del polígono. Es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución. Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución. Se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta.
MÉTODO SIMPLEX
ResponderEliminarEl Método Simplex es un método analítico de solución de problemas de programación lineal capaz de resolver modelos más complejos que los resueltos mediante el método gráfico sin restricción en el número de variables.
El Método Simplex es un método iterativo que permite ir mejorando la solución en cada paso. La razón matemática de esta mejora radica en que el método consiste en caminar del vértice de un poliedro a un vértice vecino de manera que aumente o disminuya (según el contexto de la función objetivo, sea maximizar o minimizar).
Quien invento el método simplex: Este método fue inventado por GEORGE DANTZING en 1947.La primera formulación del método simplex fue en el verano de 1947, del primer problema practico que se resolvió fue uno de nutrición, la primera implementación computacional del Método Simplex es el año 1952 para un problema de 71 variables y 48 ecuaciones.
En qué caso se aplica
El método simplex disminuye sistemáticamente un número infinito de soluciones hasta un número finito de soluciones básicas factibles. El método simplex utiliza el conocido procedimiento de eliminación en la solución de ecuaciones lineales de Gauss- Jordan y, además aplica los llamados criterios del simplex con los cuales se asegura mantener la búsqueda dentro de un conjunto de soluciones factibles al problema; así valora una función económica Z, exclusivamente en vértices FACTIBLES (posibles).
Resolver el siguiente problema de Programación Lineal utilizando el Método Simplex:
Max 40*X1 + 60*X2
s.a. 2*X1 + 1*X2 <= 70
1*X1 + 1*X2 <= 40
1*X1 + 3*X2 <= 90
X1 >= 0 X2 >= 0
Para poder aplicar el Método Simplex, es necesario llevar el modelo a su formato estándar, para lo cual definimos X3, X4, X5 >= 0 como las respectivas variables de holgura para la restricción 1, 2 y 3. De esta forma queda definida la tabla inicial del método de la siguiente forma:
En esta situación, las variables de holgura definen una solución básica factible inicial, condición necesaria para la aplicación del método. Luego, se verifican los costos reducidos de las variables no básicas (X1 y X2 en la tabla inicial) y se escoge como variable que entra a la base aquella con el costo reducido "más negativo". En este caso, X2.
X1 X2 X3 X4 X5
2 1 1 0 0 70
1 1 0 1 0 40
1 ..... 3 0 0 1 90
-40 -60 0 0 0 0
Luego, para escoger que variable básica deja la base debemos buscar el mínimo cociente entre el lado derecho y los coeficientes asociados a la variable entrante en cada fila (para aquellos coeficientes > 0 marcados en rojo en la tabla anterior). El mínimo se alcanza en Min {70/1, 40/1, 90/3} = 30 asociado a la tercera fila, el cual corresponde a la variable básica actual X5, en consecuencia, X5 deja la base. En la posición que se alcanza el mínimo cociente lo llamaremos "Pivote" (marcado con azul) el cual nos servirá para realizar las respectivas operaciones filas, logrando la siguiente tabla al cabo
X1 X2 X3 X4 X5
5/3 0 1 0 -1/3 40
2/3 0 0 1 -1/3 10
1/3 1 0 0 1/3 30
-20 0 0 0 20 1.800
de una iteración.
La actual tabla no corresponde a la solución óptima del problema P) debido a que existe una variable no básica con costo reducido negativo, por tanto X1 entra a la base. Posteriormente, mediante el criterio del mínimo cociente calculamos la variable que debe dejar la base: Min {40/(5/3), 10/(2/3), 30/(1/3)} = 15, asociado a la fila 2 (variable básica actual X4), por tanto X4 deja la base. Obtenido lo anterior se aplica una iteración del método:
X1 X2 X3 X4 X5
0 0 1 -5/2 1/2 15
1 0 0 3/2 -1/2 15
0 1 0 -1/2 1/2 25
0 0 0 30 10 2.100
Finalmente se alcanza la solución óptima del problema P) y se verifica que los costos reducidos asociados a las variables no básicas (X4 y X5 son mayores o igual que cero).
FORMA ESTÁNDAR DE UN MODELO DE PROGRAMACIÓN LINEAL
ResponderEliminarConsideremos un modelo de Programación Lineal en su forma estandar, que denotaremos en lo que sigue por:
Min c1x1 + c2x2 + ... + cnxn
sa a11x1 + a12x2 + ... + a1nxn = b1
a21x1 + a22x2 + ... + a2nxn = b2
... ... ...
am1x1 + am2x2 + ... + amnxn = bm
xi >= 0, i = 1, 2, ..., n y m <= n
Matricialmente escrito como:
Min cTx
s.a Ax = b
x >= 0
No existe pérdida de generalidad en asumir que un modelo de PL viene dado en su forma estándar:
EJEMPLO
P) Max 9u + 2v + 5z
sa 4u + 3v + 6z <= 50
u + 2v - 3z >= 8
2u - 4v + z = 5
u,v >= 0
z e IR
Siempre es posible llevar un problema de maximización a uno de minimización. Si f(x) es la función objetivo a maximizar y x* es la solución óptima f(x*) >= f(x), para todo x factible. -f(x*) <= - f(x), para todo x factible. En consecuencia: x* es también mínimo de -f(x)
Cada restricción del tipo <= puede ser llevada a una ecuación de igualdad usando una (nueva) variable de holgura no negativa, con coeficiente nulo en la función objetivo.
Cada restricción del tipo >= puede ser llevada a una ecuación de igualdad usando una (nueva) variable de exceso no negativa, con coeficiente nulo en la función objetivo.
Siempre es posible escribir una variable libre de signo como la diferencia de dos variables no negativas.
Considerando la siguiente notación: u = x1, v = x2, z = x3 - x4, s1 = x5 (holgura), s2 = x6 (exceso), el problema P) puede ser escrito en forma equivalente como:
Min - 9x1 - 2x2 - 5x3 + 5x4 + 0x5 + 0x6
sa: 4x1 + 3x2 + 6x3 - 6x4 + x5 = 50
x1 + 2x2 - 3x3 + 3x4 - x6 = 8
2x1 - 4x2 + x3 - x4 = 5
xi >= 0, i=1,2,3,4,5,6.
EJEMPLO:
Resolver el siguiente problema de Programación Lineal utilizando el Método Simplex:
Max 40*X1 + 60*X2
s.a. 2*X1 + 1*X2 <= 70
1*X1 + 1*X2 <= 40
1*X1 + 3*X2 <= 90
X1 >= 0 X2 >= 0
¿Quién creo el método simplex?
ResponderEliminarEl método simplex fue creado por el matemático George Bernard Dantzig Ourisson
¿Cuándo se creó el método simplex?
El método del simplex fue creado en 1947 por el matemático George Dantzig
Origen del método simplex
George Bernard Dantzig Ourisson nació el 8 de Noviembre de 1914 en Portland, en el estado de Oregon de los Estados Unidos de América. Hijo de Tobías Dantzig, matemático ruso, y Anja Ourisson, lingüista francesa especializada en idiomas eslavos, quienes emigraron a EEUU en 1910, después de casarse.
George Bernard obtuvo su licenciatura en Matemáticas y Física en la Universidad de Maryland en 1936, su grado de máster en Matemáticas en la Universidad de Míchigan, y su doctorado en la Universidad de California, Berkeley en 1946. Recibió además un doctorado honorario de la Universidad de Maryland en 1976.
Reconocido por desarrollar el método simplex y es considerado como el "padre de la programación lineal". Recibió muchos honores, tales como la Medalla Nacional de Ciencia en 1975 y el premio de Teoría John von Neumann en 1974.
¿Qué es el método simplex?
Se refiere a un conjunto de métodos para resolver problemas de programación lineal, en los cuales se busca el máximo de una función lineal sobre un conjunto de variables que satisfaga un conjunto de inecuaciones lineales.
¿En qué caso se emplea el método simplex? Y cite ejemplos:
Finanzas: el problema del inversor podría ser por ejemplo una selección de mix de su cartera de inversiones. El objetivo puede ser maximizar las ganancias totales cuando las ganancias de un producto determinado dependen del método de financiación. Por ejemplo, se puede financiar con fondos internos, con deuda a corto plazo o con financiación intermedia (créditos amortizados).
Administración de Producción y Operaciones: muchas veces en las industrias de proceso, una materia prima en particular puede transformarse en una gran variedad de productos. Por ejemplo, en la industria petrolera, el crudo puede refinarse para producir nafta, kerosene, aceite para calefacciones y distintas clases de aceite para motor. Según el margen de ganancia actual de cada producto, el problema es determinar la cantidad que se debería fabricar de cada producto.
Recursos Humanos: los problemas de planificación de personal también se pueden analizar con programación lineal. Por ejemplo, en la industria telefónica, la demanda de servicios de personal de instalación y reparación son estacionales. El problema es determinar la cantidad de personal de instalación y reparación de líneas que debemos tener incorporada en la fuerza laboral por cada mes a fin de minimizar los costos totales de contratación, despido, horas extras y salarios en horas ordinarias.
Marketing: se puede utilizar la programación lineal para determinar el mix adecuado de medios de una campaña de publicidad. Por ejemplo que los medios disponibles son radio, televisión y diarios. El problema es determinar cuántos avisos hay que colocar en cada medio. Por supuesto que el costo de colocación de un aviso depende del medio elegido. El objetivo es minimizar el costo total de la campaña publicitaria, sujeto a una serie de restricciones.
Distribución: otra aplicación es el área de la distribución. Por ejemplo una determinada fábrica podría realizar envíos a cualquier cantidad de depósitos. Dado el costo del envío de una unidad del producto de cada fábrica a cada depósito, el problema es determinar el patrón de envío (cantidad de unidades que cada fábrica envía a cada depósito) que minimice los costos totales.
¿QUIEN SE PROPUSO EL METODO SIMPLEX?
ResponderEliminarGeorge Bernard Dantzig Ourisson fue un profesor, físico y matemático estadounidense, reconocido por desarrollar el método simplex y es considerado como el "padre de la programación lineal".
Un hecho real en la vida de Dantzig dio origen a una famosa leyenda en 1939, cuando era un estudiante en Berkeley.
Al comienzo de una clase a la que Dantzig acudía con retraso, el profesor Jerzy Neyman escribió en la pizarra dos ejemplos famosos de problemas estadísticos aún no resueltos.
Al llegar Dantzig a clase, pensó que los dos problemas eran tarea para casa y los anotó en su cuaderno.
¿CUÁNDO SE PROPUSO EL METODO SIMPLEX?
En 1947 donde por primera vez presentó un problema de programación lineal, y propuso el Método Simplex para resolverlo.
Cuando comenzó la Segunda Guerra Mundial, Dantzig interrumpió sus estudios en Berkeley para unirse a las Fuerza Aérea de los Estados Unidos como jefe de la Rama de Análisis de Combate de los Cuarteles Centrales Estadísticos, lo cual lo llevó a lidiar con las logísticas de la cadena de abastecimiento y gestión de cientos de miles de ítems y personas.
EN QUE CASOS SE APLICA EL METODO SINPLEX.
• Aplicación del método Simplex en investigación de operaciones y simulación.
• El método Simplex se implementa en programas de ordenador (software) y resulta transparente para el usuario, esto es, el usuario no precisa tener un conocimiento de cómo funciona.
- Logísticas de la cadena de abastecimiento y gestión de cientos de miles de ítems y personas.
VENTAJAS Y DESVENTAJAS DEL METODO SIMPLEX.
Ventajas del Método Simplex:
• Sirve para modelos con 4 o más incógnitas
Desventajas del Método Simplex:
• Difícil de aprender
• Asume que todas las variables pertenecen a |R
EJEMPLO DE METODO SIMPLEX.
ResponderEliminarCon miras a conocer la metodología que se aplica en el Método SIMPLEX, vamos a resolver el siguiente problema:
Maximizar Z= f(x,y)= 3x + 2y
sujeto a: 2x + y 18
2x + 3y 42
3x + y 24
x 0 , y 0
Se consideran las siguientes fases:
1. Convertir las desigualdades en igualdades
Se introduce una variable de holgura por cada una de las restricciones, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales:
2x + y + h = 18
2x + 3y + s = 42
3x +y + d = 24
2. Igualar la función objetivo a cero
- 3x - 2y + Z = 0
3. Escribir la tabla inicial simplex
Tabla I . Iteración nº 1
Base Variable de decisión Variable de holgura Valores solución
x y h s d
H 2 1 1 0 0 18
S 2 3 0 1 0 42
D 3 1 0 0 1 24
Z -3 -2 0 0 0 0
4. Encontrar la variable de decisión que entra en la base y la variable de holgura que sale de la base
A. Para escoger la variable de decisión que entra en la base, nos fijamos en la última fila, la de los coeficientes de la función objetivo y escogemos la variable con el coeficiente negativo mayor (en valor absoluto).
En nuestro caso, la variable x de coeficiente - 3.
La columna de la variable que entra en la base se llama columna pivote.
B. Para encontrar la variable de holgura que tiene que salir de la base, se divide cada término de la última columna (valores solución) por el término correspondiente de la columna pivote, siempre que estos últimos sean mayores que cero. En nuestro caso:
18/2 [=9] , 42/2 [=21] y 24/3 [=8]
C. En la intersección de la fila pivote y columna pivote tenemos el elemento pivote operacional, 3.
5. Encontrar los coeficientes de la nueva tabla.
Tabla II. Iteración nº 2
Base Variable de decisión Variable de holgura Valores solución
x y h s d
h 0 1/3 1 0 -2/3 2
s 0 7/3 0 1 -2/3 26
x 1 1/3 0 0 1/3 8
Z 0 -1 0 0 1 24
Como en los elementos de la última fila hay uno negativo, -1, significa que no hemos llegado todavía a la solución óptima. Hay que repetir el proceso:
A. La variable que entra en la base es y, por ser la variable que corresponde al coeficiente -1
B. Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote:
2:1/3 [=6], 26:7/3 [=78/7] y 8:1/3 [=8]
y como el menor cociente positivo es 6, tenemos que la variable de holgura que sale es h.
C. El elemento pivote, que ahora hay que hacer 1, es 1/3.
Operando de forma análoga a la anterior obtenemos la tabla:
Tabla III. Iteración nº 3
Base Variable de decisión Variable de holgura Valores solución
x y h s d
y 0 1 3 0 -2 6
s 0 0 -7 0 4 12
x 1 0 -1 0 1 6
Z 0 0 3 0 -1 30
Como en los elementos de la última fila hay uno negativo, -1, significa que no hemos llegado todavía a la solución óptima. Hay que repetir el proceso:
A. La variable que entra en la base es d, por ser la variable que corresponde al coeficiente -1
B. Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote:
6/(-2) [=-3], 12/4 [=3], y 6:1 [=6]
y como el menor cociente positivo es 3, tenemos que la variable de holgura que sale es s.
C. El elemento pivote, que ahora hay que hacer 1, es 4.
Obtenemos la tabla:
Tabla IV. Final del proceso
Base Variable de decisión Variable de holgura Valores solución
x y h s d
y 0 1 -1/2 0 0 12
d 0 0 -7/4 0 1 3
x 1 0 -3/4 0 0 3
Z 0 0 5/4 0 0 33
Como todos los coeficientes de la fila de la función objetivo son positivos, hemos llegado a la solución óptima.
Los solución óptima viene dada por el valor de Z en la columna de los valores solución, en nuestro caso: 33. En la misma columna se puede observar el vértice donde se alcanza, observando las filas correspondientes a las variables de decisión que han entrado en la base: D(3,12) http://www.investigacion-operaciones.com/SIMPLEX_analitico.htm
EL MÉTODO SIMPLEX
ResponderEliminarEl Método Simplex es un método analítico de solución de problemas de programación lineal capaz de resolver modelos más complejos que los resueltos mediante el método gráfico sin restricción en el número de variables.
El Método Simplex es un método iterativo que permite ir mejorando la solución en cada paso. La razón matemática de esta mejora radica en que el método consiste en caminar del vértice de un poliedro a un vértice vecino de manera que aumente o disminuya (según el contexto de la función objetivo, sea maximizar o minimizar), dado que el número de vértices que presenta un poliedro solución es finito siempre se hallará solución.
Fue creado en año del 1947 por el estadounidense George Bernard Dantzig y el ruso Leonid Vitalievich Kantorovich, con el ánimo de crear un algoritmo capaz de solucionar problemas de m restricciones y n variables.
EN QUÉ CASO SE EMPLEA EL MÉTODO DE SIMPLEX
El algoritmo simplex utiliza el conocido procedimiento de eliminación en la solución de ecuaciones lineales de Gauss- Jordán y, además aplica los llamados criterios del simplex con los cuales se asegura mantener la búsqueda dentro de un conjunto de soluciones factibles al problema; así valora una función económica Z, exclusivamente en vértices FACTIBLES (posibles). También se consigue con eficiencia, debido a que se dirige la búsqueda haciendo cambios a una solución básica factible adyacente, que se distingue al tener m-1 variables básicas iguales; es decir, dos vértices adyacentes sólo difieren en una variable básica; seleccionando la ruta de mayor pendiente, para mejorar el valor de Z, o por lo menos conservarlo.
Primero se presenta el método simplex, específico para un modelo de PL en forma canónica de máximo, aplicado con la conocida tabla matricial, (también identificada como tableau), lo cual se resume mediante el diagrama funcional que muestra los fundamentos del algoritmo contenidos en niveles o bloques numerados para la referencia en la descripción del mismo.
o Forma estándar.-El modelo de PL en forma canónica de máximo que se desea resolver, tiene m ecuaciones obtenidas al convertir las restricciones de desigualdad a igualdad, agregando m variables de holgura, que sumadas a las n variables de decisión, hacen un total de (m + n) incógnitas.
o Calcule una primera solución básica factible.- Del total, (m + n) variables, sólo n se igualan con cero ( n = 0 ), lo cual produce (sí existen), un número finito de soluciones básicas con un límite máximo de (m + n)! / m! n!. Estas pueden ser, factibles y no factibles; se consideran sólo las primeras.
o Se toman en cuenta sólo las soluciones básicas factibles, esto es, las que tienen todas las variables básicas >= cero; es decir, con un número de iteraciones menor a (m + n)! / m! n!, se obtienen soluciones básicas factibles: no degeneradas, si todas las incógnitas básicas son positivas y soluciones degeneradas, si al menos una variable básica es igual a cero. Se aplican los criterios del algoritmo en forma iterativa para evaluar la función objetivo en puntos extremos adyacentes que potencialmente puedan mejorar el valor Z.
o Se generan nuevas soluciones básicas factibles, tales que el valor de la función objetivo Z mejore; se repite el procedimiento (iteraciones) entre los niveles 3 y 4, hasta que ninguna solución básica factible adyacente resulte mejor; es decir, hasta que no haya incremento de valor, si el problema es de máximo, (hasta que no haya decremento, para el problema, no tratado ahora, de mínimo).
Ejemplo:
Minimizar Z = 4X1 + 12X2 + 18X3
SA:
X1 + 3X3 > 3
2X2 + 2X3 > 5
CNN:
X1, X2, X3 > 0
Maximizar Z = -4X1 - 12X2 - 18X3
SA:
-X1 - 3X3 < -3
-2X2 - 2X3 < -5
¿Quién inventó el método simplex y en qué año?
ResponderEliminarFue el estadounidense George Bernard Dantzig Ourisson quien inventó el método simplex, fue un profesor, físico y matemático, reconocido por desarrollar este método y es considerado como el "padre de la programación lineal".
El método simplex fue desarrollado en el verano del año 1947, durante una de sus clases Dantzig llego atrasado y vio dos ejemplos famosos de problemas estadísticos aún no resueltos, pensó que eran tarea y los anotó en su cuaderno, le parecieron más difíciles de lo usual y le tomo varios días resolverlos.
Definición
Es un método analítico e iterativo de solución de problemas de programación lineal, sus conceptos son básicamente geométricos siendo capaz de resolver modelos más complejos que los resueltos mediante el método gráfico sin restricción en el número de variables.
Aplicación del método simplex
Este método es importante en el área empresarial utilizada para obtener solución a los problemas en cuanto a inventario, ganancias y pérdidas permitiendo visualizar cuanto se debe vender, producir o comprar para que la empresa tenga las ganancias óptimas y suficientes para competir en el mercado.
Se usa el método simplex en investigación de operaciones y simulación.
Se implementa en programas de ordenador (software) y resulta transparente para el usuario, esto es, el usuario no precisa tener un conocimiento de cómo funciona.
Logísticas de la cadena de abastecimiento y gestión de cientos de miles de ítems y personas.
Se utiliza cuando el problema es de un tamaño suficientemente grande.
Está diseñado para problemas de programación lineal cuya matriz tiene la propiedad de diseminación (el número de no-cero es pequeño).
Hay implementaciones del método simple para la solución de problemas de programación lineal con las matrices de restricción escasa.
Ejemplo de resolución de un problema con el método simplex
Un agricultor tiene una parcela de 640m² para dedicarla al cultivo de árboles frutales: naranjos, perales, manzanos y limoneros. Se pregunta de qué forma debería repartir la superficie de la parcela entre las variedades para conseguir el máximo beneficio sabiendo que: cada naranjo necesita un mínimo de 16m², cada peral 4m², cada manzano 8m² y cada limonero 12m². Dispone de 900 horas de trabajo al año, necesitando cada naranjo 30 horas al año, cada peral 5 horas, cada manzano 10 horas, y cada limonero 20 horas. a causa de la sequía, el agricultor tiene restricciones para el riego: le han asignado 200m³ de agua anuales. Las necesidades anuales son de 2m³ por cada naranjo, 1m³ por cada peral, 1m³ por cada manzano, y 2m³ por cada limonero. los beneficios unitarios son de 50, 25, 20, y 30 € por cada naranjo, peral, manzano y limonero respectivamente.
Se determinan las variables de decisión y se representan algebraicamente. En este caso: X 1 : número de naranjos X 2 : número de perales X 3 : número de manzanos X 4 : número de limoneros
Se determinan las restricciones y se expresan como ecuaciones o inecuaciones de las variables de decisión. Dichas restricciones se deducen de las necesidades de cada árbol de terreno, horas de trabajo anuales, y necesidades de riego: Necesidades de terreno: 16•X 1 + 4•X 2 + 8•X 3 + 12•X 4 ≤ 640 Necesidades de horas anuales: 30•X 1 + 5•X 2 + 10•X 3 + 20•X 4 ≤ 900 Necesidades de riego: 2•X 1 + X 2 + X 3 + 2•X 4 ≤ 200
Se expresan todas las condiciones implícitamente establecidas por la naturaleza de las variables: que no puedan ser negativas, que sean enteras, que solo puedan tomar determinados valores. En este caso las restricciones son que el número de árboles no puede ser negativo y además debe ser un número entero: X i ≥ 0 X i son enteros Se determina la función objetivo: Maximizar Z = 50•X 1 + 25•X 2 + 20•X 3 + 30•X 4
NOMBRE: LUDYS ROJAS
ResponderEliminar¿QUIEN Y CUANDO SE PROPUSO EL METODO SIMPLEX?
El Método Simplex publicado por George Dantzig en 1947 consiste en un algoritmo iterativo que secuencialmente a través de iteraciones se va aproximando al óptimo del problema de Programación Lineal en caso de existir esta última.
La primera implementación computacional del Método Simplex es el ano 1952 para un problema de 71 variables y 48 ecuaciones. Su resolución tarda 18 horas. Luego, en 1956, un código llamado RSLP1, implementado en un IBM con 4Kb en RAM, admite la resolución de modelos con 255 restricciones.
El Método Simplex hace uso de la propiedad de que la solución óptima de un problema de Programación Lineal se encuentra en un vértice o frontera del dominio de puntos factibles (esto último en casos muy especiales), por lo cual, la búsqueda secuencial del algoritmo se basa en la evaluación progresiva de estos vértices hasta encontrar el óptimo. Cabe destacar que para aplicar el Método Simplex a un modelo lineal, este debe estar en un formato especial conocido como formato estándar el cual definiremos a continuación.
El Nacimiento de la Programación Lineal
Cuando comenzó la Segunda Guerra Mundial, los estudios de Dantzig en Berkeley fueron suspendidos, y el se convirtió en la cabeza de la Rama de Análisis de Combate de los Cuarteles Centrales Estadísticos de Fuerza Aérea de los Estados Unidos, lo cual lo llevó a lidiar con las logísticas de la cadena de abastecimiento y gestión de cientos de miles de ítems y personas. El trabajo proporcionó los problemas del "mundo real" que la programación lineal vendría a resolver.
George Dantzig recibió su doctorado en Berkeley en 1946. Él originalmente iba a aceptar un puesto como profesor en Berkeley, pero fue persuadido por su esposa y colegas del Pentágono para volver ahí como consejero matemático de la USAF. Fue ahí, en 1947 que el por primera vez presentó un problema de programación lineal, y propuso el Método Simplex para resolverlo. En 1952 se convirtió en un investigador matemático en la Corporación RAND, donde comenzó a implementar la programación lineal en los computadores de la corporación. En 1960 fue contratado por su alma máter, donde enseñó ciencias de la computación, eventualmente convirtiéndose en el presidente del Centro de Investigación de Operaciones. En 1966 tomó un cargo similar en la Universidad de Stanford. Se quedó en Standord hasta su retiro en los años 90.
En adición a su trabajo significativo en el desarrollo del método simplex y la programación lineal, Dantzig también hizo avances en los campos de la teoría de la descomposición, análisis de sensibilidad, métodos de pívot complementarios, optimización a gran escala, programación no lineal, y programación bajo incertidumbre. El primer ejemplar del SIAM Jornal on Optimiza tión en 1991 fue dedicado a él. Una aplicación típica del método simplex dual es en la resolución de problemas con una función objetivo de minimización, con restricciones del tipo mayor o igual y donde las variables de decisión son mayores o iguales a cero.
Utilizado para determinar la nutrición, vitaminas, etc de una persona en general.
EliminarEJEMPLO 1
Siendo Xi la cantidad a producir del producto i.
Maximizar Z = X1 + X2 {Ganancia total en soles}
S.A.
5X1 + 3X2 <= 15 {Horas disponibles dep. A}
3X1 + 5X2 <= 15 {Horas disponibles dep. B}
Xj >= 0 ; j = 1, 2
Los problemas de Maximización, con todas sus restricciones <= y con la condición de no negatividad, se le llama Forma Estándar ó Forma Normal
Aquí debemos conseguir una solución básica factible, empleando las variables de holgura y/o artificiales, quedando el sistema de ecuaciones así:
Maximizar Z = X1 + X2
S.A.
5X1 + 3X2 + X3 = 15
3X1 + 5X2 + X4 = 15
Xj >= 0 ; j = 1,2,3,4
Las variables básicas son aquellas cuyos coeficientes forman la matriz unitaria.
En este caos accidentalmente son las variables de holgura X3 y X4.
A continuación construimos la siguiente tabla:
Cj 1 1 0 0 b/a
a>0
V.B. b X1 X2 X3 X4
0 X3 15 5 3 1 0 15/5=3
0 X4 15 3 5 0 1 15/3=5
Zj - Cj 0 -1 -1 0 0
El valor de la función objetivo Z, se encuentra frente a la casilla de Zj – Cj , en éste caso vale cero (0) y se calcula multiplicando el vector fila (en la tabla es la columna inmediatamente anterior a la de las variables básica V.B.) que contiene los coeficientes de las variables básicas en la función objetiva original por el vector columna de los términos independientes b
EliminarCXB = Vector fila de los coeficientes en la función objetivo original de las variables básicas actuales, sus valores se encuentran en la primera columna del tablero.
b = Vector columna de los términos independientes de las restricciones, que al mismo tiempo son los valores de las variables básicas actuales, sus valores se encuentran bajo la columna denominada b
CXB = (0,0) ; b = (15,15)" Z = CXB * b = (0)(15) + (0)(15) = 0
El valor de los Zj – Cj se calcula multiplicado el vector fila CXB por el vector apuntador aj dela columna de la variable j-ésima, menos el Cj, esto es:
Zj – Cj = CXB. aj – Cj ;
Los cálculos se efectúan así:
Z1 – C1 = CXB a1 – C1 = (0,0).(5,3)" - 1 = (0)(5)+(0)(3) – 1 = -1
Z2 – C2 = CXB a2 – C2 = (0,0).(3,5)" - 1 = (0)(3)+(0)(5) – 1 = -1
Z3 – C3 = CXB a3 – C3 = (0,0).(1,0)" - 0 = (0)(1)+(0)(0) – 0 = 0
Z4 – C4 = CXB a4 – C4 = (0,0).(0,1)" - 0 = (0)(0)+(0)(1) – 0 = 0
La variable que tiene Zj-Cj más negativo es ó X1 ó X2. Se escoge al azar X1.
En esta iteración b/a da: 15/5 = 3 y 15/3 = 5;
Lo que significa que la variable básica X3 restringe el crecimiento de la variable que entra, X1, hasta 3 (no la deja tomar valores superiores a 3) y la variable básica X4 restringe el crecimiento de la variable que entra X1 hasta 5 (no la deja tomar valores superiores a 5).
Por supuesto la variable básica que restringe más el crecimiento de la variable que entra X1, es X3 ,
Por lo tanto, es la variable básica escogida para salir.
La fila de la variable básica escogida para salir se divide por el elemento que se encuentra en la intersección de dicha fila con la columna de la variable que entra, la fila resultante es la fila pivote y se coloca en un nuevo tablero, desde el que se suman múltiplos de la fila pivote a las demás filas del tablero anterior de tal forma que se eliminen de cada una de ellas la variable escogida para entrar, en nuestro caso X1 , este procedimiento se denomina, hacer un uno (1) en la intersección y el resto de la columna ceros (0), por lo tanto en dicha columna aparecerá un vector unitario, el procedimiento se repite en cada iteración, hasta que todos los Zj – Cj sean mayores ó iguales a cero en el caso de maximizar ó menores ó iguales a cero en el caso de minimizar.
A continuación se muestran todas las iteraciones y en cada fila los valores por los cuales fueron multiplicadas para ser sumadas a otras filas, ello se expresa como sumar múltiplos de una fila a otra.
Fíjese que se suman múltiplos de las restricciones a la función objetivo para eliminar las variables básicas de ella.
Cj 1 1 0 0 b/a
a>0
V.B. b X1 X2 X3 X4
1 X1 3 1 3/5 1/5 0 5
0 X4 6 0 16/5 -3/5 1 15/8
Zj - Cj 3 0 -2/5 1/5 0
EliminarVariable que entra X2
Variable que sale X4
Cj 1 1 0 0 b/a
a>0
V.B. b X1 X2 X3 X4
1 X1 15/8 1 0 5/16 0
1 X2 15/8 0 1 -3/16 5/16
Zj – Cj 15/4 0 0 1/8 1/8
Solución óptima:
X1* = 15/8
X2* = 15/8
Z * = 15/4
La solución es única: X1 * = 15/8 ; X2 * = 15/8 ; Z* = 14/4
Ejemplo 2
Minimizar Z = 6X1 + 4X2 + 2X3
S.A.
6X1 + 2X2 + 6X3 >= 6
6X1 + 4X2 = 12
2X1 - 2X2 <= 2
Xj >= 0 ; j = 1, 2, 3
Minimizar Z = 6X1 + 4X2 + 2X3 + MX5 + MX6
S.A.
6X1 + 2X2 + 6X3 – X4 + X5 = 6
6X1 + 4X2 +X6 = 12
2X1 - 2X2 +X7 = 2
Xj >= 0 ; j = 1, 2, 3, 4, 5, 6, 7
Las variables básicas son X5 = 6 , X6 = 12, X7 = 2
Solución Óptima:
Variables de decisión:
X1 = 0 , X2 = 3 , X3 = 0 , Z = 12
Variables de holgura : X4 = 0 , X7 = 8
Variables artificiales: X5 = 0 , X6 = 0
METODO SIMPLEX: El método simplex fue inventado por George Dantzig en 1947, fue en el verano de 1947. El primer problema práctico que se resolvió con este método fue uno de nutrición. El Método Simplex es una técnica popular para dar soluciones numéricas del problema de la programación lineal. Es un método numérico para optimización de problemas libres multidimensionales perteneciente a la clase más general de algoritmos de búsqueda, en el cual sirve para resolver problemas de programación lineal.
ResponderEliminarEl método Simplex se emplea en un procedimiento iterativo que permite mejorar la solución de la función objetivo en cada paso. El proceso concluye cuando no es posible continuar mejorando dicho valor, es decir, se ha alcanzado la solución óptima (el mayor o menor valor posible, según el caso, para el que se satisfacen todas las restricciones).
Resolver mediante el método simplex el siguiente problema:
Maximizar Z = f(x,y) = 3x + 2y
sujeto a: 2x + y ≤ 18
2x + 3y ≤ 42
3x + y ≤ 24
x ≥ 0 , y ≥ 0
Se consideran las siguientes fases:
Realizar un cambio de variables y normalizar el signo de los términos independientes. Se realiza un cambio en la nomenclatura de las variables. Estableciéndose la correspondencia siguiente:
x pasa a ser X1
y pasa a ser X2
Como los términos independientes de todas las restricciones son positivos no es necesario hacer nada. En caso contrario habría que multiplicar por "-1" en ambos lados de la inecuación.
Normalizar las restricciones.
Se convierten las inecuaciones en ecuaciones agregando variables de holgura, exceso y artificiales según la tabla siguiente:
Tipo de desigualdad Tipo de variable que aparece
≥ - exceso + artificial
= + artificial
≤ + holgura
En este caso se introduce una variable de holgura (X3, X4 y X5) en cada una de las restricciones del tipo ≤, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales:
Eliminar2•X1 + X2 + X3 = 18
2•X1 + 3•X2 + X4 = 42
3•X1 + X2 + X5 = 24
Igualar la función objetivo a cero.
Z - 3•X1 - X2 - 0•X3 - 0•X4 - 0•X5 = 0
Escribir la tabla inicial del método Simplex.
La tabla inicial del método Simplex está compuesta por todos los coeficientes de las variables de decisión del problema original y las de holgura, exceso y artificiales agregadas en el paso 2 (en las columnas, siendo P0 el término independiente y el resto de variables Pi coinciden con Xi), y las restricciones (en las filas). La columna Cb contiene los coeficientes de las variables que se encuentran en la base.
La primera fila está formada por los coeficientes de la función objetivo, mientras que la última fila contiene el valor la función objetivo y los costes reducidos Zj - Cj.
La última fila se calcula como sigue: Zj = Σ(Cbi•Pj) para i = 1..m, donde si j = 0, P0 = bi y C0 = 0, y en caso contrario Pj = aij. Aunque al tratarse de la primera tabla del método Simplex y ser todos los Cb nulos se puede simplificar el cálculo, y por esta vez disponer Zj = -Cj.
Tabla I . Iteración nº 1
3 2 0 0 0
Base Cb P0 P1 P2 P3 P4 P5
P3 0 18 2 1 1 0 0
P4 0 42 2 3 0 1 0
P5 0 24 3 1 0 0 1
Z 0 -3 -2 0 0 0
Condición de parada.
Si el objetivo es la maximización, cuando en la última fila (fila indicadora) no existe ningún valor negativo entre los costes reducidos (columnas P1 en adelante) se alcanza la condición de parada.
En tal caso se llega al final del algoritmo ya que no existe posibilidad de mejora. El valor de Z (columna P0) es la solución óptima del problema.
Otro caso posible es que en la columna de la variable entrante a la base todos los valores son negativos o nulos. Esto indica que el problema no se encuentra acotado y su solución siempre resultará mejorable. Ante esta situación no es necesario continuar iterando indefinidamente y también se puede dar por finalizado el algoritmo.
De no ser así, se ejecutan los siguientes pasos de forma iterativa.
Elección de la variable entrante y saliente de la base.
Se determina en primer lugar la variable que entra en la base. Para ello se escoge la columna cuyo valor en la fila Z sea el menor de entre todos los negativos. En este caso sería la variable X1 (P1) de coeficiente -3.
Si existiesen dos o más coeficientes iguales que cumplan la condición anterior (caso de empate), entonces se optará por aquella variable que sea básica. La columna de la variable que entra en la base se llama columna pivote.
Una vez obtenida la variable que entra en la base, se procede a determina cual será la variable que sale de la misma. La decisión se toma en base a un sencillo cálculo: dividir cada término independiente (columna P0) entre el elemento correspondiente de la columna pivote, siempre que ambos elementos sean estrictamente positivos (mayores que cero). Se escoge la fila cuyo resultado haya resultado mínimo. Si hubiera algún elemento menor o igual a cero no se realiza dicho cociente. En caso de que todos los elementos de la columna pivote fueran de ésta condición se habría cumplido la condición de parada y el problema tendría una solución no acotada.
EliminarEn este ejemplo: 18/2 [=9] , 42/2 [=21] y 24/3 [=8]
El término de la columna pivote que en la división anterior dio lugar al menor cociente positivo indica la fila de la variable de holgura que sale de la base. En este caso resulta ser X5 (P5), de coeficiente 3. Esta fila se llama fila pivote.
La intersección de la fila pivote y columna pivote marca el elemento pivote, en este caso el 3.
Actualizar la tabla.
Los nuevos coeficientes de la tabla se calculan de la siguiente manera:
En la fila del elemento pivote cada nuevo elemento se calcula como:
Nuevo Elemento Fila Pivote = Anterior Elemento Fila Pivote / Pivote
En el resto de las filas cada elemento se calcula:
Nuevo Elemento Fila = Anterior Elemento Fila - (Anterior Elemento Fila en Columna Pivote * Nuevo Elemento Fila Pivote)
Con esto se normaliza el elemento pivote y su valor pasa a ser 1, mientras que el resto de elementos de la columna pivote se anulan.
Se muestran a continuación los cálculos para la fila P4:
Anterior fila P4 42 2 3 0 1 0
- - - - - -
Anterior Elemento Fila en Columna Pivote 2 2 2 2 2 2
x x x x x x
Nueva fila pivote 8 1 1/3 0 0 1/3
= = = = = =
Nueva fila P4 26 0 7/3 0 1 -2/3
La tabla correspondiente a esta segunda iteración es:
Tabla II . Iteración nº 2
3 2 0 0 0
Base Cb P0 P1 P2 P3 P4 P5
P3 0 2 0 1/3 1 0 -2/3
P4 0 26 0 7/3 0 1 -2/3
P1 3 8 1 1/3 0 0 1/3
Z 24 0 -1 0 0 1
Al comprobar la condición de parada se observa que no se cumple ya que entre los elementos de la última fila hay uno negativo, -1. Se continúa iterando nuevamente los pasos 4, 5 y 6.
La variable que entra en la base es X2 (P2), por ser la variable que corresponde a la columna donde se encuentra el coeficiente -1.
Para calcular la variable que sale, se dividen los términos de la columna P0 entre los términos correspondientes de la nueva columna pivote: 2 / 1/3 [=6] , 26 / 7/3 [=78/7] y 8 / 1/3 [=24]. Como el menor cociente positivo es 6, la variable que sale de la base es X3 (P3).
El elemento pivote es 1/3.
Actualizando nuevamente los valores de la tabla se obtiene:
Tabla III . Iteración nº 3
3 2 0 0 0
Base Cb P0 P1 P2 P3 P4 P5
P2 2 6 0 1 3 0 -2
P4 0 12 0 0 -7 1 4
P1 3 6 1 0 -1 0 1
Z 30 0 0 3 0 -1
Una nueva comprobación de la condición de parada revela que entre los elementos de la fila indicadora vuelve a haber uno negativo, -1. Significa que aun no se ha llegado a la solución óptima y hay que seguir iterando (pasos 4, 5 y 6):
ResponderEliminarLa variable que entra en la base es X5 (P5), por ser la variable que corresponde al coeficiente -1.
Se escoge la variable que sale calculando el cociente entre los términos de la columna de términos independientes y los términos correspondientes de la nueva columna pivote: 6/(-2) [=-3] , 12/4 [=3], y 6/1 [=6]. En esta ocasión es X4 (P4).
El elemento pivote es 4.
Después de actualizar todas las filas, se obtiene la tabla siguiente:
Tabla IV . Iteración nº 4
3 2 0 0 0
Base Cb P0 P1 P2 P3 P4 P5
P2 2 12 0 1 -1/2 1/2 0
P5 0 3 0 0 -7/4 1/4 1
P1 3 3 1 0 3/4 -1/4 0
Z 33 0 0 5/4 1/4 0
Fin del algoritmo.
Se observa que en la última fila todos los coeficientes son positivos cumpliéndose, por tanto la condición de parada.
La solución óptima viene dada por el valor de Z en la columna de los términos independientes (P0), en este ejemplo: 33. En la misma columna se puede ver el punto donde se alcanza, observando las filas correspondientes a las variables de decisión que han entrado en la base: X1 = 3 y X2 = 12.
Deshaciendo el cambio de variables se obtiene x = 3 e y = 12.
NOMBRE: VANESSA CALVO
EliminarEl Método Simplex consiste en un algoritmo iterativo que secuencialmente a través de iteraciones se va aproximando al óptimo del problema de Programación Lineal en caso de existir esta última, hace uso de la propiedad de que la solución óptima de un problema de Programación Lineal se encuentra en un vértice o frontera del dominio de puntos factibles (esto último en casos muy especiales), por lo cual, la búsqueda secuencial del algoritmo se basa en la evaluación progresiva de estos vértices hasta encontrar el óptimo. Cabe destacar que para aplicar el Método Simplex a un modelo lineal, este debe estar en un formato especial conocido como formato estándar el cual definiremos a continuación.
FORMA ESTÁNDAR DE UN MODELO DE PROGRAMACIÓN LINEAL
Consideremos un modelo de Programación Lineal en su forma estándar, que denotaremos en lo que sigue por:
* Min c1x1 + c2x2 + … + cnxn
* sa a11x1 + a12x2 + … + a1nxn = b1
* a21x1 + a22x2 + … + a2nxn = b2
* … … …
* am1x1 + am2x2 + … + amnxn = bm
* xi >= 0, i = 1, 2, …, n y m <= n
*
Matricialmente escrito como:
Min cTx
s.a Ax = b
x >= 0
Aplicación del método simplex
La aplicación del método simplex se utiliza cuando el problema es de un tamaño suficientemente grande está diseñado para problemas de programación lineal cuya matriz tiene la propiedad de diseminación
NOMBRE: VANESSA CALVO
ResponderEliminarEl Método Simplex publicado por George Dantzig en 1947 La primera implementación computacional del Método Simplex es el año 1952 para un problema de 71 variables y 48 ecuaciones. Su resolución tarda 18 horas.
QUIEN Y CUANDO CREO EL METODO SIMPLEX
ResponderEliminarFue creado por George Bernard Dantzig fue un profesor, físico y matemático estadounidense, reconocido por desarrollar el método simplex y es considerado como el "padre de la programación lineal". Recibió muchos honores, tales como la Medalla Nacional de Ciencia en 1975 y el premio de Teoría John von Neumann en 1974.
El procedimiento de optimización, en el método Simplex, comienza por la elección de la n+1 puntos donde será hecha la evaluación de la respuesta. Este resultado será evaluado contra las demás respuestas para que el proceso pueda continuar, siendo que este tipo de desarrollo convierte al simplex en un método del tipo secuencial.
El metodo simplex es un procedimiento es repetido sucesivamente, descartándose la peor respuesta. Por lo tanto, como vemos, el objetivo del método Simplex secuencial es forzar al simplex a moverse para la región de respuesta óptima.
Las decisiones requeridas para que eso sea posible constituyen las llamadas "reglas" del procedimiento simplex.
COMO SE UTILIZA EL MÉTODO SIMPLEX PARA LA SOLUCION DE PROBLEMAS DE PROGRAMACIÓN LINEAL
Es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución.
Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución.
El método del simplex se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta.
EJEMPLO
ResponderEliminarResolver el siguiente problema de Programación Lineal utilizando el Método Simplex:
Max 40*X1 + 60*X2
s.a. 2*X1 + 1*X2 <= 70
1*X1 + 1*X2 <= 40
1*X1 + 3*X2 <= 90
X1 >= 0 X2 >= 0
Para poder aplicar el Método Simplex, es necesario llevar el modelo a su formato estándar, para lo cual definimos X3, X4, X5 >= 0 como las respectivas variables de holgura para la restricción 1, 2 y 3. De esta forma queda definida la tabla inicial del método de la siguiente forma:
X1 X2 X3 X4 X5
2 1 1 0 0 70
1 1 0 1 0 40
1 3 0 0 1 90
-40 -60 0 0 0 0
En esta situación, las variables de holgura definen una solución básica factible inicial, condición necesaria para la aplicación del método. Luego, se verifican los costos reducidos de las variables no básicas (X1 y X2 en la tabla inicial) y se escoge como variable que entra a la base aquella con el costo reducido "más negativo". En este caso, X2.
Luego, para escoger que variable básica deja la base debemos buscar el mínimo cuociente entre el lado derecho y los coeficientes asociados a la variable entrante en cada fila (para aquellos coeficientes > 0 marcados en rojo en la tabla anterior). El mínimo se alcanza en Min {70/1, 40/1, 90/3} = 30 asociado a la tercera fila, el cual corresponde a la variable básica actual X5, en consecuencia, X5 deja la base. En la posición que se alcanza el mínimo cuociente lo llamaremos "Pivote" (marcado con rojo) el cual nos servirá para realizar las respectivas operaciones filas, logrando la siguiente tabla al cabo de una iteración:
X1 X2 X3 X4 X5
5/3 0 1 0 -1/3 40
2/3 0 0 1 -1/3 10
1/3 1 0 0 1/3 30
-20 0 0 0 20 1800
El valor de la función objetivo luego de una iteración ha pasado de 0 a 1.800. Se recomienda al lector hacer una representación gráfica del problema y notar como las soluciones factibles del método corresponden a vértices del dominio de puntos factibles.
La actual tabla no corresponde a la solución óptima del problema P) debido a que existe una variable no básica con costo reducido negativo, por tanto X1 entra a la base. Posteriormente, mediante el criterio del mínimo cuociente calculamos la variable que debe dejar la base: Min {40/(5/3), 10/(2/3), 30/(1/3)} = 15, asociado a la fila 2 (variable básica actual X4), por tanto X4 deja la base. Obtenido lo anterior se aplica una iteración del método:
X1 X2 X3 X4 X5
0 0 1 -5/2 1/2 15
1 0 0 3/2 -1/2 15
0 1 0 -1/2 1/2 25
0 0 0 30 10 2100
Finalmente se alcanza la solución óptima del problema P) y se verifica que los costos reducidos asociados a las variables no básicas (X4 y X5 son mayores o iguals que cero). Notése que la existencia de un costo reducido igual a cero para una variable no básica en esta etapa define un problema con "infinitas soluciones".
La solución alcanzada es X1* = 15, X2* = 25 con V(P*) = 2.100. Adicionalmente, los costos reducidos asociados a las variables no básicas definen el precio sombra asociado a las restricciones 1, 2 y 3, respectivamente, lo cual es equivalente a la obtención del precio sombra mediante el método gráfico. Dejaremos para una posterior presentación, la forma de calcular el intervalo de variación para el lado derecho que permite la validez del precio sombra, utilizando la tabla final del Método Simplex.
EJEMPLO
ResponderEliminarMax 9u + 2v + 5z
sa 4u + 3v + 6z <= 50
u + 2v - 3z >= 8
2u - 4v + z = 5
u,v >= 0
z e IR
1. Siempre es posible llevar un problema de maximización a uno de minimización. Si f(x) es la función objetivo a maximizar yx* es la solución óptima f(x*) >= f(x), para todo x factible. -f(x*) <= - f(x), para todo x factible. En consecuencia: x* es también mínimo de -f(x)
2. Cada restricción del tipo <= puede ser llevada a una ecuación de igualdad usando una (nueva) variable de holgurano negativa, con coeficiente nulo en la función objetivo.
3. Cada restricción del tipo >= puede ser llevada a una ecuación de igualdad usando una (nueva) variable de exceso no negativa, con coeficiente nulo en la función objetivo.
4. Siempre es posible escribir una variable libre de signo como la diferencia de dos variables no negativas.
Considerando la siguiente notación: u = x1, v = x2, z = x3 - x4, s1 = x5 (holgura), s2 = x6 (exceso), el problema P) puede ser escrito en forma equivalente como:
Min - 9x1 - 2x2 - 5x3 + 5x4 + 0x5 + 0x6
sa: 4x1 + 3x2 + 6x3 - 6x4 + x5 = 50
x1 + 2x2 - 3x3 + 3x4 - x6 = 8
2x1 - 4x2 + x3 - x4 = 5
xi >= 0, i=1,2,3,4,5,6.
UNIVERSIDAD TECNICA DE COTOPAXI
ResponderEliminarEXTENSION LA MANA
NOMBRE: WALTER GUANOQUIZA
¿QUIÉN Y CUÁNDO SE PROPUSO EL MÉTODO SIMPLEX PARA LA RESOLUCIÓN DE PROBLEMAS DE PROGRAMACIÓN LINEAL? ¿Y EN QUÉ CASOS SE APLICA ESTE MÉTODO, CITE EJEMPLOS?
¿Quién creo el método simplex?
Fue George Bernard Dantzig, nació el 8 de Noviembre de 1914 en Portland, en el estado de Oregón de los Estados Unidos de América.
¿CUÁNDO SE PROPUSO EL MÉTODO SIMPLEX PARA LA RESOLUCIÓN DE PROBLEMAS DE PROGRAMACIÓN LINEAL?
George Dantzig se doctoró en Berkeley en 1946. Inicialmente iba a aceptar un puesto como profesor en Berkeley, pero fue persuadido por su esposa y colegas del Pentágono para volver a las Fuerzas Aéreas como consejero matemático de la USAF. Fue ahí, en 1947 donde por primera vez presentó un problema de programación lineal, y propuso el Método Simplex para resolverlo. En 1952 se convirtió en investigador matemático en la Corporación RAND,en cuyos ordendadores comenzó a implementar la programación lineal. En 1960 fue contratado por su alma máter, donde enseñó ciencias de la computación, convirtiéndose en presidente del Centro de Investigación de Operaciones.
¿EN QUÉ CASOS DE APLICA ESTE MÉTODO?
• La aplicación del método del Simplex, se utiliza cuando el problema es de un tamaño suficientemente grande.
• Está diseñado para problemas de programación lineal cuya matriz tiene la propiedad de diseminación (el número de no-cero es pequeño).
• Hay implementaciones del método simple para la solución de problemas de programación lineal con las matrices de restricción escasa.
• Se han desarrollado diversas variantes del método simplex que tienen en cuenta las particularidades de las diversas clases especiales de problemas de programación lineal (problemas de bloque, los problemas de transporte y otros).
CONDICIONES
• El objetivo es de la forma de maximización o de minimización.
• Todas las restricciones son de igualdad.
• Todas las variables son no negativas.
• Las constantes a la derecha de las restricciones son no negativas.
EJEMPLO
ResponderEliminarUn agricultor tiene una parcela de 640m² para dedicarla al cultivo de árboles frutales: naranjos, perales, manzanos y limoneros. Se pregunta de qué forma debería repartir la superficie de la parcela entre las variedades para conseguir el máximo beneficio sabiendo que:
• cada naranjo necesita un mínimo de 16m², cada peral 4m², cada manzano 8m² y cada limonero 12m².
• dispone de 900 horas de trabajo al año, necesitando cada naranjo 30 horas al año, cada peral 5 horas, cada manzano 10 horas, y cada limonero 20 horas.
• a causa de la sequía, el agricultor tiene restricciones para el riego: le han asignado 200m³ de agua anuales. Las necesidades anuales son de 2m³ por cada naranjo, 1m³ por cada peral, 1m³ por cada manzano, y 2m³ por cada limonero.
Los beneficios unitarios son de 50, 25, 20, y 30 € por cada naranjo, peral, manzano y limonero respectivamente
resolver el siguiente problema:
Maximizar Z= f(x ,y)= 3x + 2y
sujeto a: 2x + y 1
2x + 3y 42
3x + y 24
x 0 , y 0
Se consideran las siguientes fases:
1. Convertir las desigualdades en igualdades
Se introduce una variable de holgura por cada una de las restricciones, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales:
2x + y + h = 18
2x + 3y + s = 42
3x +y + d = 24
2. Igualar la función objetivo a cero
- 3x - 2y + Z = 0
3. Escribir la tabla inicial simplex
Tabla I . Iteración nº 1
Base Variable de decisión Variable de holgura Valores solución
x y h s d
H 2 1 1 0 0 18
S 2 3 0 1 0 42
D 3 1 0 0 1 24
Z -3 -2 0 0 0 0
4. Encontrar la variable de decisión que entra en la base y la variable de holgura que sale de la base
A. Para escoger la variable de decisión que entra en la base, nos fijamos en la última fila, la de los coeficientes de la función objetivo y escogemos la variable con el coeficiente negativo mayor (en valor absoluto).
En nuestro caso, la variable x de coeficiente - 3.
La columna de la variable que entra en la base se llama columna pivote.
B. Para encontrar la variable de holgura que tiene que salir de la base, se divide cada término de la última columna (valores solución) por el término correspondiente de la columna pivote, siempre que estos últimos sean mayores que cero. En nuestro caso:
18/2 [=9] , 42/2 [=21] y 24/3 [=8]
C. En la intersección de la fila pivote y columna pivote tenemos el elemento pivote operacional, 3.
5. Encontrar los coeficientes de la nueva tabla.
Tabla II. Iteración nº 2
Base Variable de decisión Variable de holgura Valores solución
x y h s d
h 0 1/3 1 0 -2/3 2
s 0 7/3 0 1 -2/3 26
x 1 1/3 0 0 1/3 8
Z 0 -1 0 0 1 24
Como en los elementos de la última fila hay uno negativo, -1, significa que no hemos llegado todavía a la solución óptima. Hay que repetir el proceso:
A. La variable que entra en la base es y, por ser la variable que corresponde al coeficiente -1
B. Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote:
Como en los elementos de la última fila hay uno negativo, -1, significa que no hemos llegado todavía a la solución óptima. Hay que repetir el proceso:
A. La variable que entra en la base es d, por ser la variable que corresponde al coeficiente -1
B. Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote:
6/(-2) [=-3], 12/4 [=3], y 6:1 [=6]
y como el menor cociente positivo es 3, tenemos que la variable de holgura que sale es s.
C. El elemento pivote, que ahora hay que hacer 1, es 4.
Obtenemos la tabla:
Tabla IV. Final del proceso
Base Variable de decisión Variable de holgura Valores solución
x y h s d
y 0 1 -1/2 0 0 12
d 0 0 -7/4 0 1 3
x 1 0 -3/4 0 0 3
Z 0 0 5/4 0 0 33
Como todos los coeficientes de la fila de la función objetivo son positivos, hemos llegado a la solución óptima.
La solución óptima viene dada por el valor de Z en la columna de los valores solución, en nuestro caso: 33
¿QUIÉN Y CUÁNDO SE PROPUSO EL MÉTODO SIMPLEX PARA LA RESOLUCIÓN DE PROBLEMAS DE PROGRAMACIÓN LINEAL?
ResponderEliminarEste modelo fue creado por George Bernard Dantzig nacido el 8 de noviembre de 1914.
Inicialmente iba a aceptar un puesto como profesor en Berkeley, pero fue persuadido por su esposa y colegas del Pentágono para volver a las Fuerzas Aéreas como consejero matemático de la USAF. Fue ahí, en 1947 donde por primera vez presentó un problema de programación lineal, y propuso el Método Simplex para resolverlo.
¿Y EN QUÉ CASOS DE APLICA ESTE MÉTODO, CITE EJEMPLOS?
1. DEGENERACION
En la aplicación de la condición de factibilidad, una coincidencia de la razón mínima se debe descomponer en forma arbitraria para los fines de determinar la variable que sale. Cuando suceda esto una o más veces de las variables básicas, será necesariamente igual a cero en la siguiente iteración.
Ejemplo (Solución óptima degenerada)
Maximizar z = 3x1 +9x2
Sujeto a
x1 + 4x2 £ 8
x1 + 2x2 £ 4
x1,x2 ³ 0
2. OPCIONES ÓPTIMAS.
Cuando la función objetivo es paralela a una restricción de enlace (o sea, una restricción que se satisface en el sentido de la igualdad a través de la solución óptima), la función objetivo tomara el mismo valor optimo en más de un punto de solución.
Ejemplo (Infinidad de soluciones)
Maximizar z = 2x1 + 4x2
Sujeto a
x1 + x2 £ 5
x1 + x2£ 4
x1, x2³ 0
3. SOLUCION NO ACOTADA
ResponderEliminarEn algunos modelos de programación lineal los valores de las variables se pueden aumentar en forma indefinida sin violar ninguna de las restricciones, lo que significa que el espacio de soluciones es no acotado cuando menos en una dirección. Como resultado, el valor de la función objetivo puede crecer (caso de maximización) o de crecer (caso de minimización) en forma indefinida. En este caso decimos que el espacio de soluciones y el valor "óptimo" de la función objetivo son no acotados.
La falta de explicación en un modelo puede señalar solo una cosa: el modelo está mal construido. Evidentemente resulta irracional hacer que un modelo produzca una ganancia " infinita". Las irregularidades más probables en estos modelos son: 1) No se toman en cuenta unas más restricciones redundantes, y 2) No se determinan correctamente los parámetros (constantes) de algunas restricciones.
La regla general para reconocer la falta de acotación es la siguiente. Sien cualquier iteración los coeficientes de las restricciones de una variable no básica son no positivos, entonces el espacio de soluciones no está acotado en esa dirección. Además, si el coeficiente de la función objetivo de esa variable en el caso de la maximización o positivo en el caso de la minimización, entonces el valor de la función objetivo tampoco está acotado.
Ejemplo (Función objetivo no acotada)
Maximizar z = 2x1 + x2
Sujeto a
x1 - x2 £ 10
2x1 £ 40
x1, x2 ³ 0
4. SOLUCION INFACTIBLE
Si las restricciones no se pueden satisfacer en forma simultánea, se dice que el modelo no tiene solución factible. Esta situación nunca puede ocurrir si todas las restricciones son del tipo (suponiendo constantes no negativas en el segundo miembro) ya que la variable de holgura produce siempre alguna solución factible. Sin embargo, cuando empleamos los otros tipos de restricciones, recurrimos al uso de variables artificiales que, por su mismo diseño, no ofrecen una solución factible al modelo original. Aunque se toman medidas (a través del uso de la penalización) para hacer que las variables artificiales sean cero en el nivel óptimo, esto sólo puede ocurrir si el modelo tiene un espacio factible. Si no lo tiene, cuando menos una variable artificial será positiva en la iteración óptima. Esta es nuestra indicación que el problema no tiene solución factible.
Desde el punto de vista práctico un espacio infectable apunta a la posibilidad de que el modelo no se haya formulado correctamente en virtud de que las restricciones estén en conflicto. También es posible que las restricciones no estén destinadas a cumplirse en forma simultánea, en este caso, quina se necesite una estructura del modelo totalmente deferente que no admita todas las restricciones al mismo tiempo.
Ejemplo de espacio de (solución infactible)
Maximizar z = 3x1 + 2x2
Sujeto a
2x1 + x2 £ 2
3x1 + 4x2 ³ 12
x1, x2 ³ 0
TAREA:1
ResponderEliminarNOMBRE: MARIANA MIRANDA
¿Quién fue el que invento el método simple para la resolución de los problemas de programación lineal?
Fue George Bernard Dantzig, nació el 8 de Noviembre de 1914 en Portland, en el estado de Oregón de los Estados Unidos de América.
¿Cuándo se propuso el método simplex?
En 1947, en EE.UU., George Datzing encuentra el método simplex para el problema de programación lineal. En la investigación de operaciones, las computadoras son la herramienta fundamental en la investigación de operaciones.
En el verano de 1947 realizó la primera formulación del método Simplex.
El primer problema práctico resuelto con este nuevo método fue el problema de nutrición que había planteado George Joseph Stigler a finales de la década anterior, debido al interés del ejército americano por encontrar una dieta equilibrada para alimentar a sus tropas, que cumpliera con unos requisitos mínimos de nutrición y fuese económica.
El problema, que constaba de 9 ecuaciones y 77 incógnitas, fue resuelto manualmente tras 120 días de trabajo. Se demostró que el resultado obtenido apenas difería unos céntimos de la solución hallada anteriormente mediante métodos heurísticos, resultando el nuevo método Simplex todo un éxito.
La primera implementación computacional del Método Simplex es el ano 1952 para un problema de 71 variables y 48 ecuaciones. Su resolución tarda 18 horas. Luego, en 1956, un código llamado RSLP1, implementado en un IBM con 4Kb en RAM, admite la resolución de modelos con 255 restricciones.
Nombre: LUIS CHANGO
ResponderEliminar¿Quien creó y en qué fecha el método simplex?
El método simplex es un método que sirve para resolver problemas de programación lineal. Este método fue inventado por George Danzig en el 1947. La primera formulación del método simplex fue en el verano de 1947. El primer problema práctico que se resolvió con este método fue uno de nutrición.
El método simplex: Disminuye sistemáticamente un número infinito de soluciones hasta un número finito de soluciones básicas factibles.
Un modelo de programación lineal proporciona un método eficiente para determinar una decisión óptima, (o una estrategia óptima o un plan óptimo) escogida de un gran número de decisiones posibles. En todos los problemas de Programación Lineal, el objetivo es la maximización o minimización de alguna cantidad.
“En que casos se emplea el método simplex”
La aplicación del método del Simplex, se utiliza cuando el problema es de un tamaño suficientemente grande.
Aspectos fundamentales del método simplex:
Encuentra una solución óptima.
Es un método de cambio de bases.
Requiere que la función objetivo sea expresada de tal forma que cada variable básica tenga como coeficiente 0.
Requiere que cada variable básica aparezca en una y solamente una ecuación de restricción. Dualidad.
¿En qué casos se aplica este método, cite ejemplos?
ResponderEliminarCon miras a conocer la metodología que se aplica en el Método SIMPLEX, vamos a resolver el siguiente problema:
Maximizar Z= f(x,y)= 3x + 2y
sujeto a: 2x + y 18
2x + 3y 42
3x + y 24
x 0 , y 0
Se consideran las siguientes fases:
1. Convertir las desigualdades en igualdades
Se introduce una variable de holgura por cada una de las restricciones, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales:
2x + y + h = 18
2x + 3y + s = 42
3x +y + d = 24
2. Igualar la función objetivo a cero
- 3x - 2y + Z = 0
3. Escribir la tabla inicial simplex
En las columnas aparecerán todas las variables del problema y, en las filas, los coeficientes de las igualdades obtenidas, una fila para cada restricción y la última fila con los coeficientes de la función objetivo:
Tabla I . Iteración nº 1
Base Variable de decisión Variable de holgura Valores solución
x y h s d
h 2 1 1 0 0 18
s 2 3 0 1 0 42
d 3 1 0 0 1 24
Z -3 -2 0 0 0 0
4. Encontrar la variable de decisión que entra en la base y la variable de holgura que sale de la base
A. Para escoger la variable de decisión que entra en la base, nos fijamos en la última fila, la de los coeficientes de la función objetivo y escogemos la variable con el coeficiente negativo mayor (en valor absoluto).
En nuestro caso, la variable x de coeficiente - 3.
Si existiesen dos o más coeficientes iguales que cumplan la condición anterior, entonces se elige uno cualquiera de ellos.
Si en la última fila no existiese ningún coeficiente negativo, significa que se ha alcanzado la solución óptima. Por tanto, lo que va a determinar el final del proceso de aplicación del método del simplex, es que en la última fila no haya elementos negativos.
La columna de la variable que entra en la base se llama columna pivote (En color azulado).
B. Para encontrar la variable de holgura que tiene que salir de la base, se divide cada término de la última columna (valores solución) por el término correspondiente de la columna pivote, siempre que estos últimos sean mayores que cero. En nuestro caso:
18/2 [=9] , 42/2 [=21] y 24/3 [=8]
Si hubiese algún elemento menor o igual que cero no se hace dicho cociente. En el caso de que todos los elementos fuesen menores o iguales a cero, entonces tendríamos una solución no acotada y no se puede seguir.
El término de la columna pivote que en la división anterior dé lugar al menor cociente positivo, el 3, ya 8 es el menor, indica la fila de la variable de holgura que sale de la base, d. Esta fila se llama fila pivote (En color azulado).
Si al calcular los cocientes, dos o más son iguales, indica que cualquiera de las variables correspondientes pueden salir de la base.
C. En la intersección de la fila pivote y columna pivote tenemos el elemento pivote operacional, 3.
5. Encontrar los coeficientes de la nueva tabla.
Los nuevos coeficientes de x se obtienen dividiendo todos los coeficientes de la fila d por el pivote operacional, 3, que es el que hay que convertir en 1.
A continuación mediante la reducción gaussiana hacemos ceros los restantes términos de su columna, con lo que obtenemos los nuevos coeficientes de las otras filas incluyendo los de la función objetivo Z.
También se puede hacer utilizando el siguiente esquema:
Fila del pivote:
Nueva fila del pivote= (Vieja fila del pivote) : (Pivote)
Resto de las filas:
Nueva fila= (Vieja fila) - (Coeficiente de la vieja fila en la columna de la variable entrante) X (Nueva fila del pivote)
Veámoslo con un ejemplo una vez calculada la fila del pivote (fila de x en la Tabla II):
Vieja fila de s 2 3 0 1 0 42
- - - - - -
Coeficiente 2 2 2 2 2 2
x x x x x x
Nueva fila pivote 1 1/3 0 0 1/3 8
= = = = = =
Nueva fila de s 0 7/3 0 1 -2/3 26
Tabla II . Iteración nº 2
ResponderEliminarBase Variable de decisión Variable de holgura Valores solución
x y h s d
h 0 1/3 1 0 -2/3 2
s 0 7/3 0 1 -2/3 26
x 1 1/3 0 0 1/3 8
Z 0 -1 0 0 1 24
Como en los elementos de la última fila hay uno negativo, -1, significa que no hemos llegado todavía a la solución óptima. Hay que repetir el proceso:
A. La variable que entra en la base es y, por ser la variable que corresponde al coeficiente -1
B. Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote:
2:1/3 [=6] , 26:7/3 [=78/7] y 8:1/3 [=8]
y como el menor cociente positivo es 6, tenemos que la variable de holgura que sale es h.
C. El elemento pivote, que ahora hay que hacer 1, es 1/3.
Operando de forma análoga a la anterior obtenemos la tabla:
Tabla III . Iteración nº 3
Base Variable de decisión Variable de holgura Valores solución
x y h s d
y 0 1 3 0 -2 6
s 0 0 -7 0 4 12
x 1 0 -1 0 1 6
Z 0 0 3 0 -1 30
Como en los elementos de la última fila hay uno negativo, -1, significa que no hemos llegado todavía a la solución óptima. Hay que repetir el proceso:
A. La variable que entra en la base es d, por ser la variable que corresponde al coeficiente -1
B. Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote:
6/(-2) [=-3] , 12/4 [=3], y 6:1 [=6]
y como el menor cociente positivo es 3, tenemos que la variable de holgura que sale es s.
C. El elemento pivote, que ahora hay que hacer 1, es 4.
Obtenemos la tabla:
Tabla IV . Final del proceso
Base Variable de decisión Variable de holgura Valores solución
x y h s d
y 0 1 -1/2 0 0 12
d 0 0 -7/4 0 1 3
x 1 0 -3/4 0 0 3
Z 0 0 5/4 0 0 33
Como todos los coeficientes de la fila de la función objetivo son positivos, hemos llegado a la solución óptima.
Los solución óptima viene dada por el valor de Z en la columna de los valores solución, en nuestro caso: 33. En la misma columna se puede observar el vértice donde se alcanza, observando las filas correspondientes a las variables de decisión que han entrado en la base: D(3,12)
EJEMPLO 2
ResponderEliminarResolver el siguiente problema de Programación Lineal utilizando el Método Simplex:
• Max 40*X1 + 60*X2
• s.a. 2*X1 + 1*X2 <= 70
• 1*X1 + 1*X2 <= 40
• 1*X1 + 3*X2 <= 90
• X1 >= 0 X2 >= 0
Para poder aplicar el Método Simplex, es necesario llevar el modelo a su formato estándar, para lo cual definimos X3, X4, X5 >= 0 como las respectivas variables de holgura para la restricción 1, 2 y 3. De esta forma queda definida la tabla inicial del método de la siguiente forma:
X1 X2 X3 X4 X5
2 1 1 0 0 70
1 1 0 1 0 40
1 3 0 0 1 90
-40 -60 0 0 0 0
En esta situación, las variables de holgura definen una solución básica factible inicial, condición necesaria para la aplicación del método. Luego, se verifican los costos reducidos de las variables no básicas (X1 y X2 en la tabla inicial) y se escoge como variable que entra a la base aquella con el costo reducido "más negativo". En este caso, X2.
Luego, para escoger que variable básica deja la base debemos buscar el mínimo cuociente entre el lado derecho y los coeficientes asociados a la variable entrante en cada fila (para aquellos coeficientes > 0 marcados en rojo en la tabla anterior). El mínimo se alcanza en Min {70/1, 40/1, 90/3} = 30 asociado a la tercera fila, el cual corresponde a la variable básica actual X5, en consecuencia, X5 deja la base. En la posición que se alcanza el mínimo cuociente lo llamaremos "Pivote" (marcado con rojo) el cual nos servirá para realizar las respectivas operaciones filas, logrando la siguiente tabla al cabo de una iteración:
X1 X2 X3 X4 X5
5/3 0 1 0 -1/3 40
2/3 0 0 1 -1/3 10
1/3 1 0 0 1/3 30
-20 0 0 0 20 1800
El valor de la función objetivo luego de una iteración ha pasado de 0 a 1.800. Se recomienda al lector hacer una representación gráfica del problema y notar como las soluciones factibles del método corresponden a vértices del dominio de puntos factibles.
La actual tabla no corresponde a la solución óptima del problema P) debido a que existe una variable no básica con costo reducido negativo, por tanto X1 entra a la base. Posteriormente, mediante el criterio del mínimo cuociente calculamos la variable que debe dejar la base: Min {40/(5/3), 10/(2/3), 30/(1/3)} = 15, asociado a la fila 2 (variable básica actual X4), por tanto X4 deja la base. Obtenido lo anterior se aplica una iteración del método:
X1 X2 X3 X4 X5
0 0 1 -5/2 1/2 15
1 0 0 3/2 -1/2 15
0 1 0 -1/2 1/2 25
0 0 0 30 10 2100
Finalmente se alcanza la solución óptima del problema P) y se verifica que los costos reducidos asociados a las variables no básicas (X4 y X5 son mayores o iguals que cero). Notése que la existencia de un costo reducido igual a cero para una variable no básica en esta etapa define un problema con "infinitas soluciones".
La solución alcanzada es X1* = 15, X2* = 25 con V(P*) = 2.100. Adicionalmente, los costos reducidos asociados a las variables no básicas definen el precio sombra asociado a las restricciones 1, 2 y 3, respectivamente, lo cual es equivalente a la obtención del precio sombra mediante el método gráfico. Dejaremos para una posterior presentación, la forma de calcular el intervalo de variación para el lado derecho que permite la validez del precio sombra, utilizando la tabla final del Método Simplex.