Problemas de Camino Mínimo entre dos vértices de un grafos como problemas de Programación Lineal
En esta sección aprenderemos como plantear el problema del camino mínimo entre dos vértices un grafo pasando pasando una sola vez por cada arista como un problema de programación lineal.
Este planteamiento será el que usaremos para los problemas a resolver con nuestra aplicación.
Veamos que podemos realizar el siguiente planteamiento, en el cual obtendremos un problema a resolver de programación lineal entera.
Partiremos de un grafo con \(n\) nodos denotados \(1,\ldots,n\) y con un peso entre las aristas \((i,j)\) del grafo con \(i,j\in\{1,\ldots,n\}\) de \(l_{ij}\) (que puede significar longitud, tiempo, etc.). Denotaremos por \((1,j)\) las aristas que parten del vértice de origen para \(j\in\{1,\ldots,n\}\) y \((i,n)\) las aristas que llegan al vértice de destino para \(i\in\{1,\ldots,n\}\).
Tomaremos como variables de decisión
\( x_{ij}= \begin{cases} 1\,,&\mbox{si tomo el camino que va de }i\mbox{ a }j \\ 0\,,&\mbox{en caso contrario} \end{cases} \)
para todo \(i,j\in\{1,\ldots,n\}\).
La función objetivo, valor a optimizar, será \(\mbox{min}\sum_{i=1}^{n-1}\sum_{j=2}^{n}l_{ij}x_{ij}\). Veamos una explicación a esta elección:
Esta función objetivo suma solo los pesos de los caminos que tomamos, ya que el valor de \(x_{ij}\) toma el valor cero si no pasamos por ese camino, por tanto \(l_{ij}x_{ij}\) se anula y suma valor cero en nuestra función objetivo, lo que lleva a que esos pesos, por los que no pasamos, no sumen ningún valor en nuestra función objetivo. En cambio si utilizamos el camino \(x_{ij}\), al tener valor uno, nuestra función objetivo sumará su correspondiente peso \(l_{ij}x_{ij}=l_{ij}\) . Esta función recorre todos los caminos posibles de nuestro problema.
Es decir, esta función objetivo nos aportará el valor de los pesos por los caminos que pasamos, buscando el camino con peso mínimo que nos lleva desde nuestro origen al destino.
Las restricciones, condiciones que debemos imponer a nuestras variables de decisión para que la solución obtenida sea la del problema que hemos planteado, serán:
- \(\sum_{j=2}^{n}x_{1j}=1\) (sólo un camino empieza en el nodo de origen).
- \(\sum_{i=1}^{n-1}x_{ik}=\sum_{j=2}^{n}x_{kj}\) para todo \(k\in\{2,\ldots,n-1\}\) (si un camino llega al nodo \(k\) este sale del nodo \(k\)).
- \(\sum_{i=1}^{n-1}x_{in}=1\) (sólo un camino acaba en el nodo de destino).
- \(x_{ij}\in\{0,1\}\) para todo \(i,j\in\{1,\ldots,n\}\).
A continuación, analizaremos las restricciones anteriores:
Nuestro problema dispone de un origen, de donde sale una única arista, por tanto debemos restringir que todos los caminos posibles que podemos pasar están a valor cero y que solo pasamos por un camino, es decir, solo un \(x_{1j}\) toma el valor uno, de todos los caminos posibles que parten del origen.
Lo mismo ocurre con el destino, que tan solo llega una única arista, por tanto debemos restringir que todos los caminos posibles que podemos pasar están a valor cero y que solo pasamos por un camino, es decir, solo un \(x_{in}\) toma el valor uno, de todos los caminos posibles que llegan al destino.
Asimismo, nos aseguramos que en el resto de nodos, si un camino llega a un nodo, existe un camino que sale de este mismo nodo. De esta forma evitamos la existencia de "nodos sin salida", los cuales nos impiden llegar a nuestro destino.
La última restricción proviene de la descripción de las variables de decisión realizada anteriormente.