¿Qué

es la 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.
¡  En este sentido los algoritmos de resolución
de los modelos de Programación Entera
difieren a los utilizados en los modelos de
Programación Lineal, destacándose entre
ellos el Algoritmo de Ramificación y
Acotamiento (o Branch & Bound), Branch &
Cut, Planos Cortantes, Relajación
Lagrangeana, entre otros.
¡  Los modelos de Programación Entera se pueden clasificar en
2 grandes áreas:
§  Programación Entera Mixta (PEM) y ;
§  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. Un ejemplo de
ello son las siguientes aplicaciones:
§  Problema de Asignación
§  Problema de Corte de Rollos
§  Selección de Invitados a una Boda
§  Programación de la Explotación Forestal
§  Problema de la Mochila

¡  Notar que en los problemas anteriores (PEP) el conjunto de las
soluciones factibles (o dominio de soluciones factibles) es finito.
Esto ocurrirá generalmente con los problemas de Programación
Entera (puros).
¡  Adicionalmente resulta interesante hacer un contrastes
entre las propiedades de un modelo de Programación Lineal
(PL) y uno de Programación Entera (PE). A continuación se
presentan 2 modelos de optimización que se diferencian
únicamente en que al segundo de ellos (PE) se le exige que
las variables de decisión adopten valores enteros.
Solución Gráfica El dominio de soluciones
factibles del Problema Lineal
(PL) corresponde al área
achurada de color verde. Por
otro lado el dominio de
soluciones factibles del
Problema Entero (PE) es
enumerable y corresponde a las
coordenadas denotadas por A,
E, F, B, G, H, I, J, K, C, L, M, D
(que es un subconjunto del
dominio de factibilidad del PL).
En este caso en particular la
solución óptima de ambos
problemas coincide (en el vértice
C), no obstante, perfectamente
podrían ser distintas (bastaría
con modificar los parámetros del
problema).
¡  La California Manufacturing Company analiza la
posibilidad de llevar a cabo una expansión mediante la
construcción de una nueva fábrica ya sea en Los
Ángeles o en San Francisco, o tal vez en ambas
ciudades. También piensa en construir, a lo sumo, un
nuevo almacén, pero la decisión sobre el lugar en
donde lo instalará está restringida a la ciudad donde
se construya la nueva fábrica. El capital total
disponible para las inversiones es de 10 millones de
dólares. El Objetivo es encontrar la combinación
factible de alternativas que maximice el valor
presente neto total.
 Nº de Pregunta Sí o No Variable de Valor Presente Capital
decisión decisión Neto Requerido
1 ¿Construir la fábrica en Los X1 $9 millones $6 millones
Ángeles?
2 ¿Construir la fábrica en San X2 $5 millones $3 millones
Francisco?
3 ¿Construir el almacén en X3 $6 millones $5 millones
Los Ángeles?
4 ¿Construir el almacén en X4 $4 millones $2 millones
San Francisco?

Capital disponible: $10 millones

¡  Análisis de Inversión
§  ¿Deber realizarse cierta inversión fija?

¡  Elección de Localización
§  ¿Debe elegirse cierto lugar para la ubicación de cierta
instalación nueva?

¡  Diseño de una red de Producción y Distribución

§  ¿Debe cierta planta permanecer abierta?
§  ¿Debe seleccionarse cierto sitio para una nueva planta?
§  ¿Debe cierto centro de distribución permanecer abierto?
§  ¿Debe cierto sitio elegirse para instalar un nuevo centro de
distribución?
¡  Despacho de Envíos
§  ¿Deber cierta ruta seleccionarse para uno de los camiones?

¡  Aplicaciones a Líneas Aéreas

§  ¿Debe asignarse cierto tipo de avión a un trayecto en
particular?
§  ¿Debe cierta secuencia de rutas asignarse a una
tripulación?
¡  El Problema de la Mochila (conocido también como Knapsack
Problem o simplemente KP) es un problema clásico de la
Investigación de Operaciones y en particular de la Programación
Entera.
¡  Consiste en un excursionista que debe preparar su mochila, la cual
tiene una capacidad limitada y por tanto no le permite llevar todos
los artículos que quisiera tener en la excursión.
¡  Cada artículo que el excursionista puede incluir en la mochila le
reporta una determinada utilidad.
¡  Luego el problema consiste en seleccionar un subconjunto de
objetos de forma tal que se maximice la utilidad que el
excursionista obtiene, pero sin sobrepasar la capacidad de
acarrear objetos.
¡  En este contexto existen varias aplicaciones que guardan una
similitud conceptual con el Problema de la Mochila y en
consecuencia nos podemos beneficiar de la formulación y
resolución de un modelo de optimización matemática para dicho
propósito. Consideremos el siguiente ejemplo:
¡  Un armador tiene un carguero con capacidad de hasta
700 toneladas. El carguero transporta contenedores
de diferentes pesos para una determinada ruta. En la
ruta actual el carguero puede transportar algunos de
los siguientes contenedores:

¡  El analista de la empresa del armador desea

