Programación Entera
Profesor: Hermes Pantoja Carhuavilca
Programación entera
– En muchos problemas reales las variables sólo
pueden tomar valores enteros
– Ejemplos:
• decisiones sobre inversiones, compras, arranques, etc.
• Cantidades de productos no divisibles, personas, etc.
– Problemas con el método Simplex:
• soluciones no están en vértices
• ¿cómo saber si tenemos una solución?
2
•En este capítulo veremos problemas que se
podrían formular y resolver como problemas de
programación lineal, excepto por la desagradable
circunstancia de que se requiere que algunas o
todas las variables tomen valores enteros.
•Dichos problemas se llaman PE (Programación
Entera).
TIPOS DE MODELOS
PARA
PROGRAMACIÓN LINEAL ENTERA
Modelo entero puro (PEP)
Minimizar 6X1 + 5X2 + 4X3
Sujeto a 108X1 + 92X2 + 58X3 576
7X1 + 18X2 + 22X3 83
X1, X2, X3 enteros
Programación lineal entera-mixta
(PLEM)
Minimizar 6X1 + 5X2 + 4X3
Sujeto a 108X1 + 92X2 + 58X3 576
7X1 + 18X2 + 22X3 83
X1, X2, X3 0 ; X1 y X2 enteros.
Programación entera
– La solución no tiene que estar en un vértice, ni
contigua a un vértice
Solución relajada
Solución entera
9
Programación entera
• Métodos de solución:
– Comparar todas las alternativas (no es eficiente)
– Procedimientos eficientes para seleccionar o
descartar alternativas
• Basados en la aproximación del problema mediante
problemas lineales (que sabemos resolver)
10
Programación entera
– Procedimiento más simple:
• ignorar la condición de que las variables sean enteras, y
redondear la solución
– Inconvenientes:
• ¿tiene significado la solución no entera?
• ¿cómo se redondea la solución?
• ¿cómo se obtiene una solución redondeada factible?
• ¿cuándo es óptima una solución redondeada?
11
Programación entera
– Método más sofisticado:
• introducir restricciones adicionales que no eliminen
soluciones enteras (cubierta convexa)
– Si las soluciones enteras son vértices, podemos
aplicar el método Simplex
– Inconvenientes:
• ¿Cómo se calculan las restricciones necesarias?
• ¿Cuántas hacen falta?
12
Programación entera
– Cubierta convexa
13
Programación entera
• Método de “branch and bound”
– Se trata de:
• dividir la región factible, y
• descartar aquellas partes en las que no puede
encontrarse la solución
– Partes que no pueden descartarse:
• se calcula la solución por el método Simplex, o
• se subdividen en nuevas partes añadiendo restricciones
14
Programación entera
• Procedimiento:
– Dado el problema min c Tx
s.a Ax = b
x0
xi entera i
se resuelve su versión relajada (P0)
• Si la solución de (P0) es entera, se termina
• Si no lo es, se subdivide el problema en varios
15
Programación entera
• División del problema
– Supongamos que la solución del problema
relajado es xk*, y que (xk*)i no es entera
– En la solución (entera) se cumplirá una de las dos
condiciones siguientes:
xi (xk*)i , xi (xk*)i + 1
donde x denota la parte entera de x
16
Programación entera
• División del problema
– Se generan los dos problemas siguientes:
P1 = P0 {xi (xk*)i }, P2 = P0 {xi (xk*)i +1}
• En general, se tiene una lista de problemas pendientes
de resolver
• Se toman los problemas de la lista, y se resuelven hasta
que la lista queda vacía
17
Programación entera
• Ejemplo gráfico
Solución P0
P4 no factible
Solución P1 Solución P2
Solución entera Solución P3
18
Programación entera
• ¿Qué sucede al resolver subproblemas?
– Subproblema no factible:
• nada
– Subproblema con solución no entera:
• se generan nuevos subproblemas
– Subproblema con solución entera:
• se compara con la mejor solución entera hasta el
momento
19
Programación entera
• Eliminación de subproblemas
– Basada en mejor solución entera
• Mejor valor de la función objetivo para una solución
entera (hasta el momento): z
– Si para un subproblema se cumple
c Txk* > z
• descartar el subproblema (y todos los subproblemas
que se generen de él)
• Todas sus soluciones enteras son peores que z
20
Programación entera
• Arbol de subproblemas
P0
- Búsqueda en profundidad:
P2 P1 P0, P1, P3, P4, P2, P5, P7
P5 P6 P3 P4 P9, P10, P11, P12, P8, P6
P7 P8
- Búsqueda en extensión:
P9 P10
P0, P1, P2, P3, P4, P5, P6,
P11 P12 P7, P8, P9, P10, P11, P12
21
Programación entera
• Ejemplo:
max 8x1 + 9x2
s.a 76 x1 + 68 x2 767
-38 x1 + 32 x2 29
2 x2 3
x 0 entera
– Solución del problema relajado:
x1 = 9/2 , x2 = 25/4
22
Programación entera
– Nuevas restricciones:
x1 4 , x1 5
• Primer subproblema:
x 1 + s4 = 4 , s4 0
• Nueva solución del primer subproblema:
x1 = 4 , x2 = 181/32
Universidad Carlos III de
Madrid – Ingeniería
Informática 23
Investigación Operativa - Curso
Ejemplo 2
• Min -18X1 – 8 X2
• S.A.
4.8 X1 + 2 X2≤ 25
-12 X1 - X2 ≤ -22.5
X1, X2 ≥0; X1, X2 Enteros
• Paso 0 Inicializar
Resolvemos PL y obtenemos Z*PL = -98.75 con
X1*= 1.0417 y X2*=10. Elegimos como viable
X1=2, X2=0 dando ZU=-36
Paso 1 Ramificar
• Como X1* no es entero
Ramificar en X1 zLP=-98.75
• Dos subproblemas: X1=1.0417
X2= 10
– Mismo modelo y
adicionalmente X1≤1 Implica
nuevo espacio de posibilidades
es: F∩(X1≤1 )
– X1≥2; F∩(X1≥2 )
Min z(x)
Min z(x)
xєF
xєF
X1 ≥2
X1 ≤1
Paso 2 Acotar
• Resolvemos para cada
zLP=-98.75
subproblema el óptimo (z*L X1=1.0417
del subproblema) X2= 10
ZU=-36
Min z(x)
Min z(x)
xєF
xєF
X1 ≥2
X1 ≤1
ZL=-97.6
No factible
Paso 3 Sondear
• El subproblema Sondeado C
zLP=-98.75
genera que la nueva ZU= -97.6 X1=1.0417
X2= 10
ZU=-36
Min z(x)
Min z(x)
xєF
xєF
X1 ≥2
X1 ≤1
ZL=-97.6
No factible
X1=2
Sondeado B
X2=7.7
Paso 4 Prueba
• No todos los subproblemas han quedado
sondeados por lo tanto regresar a Paso 1
Min z(x)
xєF
X1 ≥2
ZL=-97.6
Min z(x) Min z(x)
xєF xєF
X1 ≥2, X2 ≤7 X1 ≥2, X2 ≥ 8
ZL=-97.25 ZL=-97.6
X1=2.29, X2=7 No factible
Min z(x)
xєF
X1 ≥2, X2 ≤7
ZL=-97.25
X1=2.29, X2=7
ZL=-92
X1=2, X2=7
ZL=-96.4
Sondeado C
X1=3, X2=5.3 ZU=-92
ZL=-96.25
X1=3.12, X2=5 No factible
ZL=-94
X1=3, X2=5
ZL=-95.2
Sondeado C
X1=4, X2=2.9
ZU=-94
ZL=-94.75
No factible
X1=4.375, X2=2
ZL=-88 ZL=-94.
X1=4., X2=2 X1=5, X2=.5
Sondeado A Sondeado A
