Investigación de Operaciones I
Sebastián Alonso Sosa Pérez
Ramos Cornejo Jhunior Israel
Vilela Vilchez Carlos David
Yesang Cavero Narciso Eduardo

Método Simplex

Creado: 10-01-2021

Metodo 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 del método gráfico, en la que se pueden usar dos o mas variables, en donde se busca alcanzar el máximo o mínimo de una función lineal compuesta por un conjunto de variables que deben satisfacer condiciones impuestas por restricciones lineales en forma de inecuaciones.

• Este método llega a la solución optima por medio de iteraciones o pasos sucesivos, utilizando los conceptos básicos del algebra matricial, para determinar la intersección de dos o mas líneas. Comienza con alguna solución factible, y sucesivamente obtiene soluciones en las intersecciones que ofrecen mejores funciones de la función objetivo.

• Una de las características del método simplex es que la ultima 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 optima.

• Nos sirve para solucionar problemas en donde debemos de optimizar nuestros recursos de la manera mas eficiente donde intervienen dos o tres a mas variables.

METODO SIMPLEX- MINIMIZACION

• Resuelve problemas de planeación y programación de operaciones.

• Utiliza el modelo de la programación lineal, a través de la solución de una matriz, usando el método de la eliminación de Gauss Jordan.

Metodo Simplex:

• Investiga sólo “algunas” de estas soluciones.

• El diseño del método simplex no permite el incremento simultáneo de las variables. En cambio, incrementa una a la vez.

• La variable que va a aumentar es la que tenga mayor grado de mejora en z.

Ejemplo

Un empresa de moda elabora dos tipos de trajes para hombre, blazer y ejecutivos. Se cuenta con dos procesos: corte y costura. Hacer un traje tipo blazer requiere 1 hora de corte y 1 hora de costura, mientras que uno de tipo ejecutivo requiere 1 hora de corte y 2 horas de costura. El sastre trabaja un total de 4 horas al día en corte y en el proceso de costura 6 horas. Las ganancias por la venta de traje tipo Blazer es $2 por unidad y $3 por cada traje tipo ejecutivo vendido. ¿Cuántos trajes de cada tipo hay que hacer para maximizar las ganancias?

Plantiamiento

\[ x_1= 𝑁úm𝑒𝑟𝑜\ 𝑑𝑒\ 𝑡𝑟𝑎𝑗𝑒𝑠\ 𝑡𝑖𝑝𝑜 \ 𝑏𝑙𝑎𝑧𝑒𝑟 \\ x_2= 𝑁ú𝑚𝑒𝑟𝑜\ 𝑑𝑒\ 𝑡𝑟𝑎𝑗𝑒𝑠\ 𝑡𝑖𝑝𝑜\ 𝑒𝑗𝑒𝑐𝑢𝑡𝑖𝑣𝑜 \]

\[ Maximizar: 𝑍=2𝑥_1+3𝑥_2 \\ Sujeto\ a: 𝑥_1+𝑥_2≤4 \\ 𝑥_1+2𝑥_2≤4 \\ 𝑥_1≥0 \\ 𝑥_2≥0 \]

Solución:

library(lpSolve) # Librería a usar 
objetivo<- c(2,3)
restricciones<- matrix(c(2,1,3,1),ncol = 2,nrow = 2)
coef<- matrix(c(4,4),ncol = 1,nrow = 2)
signo<- c("<=","<=")
solucion<-lp(direction = "max",objective.in = objetivo,
const.mat = restricciones,
const.dir = signo,
const.rhs = coef)
solucion  

## Success: the objective function is 4

Metodo simplex dual

Al obtener modelos de P. L. de problemas reales, puede ser que el objetivo sea minimizar la función de costo, y que las restricciones sean una combinación de desigualdades de la forma mayor igual que y de la forma menor igual que. Para resolver estos modelos se ha desarrollado un algoritmo alterno al método símplex, este método se conoce con el nombre de método símplex-dual. La diferencia entre el método símplex y éste es que el primero empieza con una solución factible (todas las cantidades limitantes en las restricciones son positivas) pero no óptima, mientras que el segundo empieza en una solución no factible (algunas cantidades limitantes pueden ser negativas) pero óptima. El método presenta algunas variaciones respecto al símplex, pero en esencia se tiene el mismo procedimiento, sólo que ahora el objetivo es obtener una solución factible (que todas las cantidades limitantes sean positivas) y mantener en lo posible el objetivo de optimizar.

Algoritmo símplex-dual

1. Se suman las variables de holgura a cada una de las restricciones de la forma menor igual que (como ya se ha descrito en el algoritmo), mientras que a las restricciones de la forma mayor igual que se les resta una variable de superávit. Se debe restar la variable porque las variables artificiales no pueden tomar valores negativos, y en el caso de desigualdades de la forma mayor igual que, lo que necesitamos es quitar la cantidad que se excede de la igualdad.

2. Se multiplican por –1 aquellas restricciones a las que se restó una variable de superávit.

3. Se forma la tabla símplex-dual inicial, la cual tiene las mismas características que la tabla símplex inicial. La diferencia es que algunas de las cantidades limitantes de las restricciones son negativas con una función objetivo por minimizar.

4. Se selecciona el renglón con el mayor valor negativo, ésta es la variable que sale del sistema.

5. Para seleccionar la variable que entra a la base, sólo se toman las columnas de las variables no básicas cuyo coeficiente del renglón seleccionado en el punto anterior sea negativo. Si no existe, entonces el modelo no tiene solución. Se divide el coeficiente de los candidatos del renglón R0 entre el coeficiente del renglón seleccionado y se toma su valor absoluto. El valor menor indica la variable que entra a la base.

6. La celda formada por la intersección del renglón seleccionado con la columna seleccionada es el elemento pivote, este renglón se multiplica por su inverso multiplicativo y el resultado se escribe en una nueva tabla intercambiando las etiquetas de las variables que salen y entran a la base.

7. Tomando de referencia el elemento pivote, se hacen ceros los elementos de la columna seleccionada utilizando operaciones elementales sobre matrices.

8. Si todas las cantidades limitantes son positivas, la tabla ya es óptima: si no es así, se regresa al punto 4.

Ejemplo