P. Agente Viajero

Introducción

El problema del Agente viajero es uno de los planteamientos que hemos visto a lo largo de todo el semestre. Se caracteriza por tratar de seguir un cierto camino, tratando de recorrer todas las ciudades o lugares posibles, con el menor costo en distancia recorrida.

Este tipo de problema puede resolverse con unos cuantos métodos vistos en la clase, pero lo que nos interesa en este caso es trabajarlo con el método de Ramificación y Acotamiento para modelos Binarios, mientras nos apoyamos del método Húngaro, ya que este último nos permite asignare una valor a las variables mientras con el método de Ramificación y Acotamiento nos permite analizar su factibilidad.

Problema

Un vendedor de libros que vive en Basin debe visitar una vez al mes a cuatro clientes, ubicados en Wald, Bon, MENA y Kiln. La siguiente tabla proporciona las distancias en millas entre las diferentes ciudades:

El objetivo es minimizar la distancia total que recorre el vendedor.

Planteamiento

Xij={1 si viaja de la ciudad i a la ciudad j, 0 si no hace ese viaje}

min Z = 120X12 + 220X13 + 150 X14 + ... + 185X543 + 190X54

s.a.

X12 + X13 + ... + X15 = 1

X21+ X23 + ... + X25 = 1

X31 + X32 + ... + X35 = 1

X41 + X42 + ... + X45 = 1

X51 + X52 + ... + X54 = 1

X21 + X31 + ... + X51 = 1

X12+ X32 + ... + X62 = 1

X13 + X23 + ... + X53 = 1

X14 + X24 + ... + X54 = 1

X15 + X25 + ... + X45 = 1

Xi {0,1} Xi>=0

Planteamiento explicado

min Z = 120X12 + 220X13 + 150 X14 + ... + 185X543 + 190X54 Esta función es la que busca que se minimice el costo del viaje que se vaya a hacer entre las ciudades.

Por su parte, las restricciones, son las que nos dicen que está, o no, permitido hacer. Nos guían hacia la solución si es que todas se cumplen. En este caso como todas las variables son binarias solo es posible que una tenga valor de 1 en cada función propuesta.

Resolución del modelo

Primero se forma una matriz que queda de la siguiente forma:

Se aplica el método húngaro y nos da como solución la siguiente:

X14 = X23 = X35 = X41 = X51 = 1

Z = 695

Pero esta solución crea un circuito no hamiltoniano, por lo tanto no es una solución factible. Y es aquí donde entra el método de ramificación y Acotamiento.

En la matriz original sustituyen los valores a 0 según a la variable a la que hayamos otorgado dicho valor. Y continuamos aplicando el método húngaro.

Siguiendo una de las partes nos queda de esa forma:

Y siguiendo la otra nos queda de la siguiente:

Y nos damos cuenta que en ambos sacos hay una solución en la que se forma un circuito hamiltoniano, por lo tanto nos da la solución al problema con un costo de 725.

Este resultado nos dice que el vendedor tendrá que salir de su ciudad natal hacia Mena, de ahí a Wald, después a Bon y antes de regresar a su ciudad pasará por Kiln.

Google Sites

Report abuse