a
b
c
d
x
y
z
AC
i
Randomize
Acerca de la calculadora del problema del viajante
Resuelva el problema del viajante en línea usando el método de ramificación y acotamiento con solución detallada paso a paso. con descripción completa y detallada paso a paso de las soluciones, que resuelve problemas de programación lineal de hasta 20×20 con coeficientes de tipo: números decimales y fracciones.
Para iniciar el cálculo, primero hay que introducir las dimensiones del problema en los campos de entrada en la parte superior de la pantalla y elegir la operación deseada en el menú lateral.
Un poco más abajo encontrará una ventana de entrada donde se deben ingresar los coeficientes, las restricciones y los valores del lado derecho usando el teclado. Aquí también se encuentra el panel de control de entrada, que simplifica el trabajo con los problemas de PL y contiene los siguientes elementos de control:
- El primer elemento permite expandir la ventana de entrada. Esto puede ser especialmente útil cuando la tabla no cabe completamente en la pantalla. Si la tabla aún no es totalmente visible después de expandir la ventana, puede cambiar la escala con los botones + / -;
- El segundo elemento copia los datos de entrada del problema actual al búfer de memoria. Esto puede ser útil cuando se resuelve con frecuencia el mismo problema de PL o se necesita transferir datos entre operaciones;
- Y el último elemento pega los datos de entrada copiados anteriormente, lo que permite restaurar los datos del problema en pocos clics en lugar de volver a ingresarlos manualmente;
Y más abajo encontrará una barra de herramientas que permite personalizar la calculadora y facilitar su uso. Está dividida visualmente en tres partes, cada una de las cuales se encarga de la siguiente funcionalidad:
- La primera parte permite seleccionar el formato numérico utilizado al mostrar el resultado de la solución. También puede desactivar los comentarios paso a paso si ya conoce el método y solo necesita verificar sus propios cálculos, u ocultar la solución paso a paso por completo si solo necesita la respuesta final;
- La segunda parte contiene botones que permiten modificar las dimensiones de la tabla de entrada, borrar coeficientes individuales o toda la entrada, y el botón principal con el signo igual que lleva a la pantalla de solución. Todos estos botones tienen atajos de teclado. Pase el cursor sobre un botón para ver la tecla correspondiente en un tooltip. También puede usar las teclas de flecha para mover el cursor entre los campos de entrada;
- Y la última parte permite elegir el número de dígitos después del punto decimal para redondear resultados no enteros. Una vista previa en tiempo real muestra cómo aparecerán los valores redondeados;
¿Qué es el problema del viajante?
El Problema del Viajante (TSP) es un clásico problema de optimización combinatoria NP-duro: dado un grafo completo ponderado de n ciudades, encontrar el ciclo hamiltoniano más corto — un recorrido cerrado que visita cada ciudad exactamente una vez y regresa a la ciudad inicial. El número total de recorridos posibles crece factorialmente con n, haciendo impractical la búsqueda exhaustiva incluso para tamaños moderados, por lo que se usan métodos exactos como la Ramificación y Acotamiento para podar el espacio de búsqueda.
¿Cómo resolver el problema del viajante con Ramificación y Acotamiento?
Comience reduciendo la matriz de costos: reste el mínimo de fila de cada fila y luego el mínimo de columna de cada columna; la suma de todas las reducciones es la cota inferior para el recorrido óptimo. En cada paso de ramificación, seleccione una arista de costo cero (i, j) para incluirla o excluirla. En la rama ACEPTAR, elimine la fila i y la columna j de la matriz, bloquee la arista inversa (j, i) con infinito para evitar sub-recorridos prematuros y reduzca de nuevo. En la rama RECHAZAR, establezca el costo (i, j) como infinito y reduzca. Compare las cotas inferiores de ambas ramas y explore primero la más prometedora. Continúe hasta identificar un ciclo hamiltoniano completo.
Ejemplo de resolución del problema del viajante con Ramificación y Acotamiento
Comenzamos a resolver el problema desde la etapa preliminar. Para ello, buscamos los valores mínimos en las filas de la matriz (los escribimos en la columna verde a la derecha de la matriz) y los restamos elemento a elemento, obteniendo una matriz intermedia. Luego, para la matriz resultante, buscamos los valores mínimos en las columnas (los escribimos en la fila azul debajo de la matriz).
Encontramos la suma de los valores mínimos en filas y columnas y asignamos el valor resultante a la variable acumuladora D
D = 18
Para la matriz intermedia, restamos elemento a elemento el valor mínimo de las columnas. Así, en cada fila y columna obtenemos al menos un cero. Para cada cero de la matriz, calculamos la suma de los valores mínimos en las filas y columnas donde se encuentran los ceros correspondientes, sin tener en cuenta los propios ceros. Los valores resultantes se escriben entre paréntesis.
Continuamos la solución respecto al cero con la mayor estimación calculada en la etapa anterior.
El índice bajo el que se encuentra ese cero indica una arista de ramificación.
Hay que comprobar si esta arista debe añadirse al camino común o no.
Comprobamos cuánto aumentará el costo de recorrer la ruta sin la arista de ramificación actual. La verificación se realiza sustituyendo el cero con la mayor estimación por M (infinito), tras lo cual se realiza la reducción de la matriz.
La matriz se reduce buscando en la matriz original los valores mínimos en cada fila y restándolos elemento a elemento de todos los elementos de la fila. En la matriz resultante, en cada columna se determina el valor mínimo y se resta elemento a elemento de todos los elementos de la columna.
Encontramos la suma de los valores mínimos en filas y columnas y determinamos así cuánto aumentará el costo de recorrer la ruta sin la arista de ramificación actual.
H(2*,1*) = 6
Comprobamos cuánto aumentará el costo de recorrer la ruta si añadimos la arista de ramificación actual al camino común. Y en base a estos datos, decidimos si añadir la arista de ramificación al camino común o si es más rentable elegir otro camino.
La verificación se realiza eliminando la i-ésima fila y la j-ésima columna de la matriz, donde i, j es el índice del elemento respecto al cual se toma la decisión.
En la matriz resultante, es necesario sustituir por M (infinito) el elemento bajo el índice inverso al del elemento respecto al cual se toma la decisión.
A continuación, buscamos los valores mínimos por filas y columnas de la matriz.
A continuación, para cada cero de la matriz, calculamos la suma de los valores mínimos en las filas y columnas donde se encuentran los ceros correspondientes, sin tener en cuenta los propios ceros.
Los valores resultantes se escriben entre paréntesis.
Encontramos la suma de los valores mínimos en filas y columnas y determinamos así el costo del trayecto por la arista de ramificación actual.
H(2,1) = 0
Dado que H(2,1) <= H(2*,1*), incluimos esta arista en el camino general.
Continuamos la solución respecto al cero con la mayor estimación calculada en la etapa anterior.
El índice bajo el que se encuentra ese cero indica una arista de ramificación.
Hay que comprobar si esta arista debe añadirse al camino común o no.
Comprobamos cuánto aumentará el costo de recorrer la ruta sin la arista de ramificación actual. La verificación se realiza sustituyendo el cero con la mayor estimación por M (infinito), tras lo cual se realiza la reducción de la matriz.
La matriz se reduce buscando en la matriz original los valores mínimos en cada fila y restándolos elemento a elemento de todos los elementos de la fila. En la matriz resultante, en cada columna se determina el valor mínimo y se resta elemento a elemento de todos los elementos de la columna.
Encontramos la suma de los valores mínimos en filas y columnas y determinamos así cuánto aumentará el costo de recorrer la ruta sin la arista de ramificación actual.
H(1*,4*) = 9
Comprobamos cuánto aumentará el costo de recorrer la ruta si añadimos la arista de ramificación actual al camino común. Y en base a estos datos, decidimos si añadir la arista de ramificación al camino común o si es más rentable elegir otro camino.
La verificación se realiza eliminando la i-ésima fila y la j-ésima columna de la matriz, donde i, j es el índice del elemento respecto al cual se toma la decisión.
En la matriz resultante, es necesario sustituir por M (infinito) el elemento bajo el índice inverso al del elemento respecto al cual se toma la decisión.
A continuación, buscamos los valores mínimos por filas y columnas de la matriz.
A continuación, para cada cero de la matriz, calculamos la suma de los valores mínimos en las filas y columnas donde se encuentran los ceros correspondientes, sin tener en cuenta los propios ceros.
Los valores resultantes se escriben entre paréntesis.
Encontramos la suma de los valores mínimos en filas y columnas y determinamos así el costo del trayecto por la arista de ramificación actual.
H(1,4) = 7
Dado que H(1,4) <= H(1*,4*), incluimos esta arista en el camino general.
Resultado:
El costo de toda la ruta:
D = 18 + 0 + 7 + 0 + 0 = 25
Ruta:
H(2,1) => H(1,4) => H(3,2) => H(4,3)
Preguntas frecuentes
¿Qué encuentra la calculadora del problema del viajante?
Encuentra la ruta más corta posible que visita cada ciudad exactamente una vez y regresa al punto de partida, dada una matriz de distancias o costes entre pares.
¿Cómo funciona aquí el método de ramificación y acotación?
Construye un árbol de búsqueda y calcula una cota inferior de la longitud del recorrido para cada rama reduciendo filas y columnas de la matriz de costes. Las ramas que no pueden mejorar el mejor recorrido encontrado hasta el momento se podan, lo que evita comprobar todas las permutaciones.
¿Por qué las celdas de la diagonal están marcadas con «M»?
La diagonal representa la distancia de una ciudad a sí misma, que nunca forma parte de un recorrido. Se le asigna un valor muy grande (M) para que el algoritmo nunca la seleccione.
¿La calculadora siempre devuelve el recorrido más corto exacto?
Sí. La ramificación y acotación es un método exacto: explora lo suficiente del árbol para garantizar el óptimo, omitiendo solo las ramas que demostrablemente no pueden mejorar el mejor recorrido conocido.