El Método simplex

Ejemplo de resolución de un problema de Programación Lineal (PL) por el método Simplex.

1. EL METODO SIMPLEX
SIMPLEX PRIMAL
YESID ARIZA OSORIO
ASESORAMIENTO EMPRESARIAL & GESTION
CAPACITACION Y ENTRENAMIENTO

2. EL METODO SIMPLEX
SIMPLEX PRIMAL
Es una herramienta matemática que
resuelve problemas de planeación y
programación de operaciones; es decir,
resuelve la pregunta sobre cuánto
producir de acuerdo a la capacidad
operativa y estudios de mercado
Utiliza el modelo de la Programación
Lineal, a través de la solución de una
matriz, usando el método de eliminación
de Gauss Jordan.

3. EL METODO SIMPLEX
SIMPLEX PRIMAL
METODOLOGIA DE TRABAJO
Identificación de la
función objeto y
las restricciones
Construcción del
modelo de
programación
lineal de forma
estándar
Construcción de un
modelo matricial
Solución de la
matriz por método
de eliminación
(Gauss Jordan)
Se obtiene a partir del
enunciado del ejercicio y en la
práctica, a partir de entrevistas
y/o observación
•Las variables se consideran positivas
•Se suman o restan variables básicas o
supuestas para eliminar la inecuación
•Se asegura que el signo del número al
otro lado de la solución sea positivo
Se construye una matriz, generalmente de dos
dimensiones, una para las variables básicas
incluyendo a Z (Función objeto) y otra para todas las
variables
Se utiliza la eliminación identificando en cada
iteración la columna de entrada y la ecuación
pivote

4. EL METODO SIMPLEX
SIMPLEX PRIMAL
IDENTIFICACION DE LA
FUNCION OBJETO Y LAS
RESTRICCIONES
Ejemplo
Maximizar Z= 3X + 2Y, sujeto a:
X+2Y<=6
2X+Y<=8
-X+Y<=1
Y<=2
Considere todas las variables positivas

5. EL METODO SIMPLEX
SIMPLEX PRIMAL
CONSTRUCCION DEL
MODELO DE PL USANDO
LA FORMA ESTANDAR
Función Objeto
Se debe agrupar las variables
de un solo lado de la
ecuación, entonces:
Z=3X+2Y, queda como
-3X-2Y+Z=0
Inecuaciones
Sumar o restar una
variable supuesta teniendo
en cuenta el sentido de la
inecuación; si es menor que
se suma, si es mayor que, se
resta
De ser necesario cambiar
el signo de toda la igualdad
para que el número del otro
lado del igual sea positivo
X+2Y<=6
X+2Y+S1=6
2X+Y<=8
2X+Y+S2=8
-X+Y<=1
-X+Y+S3=1
Y<=2
Y+S4=2

6. EL METODO SIMPLEX
SIMPLEX PRIMAL
MODELO DE PL USANDO
LA FORMA ESTANDAR
Restricciones
Función Objeto-3X-2Y+Z = 0
X+2Y+S1 = 6
2X+Y+S2 = 8
-X+Y+S3 = 1
Y+S4 = 2
Los números después
del signo igual, se
consideran posibles
soluciones, ellos deben
colocarse en la casilla
correspondiente de la
matriz para solucionar
el modelo de Simplex
Los números delante de las
variables son sus
coeficientes

7. EL METODO SIMPLEX
SIMPLEX PRIMAL
DISEÑO DE LA MATRIZ
BásicaZ X YS1S2 S3 S4Solución
Z
S1
S2
S3
S4
Esquema de la matriz

8. EL METODO SIMPLEX
SIMPLEX PRIMAL
DISEÑO DE LA MATRIZ
BásicaZ X YS1S2 S3 S4Solución
Z 1 -3-20 0 0 0 0
S1 0 1 21 0 0 0 6
S2 0 2 10 1 0 0 8
S3 0 -110 0 1 0 1
S4 0 0 10 0 0 1 2
Se toman los coeficientes de las ecuaciones del modelo de PL de forma estándar y se
colocan en su lugar correspondiente de acuerdo con la identificación de las filas y
columnas de la matriz

