Guı́a de Ejercicios - Certamen 3

Gestión de Operaciones II
ICN-344

Profesores: Ismael Kauak

Ayudantes: Constantino Mavrakis & Paulina Tapia

Problema 1

La empresa de transporte turı́stico Sonic Youth Ltda. realiza viajes desde la región Metro-
politana a diversos destinos en la Quinta región. Juan y Roberto son dos choferes de la empresa,
a quienes se les ha asignado el traslado de dos buses con turistas para ir a visitar las casas de
Pablo Neruda. Para esto, Juan debe viajar a Valparaı́so con destino a La Sebastiana, mientras
que Roberto a La Casa de Isla Negra en El Quisco. La zona geográfica entre Santiago y Val-
paraı́so-El Quisco se ha modelado como un grafo G(N, A), donde N es el conjunto de nodos y
A es el conjunto de arcos. Los arcos representan calles/carreteras y los nodos las intersecciones
entre ellas. El costo de transporte Cij , asociado al arco (i, j), representa el tiempo de viaje (en
minutos) en el arco. Los nodos, arcos y tiempos de viaje se indican en la siguiente figura:

Ambos choferes, Juan y Roberto, partirán desde el Hotel El Viajero en Santiago (nodo 1)
hacia sus respectivos destinos, La Sebastiana en Valparaı́so (nodo 10) y La Casa de Isla Negra
en El Quisco (nodo 8). Juan está convencido de poder llegar a su destino antes que Roberto
llegue al suyo, y es por esto que hacen una apuesta. Encuentre las rutas de mı́nimo tiempo de
viaje entre el Hotel El Viajero y las casas de Neruda, La Sebastiana y La Casa de Isla Negra,
indicando quién llegará primero y, por lo tanto, quién ganará la apuesta.

1
Problema 1 - PAUTA

Con algoritmo de Dijkstra:

2
 Con algoritmo de Bellman-Ford:

Etiquetas y rutas mı́nimas:

Ruta mı́nima Juan: 1-4-7-10

Ruta mı́nima Roberto: 1-3-6-8 ó 1-3-2-6-8
Roberto gana la apuesta.

3
Problema 2

El Ministerio de Salud esta implementando una nueva modalidad de vistas medicas domi-
ciliarias para reducir las listas de espera en consultorios y hospitales. El programa consiste en
asignar un medico a cada consultorio de salud primaria, al cual diariamente se le entrega un
listado de pacientes a visitar durante el dı́a. Por disposición sanitaria, un medico puede visitar a
pacientes con patologı́as de tipo A solo después de haber visitado pacientes con patologı́as tipo
B (no queremos que el medico transmita enfermedades de un paciente a otro).
Desarrolle un modelo de programación lineal que permita determinar la secuencia de visitas
que debe realizar el medico del consultorio Dr. Bernardo Bereton de Viña del Mar de tal forma
que visite a todos los pacientes a costo mı́nimo.
S Suponga que usted conoce diariamente el con-
junto de pacientes que se debe visitarS(A S B) y el consultorio. Por lo tanto, suponga conocido
el costo de ir de i a j, cij , ∀i, j ∈ A B {0}. Recuerde que el medico debe comenzar su dı́a
marcando tarjeta en el consultorio y al terminar las vistas debe volver a marcar.

4
Problema 2 - PAUTA

Conjuntos:

A : Conjunto de paciente con la patologı́a A.

B : Conjunto de pacientes con la patologı́a B.
{0} : Consultorio.
S S
V = A B {0} Conjunto de nodos.
Parámetros:
cij : costo de ir de i a j, , ∀i, j ∈ V
Variables:

1 si voy al nodo j inmediatamente después de ir al nodo i
xij =
0 ∼
Función Objetivo:

X
mı́n cij xij
X
i,j∈V

Restricciones:
Restricción 1: Conservacion de flujo
X X
xij − xji = 0 ∀i ∈ V
j∈O(i) j∈D(i)

Restricción 2: Satisfacción de la demanda.

X
xij = 1 ∀i ∈ V
j∈V

Restricción 3: Evitar subtur en la ruta del medico

