Unidad 4: Programación

entera
Contenidos
4.1. Introducción. Variables binarias y 4.5. Problemas de asignación
restricciones relacionadas
4.6. Problemas de localización
4.2. Problema de la mochila
4.7. Modelos de secuenciación
4.3. Problemas de corte de patrones 4.8. Transporte y logística
4.4. Costes fijos
4.9. Modelos de horarios

2
Glosario (algunos conceptos importantes)
• Variable entera • Problemas de localización
• Variable binaria • Problemas de cobertura
• Problema de la mochila • Problema de la mediana
• Problemas de corte de • Problema Weber
patrones • Problema del centro
• Costes fijos • Secuenciación
• M grandes • TSP, localización, ruteo
• Problemas de asignación
4.1 Variables binarias y restricciones
relativas
En algunas aplicaciones las variables no solo necesitan ser no negativas
sino que también deberían ser enteras. Ejemplos de enteros son
{…,-3,-2,-1,0,1,2,3,…}
En esta unidad veremos ejemplos más complejos de programación
entera (una o más variables solo pueden tomar valores enteros)
Un caso especial de variables enteras es el de las variables binarias
Las variables binarias solo pueden tomar el valor 0 o el valor 1
Modelizando relaciones con dos
variables: dos actividades
𝑌𝑌1 = 1 si la actividad 1 es elegida, cero en caso contrario.
𝑌𝑌2 = 1 si la actividad 2 es elegida, cero en caso contrario.
Esto puede extenderse a más de dos variables (más
variables binarias serían necesarias)
Modelizando relaciones con dos
variables: dos actividades
Formulación Significado
𝑌𝑌1 + 𝑌𝑌2 ≤ 1 “Como mucho una de las dos actividades puede ser elegida”
𝑌𝑌1 + 𝑌𝑌2 ≥ 1 “Al menos una de las dos actividades debe ser elegida”
𝑌𝑌1 ≤ 𝑌𝑌2 “Si la actividad 1 es elegida, entonces la actividad 2 debe ser también
elegida” o “La actividad 1 puede ser elegida sólo si la actividad 2 es
elegida”
𝑌𝑌1 ≥ 𝑌𝑌2 “Si la actividad 2 es elegida, entonces la actividad 1 debe ser también
elegida” o “La actividad 2 puede ser elegida sólo si la actividad 1 es
elegida”
4.2 Problema de la mochila
Knapsack problem
Es uno de los problemas más estudiados en IO
Tiene una gran cantidad de variantes
Estudiaremos el caso más simple: el problema de la mochila 0-1
𝑛𝑛 artículos diferentes deben ser introducidos en una mochila. Cada artículo 𝑖𝑖 tiene un
peso 𝑤𝑤𝑖𝑖 y un valor 𝑣𝑣𝑖𝑖 . La mochila tiene una capacidad de 𝑊𝑊. El problema consiste en
introducir artículos en la mochila, sin exceder su capacidad de tal manera que el valor
de los artículos introducidos sea máximo
Necesitamos decidir, para cada artículo, si lo introducimos o no (decisión de todo o
nada)  Variable Binaria
4.2 Problema de la mochila
 4.2 Problema de la mochila
Incluso aunque parece simple … es uno de los problemas catalogados como
“difíciles” de resolver (denominado NP-hard, pero eso es otra historia…)
Variantes del problema de la mochila sería considerar: varios artículos del
mismo tipo, varios pesos, función multiobjetivo, …
¿Considerarías un problema como este si estuvieras de mochilero por todo el
mundo?
No solo para mochileros: el problema de la mochila tiene muchas
aplicaciones
Ejemplo: Presupuestación de
inversiones de capital
Un inversor puede invertir hasta en cinco proyectos diferentes. Cada
uno de estos proyectos tiene un beneficio esperado y un
presupuesto, ambos en millones de euros (ver tabla adjunta). El
presupuesto máximo no puede exceder de 14 millones de euros. Se
quiere encontrar la combinación de proyectos que maximiza el
beneficio, respetando el presupuesto máximo estipulado
Teatro Supermercado Zoo Fábrica Estación tren
Beneficio 5 3 6 1 3,5
Presupuesto 8 4 10 2 6
Ejemplo: Presupuestación de
inversiones de capital

Solución: 𝑌𝑌2∗ = 𝑌𝑌3∗ = 1, todas las demás cero. 𝑍𝑍 ∗ = 9

Lo más beneficioso es invertir en el supermercado y en el zoo. El

