Investigación de Operaciones · Clase 11 · 14 de octubre
Una red, tres preguntas
Los mismos nodos. Los mismos arcos. Tres preguntas de negocio distintas, y tres respuestas que no se parecen en nada.
El relojN
Cómo se reparte la sesión
Reloj
Qué pasa
Min
0 – 15
Socialización de la tarea · los grafos en papel
15
15 – 30
El mapa: una red, tres preguntas
15
30 – 45
Nivel 1 · ruta más corta (repaso)
15
45 – 80
Nivel 2 · árbol de expansión mínima · 3 ejercicios
35
80 – 90
Pausa
10
90 – 125
Nivel 3 · flujo máximo · 3 ejercicios a mano
35
125 – 145
Flujo máximo en Solver
20
145 – 160
Dinámica central y cierre
15
Primero lo primero · 15 minN
Los cuatro grafos de la tarea
Todos trajeron su desarrollo en papel. Lo vamos a socializar completo, grafo por grafo.
Quien tenga el grafo 1 muestra su tabla de etiquetas. No el resultado: la tabla.
El salón compara. ¿Alguien fijó los nodos en otro orden? ¿Le dio lo mismo?
Grafos 2, 3 y 4, igual de rápido: Z y ruta.
Uno de los cuatro tiene dos rutas óptimas. Si dos personas trajeron rutas distintas y las dos suman lo mismo, las dos están bien — y eso es lo que hay que discutir hoy.
El mapa del corteN
Una red. Tres preguntas.
Nivel
La pregunta de negocio
La respuesta es…
1 · Ruta más corta
¿Cómo llego de aquí a allá lo más barato?
un camino
2 · Árbol de expansión
¿Cómo conecto todo gastando lo mínimo?
una estructura
3 · Flujo máximo
¿Cuánto alcanzo a pasar por esta red?
un volumen
La semana pasada vimos la primera. Hoy las otras dos — sobre la misma red, para que se vea que lo que cambia no es el dibujo: es la pregunta.
La clave de todoN
Qué significa el número del arco
Nivel 1 · ruta más corta
Un costo que se paga cada vez que se recorre el arco. Minutos, pesos, kilómetros.
Nivel 2 · árbol
Un costo que se paga una sola vez, al construir el arco. Después se usa gratis.
Nivel 3 · flujo máximo
Ya no es un costo: es un tope que no se puede exceder. Cuántas unidades por hora aguanta.
Si no tienen claro qué significa el número, no pueden escoger el modelo. Esa es la pregunta que hay que hacerle al cliente antes de abrir Excel.
En la vida realN
Para qué sirve cada uno
Nivel
Casos reales donde se usa
Ruta más corta
Google Maps y Waze · despacho de ambulancias · ruteo de domicilios · enrutamiento de paquetes en internet · secuencia de operaciones más barata en una planta
Árbol de expansión
Tendido de fibra óptica · electrificación rural · redes de acueducto y gas · cableado de una planta · agrupamiento de clientes en analítica
Flujo máximo
Capacidad de un puerto hacia el interior · cuántos pacientes por hora aguanta una urgencia · ancho de banda de una red · cuántos buses mueve un corredor · asignación de turnos
La pregunta que los separa¿Pago cada viaje, pago una sola construcción, o lo que me duele es el tope? Esa sola pregunta decide cuál de los tres modelos va.
Por qué importaN
Esto es la base de la ingeniería de redes
No es un capítulo del libro. Es el conjunto de herramientas con el que se diseña y se opera cualquier infraestructura conectada.
Se diseña
El árbol decide qué se construye: qué tramos, qué postes, qué cable. Es la fase de inversión.
Se opera
La ruta más corta decide cómo se usa todos los días: por dónde va cada envío, cada vehículo, cada paquete de datos.
Se amplía
El flujo máximo dice cuánto aguanta y, sobre todo, qué tramo ampliar cuando ya no da más.
Diseñar, operar, ampliar. Las tres decisiones grandes de cualquier red — y cada una tiene su modelo.
La red de hoyN
Parque Industrial Siberia
P portería · M muelle · A B C D bodegas · S salida. Esta misma red responde las tres preguntas.
Nivel 1 · ruta más cortaN
El montacargas de la urgencia
Mover una pieza de la portería P a la salida S. El número del arco son minutos, y se pagan cada viaje.
Repaso de la mecánicaN
Lo que ya saben, en tres pasos
Fije el nodo temporal de etiqueta más pequeña. Ese ya no se vuelve a tocar: nada puede llegarle más barato.
Solo entonces, mire a sus vecinos y calcule etiqueta del fijo + peso del arco. Si mejora, baje la etiqueta y anote el nuevo predecesor.
Copie el resto de la fila igual y repita hasta fijar el destino.
Primero confirmo, después reparto. Nunca al revés.
La corridaN
La tabla, fila por fila
fijo
P
M
A
B
C
D
S
—
0
∞
∞
∞
∞
∞
∞
P
0 ✓
4P
6P
∞
∞
∞
∞
M
0
4P ✓
6P
12M
∞
∞
∞
A
0
4P
6P ✓
8A
15A
∞
∞
B
0
4P
6P
8A ✓
11B
15B
∞
C
0
4P
6P
8A
11B ✓
13C
16C
D
0
4P
6P
8A
11B
13C ✓
16C
S
0
4P
6P
8A
11B
13C
16C ✓
Tres etiquetas se corrigen: B de 12 a 8, C de 15 a 11 y D de 15 a 13. El numerito pequeño es el predecesor.
Nivel 2 · árbol de expansión mínimaN
Cambia la pregunta
Ya no hay que ir de P a S. Hay que tender fibra óptica a las siete instalaciones del parque.
Antes
El número era minutos de un viaje, y se paga cada vez que alguien recorre el tramo.
Ahora
El número son metros de canaleta, y se paga una sola vez: al construir. Después la fibra se usa sin costo.
Misma red. Otro número en el arco. Y una respuesta que ya no es un camino, sino una estructura.
Qué es un árbolN
Tres reglas, y una verificación
Toca todos los nodos. Nadie queda sin conexión.
No tiene ciclos. Si hay un ciclo, sobra un arco y se está pagando de más.
Con n nodos tiene exactamente n−1 arcos. Ni uno más, ni uno menos.
La verificación de dos segundos: siete nodos, seis arcos. Si alguien entrega siete, está mal sin necesidad de mirar un solo número.
El algoritmo de KruskalN
Tres pasos y ya
Se hace a mano, ordenando y tachando
PASO 1 Ordene TODOS los arcos de menor a mayor peso.
PASO 2 Vaya tomándolos en ese orden.
Tome uno SOLO SI no cierra un ciclo.
Si cierra ciclo, táchelo y siga.
PASO 3 Pare cuando tenga n - 1 arcos.
Por qué funciona: siempre tomo el más barato que queda. El único motivo para rechazar un arco es que sus dos extremos ya estén conectados — ahí no conecta nada nuevo, solo cobra.
El punto que los tumbaN
El árbol mínimo no da rutas cortas
Dos nodos que estaban a 3 de distancia pueden quedar, dentro del árbol, a 20 — porque para ir del uno al otro toca dar toda la vuelta.
Y está bien. La pregunta no era qué tan rápido voy de A a B. Era cuánto me cuesta tender la red.
La frase para el cuadernoEn ruta más corta pago cada viaje. En árbol de expansión pago una sola vez la construcción y después uso la red gratis. Son dos negocios distintos, y por eso son dos modelos distintos.
Ejercicio 2.1N
La fibra del parque industrial
Metros de canaleta. Siete nodos → seis arcos. Ordenen, tomen y tachen. Hoja 2.1 del Excel.
Ejercicio 2.2N
Acueducto veredal
Un tanque T y cinco veredas. El número son millones de pesos de tubería. Hoja 2.2.
Ejercicio 2.3N
Torres eléctricas
Seis subestaciones. El número son kilómetros de línea de alta tensión. Hoja 2.3.
Decisión de herramientaN
Este no lo llevamos a Solver
Y no es pereza. Es la respuesta correcta.
A mano con Kruskal
En Solver
Dos minutos. Ordenar y tachar.
Hay que prohibir los ciclos, y esas restricciones crecen exponencialmente con el número de nodos
Funciona igual con 6 nodos que con 60
Se vuelve impráctico y no enseña nada
La lección de criterioLa semana pasada vimos que Dijkstra resuelve el problema puro y Solver el contaminado. Hoy la otra cara: hay problemas donde el algoritmo no es el paso previo al modelo. Es la respuesta, y punto.
Pausa
Diez minutos
Al volver cambia la pregunta por tercera y última vez — y el número del arco deja de ser un costo.
Nivel 3 · flujo máximoN
El número del arco ya no es un costo
Ahora es una capacidad: cuántas unidades por hora aguanta ese tramo. Y la pregunta es cuánto alcanza a pasar por la red completa.
Lo que cambia · 1
El número es un tope, no un precio. No se minimiza: se maximiza lo que pasa.
Lo que cambia · 2
Los arcos se vuelven dirigidos. En hora pico la circulación interna del parque es de un solo sentido.
Y la decisión también cambia: ya no es ¿uso este arco? sino ¿cuántas unidades mando por él?
El método a manoN
Caminos de aumento
Ford-Fulkerson
PASO 1 Busque un camino del origen al destino donde
TODOS los arcos tengan capacidad sobrante.
PASO 2 Mande por ese camino el MÍNIMO de las sobrantes.
Ese mínimo es el cuello de ESE camino.
PASO 3 Réstele esa cantidad a todos los arcos del camino.
PASO 4 Repita hasta que no quede ningún camino.
Sume todo lo que mandó.
Ejemplo: si el camino tiene sobrantes 8, 5 y 7, usted manda 5 — porque el tramo del medio no aguanta más. Ese arco queda saturado.
Ejercicio 3.1N
Del muelle a la salida
Contenedores por hora. Origen M, destino S. La portería no participa: el flujo arranca en el muelle.
Ejercicio 3.2N
Red de datos
Gigabits por segundo entre el servidor O y la terminal T. Hoja 3.2.
Ejercicio 3.3N
Cuatro nodos. Parece trivial.
Háganlo a mano. Empiecen por el camino O → A → B → T. Y anoten qué les da.
Decisión de herramientaN
Por eso este sí va a Solver
Problema
Quién gana
Por qué
Árbol de expansión
El algoritmo
Kruskal es infalible y rápido; el modelo es impráctico
Flujo máximo
El modelo
El método a mano depende de escoger bien el orden de los caminos. Solver no se equivoca nunca
Lo que de verdad se están llevandoNo es Kruskal ni Ford-Fulkerson. Es saber cuándo confiar en el algoritmo y cuándo exigir el modelo. Eso es lo que no reemplaza ninguna herramienta.
Flujo máximo en SolverN
Lo único que cambia son dos celdas
Clase 10 · ruta más corta
Hoy · flujo máximo
Decisión
0 o 1
una cantidad
Tope del arco
≤ 1
≤ capacidad
Fórmula del nodo
SUMAR.SI − SUMAR.SI
idéntica, no se toca
Nodos intermedios
= 0
= 0
Origen
= −1
= −F
Destino
= +1
= +F
Objetivo
SUMAPRODUCTO, Mín
la celda F, Máx
La hojaN
Paso a paso en Excel
La lista de arcos. Solo en el sentido que existen — aquí no se duplica nada. Nueve arcos, nueve filas.
La columna de decisión, el flujo por cada arco. Arranca en cero.
La columna de capacidad, que es el tope de cada fila.
La fórmula de nodo, la misma de siempre, arrastrada.
Objetivo: la celda F MÁXIMO
Variables: E2:E10 y la celda F
Restricciones: H2:H7 = I2:I7 (el balance de cada nodo)
E2:E10 <= D2:D10 (nadie pasa su capacidad)
E2:E10 >= 0
Método: Simplex LP
[x] Hacer variables sin restricciones no negativas
La celda F también es variable. Es el error número uno: dejarla por fuera y preguntarse por qué Solver no mueve nada.
Al correrloN
Tres cosas que hay que mirar
F dio 15, igual que a mano. Primero se valida contra el resultado que ya conocen.
Los números salieron enteros sin declarar nada. Misma razón que la semana pasada: cada variable aparece dos veces, una sumando y otra restando.
Los arcos saturados son los que tienen flujo igual a capacidad. Ahí empieza la búsqueda del cuello.
Si F le da 0, se le olvidó meter F como variable. Si le da más de lo posible, se le quedó una restricción de capacidad por fuera.
Lo que vale el temaN
Flujo máximo = corte mínimo
Un corte es un conjunto de arcos que, si los quita, deja al origen sin manera de llegar al destino. El flujo máximo es exactamente la capacidad del corte más pequeño.
La recomendación que ningún gerente ve soloEl cuello de botella no es un arco: es un conjunto. Y ampliar cualquier arco que no esté en el corte mínimo no aumenta ni una sola unidad el flujo. Es plata botada.
Cómo encontrarlo: desde el origen, marque todos los nodos a los que todavía puede llegar por arcos con sobrante. Los arcos que van de un nodo marcado a uno no marcado son el corte.
El resumenN
Los tres niveles en una tabla
Nivel
El arco es…
La respuesta
Herramienta
Verificación
Ruta más corta
costo por viaje
un camino
Dijkstra o Solver
la suma del camino
Árbol de expansión
costo de construir
una estructura
Kruskal
n − 1 arcos
Flujo máximo
tope de capacidad
un volumen
Solver
= corte mínimo
Tres preguntas, tres respuestas de naturaleza distinta, una sola red. Eso es ingeniería de redes.
Dónde vive esto hoyN
No es teoría de libro
Infraestructura
Todo tendido de fibra, de energía o de acueducto se diseña con árbol de expansión. Es el primer cálculo de un ingeniero de redes.
Operación
El cuello de botella de una planta es el mismo concepto que el corte mínimo. Es la Teoría de Restricciones, en versión de red.
Inteligencia artificial
El agrupamiento de clientes por enlace simple es un árbol de expansión cortado. Y recortar el fondo de una foto es un corte mínimo sobre millones de píxeles.
El cierreEl mismo cálculo que les dice qué vía ampliar es el que usa su celular para separar un objeto del fondo. Cambia qué significa el arco. No cambia el modelo.
Dinámica centralN
Diagnóstico de red de una operación real
En parejas. Escogen una operación real que conozcan —donde trabajan, el negocio de la familia, la universidad— y le aplican los tres niveles.
Entregan
Qué debe tener
Un Excel
La red dibujada, los tres modelos resueltos y el corte mínimo señalado
Una página
Las tres respuestas en lenguaje de negocio y una recomendación de inversión
Las instrucciones completas, con la lista de autoverificación, están en el PDF de los recursos. Todo se sube a AVATA.
Cómo saben si está bienN
No me pregunten a mí. Verifíquenlo ustedes.
¿El árbol tiene exactamente n − 1 arcos? Si no, está mal. Sin discusión.
¿El flujo máximo le dio igual a la capacidad del corte que encontró? Si no coinciden, uno de los dos está mal.
¿La ruta más corta suma lo que dice la etiqueta final? Súmenla a mano.
¿Su recomendación nombra un arco que esté en el corte mínimo? Si recomienda ampliar algo que no está en el corte, la recomendación es plata botada.
Los cuatro chequeos están en el PDF. Si los cuatro pasan, el trabajo está bien — no necesitan preguntarme.
Para cerrar
Diseñar, operar, ampliar
Tres decisiones, tres modelos, una sola red. La próxima semana cambiamos de pregunta por última vez — y en vez de la ruta más corta vamos a buscar la más larga.
Porque en un proyecto, la cadena más larga es la que define la fecha de entrega. Y acortar cualquier otra cosa no sirve de nada.