Diferencias

Muestra las diferencias entre dos versiones de la página.

--- problema_tsp [2012/04/20 08:14] – editor externo 127.0.0.1
+++ problema_tsp [2023/03/13 14:40] (actual) – editor externo 127.0.0.1
@@ Línea 10: / Línea 10: @@
 Además del reto computacional que representa este tipo de problemas, también es de los más interesantes de la teoría de grafos y de la investigación operativa por su aplicación práctica en la realidad. Su aplicación es visible y de gran importancia para la resolución de problemas reales en la Dirección de Operaciones y Logística. Por ejemplo: problemas de picking, de rutas, sistemas de navegación GPS, planificación de movimientos de robots, vehículos autoguiados (AGV), etc.
-Este problema es fácil de enunciar, aunque un poco más complicado de modelar y resolver. Se trata de un vendedor o viajante de comercio que debe visitar <tex>n</tex> ciudades para vender u ofertar sus productos. Cada par de ciudades puede estar comunicada o no, su distancia se define mediante <tex>c_{ij}</tex>. El problema es por tanto, decidir el recorrido que comenzando por una determinada ciudad pase por todas las demás una sola vez y vuelva finalmente a la primera, de manera que se minimice la distancia total recorrida.
+Este problema es fácil de enunciar, aunque un poco más complicado de modelar y resolver. Se trata de un vendedor o viajante de comercio que debe visitar $n$ ciudades para vender u ofertar sus productos. Cada par de ciudades puede estar comunicada o no, su distancia se define mediante $c_{ij}$. El problema es por tanto, decidir el recorrido que comenzando por una determinada ciudad pase por todas las demás una sola vez y vuelva finalmente a la primera, de manera que se minimice la distancia total recorrida.
-Sea <tex>x_{ij}</tex> una variable binaria que indica si el viajante utilizará el arco de la ciudad <tex>i</tex> a la <tex>j</tex> en su recorrido solución. Para el modelado matemático, la ciudad de comienzo es irrelevante. A continuación se muestra el modelo completo del problema. La función objetivo queda expresada como:
+Sea $x_{ij}$ una variable binaria que indica si el viajante utilizará el arco de la ciudad $i$ a la $j$ en su recorrido solución. Para el modelado matemático, la ciudad de comienzo es irrelevante. A continuación se muestra el modelo completo del problema. La función objetivo queda expresada como:
-<tex>  \displaystyle{\min \sum_{i=1}^n\sum_{j=1}^n {c_{ij} x_{ij}}}</tex>
+$$  \displaystyle{\min \sum_{i=1}^n\sum_{j=1}^n {c_{ij} x_{ij}}}$$
 y está sujeto a las restricciones:
-<tex>  \displaystyle{\sum_{i=1}^n {x_{ij}} =1 \quad  \forall {j=1 \ldots n}} </tex>
+$$  \displaystyle{\sum_{i=1}^n {x_{ij}} =1 \quad  \forall {j=1 \ldots n}} $$
-<tex>  \displaystyle{\sum_{j=1}^n {x_{ij}} =1 \quad  \forall {i=1 \ldots n}} </tex>
+$$  \displaystyle{\sum_{j=1}^n {x_{ij}} =1 \quad  \forall {i=1 \ldots n}} $$
-<tex>  \displaystyle{x_{ij} \in (0,1)}</tex>
+$$  \displaystyle{x_{ij} \in (0,1)}$$
 y con las condiciones de Miller-Tucker adicionales:
-<tex>  \displaystyle{u_i - u_j + n \cdot x_{ij} \leq n-1 \quad 2 \leq i \neq j \leq n}</tex>
+$$  \displaystyle{u_i - u_j + n \cdot x_{ij} \leq n-1 \quad 2 \leq i \neq j \leq n}$$
 Analizando las restricciones, se puede observar que sólo debe haber un arco de llegada a una ciudad o nodo, y que igualmente tan sólo debe haber un arco de salida. Con esto se garantiza que cada ciudad es visitada sólo una única vez.
-Sin embargo, con estas restricciones y la condición binaria de las variables <tex>x_{ij}</tex>, no es suficiente para garantizar que las soluciones factibles son recorridos. Es posible por tanto, que aparezca una solución formada por subrutas (no conectadas entre sí) y que cumplan las restricciones anteriormente comentadas.
+Sin embargo, con estas restricciones y la condición binaria de las variables $x_{ij}$, no es suficiente para garantizar que las soluciones factibles son recorridos. Es posible por tanto, que aparezca una solución formada por subrutas (no conectadas entre sí) y que cumplan las restricciones anteriormente comentadas.
-Es por ello, por lo que es necesario añadir más restricciones que eviten la formación de subrutas. Una de las posibles formas de hacer esto (ya que existen varias), es la propuesta por Miller-Tucker y que se muestra en el modelo. Las variables de decisión introducidas por las condiciones de Miller-Tucker son reales y no tienen límites ni superior ni inferior. La propuesta de Tucker genera <tex>n^2</tex> restricciones, mientras que otras en la literatura pueden llegar a generar <tex>2^n</tex>. Sin embargo, desde un punto de vista computacional, este modelo aunque más compacto es menos eficiente.
+Es por ello, por lo que es necesario añadir más restricciones que eviten la formación de subrutas. Una de las posibles formas de hacer esto (ya que existen varias), es la propuesta por Miller-Tucker y que se muestra en el modelo. Las variables de decisión introducidas por las condiciones de Miller-Tucker son reales y no tienen límites ni superior ni inferior. La propuesta de Tucker genera $n^2$ restricciones, mientras que otras en la literatura pueden llegar a generar $2^n$. Sin embargo, desde un punto de vista computacional, este modelo aunque más compacto es menos eficiente.
 En el caso de Grafos, este problema se aborda a través del modelo anteriormente expuesto y su resolución mediante Programación Lineal Entera Mixta.
@@ Línea 51: / Línea 51: @@
 ----
 ~~NOTOC~~