9. EL METODO SIMPLEX
SIMPLEX PRIMAL
SOLUCION DE LA MATRIZ
(Condiciones de optimidad y de
factibilidad)
CONDICIÓN MAXIMIZACIÓN MINIMIZACIÓN
Optimidad
La variable entrante es la que
tiene el coeficiente mas
negativo en la ecuación
objeto.
La variable entrante es la que
tiene el coeficiente mas
positivo en la ecuación objeto.
El empate (dos números iguales, se rompe de manera arbitraria
El nivel óptimo se alcanza
cuando los coeficientes No
Básicos de la ecuación Z son
No Negativos.
El nivel óptimo se alcanza
cuando los coeficientes No
Básicos de la ecuación Z son No
Positivos.
FactibilidadLa variable saliente es la variable básica con menor razón
positiva entre la solución y el coeficiente en la dirección de la
variable entrante.

10. EL METODO SIMPLEX
SIMPLEX PRIMAL
SOLUCION DE LA MATRIZ
(Identificación de Columna de
Entrada, Ecuación Pivote y
Elemento Pivote)
BásicaZ X YS1S2 S3 S4Solución
Z 1-3-200 0 0 0
S1 0 1 210 0 0 6 6/1=6
S2 0 2 101 0 0 8 8/2=4
S3 0-1100 1 0 1 1/-1=-1
S4 0 0 100 0 1 2 2/0=∞
Coeficientes de las
variables No Básicas
en la función Objeto
Columna de
Entrada
Ecuación Pivote; tiene la menor razón positiva Pivote

11. EL METODO SIMPLEX
SIMPLEX PRIMAL
SOLUCION DE LA MATRIZ
(ITERACIONES)
Se utiliza el método de eliminación Gauss Jordan para calcular los nuevos coeficientes,
según las siguientes operaciones del cálculo:
Nueva Ecuación Pivote = Ecuación Pivote / Elemento Pivote
Nueva Ecuación = Ecuación anterior –
Coeficientes
Columna
entrada
Nueva
Ecuación
Pivote
x

12. EL METODO SIMPLEX
SIMPLEX PRIMAL
SOLUCION DE LA MATRIZ
(ITERACIONES)
BásicaZ X YS1S2 S3 S4Solución
Z
S1
X 0 1 ½0½ 0 0 4
S3
S4
Utilizamos el cálculo de la nueva Ecuación Pivote, dividimos cada coeficiente entre el
elemento pivote, el resultado es:
Note que la variable X pasó a ser básica

13. EL METODO SIMPLEX
SIMPLEX PRIMAL
Calculamos cualquiera de las ecuaciones de la nueva Iteración, el ejemplo es el cálculo
de la primera fila (Ecuación objeto)
Ecuación anterior 1-3-200 000
Coeficiente Columna Entrada (CCE)-3
Nueva Ecuación Pivote 011/201/2004
CCE x Nueva Eq. Pivote 033/203/20012
Nueva Ecuación 10-1/203/20012
SOLUCION DE LA MATRIZ
(ITERACIONES)

14. EL METODO SIMPLEX
SIMPLEX PRIMAL
BásicaZ X YS1S2 S3 S4Solución
Z 1 0-1/203/2 0 0 12
S1
X 0 1 ½0½ 0 0 4
S3
S4
Se escriben los valores en la fila correspondiente de la Matriz (primera fila)
SOLUCION DE LA MATRIZ
(ITERACIONES)

15. EL METODO SIMPLEX
SIMPLEX PRIMAL
SOLUCION DE LA MATRIZ
(SOLUCIÓN)
Básica ZXY S1 S2 S3 S4 Solución
Z 100 1/3 4/3 0 0 12+2/3
Y 001 2/3 -1/3 0 0 4/3
X 010-1/32/3 0 0 10/3
S3 000 -1 1 1 0 3
S4 000-2/31/3 0 1 2/3
Se realizan las Iteraciones que sean necesarias, identificando una y otra vez la Columna
de Entrada, la Ecuación Pivote y el elemento pivote, hasta que se cumpla el valor
óptimo descrito en la condición de Optimidad. La matriz resultante es la siguiente:

16. EL METODO SIMPLEX
SIMPLEX PRIMAL
SOLUCION DE LA MATRIZ
(SOLUCIÓN)
Básica ZXY S1 S2 S3 S4 Solución
Z 100 1/3 4/3 0 0 12+2/3
Y 001 2/3 -1/3 0 0 4/3
X 010-1/32/3 0 0 10/3
S3 000 -1 1 1 0 3
S4 000-2/31/3 0 1 2/3
La solución es, los valores de X y Y que hacen máxima a Z, son 10/3 y 4/3
respectivamente y el valor máximo de Z es 12 +2/3