Fátima del Carmen Fernández Zamudio
Método simplex
Investigación de Operaciones
Método simplex
¿Qué es?
SIMPLEX se conoce como un método
analítico dedicado a solucionar los
problemas que tengan lugar dentro
de la programación lineal. De este
modo, cuenta con la habilidad de
resolver los modelos más
complicados que los resueltos a
través del método gráfico.
Pasos para el método simplex
01 Definir el problema en la forma
estándar y generar nuestra
matriz.
04
Seleccionar la variable de
salida utilizando la condición
de factibilidad.
02 Determinar la solución básica
inicial.
05
Actualizar nuestra matriz
realizando las operaciones de
Gauss-Jordan. Volver al paso
Seleccionar la variable de entrada número 3.
03 utilizando la condición de optimalidad.
Si no se puede seleccionar una
variable de entrada, quiere decir que
estamos en la condición óptima y
finalizan las iteraciones. De otro modo
se continúa con el siguiente paso.
EJEMPLO
MAXIMIZACIÓN
SOLUCIÓN
El problema se adecuará al modelo estándar de
programación lineal, agregando las variables de
holgura, exceso y/o artificiales en cada una de las
restricciones:
Restricción 1: Tiene signo “≤” (menor igual) por lo que se
agrega la variable de holgura S1.
Restricción 2: Tiene signo “≤” (menor igual) por lo que se
agrega la variable de holgura S2.
Restricción 3: Tiene signo “≤” (menor igual) por lo que se
agrega la variable de holgura S3.
Para encontrar la variable que entra a la base elegimos el valor
más negativo del vector de costes reducidos: -5. Por lo tanto la
variable de entrada sería X2
.
Para la variable de salida dividiremos los valores de la columna R
con los de la columna X2 (siempre y cuando sean positivos).
Los resultados en orden serían: 20/6, 60 y la última fila no se
considera porque su valor correspondiente a X2 no es positivo
(0)
.
Se debe elegir el menor valor de esta división: 20/6; por lo tanto
la variable de salida se encuentra en la primera fila: S1.
El elemento pivote se encuentra en el cruce de X2 y S1: 6.
Realizamos las reducciones de Gauss-Jordan:
Ingresa la variable X1 y sale de la base la
variable X2. El elemento pivote es 1/6.
Repetimos las operaciones de Gauss-Jordan y
obtenemos la siguiente matriz:
EN ESTA ÚLTIMA MATRIZ, TODOS LOS VALORES DEL VECTOR DE
COSTES REDUCIDOS SON POSITIVOS LO QUE INDICA QUE NOS
ENCONTRAMOS EN EL PUNTO ÓPTIMO. EL RESULTADO SERÍA:
Z = 40
X1= 20, X2= 0, S1= 0, S2= 40, S3= 20
EJEMPLO
MINIZAR
SOLUCIÓN
El problema se adecuará al modelo estándar de
programación lineal, agregando las variables de holgura,
exceso y/o artificiales en cada una de las restricciones:
Restricción 1: Tiene signo “≤” (menor igual) por lo que se
agrega la variable de holgura S1.
Restricción 2: Tiene signo “≤” (menor igual) por lo que se
agrega la variable de holgura S2.
Restricción 3: Tiene signo “≤” (menor igual) por lo que se
agrega la variable de holgura S3.
Como el ejercicios es de minimización, elegiremos el mayor
valor positivo para la variable de entrada: 2. Por lo tanto la
variable de entrada sería X2.
Para la variable de salida dividiremos los valores de la columna
R con los de la columna X2 (siempre y cuando sean positivos).
Los resultados en orden serían: 18/1, 42/3 y la última fila no se
considera porque su valor correspondiente a X2 es negativo
(-2). Se debe elegir el menor valor de esta división: 42/3=14; por
lo tanto la variable de salida se encuentra en la segunda fila:
S2.
El elemento pivote se encuentra en el cruce de X2 y S2: 3.
Realizamos las reducciones de Gauss-Jordan:
EN ESTA ÚLTIMA MATRIZ, TODOS LOS VALORES DEL VECTOR DE COSTES REDUCIDOS
SON NEGATIVOS, LO QUE INDICA QUE NOS ENCONTRAMOS EN EL PUNTO ÓPTIMO DEL
PROBLEMA DE MINIMIZACIÓN. EL RESULTADO SERÍA:
Z = -28
X1= 0, X2= 14, S1= 4, S2= 0, S3= 33
