AUTORAS: M.J. García-Ligero Ramírez y P.

Román Román
Departamento de Estadística e I.O. Universidad de Granada

Este material proporciona la motivación geométrica del Método Simplex. En un ejemplo concreto se
plantea una iteración del algoritmo Simplex (elección de la variable que entra en la base y la que sale) y se
muestra visualmente su interpretación gráfica de la siguiente forma: partiendo de una solución inicial (esto
es, un punto extremo de la región factible) se consideran los posibles movimientos a través de las aristas
de la región factible, seleccionando en primer lugar cuales de ellos conducen a una mejora de la función
objetivo y, posteriormente, seleccionando la que produce la mayor mejora.
A continuación mostrando dicho movimiento desde el punto extremo de partida se deducen sus
consecuencias: cambio de las variables básicas (y, por tanto, obtención de una nueva solución que, en
este caso, mejora a la anterior) por el abandono de uno de los hiperplanos que confluyen en el punto
extremo de partida y por el bloqueo de un hiperplano que evita el escape de la región factible. La variable
definitoria del hiperplano abandonado será la variable que entra en la base y la variable de bloqueo la que
sale. De esta forma, el alumno adquiere, de forma intuitiva, el mecanismo de funcionamiento del método
Simplex.

AVISO: Para su correcta visualización es necesario tener

instalada la opción Microsoft Editor de ecuaciones de Microsoft
Office. Las presentaciones avanzan con sucesivos clicks de ratón
y/o pulsando los eventuales botones (no deben usarse los
cursores ni la rueda del ratón).
 AUTORAS: M.J. García-Ligero Ramírez y P. Román Román
Departamento de Estadística e I.O. Universidad de Granada

Máx Z=2x1+x2 Máx Z=2x1+x2+0s1+0s2+0s3 x1 0

s. a. x1+2x2 ≤ 6 3 x1  2x 2 6
x1  x 2 4
s. a. x1 +2x2+ s1 =6 2
x1  x2 ≤ 4
x 2 2
x1  x2 + s2 =4 Región Factible
x2 ≤ 2 1
x2 + s3 = 2
x 1, x 2 ≥ 0 x 2 0
(0,0) 1 2 3 4 5 6
x 1, x 2, s 1, s 2, s 3 ≥ 0
 AUTORAS: M.J. García-Ligero Ramírez y P. Román Román
Departamento de Estadística e I.O. Universidad de Granada

Máx Z=2x1+x2 Máx Z=2x1+x2+0s1+0s2+0s3 x1 0

s. a. x1+2x2 ≤ 6 3 x1  2x 2 6 (s1=0)
x1  x 2 4 (s2=0)
s. a. x1 +2x2+ s1 =6 2
x1  x2 ≤ 4
x 2 2 (s3=0)
x1  x2 + s2 =4 Región Factible
x2 ≤ 2 1
c
x2 + s3 = 2
x 1, x 2 ≥ 0 x 2 0
(0,0) 1 2 3 4 5 6
ALGORITMO SIMPLEX x 1, x 2, s 1, s 2, s 3 ≥ 0

cj 2 1 0 0 0
V.
Solución (x1 , x 2 ) (0,0)
c Bi básicas x1 x 2 s1 s2 s3 x Bi
Variables no básicas
0 s1 1 2 1 0 0 6 x1 , x 2
0 s2 1 -1 0 1 0 4 Variables básicas
s1 , s 2 , s 3
0 s3 0 1 0 0 1 2
zj-cj -2 -1 0 0 0 Z=0 ITERACIÓN DEL SIMPLEX
 zj-cj<0
Sale de la base s2
cj 2 1 0 0 0 Entra en la base x1
V.
c Bi básicas x 1 x 2 s1 s2 s3 x
Solución (x1 , x 2 ) (4,0)
Bi

0 s1 0 3 1 0 0 2
Variables no básicas
2 x1 1 -1 0 1 0 4 x 2 , s2
0 s3 0 1 0 0 1 2 Variables básicas
zj-cj 0 -3 x1 , s1 , s 3
0 2 0 Z=8
 AUTORAS: M.J. García-Ligero Ramírez y P. Román Román
Departamento de Estadística e I.O. Universidad de Granada

Máx Z=2x1+x2 Máx Z=2x1+x2+0s1+0s2+0s3 x1 0

s. a. x1+2x2 ≤ 6 3 x1  2x 2 6 (s1=0)
x1  x 2 4 (s2=0)
s. a. x1 +2x2+ s1 =6 2
x1  x2 ≤ 4
x 2 2 (s3=0)
x1  x2 + s2 =4 Región Factible
x2 ≤ 2 1
c
x2 + s3 = 2
x 1, x 2 ≥ 0 x 2 0
(0,0) 1 2 3 4 5 6
ALGORITMO SIMPLEX x 1, x 2, s 1, s 2, s 3 ≥ 0

