Ruta mas corta con Solver de Excel
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
🚦 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.
📏 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.
🔍 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.
🔧 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
💡Grafo dirigido
💡Modelo de transporte
💡Variables de decisión
💡Costos unitarios
💡Restricciones de oferta y demanda
💡Solver
💡Función objetivo
💡Nodos
💡Arcos
💡Excel
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.
Transcripts
estimadas y estimados vamos a ver la
solución de este problema de la ruta más
corta
tenemos que hallar la ruta más corta del
nodo número uno al nodo número 7
los arcos permitidos es un grafo
dirigido del nodo 1 al 3 hay dos niños
de distancia del nodo 1 al 2 hay una una
milla de distancia del nodo 2 al nodo 4
hay 5 millas de distancia y así
sucesivamente
cada fecha indica la ruta permitida con
los arcos permitidos por los cuales nos
podemos transportar y dicho esto vamos a
considerarlo un problema especial del
modelo de transporte
en el modelo de transporte buscamos
minimizar el costo de traslado de
ciertas mercancías de puntos de origen
al punto de destino en esta situación
hay un solo punto de origen y hay un
solo punto de destino es un caso
especial y los números que representan
la distancia ahora van a representar
los costos dentro del modelo de
transporte es decir este uno va a
representar ahora el costo de la ruta 12
porque vídeo
y lo vamos a llamarse 12 y representa el
costo por usar la ruta ángulos
entonces voy a colocar
y etiquetar cada una de las distancias
identificando las ahora con costos
dentro del modelo detrás
ya tenemos los parámetros de costo que
representan las distancias de cada una
de las rutas por cada ruta tenemos que
decidir si usar la ruta o no usarla
dentro del algoritmo de la distancia más
corta de la ruta más corta
va a tener en este caso una variable de
decisión en el caso de la ruta 12 va a
existir la variable de decisión x 12
y representa nuestra decisión si usar o
no esa ruta es decir en este caso x12
solo puede tomar valores de 0
el 1 significa que es parte de la ruta
más corta y el 0 es que no estamos
pasando por ahí considerándolo como la
ruta más corta
vamos a hacer lo mismo con el resto de
los arcos vamos a declarar las variables
de decisión para cada
muy bien ya tenemos la nomenclatura de
cada uno de los arcos ya tenemos
declaradas las variables de decisión
para cada caso
ahora vamos a utilizar una tabla que
representan los costos unitarios de
envío en el modelo de transporte en este
caso de la ruta más corta ya habíamos
dicho que los costos van a ser
representados por las distancias de cada
vamos a colocar los nodos de esta manera
el nodo 1
va a ofrecer solo un artículo y ese
artículo vamos a encontrar la ruta por
la cual va a transitar de forma tal que
se obtenga la distancia más corta
recorrida entonces el nodo 1
ofrece un artículo y puede ser enviado
al nodo número 23
el costo porque esta es una tabla de
costos el costo de envío del nodo 112 es
igual a 1 y eso lo vemos aquí se 12 es
igual a 1 el costo de envío del nodo 193
es igual a 2
ahora eso es lo que sale del nodo 1 y
llegan 2
ahora lo que sale del maduros solo puede
llegar al nuevo número 4 y el costo
unitario de envío de lo que mandemos del
nodo 2 al nuevo número 4 instalado con 5
que es el costo unitario de 24
ahora vamos con el nuevo número 3
el nuevo número 3 que está aquí
y envía hacia el nodo número 5 y el
número 6
el costo unitario de envío del nodo
número 3 125 es igual a 10 y eso lo
podemos ver aquí en ese presidente
y el costo unitario de envío del nodo 3
al nodo número 6 es igual a 2
ya superamos el nodo 3 vamos con el
número 4 salen dos flechas de nuevo
cuatro
sale al no 25 y el 26 entonces el costo
unitario de envío del nodo 4 al modo 5
es de 8
y del nodo 4 al número 6 es de 6
lo vemos aquí el nodo 4 al 5 846
terminamos con el nodo 4 vamos con el
nodo número 5
sólo hay una flecha que sale del nuevo 5
y llega al 12 7
el costo unitario de envío del nodo 507
es de 6
y ahora vamos con el nodo número 6 que
sólo tiene una salida número 7
qué es un costo unitario de los
esta es la tabla de los costos
sanitarios de envío
no se puede buscar de formatos
y todas las celdas que no se juzguen
para poder distinguir cuáles son las
gotas en nuestras permitidas en este
modelo vamos a colorear las
entonces esa es la tabla de los costos
unitarios de envío de hecho es
exactamente la misma
ustedes notaron que el costo por ejemplo
13 hay una variable x 13 el costo 12 hay
una variable es 12 esta tabla es
exactamente la misma no solo para costos
sino también para las variables de
decisión
todas las celdas que tienen color
blanquito son las celdas que van a
contener las diferentes variables
decisiones por ejemplo aquí va a
contenerse la variable edición 12
y 13 pero no las vamos a poner los vamos
a dejar así en blanco para que no
ya tenemos la tabla de los costos
unitarios del vídeo ya tenemos la tabla
de las variables de decisión necesitamos
elaborar la función o qué
y la función objetivo en este caso va a
buscar a minimizar
la distancia
total recorrida por un solo artículo se
ofrece un solo artículo en el nodo 1 y
el nodo número 7 demanda sólo un
artículo
y entonces
como minimizamos la función objetivo
bueno si decidimos usar la ruta 12
el costo por usar la ruta 12 es de una
milla tenemos que sumarle
la posibilidad de usar la ruta 13 el
costo de usar la ruta 13 son los miles y
así sucesivamente multiplicamos ya la
equis por ejemplo 24 órganos unitarios
24
y ya lo tenemos ahora vamos a probar la
función objetiva
si nosotros decidiéramos ir por la ruta
del nodo 1 al nodo tres estaríamos
recorriendo dos millas y la solución
sería colocar no no
ustedes den se cuenta que aquí en la
función objetivo recorrimos dos millas y
si decidiéramos irnos por ejemplo del
nuevo 3 al nodo 5
entonces a los 5 aquí estaríamos usando
esta ruta estaríamos recorriendo un
total de 2 semillas y si ya estamos en
el nodo 5 nos vamos al nodo 7 del 5 al 7
entonces del 5 al 7 estaríamos
llega nuestra decisión en total
estaríamos recorriendo 18 días
y las demás variables edición pues
quedarían en cero porque son rutas por
las cuales no está pasando el artículo
quedaría de esta manera
y obviamente este es un ejemplo de cómo
funciona la fórmula cómo quedaría la
solución
a continuación vamos a colocar las
restricciones ya tenemos los costos
unitarios ya tenemos las varillas misión
ya tenemos que ir a la función objetivo
el objetivo es minimizar la distancia
total vamos a colocar las restricciones
las restricciones pueden ser de oferta
de transbordo o del imán
vamos a empezar con las restricciones de
oferta
y vamos a empezar con el nodo número 1
vamos a colocar las n
en el nodo número 1
nosotros tenemos que salen dos flechitas
no sabemos todavía
porque ruta es la ruta más corta pero lo
que sí sabemos es que la suma de los
artículos que salgan de la ruta 13 más
los artículos que salgan de la ruta 12
va a ser igual a 1
no sabemos por dónde va a salir ese
artículo pero si sabemos que por alguna
de las dos rutas de salir
entonces
declaramos la función como x 12 +
13 es igual aunque esa es la forma
algebraica
y en excel vamos a colocar la suma de x
12 + x 13
debe ser igual
hago
vamos a colocarlo
esa es esa fue la única restricción de
oferta porque hay un solo punto que
ofrece el artículo ahora vamos a colocar
los modos de transbordo las
restricciones de los nuevos de
transporte
y vamos a empezar con el nodo número 2
el nodo número 2 recibe una flecha y
saldrá una flecha
no almacena nada entonces
recibe un artículo o sea lo que recibe
es lo que va a mandar si recibe un
artículo va a mandar un artículo si
recibe ser artículos va a mandar ser
artículos
entonces podemos expresar lo así
lo que entra es igual a lo que sale pero
como típicamente en programación lineal
las variables si se colocan del lado
izquierdo de la expresión si nosotros
pasamos este x 24 restando edad x 12
menos x 24 igual a 0
en otras palabras era positivo lo que se
recibe y que da negativo lo que sale de
nosotros
y es un nodo de transbordo porque es un
nuevo intermedio por donde puede pasar
el material en este caso
en excel no es el
valor de x del 1 al 2
debe restar al valor de x del 2 al 4
y esto debe ser igual a cero porque
porque no hay más segundo
ahora vamos con el nodo
el nodo número 3 recibe una flechita
y salden o 32 flechitas
entonces recibirá una flechita x 13 y se
le resta lo que sale del x 35 menos x 36
y eso debe ser igual a cero
tiene que ser como se pone pues la
cantidad que sale la cantidad que llega
del nodo 13 debes restarlo a lo que sale
del 3 al 5 menos del 36
y esto debe ser igual a cero
vamos con el nodo 4
el nodo 4 también recibe una flechita y
salen 2 flechitas la flechita que recibe
es la variable de decisión 24
y lo que sale es a 45
45
- x 46
y eso debe ser igual a cero
en excel es la variable 24
le restamos la variable 45 menos la
variable 46
y esto es igual a cero
vamos con el nodo número 5
el nodo 5 recibe dos flechitas recibe la
x 35 y el x 45 y sale solo una flechita
que es la x 57 entonces las flechitas
que reciben son positivas x 35 más la x
45 y se le resta la precisiones al menos
le x 57
sin almacenar nada lo que le llega es
igual algo que sale de ese nombre
entonces le llega la variable x 35 35
más y x 45 al nuevo número 5 y sale la x
57
y esto es igual a cero
16 recibe 2 flechitas
y seis más
46 y salve la x6 inc
y esto es igual a 6
ese nuevo 6 es el último de transbordo
y llega material del 36
más lo que llega del 4
debe ser este al menos lo que sale del
nodo 6 qué es
16 asiento de atrás guarda
el número 6
oferta transbordo y demanda
la demanda es el nodo número 17
y demanda un artículo
no sabemos si el artículo va a llegar
por la ruta x 67 o x 57
pero sabemos
la suma de los que le lleven ya sea por
la ruta 67 a 57 debe ser igual a 1
como se coloca esto en el excel
la suma de la variable de decisión 67 +
x 57
esa suma
del ser igual
muy bien ya lo tenemos siempre guarden
su trabajo
y ya lo tenemos ahora lo que hay que
hacer es abrir el solver
nos vamos a la pestaña de datos
vamos a resolver
y en el solver vamos a identificar la
celda que contiene la función objetivo
vamos a minimizar la distancia recorrida
cambiando las celdas y ustedes colocan
con el mouse presionen y usando la tecla
control
seleccione las otras ellas que están en
blanco que son las que están sujeto a
las restricciones y agreguen las
restricciones en este caso ya las
tenemos en forma de
de columna y el lado izquierdo debe ser
igual a lo que está delante
las aceptamos y aplicamos el simple ex
línea del programa y los resolvemos
solver encontrar una solución se cumplen
todas las restricciones y condiciones
óptimas le damos clic en aceptar y la
ruta más corta es la que va de el nodo 1
al 3
del nodo 3 al 6
y del nodo 6 al 7
esa es la ruta más corta
y nos da una distancia mínima de 8 años
espero que sirva espero que sea de
utilidad muchas gracias
Voir Plus de Vidéos Connexes
EL PROBLEMA DE LA RUTA MÁS CORTA (ALGORITMO DE DIJKSTRA) EJERCICIO RESUELTO
Modelos de Redes 01 Introducción
40 - Árboles Binarios de Búsqueda, Eliminar un Nodo, Implementación (EDDJava)
Árbol binario, borrar nodo - 27 - Estructuras de Datos en C#
Grafo implementado en Java
34 - Árboles Binarios de Búsqueda, Creación e Inserción (EDDJava)
5.0 / 5 (0 votes)