07 método dos fases y penalidad
Post on 05-Jul-2015
3.789 Views
Preview:
TRANSCRIPT
Programación Lineal
Método de las Dos Fases
Método de Penalidad
IO1 R.Delgadillo 2
Método Simplex
Idea conceptual:
El simplex inicia cuando se tiene una solución factible. Cuando las restricciones son ≤, una solución factible ocurre en el origen de coordenadas.
¿qué sucede cuando el origen no es solución factible?
IO1 R.Delgadillo 3
Método Simplex
Cuando las restricciones son “≥”, “=“,
y/o bi <0, el origen no es una solución factible. El problema ahora radica en determinar una solución básica inicial
Dos métodos:
Método de las dos fases
Método de penalidad
IO1 R.Delgadillo 4
Método de las dos fases
Iniciar de acuerdo a:
Hacer todas las bi’s ≥ 0 ( si alguna bi≤0, multiplicar a la restricción correspondiente por (-1) )
Agregar (o sustraer) variables de holgura a las restricciones “≤” (“≥”)
A cada restricción “≥” ó “=“, agregar una variable artificial
Crear una función objetivo artificial, según
aiX
IO1 R.Delgadillo 5
Método de las dos fases Si el problema es de min =>
Si el problema es de máx =>
Al nuevo problema se le denomina Problema artificial
Ejemplo:
max z = 6x1 - x2
s.a. 4x1 + x2 < 21
2x1 + 3x2 ≥ 13
x1 – x2 = -1
x1, x2 > 0
aia XZMin
aia XZMax
IO1 R.Delgadillo 6
Método de las dos fases
Luego:
max z = 6x1 - x2 <= Función objetivo original
max zα = - - <= Función objetivo artificial
s.a. 4x1 + x2 + x3 = 21
2x1 + 3x2 -x4 + = 13
- x1 + x2 + = 1
x1, x2, x3, x4, , > 0
aX1
aX2
aX1aX2
aX1aX2
IO1 R.Delgadillo 7
Método de las dos fases
Método
1º fase: En la primera fase se resuelve el problema artificial
Si el problema original tiene solución factible al término de la primera fase, se halla la sol óptima del problema artificial
y , y zα =0 ( las , son VNB)0aiX i 0a
iX
IO1 R.Delgadillo 8
Método de las dos fases
2º fase: Se inicia cuando el término de la primera fase indica viabilidad del problema original (esto es, y zα =0),
=>
Base inicial = Base óptima de la primera fase
resolver el problema original a partir de la solución factible hallada (Base inicial)
Nota: el problema original no tiene solución cuando , para algún i, y por lo tanto zα≠0
0aiX
0aiX
IO1 R.Delgadillo 9
Método de las dos fases
Dado el problema:
max z = 6x1 - x2 <= Función objetivo original
max zα = - - <= Función objetivo artificial
s.a. 4x1 + x2 + x3 = 21
2x1 + 3x2 -x4 + = 13
- x1 + x2 + = 1
x1, x2, x3, x4, , > 0
Coloquemos en el tablero
aX1
aX2
aX1aX2
aX1aX2
IO1 R.Delgadillo 10
Método de las dos fasesx1 x2 x3 x4
x3 4 1 1 0 0 0 21
2 3 0 -1 1 0 13
-1 1 0 0 0 1 1
-z 6 -1 0 0 0 0 0
-zα 0 0 0 0 -1 -1 0
x3 4 1 1 0 0 0 21
2 3 0 -1 1 0 13
-1 1* 0 0 0 1 1
-z 6 -1 0 0 0 0 0
-zα 1 4 0 -1 0 0 14
aX1aX2
aX2
aX1
Las VB, deben tener coeficiente 0,
aX1
aX2
Ahora, iniciamos el pivoteamiento
IO1 R.Delgadillo 11
Método de las dos fasesx1 x2 x3 x4
x3 5 0 1 0 0 -1 20
5* 0 0 -1 1 -3 10
x2 -1 1 0 0 0 1 1
-z 5 0 0 0 0 1 1
-zα 5 0 0 -1 0 -4 10
x3 0 0 1 1 -1 2 10
x1 1 0 0 -1/5 1/5 -3/5 2
x2 0 1 0 -1/5 1/5 -2/5 3
-z 0 0 0 1 -1 4 -9
-zα 0 0 0 0 -1 -1 0
aX1aX2
aX1
Fin de la 1ª fase,Za = 0 y 0a
iX
IO1 R.Delgadillo 12
Método de las dos fasesx1 x2 x3 x4
x3 0 0 1 1 10
x1 1 0 0 -1/5 2
x2 0 1 0 -1/5 3
-z 0 0 0 1 -9
x4 0 0 1 1 10
x1 1 0 1/5 0 4
x2 0 1 1/5 0 5
-z 0 0 -1 0 -19
Inicio de la 2ª fase. Se eliminan Fila
correspondiente Za, y columnas de a
iX
Sol. ÓptimaX4=10X1=4X2=5Z=19
IO1 R.Delgadillo 13
Método de las dos fases
Algoritmo: 1ª Fase: Determine una solución óptima del
problema artificial
Si y zα =0), => pase a la 2ª fase
Caso contrario, el problema original no tiene solución (problema inviable)
2ª Fase: Utilice la solución del problema artificial como solución básica inicial posible para el problema original y resuelva el problema.
0aiX
IO1 R.Delgadillo 14
Método de las dos fases
Ejercicio:
Max z = 3x1 + 2x2 + 4x3
s.a.
2x1 + x2 + 3x3 = 60
3x1 +3x2 + 5x3 > 120
x1, x2, x3> 0
IO1 R.Delgadillo 15
Método de las dos fases
Ejercicio:
Max z = 2x1 + 5x2 + 3x3
s.a.
x1 - 2x2 > 20
2x1 +4x2 + x3 = 50
x1, x2, x3> 0
IO1 R.Delgadillo 16
Método de las dos fases
Análisis:
Al finalizar la 1ª fase se tiene ó
Si => el problema original no tiene solución
Si => puede ocurrir
fuera de la base => Se consiguió una solución básica factible.
cuando menos un esta en la base => Solución básica degenerada, pivotear y que entre algún en la base. (no
hay incremento del valor de la F.O.)
Si todos los coeficientes asociados a , en la fila correspondiente a , son ceros => es redundante, descartar esta restricción.
Continuar con la 2ª fase
0aiX 0a
iX
0aiX
0aiXaiX
aiX
aiX
jX
jXaiX
IO1 R.Delgadillo 17
Método de las dos fases
Ejemplo:Max z = x1 + 2x2 + x3
s.a.
x1 + x2 +x3 =16
2x1 +2x2 + 2x3 = 32
x1, x2, x3> 0
max zα = - -
s.a.
x1 + x2 +x3 + =16
2x1 +2x2 + 2x3 + = 32
x1, x2, x3, , > 0
aX1
aX2
aX2
aX1
aX1
aX2
IO1 R.Delgadillo 18
Método de las dos fasesx1 x2 x3
1 1 1 1 0 16
2 2 2 0 1 32
-z 1 2 1 0 0 0
-zα 0 0 0 -1 -1 0
1* 1 1 1 0 16
2 2 2 0 1 32
-z 1 2 1 0 0 0
-zα 3 3 3 0 0 0
x1 1 1 1 1 0 16
0 0 0 -2 1 0
-z 0 1 0 -1 -1 -16
-zα 0 0 0 -3 0 0
aX1aX2
aX2
aX1
aX1aX2
Se alcanzó la sol. Óptima de la 1ª fase.
Se observa que en la base , pero no puede entrar x2, ni
x3 => restricción redundante (se elimina esta fila)
aX2
aX2
IO1 R.Delgadillo 19
Método de las dos fasesx1 x2 x3
x1 1 1 1 16
-z 0 1 0 -16
x2 1 1 1 16
-z 0 0 0 -32
Sol. Óptimax2 = 16Z= 32
IO1 R.Delgadillo 20
Método de Penalidad
Iniciar de acuerdo a:
Hacer todas las bi’s ≥ 0 ( si alguna bi≤0, multiplicar a la restricción correspondiente por (-1) )
Agregar (o sustraer) variables de holgura a las restricciones “≤” (“≥”)
A cada restricción “≥” ó “=“, agregar una variable artificial a
iX
IO1 R.Delgadillo 21
Método de Penalidad
Asociar a cada variable artificial una Penalidad (M), que corresponde al mayor valor posible que cualquier otro que pueda aparecer en los cálculos
Adicionar:
Si el problema es de min => M
Si el problema es de máx => -M
a la función objetivo original
Resolver el nuevo problema
aiX
aiX
IO1 R.Delgadillo 22
Método de Penalidad
Se encuentra una solución factible del problema, cuando todas las variables artificiales están fuera de la base; esto es
La solución óptima se encuentra por un número cualquiera de iteraciones luego que las variables artificiales dejaron la base.
i 0aiX
IO1 R.Delgadillo 23
Método de Penalidad
Ejemplo:
max z = -8x1 +3x2 - 6x3
s.a. x1 + 3x2 + 5x3 = 4
5x1 + 3x2 - 4x3 ≥ 6
x1, x2, x3 > 0
Agregando variables artificiales
max z = -8x1 +3x2 - 6x3 + 0x4 –M - M
s.a. x1 + 3x2 + 5x3 + = 4
5x1 + 3x2 - 4x3 – x4 + ≥ 6
x1, x2, x3,x4, , > 0
aX1aX2
aX1
aX2
aX1aX2
IO1 R.Delgadillo 24
Método de Penalidadx1 x2 x3 x4
1 3 5 0 1 0 4
5 3 -4 -1 0 1 6
-z -8 3 -6 0 -M -M 0
1 3 5 0 1 0 4
5 3 -4 -1 0 1 6
-z -8+6M 3+6M -6+M -M 0 0 10M
x2 1/3 1 5/3 0 1/3 0 4/3
4 0 -9 -1 -1 1 2
-z -9+4M 0 -11-9M -M -1-2M 0 -4+2M
aX1aX2
aX2
aX1
Las VB, deben tener coeficiente 0,
aX2
Ahora, iniciamos el pivoteamiento
aX1
aX2
IO1 R.Delgadillo 25
Método de Penalidadx1 x2 x3 x4
x2 1/3 1 5/3 0 1/3 0 4/3
4 0 -9 -1 -1 1 2
-z -9+4M 0 -11-9M -M -1-2M 0 -4+2M
x2 0 1 29/12 1/12 5/12 -1/12 7/6
x1 1 0 -9/4 -1/4 -1/4 1/4 1/2
-z 0 0 -125/4 -9/4 -13/4-M 9/4-M 1/2
aX1aX2
aX2
Sol. ÓptimaX1=1/2X2=7/6Z=-1/2
IO1 R.Delgadillo 26
Ejercicios
Min 6x1 + 3x2+ 4x3
sujeto a:
x1 + 6x2+ x3 = 10
2x1 + 3x2 ≤ 15
x1, x2, x3 ≥ 0
IO1 R.Delgadillo 27
Ejercicio
Min 4x1 + x2
Sujeto a:
3x1 + x2 = 3
4x1 + 3x2 ≥ 6
x1 + 2x2 ≤ 4
x1, x2 ≥ 0
IO1 R.Delgadillo 28
Método de Penalidad
Análisis:
Al resolver el problema modificado P(M) puede ocurrir:
Se alcanza la sol óptima de P(M)
Se concluye que P(M) tiene sol. Óptima no acotada, es decir Z ->∞
IO1 R.Delgadillo 29
Método de Penalidad
Análisis:
¿Qué respecto del problema original, P?
Si se alcanzó sol óptima de P(M)
La Base no tiene variables artificial ( ), => sol óptima de P(M) = sol óptima de P
La Base continua con variables artificiales, => si M es un número negativo (positivo) muy grande => no existe sol factible de P
jX aj ,0
IO1 R.Delgadillo 30
Método de Penalidad
Análisis:
P(M) tiene sol. Óptima no acotada (esto es la columna pivot es ≤0)
Si todas las variables artificial son ceros ( ), => Problema original (P) tiene sol óptima no acotada
Cuando menos una variables artificial es positiva => P no tiene sol factible
jX aj ,0
IO1 R.Delgadillo 31
Método de Penalidad
Ejemplo:Min z = -x1 -x2
s.a.
x1 - x2 - x3 = 1
- x1 + x2 + 2x3 ≥ 1
x1, x2, x3> 0
Min z = -x1 - x2 +M +M
s.a.
x1 - x2 - x3 + =1
-x1 +x2 + 2x3 -x4 + = 1
x1, x2, x3, x4, , > 0
aX1
aX2
aX2
aX1
aX1
aX2
IO1 R.Delgadillo 32
Método de Penalidadx1 x2 x3 x4
1 -1 -1 0 1 0 1
-1 1 2 -1 0 1 1
-z -1 -1 0 0 M M 0
1 -1 -1 0 1 0 1
-1 1 2* -1 0 1 1
-z -1 -1 -M M 0 0 -2M
1/2* -1/2 0 -1/2 1 1/2 3/2
x3 -1/2 1/2 1 -1/2 0 1/2 1/2
-z -1-M/2 -1+M/2 0 M/2 0 M/2 -3M/2
x1 1 -1 0 -1 2 1 3
x3 0 0 1 -1 1 1 2
-z 0 -2 0 -1 2+M 1+M 3
aX1aX2
aX2
aX1
aX1
aX2
(PM) es no acotado
como , están
fuera de la base=> (P) tiene sol
óptima no acotada
aX2
aX1
aX1
IO1 R.Delgadillo 33
Método de Penalidad
Ejemplo:Min z = -x1 -x2
s.a.
x1 - x2 ≥ 1
- x1 + x2 ≥ 1
x1, x2> 0
Min z = -x1 - x2 +M +M
s.a.
x1 - x2 - x3 + =1
-x1 +x2 -x4 + = 1
x1, x2, x3, x4, , > 0
aX1
aX2
aX2
aX1
aX1
aX2
IO1 R.Delgadillo 34
Método de Penalidadx1 x2 x3 x4
1 -1 -1 0 1 0 1
-1 1 0 -1 0 1 1
-z -1 -1 0 0 M M 0
1* -1 -1 0 1 0 1
-1 1 0 -1 0 1 1
-z -1 -1 M M 0 0 -2M
x1 1 -1 -1 0 1 0 1
0 0 -1 -1 1 1 2
-z 0 -2 -1+M M 1 0 1-2M
aX1aX2
aX2
aX1
aX1
aX2(PM) es no acotado y
=> (P) no tiene sol factible
022a
X
aX2
top related