beneficio esperado será de 9 millones de euros
Modifica el modelo anterior para incluir las siguientes condiciones:
a) No se puede invertir en el zoo y en el supermercado a la vez, es decir, solo se puede invertir en
uno de ellos como mucho.
b) Se debe invertir en al menos 2 proyectos.
c) Como mucho se puede invertir en 3 proyectos.
d) Si el proyecto fábrica es elegido, entonces el proyecto estación de tren debe ser también elegido,
es decir, el proyecto fábrica puede ser elegido sólo si el proyecto estación de tren es elegido.
12
4.3 Problemas de corte de patrones
Cutting Stock problems, Trim loss
Rollos de papel de un ancho prefijado, que se pueden cortar a la
longitud deseada
En este modelo, las variables necesitan tomar valores enteros
Típicamente, hay dos objetivos en este tipo de problemas:
◦ Minimizar el desperdicio producido durante el proceso (más difícil)
◦ Minimizar los costes en los que se incurre en el proceso (más sencillo)
Ejemplo
Una tienda trabaja con tableros de madera. Tienen dos posibles longitudes:

1. Longitud1, 12m (de los que tiene 20 unidades)

2. Longitud2, 10m (de los que tiene 25 unidades)

Hay tres diferentes tipos de barras:

1. Tipo 1: 60 barras de 8m

2. Tipo 2: 40 barras de 5m

3. Tipo 3: 75 barras de 3m

La tienda puede obtener las barras necesarias cortando los tableros existentes (a un coste de 50 céntimos por corte) o
comprando barras nuevas (a un coste de 2 €, 1,5 € y 1,1 €, para las barras de 8, 5 y 3 metros, respectivamente). Encontrar una
solución para la tienda que minimice el coste total del proceso
Variables
Definir patrones de corte deseables
1. 12m  8 + 3 + 1
2. 12m  5 + 5 + 2
3. 12m  5 + 3 + 3 + 1
4. 12m  3 + 3 + 3 + 3
5. 10m  8 + 2
6. 10m  5 + 5
7. 10m  5 + 3 + 2
8. 10m  3 + 3 + 3 + 1
Para cada patrón 𝑖𝑖 = 1, … , 8, la variable 𝑌𝑌𝑖𝑖 es el número de veces que ese patrón es
cortado
Las variables 𝑉𝑉𝑗𝑗 definen la cantidad de barras de diferentes tipos que se compran 𝑗𝑗 = 1,2,3
Función objetivo
El coste de cortar más el coste de compra o adquisición
◦ Costes de Corte: Patrones 5,6 necesitan un corte 0,5 €. Patrones 1,2,7
necesitan dos cortes  1 €. Patrones 3,4,8 necesitan tres cortes  1,5 €.
◦ Costes de compra: Tipo 1  2 €; Tipo 2  1,5 €. Tipo 3  1,1 €.

16
Restricciones de suministro
La cantidad de patrones cortados de una determinada longitud no
puede exceder de la cantidad de tableros disponibles

17
Restricciones de demanda
La demanda requerida de cada barra debe ser satisfecha
4.3 Problemas de corte de patrones
4.4 Costes fijos
Fixed Costs
Cuando las contribuciones son proporcionales, la programación lineal standard
es suficiente
Sin embargo, a veces los costes no son constantes
Tú sueles pagar menos por unidad cuando el tamaño del lote incrementa
O llegas a un punto a partir del cual no hay necesidad de pagar más
En tales casos, la programación lineal entera te ayuda a modelar el problema
 UN PROBLEMA CON COSTES FIJOS
Una compañía puede fabricar 4 tipos diferentes de productos en una línea de
producción que pasa por tres departamentos diferentes. La producción gasta horas de
trabajo, proporciona beneficios, y llevan asociados costes fijos de acuerdo a la siguiente
tabla:
Horas-hombre por 1000 unidades de
producto Beneficio Bruto
Producto Coste Fijo (miles €)
(€/ud)
Dep 1 Dep 2 Dep 3
P1 160 120 50 80 200
P2 150 200 50 85 200
P3 100 180 50 98 90
P4 200 175 50 100 150
Disponibilidad mensual horas-
4000 4800 1600
hombre
UN PROBLEMA CON COSTES FIJOS
Si se produce un tipo específico de producto, la empresa incurre en un coste general o
fijo por la renovación de la línea de producción
La empresa desea programar la producción para maximizar los beneficios
Los costes fijos no se pueden modelizar con programación lineal
Variables
𝑋𝑋𝑗𝑗 ≥ 0 para 𝑗𝑗 = 1,2,3,4 será la cantidad de producto 𝑗𝑗
𝑌𝑌𝑗𝑗 ∈ {0,1} será 1 cuando 𝑋𝑋𝑗𝑗 > 0 y cero cuando 𝑋𝑋𝑗𝑗 = 0
Función objetivo:
Max 80·X1 + 85·X2 + 98·X3 + 100·X4 –1000(200·Y1 + 200·Y2 + 90·Y3 + 150·Y4)

