Embed Size (px)
Citation preview
Tipos de soluciones en el Metodo Simplex
Tipos de Soluciones
• Solución única• Múltiples Soluciones• Solución No Acotada• Solución Infactible
Solución Unica
Max z= 3x1 +5x2
s.a. x1 ≤ 4 2x2 ≤ 12 3x1 + 2x2 ≤ 18 x1, x2 ≥ 0
Única Solución
• Al resolverlo gráficamente:
El punto E es el punto óptimo, cuyas coordenadas son: (2,6) y Z*=36
Solución única
x1 x2 h1 h2 h3 b
Z 0 0 0 1,5 1 36
h1 0 0 1 0,333 -0,333 2
X2 0 1 0 0,5 0 6
X1 1 0 0 -0,333 -0,333 2
Existirá única solución cuando sólo las variables básicas poseen valores o coeficientes ceros en el renglón z o renglón 0.
Si observamos el tableau óptimo sólo las variables básicas tienen coeficientes ceros en el renglón z, no así h2 =1,5 y h3 =1.
Múltiples Soluciones
• Min Z= X1-X2
s.a. 5X1+7X2 ≤35 X1-X2 ≥ 4 X1, x2 ≥ 0.
Múltiples Soluciones
•En la recta CD se encuentran las múltiples soluciones.•Cualquier punto que se encuentre sobre este tramo, el valor óptimo será 4.
(4,0)
(5.25, 1.25)
Múltiples Solucionesx1 x2 h1 e2 A2 b
Z 0 0 0 -1 1-M 4
h1 0 12 1 5 5 15
x1 1 -1 0 -1 1 4
Existirán múltiples soluciones cuando las variables básicas tengan valores o coeficientes ceros en el renglón z o renglón 0 y además al menos una de las variables no básicas tengan valor cero.
Si observamos el tableau óptimo no sólo las variables básicas tienen coeficientes ceros en el renglón z, sino también X2 =0.
Las otras soluciones óptimas se pueden encontrar realizando iteraciones adicionales del método simplex, en las que cada vez se elige una variable no básica con coeficiente cero como variable de entrada.
Múltiples Soluciones
x1 x2 h1 e2 A2 b
Z 0 0 0 -1 1-M 4
h1 0 12 1 5 5 15
x1 1 -1 0 -1 1 4
Tabla Adicional
x1 x2 h1 e2 A2 b
Z 0 0 0 -1 1-M 4
x2 0 1 0.083 0.416 0.416 1.25
x1 1 0 0.083 -0.584 1.416 5.25
Solución No Acotada
• Maximizar: Z = 10X1 + 5X2
s.a. -3X1 + 4X2 ≤ 12 X1 - 2X2 ≤ 2 X1 + 2X2 ≥ 8 X1, X2 ≥ 0
Solución No Acotada
Solución No AcotadaX1 X2 h1 h2 e3 A3 b
Z -10 -5 0 0 0 M
h1 -3 4 1 0 0 0 12
h2 1 -2 0 1 0 0 2
A3 1 2 0 0 -1 1 8
X1 X2 h1 h2 e3 A3 b
Z -10-M -5-2M 0 0 M 0 -8M
h1 -3 4 1 0 0 0 12
h2 1 -2 0 1 0 0 2
A3 1 2 0 0 -1 1 8
Tableau Inicial
Solución No Acotada
X1 X2 h1 h2 e3 A3 b
Z -13,75-2,5M 0 1,25+0,5M 0 M 0 15-2M
x2 -0,75 1 0,25 0 0 0 3
h2 -0,5 0 0,5 1 0 0 8
A3 2,5 0 -0,5 0 -1 1 2
X1 X2 h1 h2 e3 A3 b
Z 0 0 -1,5 0 -5,5 5,5+M 26
X2 0 1 0,1 0 -0,3 0,3 3,6
h2 0 0 0,4 1 -0,2 0,2 8,4
X1 1 0 -0,2 0 -0,4 0,4 0,8
Primera Iteración
Segunda Iteración
Solución No Acotada
• Esto ocurre cuando ninguna variable califica como variable básica de salida. Esto se puede dar cuando en la columna pivote todos los coeficientes tengan valor cero y/o negativos, como sucede en el caso de la columna pivote e3.
• La interpretación que se da en estos casos es que se ha cometido un error de tipo, tal vez mal formulado.
Solución Infactible
Minimizar z= 0,4X1 + 0,5X2
s.a. 0,3X1 + 0,1X2 ≤ 1,8 0,5X1 + 0,5X2 = 6 0,6X1 + 0,4X2 ≥ 6 X1, X2 ≥ 0
Solución Infactible
El problema no tiene solución
Solución InfactibleX1 X2 h1 A2 e3 A3 b
Z -0.4 -0.5 0 0 0 -M
h1 0.3 0.1 1 0 0 0 1.8
A2 0.5 0.5 0 1 0 0 6
A3 0.6 0.4 0 0 -1 1 6
X1 X2 h1 A2 e3 A3 b
Z -0.4+1.1M -0.5+0.9M 0 0 -M 0 12M
h1 0.3 0.1 1 0 0 0 1.8
A2 0.5 0.5 0 1 0 0 6
A3 0.6 0.4 0 0 -1 1 6
Tableau Inicial
Solución InfactibleX1 X2 h1 A2 e3 A3 b
Z 0 0.53M-0.36 -3.66M+1.33 0 -M 0 5.4M+2.4
X1 1 0.333 3.333 0 0 0 6
A2 0 0.333 -1.666 1 0 0 3
A3 0 0.2 -2 0 -1 1 2.4
X1 X2 h1 A2 e3 A3 b
Z 0 0 -M-0.5 -1.6M+1.1 -M 0 0.6M+5.7
X1 1 0 5 -1 0 0 3
X2 0 1 -5 3 0 0 9
A3 0 0 -1 -0.6 -1 1 0.6
Primera Iteración
Segunda Iteración
Solución Infactible
• Como todos los coeficientes en el renglón z son ≤ 0, entonces se cumple el test de la optimalidad para el caso de la minimización, por lo tanto se deja de iterar.
• En este caso no posee soluciones factibles, ya se encuentra como variable básica una variable artificial mayor que cero. (A3=0.6)
• Por lo tanto se dice que una solución es infactible cuando en el tableau óptimo aparece una variable A con valor mayor que cero.
