Laboratorio 10 - Modelo del Vendedor Viajero.

[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:

...