Restricciones:
◦ Disponibilidad Horas-hombre por departamento:
(160·X1 + 150·X2 + 100·X3 + 200·X4)/1000 ≤ 4000 (dep 1)
(120·X1 + 200·X2 + 180·X3 + 175·X4)/1000 ≤ 4800 (dep 2)
(50·X1 + 50·X2 + 50·X3 + 50·X4)/1000 ≤ 1600 (dep 3)
◦ Garantiza que los costes fijos se tienen en cuenta sólo cuando el producto es producido:
X1 ≤ M1·Y1 X2 ≤ M2·Y2 Las M representan un valor lo suficientemente grande para que las
restricciones se cumplan. ¿Cuál es el valor mínimo que estas variables
X3 ≤ M3·Y3 X4 ≤ M4·Y4
podrían tomar sin afectar al modelo? Echa un vistazo:

[Link]
Otras formulaciones con variables binarias
TARIFAS (PRECIOS/COSTES VARIABLES EN FUNCIÓN DE LA CANTIDAD)
Modelos en los que el precio/coste depende de la cantidad
vendida/comprada
Tramos o tarifas en función de la cantidad
1 ≤ cantidad ≤ 100  Precio/coste = 5
101 ≤ cantidad ≤ 200  Precio/coste= 4
Cantidad ≥ 201  Precio/coste = 3

24
Otras formulaciones con variables binarias
Ejercicio
Una compañía produce dos productos A y B. Cada unidad de producto A requiere 1 hora de servicios de
ingeniería y 5 horas de tiempo de máquina. Producir una unidad de producto B requiere 2 horas de
ingeniería y 8 horas de tiempo de máquina. Hay 100 horas de ingeniería y 400 horas de tiempo de
máquina disponibles. El coste de producción es una función no lineal de la cantidad producida, tal como
aparece en la siguiente tabla:
Producto A Producto B
Producción Unidades Coste Unitario Producción Unidades Coste Unitario
1-50 10 1-40 7
51-100 8 41-100 3
101-200 6 101-200 2
Los precios de venta de los productos A y B son de 12 y 14 u.m. respectivamente. La
compañía desea conocer el plan de producción que maximice su beneficio. Formula un
modelo de programación lineal entera que permita resolver el problema.

25
Otras formulaciones con variables binarias
EJEMPLO
Fabricación de dos productos A y B con beneficio 4 y 3 u.m. respectivamente. La
empresa debe decidir sobre la compra de una nueva máquina, con las siguientes
características.

A (min/unidad) B(min/unidad) Coste Capacidad (h)

M1 3 2 10 18
M2 1 3 12 16
MODELO DE PROGRAMACIÓN LINEAL ENTERA
Variables:
𝑋𝑋𝑖𝑖 : Número de unidades a fabricar del producto i, 𝑖𝑖 = {𝐴𝐴, 𝐵𝐵}
𝑌𝑌𝑖𝑖 : Variables binarias, toman el valor 1 si compramos máquina 𝑖𝑖 y 0 en caso contrario, 𝑖𝑖 = 1, 2

Función Objetivo: Max Z = 4·XA + 3·XB – 10·Y1 - 12·Y2

Restricciones:
[M1] 3·XA + 2·XB ≤ 1080 + (1-Y1)·M
[M2] XA + 3·XB ≤ 960 + (1-Y2)·M
[Solo1Máquina] Y1 + Y2 = 1

27
MODELO DE PROGRAMACIÓN LINEAL ENTERA (EQUIVALENTE)
Variables:
𝑋𝑋𝑖𝑖 : Número de unidades a fabricar del producto i, 𝑖𝑖 = 𝐴𝐴, 𝐵𝐵
𝑌𝑌𝑖𝑖 : Variables binarias, toman el valor 0 si compramos máquina 𝑖𝑖 y 1 en caso contrario, 𝑖𝑖 = 1, 2

Función Objetivo: Max Z = 4·XA + 3·XB – 10·(1-Y1) - 12·(1-Y2 )

Restricciones:
[M1] : 3·XA + 2·XB ≤ 1080 + Y1·M
[M2] XA + 3·XB ≤ 960 + Y2·M
[Solo1Máquina] Y1 + Y2 = 1

28
Otras formulaciones con variables binarias
RESTRICCIONES CON POSIBILIDAD DE DISTINTOS VALORES

Restricciones con el mismo lado izquierdo donde hay que

