Objetivo
• Al terminar esta sesión, el participante será capaz de:
• Reconocer un problema de programación lineal entera.
• Formular un modelo de programación lineal entera.
Tema a tratar
• Formular y resolver problemas de programación lineal entera.
Programación Entera
INTRODUCCIÓN (1)
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.
INTRODUCCIÓN (2)
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.
EJEMPLO
Max (z) = y1 + y2 La solución continua es: La solución entera es:
y1 = 4
sujeto a: y2 = 4,5
-2 y1 + 2 y2 1 z = 8,5
-8 y1 + 10 y2 13
y1, y2 {0,1,2,...}
PROGRAMACIÓN ENTERA PURA (PE)
Todas las variables están restringidas a tomar valores enteros.
Programación Entera: Programación Entera Binaria:
Max (z) = cT y Max (z) = cT y
sujeto a: sujeto a:
Ay < b Ay < b
yj {0,1,2,...} j = 1,2,... n yj {0,1} j = 1,2,... n
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
TIPOS DE ALGORITMOS DE PROGRAMACIÓN ENTERA
Algoritmos de PE Pura (IP) Algoritmos de PE Mixta (MIP)
• Enumerativos: • Enumerativos:
• Branch and Bound
• Branch and Bound
• Balas, etc
• Balas, etc • De descomposición dual:
• De planos cortantes: • Benders
• Gomory • Otros
• Otros
ALGORITMOS DE IP: ALGORITMOS ENUMERATIVOS (1)
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º[Link]
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.
ALGORITMOS DE IP: ALGORITMOS ENUMERATIVOS (2)
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.
ALGORITMOS DE BRANCH AND BOUND (1)
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
ALGORITMOS DE BRANCH AND BOUND (2)
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.
ALGORITMOS DE BRANCH AND BOUND (3)
• 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
ALGORITMOS DE BRANCH AND BOUND (4)
• 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
ALGORITMOS DE BRANCH AND BOUND (5)
• 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
ALGORITMOS DE BRANCH AND BOUND (6)
