Programacin Entera
Investigacin Operativa
Universidad Tecnolgica Nacional Facultad Regional Mendoza
Programacin Entera 01
Aplicaciones de programacin lineal suposicin de divisibilidad
grandes limitaciones
Exigir valores enteros
Problema De Programacin entera (PE)
Programacin Entera 02
Programacin Entera Mixta (PEM)
variables enteras y la suposicin de divisibilidad se cumple para el resto
Programacin Entera Pura (PEP)
Todas las variables enteras
Arbol enumerando todas las soluciones enteras posibles a: Max (3x1 + 2x2 + x3) x 1 + x 2 + x3 s.a. 2x1 x2 x3 x1 + x 2 x3 x1 x2 x3 x1 , x 2 , x 3 <=4 <=0 <=0 <=2 <=2 <=2 >=0 y enteras
X1=0 ( 0 , _ ,_ ) 1 ( 1 , _ ,_ ) X2=0
(0,0,--)
Programacin Entera 03
Nivel 0 ( _ , _ ,_ ) 0
X1=1 2
X1=2 3 X2=0 ( 2 , _ ,_ ) 1
1
(0,1,--)
2
(0,2,--)
X2=0 6 1 20 2 21 7
1 8
2 9
2 11 12
(2,2,--)
4 1 2
5 X3=0 19
10
(1,2,--)
X3=0 13
(0,0,0)
(1,0,--)
X3=0 28
1 29
2 30
X3=0 37
1 38
2 39 3
14 15
(0,0,2)
(0,0,1)
(0,2,0) (0,2,1) (0,2,2)
(1,2,0) (1,2,1) (1,2,2) (2,2,0) (2,2,1) (2,2,2)
Programa Lineal en el nodo 3: Max (6 + 2x2 + x3 ) s.a. 2 + x2 + x3 4 x2 x3 2 + x2 x3 X2 x3 x2 , x3 <=4 <=0 <=0 <=2 <=2 >=0
Programacin Entera 04
Solucin PL: 0 X1=4/3 , X2=2/3 , X3=2 Z=22/3 X1=2 ( 2 , _ ,_ ) 3 PL infactible ( _ , _ ,_ )
Todos los nodos debajo del nodo 3 se eliminan
X2=0 1 10 11 (2,1,--) X3=0 1 2 33
(2,0,2)
2 12
(2,2,--)
X3=0 31
(2,0,0)
32
(2,0,1)
...
1 37
(2,2,0)
2 39
(2,2,2)
38
(2,2,1)
Programacin Entera 05
Programa Lineal en el nodo 2: Max s.a. (3 + 2x2 + x3) 1 + x2 + x3 2 x2 x3 1 + x2 x3 X2 X3 x2 , x3 <=4 <=0 <=0 <=2 <=2 >=0
Solucin PL: X1=4/3 , X2=2/3 , X3=2 Z=22/3 X1=1 2 ( 1 , _ ,_ ) 2 8 X3=0 28 9 0 ( _ , _ ,_ )
Solucin PL: X1=1 , X2=1 , X3=2 Z=7
X1=2 3
PL infactible ( 2 , _ ,_ )
X2=0
(1,0,--)
(1,2,--)
Todos los nodos debajo del nodo 2 se eliminan
X3=0 22
(1,0,0)
1 23
2 24
(1,0,2)
1 29
2 30
(1,0,1)
(1,2,0)(1,2,1) (1,2,2)
Programacin Entera 06
Programa Lineal en el nodo 1: Max (0 + 2x2 + x3) s.a. 0 + x2 + x3 0 x2 x3 0 + x2 x3 x2 X3 x2 , x3
X1=2 2 ( 1 , _ ,_ ) X2=0 1
(0,1,--)
Solucin PL: X1=4/3 , X2=2/3 , X3=2 Z=22/3 0 Solucin PL: X1=0 , X2=2 , X3=3 X1=0 Z=6 ( 0 , _ ,_ ) 1 X1=1 ( _ , _ ,_ )
<=4 <=0 <=0 <=2 <=2 >=0
( 2 , _ ,_ ) Solucin PL:
2
(0,2,--)
X1=1 , X2=1 , X3=2 Z=7 6
(1,0,--)
(0,0,--)
4 1 2
5 X3=0 19 1
X3=0
2 21
13 14 15
(0,0,0) (0,0,1) (0,0,2)
20
(0,2,0)(0,2,1) (0,2,2)
Todos los nodos debajo del nodo 1 se eliminan
Paso hacia adelante: Iteracin 1: Examinar el nodo (1,_,_) Max s.a. (2 + 3x2 + x3) 1 + x2 + x3 <= 5 -1 + 2x2 x3 <=1 1+ x2 x3 <= 0 x2 , x3 >=0
Programacin Entera 07
Solucin PL: X1=0,5 , X2=2 , X3=2,5 Z=9,5 0 ( _ , _ ,_ )
Paso hacia Adelante
X1=1 1 ( 1 , _ ,_ )
Iteracin 2: Examinar el nodo (1,2,_) Max s.a. (2 + 6 + x3) 1 + x2 + x3 <= 5 -1 + 2x2 x3 <=1 1 + 2 x3 <= 0 x3 >=0
( _ , _ ,_ ) X1=1 Solucin PL: ( 1 , _ ,_ ) 1 X1=1 , X2=1,5 , X3=2,5 Z=9 X2=2 Paso hacia Adelante 2 ( 1 , 2 ,_ )
Paso Lateral: Iteracin 3: Examinar el nodo (1,1,_) Max (2 + 3 + x3) s.a. 1 + 1 + x3 -1 + 2 x3 1 + 1 x3 x3 <= 5 <=1 <= 0 >=0
0 ( _ , _ ,_ ) X1=2
Programacin Entera 08
( 1 , _ ,_ ) X2=1 3
1 X2=2 2 ( 1 , 2 ,_ ) Problema relajado infactible
( 1 , 1 ,_ )
Paso lateral
Paso hacia Atrs: Iteracin 4: Examinar el nodo (2,_,_) Max (4 + 3x2 + x3) s.a. 2 + x2 + x3 -2 + 2x2 x3 2 + x2 x3 x2, x3
Programacin Entera 09
<= 5 <=1 <= 0 >=0
( _ , _ ,_ ) 0 X1=2 X1=1 ( 1 , _ ,_ ) X2=1 Solucin PL: X1=1 , X2=1 , X3=3 Z=8 3 Paso hacia atrs 1 Paso lateral X2=2 2 ( 1 ,2 ,_ ) 4 ( 2 , _ ,_ )
( 1 ,1 ,_ )
Iteracin 5: Examinar el nodo (0,_,_)
( _ , _ ,_ ) X1=0
0 X1=2 X1=1 Solucin PL: X1=2 , X2=0,5 , X3=2,5 Z=8 4 ( 2 , _ ,_ ) X2=2 2 ( 1 ,2 ,_ )
( 1 , _ ,_ ) ( 0 , _ ,_ ) 5 Paso lateral
X2=1
Max s.a.
(0 + 3x2 + x3) 0 + x2 + x3 -0 + 2x2 x3 0 + x2 x3 x2, x3
<= 5 <=1 <= 0 >=0
3 ( 1 ,1 ,_ )
( _ , _ ,_ ) X1=0
0 X1=2 X1=1
( 1 , _ ,_ ) ( 0 , _ ,_ ) 5
4 ( 2 , _ ,_ ) X2=2 2 ( 1 ,2 ,_ )
Programacin Entera 10
Solucin PL: X1=0 , X2=0 , X3=0 Z=9 Solucin ptima 3 ( 1 ,1 ,_ )
X2=1
Pasos del algoritmo de ramificacin
Programacin Entera 11
Paso 0: Inicializacin: Resuelva el programa lineal asociado con el nodo 0. A:Si el Problema es infactible, detenerse. El programa entero tambin lo es. B:Si este problema tiene una solucin ptima que satisface todos los requerimientos enteros, detenerse. Esta solucin es ptima para el programa entero tambin. C:Si este problema tiene una solucin ptima que no satisface los requerimientos enteros, llame al nodo cero actual y vaya al paso 1. Paso 1: D un paso hacia delante:Descienda un nivel en el rbol seleccionando una variable cuyo valor fraccional actual est lo ms alejado de un entero y fijarlo en el menor entero mayor que su valor fraccional. Llame al nodo actual y siga con el paso dos.
Programacin Entera 12
Paso 2: examine un nodo: resuelva el programa lineal asociado con el nodo actual. A: Si este problema lineal es infactible, elimine ste y todos los nodos debajo inferior y vaya al paso 3. B: Si este programa lineal tiene una solucin ptima que satisface todos los requerimientos enteros, entonces determine si la solucin entera factible proporciona una cota inferior mayor que la cota actual.Elimine todos los nodos debajo de ste y vaya al paso 3. C: Si este programa lineal tiene una solucin ptima que no satisface todos los requerimientos enteros, entonces determine si el valor de la funcin objetivo es menor que la cota inferior actual. Si es as, elimine todos los nodos debajo de ste y vaya al paso 3. Si no , redondee la solucin actual para ver si da una mejor cota inferior que la actual y vaya al paso 1.
Programacin Entera 13
Paso 3: D un paso lateral: muvase hacia el nodo no examinado ms cercano en el mismo y a la derecha del nodo actual y vaya al paso 2, si no existe tal nodo, muvase al nodo mas a la izquierda y vaya al paso 2. si no existe tal nodo,vaya al paso 4. Paso 4: D un paso hacia atrs: retroceda un nivel del nodo actual al nuevo nodo actual. Si el nuevo nodo actual es el nodo 0, detengase. La solucin entera asociada con la mejor cota inferior es la solucin ptima al problema entero original. Si el nuevo nodo actual no es el nodo 0, vaya al paso 3. Si no encuentra la solucin entera factible, el problema original entero es infactible.
Programacin Entera
Gracias por su atencin
Aghetoni Leandro Falconi Valeria Llanos Christian Petri Mara Lila Sutter Leandro
