Diferencias
Muestra las diferencias entre dos versiones de la página.
Ambos lados, revisión anteriorRevisión previaPróxima revisión | Revisión previa | ||
problema_tsp [2010/10/21 10:27] – admin | 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. | 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 | + | 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 |
- | Sea <tex>x_{ij}</ | + | Sea $x_{ij}$ una variable binaria que indica si el viajante utilizará el arco de la ciudad |
- | < | + | $$ |
y está sujeto a las restricciones: | y está sujeto a las restricciones: | ||
- | < | + | $$ |
- | < | + | $$ |
- | < | + | $$ |
y con las condiciones de Miller-Tucker adicionales: | y con las condiciones de Miller-Tucker adicionales: | ||
- | < | + | $$ |
Analizando las restricciones, | Analizando las restricciones, | ||
- | Sin embargo, con estas restricciones y la condición binaria de las variables | + | Sin embargo, con estas restricciones y la condición binaria de las variables |
- | 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 | + | 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 |
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. | 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~~ | ~~NOTOC~~ | ||
- | |||