X
xij ≤ |S| − 1 ∀S ( V : 2 ≤ |S| ≤ |V | − 2
i,j∈S,i6=j

Restricción 4: Pacientes con patologı́a B deben visitarse antes que los pacientes con patologı́a A

xij = 0 ∀i ∈ A, j ∈ B

Restricción 5: Naturaleza de las variables

xij ∈ {0, 1} ∀i, j ∈ V

Observación: Este modelo es exactamente igual al TSP visto en clases. Solo se agrega la
restricción cuatro que garantiza que no exista un arco activo entre un paciente tipo A y un
paciente tipo B. De esta forma se asegura que el medico visite primero a los pacientes tipo B y
luego a los pacientes tipo A.

5
Problema 3

Un ladrón desea visitar un conjunto de casas C, las cuales se encuentran a una distancia
d1j,k , (j, k ∈ C,, con j 6= k ) entre sı́. En base al estudio previo que ha realizado, sabe que cada
casa c posee un conjunto Ic de artı́culos que puede robar, con un valor pi (i ∈ Ic ) y volumen hi
cada uno.
El ladrón posee una mochila con un volumen disponible W . Cuando su mochila está vacı́a se
desplaza a una velocidad vmáx , y a medida que se va llenando la velocidad disminuye linealmente
hasta llegar un valor vmı́n cuando está llena. El delincuente cuenta con un conjunto de escondites
O que se encuentran a una distancia d2o,j (o ∈ O, j ∈ C ) de las casas (que es equivalente a la
distancia desde las casas a los escondites), pudiendo iniciar su ruta desde cualquiera de ellos
y no necesariamente terminarla en el mismo. Sin embargo, una vez llegado a un escondite, no
puede volver a salir para seguir robando. Por último, considere que cada unidad de tiempo que
se encuentra realizando la ruta tiene un costo β
Formule un TSP (cuya función objetivo es no lineal) que permita maximizar la utilidad del
ladrón. Hint: Para formular el problema como TSP considere que la distancia entre escondites
es 0.

6
Problema 3 - PAUTA

Conjuntos:

C : Conjunto de casas.
O : Conjunto de escondites.
Ic : Conjunto de artı́culos enSla casa C.
N : Conjunto de nodos. ( C O )
Parámetros:
di,j : Distancia entre dos nodos en N. Se define según:
 1
 di,j si i, j ∈ C
 2

di,j si i ∈ O, j ∈ C
di,j =
d2 si i ∈ C, j ∈ O
 j,i


0 si i, j ∈ O

hi : Volumen del artı́culo i.

pi : Valor del artı́culo i.
β : Costo de tiempo de ruta.
Variables:
xj,k : Variable binaria. Toma el valor 1 si se activa el arco (j, k)
yi : Variable binaria. Toma el valor 1 si se roba el artı́culo i.
Wj : Capacidad ocupada de la mochila al llegar al nodo j.
vj : Velocidad del ladrón al llegar al nodo j.
Función Objetivo:

 
XX X X di,j
máx pi yi − β  xi,j 
vj
c∈C i∈Ic i∈N j∈N

Restricciones:
Restricción 1: Todas las casas se deben visitar. (Se sale solo una vez de cada casa)
X
xj,k = 1 ∀j ∈ C
k∈O(j)

Restricción 2: Divergencia.
X X
xj,k − xk,j = 0 ∀j ∈ N
k∈N k∈N

Restricción 3: Solo se puede salir una vez de los escondites.

XX
xo,j = 1
o∈O j∈C

Restricción 4: No se puede sobrepasar la capacidad de la mochila.

Wj ≤ W ∀j ∈ N
Restricción 5: Secuenciamiento de capacidad.
P
Wk ≥ Wj + i∈Ij hi yi − (1 − xj,k ) M ∀k ∈ N, j ∈ C
Wk ≥ Wj − (1 − xj,k ) M ∀k ∈ N, j ∈ O

7
Restricción 6: Velocidad al llegar al nodo c.
Wj
vj ≤ vmáx + (vmı́n − vmáx ) ∀j ∈ N
W
Restricción 7: Naturaleza.

vj , Wj ≥ 0 ∀j ∈ N
xj,k , yi ∈ {0, 1} ∀j, k ∈ N, i ∈ Ic , c ∈ C

8
Problema 4

La compañı́a ’Dream’ necesita coordinar a un equipo de trabajo para difundir Rock por toda
la ciudad ’Metrópolis: Scenes From a Memory’ y luego volver a la empresa. Los clientes rockeros
R están distribuidos en dos sectores extremos de la ciudad: Theater y Floyd, representados por
los conjuntos de nodos T y F . La red de Metrópolis se puede modelar entonces como un grafo
G(N, A) con N = T ∪ F ∪ N0 , donde N0 representa la casa matriz de la empresa y A el conjunto
de arcos o caminos disponibles entre nodos. Sea cij , el costo de transporte desde nodo i a j,
conocido para todo (i, j) ∈ A.
El tamaño de la fuerza a definir es m agentes con m ≥ 1, quienes empiezan y terminan sus
rutas en la central. Luego, se debe asegurar que exactamente m agentes salgan y regresen a la casa
matriz, además de procurar que cada cliente sea visitado sólo una vez. Este problema se puede
considerar como un ’mTSP’. El principio usado en el diseño de la secuencia es visitar primero a
los rockeros del sector T y luego al sector F . Se consideran los sectores conectados cuando uno
del equipo de m visitadores ingresa a F , dado que todo T ya haya sido visitado por la fuerza de
trabajo distribuida. Por otro lado, cada agente tiene asociado un costo f que se incurre toda vez
que el recurso humano m es enviado. Ası́, optimizar los requerimientos de visitadores se convierte
también en parte del objeto de la definición de ruta. 1. Bajo las condiciones descritas, formule
un modelo de programación entera que permita definir la secuencia para todos los m agentes,
de modo que cada cliente sea visitado sólo una vez y el costo total de la ruta sea mı́nimo. 2.
Re-defina la restricción de conexión entre sectores, asumiendo que éstos se consideran vinculados
cuando el equipo completo de m visitadores pasa al grupo F , una vez que todo el grupo T ya fue
visitado. Además, explique las implicancias para el modelo de esta nueva situación. 3. Asumiendo
una matriz de costos asimétrica donde los pesos de subir a un sector son más altos que los de
bajar desde dicho sector, analice conceptualmente la diferencia para la solución óptima entre
este problema propuesto y uno sin división de sectores.

9
Problema 4 - PAUTA

1. Formulación del modelo.

Conjuntos:
R : Conjunto de clientes.
V0 : Casa matriz.
N : V0 ∪ R.
A : Conjunto de arcos.
M : Conjunto de fuerza de trabajo (agentes).
Parámetros:
cij : Costo de traslado desde nodo i hacia nodo j.
fm : Costo por decisión de envı́o de agente m.
Variables:
xij : 1, si nodo j se visita inmediatamente después de i con el agente m asignado; ; 0, ∼.

Restricciones:

Restricción 1: Divergencia.
X X
xij − xji = 0, ∀i ∈ N
j∈O(i) j∈D(i)

Restricción 2: Sólo se sale una vez de cada nodo. (Opcional a Restricción 3).
X
xij = 1, ∀i ∈ N
j∈O(i)

Restricción 3: Sólo se entra una vez de cada nodo.

X
xij = 1, ∀j ∈ N.
i∈D(j)

Restricción 4: Conexión de sector Theater con sector Floyd.

X
xij = 1, ∀i ∈ N.
i∈T,j∈F

Restricción 5: Se asegura que exactamente m agentes salgan desde la casa matriz.

X
x0j = m
j∈R

Restricción 6: Se asegura que exactamente m agentes regresen a la casa matriz. (Opcional a

Restricción 5). X
xj0 = m
j∈R

Restricción 7: Eliminación de loops.

X
xij ≤ |S| − 1, ∀S ⊆ N : 2 ≤ |S| ≤ |N | − 2
i,j∈S:i6=j

Restricción 8: Naturaleza de variables.

xij ∈ {0, 1}, ∀i, j
m≥1 y entero.

10
Función Objetivo:

Minimizar el costo total de recorrido.

X
mı́n cij xij + fm
x
i,j∈A

2. Nueva restricción de conexión.

X
xij = m, ∀i ∈ N
i∈T,j∈F

Detalle de implicancias de esta re-definición para el modelo.

3. Análisis comparativo.

La inclusión de matriz de costos asimétrica (e.g. los costos de subir a un sector son más al-
tos que los de bajar desde dicho sector), impacta en la función objetivo a través de los pesos (
cij ) y hace que la solución difiera desde T hasta F o desde F hacia T. La indiferencia podrı́a
ocurrir si los sectores usan sólo distancias (e.g. Euclidianas, sin peso) en una matriz simétri-
ca o, simplemente, no hay sectores (modelo tradicional). Completar con análisis detallado de
Restricciones 4 y 5 y su influencia en el nuevo contexto planteado.

11
Problema 5

“Acción R” es una empresa de recolección, clasificación y eliminación de todo tipo de residuos,

excepto residuos domiciliarios. La empresa presta servicios a clientes comerciales e instituciones
públicas del área urbana de Viña del Mar, para ello cuenta con K, k = {1, . . . |K|} camiones
recolectores de capacidad C (flota homogénea); V f = {1, . . . , m} sitios de disposición de residuos,
donde los camiones recolectores deben vaciar su carga; V c = {m + 1, . . . , m + n} clientes; y un
solo depósito para guardar los camiones V d = {0}.
El área urbana de Viña del Mar se puede modelar como un grafo G = (V, A) donde V =
V ∪ V f ∪ V c es el conjunto de nodos y A = {(i, j) | i, j ∈ V, i 6= j} es el conjunto de arcos.
d

Diariamente se debe hacer el programa de los vehı́culos, para lo cual se conoce: la demanda del
cliente i, qi , ∀i ∈ V c ; el tiempo de viaje asociado al arco (i, j), tij , ∀(i, j) ∈ A; el costo asociado
al arco (i, j), cij , ∀(i, j) ∈ A. Además, cada nodo i ∈ V tiene asociado un tiempo de servicio Si
y una ventana de tiempo [ai , bi ].
Por disposición de la empresa: (i) todos los camiones deben ser utilizados; (ii) cada camión
recolector debe estar vacı́o cuando retorna al depósito; y (iii) se permiten múltiples viajes de un
camión a los sitios de disposición de residuos.
Formule un PPL que permita programar los vehı́culos de recolección de residuos de “Acción
R”. El objetivo es encontrar el conjunto de rutas para los vehı́culos, minimizando el costo total
de trasporte y satisfaciendo la capacidad vehı́culo, tal que todos los clientes sean visitados
exactamente una vez dentro de su ventana de tiempo.

12
Problema 5 - PAUTA

Conjuntos:

K : Conjunto de camiones.
Vf : Conjunto de vertederos.
Vd : Depósito {0}.
Vc : Conjunto Sde clientes.
V f V d V c Conjunto de nodos.
S
V =
A : Conjunto de arcos.
Parámetros:
C : Capacidad de los camiones.
qi : Demanda del cliente i.
cij : Costo de moverse por el arco (i, j).
tij : Tiempo de viaje por el arco (i, j).
Si : Tiempo de servicio del nodo i.
ai : Lı́mite inferior de la ventana de tiempo para atender i.
bi : Lı́mite superior de la ventana de tiempo para atender i.
Variables:

1 si se visita j inmediatamente después de i con k
xkij =
0 ∼
dki : Carga del camión k al llegar a i.
wik : Tiempo de llegada del camión k al nodo i.
Función Objetivo:

XX X
mı́n cij xkij
x,d,w
i∈I j∈J k∈K

Restricciones:
Restricción 1: Divergencia o conservación de flujo.

X X
xkij − xkji = 0 ∀i ∈ V, k ∈ K
j∈O(i) j∈D(i)

Restricción 2: Se utilizan todos los camiones (todos los camiones salen del origen O hacia un
único nodo j.

X
xkoj = 1 ∀k ∈ K
j∈O(o)

Restricción 3: Satisfacción de la demanda.

X X
xkij = 1 ∀i ∈ V c
k∈K j∈O(i)

Restricción 4: Respetar la ventana de tiempo del nodo i.

ai ≤ wik + Si ≤ bi i ∈ V, k ∈ K

13
Restricción 5: Capacidad máxima de los camiones.

dki + qi ≤ C ∀i ∈ V c

Restricción 6: Secuenciamiento de tiempo (gran M).

wik + Si + tij = wjk si xkij = 1
No hay restricción si xkij = 0

=⇒ wik + Si + tij ≤ wjk + (1 − xkij ) M i ∈ V, j ∈ V, k ∈ K

Restricción 7: Secuenciamiento de capacidad (gran M).

dki + qi = dkj si xkij = 1
No hay restricción si xkij = 0

=⇒ dki + qi ≤ dkj + (1 − xkij ) M i, j ∈ V c

Restricción 8: Se reinicia la capacidad luego de ir a un vertedero.

[
dki ≤ (1 − xkji ) M i∈Vc V d, j ∈ V f , k ∈ K

Restricción 9: Camiones deben volver vacı́os al depósito. (Están obligados a pasar por un verte-
dero antes de volver al depósito.)

xkio = 0 ∀i ∈ V c , k ∈ K
o bien X
xkio = 1 ∀i ∈ V f , k ∈ K
i

Restricción 10: Naturaleza de las variables.

xkij = 0, 1
wik , dki ≥ 0

Observación: Si existen restricciones de secuenciamiento de capacidad/tiempo, no es necesario

incluir la restricción de eliminar subtur o subciclo.

14