“elegir” entre distintos valores para los lados derechos
Otras formulaciones con variables binarias
EJEMPLO
Decidir sobre la compra de un vehículo. Dos alternativas con distintas
capacidades y costes (C1 y C2). Dos mercancías a introducir en el vehículo
(A y B) con pesos de 15 y 20 Kg y beneficio de 3 y 4 u.m. respectivamente

Capacidad (Kg) Coste (u.m.)

C1 500 20
C2 700 30
MODELO DE PROGRAMACIÓN LINEAL ENTERA
Variables:
𝑋𝑋𝑖𝑖 : Número de unidades a cargar del producto i, 𝑖𝑖 = {𝐴𝐴, 𝐵𝐵}
𝑌𝑌𝑖𝑖 : Variables binarias, toman el valor 1 si compramos vehículo 𝑖𝑖 y 0 en caso contrario, 𝑖𝑖 = 1, 2

Función Objetivo: Max Z = 3·XA + 4·XB -20·Y1-30·Y2

Restricciones:
[M1] : 15·XA + 20·XB ≤ 500·Y1 + 700·Y2
[Solo1Vehículo] Y1 + Y2 = 1

31
4.5 Problema de asignación
Suponemos que m trabajadores pueden hacer m tareas
Todas las tareas deben realizarse y cada trabajador no puede hacer más de
una tarea
Si el trabajador i hace la tarea j, la compañía obtiene un beneficio de cij u.m.
La compañía quiere encontrar la asignación de trabajadores a tareas que
maximice el beneficio global
cij puede ser considerado como un coste (por ejemplo, tiempo). En tal caso la
función objetivo debería ser minimizada
 1 A

2 B

3 C

4 D

Ejemplo gráfico del problema de asignación

33
Si cij fuese el coste de que el trabajador i hiciese el trabajo j

𝑋𝑋𝑖𝑖𝑖𝑖 = 1 si el trabajador 𝑖𝑖 realiza la tarea 𝑗𝑗;

min � 𝑐𝑐𝑖𝑖𝑖𝑖 𝑋𝑋𝑖𝑖𝑖𝑖 1 A

𝑖𝑖,𝑗𝑗
2 B
𝑠𝑠. 𝑎𝑎. : � 𝑋𝑋𝑖𝑖𝑖𝑖 = 1, 𝑖𝑖 = 1, … , 𝑚𝑚
𝑗𝑗
3 C
� 𝑋𝑋𝑖𝑖𝑖𝑖 = 1, 𝑗𝑗 = 1, … , 𝑚𝑚
𝑖𝑖 4 D
𝑋𝑋𝑖𝑖𝑖𝑖 ∈ 0,1

34
 Ejemplo
La empresa de transportes la Rapidita tiene que asignar 3 rutas a 3 transportistas de tal manera que el tiempo
total sea mínimo. Cada transportista solo puede hacer una ruta y cada ruta solo puede ser realizada una vez.
Si el coste, en unidades de tiempo, de cada ruta para cada transportista se muestra en la siguiente tabla,
plantea un modelo que permita asignar cada ruta a cada transportista con el objetivo de minimizar el tiempo
total de transporte de las tres rutas.

Ruta 1 Ruta 2 Ruta 3

Transportista 1 20 25 35
Transportista 2 22 20 38
Transportista 3 30 28 33
4.6 Problemas de localización
4.6 Problemas de localización
Location Problems
Los problemas de localización fueron abordados primeramente por matemáticos
Encontrar un punto en un triángulo en el cual la suma de las distancias a sus vértices
sea mínima Torricelli y Fermat en el siglo XVII
Weber escribió sobre la localización de actividades económicas alrededor de un lugar
central a principios del siglo XX
Hakimi introdujo los modelos de localización en la IO (1964)
La localización es hoy en día una gran área de investigación
Localización = Espacio + Clientes + Instalaciones
38
Diferentes problemas de localización
Problemas de cubrimiento (ya vistos)
◦ Ubicar instalaciones que proporcionan algunos servicios requeridos por los clientes (un cliente está
cubierto por una instalación si la distancia entre ellos es menor que un umbral predefinido)
Problemas de la Mediana
◦ Objetivos Minimizar la suma (Minisum) : ubicar instalaciones para minimizar la suma de distancias
a los clientes
Problemas del Centro
◦ Objetivos Minimizar el máximo (Minimax): localizar instalaciones tal que se minimice la distancia
más larga entre un cliente y su instalación más cercana
Conjuntos de cobertura (set covering)
El problema básico de cobertura de
conjuntos consiste en encontrar
subconjuntos que cubran una región de
interés dada al menor coste posible
Dada la región de interés R, y n conjuntos
C={a1, a2,…, an}, para que su unión cubra R,
encontrar un subconjunto de C que cubre
R al mínimo coste
De los conjuntos en C, la región
de interés R se divide en m
subregiones diferentes, que 𝑎𝑎2

