Teoría de Grafos

Definición de Grafo

• Colección de vértices (nodos) y aristas (conexiones) entre estos vértices
  • Nodos o vértices → Los elementos individuales de un grafo
  • Aristas → Las conexiones entre vértices
• Grado de un nodo
  • Cantidad de aristas conectadas a ese nodo.
• En Investigación Operativa nos permite modelar y resolver problemas que involucran redes, rutas y relaciones

Representación de Grafos en MILP

• $x_{ij}=1$ si la arista entre $i$ y $j$ está presente, y $x_{ij}=0$ en caso contrario.
• Función objetivo $\min {\sum }_{i,j}{x}_{ij}{d}_{ij}$ donde $d_{ij}$ es la distancia entre $i$ y $j$.

Problema del Camino Mínimo

El Problema del Camino Mínimo busca determinar la trayectoria óptima entre un nodo inicial y uno final dentro de una red. Esta red está compuesta por aristas que tienen asignados ciertos valores, como costo, distancia o tiempo, que sirven para cuantificar la ‘calidad’ de cada ruta posible.

Ejemplo

• Necesito ir a la universidad pasando por una librería y un cafetería. El siguiente grafo representa las distancias y las rutas que puedo tomar. Cuál es el camino que minimiza las distancias?

• Variables de decisión

  • $x_{ij}=1$ si se toma el camio entre $i$ y $j$ está presente, y $x_{ij}=0$ en caso contrario.

• Función objetivo

• Restricciones

Problema del Viajero

Problema del Viajero

Problema del viajero

Se busca minimizar las distancias. El viajero debe salir de un origen, pasar por todos los nodos solo una vez y volver a su origen. Tiene aplicaciones en logística, la industria automotriz, para medidas de seguridad, entre otros usos. Las variables de decisión son las aristas del grafo. $x_{ij}$ donde x es 1 si hago el viaje de i a j y 0 en caso contrario la función objetivo será

${\sum }_{i,j}{x}_{ij}\cdot d_{ij}$ donde d es la distancia entre cada lugar las restricciones son que solo se puede llegar a un lugar una sola vez:

${\sum }_i{x}_{ij}=1\forall j\ne i$ y solo se puede salir de un lugar una sola vez ${\sum }_j{x}_{ji}=1\forall i\ne i$ Para eliminar el problema de subtours se resuelve creando variables de decisión adicionales $u_j$ que valdrá un numero entero correspondiente al orden de lugares a los que llego, es decir, el primer destino j al que llegue tendrá la variable $u_j=1$ Se arma la restricción $u_i-uj+n\cdot x_{ij}\le n-1$ donde n es la cantidad de nodos o destinos.

Link to original