UNIVERSIDAD RICARDO PALMA
FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE
INGENIERÍA
INVESTIGACION OPERATIVA
PROGRAMACION LINEAL ENTERA
Prof. Puelles Bulnes, María Elizabeth
[Link]@[Link]
Semana 09 16/10/2019
ACTIVIDADES UNIDAD Nº 4: PROGRAMACION
ENTERA Y PROGRAMACION DINAMICA
Logros de aprendizaje:
• Modela y resuelve diversos problemas de
optimización que requieran el uso de variables
enteras o binarias con claridad y precisión.
• Resuelve problemas de optimización a través de
la técnica de la Programación Dinámica con
claridad y precisión.
Nº horas: 10
SEMANAS Nº 9 y 10.
UNIVERSIDAD RICARDO PALMA
FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE
INGENIERÍA
PROGRAMACION ENTERA
Es aquel cuya solución óptima tiene sentido
solamente si una parte o todas las variables de
decisión toman valores restringidos a números
enteros, permitiendo incorporar en el modelamiento
matemático algunos aspectos que quedan fuera del
alcance de los modelos de Programación Lineal.
UNIVERSIDAD RICARDO PALMA
FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE
INGENIERÍA
PROGRAMACION ENTERA
UNIVERSIDAD RICARDO PALMA
FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE
INGENIERÍA
PROGRAMACION ENTERA
UNIVERSIDAD RICARDO PALMA
FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE
INGENIERÍA
PROGRAMACION ENTERA
UNIVERSIDAD RICARDO PALMA
FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE
INGENIERÍA
PROGRAMACION LINEAL ENTERA
ALGORITMO RAMIFICACION Y ACOTAMIENTO
(Branch & Bound)
UNIVERSIDAD RICARDO PALMA
FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE
INGENIERÍA
PROGRAMACION LINEAL ENTERA
ALGORITMO RAMIFICACION Y ACOTAMIENTO
(Branch & Bound)
UNIVERSIDAD RICARDO PALMA
FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE
INGENIERÍA
PROGRAMACION LINEAL ENTERA
ALGORITMO RAMIFICACION Y ACOTAMIENTO
(Branch & Bound)
UNIVERSIDAD RICARDO PALMA
FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE
INGENIERÍA
PROGRAMACION LINEAL ENTERA
ALGORITMO RAMIFICACION Y ACOTAMIENTO
(Branch & Bound)
UNIVERSIDAD RICARDO PALMA
FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE
INGENIERÍA
PROGRAMACION LINEAL ENTERA
ALGORITMO RAMIFICACION Y ACOTAMIENTO
(Branch & Bound)
PL0
PL1 PL2
UNIVERSIDAD RICARDO PALMA
FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE
INGENIERÍA
PROGRAMACION LINEAL ENTERA
ALGORITMO RAMIFICACION Y ACOTAMIENTO
(Branch & Bound)
PL1
UNIVERSIDAD RICARDO PALMA
FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE
INGENIERÍA
PROGRAMACION LINEAL ENTERA
ALGORITMO RAMIFICACION Y ACOTAMIENTO
(Branch & Bound)
UNIVERSIDAD RICARDO PALMA
FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE
INGENIERÍA
PROGRAMACION LINEAL ENTERA
ALGORITMO RAMIFICACION Y ACOTAMIENTO
(Branch & Bound)
UNIVERSIDAD RICARDO PALMA
FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE
INGENIERÍA
PROGRAMACION LINEAL ENTERA
ALGORITMO RAMIFICACION Y ACOTAMIENTO
(Branch & Bound)
UNIVERSIDAD RICARDO PALMA
FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE
INGENIERÍA
PROGRAMACION LINEAL ENTERA
ALGORITMO RAMIFICACION Y ACOTAMIENTO
(Branch & Bound)
UNIVERSIDAD RICARDO PALMA
FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE
INGENIERÍA
PROGRAMACION LINEAL ENTERA
ALGORITMO RAMIFICACION Y ACOTAMIENTO
(Branch & Bound)
UNIVERSIDAD RICARDO PALMA
FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE
INGENIERÍA
PROGRAMACION LINEAL ENTERA
ALGORITMO RAMIFICACION Y ACOTAMIENTO
(Branch & Bound)
2)
UNIVERSIDAD RICARDO PALMA
FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE
INGENIERÍA
PROGRAMACION LINEAL ENTERA
ALGORITMO RAMIFICACION Y ACOTAMIENTO
(Branch & Bound)
UNIVERSIDAD RICARDO PALMA
FACULTAD DE INGENIERÍA
ESCUELA ACADÉMICO PROFESIONAL DE
INGENIERÍA
PROGRAMACION LINEAL ENTERA
ALGORITMO RAMIFICACION Y ACOTAMIENTO
(Branch & Bound)
EJERCICIO
Se tiene el siguiente modelo de Programación Entera y ser desea
maximizar los ingresos. Encuentre la solución la solución óptima
aplicando el método de ramificación y acotamiento.
Max Z = 5X1 + 4X2
Sujeto a 1) X1 + X2 ≤ 5
2) 10X1 + 6X2 ≤ 45
X1, X2 enteros no negativos