PROGRAMACION ENTERA
Como se ha visto ya en Programación Lineal, el cual busca obtener la solución óptima
para una función objetivo dado sus respectivas restricciones, ahora la Programación
Entera tendrá un ligero cambio, y es que ahora las variables del problema pueden tomar
valores enteros. Esto hace que el método de solución sea distinto al de Programación
Lineal ya que las variables se restringen a que solo tomen valores enteros.
Generalmente la estructura de la Programación Entera es la misma que la de
Programación Lineal, salvo algunos detalles:
Max / Min Z cT x
s.a.
Ax , , b
x0
xi Z para i I 1, 2,..., n
Como se ve en la última línea, se encuentra la condición de que las variables deben
tomas valores enteros para un conjunto de valores, y de estos valores se pueden hacer
tres clasificaciones de la Programación Entera:
Programación Entera Pura: cuando todas las variables del problema solo pueden
tomar valores enteros.
I 1, 2,3,..., n
Programación Entera Mixta: se da cuando solo algunas de las variables
requieren que sea valores enteros.
I 1, 2,3,..., n
Programación Entera Binaria: este es un caso específico ya que solo se dan dos
resultados, 1 si la variable se escoge y 0 si la variable no es tomada en cuenta.
Esto se ve más seguido en problemas de asignación, transportes, etc. Así:
1 si la decisión i es sí
xi (i 1, 2,3,...)
0 si la decisión i es no
En este tipo de programación hace que aparezcan diferentes tipos de restricciones que
permitan cumplir la condición de que la variable sea entera, algunas de estas
restricciones son:
Restricciones de tipo una u otra. En este tipo de restricciones, nos dan a elegir
que restricciones se cumplen bajo determinadas condiciones. En este caso solo
debemos de elegir UNA de las restricciones dadas en la condición (aunque
exista el caso que puedan cumplirse algunas restricciones, no necesariamente
una). Para la solución de estos casos se usa el método de la gran M.
Restricciones del tipo “se deben cumplir K restricciones”. Aquí el problema ya
es más complejo, debido a que nos condicionan previamente que deben si o si
cumplirse K restricciones de un total de N. Para estos casos debemos aplicar la
misma lógica del caso anterior, salvo que debemos agregar una última
restricción:
N
y
i 1
i N K
yi es binaria, para i 1, 2,3,..., N
Para la Programación Entera existen distintos algoritmos de solución, los más conocidos
son los siguientes:
Enumeración Exhaustiva. Este tipo de solución no es recomendable ya que hace
que las soluciones crezcan de forma exponencial.
Relajación Lineal. Consiste en resolver el problema como si fuese un problema
de Programación Lineal cualquiera. Si el óptimo satisface las condiciones de las
variables enteras, entonces se dice que esa es la solución al problema dado
Ramificación y acotamiento. Divide el problema en problemas menores y se
descartan algunos de ellos. Se toma este método si la relajación lineal no
satisface las condiciones de las variables enteras. El algoritmo consta de 4 pasos
1. Crear dos subproblemas ramificando una variable.
2. Para cada subproblema determinar una cota (ya sea superior o inferior)
para la función objetivo.
3. Se deja de desarrollar una rama si:
a. La solución es entera
b. La función objetivo es peor que la cota
c. La solución no es factible
4. Si se ha recorrido todas las ramas, escoger como óptima aquella que
tenga mejor función objetivo.
Método de los planos de corte. Son planos de corte a todas las restricciones
validas deducidas de las restricciones lineales: En este caso las soluciones
enteras van a verificar dichos planos de corte, hasta llegar a un óptimo.
APLICACIONES DE LA PROGRAMACION ENTERA
Las aplicaciones de la programación entera son muy diversas. Por ejemplo, la
Programación Entera Binaria es muy usada en casos de toma de decisiones de proyectos
(para comprobar cuan viable y optimo es el proyecto), contratación de personas o
servicios, análisis de inversión o diseño de redes de producción y distribución. En todas
ellas entra la toma de decisiones en la que es útil la PEB.
Un ejemplo aplicativo es el de la empresa de aerotransporte AIR New Zealand, la cual
usa la PEB para resolver problemas de planeación de viajes ocupados y problemas de
lista de turnos. Dicha empresa ahorra 6.7 millones de dólares al año por usar este
método de optimización, lo cual genera una increíble ganancia de 11% más de lo
normal.
Otra aplicación ilustrativa es de la empresa Taco Bell Corporation que cuenta con más
de 6500 establecimientos de comida rápida en Estados Unidos. Para ello usa la
Programación Entera Mixta (PEM) para resolver problemas de asignación de personal y
recursos en cada uno de sus establecimientos, esto le ha llevado ahorros en más de 13
millones de dólares al año en costos laborales.
