Problema de camino mínimo en grafos visto como un problema de programación lineal
Aunque este problema podría ser resuelto por los algoritmos que hemos visto anteriormente, dado que la asignatura es de programación lineal, transformaremos el problema en cuestión en un PPL, ya que, quizás no sea el mejor método para resolver problemas de caminos mínimo; sin embargo, si que sera lo más adecuado dentro del ámbito de estudio de la asignatura.
Veamos a continuación el planteamiento que usaremos para obtener un problema de programación lineal entera:
En primer lugar, partamos de un grafo con \(\mathbf{n}\) nodos denotados \(\mathbf{{1,...,n}}\) y con un peso entre las aristas \(\mathbf{(i, j)}\) de \( \mathbf{x_{ij}}\). Denotemos ahora por \(\mathbf{(1,j)}\) las aristas que parten del vértice de origen para \(\mathbf{j \in{1,...,n} }\).
Tomemos como variables de decisión: \(A=\left\{ \begin{array}{lcc} 1 & \textrm{si tomo el camino que va de i a j}\\ 0 & \textrm{en caso contrario} \end{array} \right.\) (Esto queda pendiente de ser solucionado)
Para todo \(i,j\in \left\{1,...,n\right\}\)
Nuestra función objetivo será \(\textbf{min} \mathbf{\sum_{j=2}^{n}\sum_{i=1}^{n-1}l_{ij}x_{ij}}\) . Veamos el por qué de esta decisión:
Esta función únicamente sumará los pesos de los caminos que tomemos, ya que el valor de \(x_{ij}\) valdrá 0 si no pasamos por dicho camino, en consecuencia el producto con \(l_{ij}\) se anulará y el valor de la función objetivo permanecerá intacto. Por otro lado si recorremos el camino \(x_{ij}\), al valer 1, se le sumará el correspondiente peso \(l_{ij}\) a nuestra función objetivo abarcando así todas las opciones posibles de nuestro problema. Finalmente esta función objetivo nos dará el valor correspondiente a la suma de los pesos de los caminos por los que pasamos, buscando minimizar esta última.
Por último debemos pensar en las restricciones que debemos imponer a nuestras variables de decisión para que la solución que obtengamos se corresponda con la del problema planteado:
Nuestro problema tiene un origen de donde sale una única arista, por ende hemos de restringir todos los caminos posibles por los que podemos pasar están a valor cero y solo pasaremos por uno, es decir, solo un \(x_{1j}\) toma el valor uno, de todos los posibles caminos que parten del origen.
Por otro lado, al destino llega una única arista, usando un razonamiento similar al del origen deducimos que solo un \(x_{in}\) toma el valor uno.
Asimismo,en el resto de nodos, si un camino llega a un nodo entonces debe existir un camino que salga del mismo evitando así la existencia de "nodos sin salida" o bucles, los cuales nos impedirían llegar a un destino.
Podemos ver a continuación lo expresado anteriormente en forma de restricciones:
- \(\mathbf{\sum_{j=1}^{n}x_{ij}=1}\) (sólo un camino puede empezar en el origen)
- \(\mathbf{\sum_{i=1}^{n}x_{in}=1}\)(solo uno para el destino)