PROGRAMACIÓN ENTERA
Un problema de Programación entera (PE) es un programa de PL en el cual algunas de las
variables, o todas, tienen que ser números enteros no negativos.
Puede tratarse de un problema de programación entera pura o de programación entera mixta.
El PL que se obtiene al omitir todas las restricciones enteras para las variables se llama
relajación PL del PE.
La región factible para cualquier PE tiene que estar incluida en la región factible del PL
correspondiente (es decir, sin considerar valores enteros).
z óptima relajación PL z óptima PE
Restricciones “o bien”
Se dan dos restricciones de la forma
(1) f(x1, x2, . . . , xn) 0
(2) g(x1, x2, . . . , xn) 0
Se quiere satisfacer por lo menos una de ellas. Para conseguirlo se hace lo siguiente:
(1) f(x1, x2, . . . , xn) My
(2) g(x1, x2, . . . , xn) M (1 – y)
Donde y es una variable 0 ó 1 y M es un número que se escoge suficientemente grande para
asegurar que se satisfacen f(x1, x2, . . . , xn) M y g(x1, x2, . . . , xn) M para todos los valores
de x1, x2, . . . , xn que a su vez satisfacen las otras restricciones del problema.
Restricciones “si entonces”
En muchas aplicaciones se presenta la situación siguiente: se desea estar seguro de que se
debe satisfacer la restricción g(x1, x2, . . . , xn) 0, si se satisface una restricción f(x1, x2, . . . ,
xn) > 0, mientras que si no se satisface f(x1, x2, . . . , xn) > 0, entonces g(x1, x2, . . . , xn) 0
puede o no puede satisfacerse. En resumen, se quiere estar seguro de que
(1) f(x1, x2, . . . , xn) > 0 implica
(2) g(x1, x2, . . . , xn) 0.
Para asegurar esto, se incluyen las siguientes restricciones en la formulación:
(1) f(x1, x2, . . . , xn) My
(2) – g(x1, x2, . . . , xn) M (1 – y)
y=01
Como siempre, M es un número suficientemente grande.
Programación Entera y funciones lineales por partes
Una función lineal por partes es una función que consta de varios segmentos rectilíneos.
Se puede aprovechar la programación entera para modelar funciones lineales por partes.
Mediante el uso de variables 0 – 1, se puede representar funciones lineales por partes en una
forma lineal.
Supóngase que una función lineal por partes f(x) tiene los puntos de ruptura b1, b2, . . . ,bn.
Para algún k (k = 1, 2, . . . ,n – 1), bk x bk+1. Entonces, para algún número zk (0 zk 1), se
puede escribir x como
x = zkbk + (1 – zk)bk+1
Ya que f(x) es lineal para bk x bk+1, podemos escribir
f(x) = zkf(bk) + (1 – zk) f(bk+1)
Si una función por partes f(x) aparece en el modelo matemático, debemos realizar los
siguientes pasos:
Paso 1
Reemplazar f(x) = z1f(b1) + z2f(b2) + . . . + znf(bn).
Paso 2
Añadir las restricciones siguientes:
x = z1b1 + z2b2 + . . . + znbn
z1 y1,
z2 y1 + y2,
z3 y2 + y3, . . . . ,
zn-1 yn-2 + yn-1,
zn yn-1
y1 + y2 + . . . + yn-1 = 1
z1 + z2 + . . . + zn = 1
yi = 0 1 (i = 1, 2, . . . , n – 1)
zi 0 (i = 1, 2, . . . , n)
Ejercicios de PE
Ejemplo 1
Stockco considera cuatro inversiones. La inversión 1 proporcionará un valor actual neto
(VAN) de 16 000 dólares; la inversión 2 un VAN de 22 000 dólares; la inversión 3 un VAN
de 12 000 dólares; y la inversión 4 un VAN de 8 000 dólares.
Cada inversión requiere cierto flujo de caja en el momento actual: la inversión 1, 5 000
dólares; la inversión 2, 7 000 dólares; la inversión 3, 4 000 dólares; y la inversión
4, 3 000 dólares respectivamente. Se dispone de 14 000 dólares para la inversión.
Formule un PE cuya solución dirá a Stockco cómo maximizar el VAN obtenido de las
inversiones 1–4.
Ejemplo 2
Modifique la formulación de Stockco para considerar cada una de las siguientes restricciones:
1. Stockco puede invertir en a lo más dos inversiones.
2. Si Stockco invierte en la inversión 2, también tendrá que invertir en la inversión 1.
3. Si Stockco invierte en la inversión 2, no podrá invertir en la inversión 4.
Ejemplo 3
Gandhi Cloth Company puede fabricar tres tipos de ropa: camisas, camisetas y pantalones.
Para poder fabricar cada tipo de ropa, Gandhi tiene que disponer de la maquinaria adecuada.
Hay que rentar la maquinaria requerida para fabricar cada tipo de ropa, a la siguiente tarifa:
maquinaria para camisas, 200 dólares por semana: maquinaria para camisetas, 150 dólares por
semana; maquinaria para pantalones, 100 dólares por semana. La fabricación de cada tipo de
ropa también requiere las cantidades de tela y de trabajo que se dan en la Tabla 1. Cada
semana se disponen de 150 horas de trabajo y de 160 yardas cuadradas de tela. En la Tabla 2
se dan los costos unitarios variables y los precios de venta para cada tipo de ropa.
Formule un PE cuya solución maximizará las ganancias semanales de Gandhi.
Tabla 1
Requerimientos de recursos
para el Ejemplo de Gandhi
TRABAJO TELA
(Horas) (Yardas cuadradas)
Camisas 3 4
Camisetas 2 3
Pantalón 6 4
Tabla 2
Información acerca del ingreso
y del costo para el Ejemplo de Gandhi
PRECIO DE COSTO
VENTA VARIABLE
(dólares) (dólares)
Camisas 12 6
Camisetas 8 4
Pantalón 15 8
Ejemplo 4
Hay seis ciudades (ciudades 1–6) en el Condado de Kilroy. El condado debe determinar en
qué lugar construir estaciones de bomberos. El condado quiere construir una mínima cantidad
de estaciones de bomberos para asegurar que por lo menos una estación esté dentro de 15
minutos (tiempo de viaje) de cada ciudad. En la Tabla 3 se muestran los tiempos requeridos
(en minutos) para viajar entre las ciudades del Condado de Kilroy. Formule un PE que dirá a
Kilroy cuántas estaciones de bomberos habría que construirse y en dónde.
Tabla3
Tiempo requerido para
viajar entre ciudades en
el condado de Kilroy
HACIA
DE Ciudad 1 Ciudad 2 Ciudad 3 Ciudad 4 Ciudad 5 Ciudad 6
Ciudad 1 0 10 20 30 30 20
Ciudad 2 10 0 25 35 20 10
Ciudad 3 20 25 0 15 30 20
Ciudad 4 30 35 15 0 15 25
Ciudad 5 30 20 30 15 0 14
Ciudad 6 20 10 20 25 14 0
Ejemplo 5
Dorian Auto considera la fabricación de tres tipos de automóviles: compacto, mediano y
largo. En la Tabla 4 se presentan los recursos requeridos por y las ganancias proporcionadas
por, cada tipo de automóvil.
En la actualidad se cuenta con 6000 toneladas de acero y 60 000 horas de trabajo. Para que la
producción de un tipo de automóvil sea económicamente factible, hay que fabricar por lo
menos 1 000 automóviles de este tipo. Formule un PE para maximizar la ganancia de Dorian.
Tabla 4
Recursos y ganancias para
tres tipos de automóviles
COMPACTO MEDIANO GRANDE
Acero requerido 1.5 toneladas 3 toneladas 5 toneladas
Trabajo requerido 30 horas 25 horas 40 horas
Ganancia Proporcionada 2 000 dólares 3 000 dólares 4 000 dólares
Ejemplo 6
Euing Gas produce dos tipos de gasolina (gasolina 1 y gasolina 2) a partir de dos tipos de
petróleo (petróleo 1 y petróleo 2). Cada galón de gasolina 1 debe contener por lo menos 50
porciento de petróleo 1, y cada galón de gasolina 2 debe contener por lo menos 60 porciento
de petróleo 1. Se puede vender cada galón de gasolina 1 a 12 centavos, y cada galón de
gasolina 2 a 14 centavos.
Actualmente, se dispone de 500 galones de petróleo 1 y de 1 000 galones de petróleo 2. Se
puede comprar hasta 1 500 galones extra de petróleo 1 a los siguientes precios: los primeros
500 galones, a 25 centavos/galón; los siguientes 500 galones, a 20 centavos/galón; y los
siguientes 500 galones, a 15 centavos/galón.
Formule un PE que maximizará las ganancias (ingresos – costos de compra) de Euing.