Ruta mas corta con Solver de Excel

Marcel Ruiz :)

17 Mar 202119:18

Summary

TLDREl script describe un problema de optimización de rutas en un grafo dirigido, donde se busca la ruta más corta desde el nodo 1 hasta el nodo 7. Se presenta como un caso especial del modelo de transporte, donde los costos son representados por las distancias entre los nodos. Se definen variables de decisión para cada arco del grafo, que toman valores 0 o 1 dependiendo de si la ruta es parte de la ruta más corta. Se establecen restricciones de oferta y transbordo para cada nodo, asegurando que la cantidad de artículos que entran y salen de cada nodo cumplan con las condiciones del problema. Finalmente, se utiliza el Solver de Excel para encontrar la solución óptima, que resulta en una ruta de 8 unidades de distancia total, pasando por los nodos 1, 3, 6 y 7.

Takeaways

📐 Se busca encontrar la ruta más corta en un grafo dirigido desde el nodo 1 al nodo 7.
🛤️ Los arcos representan rutas permitidas y las distancias se convierten en costos dentro del modelo de transporte.
🔢 Las variables de decisión (x_ij) toman valores 0 o 1, indicando si se utiliza una ruta o no.
💡 Las distancias se etiquetan como costos y se asignan a las variables de decisión correspondientes.
📋 Se utiliza una tabla para representar los costos unitarios de envío, que son en realidad las distancias entre los nodos.
🔑 Se establecen restricciones de oferta y transbordo para asegurar que el flujo de mercancías se comporte de manera lógica en el grafo.
🔍 Se aplican las restricciones en Excel, utilizando sumas y restas de variables de decisión para representar el flujo entre los nodos.
📉 La función objetivo es minimizar la distancia total recorrida por un solo artículo desde el nodo 1 hasta el nodo 7.
🚫 Solo se permite un artículo salir del nodo de origen y solo se requiere un artículo en el nodo de destino.
🔄 Se aplican restricciones de transbordo para que el material no se almacene en los nodos intermedios.
🔑 Se utiliza el Solver de Excel para encontrar la solución óptima que minimiza la función objetivo sujeta a las restricciones.
🏁 La solución final indica que la ruta más corta es desde el nodo 1 a 3, luego de 3 a 6, y finalmente de 6 a 7, con una distancia mínima de 8.

Q & A

¿Cuál es el problema que se busca resolver en el script?
-El problema es encontrar la ruta más corta desde el nodo número uno hasta el nodo número 7 en un grafo dirigido.
¿Cómo se representan las distancias en el modelo de transporte mencionado?
-Las distancias se representan como costos dentro del modelo de transporte, donde cada número indica el costo de una ruta específica.
¿Cuál es el propósito de las variables de decisión en este contexto?
-Las variables de decisión, como x12, representan la elección de si se utiliza o no una ruta específica, pudiendo tomar valores de 0 (no se utiliza) o 1 (es parte de la ruta más corta).
¿Cómo se utiliza la tabla de costos unitarios de envío en el modelo de transporte?
-La tabla de costos unitarios de envío se utiliza para minimizar el costo total de enviar un artículo desde un nodo de origen hasta un nodo de destino a través de las rutas permitidas.
¿Qué restricciones se deben considerar al modelar este problema?
-Se deben considerar restricciones de oferta, que aseguran que un artículo salga del nodo de origen; y restricciones de transbordo, que garantizan que en cada nodo intermedio, la cantidad de artículos que llegan sea igual a la cantidad que sale.
¿Cómo se determina la función objetivo en el modelo de transporte?
-La función objetivo es minimizar la distancia total recorrida por un solo artículo desde el nodo 1 hasta el nodo 7, considerando las distancias como costos.
¿Qué herramienta se utiliza para resolver el modelo de transporte en este ejemplo?
-Se utiliza el Solver de Excel para encontrar la solución óptima que minimiza la distancia recorrida y cumple con todas las restricciones.
¿Cuál es la ruta más corta encontrada en el ejemplo?
-La ruta más corta es desde el nodo 1 al nodo 3, luego del nodo 3 al nodo 6, y finalmente del nodo 6 al nodo 7, con una distancia mínima total de 8.
¿Cómo se aplican las restricciones de oferta y transbordo en Excel?
-Se establecen restricciones de oferta asegurando que la suma de las variables de decisión de las rutas salientes del nodo de origen sea igual a 1. Las restricciones de transbordo se aplican asegurando que en cada nodo intermedio, la suma de las variables de decisión de las rutas entrantes menos las de las rutas salientes sea igual a 0.
¿Qué significa el valor 1 en el contexto de las restricciones de oferta y demanda?
-El valor 1 indica que hay un solo artículo que se ofrece en el nodo de origen y que la demanda en el nodo de destino es también por un solo artículo.
¿Cómo se interpreta el resultado final de la solución del Solver en el contexto del problema?
-El resultado final muestra la ruta más corta y el mínimo costo (distancia) que se debe recorrer para transportar el artículo del nodo de origen al nodo de destino.
¿Qué sucede si se desea optimizar un modelo de transporte con múltiples puntos de origen y destino?
-El modelo se vuelve más complejo y requiere la consideración de múltiples variables de decisión y restricciones para garantizar que la oferta y la demanda se cumplan en todos los puntos de origen y destino.

