Posgrado
  1. Introducción al análisis real  1.1. Teoría de conjuntos y lógica en el análisis real  1.1.1. Conjuntos y operaciones en teoría de conjuntos y lógica en análisis real  1.1.2. Relaciones y funciones  1.1.3. Lógica y cuantificadores  1.1.4. Cardinalidad de conjuntos  1.2. Espacio métrico  1.2.1. Introducción a conjuntos abiertos y cerrados en espacios métricos  1.2.2. Convergencia de secuencias en un espacio métrico  1.2.3. Función continua en un espacio métrico  1.2.4. Compacidad y completitud en espacios métricos en análisis real  1.3. Secuencias y series  1.3.1. Convergencia de secuencias  1.3.2. Series infinitas  1.3.3. Convergencia uniforme  1.3.4. Serie de potencias  1.4. Discriminación  1.4.1. Teorema del valor medio  1.4.2. Serie de Taylor  1.4.3. Funciones de varias variables  1.4.4. Derivada parcial  1.5. Integración  1.5.1. Integración de Riemann y Lebesgue  1.5.2. Integrales impropias  1.5.3. Teoría de la medida: una herramienta fundamental en la integración  1.5.4. Teorema de Fubini  1.6. Análisis funcional  1.6.1. Comprendiendo los espacios de Banach  1.6.2. Espacios de Hilbert  1.6.3. Operadores en espacios  1.6.4. Teoría espectral
  2. Álgebra abstracta  2.1. Entendiendo los grupos en el álgebra abstracta  2.1.1. Definiciones y ejemplos de grupos en álgebra abstracta  2.1.2. Homomorfismos de grupos  2.1.3. Introducción a los subgrupos normales  2.1.4. Teorema de Sylow  2.2. Anillos y campos  2.2.1. Ideales y anillos cociente  2.2.2. Extensiones de campos  2.2.3. Teoría de Galois  2.2.4. Anillos de polinomios  2.3. Introducción a los módulos en álgebra abstracta  2.3.1. Homomorfismo de módulos  2.3.2. Módulos libres  2.3.3. Introducción a los productos tensoriales  2.3.4. Secuencia exacta en módulos  2.4. Álgebra lineal  2.4.1. Espacio vectorial  2.4.2. Autovalores y autovectores  2.4.3. Espacio de producto interior  2.4.4. Diagonalización
  3. Topología  3.1. Topología general  3.1.1. Conjuntos abiertos y cerrados  3.1.2. Compacidad y conexión  3.1.3. Mapas continuos  3.1.4. Axioma de separación  3.2. Topología algebraica  3.2.1. Comprensión de los grupos fundamentales en la topología algebraica  3.2.2. Homotopía y homología  3.2.3. Complejo simplicial  3.2.4. Secuencias exactas en homología  3.3. Topología diferencial  3.3.1. Comprendiendo las variedades en topología diferencial  3.3.2. Funcionamiento suave  3.3.3. Espacio tangente y cotangente  3.3.4. Fibrados vectoriales
  4. Ecuaciones diferenciales  4.1. Ecuación diferencial ordinaria  4.1.1. Ecuaciones de primer orden  4.1.2. Ecuaciones lineales de segundo orden  4.1.3. Sistemas de ecuaciones diferenciales  4.1.4. Análisis de estabilidad en ecuaciones diferenciales ordinarias  4.2. Ecuaciones en derivadas parciales  4.2.1. Clasificación de EDP  4.2.2. Entendiendo las series de Fourier en ecuaciones diferenciales parciales  4.2.3. Introducción a las funciones de Green  4.2.4. Método de caracterización  4.3. Sistemas dinámicos en ecuaciones diferenciales  4.3.1. Teoría de la sostenibilidad  4.3.2. Ciclos límite en sistemas dinámicos  4.3.3. Teoría del caos  4.3.4. Teoría de bifurcación
  5. Probabilidad y estadística  5.1. Teoría de la probabilidad  5.1.1. Variables aleatorias  5.1.2. Distribuciones de probabilidad  5.1.3. Ley de los grandes números  5.1.4. Teorema del límite central  5.2. Inferencia estadística  5.2.1. Pruebas de hipótesis  5.2.2. Intervalo de confianza  5.2.3. Métodos bayesianos  5.2.4. Estimación de máxima verosimilitud  5.3. Procesos estocásticos  5.3.1. Cadenas de Markov  5.3.2. Movimiento browniano  5.3.3. Comprendiendo los procesos de Poisson  5.3.4. Martingalas: Un estudio integral en probabilidad y estadística
  6. Análisis numérico  6.1. Soluciones numéricas de ecuaciones  6.1.1. Descubrimiento original  6.1.2. Métodos iterativos  6.1.3. Análisis de convergencia  6.1.4. Cotas de error en soluciones numéricas de ecuaciones  6.2. Álgebra lineal numérica  6.2.1. Factorización de matrices  6.2.2. Cálculo de valores propios  6.2.3. Matrices dispersas  6.2.4. Técnicas de preacondicionamiento  6.3. Integración y diferenciación numérica  6.3.1. Métodos de cuadratura  6.3.2. Introducción a las diferencias finitas  6.3.3. Análisis de errores en la integración y diferenciación numérica  6.3.4. Métodos adaptativos en integración y diferenciación numérica
  7. Análisis complejo  7.1. Números complejos  7.1.1. Forma polar  7.1.2. Conjugados complejos  7.1.3. Forma exponencial de los números complejos  7.1.4. Raíces de la unidad  7.2. Funciones analíticas  7.2.1. Ecuaciones de Cauchy–Riemann  7.2.2. Series de potencias  7.2.3. Mapeo conforme  7.2.4. Funciones armónicas  7.3. Integración en el plano complejo  7.3.1. Teorema de Cauchy  7.3.2. Teorema del residuo  7.3.3. Integración de contornos  7.3.4. Transformaciones integrales
  8. Lógica matemática y fundamentos  8.1. Lógica proposicional  8.1.1. Tablas de verdad  8.1.2. Equivalencia lógica en la lógica proposicional  8.1.3. Técnicas de demostración en lógica proposicional  8.1.4. Solución en lógica proposicional  8.2. Lógica de predicados  8.2.1. Cuantificadores en lógica de predicados  8.2.2. Sistemas formales en lógica de predicados  8.2.3. Integridad y solidez  8.2.4. Teoría de modelos  8.3. Teoría de conjuntos  8.3.1. Cardinalidad y ordinalidad  8.3.2. Sistemas axiomáticos  8.3.3. Comprender la teoría de conjuntos de Zermelo-Fraenkel  8.3.4. Fuerzas en la teoría de conjuntos
  9. Personalización  9.1. Programación lineal  9.1.1. Método simplex  9.1.2. Dualidad en la programación lineal  9.1.3. Análisis de sensibilidad en programación lineal  9.1.4. Métodos de punto interior  9.2. Programación no lineal  9.2.1. Descenso de gradiente  9.2.2. Multiplicadores de Lagrange  9.2.3. Optimización convexa  9.2.4. Programación cuadrática  9.3. Optimización Combinatoria  9.3.1. Algoritmos de grafos  9.3.2. Programación entera  9.3.3. Flujo de red  9.3.4. Algoritmos de aproximación
  10. Matemáticas discretas  10.1. Teoría de grafos  10.1.1. Representación de grafos  10.1.2. Llanura y color  10.1.3. Algoritmo de camino más corto  10.1.4. Flujo de red  10.2. Compañerismo  10.2.1. Permutación y combinación  10.2.2. Función generadora  10.2.3. Relación de recurrencia  10.2.4. Comprendiendo el Principio de Inclusión-Exclusión  10.3. Criptografía  10.3.1. Aplicaciones de la teoría de números en criptografía  10.3.2. Criptografía Simétrica y Asimétrica  10.3.3. RSA y criptografía de curvas elípticas  10.3.4. Criptografía post-cuántica

