Laboratorio 10 - Modelo del Vendedor Viajero.
Enviado por xavi_muse • 25 de Octubre de 2016 • Resumen • 965 Palabras (4 Páginas) • 523 Visitas
[pic 1][pic 2]
Modelo del Vendedor Viajero
[pic 3]
I
OBJETIVOS
- Conocer y aplicar el concepto del algoritmo del agente viajero.
- Utilizar el Lindo, WinQsb o PomQm como herramientas de software para encontrar una solución.
- Interactuar con los modelos.
II[pic 4]
TEMAS A TRATAR
- Algoritmo del Agente viajero.
- Modelamiento de problemas.
[pic 5]
III
[pic 6]
MARCO TEORICO
Modelo del flujo máximo
[pic 7]
Modelo Matemático para el problema del Agente Viajero:
max F
st
Origen) XOA + XOB - F = 0
A) XOA - ZAD - XAC = 0
B) XOB + XCB - XBE = 0
C) XAC -XCB - XCE - XCF = 0
D) XAD - XDT = 0
E) XBE + XCE - XEF - XET = 0
F) XCF + XEF - XFT = 0
Destino) XDT + XFT + XET - F = 0
XOA <= 8
XOB <= 5
XAD <= 5
XAC <= 4
XCB <= 3
XBE <= 4
XCF <= 2
XCE <= 2
XDT <= 6
XEF <= 3
XET <= 6
XFT <= 4
end
Modelo del Agente Viajero
Dada la siguiente Red:
[pic 8]
Modelo del Agente Viajero: Si la Red mostrada arriba representa alternativas de visita del alcalde de Seatle a todas las demás ciudades, pasando por cada una de ellas por una sola vez y los datos de los arcos representan distancias de recorrido en kilómetros ¿Cuál debería ser la trayectoria de desplazamiento, suponiendo que se considera como alternativa de traslado el tramo 2 a 6 ó 6 a 2 con 700 kms. de distancia? ¿Cuál es la distancia total recorrida?
Uso del WinWsb:
Utilizando la opción Network Modeling eligiendo el tipo de problema Problema del agente viajero (Traveling Salesman Problem).
[pic 9]
Ingresamos los datos de las distancias entre pares de nodos (la distancia de i a j es la misma que de j a i), agregamos también la distancia de 700 kms. entre los nodos 2 y 6, y 6-2 pedimos la solución del problema eligiendo el Método de Ramificación y Acotamiento (Branch and Bound Method).
[pic 10]
Obtenemos la siguiente solución:
[pic 11]
La trayectoria de desplazamiento es la mostrada en la gráfica siguiente:
[pic 12]
La distancia total recorrida es 6024 Kms.
Modelo Matemático para el problema del Agente Viajero:
Para formular el modelo matemático, en vista de que todos los arcos tienen la misma distancia del nodo i al nodo j que del nodo j al nodo i, podemos utilizar una sola variable por cada arco de la red a efectos de simplificación:
Min 599x12+180x13+497x14+700x26+420x27+691x28+432x34+200x35+345x47+138x56+291x510+
526x67+440x78+432x711+621x712+102x89+452x912+280x1011+114x1013+155x1114+108x1115+
140x1116+469x1215+180x1219+120x1314+386x1316+118x1317+207x1415+403x1619+425x1718+
314x1819
St
x12+x13+x14=2
x12+ x26+x27+x28 =2
x13+x34+x35=2
x14+x34+x47=2
x35+x56+x510=2
x26+X56+x67=2
x27+x47+x67+x78=2
x28+x78+x89=2
x89+x912=2
x510+x1011+x1013=2
x711+x1011+x1114+x1115+x1116=2
x712+x912+x1215+x1219=2
x1013+x1314+x1316+x1317=2
x1114+x1314+x1415=2
x1115+x1215+x1415=2
x1116+x1316+x1619=2
x1317+x1718=2
x1718+x1819=2
x1219+x1619+x1819=2
End
Int 30
Donde Xij=1, si el arco ij es considerado en la trayectoria; =0, en caso contrario.
La solución utilizando el Lindo 6.0 es:
[pic 13]
Esta solución nos da 2 trayectorias de desplazamiento:
...