Outlines

00:00

🚦 Introducción al problema de la ruta más corta

Este primer párrafo introduce el problema de encontrar la ruta más corta en un grafo dirigido desde el nodo 1 al nodo 7. Se menciona que los arcos representan diferentes rutas con costos asociados en términos de distancia. El problema se enmarca en el modelo de transporte, donde se busca minimizar el costo de traslado de mercancías de un punto de origen al punto de destino. Las distancias se transforman en costos y se introducen variables de decisión (x12, x13, etc.) para cada ruta, las cuales tomarán valores 0 o 1 dependiendo de si la ruta es parte de la ruta más corta o no.

05:03

📏 Costos unitarios y variables de decisión

El segundo párrafo se enfoca en los costos unitarios de envío, que en este contexto son equivalentes a las distancias entre los nodos. Se describe cómo se representan en una tabla y cómo se relacionan con las variables de decisión. Cada celda de la tabla de costos tiene una variable de decisión asociada (x13, x12, etc.), y se destaca que las celdas sin color representan las variables de decisión que aún no han sido definidas.

10:07

🔍 Función objetivo y restricciones

Este párrafo describe la construcción de la función objetivo, que busca minimizar la distancia total recorrida por un solo artículo desde el nodo 1 hasta el nodo 7. Se detalla cómo se calcula el costo total utilizando las variables de decisión y los costos unitarios. Además, se introducen las restricciones del problema, que incluyen las de oferta, transbordo y demanda. Se menciona que se utilizará el Solver de Excel para encontrar la solución que cumpla con todas estas restricciones.

15:08

🔧 Aplicación del Solver y obtención de la solución

El último párrafo explica cómo se utiliza el Solver en Excel para resolver el problema. Se indica que la función objetivo es minimizar la distancia recorrida y se describen las restricciones que deben cumplirse. Finalmente, se obtiene la ruta más corta que va desde el nodo 1 al 3, luego al 6 y finalmente al 7, con una distancia mínima de 8 unidades.

Mindmap

Keywords

💡Ruta más corta

La 'Ruta más corta' es un concepto central en el video, que se refiere a la secuencia de puntos (nodos) en un grafo que permite viajar de un punto a otro de manera más eficiente en términos de distancia o costo. En el video, se busca encontrar la ruta más corta desde el nodo 1 hasta el nodo 7, representando los costos en términos de distancias recorridas.

💡Grafo dirigido

Un 'Grafo dirigido' es una estructura matemática que consiste en un conjunto de nodos y arcos, donde los arcos tienen una dirección específica, indicando que el movimiento es de un nodo a otro, pero no necesariamente en el sentido inverso. En el contexto del video, el grafo dirigido representa las diferentes rutas que se pueden tomar para encontrar la ruta más corta.

💡Modelo de transporte

El 'Modelo de transporte' es una técnica utilizada en la optimización de la logística y el transporte de mercancías. En el video, aunque se habla de la ruta más corta, se hace una analogía con el modelo de transporte, donde los costos son representados por las distancias de las rutas, y se busca minimizar el costo total de traslado.