resultan de las intersecciones

entre los conjuntos en C. 𝑎𝑎1 𝑎𝑎3 𝑎𝑎4

41
FORMULACIÓN
Sea 𝑞𝑞𝑖𝑖𝑗𝑗 = 1 si el conjunto 𝑎𝑎𝑗𝑗 cubre la subregión 𝑅𝑅𝑖𝑖 , cero en caso
contrario
Sea 𝑐𝑐𝑗𝑗 el coste en el que se incurre cuando se usa el conjunto 𝑎𝑎𝑗𝑗

min ∑𝑐𝑐𝑗𝑗 𝑋𝑋𝑗𝑗

𝑠𝑠. 𝑎𝑎. : � 𝑞𝑞𝑖𝑖𝑖𝑖 𝑋𝑋𝑗𝑗 ≥ 1, 𝑖𝑖 = 1, … , 𝑚𝑚
𝑗𝑗
𝑋𝑋𝑗𝑗 ∈ {0,1}

𝑋𝑋𝑗𝑗 = 1 si se usa el conjunto 𝑎𝑎𝑗𝑗 , cero en caso contrario

42
Problema minimizar suma en el
plano
El problema más simple es “el problema de la Mediana”
La tarea es localizar una única instalación en el plano
Tenemos 𝑛𝑛 clientes
Para cada cliente 𝑖𝑖, sus coordenadas (𝑎𝑎𝑖𝑖 , 𝑏𝑏𝑖𝑖 ) y demanda 𝑤𝑤𝑖𝑖 son conocidas
El objetivo es minimizar la suma ponderada de las distancias cliente-instalación (una
aproximación del coste total de transporte)
◦ min ∑𝑖𝑖 𝑤𝑤𝑖𝑖 𝑑𝑑(𝑥𝑥, 𝑖𝑖) , x ∈ 𝑅𝑅2

◦ Donde 𝑑𝑑(𝑥𝑥, 𝑖𝑖) es la distancia entre la nueva instalación 𝑥𝑥 y 𝑖𝑖

También conocidos como problemas de Weber
Fuente:
[Link]

44
Ejemplo de mini suma (Weber)
2
Nodo 1: 0; 0
3
Nodo 2: (0; 3)
Nodo 3: (3; 2,5)
Distancia Euclídea
Solución: Instalación en (0,758903 ; 2,099665)

1
Problema de 1-Centro
El problema más sencillo del problema del Centro
Encontrar un localización para la instalación tal que minimice la distancia
máxima entre la instalación y cualquiera de los clientes
El problema consiste en
◦ min max{𝑤𝑤𝑖𝑖 𝑑𝑑 𝑥𝑥, 𝑖𝑖 } , 𝑥𝑥 ∈ 𝑅𝑅2
𝑖𝑖
◦ Donde 𝑑𝑑(𝑥𝑥, 𝑖𝑖) es la distancia desde la nueva instalación 𝑥𝑥 a 𝑖𝑖
Este problema minmax puede ser modelizado usando programación matemática
tal y como se muestra:
min 𝑧𝑧, 𝑠𝑠. 𝑎𝑎. {𝑧𝑧 ≥ 𝑑𝑑 𝑥𝑥, 𝑖𝑖 ∀ 𝑖𝑖 , 𝑥𝑥 ∈ 𝑅𝑅2 }
 Nodo 1: 0; 0
2 Nodo 2: (0; 3)
Nodo 3: (3; 2.5)
3
Distancia Euclídea
Solución: Instalación en (1,291667 ; 1,499999), 𝑧𝑧 = 1,979

47
Weber versus Centro
Problema del Centro
3,5

2,5

1,5

0,5

0
0 0,5 1 1,5 2 2,5 3 3,5
Weber versus Centro
Problema Weber
3,5

2,5

1,5

0,5

0
0 0,5 1 1,5 2 2,5 3 3,5
Problema de localización de una
industria
 Es una aplicación importante de programación entera mixta en la que uno desea
determinar la localización y el tamaño óptimo de una serie de fábricas que
producen mercancías muy demandadas. Extensión del Problema de Transporte
 La demanda de productos y la localización de los clientes son conocidas de
antemano
 𝑏𝑏1, 𝑏𝑏2, … , 𝑏𝑏𝑛𝑛 : Demandas conocidas de los 𝑛𝑛 clientes
 𝑎𝑎1, 𝑎𝑎2, … , 𝑎𝑎𝑚𝑚 : Capacidad de producción de cada una de las 𝑚𝑚 fábricas que
