ZCBC/JAG/Métodos de Optimización

Modelos de
Transporte Yimy Alexander Hernández Ortiz
Bogotá, septiembre 14 de 2021
Problema de transporte

En particular, el problema La red representa el problema. Hay m orígenes y

general de transporte se n destinos, cada uno representado por un nodo.
refiere a la distribución de Los arcos (i, j) representan las rutas que unen
cualquier mercancía desde los orígenes con los destinos.
cualquier grupo de centros de
suministro, llamados orígenes,
a cualquier grupo de centros
de recepción, llamados
destinos, de tal manera que se
minimicen los costos totales de
distribución. (Hillier y
Lieberman, 2010)
Modelo del problema de transporte

El modelo del problema de transporte Sujeto a:

general es un tipo especial de problema
de programación lineal. 𝑛
Sea Z el costo total de distribución y xij ෍ 𝑥𝑖𝑗 ≤ 𝑠𝑖 ∀ 𝑖 = 1,2, … , 𝑚
(i = 1, 2, ..., m; j = 1, 2, ..., n) el número
𝑗=1
de unidades que se distribuyen del origen
i al destino j, la formulación de 𝑚
programación lineal de este problema es:
෍ 𝑥𝑖𝑗 = 𝑑𝑗 ∀ 𝑗 = 1,2, … , 𝑛
𝑚 𝑛
𝑖=1
𝑀𝑖𝑛 𝑍 = ෍ ෍ 𝑐𝑖𝑗 𝑥𝑖𝑗
𝑖=1 𝑗=1 𝑥𝑖𝑗 ≥ 0 ∀𝑖∧ 𝑗
Modelo específico de transporte

𝑀𝑖𝑛 𝑍 = 𝑐11 𝑥11 + 𝑐12 𝑥12 + ⋯ + 𝑐1𝑛 𝑥1𝑛 +

𝑐21 𝑥21 + 𝑐22 𝑥22 + ⋯ + 𝑐𝑚𝑛 𝑥𝑚𝑛
Sujeto a: 𝑥𝑖𝑗
𝑥11 + 𝑥12 + ⋯ + 𝑥1𝑛 ≤ 𝑠1
𝑥21 + 𝑥22 + ⋯ + 𝑥2𝑛 ≤ 𝑠2
⋮ ⋮
𝑥𝑚1 + 𝑥𝑚2 + ⋯ + 𝑥𝑚𝑛 ≤ 𝑠𝑚

𝑥11 + 𝑥21 + ⋯ + 𝑥𝑚1 = 𝑑1

𝑥12 + 𝑥22 + ⋯ + 𝑥𝑚2 = 𝑑2
⋮ ⋮
𝑥1𝑛 + 𝑥2𝑛 + ⋯ + 𝑥𝑚𝑛 = 𝑑𝑛
Modelo del problema de transbordo

El problema de transbordo es una extensión Sujeto a:

del modelo de transporte en el que se 𝑛
agregan puntos intermedios de transbordo ෍ 𝑥𝑖𝑗 ≤ 𝑠𝑖 ∀ 𝑖 = 1,2, … , 𝑚
entre las fuentes y los destinos..
𝑗=1
Sea Z el costo total de distribución y xij , wjk
(i = 1, 2, ..., m; j = 1, 2, ..., n; k = 1, 2, ..., p)
𝑚 𝑝
el número de unidades que se distribuyen
del origen i pasando por el transbordo j al ෍ 𝑥𝑖𝑗 = ෍ 𝑤𝑗𝑘 ∀ 𝑗 = 1,2, … , 𝑛
destino k, la formulación de programación
lineal de este problema es: 𝑖=1 𝑘=1

𝑚 𝑛 𝑛 𝑝 𝑛
𝑀𝑖𝑛 𝑍 = ෍ ෍ 𝑐𝑖𝑗 𝑥𝑖𝑗 + ෍ ෍ 𝑐𝑗𝑘 𝑤𝑗𝑘 ෍ 𝑤𝑗𝑘 = 𝑑𝑘 ∀ 𝑘 = 1,2, … , 𝑝
𝑖=1 𝑗=1 𝑗=1 𝑘=1 𝑗=1
𝑥𝑖𝑗 , 𝑤𝑗𝑘 ≥ 0 ∀ 𝑖, 𝑗 ∧ 𝑘
Modelo del problema de transbordo

