PROGRAMACIÓN ENTERA
INTRODUCCIÓN
No siempre es admisible que las variables
de un PL tomen valores continuos:
• Decisiones dicotómicas (si-no)
• Decisiones que deben tomarse en unidades
discretas
Problema de Programación entera:
Cuando en un problema existen variables
que deben tomar valores discretos y la
función objetivo y las restricciones son
lineales.
Problema de Programación binaria o 0-1:
Cuando los valores que pueden tomar las
variables discretas son tan sólo 0 o 1.
Cap. 9 Programación Entera y Mixta 1
PROGRAMACIÓN ENTERA
INTRODUCCIÓN
La PE tiene gran cantidad de aplicaciones
en todos los campos.
Hay problemas que no pueden resolverse
con las técnicas actuales por:
• Disponibilidad de tiempo de
ordenador
• Capacidad de memoria
Para evitar esto parece sensato calcular la
solución de un PE redondeando la
solución continua.
Pero el redondeo no es aconsejable
debido a:
• La solución redondeada no es
necesariamente óptima. En muchos
casos, ni siquiera estará cera del
óptimo.
• La solución redondeada puede no
ser factible.
Cap. 9 Programación Entera y Mixta 2
PROGRAMACIÓN ENTERA
INTRODUCCIÓN
EJEMPLO
Max (z) = y1 + y2
sujeto a:
-2 y1 + 2 y2 1
-8 y1 + 10 y2 13
y1, y2 {0,1,2,...}
La solución continua es:
y1 = 4
y2 = 4,5
y2
z = 8,5
Solución
Entera
Cap. 9 Programación Entera y Mixta
y1 3
PROGRAMACIÓN ENTERA
PURA (PE)
Todas las variables están restringidas a
tomar valores enteros.
Programación Entera:
Max (z) = cT y
sujeto a:
Ay < b
yj {0,1,2,...} j = 1,2,... n
Programación Entera Binaria:
Max (z) = cT y
sujeto a:
Ay < b
yj {0,1} j = 1,2,... n
Cap. 9 Programación Entera y Mixta 4
PROGRAMACION ENTERA
MIXTA (MIP)
Algunas variables de decisión están
restringidas a tomar valores enteros,
mientras que otras pueden tomar valores
continuos.
Un problema de MIP puede expresarse
como:
Max (z) = cT x + dT y
sujeto a:
Ax + By < b
x>0
yj {0,1,2,...} j = 1,2,... n
En este caso:
• x: vector de variables que toman
valores continuos.
• y: contiene n variables enteras
Cap. 9 Programación Entera y Mixta 5
TIPOS DE ALGORITMOS DE
PROGRAMACIÓN ENTERA
Algoritmos de PE Pura (IP)
• Enumerativos:
• Branch and Bound
• Balas, etc
• De planos cortantes:
• Gomory
• Otros
Algoritmos de PE Mixta (MIP)
• Enumerativos:
• Branch and Bound
• Balas, etc
• De descomposición dual:
• Benders
• Otros
Cap. 9 Programación Entera y Mixta 6
ALGORITMOS DE IP:
ALGORITMOS ENUMERATIVOS
Estos algoritmos obtienen la solución en
base a enumerar, implícita o
explícitamente, todas las soluciones
posibles y escogiendo la mejor de todas
ellas.
ENUMERACIÓN EXPLÍCITA:
• Calcular todas las posibles soluciones y
escoger la mejor de ellas.
• Este método tiene graves inconvenientes:
• Ejemplo: En PE 0-1 el número de
posibles soluciones es 2 nºvar.enteras
4 variables: 24 = 16 soluciones o
nodos
10 variables: 210 = 1.024 nodos
20 variables 220 = 1.048.276 nodos
• En problemas complejos, un ordenador no
sería capaz de enumerar todas las posibles
soluciones.
Cap. 9 Programación Entera y Mixta 7
ALGORITMOS DE IP:
ALGORITMOS ENUMERATIVOS
ENUMERACION IMPLÍCITA:
• Aplican un conjunto de reglas para
evitar enumerar soluciones
infactibles o peores que la mejor
solución factible que se haya
localizado hasta el momento.
• La familia de algoritmos
enumerativos más importante es la
de los algoritmos de Branch and
Bound (BB).
• Prácticamente todos los códigos
comerciales de PE están basados en
un algoritmo del tipo BB.
Cap. 9 Programación Entera y Mixta 8
ALGORITMOS DE BRANCH AND
BOUND
Tienen su origen en Land y Doig (1960).
Esta metodología se ha sofisticado
posteriormente pero, la idea básica es muy
sencilla.
EJEMPLO:
Max (z) = x1 + 3 x2
sujeto a:
x2 1,87
22 x1 + 34 x2 105
x1 {0,1,2,...}
x2 {0,1,2,...}
La solución continua del problema es:
x1 = 1,88
x2 = 1,87
z = 7,49
Cap. 9 Programación Entera y Mixta 9
ALGORITMOS DE BRANCH AND
BOUND
Bound:
• Asociamos a esta solución el nodo 0.
• Cualquier solución entera tendrá un
valor de la función objetivo menor o
igual que z = 7,49
• Esto se debe a que al poner la
condición de integralidad el problema
se hace más restrictivo.
Branch:
• A partir del nodo 0 se generan 2
problemas añadiendo a uno de ellos
x1 2 (nodo1) y x1 1 (nodo2).
• Es decir, buscamos la solución a
cada lado de la variable que está
más cercana a tomar un valor
entero.
Cap. 9 Programación Entera y Mixta 10
ALGORITMOS DE BRANCH AND
BOUND
• Las soluciones a ambos problemas
son:
nodo 1 (x1 2): x1= 2; x2 = 1,79; z = 7,38
nodo 2 (x1 1): x1= 1; x2 = 1,87; z = 6,61
• No tenemos soluciones enteras, por
tanto, debemos seguir.
• En el nodo 1 el valor de la función
objetivo es mayor. Seguimos
ramificando el nodo 1:
• nodo 3 (x2 2)
• nodo 4 (x2 1)
nodo 3 (x2 2): INFACTIBLE
nodo 4 (x2 1): x1= 3,23; x2 = 1; z = 6,23
Cap. 9 Programación Entera y Mixta 11
ALGORITMOS DE BRANCH AND
BOUND
Branch:
• En el nodo 4 el valor de z es inferior
al del nodo 2. Debemos seguir por el
nodo 2.
Bound:
• A partir del nodo 2 se generan 2
nuevos nodos:
• nodo 5 (x2 2)
• nodo 6 (x2 1)
nodo 5 (x2 2): INFACTIBLE
nodo 6 (x2 1): x1= 1; x2 = 1; z = 4
• Ya tenemos una solución entera,
pero el valor de z es menor que en el
nodo 4.
Branch:
• Como el valor de z en el nodo 6 es
menor que en el 4, ramificamos por
el 4.
Cap. 9 Programación Entera y Mixta 12
ALGORITMOS DE BRANCH AND
BOUND
Bound:
• Del nodo 4 surgen dos nuevos
nodos:
• nodo 7 (x1 3)
• nodo 8 (x1 4)
nodo 7 (x1 3): x1= 3; x2 = 1; z = 6
nodo 8 (x1 4): x1= 4; x2 = 0,5; z = 5,5
La solución del nodo 7 es entera y mejor
que la del nodo 6.
La solución del nodo 8 es continua y peor
que la del nodo 7.
No queda ninguna posibilidad de mejorar
el valor de la función objetivo.
Por tanto tenemos la siguiente solución
entera:
x1= 3 x2 = 1 z=6
Cap. 9 Programación Entera y Mixta 13
ALGORITMOS DE BRANCH AND
BOUND
x1 =1.88
x2 = 1.87
z = 7.49
x1 1 x1 2
Nodo 2 Nodo 1
x1 =1 x1 =2
x2 = 1.87 x2 = 1.79
z = 6.61 z = 7.38
x2 1 x2 2
Nodo 6
x1 = 1 Nodo 5
x2 = 1 Infactible
x2 1 x2 2
z=4
Nodo 4
x1 =3.23 Nodo 3
x2 = 1 Infactible
z = 6.23
x1 3 x1 4
Nodo 7 Nodo 8
x1 =3 x1 = 4
x2 = 1 x2 = 0.5
z=6 z = 5.5
ÓPTIMA
Cap. 9 Programación Entera y Mixta 14
