Modelos De Transporte VMC Floyd Dikstra H Ngaro FM

Método del Vecino más Cercano
Se basa en el principio de seleccionar secuencialmente un eslabón restante que sea más barato, de modo que su inclusión no complete demasiado pronto el circuito.
Paso 1: Localizar el menor elemento de la matriz de costos y encerrar éste en un círculo para incluirlo como parte del eslabón correspondiente al itinerario. Los empates se deciden arbitrariamente.
Paso2: Si el elemento que acabas de encerrar con el círculo es Cpq, remplaza todos los elementos de la p-ésima fila, de la q-ésima columna y el elemento transpuesto, por un número M, prohibitivamente grande.
Paso 3: Prueba si la elección de este último costo no atenta dejando un itinerario no factible; si corta el itinerario pasa al paso 4; sino, continúa al paso 5.
Paso 4: Si el itinerarioresultante no es factible, elimina el último eslabón del itinerario vuelve a colocar los números en el lugar que estaban antes del último reemplazo por M y busca tentativamente el siguiente menor costo y vuelve al paso 3.
Paso 5: Determina si el itinerario está completo. De ser así, acepta éste como itinerario cercano al óptimo; si no lo es, continúa busca el siguiente menor costo y continúa con elpaso 2.

Ejemplo:
Supongamos que un furgón repartidor tiene que entregar mercadería en 4 locales comerciales y luego volver a la fábrica, pasando sólo una vez por cada local. Encontrar la ruta más económica asumiendo que los costos en kilómetros quedan determinados en los arcos del grafo.







Si se representa el esquema anterior como un grafo en el cual sus nodos representan la fábrica ylos locales dónde hay que realizar las entregas, el problema consiste en encontrar la ruta más económica para hacer el recorrido completo y volver a la fábrica (F), la matriz de el algoritmo se aplica cómo :




Paso 1: Se localiza el menor elemento de la matriz de costos y se encierra éste en un círculo para incluirlo como parte del eslabón correspondiente al itinerario. Los empates seresuelven arbitrariamente.




Paso 2: Si el elemento que acabas de encerrar con el círculo es Cpq, remplaza todos los elementos de la p-ésima fila, de la q-ésima columna y el elemento transpuesto, por un número M, prohibitivamente grande.



Paso 3: Prueba si la elección de este último costo no atenta dejando un itinerario no factible; si corta el itinerario pasa al paso 4; sino, continúa al paso5.
De las filas restantes, ninguna se cierra sólo con “M” y “x”, lo que indica que existe posibilidad de incluir un nuevo eslabón. Es decir, se puede continuar al paso 5.
Paso 5: Determina si el itinerario está completo. De ser así, acepta éste como itinerario cercano al óptimo; si no lo es, continúa busca el siguiente menor costo y continúa con el paso 2.




Cómo el itinerario no estácompleto, entonces se continúa en el paso 2:
Paso 2: Si el elemento que acabas de encerrar con el círculo es Cpq, remplaza todos los elementos de la p-ésima fila, de la q-ésima columna y el elemento transpuesto, por un número M, prohibitivamente grande.




Paso 3: Prueba si la elección de este último costo no atenta dejando un itinerario no factible; si corta el itinerario pasa al paso 4; sino,continúa al paso 5.
Aún quedan itinerarios factibles ya que ninguna de las filas restantes tiene sólo “M” y “x”, entonces buscamos el siguiente menor costo:




Paso 4: Si el itinerario resultante no es factible, elimina el último eslabón del itinerario vuelve a colocar los números en el lugar que estaban antes del último reemplazo por “M” y busca tentativamente el siguiente menor costo yvuelve al paso 3.
En este caso es factible ya que aún quedan filas completas sin que todos sus componentes sean “M” y “x”, entonces pasamos al paso 5.
Paso 5: Determina si el itinerario está completo. De ser así, acepta éste como itinerario cercano al óptimo; si no lo es, continúa busca el siguiente menor costo y continúa con el paso 2.
Aún no está completo el itinerario ya que tenemos 3...