Posgrado → Personalización → Optimización Combinatoria ↓


Flujo de red


Los flujos de red desempeñan un papel fundamental en el campo de la optimización combinatoria, una rama de la optimización matemática. El estudio de los flujos de red es una forma de modelar y resolver una variedad de problemas de distribución y asignación de recursos. Los algoritmos de flujo de red ayudan a mejorar el enrutamiento del tráfico, las redes de comunicación, la logística y muchos otros procesos. Profundicemos en este concepto en detalle, comprendamos sus fundamentos, aplicaciones y cómo se utilizan los algoritmos matemáticos para resolver problemas de flujo de red.

Conceptos básicos del flujo de red

Una red en este contexto típicamente consiste en nodos (o vértices) y aristas (o arcos) que conectan estos nodos. Una metáfora simple podría ser un mapa de carreteras de una ciudad donde las intersecciones son los nodos y las carreteras son las aristas. Cada arista tiene una capacidad, que representa el flujo máximo que puede pasar a través de ella.

g = (v, e)

Aquí, G representa el grafo, V es el conjunto de vértices (nodos), y E es el conjunto de aristas. El flujo de red significa encontrar la manera óptima de enviar flujo desde el nodo de origen hasta el nodo sumidero respetando los límites de capacidad en las aristas.

Términos importantes en el flujo de red

  • Nodo de origen: Este es el punto de partida del flujo. Algunos problemas pueden tener múltiples nodos de origen.
  • Nodo sumidero: Este es el punto final del flujo. En algunos escenarios puede haber múltiples nodos sumideros.
  • Capacidad: El flujo máximo que una arista puede transportar.
  • Flujo: La cantidad real que pasa a través de una arista entre dos nodos.
  • Capacidad residual: La capacidad extra disponible en el banco. Es la cantidad obtenida al restar el flujo de la corriente de la capacidad original.

Conservación del flujo

Un principio fundamental en el flujo de red es la conservación del flujo. Para cualquier nodo intermedio (ni origen ni sumidero), la cantidad de flujo entrante debe ser igual a la cantidad de flujo saliente. Matemáticamente, para cualquier nodo v :