💡Variables de decisión

Las 'Variables de decisión' son símbolos matemáticos que representan las opciones que tomar en un problema de optimización. En el video, las variables de decisión están relacionadas con la elección de las rutas (arcos) que componen la ruta más corta, y pueden tomar valores de 0 o 1, indicando si una ruta es o no parte de la solución.

💡Costos unitarios

Los 'Costos unitarios' son los costos asociados con enviar un artículo de un nodo a otro en el contexto del modelo de transporte. En el video, estos costos están representados por las distancias de las rutas, y son claves para construir la función objetivo que se desea minimizar.

💡Restricciones de oferta y demanda

Las 'Restricciones de oferta y demanda' son condiciones que aseguran que la cantidad de artículos ofrecidos en un nodo coincida con la cantidad demandada en otro. En el video, estas restricciones son fundamentales para que el solver pueda encontrar una solución viable al problema de la ruta más corta.

💡Solver

El 'Solver' es una herramienta en programas de planificación y análisis como Excel, que se utiliza para resolver problemas de optimización. En el video, el Solver es el instrumento que se emplea para encontrar la ruta más corta, tomando en cuenta la función objetivo y las restricciones establecidas.

💡Función objetivo

La 'Función objetivo' es una expresión matemática que se define para maximizar o minimizar en un problema de optimización. En el video, la función objetivo es minimizar la distancia total recorrida por un solo artículo desde el nodo 1 hasta el nodo 7.

💡Nodos

Los 'Nodos' son los puntos de conexión en un grafo, representando las ubicaciones a través de las cuales se puede viajar. En el video, los nodos son los puntos de partida y llegada para la ruta más corta que se está analizando.

💡Arcos

Los 'Arcos' son las conexiones directas entre los nodos en un grafo dirigido, que representan las rutas que se pueden tomar. En el video, los arcos están asociados con costos (distancias) y son las opciones que se evalúan para construir la ruta más corta.

💡Excel

Excel es una hoja de cálculo electrónica y una herramienta de análisis de datos ampliamente utilizada. En el video, se utiliza para modelar y resolver el problema de la ruta más corta, empleando las herramientas de Solver y las funciones de programación lineal.

Highlights

Se presenta un problema de encontrar la ruta más corta del nodo 1 al nodo 7 en un grafo dirigido.

Los arcos permitidos y las distancias entre los nodos son fundamentales para la solución del problema.

Se transforma el problema en un modelo de transporte, donde las distancias se convierten en costos.

Para cada ruta, se define una variable de decisión (x_ij) que indica si se utiliza o no esa ruta.

Las variables de decisión solo pueden tomar valores 0 (no se utiliza la ruta) o 1 (es parte de la ruta más corta).

Se utiliza una tabla para representar los costos unitarios de envío, que corresponden a las distancias entre los nodos.

Se establecen las restricciones de oferta y transbordo para asegurar el flujo adecuado de material entre los nodos.

La restricción de oferta garantiza que un artículo salga del nodo de origen (nodo 1).

Las restricciones de transbordo aseguran que en cada nodo intermedio, lo que entra es igual a lo que sale.

La demanda en el nodo de destino (nodo 7) es de un artículo, lo que se cumple con la suma de las variables de decisión de entrada.

Se utiliza la función objetivo para minimizar la distancia total recorrida por un solo artículo desde el nodo 1 hasta el nodo 7.

Se emplea el Solver de Excel para encontrar la solución óptima que cumpla con todas las restricciones.

La solución óptima indica la ruta más corta y los costos asociados a través de la tabla de costos unitarios.

La ruta más corta encontrada por el Solver es el nodo 1 al 3, del 3 al 6, y del 6 al 7.

La distancia mínima obtenida es de 8 unidades, representando el costo o distancia total recorrida.

El proceso demuestra cómo aplicar el modelo de transporte en problemas de optimización de rutas.

El uso de variables de decisión y restricciones permite modelar eficazmente el problema y encontrar la solución más corta.

La transformación de un problema de ruta más corta en un modelo de transporte es una técnica innovadora para optimización de costos.