IO Ramificacion y Acotamiento
of 17
-
Upload
juanpa-garcia-pulido -
Category
Documents
-
view
21 -
download
0
Transcript of IO Ramificacion y Acotamiento
-
1Ramificacin y Acotamiento
EII-450Investigacin de Operaciones II
Ramificacin y AcotamientoRamificacin Propiedad 3.3
Considere el problema
Xxas
cxZ
=
.
max
{ }2121
21
212121
,Zmax Zque cumple se Entonces
X x X x s.a s.a
maxZy maxSean Z
XXy XXX que talXy XSean
Z
cxcx
=
==
==
Ramificacin se refiere a la aplicacin recursiva de la Propiedad 3.3
-
2RamificacinGrficamente
Xxascx
.max
X
RamificacinGrficamente
Xxascx
.max X
2 .
max
Xxascx
1 .
max
Xxascx
X1 X2
-
3RamificacinGrficamente
Xxascx
.max X
2 .
max
Xxascx
1 .
max
Xxascx
X1 X2
3 .
max
Xxascx
4 .
max
Xxascx
X3
X4
RamificacinGrficamente
Xxascx
.max X
2 .
max
Xxascx
1 .
max
Xxascx
X1 X2
3 .
max
Xxascx
4 .
max
Xxascx
5 .
max
Xxascx
6 .
max
Xxascx
X3
X4
X5
X6
-
4Ramificacin y AcotamientoAcotamiento Propiedad 3.4
Considere el problemaXx
ascxZ
=
.
max
{ }{ } Zdeinferior cota una es Z,ZmaxZy
Zdesuperior cota una es Z,Zmax ZEntonces
menterespectiva y Z Zdeinferior cotas y Z Sean Z
menterespectiva y Z Zdesuperior cotas y Z Sean Z
X x X x s.a s.a
maxZy maxSean Z
XXy XXX que talXy XSean
21
21
2121
2121
21
21
212121
+++
++
==
==
==
cxcx
Ramificacin y AcotamientoAcotamiento El algoritmo de Ramificacin y Acotamiento mantiene
una cota superior para cada subproblema, y una cota inferior global respecto de la F.O del problema original.
Esta informacin se utiliza para determinar qu subproblemas requieren ramificacin adicional, los que denominan ACTIVOS, y cuales no.
-
5Ramificacin y AcotamientoAcotamiento Un subproblema k es NO-ACTIVO si:
El subproblema k ha sido ramificado.
El subproblema k ha sido resuelto.
El subproblema k es infactible.
Se verifica que -k ZZ +
Elementos de diseo de un algoritmo de Ramificacin y Acotamiento
Seleccin de la cota superior Relajacin
Seleccin de la cota inferior Solucin factible
Estrategia de Ramificacin Criterio para particionar el espacio desoluciones, tpicamente depende de la Relajacin utilizada
Seleccin del subproblema ACTIVO a ramificar Depth first search Best node search Breadth first search
-
6Ramificacin y Acotamiento basado en Programacin Lineal
2. a Vaya activo. no como P defina factible, es no P de lineal relajacin la Si 6.
7. a Vaya .P de lineal relajacin la desolucin x
y relajada, linealsolucin laen F.O. la de valor Z defina factible, es P de lineal relajacin la Si 5.
.P de lineal relajacin la Resuelva 4..P problemaun Seleccione 3.
ptima. es x, terminar vaco,est activos assubproblem de conjunto el Si 2.vaco.y x ZDefina .P problemaun Considere 1.
ii
iii
i
i
i
*
*-0
==
==
+
Ramificacin y Acotamiento basado en Programacin Lineal
2. a Vaya mente.respectiva
xy x x x nesrestriccio las P den formulaci la a
agregando assubproblem dos genere io,fraccionar es P de lineal relajacin
laen valor xcuyo xentera variableuna Seleccione :nRamificaci .9activos. assubproblem
de conjunto delk elimine Z Zsi i,k asubproblem todoPara
.xy x Z ZActualice
Z ZSi 8.2 activos. assubproblem de conjunto del P Elimine 8.1
factible enterasolucin una es xSi 8.
2. a Vaya activo. no como P defina ,Z ZSi 7.
ijj
ijj
i
i
ijj
-k
i*i
-
-i
i
i
i-i
+
+
+
+
-
7Ramificacin y AcotamientoEjemplo
0, 3694 3575
.32
++
+
yxyxyx
asyxMax
Considere el siguiente problema:
Ejemplo: F.O. Max 2x+3y
7
4
x
y
-
8Ejemplo: F.O. Max 2x+3y
47.14Z 2.35y
3.72 x
0 ===+
0Z =
7
4
x
y
P0
P0
Ejemplo: F.O. Max 2x+3y
47.14Z 2.35y
3.72 x
0 ===+
0Z =
7
4
x
y
3x 4x
P0
4x 3x
P0
-
9Ejemplo: F.O. Max 2x+3y
47.14Z 2.35y
3.72 x
0 ===+
42.14Z 2.14y
4 x
1 ===+
0Z =
7
4
x
y
3x 4x
4x 3x
P1
P1
P0
Ejemplo: F.O. Max 2x+3y
47.14Z 2.35y
3.72 x
0 ===+
14Z 2.67y
3.0 x
2 ===+ 42.14Z
2.14y4 x
1 ===+
0Z =
7
4
x
y
3x 4x
4x 3x
P1
P2
P2
P0
P1
-
10
Ejemplo: F.O. Max 2x+3y
47.14Z 2.35y
3.72 x
0 ===+
14Z 2.67y
3.0 x
2 ===+ 42.14Z
2.14y4 x
1 ===+
0Z =
7
4
x
y
3x 4x
2y 3y 4x 3x
P2
2y
3y
P2
P0
P1
Ejemplo: F.O. Max 2x+3y
47.14Z 2.35y
3.72 x
0 ===+
14Z 2.67y
3.0 x
2 ===+ 42.14Z
2.14y4 x
1 ===+
INF
0Z =
7
4
x
y
3x 4x
2y 3y 4x 3x
P2
2y
3y P3
P2
P0
P1
-
11
Ejemplo: F.O. Max 2x+3y
47.14Z 2.35y
3.72 x
0 ===+
14Z 2.67y
3.0 x
2 ===+ 42.14Z
2.14y4 x
1 ===+
4.14Z 2.0y
4.2 x
4 ===+
INF
0Z =
7
4
x
y
3x 4x
2y 3y 4x 3x
P4
P2
2y
3y P4P3
P2
P0
P1
Ejemplo: F.O. Max 2x+3y
47.14Z 2.35y
3.72 x
0 ===+
14Z 2.67y
3.0 x
2 ===+ 42.14Z
2.14y4 x
1 ===+
4.14Z 2.0y
4.2 x
4 ===+
INF
0Z =
7
4
x
y
3x 4x
2y 3y 2y 3y 4x 3x
P4 2y
3y
2y
P3
P2
P0
P1
P4
-
12
Ejemplo: F.O. Max 2x+3y
47.14Z 2.35y
3.72 x
0 ===+
14Z 2.67y
3.0 x
2 ===+ 42.14Z
2.14y4 x
1 ===+
5.13Z 3.0y
2.25 x
5 ===+ 4.14Z
2.0y4.2 x
4 ===+
INF
0Z =
7
4
x
y
3x 4x
2y 3y 2y 3y 4x 3x
P4
P5
2y
3y
2y
P3P5
P2
P0
P1
P4
Ejemplo: F.O. Max 2x+3y
47.14Z 2.35y
3.72 x
0 ===+
14Z 2.67y
3.0 x
2 ===+ 42.14Z
2.14y4 x
1 ===+
12Z2.0y3.0 x
6 ===+ 5.13Z
3.0y2.25 x
5 ===+ 4.14Z
2.0y4.2 x
4 ===+
INF
0Z =12Z =
7
4
x
y
3x 4x
2y 3y 2y 3y 4x 3x
P4
P5
2y
3y
2y
P3P6
P2
P0
P1
P4P5
P6
-
13
Ejemplo: F.O. Max 2x+3y
47.14Z 2.35y
3.72 x
0 ===+
14Z 2.67y
3.0 x
2 ===+ 42.14Z
2.14y4 x
1 ===+
12Z2.0y3.0 x
6 ===+ 5.13Z
3.0y2.25 x
5 ===+ 4.14Z
2.0y4.2 x
4 ===+
INF
0Z =12Z =
7
4
x
y
3x 4x
2y 3y 2y 3y
4x = 5x
4x 3x P5
2y
3y
2y 5x
4x =
P3P6
P2
P0
P1
P4P5
P6
Ejemplo: F.O. Max 2x+3y
47.14Z 2.35y
3.72 x
0 ===+
14Z 2.67y
3.0 x
2 ===+ 42.14Z
2.14y4 x
1 ===+
5.13Z 3.0y
2.25 x
5 ===+ 4.14Z
2.0y4.2 x
4 ===+
INF
28.14Z 1.43y
5.0 x
7 ===+
0Z =12Z =
7
4
x
y
3x 4x
3y 2y 3y
4x = 5x
4x 3x P5
2y
3y
2y 5x
P7
4x =
P7
P3
P2
P0
P1
P4P5
P6
12Z2.0y3.0 x
6 ===+
2y P6
-
14
Ejemplo: F.O. Max 2x+3y
47.14Z 2.35y
3.72 x
0 ===+
14Z 2.67y
3.0 x
2 ===+ 42.14Z
2.14y4 x
1 ===+
5.13Z 3.0y
2.25 x
5 ===+ 4.14Z
2.0y4.2 x
4 ===+
INF
14Z 2.0y
4.0 x
8 ===+ 28.14Z
1.43y5.0 x
7 ===+
0Z =12Z =14Z =
7
4
x
y
3x 4x
3y 2y 3y
4x = 5x
4x 3x P5
2y
3y
2y 5x
P7
P8 4x =
P8 P7
P3
P2
P0
P1
P4P5
P6
12Z2.0y3.0 x
6 ===+
2y P6
Ejemplo: F.O. Max 2x+3y
47.14Z 2.35y
3.72 x
0 ===+
14Z 2.67y
3.0 x
2 ===+ 42.14Z
2.14y4 x
1 ===+
5.13Z 3.0y
2.25 x
5 ===+ 4.14Z
2.0y4.2 x
4 ===+
INF
14Z 2.0y
4.0 x
8 ===+ 28.14Z
1.43y5.0 x
7 ===+
0Z =12Z =14Z =
7
4
x
y
3x 4x
3y 2y 3y
4x = 5x
4x 3x P5
2y
3y
2y 5x
P7
P8 4x =
Como Z8+ > Z5+No se sigue ramificando
por este nodo
P8 P7
P2
P0
P1
P5
P6
12Z2.0y3.0 x
6 ===+
2y P6
-
15
Ejemplo: F.O. Max 2x+3y
47.14Z 2.35y
3.72 x
0 ===+
14Z 2.67y
3.0 x
2 ===+ 42.14Z
2.14y4 x
1 ===+
5.13Z 3.0y
2.25 x
5 ===+ 4.14Z
2.0y4.2 x
4 ===+
INF
14Z 2.0y
4.0 x
8 ===+ 28.14Z
1.43y5.0 x
7 ===+
0Z =12Z =14Z =
7
4
x
y
3x 4x
3y 2y 3y
4x = 5x
4x 3x P5
2y
3y
2y 5x
P8 4x =1y 2y =
1y
2y =P6
P8 P7
P3
P2
P0
P1
P4P5
12Z2.0y3.0 x
6 ===+
2y P6
Ejemplo: F.O. Max 2x+3y
47.14Z 2.35y
3.72 x
0 ===+
14Z 2.67y
3.0 x
2 ===+ 42.14Z
2.14y4 x
1 ===+
5.13Z 3.0y
2.25 x
5 ===+ 4.14Z
2.0y4.2 x
4 ===+
INF
14Z 2.0y
4.0 x
8 ===+ 28.14Z
1.43y5.0 x
7 ===+
0Z =12Z =14Z =
7
4
x
y
3x 4x
3y 2y 3y
4x = 5x
4x 3x P5
2y
3y
2y 5x
P8 4x =1y 2y =
1y
2y =P6
P8 P7
P3
P2
P0
P1
P4P5
12Z2.0y3.0 x
6 ===+
2y P6
-
16
Ejemplo: F.O. Max 2x+3y
47.14Z 2.35y
3.72 x
0 ===+
14Z 2.67y
3.0 x
2 ===+ 42.14Z
2.14y4 x
1 ===+
5.13Z 3.0y
2.25 x
5 ===+ 4.14Z
2.0y4.2 x
4 ===+
INF
14Z 2.0y
4.0 x
8 ===+ 28.14Z
1.43y5.0 x
7 ===+
0Z =12Z =14Z =
7
4
x
y
3x 4x
3y 2y 3y
4x = 5x
4x 3x P5
2y
3y
2y 5x
P8 4x =INF1y 2y =
1y
2y =P6
P9
P8 P7
P3
P2
P0
P1
P4P5
12Z2.0y3.0 x
6 ===+
2y P6
Ejemplo: F.O. Max 2x+3y
47.14Z 2.35y
3.72 x
0 ===+
14Z 2.67y
3.0 x
2 ===+ 42.14Z
2.14y4 x
1 ===+
5.13Z 3.0y
2.25 x
5 ===+ 4.14Z
2.0y4.2 x
4 ===+
INF
14Z 2.0y
4.0 x
8 ===+ 28.14Z
1.43y5.0 x
7 ===+
0Z =12Z =14Z =
7
4
x
y
3x 4x
3y 2y 3y
4x = 5x
4x 3x P5
2y
3y
2y 5x
P10
P8 4x =2.14Z
1.0y5.6 x
8 ===+
INF1y 2y =
1y
2y =P6
P9P10
P8 P7
P3
P2
P0
P1
P4P5
12Z2.0y3.0 x
6 ===+
2y P6
-
17
Ejemplo: F.O. Max 2x+3y
47.14Z 2.35y
3.72 x
0 ===+
14Z 2.67y
3.0 x
2 ===+ 42.14Z
2.14y4 x
1 ===+
12Z2.0y3.0 x
6 ===+ 5.13Z
3.0y2.25 x
5 ===+ 4.14Z
2.0y4.2 x
4 ===+
INF
14Z 2.0y
4.0 x
8 ===+ 28.14Z
1.43y5.0 x
7 ===+
0Z =12Z =14Z =
7
4
x
y
3x 4x
2y 3y 2y 3y
4x = 5x
4x 3x P5
2y
3y
2y P65x
P10
INF1y 2y =
1y ptimo
P8 P7
P3P6
P2
P0
P1
P4P5
P9
2.14Z1.0y5.6 x
8 ===+ P10
2y =
