Método

Simplex

Introducción
El Método Simplex, como parte de la programación lineal, es un método analítico
capaz de resolver aquellos modelos que se vuelven complejos en el uso del
método gráfico por el número de variables empleadas, por ejemplo: Si usted se
traslada a su Universidad ¿cuántas opciones tiene para llegar? ¿Se va caminando
o en carro? Si decide irse en transporte ¿automóvil particular, transporte público,
bicicleta, patines, de aventón? ¿Qué implica que usted opte por viajar en alguno
de estos? ¿Cuántos recursos será necesario invertir? ¿Cuál es la ruta más corta?
¿Se da cuenta?... Son varios los factores a considerar, muchas las variables que
contemplar y los resultados diferentes. Una pregunta clave: ¿Con cuántos
recursos cuenta usted?, porque hasta el hombre más rico desea optimizar sus
recursos sabiéndolos escasos, ¿a qué estamos limitados? Ante este panorama
que en las empresas se vuelve más complejo por el uso de materia prima,
recursos implicados y productos fabricados, de ahí la importancia de éste método
que facilitará el camino en el proceso de tomar una decisión.
BASES DEL MÉTODO SIMPLEX
Desarrollado en 1947 por George B. Dantzing, el método simplex se ha convertido
en el método general para resolver problemas de programación lineal, a diferencia
del método gráfico puede ser usado cuando las variables del problema son más
de 2 caracterizándose por buscar soluciones “mejores” que el método grafico para
optimizar la función objetivo del problema. Antes de desarrollar el método habrá
que hacer algunas especificaciones: Formulación del Modelo Usar un modelo
matemático para la resolución de problemas es la base de la programación lineal
recordando que modelo se refiere a la representación simplificada de la realidad;
los modelos matemáticos en específico hacen uso de símbolos matemáticos y
presentan elementos como:

 Variables: representan las incógnitas del problema

 Restricciones: se contemplan las limitaciones a las que se encuentra sujeta la

resolución del problema considerando la escasez de recursos en tiempo y
espacio.

 Función objetivo: representa la meta que se pretende alcanzar y en la cual se

basan las decisiones principales para maximizar los beneficios o bien para
minimizar los costos (considere que en la programación lineal el calificativo “lineal”
hace referencia que las ecuaciones usadas en el modelo serán siempre de primer
grado, es decir, sin exponentes).

Método Simplex.
Solución algebraica de un sistema de ecuaciones aplicable a desigualdades (≤).

Las desigualdades del tipo ≤ implican la cantidad no usada u holgura del recurso.

Se tiene el siguiente modelo en su forma original.

Max Z=5 X 1 +4 X 2
Sujeto a:
6 X 1 + 4 X 2 ≤24
X 1 +2 X 2 ≤6
−X 1 + X 2 ≤ 1
X2 ≤ 2
X 1 , X 2 ≠0

Procedimiento
 1. Agregar variables artificiales (en restricciones)
Las desigualdades del tipo ≤ implican la cantidad no usada u holgura del
recurso. Para convertirla en una igualdad y hacer uso de ella en el método
Simplex, se adiciona una variable artificial “ Sn” en las restricciones, de tal
forma que: 6 X 1 + 4 X 2 ≤24
Se convertirá en:

6 X 1 + 4 X 2 + S1 ≤24

Se deben de poner tantas variables artificiales o de holgura como

restricciones ≤existan.

X 1 +2 X 2 + S2 ≤6

−X 1 + X 2+ S 3 ≤ 1

X2+ S4 ≤ 2

2.-Representación de variables artificiales en la función objetivo.

Z=5 X 1 +4 X 2 +∅ S 1 +∅ S 2 + ∅ S 3+ ∅ S 4

Se iguala la función objetivo a cero (0), deberá cambiar de signo (positivo a

negativo y viceversa), de modo que nos resulta de la siguiente manera.

Z−5 X 1−4 X 2−∅ S 1−∅ S 2−∅ S 3 −∅ S 4 =0

Nuestro modelo finalmente será el siguiente:

Z−5 X 1−4 X 2−∅ S 1−∅ S 2−∅ S 3 −∅ S 4 =0

6 X 1 + 4 X 2 + S1 ≤24

X 1 +2 X 2 + S2 ≤6

−X 1 + X 2+ S 3 ≤ 1

X2+ S4 ≤ 2
 3.-Armar tabla Simplex
Se genera la primera tabla de iteración los valores del modelo serán
introducidos a la tabla.

Z−5 X 1−4 X 2−∅ S 1−∅ S 2−∅ S 3 −∅ S 4 =0

6 X 1 + 4 X 2 + S1 ≤24

X 1 +2 X 2 + S2 ≤6

−X 1 + X 2+ S 3 ≤ 1

X2+ S4 ≤ 2
Básicas

Z X1 X2 S1 S2 S3 S4 Solución
Z 1 -5 -4 0 0 0 0 0
No S1 0 6 4 1 0 0 0 24
básicas S2 0 1 2 0 1 0 0 6
S3 0 -1 1 0 0 1 0 1
S4 0 0 1 0 0 0 1 2

Observe que en la primera columna se colocan las variables holgura Sn o también

llamadas no básicas y en las filas se colocan las básicas correspondientes.

Para definir movimiento de variables:

Max Z=5 X 1 +4 X 2

