07 método dos fases y penalidad
TRANSCRIPT
![Page 1: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/1.jpg)
Programación Lineal
Método de las Dos Fases
Método de Penalidad
![Page 2: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/2.jpg)
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?
![Page 3: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/3.jpg)
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
![Page 4: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/4.jpg)
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
![Page 5: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/5.jpg)
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
![Page 6: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/6.jpg)
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
![Page 7: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/7.jpg)
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
![Page 8: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/8.jpg)
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
![Page 9: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/9.jpg)
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
![Page 10: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/10.jpg)
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
![Page 11: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/11.jpg)
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
![Page 12: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/12.jpg)
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
![Page 13: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/13.jpg)
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
![Page 14: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/14.jpg)
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
![Page 15: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/15.jpg)
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
![Page 16: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/16.jpg)
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
![Page 17: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/17.jpg)
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
![Page 18: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/18.jpg)
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
![Page 19: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/19.jpg)
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
![Page 20: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/20.jpg)
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
![Page 21: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/21.jpg)
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
![Page 22: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/22.jpg)
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
![Page 23: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/23.jpg)
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
![Page 24: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/24.jpg)
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
![Page 25: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/25.jpg)
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
![Page 26: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/26.jpg)
IO1 R.Delgadillo 26
Ejercicios
Min 6x1 + 3x2+ 4x3
sujeto a:
x1 + 6x2+ x3 = 10
2x1 + 3x2 ≤ 15
x1, x2, x3 ≥ 0
![Page 27: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/27.jpg)
IO1 R.Delgadillo 27
Ejercicio
Min 4x1 + x2
Sujeto a:
3x1 + x2 = 3
4x1 + 3x2 ≥ 6
x1 + 2x2 ≤ 4
x1, x2 ≥ 0
![Page 28: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/28.jpg)
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 ->∞
![Page 29: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/29.jpg)
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
![Page 30: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/30.jpg)
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
![Page 31: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/31.jpg)
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
![Page 32: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/32.jpg)
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
![Page 33: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/33.jpg)
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
![Page 34: 07 método dos fases y penalidad](https://reader033.vdocumento.com/reader033/viewer/2022052413/5598ca581a28ab36568b47d8/html5/thumbnails/34.jpg)
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