Ejemplo del Mtodo Simplex Revisado e
Javier Parra Pea n Ingeniera de Produccin o Universidad Distrital Francisco Jos de Caldas e
Ejemplo 1. Problema de Programacin lineal por el Mtodo Siimplex Revisado o
Considere el siguiente problema: sujeto a: 2x1 + x2 14
max 2x1 + 3x2
x1 + 2x2 8 2x1 2x2 10 x1 + x2 2 x1 , x2 0
a. Dibuje la regin de Factibilidad o b. Resuelva el Problema aplicando el mtodo simplex. e
Forma estndar a -min -2x1 3x2 sujeto a: 2x1 + x2 + x3 = 14 x1 + 2x2 + x4 = 8 2x1 2x2 + x5 = 10 x1 + x2 x6 + x7 = 2 x1 , x2 0
10 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 10
Regin Factible Simplex Punto Interior
2x1+x2<=14 -x1+2x2<=8 2x1-2x2<=10 x1+x2>=2
Figure 1: Evolucin de las variables en la solucin del problema o o Dado que existe una variable articial es necesario desarrollar el mtodo de las dos fases, teniendo como e funcin objetivo para la primera fase minimizar x7 o
Fase I
Primera iteracin o
Variables bsicas= a
x3
x4
x5
x7
CT = B
Variables no bsicas= a
x1
x2
x6
CT = N
N =
2 1 2 1
1 2 2 1
0 0 0 1
B =
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
B 1 =
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
b =
14 8 10 2
X = B 1 b =
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
14 8 10 2
14 8 10 2
z = CT X = B
14 8 10 2
= 2
WT =
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
rT = C T W T N = N
2 1 2 1
1 2 2 1
0 0 0 1
No Existe optimalidad, se debe por tanto aplicar la regla de Bland para determinar la variable que entra a la Base, en este caso x1
Aq =
2 1 2 1
D = B 1 Aq =
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
2 1 2 1
2 1 2 1
eq =
1 0 0
Aplicando la prueba de la razn m o nima
14/ 2 8/1 10/ 2 2/ 1
7 8 5 2
,por tanto sale de la base la variable x7
Segunda Iteracin o
Variables bsicas= a
x3
x4
x5
x1
CT = B
Variables no bsicas= a
x7
x2
x6
CT = N
N =
0 0 0 1
1 2 2 1
0 0 0 1
B =
1 0 0 0
0 1 0 0
0 0 1 0
2 1 2 1
B 1 =
1 0 0 0
0 1 0 0
0 0 1 0
2 1 2 1
b =
14 8 10 2
X = B 1 b =
1 0 0 0
0 1 0 0
0 0 1 0
2 1 2 1
14 8 10 2
10 10 6 2
z = CT X = B
10 10 6 2
= 0
WT =
1 0 0 0
0 1 0 0
0 0 1 0
2 1 2 1
rT = C T W T N = N
0 0 0 1
1 2 2 1
0 0 0 1
Se ha llegado a una solucin ptima para la primera fase. o o
Fase II
Iteracin 1 o
Variables bsicas= a
x3
x4
x5
x1
CT = B
Variables no bsicas= a
x2
x6
CT = N
N =
1 2 2 1
0 0 0 1
B =
1 0 0 0
0 1 0 0
0 0 1 0
2 1 2 1
B 1 =
1 0 0 0
0 1 0 0
0 0 1 0
2 1 2 1
b =
14 8 10 2
X = B 1 b =
1 0 0 0
0 1 0 0
0 0 1 0
2 1 2 1
14 8 10 2
10 10 6 2
z = CT X = B
10 10 6 2
=4
WT =
1 0 0 0
0 1 0 0
0 0 1 0
2 1 2 1
rT = C T W T N = N
1 2 2 1
0 0 0 1
No existe optimalidad, por la regla de Bland entra a la base la variable x2
Aq =
1 2 2 1
D = B 1 Aq =
1 0 0 0
0 1 0 0
0 0 1 0
2 1 2 1
1 2 2 1
1 3 4 1
eq =
1 0
Aplicando la prueba de la razn m o nima
10/1 10/ 3 6/4 2/ 1
10 10 3 3 2 2
,por tanto sale de la base la variable x1
Iteracin 2 o
Variables bsicas= a
x3
x4
x5
x2
CT = B
Variables no bsicas= a
x1
x6
CT = N
N =
2 1 2 1
0 0 0 1
B =
1 0 0 0
0 1 0 0
0 0 1 0
1 2 2 1
B 1 =
1 0 0 0
0 1 0 0
0 0 1 0
1 2 2 1
b =
14 8 10 2
X = B 1 b =
1 0 0 0
0 1 0 0
0 0 1 0
1 2 2 1
14 8 10 2
12 4 14 2
z = CT X = B
12 4 14 2
=6
WT =
1 0 0 0
0 1 0 0
0 0 1 0
1 2 2 1
rT = C T W T N = N
2 1 2 1
0 0 0 1
No existe optimalidad, por la regla de Bland entra a la base la variable x6
Aq =
0 0 0 1
D = B 1 Aq =
1 0 0 0
0 1 0 0
0 0 1 0
1 2 2 1
0 0 0 1
1 2 2 1
eq =
0 1
Aplicando la prueba de la razn m o nima
12/ 1 4/ 2 14/2 2/1
12 2 7 2
,por tanto sale de la base la variable x4
Iteracin 3 o
Variables bsicas= a
x3
x6
x5
x2
CT = B
Variables no bsicas= a
x1
x4
CT = N
N =
2 1 2 1
0 1 0 0
B =
1 0 0 0
0 0 0 1
0 0 1 0
1 2 2 1
1 , B 1 = 0 0 0
1 2 1 2 1 1 2
0 0 1 0
0 1 0 0 , b =
14 8 10 2
1 X = B 1 b = 0 0 0
1 2 1 2 1 1 2
0 0 1 0
0 1 0 0
14 8 10 2
10 2 18 4
z = CT X = B
10 2 18 4
12
1 WT = 0 0 0 3 0 0 0
1 2 1 2 1 1 2
0 0 1 0
0 1 0 0 = 0 3 2 0 0
rT = C T W T N = N
3 2
2 1 2 1
0 1 0 0
7 2
3 2
No existe optimalidad, por la regla de Bland entra a la base la variable x1
Aq =
2 1 2 1
1 , D = B 1 Aq = 0 0 0
1 2 1 2 1 1 2
0 0 1 0
0 1 0 0
2 1 2 1
5 2 3 2 1 1 2
eq =
0 1
Aplicando la prueba de la razn m o nima
10/ 5 2 2/ 3 2 18/ 1 4/ 1 2
4 4 3 18 8
,por tanto sale de la base la variable x3
Iteracin 4 o
Variables bsicas= a
x1
x6
x5
x2
CT = B
Variables no bsicas= a
x3
x4
CT = N
N =
1 0 0 0
0 1 0 0
B =
2 1 2 1
0 0 0 1
0 0 1 0
1 2 2 1
B 1 =
2 5 3 5 2 5 1 5
1 5 1 5 6 5 2 5
0 0 1 0
0 1 0 0 , b =
14 8 10 2
X = B 1 b =
2 5 3 5 2 5 1 5
1 5 1 5 6 5 2 5
0 0 1 0
0 1 0 0
14 8 10 2
4 8 14 6
z = CT X = B
4 8 14 6
=26
WT =
2 5 3 5 2 5 1 5
1 5 1 5 6 5 2 5
0 0 1 0
0 1 0 0 = 7 5 4 5 0 0
rT = C T W T N = N
7 5
4 5
1 0 0 0
0 1 0 0
7 5
4 5
Se ha llegado a la solucin ptima o o
x1 = 4,
x2 = 6,
z = 26