cj
Solución inicial  Punto extremo de partida(x1 , x 2 ) (0,0)
2 1 0 0 0
V.
Solución (x1 , x 2 ) (0,0) Búsqueda del punto extremo adyacente que proporcione
c Bi x1 x 2 s1 s2 s3 x
básicas Bi
Variables no básicas la mayor mejora en la función objetivo
0 s1 1 2 1 0 0 6 x1 , x 2
s2 1 -1 0 1 0 4 Variables básicas Posibles direcciones de movimiento
0
s1 , s 2 , s 3
0 s3 0 1 0 0 1 2 Direcciones de mejora
zj-cj -2 -1 0 0 0 Z=0 ITERACIÓN DEL SIMPLEX Una dirección d produce una mejora en la función
 zj-cj<0 objetivo si forma con su gradiente un ángulo agudo,
Sale de la base s2 es decir si cos(d, c)  0 o, equivalentemente, d c T  0
cj 2 1 0 0 0 Entra en la base x1
 2
V.
c Bi básicas x 1 x 2 s1 s2 s3 x d1=(1,0) d1 c T (1,0)  2
Bi
Solución (x1 , x 2 ) (4,0)  1
0 s1 0 3 1 0 0 2
Variables no básicas  2
2 x1 1 -1 0 1 0 4 x 2 , s2 d2=(0,1) d 2 c T (0,1)  1
s3 0 1 Variables básicas  1
0 0 0 1 2
zj-cj 0 -3 0 2 0 Z=8
x1 , s1 , s 3
 AUTORAS: M.J. García-Ligero Ramírez y P. Román Román
Departamento de Estadística e I.O. Universidad de Granada

Máx Z=2x1+x2 Máx Z=2x1+x2+0s1+0s2+0s3 x1 0

s. a. x1+2x2 ≤ 6 3 x1  2x 2 6 (s1=0)
x1  x 2 4 (s2=0)
s. a. x1 +2x2+ s1 =6 2
x1  x2 ≤ 4
x 2 2 (s3=0)
x1  x2 + s2 =4 Región Factible
x2 ≤ 2 1
c
x2 + s3 = 2
x 1, x 2 ≥ 0 x 2 0
(0,0) 1 2 3 4 5 6
ALGORITMO SIMPLEX x 1, x 2, s 1, s 2, s 3 ≥ 0

cj
Solución inicial  Punto extremo de partida(x1 , x 2 ) (0,0)
2 1 0 0 0
V.
Solución (x1 , x 2 ) (0,0) Búsqueda del punto extremo adyacente que proporcione
c Bi x1 x 2 s1 s2 s3 x
básicas Bi
Variables no básicas la mayor mejora en la función objetivo
0 s1 1 2 1 0 0 6 x1 , x 2
s2 1 -1 0 1 0 4 Variables básicas Posibles direcciones de movimiento 2
0
s1 , s 2 , s 3 d1=(1,0), cos(d , c)  1
0 s3 0 1 0 0 1 2 Direcciones de mejora 5
zj-cj -2 -1 0 0 0 Z=0 1
ITERACIÓN DEL SIMPLEX d2=(0,1), cos(d , c)  2

 zj-cj<0 5
Sale de la base s2 Dirección óptima de mejora
cj 2 1 0 0 0 Entra en la base x1 La dirección d que produce la mayor mejora es aquella
V. para la cual cos(d, c) es mayor.
c Bi básicas
x 1 x 2 s1 s2 s3 x Bi
Solución (x1 , x 2 ) (4,0)
0 s1 0 3 1 0 0 2
Variables no básicas
2 x1 1 -1 0 1 0 4 x 2 , s2
0 s3 0 1 0 0 1 2 Variables básicas
zj-cj 0 -3 0 2 0 Z=8
x1 , s1 , s 3
 AUTORAS: M.J. García-Ligero Ramírez y P. Román Román
Departamento de Estadística e I.O. Universidad de Granada

Máx Z=2x1+x2 Máx Z=2x1+x2+0s1+0s2+0s3 x1 0

s. a. x1+2x2 ≤ 6 3 x1  2x 2 6 (s1=0)
x1  x 2 4 (s2=0)
s. a. x1 +2x2+ s1 =6 2
x1  x2 ≤ 4
x 2 2 (s3=0)
x1  x2 + s2 =4 Región Factible
x2 ≤ 2 1
c
x2 + s3 = 2 (4,0)
x 1, x 2 ≥ 0 x 2 0
(0,0) 1 2 3 4 5 6
ALGORITMO SIMPLEX x 1, x 2, s 1, s 2, s 3 ≥ 0