pueden ser construidas
 𝑓𝑓1, 𝑓𝑓2, … , 𝑓𝑓𝑚𝑚 : coste de producir cada una de las 𝑚𝑚 fábricas

 𝑐𝑐𝑖𝑖𝑖𝑖 : Coste de enviar una unidad desde la 𝑖𝑖 − é𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 fábrica al 𝑗𝑗 − é𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠

cliente
MODELO DE PROGRAMACIÓN LINEAL ENTERA
Variables:
𝑋𝑋𝑖𝑖𝑖𝑖 : Número de unidades transportadas desde la factoría 𝑖𝑖 al cliente 𝑗𝑗, 𝑖𝑖 = 1, 2, … , 𝑚𝑚, 𝑗𝑗 = 1, 2, … , 𝑛𝑛
𝑌𝑌𝑖𝑖 : Variables binarias, toman el valor 1 si la factoría 𝑖𝑖 es construida y 0 en caso contrario, 𝑖𝑖 =
1, 2, … , 𝑚𝑚

Función Objetivo: min ∑𝑖𝑖(𝑓𝑓𝑖𝑖 𝑌𝑌𝑖𝑖 + ∑𝑗𝑗 𝑐𝑐𝑖𝑖𝑖𝑖 𝑋𝑋𝑖𝑖𝑖𝑖 )

Restricciones
◦ Demandas de Clientes : ∑𝑖𝑖 𝑋𝑋𝑖𝑖𝑖𝑖 ≥ 𝑏𝑏𝑗𝑗 , 𝑗𝑗 = 1, … , 𝑛𝑛.
◦ Producción en las factorías o fábricas : ∑𝑗𝑗 𝑋𝑋𝑖𝑖𝑖𝑖 ≤ 𝑎𝑎𝑖𝑖 𝑌𝑌𝑖𝑖 , 𝑖𝑖 = 1, … , 𝑚𝑚.

Pueden establecerse muchas otras restricciones: incompatibilidad entre dos fábricas, costes no lineales,
capacidades de arco limitadas, …

51
Ejemplo
La empresa Surgerisim ha firmado un contrato con el Ministerio de Sanidad para
abastecer a cinco hospitales diferentes de España, localizados en Valencia, Barcelona,
Madrid, Bilbao y Sevilla, con colchones para sus camas, en los próximos 30 años. Con el
objetivo de fabricar estos colchones, la empresa se plantea abrir dos factorías
diferentes. Las localizaciones potenciales para esas dos fábricas son Zaragoza, Granada,
Cuenca, y Castellón
El coste unitario de enviar colchones desde cada fábrica a cada hospital (en euros), la
capacidad de producción anual (en unidades), el coste total de construcción y
mantenimiento relativo a cada factoría en los próximos 30 años ( en miles de euros) y la
demanda esperada anual de los hospitales (en unidades) están especificadas en la
siguiente tabla:
 Val Bar Mad Bil Sev Capacidad Coste
Zar 15 15 15 30 40 1500 300
Gra 25 40 20 50 15 1200 250
Cue 10 20 10 35 30 1100 230
Cas 5 10 20 20 35 1300 270
Demanda 300 500 600 250 325

Asumimos que no hay otros costes involucrados. La compañía intenta decidir

dónde localizar las dos fábricas, y cuántos colchones tienen que ser enviados
desde cada factoría a cada hospital, de tal manera que el coste total en los
próximos años sea minimizado

53
4.7 Modelos de secuenciación
Scheduling Models
Asignación de trabajos (o tareas) a procesadores (o máquinas)
Estos conceptos deberían ser entendidos en el sentido más amplio posible
Los/las médicos tratan pacientes: médicos son procesadores y pacientes son
trabajos
Auditoría : auditores son procesadores y compañías auditadas son trabajos
…
Datos de entrada
𝑛𝑛 tareas (indexadas por 𝑗𝑗)
𝑚𝑚 máquinas (indexadas por 𝑖𝑖)
𝑝𝑝𝑖𝑖𝑖𝑖 es el tiempo de procesamiento de la tarea 𝑗𝑗 en la máquina 𝑖𝑖
Queremos encontrar una asignación de tareas a máquinas de tal manera que un determinado
criterio sea optimizado
Cantidad y naturaleza de las máquinas
• Una máquina, múltiples máquina, máquinas idénticas, máquinas relacionadas, máquinas no relacionadas,…

