Modelado en Redes

Modelos sobre grafos: conservación de flujo, transporte, flujo a costo mínimo, ruta mínima y ruteo con eliminación de subtours (VRP). La restricción de balance de nodo y el arquetipo de redes de la I1.

Creado por

SebastianZ28

Valoración0 votos

-.-

hub

Grafos y conservación de flujo

Flujo que circula por una red respetando balances

Un modelo de redes vive sobre un grafo dirigido $G = (N, A)$ : nodos $N$ (ciudades, bodegas) y arcos $A$ (rutas). La variable $x_{a}$ es el flujo que circula por el arco $a$ . Las dos reglas base son la conservación de flujo en cada nodo y la capacidad de cada arco.

Conservación de flujo (balance de nodo)

En un nodo intermedio (ni origen ni destino), todo lo que entra debe salir. Con $δ_{i}^{-}$ = arcos que entran a $i$ y $δ_{i}^{+}$ = arcos que salen:

a \in δ_{i}^{-} \sum x_{a} = a \in δ_{i}^{+} \sum x_{a} \forall i intermedio

En nodos con oferta o demanda, el balance queda desequilibrado por esa cantidad neta. La forma general con oferta neta $b_{i}$ (positiva = fuente, negativa = sumidero) es $\sum_{δ_{i}^{+}} x_{a} - \sum_{δ_{i}^{-}} x_{a} = b_{i}$ .

Capacidad de arco

0 \leq x_{a} \leq u_{a} \forall a \in A

Si ves balance de nodo ('lo que entra = lo que sale') estás ante un modelo de redes. Casi todo se arma sobre esa conservación + capacidades de arco; el resto son variaciones.

La firma de una red

Cargando Quiz...

schema

Transporte

De orígenes con oferta a destinos con demanda

El problema de transporte envía producto desde orígenes $i$ (con oferta $s_{i}$ ) a destinos $j$ (con demanda $d_{j}$ ), minimizando el costo total de envío. Variable $x_{ij} \geq 0$ = unidades enviadas de $i$ a $j$ .

min i, j \sum c_{ij} x_{ij} s.a. j \sum x_{ij} \leq s_{i} \forall i, i \sum x_{ij} \geq d_{j} \forall j

Dos familias de restricciones: oferta (no enviar más de lo que tiene cada origen, $\leq s_{i}$ ) y demanda (cubrir lo que pide cada destino, $\geq d_{j}$ ). Es un LP; su matriz es totalmente unimodular, así que la relajación lineal ya da solución entera.

Cuida el sentido: la oferta limita por arriba ( $\leq s_{i}$ , no puedes enviar lo que no tienes) y la demanda exige por abajo ( $\geq d_{j}$ , hay que cubrirla). Invertirlos es el error clásico del transporte.

Oferta vs demanda

Cargando Quiz...

data_object

Flujo a costo mínimo y ruta mínima

El modelo maestro de redes: PFCM

El problema de flujo a costo mínimo (PFCM) generaliza a transporte, asignación y ruta mínima. Enviar flujo por la red minimizando costo, con balance de nodo (oferta neta $b_{i}$ ) y capacidad de arco:

min a \sum c_{a} x_{a} s.a. a \in δ_{i}^{+} \sum x_{a} - a \in δ_{i}^{-} \sum x_{a} = b_{i} \forall i, 0 \leq x_{a} \leq u_{a}

Ruta mínima como caso particular

La ruta mínima de un origen $s$ a un destino $t$ es un PFCM donde se envía 1 unidad: $b_{s} = 1$ (fuente), $b_{t} = - 1$ (sumidero) y $b_{i} = 0$ en el resto. El flujo óptimo traza el camino más barato; con costos no negativos, la solución es un camino simple.

Demanda con faltante

Cuando la red puede no alcanzar a cubrir toda la demanda, se agrega una variable de faltante $r_{j} \geq 0$ que se penaliza en la FO: $\sum_{a \in δ_{j}^{-}} x_{a} = d_{j} - r_{j}$ .

Transporte, asignación y ruta mínima son casos del PFCM. Si dominas balance de nodo + capacidad + costo por arco, adaptas cualquiera de ellos cambiando solo los $b_{i}$ y las cotas $u_{a}$ .

Un solo esqueleto

Cargando Quiz...

schema

Ruteo y eliminación de subtours (VRP)

Cuando los arcos se vuelven binarios

En ruteo (TSP, VRP) la variable de arco es binaria: $x_{ij} \in {0, 1}$ = "el vehículo usa el arco de $i$ a $j$ ". Se pide visitar cada cliente una vez (restricciones de grado: entra un arco y sale un arco por nodo). Esto vuelve el problema un MILP.

j \sum x_{ij} = 1 \forall i, i \sum x_{ij} = 1 \forall j

El problema de los subtours

Las restricciones de grado por sí solas permiten ciclos desconectados (subtours) en vez de un único recorrido. Hay que eliminarlos. La formulación MTZ (Miller-Tucker-Zemlin) agrega variables de orden $u_{i}$ que fuerzan una secuencia coherente:

u_{i} - u_{j} + n x_{ij} \leq n - 1 \forall i \neq = j, i, j \neq = dep \overset{o}{ˊ} sito

Si $x_{ij} = 1$ , la restricción obliga $u_{j} \geq u_{i} + 1$ : el nodo $j$ va "después" de $i$ en el orden, lo que impide cerrar ciclos que no pasen por el depósito. La otra opción es la eliminación de subtours por flujo (mandar flujo por los arcos usados).

Las restricciones de grado (entrar y salir una vez) no bastan: sin eliminación de subtours el modelo admite ciclos sueltos. Si el enunciado pide 'una sola ruta' o 'un recorrido', tienes que agregar MTZ o eliminación por flujo. Olvidarlo es un error típico.

Ojo en la I1

Cargando Quiz...