cj
Solución inicial  Punto extremo de partida(x1 , x 2 ) (0,0)
2 1 0 0 0
V.
Solución (x1 , x 2 ) (0,0) Búsqueda del punto extremo adyacente que proporcione
c Bi x1 x 2 s1 s2 s3 x
básicas Bi
Variables no básicas la mayor mejora en la función objetivo
0 s1 1 2 1 0 0 6 x1 , x 2
s2 1 -1 0 1 0 4 Variables básicas Posibles direcciones de movimiento 2
0
s1 , s 2 , s 3 d1=(1,0), cos(d , c)  1
0 s3 0 1 0 0 1 2 Direcciones de mejora 5
zj-cj -2 -1 0 0 0 Z=0 1
ITERACIÓN DEL SIMPLEX d2=(0,1), cos(d , c)  2

 zj-cj<0 5
Sale de la base s2 Dirección óptima de mejora
cj 2 1 0 0 0 Entra en la base x1 x 1 >0
V.
s3 x
Nueva solución  Punto
Abandono del hiperplano x1=0 extremo adyacente
c Bi básicas x 1 x 2 s1 s2 Bi
Solución (x1 , x 2 ) (4,0) Entra en la base x1
0 s1 0 3 1 0 0 2 (x 1 , x 2 ) (4,0)
Variables no básicas
2 x1 1 -1 0 1 0 4 x 2 , s2 s 2=0
0 s3 0 1 0 0 1 2 Variables básicas Bloqueo del hiperplano s2=0
x1 , s1 , s 3 Deja la base s2
zj-cj 0 -3 0 2 0 Z=8
 AUTORAS: M.J. García-Ligero Ramírez y P. Román Román
Departamento de Estadística e I.O. Universidad de Granada

Máx Z=2x1+x2 Máx Z=2x1+x2+0s1+0s2+0s3 x1 0

s. a. x1+2x2 ≤ 6 3 x1  2x 2 6 (s1=0)
x1  x 2 4 (s2=0)
s. a. x1 +2x2+ s1 =6 2
x1  x2 ≤ 4
x 2 2 (s3=0)
x1  x2 + s2 =4 Región Factible
x2 ≤ 2 1 (14/3,2/3)
c
x2 + s3 = 2 (4,0)
x 1, x 2 ≥ 0 x 2 0
1 2 3 4 5 6
ALGORITMO SIMPLEX x 1, x 2, s 1, s 2, s 3 ≥ 0

cj
Nueva solución  Punto extremo asociado (x , x ) (4,0)
2 1 0 0 0 1 2

V.
Solución (x , x ) (4,0)
1 2 Búsqueda del punto extremo adyacente que proporcione
c Bi básicas
x1 x 2 s1 s2 s3 x Bi
Variables no básicas la mayor mejora en la función objetivo
0 s1 0 3 1 0 0 2 x 2 , s2
x1 1 -1 0 1 0 4 Variables básicas Posibles direcciones de movimiento
2
x 1 , s1 , s 3
0 s3 0 1 0 0 1 2 Direcciones de mejora d1=(1,1), cos(d , c)  01
zj-cj 0 -3 0 2 0 Z=8 ITERACIÓN DEL SIMPLEX Una dirección d produce una mejora en la función
 zj-cj<0 objetivo si forma con su gradiente un ángulo agudo,
Sale de la base s1 Dirección óptima
es decir si cos(d, c) de mejora
0 o, equivalentemente, d c T  0
cj 2 1 0 0 0 Entra en la base x2 x22>0
V.
s3 x
Nueva
d
Abandono solución
=(1,1) 
1 del hiperplanod Punto
c T
x2=0 extremo
(1,1)  adyacente
3
c Bi básicas x 1 x 2 s1 s2 1
1
Bi
Solución (x , x ) (14/3, 2/3) Entra
 en la base x2
1 x2 0 1 1/3 -1/3 0 2/3
1 2 (x , x ) (14/3,2/3)
1 2
Variables no básicas  2
2 x1 1 0 1/3 2/3 0 14/3 s1 , s 2 d2=(-1,0) d 2 c T (-1,0)s 1 = 
02
1
 
0 s3 0 0 -1/3 0 1 1 Variables básicas Bloqueo del hiperplano s1=0
x1 , x 2 , s3 Deja la base s1
zj-cj 0 0 1 1 0 Z=10
 AUTORAS: M.J. García-Ligero Ramírez y P. Román Román
Departamento de Estadística e I.O. Universidad de Granada

Máx Z=2x1+x2 Máx Z=2x1+x2+0s1+0s2+0s3 x1 0

s. a. x1+2x2 ≤ 6 3 x1  2x 2 6 (s1=0)
x1  x 2 4 (s2=0)
s. a. x1 +2x2+ s1 =6 2
x1  x2 ≤ 4
x 2 2 (s3=0)
x1  x2 + s2 =4 Región Factible
x2 ≤ 2 1 (14/3,2/3)
c
x2 + s3 = 2
x 1, x 2 ≥ 0 x 2 0
1 2 3 4 5 6
ALGORITMO SIMPLEX x 1, x 2, s 1, s 2, s 3 ≥ 0

