Investigación de Operaciones · Clase 10 · 7 de octubre
La ruta más corta
Arranca el corte 3. Cambia la estructura del problema: ya no es una tabla de orígenes y destinos, es una red.
AperturaN
Abran Google Maps ahora mismo
Pidan la ruta de donde están hasta su casa.
¿Por qué les dio esa ruta y no otra? Alguien tuvo que convertir Bogotá en un modelo matemático. Eso es lo que vamos a hacer hoy — con ocho nodos en vez de doscientos mil.
El relojN
Cómo se reparte la sesión
Reloj
Qué pasa
Min
0 – 8
Apertura y encuadre
8
8 – 28
Teoría: de dónde venimos y qué es una red
20
28 – 58
El algoritmo de Dijkstra, a mano
30
58 – 68
Pausa
10
68 – 108
El modelo en Solver, paso a paso
40
108 – 138
Lo montan ustedes
30
138 – 148
Cómo conecta con el resto del corte
10
148 – 160
Reto de los 4 grafos y cierre
12
De dónde venimosN
El semestre en una tabla
Corte
Qué decidían
Cómo se veía el dato
1
Cuánto producir de cada cosa
Una lista de variables y restricciones
2
Quién le manda a quién, quién hace qué
Una matriz completa: filas × columnas
3
Por dónde pasar, qué conectar, cuándo termina
Una red: nodos y arcos
Las herramientas son las mismas — Solver, función objetivo, restricciones. Lo que cambia es la forma del problema.
El cambio de chipN
De matriz a lista de arcos
En transporte, cada origen podía mandarle a cada destino. La matriz estaba llena.
En una red, la mayoría de los pares de nodos no están conectados. Y esa ausencia no es un dato faltante — es el dato.
Lo que hay que guardarOcho nodos dan 28 pares posibles. La red de hoy tiene 11 conexiones. Las otras 17 no son ceros ni infinitos: no existen, y por eso la red se guarda como una lista de los arcos que sí hay.
Vocabulario · 1 de 3N
Las piezas de una red
NodoUn punto donde pasa algo: un cruce, una bodega, una máquina, un evento. También se le dice vértice.
ArcoUna conexión entre dos nodos. Siempre carga un número: tiempo, costo, distancia o capacidad.
Arco dirigidoSe recorre en un solo sentido. Una vía de una sola mano, un proceso que no se devuelve.
Arco no dirigidoSe recorre en los dos sentidos. Los de hoy son todos así.
Una red es simplemente el conjunto de nodos más el conjunto de arcos. Nada más.
Vocabulario · 2 de 3N
Cómo se recorre una red
CaminoSecuencia de arcos que une dos nodos sin repetir ninguno. También se le dice cadena.
CicloUn camino que vuelve al nodo donde empezó. En minimización, un ciclo solo suma costo.
Red conexaDesde cualquier nodo se puede llegar a cualquier otro. Si no lo es, hay nodos huérfanos.
ÁrbolRed conexa sin ciclos. Con n nodos tiene exactamente n−1 arcos. Ni uno más.
Esa última definición es la base de la clase 11. Si sobra un arco, hay un ciclo; si falta uno, la red se parte.
Vocabulario · 3 de 3N
Qué se mueve por la red
FlujoLo que se mueve por los arcos: unidades, vehículos, datos, dinero. Hoy movemos una sola unidad.
CapacidadEl tope de flujo que aguanta un arco. Hoy no importa. En flujo máximo es el corazón del problema.
FuenteEl nodo donde nace el flujo. El origen del recorrido.
SumideroEl nodo donde el flujo se absorbe. El destino.
Son ocho palabras. Con estas ocho se arman los cinco problemas que vamos a ver en todo el corte.
El mapa del corteN
Cuatro problemas, una sola estructura
Problema
La pregunta de negocio
Qué optimiza
Ruta más corta
¿Cómo llego de aquí a allá?
La suma mínima sobre un camino
Árbol de expansión
¿Cómo conecto todo gastando lo menos?
La suma mínima sobre una estructura
Flujo máximo
¿Cuánto alcanzo a pasar por la red?
El volumen total, con capacidades
CPM y PERT
¿Cuándo termina el proyecto?
La ruta más larga
Mismos nodos, mismos arcos, mismo Solver. Cambia qué le pedimos a la red.
El arco del corteN
Empiezan buscando la más corta. Terminan buscando la más larga.
En un proyecto, la cadena de tareas más larga es la que define la fecha de entrega. Acortar cualquier otra cosa no sirve de nada.
Esa cadena tiene nombre: la ruta crítica. Y es, literalmente, el mismo modelo de hoy con el signo cambiado.
El algoritmoN
Dijkstra — se dice DÉIKS-tra
Edsger Wybe Dijkstra, neerlandés. En holandés la ij suena como el ei de "reina".
Lo pensó en 1956, en unos veinte minutos, sentado en la terraza de un café en Ámsterdam. Sin papel y sin lápiz. Lo publicó en 1959 en un artículo de página y media.
Setenta años despuésEse mismo algoritmo, con mejoras, corre miles de millones de veces al día dentro de Maps, Waze, Uber y Rappi. Es el despliegue de investigación de operaciones más grande que existe.
Los bordesN
Qué resuelve y qué no
Sí
No
La ruta mínima desde un origen a todos los nodos, de una sola corrida
Costos negativos en algún arco: ahí se equivoca
Redes enormes, muy rápido
Restricciones añadidas: "pase por C", "tope de presupuesto"
Exige una sola cosa: que ningún arco cueste menos que cero. Toda su garantía depende de que agregar arcos nunca abarate el camino.
Las tres piezasN
Qué hay que anotar en cada nodo
Etiqueta
La mejor distancia conocida desde el origen hasta ese nodo. Arranca en infinito, salvo el origen en cero.
Temporal o permanente
Temporal: lo mejor que conozco por ahora, puede bajar. Permanente: ya no puede mejorar nunca.
Predecesor
De qué nodo llegué. Sin esto le queda el número final pero no la ruta.
Se escribe así: [distancia , predecesor]. El origen arranca en [0, —].
La mecánicaN
El ciclo, en tres pasos
Fije el nodo temporal de etiqueta más pequeña. Ese ya no se vuelve a tocar.
Mire a sus vecinos que sigan temporales. Para cada uno calcule etiqueta del fijo + peso del arco. Si da menos que lo que el vecino tenía, bájele la etiqueta y anote el nuevo predecesor.
Repita hasta que el destino quede fijo.
¿Por qué el paso 1 es válido? Si un nodo tiene la etiqueta más pequeña, ninguna otra ruta puede llegarle más barato: cualquier otra tendría que pasar primero por un nodo que ya cuesta más.
El grafo de hoyN
De A hasta H
Ocho nodos, once arcos. Nadie grite la respuesta. Vamos a dejar que el algoritmo la encuentre.
La corrida · 1N
Iteraciones 1 a 4
fijo
A
B
C
D
E
F
G
H
—
0
∞
∞
∞
∞
∞
∞
∞
A
0 ✓
3A
1A
∞
∞
∞
∞
∞
C
0
3A
1A ✓
3C
∞
6C
∞
∞
B
0
3A ✓
1A
3C
∞
6C
8B
∞
D
0
3A
1A
3C ✓
7D
5D
8B
∞
Arriba a la izquierda, el nodo que se fija en esa iteración. El numerito pequeño es el predecesor. Las celdas doradas ya son permanentes.
El primer golpeN
La etiqueta de F se corrige
Momento
Cuenta
F queda en
Al fijar C (etiqueta 1)
1 + 5 = 6
6, viniendo de C
Al fijar D (etiqueta 3)
3 + 2 = 5
5, viniendo de D
El arco directo C→F cuesta 5 y parece lo más barato. Dando la vuelta por D cuesta 2+2 = 4. El arco directo pierde.
Por eso existe la palabra "temporal"Si hubiéramos dado F por bueno en la iteración 2, nos quedamos con 6 y la respuesta final habría salido mal.
La corrida · 2N
Iteraciones 5 a 8
fijo
A
B
C
D
E
F
G
H
F
0
3A
1A
3C
7D
5D ✓
8B
8F
E
0
3A
1A
3C
7D ✓
5D
8B
8E,F
G
0
3A
1A
3C
7D
5D
8B ✓
8E,F
H
0
3A
1A
3C
7D
5D
8B
8E,F ✓
Mire la columna H en las dos últimas filas: tiene dos predecesores. Eso no es un error de la tabla.
El segundo golpeN
G se fija y no sirve para nada
El nodo G termina con etiqueta 8 — el mismo número que el destino. Y no aparece en ninguna ruta óptima.
Dijkstra no apunta al destino. Se expande en todas las direcciones, como una mancha de aceite. Por eso también gasta tiempo en nodos que no van a servir.
Y eso resulta ser una ventajaCuando termina, usted no tiene solo la ruta a H: tiene la distancia mínima de A a los ocho nodos. Para un despachador, eso es la columna completa de su tabla de distancias, gratis, en una sola corrida.
Lo que significa el empateN
Cuando el modelo no puede desempatar
Las dos rutas cuestan 8 y usan 4 arcos. Para el modelo son idénticas.
Esto ya lo vieron en ServiTech: cuando el objetivo no mide algo, el modelo lo reparte al azar. Solver le va a entregar una de las dos y ni le avisa que existe la otra.
Qué hacer en la vida realSi las dos rutas le dan igual, escoja cualquiera. Si no le dan igual — una pasa por un barrio pesado, la otra tiene más semáforos — entonces ese criterio le faltaba al modelo, y hay que meterlo en el número del arco.
La objeciónN
"Para qué modelar, si se ve a ojo"
Con ocho nodos, revisar arco por arco funciona. Veamos qué pasa cuando la red crece.
Red de esquinas
Nodos
Rutas posibles
3 × 3
9
12
4 × 4
16
184
5 × 5
25
8.512
6 × 6
36
1.262.816
Treinta y seis esquinas son un barrio. A diez segundos por ruta, revisarlas todas son 146 días sin dormir.
El segundo grafoN
Ahora de H hasta 5
Ocho nodos, trece arcos. Este no lo vamos a hacer a mano. Lo vamos a montar en Excel, paso a paso.
Paso 1N
La red se vuelve una lista
Cada arco de doble sentido genera dos filas: ida y vuelta. Trece arcos dan 26 filas.
fila
origen
destino
costo
usar (x)
2
H
7
8
3
7
H
8
4
H
4
7
5
4
H
7
…
…
…
…
27
5
2
2
¿Por qué dirigidos, si las vías son de doble sentido? Porque así "lo que entra" y "lo que sale" se pueden contar por separado. Ya van a ver por qué importa.
Paso 2N
La columna de decisión
Una celda por arco. Vale 1 si la ruta usa ese arco, 0 si no.
E2:E27 ← las 26 celdas que Solver va a mover
Arránquelas en cero. Nunca en blanco: una celda vacía y una celda en cero se ven igual, pero algunas fórmulas las tratan distinto.
Ojo con estoSon 26 variables para una red de 8 nodos. En transporte, 8 orígenes y 8 destinos daban 64 variables. La red usa menos, porque solo guarda lo que existe.
Paso 3N
La función objetivo
Idéntica a todo lo que llevan haciendo desde el corte 2.
Celda objetivo
=SUMAPRODUCTO(D2:D27 ; E2:E27)
Costo de cada arco × si lo uso o no. Los arcos en cero no suman nada. Minimizar.
La pregunta que hay que hacerles¿Qué pasa si en vez de la columna de costos apunto a una columna de kilómetros? ¿O de peajes? Misma red, misma estructura, otra respuesta. Qué número va en el arco es una decisión de negocio, no técnica.
Paso 4 · lo nuevoN
Conservación de flujo = balance de masa
Para cada nodo: lo que entra menos lo que sale.
Nodo
Qué le pasa
Debe dar
H · origen
Despacha la unidad, no la recibe
−1
5 · destino
Recibe la unidad, no la despacha
+1
Los demás
Si entra, tiene que salir
0
En transporte restringían por fila y por columna. En redes se restringe por nodo. Ese es el salto de todo el corte 3.
Busca el nodo en la columna destino → suma lo que entra
Segundo SUMAR.SI
Busca el nodo en la columna origen → suma lo que sale
Ocho filas y se acabó. Esta fórmula no cambia en árbol, en flujo máximo ni en CPM. Apréndansela hoy.
Paso 6N
El cuadro de Solver
Datos → Solver
Objetivo: la celda del SUMAPRODUCTO Mín
Variables: E2:E27
Restricciones: H2:H9 = I2:I9 (el balance de cada nodo)
E2:E27 >= 0
E2:E27 <= 1
Método: Simplex LP
[x] Hacer variables sin restricciones no negativas
Sin declarar binarias. Y aun así van a salir ceros y unos exactos. Córranlo y vemos por qué.
El resultadoN
Z = 8 por H-1-3-2-5
4 + 1 + 1 + 2 = 8. El arco directo H→4 cuesta 7 y no se usa: llegar al 4 por 1 y 3 cuesta 6. La misma lección del grafo anterior.
La verificaciónN
Nodo por nodo, tiene que cuadrar
nodo
entra
sale
entra − sale
debe ser
H
0
1
−1
−1
1
1
1
0
0
2
1
1
0
0
3
1
1
0
0
4
0
0
0
0
6
0
0
0
0
7
0
0
0
0
5
1
0
1
1
Miren los nodos 4, 6 y 7: no entra nada y no sale nada. Un nodo que el modelo decide no visitar también cumple su restricción. Eso es justo lo que le permite escoger la ruta.
La pregunta de la clase 6N
¿Por qué salieron 0 y 1 solos?
Nunca declaramos las variables como binarias. Corrimos Simplex LP, sin enteros. Y sin embargo no salió ningún 0,4.
Porque cada variable aparece exactamente dos veces en las restricciones: una vez sumando (en el nodo al que entra) y una vez restando (en el nodo del que sale). Con esa estructura, la geometría del problema solo tiene vértices enteros. No hay por dónde que salga un decimal.
Lo mismo que pasó en asignaciónTiene nombre técnico: matriz totalmente unimodular. Y tiene un límite: si aparece un costo fijo ("abrir este tramo cuesta 200 mil además del recorrido"), la estructura se rompe y ahí sí hay que declarar binarias.
Cómo se delatanN
Los tres errores de esta hoja
El error
Cómo se ve
Cargaron los arcos en un solo sentido
Solver dice que no hay solución factible
Invirtieron los signos del origen y el destino
Sale una ruta, pero al revés: de 5 hacia H
Los dos SUMAR.SI quedaron en el mismo orden
Todo da cero y el modelo "resuelve" sin moverse
El tercero es el peligroso: no da error. Da una respuesta tranquila y equivocada. Si Z le sale cero, revise ese orden.
Lo montan ustedes · 30 minN
El grafo de A hasta H, en Solver
Cómo
Qué entregan
Qué buscamos
Solos o en parejas, máximo dos
Nada. Lo muestran en pantalla
Que Solver les dé 8 y una ruta válida
Antes de arrancarN
Tres cosas que les van a doler
Once arcos son 22 filas, no 11. Cada uno en los dos sentidos.
El origen es A y el destino es H. A lleva −1, H lleva +1, los seis del medio llevan cero.
Ya saben que hay empate. Si su compañero obtuvo otra ruta y también suma 8, los dos están bien. Compárenlas.
Quien copie la hoja del grafo anterior y solo cambie los números va a chocar con que esta red tiene otros nodos y otro tamaño. Revisen los rangos.
Hacia dónde vamosN
Esta hoja no se bota
Lo que montaron hoy es la plantilla de todo el corte. Lo único que cambia es el lado derecho.
Problema
Qué cambia respecto a hoy
Árbol de expansión
Ya no busca un camino: conecta todos los nodos con n−1 arcos
Flujo máximo
Los arcos ganan capacidad y la unidad se vuelve volumen
CPM
Los nodos son eventos y se busca la ruta más larga
PERT
Lo mismo que CPM, pero cada arco trae tres duraciones y una probabilidad
El hilo conductorN
Lo que nunca cambia
La lista de arcos
Origen, destino, número. Siempre. En los cinco problemas del corte.
La restricción por nodo
Entra menos sale. Cambia el lado derecho, nunca la fórmula.
El SUMAPRODUCTO
Peso por decisión. Lo único que se mueve es a qué columna apunta.
Si hoy entienden por qué la restricción es por nodo y no por fila, las próximas cuatro clases son variaciones de lo mismo.
El calendarioN
Lo que queda del semestre
Fecha
Clase
Tema
7 oct
10
Ruta más corta — hoy
14 oct
11
Árbol de expansión mínima y flujo máximo
21 oct
12
CPM: la ruta crítica
28 oct
13
PERT: duraciones con incertidumbre
4 nov
14
Taller integrador
11 nov
15
Parcial del corte 3
Reto de los 4 grafos · 12 minN
A mano, contra el reloj
Cada grupo recibe un grafo distinto. Nadie tiene el mismo que el vecino.
Seis minutos para correr Dijkstra a mano. Tabla de etiquetas, no adivinanza.
Veinte segundos por grupo para decir dos cosas: el número y la ruta.
Los cuatro grafos tienen trampas distintas. Uno de ellos tiene empate. No digo cuál.
Para la próxima
Hoy buscaron la más corta
En cinco semanas van a buscar la más larga — y esa es la que decide si un proyecto se entrega a tiempo o no.
Maps optimiza el tiempo, porque eso fue lo que Google decidió optimizar. Si a su empresa lo que le duele son los peajes, el combustible o el riesgo de la vía, Maps no es su modelo. El suyo lo arma usted.