2 Variantes Del Simplex 1
Páginas: 7 (1539 palabras)
Publicado: 22 de marzo de 2015
Variantes del Simplex
Determinación de una solución inicial
Método de la doble fase
• Fase I : Resolver el siguiente problema de
programación lineal empezando con la
solución x=0 y xa=b.
min 1x a
s.a
Ax + x a b
x,x a 0
Método de la doble fase
• Si en la optimalidad xa0, entonces PARE; el
problema original NO tiene soluciones
factibles.
• FASE II : Resolver el problema de PL con lasolución inicial igual a la encontrada en la fase
I.
El modelo matemático
Minimizar z = x1 – 2x2
Sujeto a:
x1+x2 >= 2
-x1 + x2 >= 1
x2<=3
x1, x2 >= 0
Formato Tabla
Min z - x1 + 2x2
=0
Sujeto a:
x 1 + x 2 - x3
-x1 + x2
- x4
x2
+ x5
x1,x2,x3,x4,x5>=0
= 2+x6
= 1 +x7
= 3
Variables auxiliares
z = x6+x7
El Algoritmo Simplex : FASE I
Paso 1: Seleccionar una nueva variable que entre a la base. z -x6-x7=0
Var z
Z 1
x1 x2 x3 x4 x5 x6 x7 RHS
0 0 0 0 0 -1 -1 0
x6 0
1
x7 0
-1 1
x5 0
0
1
1
-1 0
0
1
0
2
0
-1 0
0
1
1
0
0
0
0
3
1
Var z
Z 1
x1 x2 x3 x4 x5 x6 x7 RHS
0 0 0 0 0 -1 -1 0
x6 0
1
x7 0
-1 1
x5 0
0
Var z
Z 1
x1 x2 x3 x4 x5 x6 x7 RHS
0 2 -1 -1 0 0 0 3
x6 0
1
x7 0
-1 1
x5 0
0
1
1
1
1
-1 0
0
1
0
2
0
-1 0
0
1
1
0
0
0
0
3
-1 0
1
01
0
2
0
-1 0
0
1
1
0
0
0
0
3
1
Var z
Z 1
x1 x2 x3 x4 x5 x6 x7 RHS
0 2 -1 -1 0 0 0 3
x6 0
1
x7 0
-1 1
x5 0
0
1
-1 0
0
1
0
2
-1 0
0
1
1
1 0 0 1 0 0
Elemento pivote
3
0
Var z
Z 1
x1 x2 x3 x4 x5 x6 x7 RHS
2 0 -1 1 0 0 -2 1
x6 0
2
x2 0
-1 1
x5 0
1
0
0
-1 1
0
1
-1 1
0
-1 0
0
1
0
1
0
-1 2
1
1
Var z
Z 1
x1 x2 x3 x4 x5 x6 x7 RHS
2 0 -1 1 0 0 -21
x6 0
2
x2 0
-1 1
x5 0
1 0 0 1 1 0
Elemento pivote
0
-1 1
0
0
1
-1 1
-1 0
0
1
1
-1 2
Var z
Z 1
x1 x2 x3 x4 x5 x6 x7 RHS
0 0 0 0 0 -1 -1 0
x1 0
1
0
-1/2
1/2 0
1/2 -1/2
x2 0
0
1
-1/2
-1/2
0
x5 0
0
0
1/2 1/2 1
-1/2
1/2
1/2 1/2 3/2
-1/2
3/2
Ejemplo del método de la doble fase
(2,3)
(0,3)
(0,2)
(1/2,3/2)
(0,1)
(0,0)
Región factible
z = x1-2x2
El AlgoritmoSimplex : FASE II
Paso 1: Seleccionar una nueva variable que entre a la base. z - x1+2x2=0
Var z
Z 1
x1 x2 x3 x4 x5 RHS
-1 2 0 0 0 0
x1 0
1
0
-1/2
1/2 0
1/2
x2 0
0
1
-1/2
-1/2
0
x5 0
0
0
1/2 1/2 1
3/2
3/2
Var z
Z 1
x1 x2 x3 x4 x5 RHS
-1 2 0 0 0 0
x1 0
1
0
-1/2
1/2 0
1/2
x2 0
0
1
-1/2
-1/2
0
x5 0
0
0
1/2 1/2 1
Var z
Z 1
x1 x2 x3 x4 x5 RHS
0 0 1/2 3/2 0 -5/2x1 0
1
0
-1/2
1/2 0
1/2
x2 0
0
1
-1/2
-1/2
0
x5 0
0
0
1/2 1/2 1
3/2
3/2
3/2
3/2
Var z
Z 1
x1 x2 x3 x4 x5 RHS
0 0 1/2 3/2 0 -5/2
x1 0
1
0
-1/2
1/2 0
1/2
x2 0
0
1
-1/2
-1/2
0
x5 0
0
0
1/2 1/2 1
3/2
3/2
Elemento pivote
Var z
Z 1
x1 x2 x3 x4 x5 RHS
-3 0 2 0 0 -4
x4 0
2
0
-1 1
0
1
x2 0
1
1
-1 0
0
2
x5 0
-1 0
1 0
1
1
Var z
Z 1
x1 x2 x3 x4 x5RHS
-3 0 2 0 0 -4
x4 0
2
0
-1 1
0
1
x2 0
1
1
-1 0
0
2
x5 0
-1 0
1 0
1
Var z
Z 1
x1 x2 x3 x4 x5 RHS
-1 0 0 0 -2 -6
x4 0
1
0
0
1
1
2
x2 0
0
1
0
0
1
3
x5 0
-1 0
1 0
1
1
1
Elemento pivote
Ejemplo del método de la doble fase
(0,3)
Solución óptima
(2,3)
(0,2)
(0,1)
(0,0)
(1/2,3/2)
Región factible
Método de la Big-M
Minimizar z = cx+Mxa
Sujeto a:
Ax + xa= b
x, xa >= 0
El modelo matemático
Minimizar z = x1 – 2x2 +Mx6+Mx7
Sujeto a:
x 1 + x2 - x 3
-x1 + x2
- x4
x2
+ x5
x1,x2,x3,x4,x5>=0
= 2+x6
= 1 +x7
= 3
Variables auxiliares
El Algoritmo Simplex : Método BigM
Paso 1: Seleccionar una nueva variable que entre a la base.
Var z
Z 1
x1 x2 x3 x4 x5 x6 x7 RHS
-1 2 0 0 0 -M -M 0
x6 0
1
x7 0
-1 1
x5 0
0
1
1
-1 0
0
1
0
2
0
-1 0
0
11
0
0
0
0
3
1
Var z
Z 1
x1 x2 x3 x4 x5 x6 x7 RHS
-1 2 0 0 0 -M -M 0
x6 0
1
x7 0
-1 1
x5 0
0
1
1
-1 0
0
1
0
2
0
-1 0
0
1
1
0
0
0
0
3
1
Var z
Z 1
x1 x2 x3 x4 x5 x6 x7 RHS
-1
2+2M -M -M 0 0 0
x6 0
1
x7 0
-1 1
x5 0
0
1
1
-1 0
0
1
0
2
0
-1 0
0
1
1
0
0
0
0
3
1
3M
Var z
Z 1
x1 x2 x3 x4 x5 x6 x7 RHS
-1
2+2M -M -M 0 0 0
x6 0
1
x7 0
-1 1...
Determinación de una solución inicial
Método de la doble fase
• Fase I : Resolver el siguiente problema de
programación lineal empezando con la
solución x=0 y xa=b.
min 1x a
s.a
Ax + x a b
x,x a 0
Método de la doble fase
• Si en la optimalidad xa0, entonces PARE; el
problema original NO tiene soluciones
factibles.
• FASE II : Resolver el problema de PL con lasolución inicial igual a la encontrada en la fase
I.
El modelo matemático
Minimizar z = x1 – 2x2
Sujeto a:
x1+x2 >= 2
-x1 + x2 >= 1
x2<=3
x1, x2 >= 0
Formato Tabla
Min z - x1 + 2x2
=0
Sujeto a:
x 1 + x 2 - x3
-x1 + x2
- x4
x2
+ x5
x1,x2,x3,x4,x5>=0
= 2+x6
= 1 +x7
= 3
Variables auxiliares
z = x6+x7
El Algoritmo Simplex : FASE I
Paso 1: Seleccionar una nueva variable que entre a la base. z -x6-x7=0
Var z
Z 1
x1 x2 x3 x4 x5 x6 x7 RHS
0 0 0 0 0 -1 -1 0
x6 0
1
x7 0
-1 1
x5 0
0
1
1
-1 0
0
1
0
2
0
-1 0
0
1
1
0
0
0
0
3
1
Var z
Z 1
x1 x2 x3 x4 x5 x6 x7 RHS
0 0 0 0 0 -1 -1 0
x6 0
1
x7 0
-1 1
x5 0
0
Var z
Z 1
x1 x2 x3 x4 x5 x6 x7 RHS
0 2 -1 -1 0 0 0 3
x6 0
1
x7 0
-1 1
x5 0
0
1
1
1
1
-1 0
0
1
0
2
0
-1 0
0
1
1
0
0
0
0
3
-1 0
1
01
0
2
0
-1 0
0
1
1
0
0
0
0
3
1
Var z
Z 1
x1 x2 x3 x4 x5 x6 x7 RHS
0 2 -1 -1 0 0 0 3
x6 0
1
x7 0
-1 1
x5 0
0
1
-1 0
0
1
0
2
-1 0
0
1
1
1 0 0 1 0 0
Elemento pivote
3
0
Var z
Z 1
x1 x2 x3 x4 x5 x6 x7 RHS
2 0 -1 1 0 0 -2 1
x6 0
2
x2 0
-1 1
x5 0
1
0
0
-1 1
0
1
-1 1
0
-1 0
0
1
0
1
0
-1 2
1
1
Var z
Z 1
x1 x2 x3 x4 x5 x6 x7 RHS
2 0 -1 1 0 0 -21
x6 0
2
x2 0
-1 1
x5 0
1 0 0 1 1 0
Elemento pivote
0
-1 1
0
0
1
-1 1
-1 0
0
1
1
-1 2
Var z
Z 1
x1 x2 x3 x4 x5 x6 x7 RHS
0 0 0 0 0 -1 -1 0
x1 0
1
0
-1/2
1/2 0
1/2 -1/2
x2 0
0
1
-1/2
-1/2
0
x5 0
0
0
1/2 1/2 1
-1/2
1/2
1/2 1/2 3/2
-1/2
3/2
Ejemplo del método de la doble fase
(2,3)
(0,3)
(0,2)
(1/2,3/2)
(0,1)
(0,0)
Región factible
z = x1-2x2
El AlgoritmoSimplex : FASE II
Paso 1: Seleccionar una nueva variable que entre a la base. z - x1+2x2=0
Var z
Z 1
x1 x2 x3 x4 x5 RHS
-1 2 0 0 0 0
x1 0
1
0
-1/2
1/2 0
1/2
x2 0
0
1
-1/2
-1/2
0
x5 0
0
0
1/2 1/2 1
3/2
3/2
Var z
Z 1
x1 x2 x3 x4 x5 RHS
-1 2 0 0 0 0
x1 0
1
0
-1/2
1/2 0
1/2
x2 0
0
1
-1/2
-1/2
0
x5 0
0
0
1/2 1/2 1
Var z
Z 1
x1 x2 x3 x4 x5 RHS
0 0 1/2 3/2 0 -5/2x1 0
1
0
-1/2
1/2 0
1/2
x2 0
0
1
-1/2
-1/2
0
x5 0
0
0
1/2 1/2 1
3/2
3/2
3/2
3/2
Var z
Z 1
x1 x2 x3 x4 x5 RHS
0 0 1/2 3/2 0 -5/2
x1 0
1
0
-1/2
1/2 0
1/2
x2 0
0
1
-1/2
-1/2
0
x5 0
0
0
1/2 1/2 1
3/2
3/2
Elemento pivote
Var z
Z 1
x1 x2 x3 x4 x5 RHS
-3 0 2 0 0 -4
x4 0
2
0
-1 1
0
1
x2 0
1
1
-1 0
0
2
x5 0
-1 0
1 0
1
1
Var z
Z 1
x1 x2 x3 x4 x5RHS
-3 0 2 0 0 -4
x4 0
2
0
-1 1
0
1
x2 0
1
1
-1 0
0
2
x5 0
-1 0
1 0
1
Var z
Z 1
x1 x2 x3 x4 x5 RHS
-1 0 0 0 -2 -6
x4 0
1
0
0
1
1
2
x2 0
0
1
0
0
1
3
x5 0
-1 0
1 0
1
1
1
Elemento pivote
Ejemplo del método de la doble fase
(0,3)
Solución óptima
(2,3)
(0,2)
(0,1)
(0,0)
(1/2,3/2)
Región factible
Método de la Big-M
Minimizar z = cx+Mxa
Sujeto a:
Ax + xa= b
x, xa >= 0
El modelo matemático
Minimizar z = x1 – 2x2 +Mx6+Mx7
Sujeto a:
x 1 + x2 - x 3
-x1 + x2
- x4
x2
+ x5
x1,x2,x3,x4,x5>=0
= 2+x6
= 1 +x7
= 3
Variables auxiliares
El Algoritmo Simplex : Método BigM
Paso 1: Seleccionar una nueva variable que entre a la base.
Var z
Z 1
x1 x2 x3 x4 x5 x6 x7 RHS
-1 2 0 0 0 -M -M 0
x6 0
1
x7 0
-1 1
x5 0
0
1
1
-1 0
0
1
0
2
0
-1 0
0
11
0
0
0
0
3
1
Var z
Z 1
x1 x2 x3 x4 x5 x6 x7 RHS
-1 2 0 0 0 -M -M 0
x6 0
1
x7 0
-1 1
x5 0
0
1
1
-1 0
0
1
0
2
0
-1 0
0
1
1
0
0
0
0
3
1
Var z
Z 1
x1 x2 x3 x4 x5 x6 x7 RHS
-1
2+2M -M -M 0 0 0
x6 0
1
x7 0
-1 1
x5 0
0
1
1
-1 0
0
1
0
2
0
-1 0
0
1
1
0
0
0
0
3
1
3M
Var z
Z 1
x1 x2 x3 x4 x5 x6 x7 RHS
-1
2+2M -M -M 0 0 0
x6 0
1
x7 0
-1 1...
Leer documento completo
Regístrate para leer el documento completo.