i j k
Modelo del problema de asignación

En general, un problema de asignación es Sujeto a:

un problema de transporte equilibrado en
el que suministros y demandas son 𝑛
iguales a 1.
෍ 𝑥𝑖𝑗 = 1 ∀ 𝑖 = 1,2, … , 𝑛
Sea Z el costo total de asignación y xij
(i = 1, 2, ..., n; j = 1, 2, ..., n) la variable 𝑗=1
binaria que indica la asignación (1) o no
(0) del recurso i a la tarea j, la 𝑚
formulación de programación lineal de ෍ 𝑥𝑖𝑗 = 1 ∀ 𝑗 = 1,2, … , 𝑛
este problema es:
𝑖=1
𝑚 𝑛

𝑀𝑖𝑛 𝑍 = ෍ ෍ 𝑐𝑖𝑗 𝑥𝑖𝑗 𝑥𝑖𝑗 ∈ 0,1 ∀𝑖∧ 𝑗

𝑖=1 𝑗=1
Programación Entera (PE) y Entera Mixta (PEM)

En muchos problemas prácticos, las Si sólo es necesario que algunas de

variables de decisión sólo tienen las variables tengan valores enteros,
sentido real si su valor es entero. el modelo se conoce como de
El modelo matemático para programación entera mixta (PEM)
programación entera (PE) es Existen además muchas otras
sencillamente el modelo de situaciones donde el uso de la
programación lineal con la programación entera resulta menos
restricción adicional de que las obvio pero igualmente necesario. Tal
variables deben tener valores es el caso de situaciones en las que
enteros. se hace preciso tomar decisiones. En
estos casos se utilizan variables
binarias (0-1) que representan
decisiones tipo “SI, NO”
El problema de la mochila (knapsack)

Considérese un excursionista que Sea Z la utilidad total de los objetos

debe preparar su mochila y que hay empacados y xj (j = 1, 2, ..., n) la
una serie de objetos de utilidad para variable binaria que indica si el
él, pero sólo puede llevar un número objeto j es empacado (1) o no (0), la
limitado de objetos. formulación de este problema es:
El problema consiste en elegir un 𝑛
subconjunto de objetos de tal forma
que se maximice la utilidad que el 𝑀𝑎𝑥 𝑍 = ෍ 𝑢𝑗 𝑥𝑗
excursionista obtiene, pero sin 𝑗=1
rebasar su capacidad de acarrear Sujeto a:
objetos. 𝑛

෍ 𝑎𝑗 𝑥𝑗 ≤ 𝑏
𝑗=1
𝑥𝑗 ∈ 0,1 ∀𝑗
El problema de recubrimiento (set covering)

𝑛
Dado un conjunto de elementos
(llamado universo) y n subconjuntos 𝑀𝑖𝑛 𝑍 = ෍ 𝑐𝑗 𝑥𝑗
cuya unión comprende el universo, el 𝑗=1
problema de cobertura consiste en Sujeto a:
identificar el menor número de 𝑛
subconjuntos que contienen ෍ 𝑥𝑗 ≥ 1 ∀𝑒 ∈𝑈
(cubren) todos los elementos del 𝑗=1
universo.
Sea Z el costo total de los 𝑥𝑗 ∈ 0,1 ∀𝑗
subconjuntos utilizados y xj (j = 1, 2,
..., n) la variable binaria que indica si
se elige (1) o no (0) el subconjunto j,
la formulación de este problema es:
Problema del viajante de comercio (TSP)

El problema consiste en hacer un La formulación de programación entera de

