SEMANA 3

PROGRAMACIÓN ENTERA

En muchos problemas prácticos, las variables de decision solo tienen sentido real si su valor es entero. Por ejemplo, con frecuencia es necesario asignar a las actividades cantidades enteras de personas, máquinas o vehículos. Si el hecho de exigir valores enteros es la única diferencia que tiene un problema con la formulación de programación lineal, entonces se trata de un problema de programación entera (PE). (El nombre completo es programación lineal entera, pero, por lo general, el adjetivo lineal se omite, excepto cuando se hace una comparación con el problema más esotérico de programación no lineal entera que está fuera del alcance de este libro).
El modelo matemático para programación entera es sencillamente el modelo de programación lineal (vea la sección 3.2) con la restricción adicional de que las variables deben tener valores enteros. Si sólo es necesario que algunas de las variables tengan valores enteros —y el supuesto de divisibilidad se cumple para el resto—, el modelo se conoce como de programación entera mixta (PEM). Cuando se hace la distinción entre un problema con todas las variables enteras y este caso mixto, el primero se llama de programación entera pura.
Por ejemplo, el problema de la Wyndor Glass Co. presentado en la sección 3.1 habría sido en realidad un problema de PE, si las dos variables de decisión x_1 y x_2 hubiera representado el número total de unidades que se debía producir de los respectivos artículos 1 y 2, en lugar de las tasas de producción. Como ambos productos —puertas de vidrio y marco de madera— deben ser unidades completas, x_1 y x_2 deben restringirse a valores enteros.
Otro ejemplo de un problema de PE es un estudio galardonado de IO encargado por el San Francisco Pólice Department que se presentó (y citó) en la sección 2.1. Como se indicó, el resultado fue el desarrollo de un sistema computarizado para la programación y despliegue óptimos del cuerpo de patrulleros. El nuevo sistema permitió ahorros anuales de $11 millones, un incremento de $3 millones en los ingresos por multas y una mejora de 20% en los tiempos de respuesta. Las principales variables de decisión del modelo matemático fueron el número de oficiales programados para estar en servicio en cada inicio de turno. Como este número tenía que ser un entero, estas variables de decisión se restringieron a valores enteros.
Se han desarrollado numerosas aplicaciones de programación entera que involucra una extensión directa de programación lineal en la que debe eliminarse el supuesto de divisibilidad. Sin embargo, existe otra área de aplicación que puede ser mucho más importante, como el problema que incluye cierto número de "decisiones sí o no" interrelacionadas. En situaciones de este tipo, las únicas dos elecciones posibles son sí y no. Por ejemplo, ¿debe emprenderse un proyecto fijo específico? ¿Debe hacerse cierta inversión fija? ¿Debe localizar¬se una instalación en un sitio en particular?
Debido a que estos problemas involucran sólo dos posibilidades, este tipo de decisiones se puede representar mediante variables de decisión restringidas a sólo dos valores, por ejem¬plo, 0 y 1. De esta forma, la j-ésima decisión sí o no se puede representar por X_j, tal que
X_j= {█(1 si la decision j es si@0 si la decision j es no)┤
Las variables de este tipo se llaman binarias (o variables 0-1). En consecuencia, algunas ve¬ces se hace referencia a los problemas de programación entera que contienen sólo variables binarias como problemas de programación entera binaria (PEB) (o problemas 0-1 de pro¬gramación entera).
EJEMPLO PROTOTIPO
La CALIFORNIA MANUFACTURING COMPANY analiza la posibilidad de una expan¬sión mediante la construcción de una nueva fábrica ya sea en Los Ángeles o en San Fran¬cisco, o tal vez en ambas ciudades. También piensa en construir, a lo sumo, un nuevo alma¬cén, pero la decisión sobre el lugar en donde lo instalará está restringida a la ciudad donde se construya la nueva fábrica. En la cuarta columna de la tabla 11.1 se muestra el valor pre¬sente neto —rendimiento total que toma en cuenta el valor del dinero en el tiempo— de ca¬da alternativa. En la última columna se proporciona el capital requerido —incluido en el va¬lor presente neto— para las respectivas inversiones, donde el capital total disponible es de 10 millones de dólares. El objetivo es encontrar la combinación factible de alternativas que maximice el valor presente neto total.
El modelo PEB
Aun cuando este problema es tan pequeño que se puede resolver con rapidez por inspección —construir fábricas en ambas ciudades, pero ningún almacén—, se formulará el modelo de programación entera con propósitos ilustrativos. Todas las variables de decisión tienen la forma binaria
X_j= {█(1 si la decision j es si,@0 si la decision j es no,)┤
(j =1,2,3,4)
TABLA 11.1 Datos del ejemplo de la California Manufacturing Co.
Número de decisión Pregunta sí o no Variable de decisión Valor presente neto Capital requerido
1 2 3 4 ¿Construir la fábrica en Los Ángeles? ¿Construir la fábrica en San Francisco? ¿Construir el almacén en Los Ángeles? ¿Construir el almacén en San Francisco? *1
X4 $9 millones $5 millones $6 millones $4 millones $6 millones $3 millones $5 millones $2 millones
Capital disponible: $10 millones
Sea
Z= Valor presente neto de estas decisiones.
Si se hace la inversión para construir una instalación dada —de manera decisión correspondiente tenga valor de 1—, el valor presente neto estimado de estas inversiones aparece en la cuarta columna de la tabla 11.1. Si la inversión no tanto, la variable de decisión es igual a O—, el valor presente neto es 0. Entonces con unidades de millones de dólares,
Z=9X_1+ 5X_2+6X_3+ 4 X_4
La última columna de la tabla 11.1 indica que la cantidad que se gastara en las cuatro instalaciones no puede exceder a 10 millones de dólares. En consecuencia, si se sigue con el uso de estas unidades de millones de dólares, una restricción del modelo es
6X_1+ 3X_2+ 5X_3+ 2X_4<10
Como las últimas dos decisiones representan alternativas mutuamente excluyentes –la compañía quiere construir cuando mucho un almacén nuevo—, se necesita la restricción
X_3+ X_4≤1
Aún más, las decisiones 3 y 4 son contingentes —o condicionales— porque dependen de las decisiones 1 y 2, respectivamente —la compañía consideraría la construcción de un almacén en determinada ciudad sólo si la nueva fábrica va a estar ahí—. Por lo tanto, en caso de tomar la decisión 3, se requiere que X_3=0 si X_j=0. Esta restricción sobre X_3(cuando X_1=0) se impone al agregar la restricción
X_3≤ X_1
De manera similar, el requerimiento de que X_4=0 si X_2=0 se impone con la restricción
X_4≤X_2
Por lo tanto, después de escribir de nuevo estas dos restricciones para que todas las variables queden en el lado izquierdo, el modelo completo de PEB es
Maximizar Z=9X_1+5X_2+ 6X_3+ 4X_4
sujeta a
6X_1+3X_2+5X_3+2X_4≤10
X_3+X_4 ≤1
〖-X〗_1 +X_(3 ) ≤0
〖-X〗_2 +X_4 ≤0
X_j≤1
X_(j )≥0
Y
X_j es entera,para j=1,2,3,4.
De manera equivalente, las tres últimas líneas de este modelo se pueden sustituir por una sola restricción
X_j es binaria, para j=1,2,3,4.
Excepto por su tamaño pequeño, este ejemplo representa muchas aplicaciones reales de programación entera en las que las decisiones básicas que se toman son del tipo sí o no. Al igual que el segundo par de decisiones de este ejemplo, muchos grupos de decisiones sí o no constituyen grupos de alternativas mutuamente excluyentes, tales que sólo una deci¬sión de ese grupo puede ser sí. Cada grupo requiere una restricción que obligue a la suma de las variables binarias correspondientes a ser igual a 1 si exactamente una decisión de ese grupo debe ser sí— o menor o igual a 1 —si cuando mucho una decisión de ese grupo pue¬de ser sí—. En ocasiones, las decisiones del tipo sí o no son decisiones contingentes, es de¬cir, dependen de decisiones anteriores. Por ejemplo, se dice que una decisión es contingen¬te respecto a otra si se permite que sea si sólo si la otra es sí. Esta situación ocurre cuando una decisión contingente implica una acción que sigue a otra y que se vuelve irrelevante, o imposible, si la otra decisión es no. La forma de la restricción obtenida se ilustra en la cuar¬ta y quinta restricciones del ejemplo.