cj 2 1 0 0 0
Nueva solución  Punto extremo asociado
c Bi V.
x1 x 2 s1 s2 s3 x (x 1 , x 2 ) (14/3,2/3)
básicas Bi
Solución (x , x ) (14/3,2/3)
x2
1 2
Búsqueda del punto extremo adyacente que proporcione
1 0 1 1/3 -1/3 0 2/3 Variables no básicas
x1 s ,s la mayor mejora en la función objetivo
2 1 0 1/3 2/3 0 14/3 1 2

0 s3 0 0 -1/3 0 1 1 Variables básicas Posibles direcciones de movimiento

x1 , x 2 , s3 Direcciones de mejora
zj-cj 0 0 1 1 0 Z=10
Una dirección d produce una mejora en la función
objetivo si forma con su gradiente un ángulo agudo,
zj-cj0,  j Solución óptima es decir si cos(d, c)  0 o, equivalentemente, d c T  0
 2
d1=(-1,-1) d1 c T (-1,-1)   3  0
 1
 2
d2=(-2,1) d 2 c T (-2,1)   3  0
 1
No existen direcciones de mejora
 AUTORAS: M.J. García-Ligero Ramírez y P. Román Román
Departamento de Estadística e I.O. Universidad de Granada

Máx Z=2x1+x2 Máx Z=2x1+x2+0s1+0s2+0s3 x1 0

s. a. x1+2x2 ≤ 6 3 x1  2x 2 6 (s1=0)
x1  x 2 4 (s2=0)
s. a. x1 +2x2+ s1 =6 2
x1  x2 ≤ 4
x 2 2 (s3=0)
x1  x2 + s2 =4 Región Factible
x2 ≤ 2 1 (14/3,2/3)
c
x2 + s3 = 2
x 1, x 2 ≥ 0 x 2 0
1 2 3 4 5 6
ALGORITMO SIMPLEX x 1, x 2, s 1, s 2, s 3 ≥ 0

cj 2 1 0 0 0
Nueva solución  Punto extremo asociado
c Bi V.
x1 x 2 s1 s2 s3 x (x 1 , x 2 ) (14/3,2/3)
básicas Bi
Solución (x , x ) (14/3,2/3)
x2
1 2
Búsqueda del punto extremo adyacente que proporcione
1 0 1 1/3 -1/3 0 2/3 Variables no básicas
x1 s ,s la mayor mejora en la función objetivo
2 1 0 1/3 2/3 0 14/3 1 2

0 s3 0 0 -1/3 0 1 1 Variables básicas Posibles direcciones de movimiento

x1 , x 2 , s3 Direcciones de mejora No existen
zj-cj 0 0 1 1 0 Z=10

zj-cj0,  j Solución óptima Se ha encontrado la solución óptima

Solución óptima
(x 1 , x 2 ) (14/3,2/3), Z 10
 AUTORAS: M.J. García-Ligero Ramírez y P. Román Román
Departamento de Estadística e I.O. Universidad de Granada

Máx Z=2x1+x2 Máx Z=2x1+x2+0s1+0s2+0s3 x1 0

s. a. x1+2x2 ≤ 6 3 x1  2x 2 6 (s1=0)
x1  x 2 4 (s2=0)
s. a. x1 +2x2+ s1 =6 2
x1  x2 ≤ 4
x 2 2 (s3=0)
x1  x2 + s2 =4 Región Factible
x2 ≤ 2 1 (14/3,2/3)
c
x2 + s3 = 2
x 1, x 2 ≥ 0 x 2 0
1 2 3 4 5 6
ALGORITMO SIMPLEX x 1, x 2, s 1, s 2, s 3 ≥ 0

cj 2 1 0 0 0
Nueva solución  Punto extremo asociado
c Bi V.
x1 x 2 s1 s2 s3 x (x 1 , x 2 ) (14/3,2/3)
básicas Bi
Solución (x , x ) (14/3,2/3)
x2
1 2
Búsqueda del punto extremo adyacente que proporcione
1 0 1 1/3 -1/3 0 2/3 Variables no básicas
x1 s ,s la mayor mejora en la función objetivo
2 1 0 1/3 2/3 0 14/3 1 2

0 s3 0 0 -1/3 0 1 1 Variables básicas Posibles direcciones de movimiento

x1 , x 2 , s3 Direcciones de mejora No existen
zj-cj 0 0 1 1 0 Z=10

zj-cj0,  j Solución óptima Se ha encontrado la solución óptima

Solución óptima
(x 1 , x 2 ) (14/3,2/3), Z 10