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

RelojQué pasaMin
0 – 15Socialización de la tarea · los grafos en papel15
15 – 30El mapa: una red, tres preguntas15
30 – 45Nivel 1 · ruta más corta (repaso)15
45 – 80Nivel 2 · árbol de expansión mínima · 3 ejercicios35
80 – 90Pausa10
90 – 125Nivel 3 · flujo máximo · 3 ejercicios a mano35
125 – 145Flujo máximo en Solver20
145 – 160Dinámica central y cierre15
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.

  1. Quien tenga el grafo 1 muestra su tabla de etiquetas. No el resultado: la tabla.
  2. El salón compara. ¿Alguien fijó los nodos en otro orden? ¿Le dio lo mismo?
  3. 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.

NivelLa pregunta de negocioLa 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

NivelCasos reales donde se usa
Ruta más cortaGoogle 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ónTendido de fibra óptica · electrificación rural · redes de acueducto y gas · cableado de una planta · agrupamiento de clientes en analítica
Flujo máximoCapacidad 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 M A B C D S
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

4 6 3 8 2 9 3 7 2 5 4 P M A B C D S
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

  1. Fije el nodo temporal de etiqueta más pequeña. Ese ya no se vuelve a tocar: nada puede llegarle más barato.
  2. Solo entonces, mire a sus vecinos y calcule etiqueta del fijo + peso del arco. Si mejora, baje la etiqueta y anote el nuevo predecesor.
  3. 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

fijoPMABCDS
—0∞∞∞∞∞∞
P0 ✓4P6P∞∞∞∞
M04P ✓6P12M∞∞∞
A04P6P ✓8A15A∞∞
B04P6P8A ✓11B15B∞
C04P6P8A11B ✓13C16C
D04P6P8A11B13C ✓16C
S04P6P8A11B13C16C ✓
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

  1. Toca todos los nodos. Nadie queda sin conexión.
  2. No tiene ciclos. Si hay un ciclo, sobra un arco y se está pagando de más.
  3. 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

12 20 9 25 7 11 10 22 6 8 11 P M A B C D S
Metros de canaleta. Siete nodos → seis arcos. Ordenen, tomen y tachen. Hoja 2.1 del Excel.
Ejercicio 2.2N

Acueducto veredal

4 6 3 5 5 8 7 9 7 T A B C D E
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

2 4 3 6 5 4 8 12 14 A B C D E F
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 KruskalEn 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 60Se 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

12 11 3 6 5 4 4 9 9 M A B C D S
Contenedores por hora. Origen M, destino S. La portería no participa: el flujo arranca en el muelle.
Ejercicio 3.2N

Red de datos

8 6 3 4 4 3 2 7 6 O A B C D T
Gigabits por segundo entre el servidor O y la terminal T. Hoja 3.2.
Ejercicio 3.3N

Cuatro nodos. Parece trivial.

3 2 3 2 3 O A B T
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

ProblemaQuién ganaPor qué
Árbol de expansiónEl algoritmoKruskal es infalible y rápido; el modelo es impráctico
Flujo máximoEl modeloEl 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 cortaHoy · flujo máximo
Decisión0 o 1una cantidad
Tope del arco≤ 1≤ capacidad
Fórmula del nodoSUMAR.SI − SUMAR.SIidéntica, no se toca
Nodos intermedios= 0= 0
Origen= −1= −F
Destino= +1= +F
ObjetivoSUMAPRODUCTO, Mínla celda F, Máx
La hojaN

Paso a paso en Excel

  1. La lista de arcos. Solo en el sentido que existen — aquí no se duplica nada. Nueve arcos, nueve filas.
  2. La columna de decisión, el flujo por cada arco. Arranca en cero.
  3. La columna de capacidad, que es el tope de cada fila.
  4. La fórmula de nodo, la misma de siempre, arrastrada.
  5. La celda F, sola, en blanco. Es una variable más.
En H2, y se arrastra
=SUMAR.SI($C$2:$C$10 ; G2 ; $E$2:$E$10) - SUMAR.SI($B$2:$B$10 ; G2 ; $E$2:$E$10)
El cuadro de SolverN

Tal cual se llena

Datos → Solver
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

  1. F dio 15, igual que a mano. Primero se valida contra el resultado que ya conocen.
  2. 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.
  3. 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

NivelEl arco es…La respuestaHerramientaVerificación
Ruta más cortacosto por viajeun caminoDijkstra o Solverla suma del camino
Árbol de expansióncosto de construiruna estructuraKruskaln − 1 arcos
Flujo máximotope de capacidadun volumenSolver= 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.

EntreganQué debe tener
Un ExcelLa red dibujada, los tres modelos resueltos y el corte mínimo señalado
Una páginaLas 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.

  1. ¿El árbol tiene exactamente n − 1 arcos? Si no, está mal. Sin discusión.
  2. ¿El flujo máximo le dio igual a la capacidad del corte que encontró? Si no coinciden, uno de los dos está mal.
  3. ¿La ruta más corta suma lo que dice la etiqueta final? Súmenla a mano.
  4. ¿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.
← Portal
← → o el apuntador para avanzar · F pantalla completa
1 / 0