Objetivos
• Makespan (o duración de la secuencia), tiempo de flujo medio, tardanza máxima, adelantos, tardanzas,…
Secuenciación
Asignación se refiere a la asignación de recursos a tareas.
En esta unidad: asignar trabajos 𝑗𝑗 a máquinas 𝑖𝑖
Si 𝑝𝑝𝑖𝑖𝑖𝑖 , es el tiempo necesario para procesar el trabajo j en máquina i , …
◦ … es para todas las máquinas: 𝑝𝑝𝑖𝑖𝑖𝑖 = 𝑝𝑝𝑗𝑗 ∀ 𝑖𝑖, máquinas idénticas
◦ … depende de la máquina, por medio de un factor de velocidad: 𝑝𝑝𝑖𝑖𝑖𝑖 = 𝑝𝑝𝑗𝑗 /𝑠𝑠𝑖𝑖 , máquinas
uniformes
◦ … depende de la máquina, no uniformemente, máquinas no relacionadas
Posibles objetivos a optimizar:
◦ Minimizar el tiempo de finalización del ultimo trabajo (makespan)
◦ Minimizar adelantos o retrasos de los trabajos que se procesan
◦ Minimizar la necesidad de recursos (adicionales)
UPM
Mostramos el caso más general: Problema de Secuenciación con Máquinas
Paralelas no Relacionadas (The Unrelated Parallel Machines scheduling
problem –UPMS-)
•Asignar trabajos a máquinas tal que el tiempo de completación del ultimo

trabajo sea minimizado (llamado makespan e identificado como 𝐶𝐶max ).

•Una vez un trabajo empieza a ser procesado no puede paralizarse dicho proceso

(no se permite la interrupción)

•Cualquier trabajo debe ser asignado solo a una sola máquina
Datos de entrada
𝑛𝑛 trabajos
𝑚𝑚 máquinas
Trabajos-máquinas  Tiempos de proceso (𝑝𝑝𝑖𝑖𝑖𝑖 )
No solapamiento
No interrupción
Objetivo: minimizar makespan (el último tiempo de completación)
• Otros objetivos podrían ser: minimizar adelantos/tardanzas,
Veremos un modelo de programación lineal mixto (MILP) para resolver el
problema UPM
Ejemplo
Tres trabajos y dos máquinas
Tiempo de Trabajo Trabajo azul Trabajo verde
Proceso morado
Máquina 1 2 2 2
Máquina 2 3 1 1

Makespan óptimo= 2 unidades temporales. Una solución:

Hora 1 Hora 2
Máquina 1

Máquina 2
4.8 Transporte y logística
En el campo del transporte y la logística hay una gran cantidad de problemas
que pueden ser resueltos usando IO.
Problemas de optimización de red
Gestión de inventarios
Optimización de procesos de almacenes
Problemas de ruta de vehículos
…
Nos centraremos en los problemas de rutas
Problemas de Enrutamiento de
vértices
Varios puntos tienen que ser visitados
Ciertas condiciones necesitan ser satisfechas
• Capacidad
• Distancias
•…
Problema del viajante
Problema de ruta de vehículos
Problema del Viajante
Traveling salesman problem (TSP)
Problema muy conocido en IO
Dado un conjunto de ciudades, hay que encontrar
la ruta que empieza en un origen, visita cada ciudad
exactamente una vez y vuelve al origen.
La solución es un ciclo (no hay subciclos)
Ciclo de circuito Hamiltoniano
Parece simple pero…
Ejemplo de TSP
Un comerciante tiene su oficina en el punto 0
Tiene que visitar 5 compañías, localizadas en los otros puntos del grafo
¿Cuál es la ruta que tiene que seguir para minimizar los costes de transporte?
3
2

0
1
5
4
Dos posibles rutas
3 3
2 2

0 0
1 1
5 5
4 4
TSP: Definición formal
𝑁𝑁 = {1, … , 𝑛𝑛} es el conjunto de puntos a visitar. El comercial está en el punto 0,
denominado depósito. 𝑁𝑁0 = 𝑁𝑁 ∪ {0}. Los puntos en 𝑁𝑁0 están indexados por 𝑖𝑖, 𝑗𝑗
𝐴𝐴 = { 𝑖𝑖, 𝑗𝑗 : 𝑖𝑖, 𝑗𝑗 ∈ 𝑁𝑁0 } es el conjunto de arcos (enlaces entre puntos). 𝑐𝑐𝑖𝑖𝑖𝑖 es el
coste de atravesar el arco (𝑖𝑖, 𝑗𝑗)
(𝑁𝑁, 𝐴𝐴) es un grafo dirigido conectado
Problema: Encontrar la ruta que empieza en 0, visita todos los puntos de N
exactamente una vez y vuelve a 0, de tal forma que el coste total de la ruta
(distancia recorrida) sea mínima. Los únicos enlaces disponibles son los que
están en A
(2) Impone que de cada nodo ha de salir un arco, y (3) impone que a cada nodo ha de
llegar un arco. (4) impone que no haya ciclos o subtours intermedios. Éstas son las
conocidas restricciones de Miller-Tucker-Zemlin (MTZ)
Point X-coord Y-coord
0 20 4 • Distancia euclídea entre puntos
1 -7 9
2 -3 10
3 -17 -9 TSP_7

