simplex
Páginas: 8 (1878 palabras)
Publicado: 12 de julio de 2013
CASOS ESPECIALES
DEL MÉTODO SIMPLEX
OBJETIVO: PRESENTAR LOS CASOS
ESPECIALES DE SOLUCIÓN DEL MÉTODO
SIMPLEX
TEMAS:
SOLUCIÓN NO ACOTADA
SOLUCIONES ÓPTIMAS MÚLTIPLES
SOLUCIÓN DEGENERADA
EMPATES EN LA SELECCIÓN DE VARIABLES
CONCLUSIONES
29/06/2007 03:25 p.m.
1
SOLUCIÓN NO ACOTADA
Como se definió en el algoritmo:
Cuando aun existe una variable entrante (existen
coeficientesnegativos en el renglón cero), pero no
existe una variable de salida (a causa de que en la
columna pivote todos los elementos son negativos
o ceros), se tiene una solución no acotada.
29/06/2007 03:25 p.m.
2
SOLUCIÓN NO ACOTADA
En alguna iteración del algoritmo se identificará:
Aún existe una variable con coeficiente negativo en el
renglón cero. xk: c’k < 0
Al explorar loscoeficientes en la columna pivote, todos son
negativos o cero. a’1k , … , a’1k ≤ 0
Variable
básica
Ecuación
z
xB1
…
xBm
29/06/2007 03:25 p.m.
Coeficientes
Lado
derecho
z
x1, … xk …, xn
(0)
1
c’1, … c’k …, c’n
z
(1)
…
(m)
0
…
0
a’11, … a’1k …, a’1n
… …………
a’m1, … a’mk …, a’mn
b’1
…
b’m
3
SOLUCIÓN NO ACOTADA
Ejercicio 13
max z = 5 x1 + x2 + 3 x3+ 4 x4
sujeta a
x1 - 2 x2 + 4 x3 + 3 x4 ≤ 20
- 4 x1 + 6 x2 + 5 x3 - 4 x4 ≤ 40
2 x1 - 3 x2 + 3 x3 + 8 x4 ≤ 50
x1, x2, x3, x4 ≥ 0
Utilice el método simplex para demostrar que z
no está acotada.
29/06/2007 03:25 p.m.
4
SOLUCIÓN NO ACOTADA
Ejercicio 13
Variable
básica
Ecuación
(renglón)
z
Coeficientes
Lado
derecho
z
x1
x2
x3
x4
x5
x6
x7
(0)1
-5
-1
-3
-4
0
0
0
0
x5
(1)
0
1
-2
4
3
1
0
0
20
x6
(2)
0
-4
6
5
-4
0
1
0
40
x7
(3)
0
2
-3
3
8
0
0
1
50
29/06/2007 03:25 p.m.
5
SOLUCIÓN NO ACOTADA
El coeficiente más negativo y columna pivote
Variable
básica
Ecuación
(renglón)
z
Coeficientes
Ladoderecho
z
x1
x2
x3
x4
x5
x6
x7
(0)
1
-5
-1
-3
-4
0
0
0
0
x5
(1)
0
1
-2
4
3
1
0
0
20
x6
(2)
0
-4
6
5
-4
0
1
0
40
x7
(3)
0
2
-3
3
8
0
0
1
50
29/06/2007 03:25 p.m.
6
SOLUCIÓN NO ACOTADA
Prueba de cociente mínimo y renglón pivote
Variablebásica
Ecuación
(renglón)
z
Coeficientes
Lado
derecho
z
x1
x2
x3
x4
x5
x6
x7
(0)
1
-5
-1
-3
-4
0
0
0
0
x5
(1)
0
1
-2
4
3
1
0
0
20
x6
(2)
0
-4
6
5
-4
0
1
0
40
x7
(3)
0
2
-3
3
8
0
0
1
50
20/1=20,
40/-4; NO PERMITIDO,
50/2=25.x1 desplazará a x5
29/06/2007 03:25 p.m.
7
SOLUCIÓN NO ACOTADA
Pivote
Variable
básica
Ecuación
(renglón)
z
Coeficientes
Lado
derecho
z
x1
x2
x3
x4
x5
x6
x7
(0)
1
-5
-1
-3
-4
0
0
0
0
x5
(1)
0
1
-2
4
3
1
0
0
20
x6
(2)
0
-4
6
5
-4
0
1
0
40
x7
(3)0
2
-3
3
8
0
0
1
50
4 (renglón 1) + (renglón 2);
-2 (renglón 1) + (renglón 3);
5 (renglón 1) + (renglón 0);
29/06/2007 03:25 p.m.
8
SOLUCIÓN NO ACOTADA
Actualización de tabla
Variable
básica
Ecuación
(renglón)
z
Coeficientes
Lado
derecho
z
x1
x2
x3
x4
x5
x6
x7
(0)
1
0
-11
17
11
5
0
0
100x1
(1)
0
1
-2
4
3
1
0
0
20
x6
(2)
0
0
-2
21
8
4
1
0
120
x7
(3)
0
0
1
-5
2
-2
0
1
10
29/06/2007 03:25 p.m.
9
SOLUCIÓN NO ACOTADA
Aún hay coeficientes negativos en (0)
El coeficiente más negativo y columna pivote
Variable
básica
Ecuación
(renglón)
z
Coeficientes
Lado...
DEL MÉTODO SIMPLEX
OBJETIVO: PRESENTAR LOS CASOS
ESPECIALES DE SOLUCIÓN DEL MÉTODO
SIMPLEX
TEMAS:
SOLUCIÓN NO ACOTADA
SOLUCIONES ÓPTIMAS MÚLTIPLES
SOLUCIÓN DEGENERADA
EMPATES EN LA SELECCIÓN DE VARIABLES
CONCLUSIONES
29/06/2007 03:25 p.m.
1
SOLUCIÓN NO ACOTADA
Como se definió en el algoritmo:
Cuando aun existe una variable entrante (existen
coeficientesnegativos en el renglón cero), pero no
existe una variable de salida (a causa de que en la
columna pivote todos los elementos son negativos
o ceros), se tiene una solución no acotada.
29/06/2007 03:25 p.m.
2
SOLUCIÓN NO ACOTADA
En alguna iteración del algoritmo se identificará:
Aún existe una variable con coeficiente negativo en el
renglón cero. xk: c’k < 0
Al explorar loscoeficientes en la columna pivote, todos son
negativos o cero. a’1k , … , a’1k ≤ 0
Variable
básica
Ecuación
z
xB1
…
xBm
29/06/2007 03:25 p.m.
Coeficientes
Lado
derecho
z
x1, … xk …, xn
(0)
1
c’1, … c’k …, c’n
z
(1)
…
(m)
0
…
0
a’11, … a’1k …, a’1n
… …………
a’m1, … a’mk …, a’mn
b’1
…
b’m
3
SOLUCIÓN NO ACOTADA
Ejercicio 13
max z = 5 x1 + x2 + 3 x3+ 4 x4
sujeta a
x1 - 2 x2 + 4 x3 + 3 x4 ≤ 20
- 4 x1 + 6 x2 + 5 x3 - 4 x4 ≤ 40
2 x1 - 3 x2 + 3 x3 + 8 x4 ≤ 50
x1, x2, x3, x4 ≥ 0
Utilice el método simplex para demostrar que z
no está acotada.
29/06/2007 03:25 p.m.
4
SOLUCIÓN NO ACOTADA
Ejercicio 13
Variable
básica
Ecuación
(renglón)
z
Coeficientes
Lado
derecho
z
x1
x2
x3
x4
x5
x6
x7
(0)1
-5
-1
-3
-4
0
0
0
0
x5
(1)
0
1
-2
4
3
1
0
0
20
x6
(2)
0
-4
6
5
-4
0
1
0
40
x7
(3)
0
2
-3
3
8
0
0
1
50
29/06/2007 03:25 p.m.
5
SOLUCIÓN NO ACOTADA
El coeficiente más negativo y columna pivote
Variable
básica
Ecuación
(renglón)
z
Coeficientes
Ladoderecho
z
x1
x2
x3
x4
x5
x6
x7
(0)
1
-5
-1
-3
-4
0
0
0
0
x5
(1)
0
1
-2
4
3
1
0
0
20
x6
(2)
0
-4
6
5
-4
0
1
0
40
x7
(3)
0
2
-3
3
8
0
0
1
50
29/06/2007 03:25 p.m.
6
SOLUCIÓN NO ACOTADA
Prueba de cociente mínimo y renglón pivote
Variablebásica
Ecuación
(renglón)
z
Coeficientes
Lado
derecho
z
x1
x2
x3
x4
x5
x6
x7
(0)
1
-5
-1
-3
-4
0
0
0
0
x5
(1)
0
1
-2
4
3
1
0
0
20
x6
(2)
0
-4
6
5
-4
0
1
0
40
x7
(3)
0
2
-3
3
8
0
0
1
50
20/1=20,
40/-4; NO PERMITIDO,
50/2=25.x1 desplazará a x5
29/06/2007 03:25 p.m.
7
SOLUCIÓN NO ACOTADA
Pivote
Variable
básica
Ecuación
(renglón)
z
Coeficientes
Lado
derecho
z
x1
x2
x3
x4
x5
x6
x7
(0)
1
-5
-1
-3
-4
0
0
0
0
x5
(1)
0
1
-2
4
3
1
0
0
20
x6
(2)
0
-4
6
5
-4
0
1
0
40
x7
(3)0
2
-3
3
8
0
0
1
50
4 (renglón 1) + (renglón 2);
-2 (renglón 1) + (renglón 3);
5 (renglón 1) + (renglón 0);
29/06/2007 03:25 p.m.
8
SOLUCIÓN NO ACOTADA
Actualización de tabla
Variable
básica
Ecuación
(renglón)
z
Coeficientes
Lado
derecho
z
x1
x2
x3
x4
x5
x6
x7
(0)
1
0
-11
17
11
5
0
0
100x1
(1)
0
1
-2
4
3
1
0
0
20
x6
(2)
0
0
-2
21
8
4
1
0
120
x7
(3)
0
0
1
-5
2
-2
0
1
10
29/06/2007 03:25 p.m.
9
SOLUCIÓN NO ACOTADA
Aún hay coeficientes negativos en (0)
El coeficiente más negativo y columna pivote
Variable
básica
Ecuación
(renglón)
z
Coeficientes
Lado...
Leer documento completo
Regístrate para leer el documento completo.