(sum_{text{flujo hacia } v} = sum_{text{flujo desde } v})

Problema del flujo máximo

El problema más popular en el flujo de red es el problema del flujo máximo. Involucra encontrar el flujo máximo posible desde un nodo de origen hasta un nodo sumidero en la red. Las restricciones son la capacidad de las aristas y la conservación del flujo en los nodos intermedios.

Algoritmo de Ford-Fulkerson

El algoritmo de Ford-Fulkerson es uno de los métodos más antiguos y comúnmente utilizados para resolver el problema del flujo máximo. La idea detrás del algoritmo es comenzar con un flujo inicial (generalmente 0) y luego aumentarlo utilizando caminos de augmentación.

A continuación, se describe de manera simple el algoritmo de Ford-Fulkerson:

  1. Comience con un flujo de 0.
  2. Encuentre un camino de augmentación desde el origen al sumidero. El camino de augmentación es donde se puede empujar flujo adicional desde el origen al sumidero.
  3. Aumente el flujo a lo largo de este camino por la capacidad residual más pequeña (cuello de botella) de las aristas de este camino.
  4. Siga repitiendo los pasos anteriores hasta que no queden más caminos de augmentación.

Una vez que se agoten todos los caminos de augmentación, se logra el flujo máximo posible.

Ejemplo

Considere una red simple con nodos A (origen), B, C, y D (sumideros) y las siguientes aristas con capacidades:

a -> b : 4
A -> C : 5
B -> C : 3
B -> D : 2
C -> D : 6

Imaginemos esta red:

A B C D 4 5 2 6 3

En esta red, puede comenzar con el camino A -> B -> D. Aquí, la capacidad cuello de botella es 2, así que aumenta el flujo a través de este camino en 2 unidades.

A continuación, utilice el camino A -> C -> D. Aquí, el cuello de botella es de 5 unidades, pero como previamente añadió un flujo de 2 en la sección B -> D, la capacidad disponible actualmente de C -> D se convierte en 4 (original 6 - 2 ya están ocupados de B -> D).

Así, el flujo máximo de A a D alcanza 2 + 4 = 6 unidades.

Problema de flujo máximo de costo mínimo

El problema de costo máximo flujo mínimo se basa en el problema de flujo máximo al agregar costos a las aristas. Su objetivo no es solo encontrar el flujo máximo posible, sino hacerlo al costo mínimo posible.

En este problema, cada arista tiene una capacidad, así como un costo. El costo se incurre por unidad de flujo en esa arista, y el objetivo es minimizar el costo total mientras se logra el flujo máximo.

Ejemplo

Considere la red descrita anteriormente, pero ahora agregue costos a las aristas:

A -> B : 4 (costo 1)
A -> C : 5 (costo 2)
B -> C : 3 (costo 1)
B -> D : 2 (costo 3)
C -> D : 6 (costo 1)

El objetivo es aumentar el flujo de A a D lo máximo posible, manteniendo el costo de ese flujo al mínimo. Las soluciones típicamente utilizan algoritmos como el algoritmo de camino más corto secuencial, que aumenta iterativamente los caminos con el mínimo costo hasta que el flujo se maximiza.

Aplicaciones del flujo de red

Los flujos de red y sus algoritmos se usan ampliamente en una variedad de aplicaciones del mundo real:

  • Transporte: Optimización del flujo de tráfico, programación de semáforos y planificación de rutas en redes logísticas.
  • Telecomunicaciones: Enrutamiento de datos a través de caminos de red para minimizar el retraso, optimizar la distribución del ancho de banda y mejorar la eficiencia general de la red.
  • Gestión de proyectos: Las redes de flujo se pueden usar en técnicas de gestión de proyectos PERT y CPM para optimizar la asignación de recursos y reducir los tiempos de finalización del proyecto.
  • Cadena de suministro: Optimización de redes de distribución, determinación de rutas de envío óptimas y minimización de costos de transporte.
  • Red eléctrica: Gestión eficiente del flujo de electricidad desde las plantas de energía a los consumidores.

Conclusión

Los flujos de red representan una forma importante de modelar y resolver problemas complejos de optimización que involucran la distribución de recursos o información. Con una combinación de conceptos teóricos y algoritmos robustos, los modelos de flujo de red son herramientas poderosas en muchos campos, proporcionando soluciones que equilibran viabilidad y optimización.

Al comprender los conceptos básicos como los problemas de flujo máximo y flujo máximo de costo mínimo y emplear algoritmos como Ford-Fulkerson o camino más corto secuencial, el flujo de red puede abordar efectivamente varios desafíos en logística, comunicación y gestión de recursos.


Posgrado → 9.3.3


U
username
0%
completado en Posgrado

← Anterior (9.3.2)
Programación entera
Siguiente (9.3.4) →
Algoritmos de aproximación

Comentarios 



Flujo de red

https://www.buddymath.com/g/9.3.3?bmal=es