determinar el envío (conjunto de contenedores) que
maximiza la carga transportada. Para ello se propone
el siguiente modelo de Programación Entera:
 §  Variables de Decisión:

§  Función Objetivo: Consiste en maximizar la carga que

transportará el carguero.



§  Restricciones: El peso de la carga transportada no puede
exceder la capacidad máxima del carguero.

¡  La solución óptima consiste en transportar los
contenedores C1, C2, C3, C4, C8, C9 y C10, con
un valor óptimo de 700 (toneladas), es decir, se
utiliza la capacidad completa del carguero.
¡  Consideremos una empresa que dispone de 5 ingenieros
que deben desarrollar 7 proyectos.
¡  La tabla a continuación resume el tiempo que demora
cada ingeniero (en horas) en completar un determinado
proyecto.
¡  El problema consiste en determinar una asignación
óptima que permita realizar cada uno de los proyectos con
la limitante que por motivos estratégicos cada ingeniero
debe desarrollar al menos un proyecto y en ningún caso
hacer más de 2 proyectos.
¡  Por supuesto se busca que el tiempo requerido para
realizar los 7 proyectos sea el menor posible.
¡  Variables de Decisión: Utilizamos las siguientes variables de decisión
binarias
 ¡  Función Objetivo: Minimizar el tiempo total
requerido para completar los proyectos.

Donde Tij (parámetros) es el tiempo (en horas) requerido por el ingeniero i en
realizar el proyecto j. Por ejemplo T(A,P5)=7.
¡  Restricciones:
-  Cada proyecto debe ser realizado por un solo ingeniero:

-  Cada ingeniero debe ser al menos un proyecto y no puede

hacer más de 2:
¡  En total se requieren 56 horas para realizar los 7 proyectos.
§  El ingeniero A realiza el P7.
§  El ingeniero B el P3 y P5.
§  El ingeniero C el P6.
§  El ingeniero D el P2 y P4.
§  El ingeniero E el P1.
§  Notar que cada proyecto es realizado por un ingeniero y cada
ingeniero al menos realiza un proyecto, pero no más de 2 proyectos.
¡  A esta categoría pertenecen aquellos problemas de optimización
que consideran variables de decisión enteras o binarias pero no de
forma exclusiva.
¡  De esta forma un problema de PEM puede considerarse como un
híbrido entre distintas categorías de modelamiento, siendo un
caso típico aquel que considera la mezcla de variables enteras y
variables continuas (estas últimas características de los modelos
de Programación Lineal).
¡  Por ejemplo:
§  Incorporación de Costos Fijos
§  Problemas de Localización y Transporte
§  Problema de Generación Eléctrica
¡  La estructura de cobro utilizadas en general por las
compañías de servicios donde el cliente debe pagar un
valor fijo sólo por su utilización (independiente del nivel de
consumo y/o eventualmente acotado a un máximo
permitido) y un valor variable proporcional al consumo,
son una práctica común en el esquema de fijación de
precios.
¡  Esto suele ser el caso de las compañías de luz, agua, gas,
teléfono, entre otras, donde el sólo hecho de tener una red
operativa genera costos para la empresa los cuales son
traspasados en parte o en su totalidad a los usuarios en un
cargo fijo o de mantención más un cargo variable por
consumo.
 Ejemplo Inclusión de Costos Fijos en Programación Entera

¡  Tres empresas telefónicas pidieron que me suscribiera a su servicio
de larga distancia dentro del país.
§  MaBell cobra US$16 fijos por mes, más US$0,25 por minuto
§  PaBell cobra US$25 por mes, pero el costo por minuto se reduce a
US$0,21.
§  PhoneBell, la tarifa fija es de US$18 y el costo por minuto de US$0,22.

¡  Suelo hacer un promedio de 200 minutos de llamadas de larga

distancia al mes.
¡  Suponiendo que no pague el cargo fijo si no hago llamadas y que
puedo repartir a voluntad mis llamadas entre las tres
empresas, ¿Cómo debo repartir las llamadas entre las tres
empresas para minimizar la cuenta telefónica mensual?.
 ¡  Variables de Decisión:

¡  Función Objetivo:

Donde representa el costo fijo mensual asociado a la compañía i y el
costo variable por minuto de larga distancia nacional correspondiente
a la compañía i. Para mayor claridad se ha marcado con color amarillo
y verde los elementos de costos fijos y variables (respectivamente) en
la función objetivo.
¡  Restricciones:

Donde:
(1) garantiza que se satisfaga el consumo mensual de
llamadas,
(2) que se realizan llamadas sólo a través de la(s)
compañía(s) donde se asume el cargo fijo mensual y
(3) impone las condiciones de no negatividad para las
variables continuas .
•  Solver









La solución óptima consiste en que se utiliza exclusivamente la
compañía 3 (PhoneBell) y se cursan los 200 minutos mensuales
de llamadas de larga distancia a través de dicha compañía.
El valor óptimo es de US$62 que representa el costo mínimo de
la cuenta telefónica mensual (US$18+200*US$0,22).