4 8 -16 6 1 2

5 7 -20 7 0

6 -18 8 3

7 4 4 5
4

8 -13 7
TSP_7: SOL
9 -18 10
10 -15 12 6 1 2
7
0

4
5
Extensiones
Puedes encontrar herramientas en la web para resolver problemas TSPs como:
• Google maps
• [Link]
using-google-maps-and-genetic-algorithms/9
Extensiones
• Más de un comercial o viajante: m-TSP
• Más de una viajante que además viajan a velocidades diferentes m-TSP heterogéneo
• Los viajantes deben visitar a los clientes dentro de una ventana de tiempos: TSP con
ventana de tiempos
• Los viajantes o comerciales distribuyen cierta mercancía en vehículos con capacidad:
vehicle routing problem (VRP),…
4.9 Horarios
La asignación de recursos a los objetos que se colocan en el espacio-
tiempo
Ciertas restricciones necesitan ser satisfechas
Los recursos podrían ser, por ejemplo, trabajadores
Los objetos podrían ser, por ejemplo, las tareas
Las restricciones a satisfacer incluyen
• Máximo número de tareas
• Períodos vacacionales
Horario de un curso universitario
Un conjunto de cursos
Un conjunto de profesores
Un conjunto de aulas
Asignar la programación de los cursos de tal manera que se
maximicen las preferencias totals de profesor-curso, profesor-día,
curso-día
[Link]
[Link]
Datos
𝑛𝑛 profesores (indexados por 𝑖𝑖)
𝑚𝑚 cursos (indexados por 𝑗𝑗)
𝑒𝑒 clases (indexados por 𝑙𝑙)
𝑑𝑑 días (indexados por 𝑘𝑘)
1
𝑝𝑝𝑖𝑖𝑖𝑖 preferencia del profesor 𝑖𝑖 para impartir el curso 𝑗𝑗
2
𝑝𝑝𝑖𝑖𝑘𝑘 preferencia del profesor 𝑖𝑖 para enseñar el día 𝑘𝑘
3
𝑝𝑝𝑗𝑗𝑗𝑗 preferencia del curso 𝑗𝑗 para para ser impartido el día 𝑘𝑘
𝑎𝑎𝑖𝑖𝑖𝑖 toma el valor 1 si el profesor 𝑖𝑖 puede enseñar el día 𝑘𝑘, cero en caso contrario
𝑏𝑏𝑖𝑖𝑖𝑖 toma el valor 1 si el profesor 𝑖𝑖 puede enseñar el curso 𝑗𝑗, cero en caso contrario
𝑐𝑐𝑗𝑗𝑗𝑗 toma el valor 1 si el curso 𝑗𝑗 puede ser impartido en la clase 𝑙𝑙, cero en caso contrario
Variables de decisión
𝑍𝑍𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 Variable binaria que toma el valor 1 si el profesor 𝑖𝑖 imparte el
curso 𝑗𝑗 en el día 𝑘𝑘 en el aula 𝑙𝑙 en el instante 𝑡𝑡, cero en caso
contrario
𝑋𝑋𝑖𝑖𝑖𝑖 Variable binaria que toma el valor 1 si el profesor 𝑖𝑖 está invitado
en el día 𝑘𝑘, cero en caso contrario
Muchas restricciones diferentes. Un modelo largo. Lo dejamos aquí

Glossary (some important concepts)
• Integer variable • Location problems
• Binary variable • Set covering
• Knapsack problem • Median problem
• Cutting stock problem • Weber problem
• Fixed costs • Center problem
• Big M values • Scheduling
• Assignment problem • TSP, location, routing
Bibliografía
H.A. Eiselt and Carl-Louis Sandblom (2012). “Operations Research: A
model based approach” 2nd edition. Springer
F. S. Hillier, G. J. Lieberman, B. Nag and [Link], (2017). “Introduction
to Operations Research”. Mc Graw Hill
R. A. Sarker and C. S. Newton (2008). “Optimization Modelling: A
Practical Approach”. CRC Press
H. A. Taha (2016). “Operations Research: An Introduction” 10th
edition. Pearson