Programación entera
Investigación de operaciones
Docente: Alejandra Arana Lugo
Alumno: Basni Vetvirai Serrano Lopez
¿Qué es?
El modelo matemático para programación entera es
sencillamente el modelo de programación lineal con la
restricción adicional de que las variables deben tener valores
enteros
Modelos de programación entera
Un modelo de programación 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.
Programación entera mixta (PEM)
A esta categoría pertenecen aquellos problemas de
optimización que consideran variables de decisión enteras o
binarias pero no de forma exclusiva.
Problemas en los que se puede utilizar:
• Incorporación de costos fijos
• Problemas de localización y transporte
• Problemas de generación eléctrica
Programación entera pura (PEP)
En esta categoría encontramos aquellos modelos de
programación entera que consideran exclusivamente variables
de decisión que adoptan valores enteros o binarios.
Problemas en los que se puede utilizar:
• Problemas de asignación
• Problemas de corte de rollos
• Selección de invitados a una boda
• Programación de la explotación forestal
• Problema de la mochila
Programación Entera Binaria (PEB)
Es un método perteneciente a la programación lineal, por lo que su
base es un algoritmo matemático que tiene como finalidad resolver
un problema indeterminado formulado a través de ecuaciones
lineales, optimizando así una función objetivo también lineal que
generalmente se refiere a costo o a tiempo.
Problemas en los que se puede utilizar:
• Despacho de envíos
• Diseño de redes
• Programación de actividades
Método grafico de programación entera
Cada una de las ecuaciones que forman un sistema lineal de
dos ecuaciones con dos incógnitas es la de una función de
primer grado, es decir, una recta. El método gráfico para
resolver este tipo de sistemas consiste, por tanto, en
representar en unos ejes cartesianos, o sistema de
coordenadas, ambas rectas y comprobar si se cortan y, si es
así, en dónde se cortan.
Método de ramificación y acotación
Su operatoria consiste en linealizar el modelo de
Programación Entera, es decir, resolver éste como si fuese un
modelo de Programación Lineal y luego generar cotas en
caso que al menos una variable de decisión (entera) adopte
un valor fraccionario.
Método heurístico para problemas
binarios
Un método heurístico es un procedimiento para resolver un
problema de optimización bien definido mediante una
aproximación intuitiva, en la que la estructura del problema se
utiliza de forma inteligente para obtener una buena solución.
Software
WINQSB
SOLVER
LINGO
TORA
MATLAB
LINDO
Ejercicio de ramificación y acotamiento
Ejercicio: Se hace otra rama y se coloca el valor al entero
hacia arriba, se agrega una nueva restricción x1 ≥ 4
“se pone así cuando es entero hacia arriba”
Resuelto mediante el método grafico o simplex
Se resuelve la rama 1, y se iguala de manera arbitraria
Encontrar el valor de la variable desconocida
Paso 1: Elegir x1 o x2 de manera arbitraria, se elige x1 y se es decir x2, se despeja para cada restricción
hace una rama y se coloca el valor al entero hacia abajo, se
agrega una nueva restricción x1≤3 “se pone así cuando es
entero hacia abajo”
Comprobar regla de desigualdad para cada Hacemos los mismos pasos con la rama 2, se
restricción “cuando se cumplan todas las iguala a 0
restricciones esos serán los valores que tomaran x1
y x2 para sustituir en F.O.”
Encontrar el valor de la variable desconocida
es decir x2, se despeja para cada restricción
Se sustituye en F.O.
Colocamos los resultados en rama 1
Comprobar regla de desigualdad para cada restricción
“cuando se cumplan todas las restricciones esos serán m
los valores que tomaran x1 y x2 para sustituir en F.O.”
Se sustituye en F.O Se toma x2 y se pone el entero hacia abajo
Colocamos los resultados en rama 2
m
Se toma x2 y se pone el entero hacia arriba
Las variables x2 no son enteras, por lo tanto se debe seguir
ramificando y como es Max se debe tomar la rama de mayor valor,
entonces se sigue ramificando la rama 1
Se iguala la primer rama a 0
Encontramos el valor de la variable desconocida Se sustituye en F.O
Hacemos los mismo pasos para la rama 2
n
Comprobar regla de desigualdad Sale solución no factible
Por lo tanto la rama 3 es la solución optima