VARIABLE ENTRADA VARIABLE SALIDA

(en Z) (en restricciones)
MAX MAYOR (-) Menor cociente de:
MIN MAYOR (+)
RESULTADO/Variable
correspondiente de
entrada
 Z X1 X2 S1 S2 S3 S4 Solución
Z 1 -5 -4 0 0 0 0 0
S1 0 6 4 1 0 0 0 24
S2 0 1 2 0 1 0 0 6 = 24/6= 4
= 6/1= 6
S3 0 -1 1 0 0 1 0 1
= 1/-1 se aplica no negatividad X
S4 0 0 1 0 0 0 1 2 = 2/0 = infinito no aplica X

Método Gauss-Jordan

Elemento pivote: Donde coinciden variable de entrada con variable de salida.

Se debe llevar a UNO el elemento Pivote

S1 0 6 4 1 0 0 0 24

--------------------------------------------------------

Quedando como:

A esto se le llama RENGLON PIVOTE

S1 0 1 2/3 1/6 0 0 0 4
A partir del renglón pivote se deben llevar el resto de los valores de la columna de entrada a
valor CERO.

Z X1 X2 S1 S2 S3 S4 Sol
Z 1 -5 -4 0 0 0 0 0
S1 0 1 2/3 1/6 0 0 0 4
S2 0 1 2 0 1 0 0 6
S3 0 -1 1 0 0 1 0 1
S4 0 0 1 0 0 0 1 2

Renglón pivote * (-1)

X1 0 1 2/3 1/ 0 0 0 4
6
S2 0 1 2 0 1 0 0 6
X1 0 -1 -2/3 -1/6 0 0 0 -4
Se suman
S2 0 0 4/3 -1/6 1 0 0 2

Nuevo renglón de S

Z X1 X2 S1 S2 S3 S4 Sol
Z 1 -5 -4 0 0 0 0 0
S1 0 1 2/3 1/6 0 0 0 4
S2 0 0 4/3 -1/6 1 0 0 2

S3 0 -1 1 0 0 1 0 1
S4 0 0 1 0 0 0 1 2

Ahora se trabaja con S3

X1 0 1 2/3 1/6 0 0 0 4
Renglón pivote

S3 0 -1 1 0 0 1 0 1
Se suman directamenta ya que se
cuenta con 1 y -1 = 0
S3 0 0 5/3 1/6 0 1 0 5

Nuevo renglón de S3
 Z X1 X2 S1 S2 S3 S4 Sol
Z 1 -5 -4 0 0 0 0 0
S1 0 1 2/3 1/6 0 0 0 4
S2 0 0 4/3 -1/6 1 0 0 2

S3 0 0 5/3 1/6 0 1 0 5
S4 0 0 1 0 0 0 1 2

Ahora se trabaja con S4

X1 0 1 2/3 1/6 0 0 0 4
Renglón pivote * (-1)

S4 0 0 1 0 0 0 1 2
Ya no es necesario hacer algún
arreglo dado que ya se tiene el
S3 0 0 1 0 0 0 1 2
CERO en la variable de entrada.
Por lo tanto la fila queda igual.

Z X1 X2 S1 S2 S3 S4 Sol
Z 1 -5 -4 0 0 0 0 0
S1 0 1 2/3 1/6 0 0 0 4
S2 0 0 4/3 -1/6 1 0 0 2

S3 0 0 5/3 1/6 0 1 0 5
S4 0 0 1 0 0 0 1 2

Finalmente se trabaja con Z

X1 0 1 2/3 1/6 0 0 0 4
Renglón pivote * (5)

Z4 1 -5 -4 0 0 0 0 0
RP multiplicado por 5
X1 0 5 10/3 5/6 0 0 0 20

Z 1 0 -2/3 5/6 0 0 0 20
Nuevo valor para Z
Se obtiene la tabla #2

Z X1 X2 S1 S2 S3 S4 Sol
Z 1 0 -2/3 5/6 0 0 0 20
S1 0 1 2/3 1/6 0 0 0 4
S2 0 0 4/3 -1/6 1 0 0 2

S3 0 0 5/3 1/6 0 1 0 5
S4 0 0 1 0 0 0 1 2

Con esta nueva tabla se repite el procedimiento:

- Identificar variable de entrada y variable de salida

- Llevar el elemento pivote a valor UNO
- Llevar el resto de los valores de la columna de entrada a CERO
- Obtener la tercera tabla

Z X1 X2 S1 S2 S3 S4 Sol
Z 1 0 -2/3 5/6 0 0 0 20
S1 0 1 2/3 1/6 0 0 0 4
S2 0 0 4/3 -1/6 1 0 0 2

S3 0 0 5/3 1/6 0 1 0 5
S4 0 0 1 0 0 0 1 2

Se obtiene la siguiente tabla:

Z X1 X2 S1 S2 S3 S4 Solución
Z 1 0 0 3/4 1/2 0 0 21
X1 0 1 0 1/4 - 1/2 0 0 3
X2 0 0 1 - 1/8 3/4 0 0 3/2
S3 0 0 0 3/8 -5/4 1 0 5/2
S4 0 0 0 1/8 - 3/4 0 1 1/2

Z=21

X 1 =3

X 2 =3/2
4.-Sustitución
Z=5 X 1 +4 X 2

3
Z=5(3)+4 ( )
2

Z=21