República Bolivariana de Venezuela
Instituto Universitario Politécnico
"Santiago Marino"
Extensión: Puerto Ordaz
Escuela: 45
Ingeniería Industrial
Método Simplex
Autor: Rasshel
Farias CI 27.922.429
Índice:
Presentación………………………………………………………. 1
Introducción…………………………………………………………2
Método simplex (definición
y ventajas)…………………………………………………………..….2
Matriz identidad (ejemplo de calculo)……………………….….3
Método
Simplex: Formulación…………………………..….3 .4.5
Simplex: maximización……………………………………….....6.7
Simplex:
minimización…………………………………………….8
Conclusiones:……………………………………………………….9
Bibliografía:
………………………………………………………....9
Método
Simplex (Presentación)
En la historia de la investigación de operaciones, hemos visto diferentes formas para la toma de decisiones y evaluación de los resultados. El método simplex surgió
al necesitarse una forma de evaluar muchos variables o de difícil análisis a simple vista. lo
cual ha hecho que se convierta en un método muy
usado en la investigación de operaciones. Método Simplex es una herramienta matemática básica en la
toma de decisiones pero requiere de entender cada uno de sus pasos y la
constancia de practicarlos, esta investigación nos permitirá estudiar más a fondo todos
los aspectos que lo engloban con el fin de entender mejor como funciona, el
objetivo no solo es conocer que es el método simplex en general y todo el
entorno, también poder utilizar toda la información suministrada para ponerla
en práctica de una forma más fácil y mucho más rápida
Introducción:
El Método
Simplex es un método analítico de solución de problemas de programación lineal, es un procedimiento
iterativo que permite mejorar la solución de la función objetivo en cada paso
también capaz de resolver modelos más complejos mediante el método gráfico sin restricción en el número de
variables, La gran virtud
del método simplex es su sencillez, método muy práctico, ya que solo
trabaja con los coeficientes de la función objetivo y de las restricciones
Es muy importante en el área empresarial ya que lo utilizan para obtener
solución a los problemas de las empresas en cuanto a inventario, ganancias
y pérdidas.
Método Simplex:
Básicamente, es un procedimiento que permite ir mejorando la solución a cada
paso, y por lo tanto El proceso
concluye cuando no es posible seguir mejorando
más dicha solución, es un procedimiento general para resolver temas de
programación lineal, es bien aceptado en las zonas donde las diferentes
necesidades y limitaciones influencia en un valor que necesita ser aumentado o
disminuido al máximo.
El uso más común de Simplex es maximizar el
resultado, que es encontrar el valor más grande posible para un total. Los
problemas típicos de resolver con Simplex están buscando cantidades óptimas de
productos para ser vendidos, con restricciones en el almacenamiento y la
producción de los mismos. Ante
un problema, las desigualdades se establecen limitaciones que representan a las
variables. A partir de ahí, se prueba posibilidades con el fin de optimizar el
resultado tan pronto como sea posible
Como
dijimos se utiliza para resolver problemas de programación lineal pero, con la
particularidad de que en estos intervienen tres o más variables.
Método Simplex: Algunas ventajas
ü Puede ser de gran eficiencia incluso para ajustar un
gran número de parámetros
ü También es muy fácil de usar
ü No requiere el uso de derivadas de la función objeto
Matriz identidad:
La matriz identidad es una matriz que cumple la propiedad de ser el
elemento neutro del producto de matrices. Esto quiere decir que el producto de
cualquier matriz por la matriz identidad no tiene ningún efecto:
AxI
: A
A(1):A
IxA: A
A A
(2 -1 3) (1 0
0 ) = ( 2
-1 3 )
(7 -4 2) (0 1
0 ) = (7
-4 2 )
(-4 3 5) X (0
0 1 ) = (-4 3
5 )
Método Simplex:
Formulación
Publicado por George Dantzig en 1947 y el ruso Leonid Vitalievich Kantorovich, con el ánimo de crear un
algoritmo capaz de solucionar problemas de m restricciones
y n variables.
Este método se emplea con un proceso interactivo, o sea, que se
usa sucesivamente la misma rutina básica de cálculo, lo que da por
resultado una serie de soluciones sucesivas hasta que se encuentra la
mejor. Una característica básica del método Simplex es que la última
solución produce una contribución tan grande o mayor que la solución
previa en un problema de maximización, lo que da la seguridad de llegar
finalmente a la respuesta óptima.
Ejemplo:
A
un grupo de personas se le presenta la oportunidad exportar cinturones de piel
de salmón al mercado europeo. Clasifican los cinturones en dos tipos A y
B: A por alta calidad y B por baja calidad. De acuerdo a sus estimaciones
tendrían una utilidad de 4 euros por cinturón tipo A y 3 euros por el tipo B.
La confección de un cinturón tipo A les requiere el doble de tiempo que uno
tipo B. Si confeccionaran sólo cinturones tipo B podrían hacer 1.000
diarios. En todo caso, el abastecimiento de piel es suficiente para
confeccionar un total combinado de 800 cinturones diarios. Los cinturones
usan un diferente tipo de hebilla según su calidad. Se pueden abastecer de 800
hebillas elegantes al día para los cinturones tipo A y 700 hebillas corrientes
al día para los cinturones tipo B. Se desea formular y resolver un modelo de
Programación Lineal que permita a los artesanos decidir cuántos cinturones
de cada tipo fabricar de modo de maximizar sus ganancias.
1.-Variables de Decisión
·
x1: Número de
cinturones tipo A a fabricar por semana.
·
x2: Número de
cinturones tipo B a fabricar por semana.
2.- Función Objetivo
Cada
cinturón tipo A reporta una utilidad de 4 euros y cada cinturón tipo B reporta
una utilidad de 3 euros. Se desea maximizar la utilidad total dada por: Max 4x1+3x2
3.-Restricciones
·
No se puede fabricar más cinturones tipo A que la
cantidad de hebillas disponibles: x1≤800
·
No se puede fabricar más cinturones tipo B que la
cantidad de hebillas disponibles: x2≤
700
·
Como máximo se puede confeccionar diariamente 800
cinturones del tipo A y del tipo B en conjunto: x1+x2≤800
·
La capacidad de producción permite fabricar
1.000 cinturones tipo B a la semana si se fabricara sólo cinturones de este
tipo. Los cinturones tipo A ocupan el doble de recursos que uno B, esto es se
pueden fabricar 500 cinturones a la semana si sólo se fabrican cinturones tipo
A: 2x1+x2≤1.000
·
No negatividad de las variables de decisión: x1, x2 ≥ 0
En términos
compactos el modelo de Programación Lineal queda definido por:
Previo
a la aplicación del Método Simplex será
necesario llevar el modelo a su forma estándar. Para ello llevamos la función
objetivo a minimización y agregamos las variables de holgura no negativas x3, x4, x5, y x6, para
las restricciones 1, 2, 3 y 4, respectivamente.
Con ello
construimos la tabla inicial del Método Simplex donde las variables de holgura
previamente identificadas definen una solución básica factible inicial (no
óptima):
Por
el criterio del costo reducido más negativo la variable que ingresa a la
base es x1. Luego calculamos en dicha columna el
mínimo cuociente que esta dado por:
.
En
consecuencia el pivote se encuentra en la fila 4 y por tanto la variable x6 deja la base. (Notar que para el
cálculo del mínimo cuociente o criterio de factibilidad sólo se consideran
denominadores que sean estrictamente mayores a cero).
Ahora
la variable no básica que ingresa a la base es x2.
Calculamos nuevamente el mínimo cuociente sobre dicha columna obteniendo:
.
Por
tanto x5 abandona la base. Con ello
realizamos una nueva iteración del Método Simplex:
La solución óptima es x1=200 y x2=600,
donde el valor de las holguras x3 y x4 corresponde a 600 y
100, respectivamente. Notar adicionalmente que las variables x5 y x6 son no básicas en el
óptimo, por tanto su valor es cero, lo que indica que las restricciones 3 y 4
son activas. El valor óptimo del problema es V(P)=2.600.
Simplex:
maximización
Vamos
a resolver el siguiente problema: Maximizar Z = f(x1 ,x2 ) = 3x1 + 2x2
Sujeto a: 2x1 + x2 ≤ 18
2x1 + 3x2 ≤ 42
3x1 + x2 ≤ 24
x1 ≥ 0 , x2 ≥ 0
. Se
consideran los siguientes pasos:
Convertir
las desigualdades en igualdades:
Se introduce una variable de holgura por cada
una de las restricciones, este caso s1 , s2 , s3 para convertirlas en
igualdades y formar el sistema de ecuaciones estándar. Usando en simplex el
siguiente criterio: Signo: Introducir ≤ sn
FORMA
ESTÁNDAR: 2x1 + x2 + s1 = 18 2x1 + 3x2 + s2 = 42 3x1 + x2 + s3 = 24 NOTA: CON
ESTA FORMA ESTÁNDAR SE TRABAJARÁ EN LO SUCESIVO.
. Igualar la
función objetivo a cero y después agregar las variables de holgura del sistema
anterior: Z - 3 x1 - 2 x2 = 0
.
3. Elaborar la tabla inicial del 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
Inicial
Base
Variable de decisión Variable de holgura
Solución X1 X2 S1 S2 S3 S1 2 1 1 0 0 18 S2 2 3 0 1 0 42 S3 3 1 0 0 1 24 Z -3 -2
0 0 0 0
Encontrar la
variable de decisión que entra en la base y la variable de holgura que sale de
la base 4,1.Para escoger la variable de decisión que entra en la base, (FLECHA
VERDE VERTICAL), observamos la última fila, la cual muestra los coeficientes de
la función objetivo y escogemos la variable con el coeficiente más negativo (en
términos de valor absoluto). En este caso, la variable x1 de coeficiente – 3.
1.-Si existen dos
o más coeficientes iguales que cumplan la condición anterior, entonces se elige
cualquiera de ellos.
2.-Si en la última fila no hay un 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 (aparece de color Verde). 4.Encontrar
la variable de decisión que entra en la base y la variable de holgura que sale
de la base
4.2. Para
encontrar la variable de holgura que tiene que salir de la base, (FLECHA VERDE
HORIZONTAL) 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. Si hubiese algún elemento menor o igual que cero no se hace
la división. 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, S3 . Esta fila se llama fila pivote (aparece en
color Verdel).
Iteración No. 1 Base Variable de decisión
Variable de holgura Solución Operación X1 X2 S1 S2 S3 S1 2 1 1 0 0 18 18/2 = 9
S2 2 3 0 1 0 42 42/2 = 21 S3 3 1 0 0 1 24 24/3 = 8 Z -3 -2 0 0 0 0
. 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, este
indica que lavariable de decisión X1 entra y la variable de holgura S3 sale.
5. Encontrar los coeficientes para el nuevo
tablero de simplex. Los nuevos coeficientes de la fila pivote se obtienen
dividiendo todos los coeficientes de la fila por el pivote operacional “3”, ya
que este se debe convertir en 1. A continuación mediante la reducción gaussiana
hacemos ceros los restantes términos de la columna pivote, con lo que obtenemos
los nuevos coeficientes de las otras filas incluyendo los de la función
objetivo Z.
Resultado
de Iteración No. 1 Base Variable de decisión Variable de holgura Solución
Operación X1 X2 S1 S2 S3 S1 0 1/3 1 0 -2/3 2 f(S1 ) – 2 f(X1 ) S2 0 7/3 0 1 -2/3
26 f(S2 ) – 2 f(X1 ) X1 1 1/3 0 0 -1/3 8 (1/3) X1 Z 0 -1 0 0 1 24 f(Z) + 3 f(X1
)
Como
en los elementos de la última fila hay un numero negativo, -1, significa que no
hemos llegado todavía a la solución óptima. Hay que repetir el proceso: La
variable que entra en la base es x2 , por ser la columna pivote que corresponde
al coeficiente -1 Para calcular la variable que sale o la fila pivote,
dividimos los términos de la columna solución entre los términos de la nueva
columna pivote: y como el menor cociente positivo es 6, tenemos que la fila
pivote y la variable de holgura que sale es S1 . El elemento pivote, que ahora
hay que hacer 1, es 1/3. Y se opera de forma análoga a la anterior iteración
Iteración
No. 2 Base Variable de decisión Variable de holgura Solución Operación X1 X2 S1
S2 S3 S1 0 1/3 1 0 -2/3 2 2/(1/3) = 6 S2 0 7/3 0 1 -2/3 26 26/(7/3) = 78/7 X1 1
1/3 0 0 -1/3 8 8/(1/3) = 24 Z 0 -1 0 0 1 24
. Resultado
de Iteración No. 2 Base Variable de decisión Variable de holguraSolución
Operación X1 X2 S1 S2 S3 X2 0 1 3 0 -2 6 3X2 S2 0 0 -7 0 4 12 f(S2 ) – (7/3)
f(X2 ) X1 1 0 -1 0 1 6 f(X1 ) – (1/3) f(X2 ) Z 0 0 3 0 -1 30 f(Z) + f(X2 )
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: La variable
que entra en la base es S3 , por ser la variable que corresponde al coeficiente
-1 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 S2 . El elemento pivote, que ahora hay
que hacer 1, es 4. Obtenemos la tabla:
. Iteración
No. 3 Base Variable de decisión Variable de holgura Solución Operación X1 X2 S1
S2 S3 X2 0 1 3 0 -2 6 No se toma por ser negativo S2 0 0 -7 0 4 12 12/4 = 3 X1
1 0 -1 0 1 6 6/1 = 6 Z 0 0 3 0 -1 30
. Resultado
de Iteración No. 3 Base Variable de decisión Variable de holgura Solución
Operación X1 X2 S1 S2 S3 X2 0 1 -1/2 0 0 12 f(X2 ) + 2 f(S3 ) S3 0 0 -7/4 0 1 3
(1/4) S3 X1 1 0 -3/4 0 0 3 f(X1 ) – f(S3 ) Z 0 0 5/4 0 0 33 f(Z) + f(S3 )
. Tablero
Final Base Variable de decisión Variable de holgura Solución X1 X2 S1 SS3 X2 0 -1/2
0 0 12 S3 0 0 -7/4 0 1 3 X1 1 0 -3/4 0 0 3 Z 0 0 5/4 0 0 33
Respuesta:
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. El valor de
las variables de decisión para X1 es 3 y para X2 es 12. Ejercicio Propuesto.
Sea la función objetivo z= 50X1 + 80x2 s.a. X1+2X2 <= 120 X1+ X2 <= 90
X1>=0 y X2>=0; MaximIzar la función aplicando el método simplex
Simplex: minimización
Ejemplo: Dos
empresas Mineras extraen dos tipos diferentes de minerales, los cuales
sonsometidos a un proceso de trituración, con tres grados: alto, medio y bajo.
Las compañías hanfirmado un contrato para proveer de mineral a una planta de
fundición, cada semana, 12toneladas de mineral de grado alto, 8 toneladas de
grado medio y 24 toneladas de grado bajo.Cada una de las empresas tiene
diferentes procesos de fabricación.
MINA COSTO/DÍA(miles de euros) PRODUCCIÓN (Tn/día)
ALTO MEDIO BAJO X
180 6 3 4 Y 160 1 1 6
¿Cuántos
días a la semana debería operar cada empresa para cumplir el contrato con la
planta defundición?
Minimizar
la FO Z= 180X + 160 X 2
SUJETO A: FORMA
ESTÁNDAR
6X1+X2 12 6X1+X2
+S1=12
3X1+X2 8
3X1+X2 +S2 8
4X1+6X2 24
4X1+6X2+ S3 24
X1 5, X2 5 Z=-180X1-160X2
TABLA
INICIAL BASE
Variables de VARIABLES DE SOLUCIÓN OPERACIÓN
DECISIÓN HOLGURA X1 X2 S1 S2 S3 S1 6 1 1 0 0 12 S2 3 1 0 1 0 8 S3 4 6 0 0 1 24
Z -180 -160 0 0 0 0
ITERACIÓN
No 1BASE Variables de VARIABLES DE SOLUCIÓN OPERACIÓN DECISIÓN HOLGURA X1 X2 S1
S2 S3 S1 6 1 1 0 0 12 12÷6=2 S2 3 1 0 1 0 8 8÷3=2.6 S3 4 6 0 0 1 24 24÷4=6 Z
-180 -160 0 0 0 0 RESULTADO DE ITERACIÓN No 1BASE Variables de VARIABLES DE
SOLUCIÓN OPERACIÓN DECISIÓN HOLGURA X1 X2 S1 S2 S3 X1 1 1/6 1/6 0 0 2 (6)÷ X1
S2 0 1/2 -1/2 1 0 2 S3 0 16/3 -2/3 0 1 16 Z 0 -130 30 0 0 360
ITERACIÓN No 2BASE
Variables de VARIABLES DE SOLUCIÓN OPERACIÓN DECISIÓN HOLGURA X1 X2 S1 S2 S3 S1
1 1/6 1/6 0 0 2 2÷1/6=12 S2 0 1/2 -1/2 1 0 2 2÷1/2=4 S3 0 16/3 -2/3 0 1 16
16÷16/3=3 Z 0 -130 30 0 0 360 RESULTADO DE ITERACIÓN No 2BASE Variables de
VARIABLES DE SOLUCIÓN OPERACIÓN DECISIÓN HOLGURA X1 X2 S1 S2 S3 X1 1 0 3/16 0
-1/32 3/2 S2 0 0 -7/16 1 -3/32 1/2 X2 0 1 -1/8 0 3/16 3 (3/16)• X2 Z 0 0 55/4 0
195/8 750
. TABLA
FINAL BASE Variables de VARIABLES DE SOLUCIÓN OPERACIÓN DECISIÓN HOLGURA X1 X2
S1 S2 S3 X1 1 0 3/16 0 -1/32 3/2 S2 0 0 -7/16 1 -3/32 1/2 X2 0 1 -1/8 0 3/16 3
Z 0 0 55/4 0 195/8 750Como todos los coeficientes de la fila de la
funciónobjetivo son positivos, hemos llegado a la soluciónóptima. La solución
óptima viene dada por el valor de Zen la columna de los valores solución, en
nuestro caso:750.DONDE X1 = 3/2DONDE X2 = 3
La empresa X (=X1)
debe operar 1.5 días para cumplir elcontrato con la planta de fundición.La empresa
Y (=X2) debe operar 3 días para cumplir elcontrato con la planta de fundición.
Conclusiones:
La investigación de operaciones permite el análisis en la toma de decisiones,
gracias a estos conceptos podemos aprender términos como el método simplex, El método simplex permite
localizar de manera eficiente la óptima solución entre los puntos extremos de
un problema de programación lineal. Este
método permite visualizar cuánto se debe vender, cuanto se debe producir o
cuánto se debe comprar según sea el caso para que la empresa obtenga las
ganancias óptimas y suficientes para competir en el mercado.
En Base a esta
importancia El método simplex ha tenido diversas aplicaciones en las industrias
especialmente en el área de transporte, en la parte de inventarios y en lo
empresarial en general. Este método sirve para resolver problemas.
Bibliografía:
Comentarios
Publicar un comentario