Metodo Simplex

El método del simplex. Ejercicios resueltos y comentados
1.- Resolver utilizando el método del simplex el programa siguiente
Max x1 + 9 x 2 + x 3
sujeto a
x1 + 2 x 2 + 3x 3 ≤ 9 .
3x1 + 2 x 2 + 2 x 3 ≤ 15
x1 , x 2 , x 3 ≥ 0

Solución:
Paso 1: En primer lugar, transformamos este programa de forma canónica a forma estándar mediante la

introducción de dos variables de holgura
Las variables deholgura se
incorporan a la
función objetivo con
costos (coeficientes)
nulos.

Max x1 + 9 x2 + x3 + 0 x1h + 0 x2h
sujeto a
Este es el
cuerpo de las
restricciones

x1 + 2 x2 + 3x3 + x1h
3x1 + 2 x2 + 2 x3 +
x1 , x2 , x3 , x1h , x2h

=9
x2h

= 15

≥0

Restricciones de no
negatividad para las
variables

Expresamos ahora los componentes del problema en forma matricial
 1
 x1 
 
 
9
 
 x2 


C =1 ; X =  x3  ;
 
 h
 0
 x1 
 
 h
 0
 x2 

 1 2 3 1 0
 9
A=
; B= 
3
2
2
0
1


15

y comprobamos que rgA = rg( A, B) = 2 . Esto significa que el sistema AX = B es compatible.
Además obtenemos una base canónica en la matriz A utilizando las dos últimas columnas lo que implica que
no son necesarias variables artificiales para este problema.
 1 0
,
 0 1

Paso 2:Determinamos una primera solución factible básica utilizando la matriz básica canónica Ab = 
 1 0  9   9 
  = 
 0 1 15 15

y tenemos X 0 = Ab −1 B = 

Esta solución básica es factible no degenerada y permite considerar las variables de holgura como básicas y
sus costes asociadas como básicos
 xh
X b =  1h 
 x2 

 0
C0 =   .
 0

Paso 3: Como se trata de un problema demaximización utilizaremos el siguiente esquema para la primera

tabla del simplex
XT
CT
Aquí se
disponen las
variables básicas
y sus costes
asociados

Xb

A

Cb

zj −cj

Este es el cuerpo de
la tabla

B

C0 T A − C T

C0T B

Calculamos en primer lugar los valores C0 T A − C T y C0T B y luego sustituimos en esta primera tabla
 1 2 3 1 0
C0 T A − C T = ( 0,0)
 − (1,9,1,0,0) = ( −1,−9,−1,0,0)
 3 22 0 1
 9
C0T B = ( 0,0)  = 0
15
x1 x 2 x 3 x1h x 2h

1 9
x1h 0
x 2h 0

zj −cj

1 0 0
9
15

1 2 3 1 0
3 2 2 0 1

-1 -9 -1 0 0

0

Paso 4: Para evitar confusiones prescindimos de los valores de la segunda columna y a continuación

localizaremos el número más negativo de la última fila (excluyendo la última columna). La columna del
cuerpo de la tabla que esté situada inmediatamente encima serála columna de trabajo.
x1 x 2 x 3 x1h x 2h

1 9 1 0
x1h
x 2h
zj −cj

1
3

[ 2]
[ 2]

-1 -9

Esta es la columna
de trabajo

0

3 1 0
2 0 1

9
15

-1 0 0

0
Este es el número
más negativo de la
última fila (sin contar
el elemento de la
última columna)

Ahora dividiremos cada número de la última columna del cuerpo de la tabla por el correspondiente en la
columna de trabajo
x1 x 2 x 3 x1h x 2h

1 91 0
x1h

1

x 2h

3

zj −cj

[ 2]
[ 2]

0

2 0 1

9
15

-1 0 0

0

3 1 0

-1 -9

y obtenemos los valores 9/2 = 4,5 y 15/2= 7,5. Entre tales valores se escoge el que dé un resultado menor
y el elemento de la columna de trabajo que proporciona este valor mínimo se distingue como elemento
pivote.
x1 x 2 x 3 x1h x 2h

1 9 1 0
x1h

1 2*

3 1 0

x 2h

3

2 0 1

zj −cj

2

-1 -9

0
9
15

-1 0 0

0

Estees el elemento
pivote

Paso 5: Prescindimos de los valores numéricos de la última fila de la tabla y utilizando operaciones

elementales de filas reducimos a ceros todos los elementos de la columna de trabajo distintos del pivote y a
éste lo hacemos igual a la unidad
x1

x2

x 3 x1h x 2h

9

1

1
x1h

0

0

1 / 2 1* 3 / 2 1 / 2 0

x 2h

3

2

2

0

1

9/2
15

zj −cj
Hemos multiplicado
por ½ todoslos
elementos de la
primera fila del
cuerpo de la tabla

x1

1
x1h
x 2h

zj −cj

x 3 x1h x 2h

x2

9

1

0

0

1 / 2 1* 3 / 2 1 / 2 0
2

0

−1

−1

1

9/2
6

A la segunda fila le
añadimos el
resultado de
multiplicar (-2) por
la primera

Paso 6: La variable básica situada en la fila del pivote pasa a ser no básica y la variable no básica situada en

la columna del pivote pasa a ser básica....