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

RelojQué pasaMin
0 – 8Apertura y encuadre8
8 – 28Teoría: de dónde venimos y qué es una red20
28 – 58El algoritmo de Dijkstra, a mano30
58 – 68Pausa10
68 – 108El modelo en Solver, paso a paso40
108 – 138Lo montan ustedes30
138 – 148Cómo conecta con el resto del corte10
148 – 160Reto de los 4 grafos y cierre12
De dónde venimosN

El semestre en una tabla

CorteQué decidíanCómo se veía el dato
1Cuánto producir de cada cosaUna lista de variables y restricciones
2Quién le manda a quién, quién hace quéUna matriz completa: filas × columnas
3Por dónde pasar, qué conectar, cuándo terminaUna 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

ProblemaLa pregunta de negocioQué 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 corridaCostos negativos en algún arco: ahí se equivoca
Redes enormes, muy rápidoRestricciones 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

  1. Fije el nodo temporal de etiqueta más pequeña. Ese ya no se vuelve a tocar.
  2. 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.
  3. 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

1 3 1 5 2 5 2 4 2 3 1 A C F B D H G E
Ocho nodos, once arcos. Nadie grite la respuesta. Vamos a dejar que el algoritmo la encuentre.
La corrida · 1N

Iteraciones 1 a 4

fijoABCDEFGH
—0∞∞∞∞∞∞∞
A0 ✓3A1A∞∞∞∞∞
C03A1A ✓3C∞6C∞∞
B03A ✓1A3C∞6C8B∞
D03A1A3C ✓7D5D8B∞
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

MomentoCuentaF queda en
Al fijar C (etiqueta 1)1 + 5 = 66, viniendo de C
Al fijar D (etiqueta 3)3 + 2 = 55, 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

fijoABCDEFGH
F03A1A3C7D5D ✓8B8F
E03A1A3C7D ✓5D8B8E,F
G03A1A3C7D5D8B ✓8E,F
H03A1A3C7D5D8B8E,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 esquinasNodosRutas posibles
3 × 3912
4 × 416184
5 × 5258.512
6 × 6361.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

8 7 4 2 1 3 1 3 3 1 6 1 2 7 6 4 5 H 3 1 2
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.

filaorigendestinocostousar (x)
2H78
37H8
4H47
54H7
…………
27522
¿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.

NodoQué le pasaDebe dar
H · origenDespacha la unidad, no la recibe−1
5 · destinoRecibe la unidad, no la despacha+1
Los demásSi entra, tiene que salir0
En transporte restringían por fila y por columna. En redes se restringe por nodo. Ese es el salto de todo el corte 3.
Paso 5 · la fórmulaN

Una sola, y se arrastra

En H2, y se arrastra hasta H9 — una fila por nodo
=SUMAR.SI($C$2:$C$27 ; G2 ; $E$2:$E$27)
   - SUMAR.SI($B$2:$B$27 ; G2 ; $E$2:$E$27)
ParteQué hace
Primer SUMAR.SIBusca el nodo en la columna destino → suma lo que entra
Segundo SUMAR.SIBusca 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

8 7 4 2 1 3 1 3 3 1 6 1 2 7 6 4 5 H 3 1 2
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

nodoentrasaleentra − saledebe ser
H01−1−1
11100
21100
31100
40000
60000
70000
51011
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 errorCómo se ve
Cargaron los arcos en un solo sentidoSolver dice que no hay solución factible
Invirtieron los signos del origen y el destinoSale una ruta, pero al revés: de 5 hacia H
Los dos SUMAR.SI quedaron en el mismo ordenTodo 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

1 3 1 5 2 5 2 4 2 3 1 A C F B D H G E
CómoQué entreganQué buscamos
Solos o en parejas, máximo dosNada. Lo muestran en pantallaQue Solver les dé 8 y una ruta válida
Antes de arrancarN

Tres cosas que les van a doler

  1. Once arcos son 22 filas, no 11. Cada uno en los dos sentidos.
  2. El origen es A y el destino es H. A lleva −1, H lleva +1, los seis del medio llevan cero.
  3. 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.

ProblemaQué cambia respecto a hoy
Árbol de expansiónYa no busca un camino: conecta todos los nodos con n−1 arcos
Flujo máximoLos arcos ganan capacidad y la unidad se vuelve volumen
CPMLos nodos son eventos y se busca la ruta más larga
PERTLo 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

FechaClaseTema
7 oct10Ruta más corta — hoy
14 oct11Árbol de expansión mínima y flujo máximo
21 oct12CPM: la ruta crítica
28 oct13PERT: duraciones con incertidumbre
4 nov14Taller integrador
11 nov15Parcial del corte 3
Reto de los 4 grafos · 12 minN

A mano, contra el reloj

  1. Cada grupo recibe un grafo distinto. Nadie tiene el mismo que el vecino.
  2. Seis minutos para correr Dijkstra a mano. Tabla de etiquetas, no adivinanza.
  3. 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.
← Portal
← → o el apuntador para avanzar · F pantalla completa
1 / 42