recorrido que pase por n ciudades sin este problema es: 𝑛 𝑛
repetir ninguna y volviendo a la ciudad 𝑀𝑖𝑛 𝑍 = ෍ ෍ 𝑐𝑖𝑗 𝑥𝑖𝑗
de partida de manera que la distancia (o
tiempo o costo) total sea mínima. Es un 𝑖=1 𝑗=1
problema de asignación pero con la Sujeto a:𝑛
condición de que la asignación sea un
ciclo. ෍ 𝑥𝑖𝑗 = 1 ∀ 𝑗 = 1,2, … , 𝑛
𝑖=1
Sea Z la distancia total recorrida, xij 𝑛
(i = 1, 2, ..., n; j = 1, 2, ..., n) la variable
binaria que indica si se va (1) o no (0) de ෍ 𝑥𝑖𝑗 = 1 ∀ 𝑖 = 1,2, … , 𝑛
la ciudad i a la ciudad j, y ui el lugar de 𝑗=1
la secuencia en que se visita el nodo i. 𝑢𝑖 − 𝑢𝑗 ≤ 𝑛 − 1 1 − 𝑥𝑖𝑗 − 1 ∀𝑖∧𝑗
𝑥𝑖𝑗 ∈ 0,1 ∀ 𝑖 ∧ 𝑗
Modelo de transporte para localización de instalaciones

𝑚 𝑛 𝑚
Es un típico problema de programación
entera mixta, cuyo principal beneficio 𝑀𝑖𝑛 𝑍 = ෍ ෍ 𝑐𝑖𝑗 𝑥𝑖𝑗 + ෍ 𝐹𝑖 𝑦𝑖
es la capacidad para manejar costos
fijos en forma óptima. 𝑖=1 𝑗=1 𝑖=1

Sea Z el costo total de distribución, xij Sujeto a:

𝑛
(i = 1, 2, ..., m; j = 1, 2, ..., n) el número
de unidades que se distribuyen de la ෍ 𝑥𝑖𝑗 ≤ 𝑠𝑖 𝑦𝑖 ∀ 𝑖 = 1,2, … , 𝑚
instalación i al destino j, y yi la variable 𝑗=1
binaria que indica la apertura (1) o no
𝑚
(0) de la instalación i, la formulación de
programación entera mixta de este ෍ 𝑥𝑖𝑗 = 𝑑𝑗 ∀ 𝑗 = 1,2, … , 𝑛
problema es:
𝑖=1

𝑥𝑖𝑗 ≥ 0; 𝑦𝑖 ∈ 0,1 ∀𝑖∧𝑗

Modelo de transbordo para localización de instalaciones

Es una extensión del modelo de transporte Sujeto a:

𝑛
para localización, en el que se agregan
puntos intermedios de transbordo entre las ෍ 𝑥𝑖𝑗 ≤ 𝑠𝑖 ∀ 𝑖 = 1,2, … , 𝑚
fuentes y los destinos. 𝑗=1
Sea Z el costo total de distribución, xij , wjk 𝑚
(i = 1, 2, ..., m; j = 1, 2, ..., n; k = 1, 2, ..., p) ෍ 𝑥𝑖𝑗 ≤ 𝑉𝑗 𝑦𝑗 ∀ 𝑗 = 1,2, … , 𝑛
el número de unidades que se distribuyen
del origen i pasando por el transbordo j al 𝑖=1
destino k, y yj la variable binaria que indica 𝑚 𝑝
la apertura (1) o no (0) de la instalación j. ෍ 𝑥𝑖𝑗 = ෍ 𝑤𝑗𝑘 ∀ 𝑗 = 1,2, … , 𝑛
𝑚 𝑛 𝑛 𝑝 𝑛 𝑖=1 𝑘=1
𝑛
𝑀𝑖𝑛 𝑍 = ෍ ෍ 𝑐𝑖𝑗 𝑥𝑖𝑗 + ෍ ෍ 𝑐𝑗𝑘 𝑤𝑗𝑘 + ෍ 𝐹𝑗 𝑦𝑗
𝑖=1 𝑗=1 𝑗=1 𝑘=1 𝑗=1 ෍ 𝑤𝑗𝑘 = 𝑑𝑘 ∀ 𝑘 = 1,2, … , 𝑝
𝑗=1
𝑥𝑖𝑗 , 𝑤𝑗𝑘 ≥ 0; 𝑦𝑖 ∈ 0,1 ∀ 𝑖, 𝑗 ∧ 𝑘
¡GRACIAS POR SU ATENCIÓN!