FLUJO MÁXIMO Y AGENTE VIAJERO

Origen

Se atribuye a Flood

Definición

Conocemos como ciclo Hamiltoniano

Objetivo

Minimizar el recorrido

Tipos

PAV simetrico

El costo de ir a i a j es el mismo que de ir de j a i

PAV asimétrico

El punto i a un punto j no es necesariamente el mismo viajar del punto j al punto i

Catracterísticas

Las variables más empleadas por investigadores

Tiempo de recorrido

Distancia

Costos

Que se puede adoptar

Circuitos electrónicos

Control de semáforos

Previsión del tránsito

Entrega de productos

Estaciones de trabajo

Edificaciones

Métodos

Método de la fuerza bruta

No implica la aplicación de ningún algoritmo sistemático, tan solo consiste en explorar todos los recorridos posibles

Métodolo del vecino más cercano

Es un algoritmo heurístico diseñado para solucionar el problema del agente viajero, no asegura una solución óptima, sin embargo, suele proporcionar buenas soluciones y tinen un tiempo de cálculo muy eficiente

Algoritmo del agente viajero exacto

El de ramificación y acotamiento

Llamado trambien Branch and Bound

Es un algoritmo diseñado para la resolución de modelos de programación entera

El del plano de corte

Fue introducido por Gomory

Es un procedimiento para encontrar soluciones enteras de un problemea lineal

Metaheurística

La metaheurística se encuentra dentro de la heurística

HEURÍSTICA

Encuentra soluciones aproximadas de problemas combinatorios difíciles

HEURÍSTICA CODICIOSA

"Miopes"

En su mayoría no encuentran la solución optima globalmente

características

Métodos diseñados para resolver problemas de optimización combinatoria

termina cuando se llega a un optimo local

Busca escapar de un optimo local

para problemas complejos de secuenciación

Las 3 Metaheurísticas que se aplican al TSP

1. ALGORITMO DE BÚSQUEDA TABÚ

Escapa de quedar atrapada en un óptimo local

Lista tabú

2. ALGORITMO DE RECOCIDO SIMULADO (RS)

Los resultados obtenidos mejoran la calidad de las soluciones reportadas por otros métodos .

3. ALGORITMO GENÉTICO (AG)

Fue John Holland

Son llamados así porque se inspiran en la evolución biológica.

cruzar su información y crear nuevas soluciones.

Definición

Es la representación gráfica de un proceso, serie
de actividades interconectadas o la distribución de puntos geográficos específicos

Terminología

Árbol

Grafo

Serie de puntos llamados grafos

Nodo

Representado por un círculo
unido por arcos o ramas

Red

conjunto de puntos y conjunto de
líneas que unen ciertos pares de puntos

Ciclo

Es una trayectoria que
inicia y termina en un mismo nodo.

Flujo

Asociado a cada red, por donde se dirige

Ruta

Conjunto de arcos que unen dos
nodos distitos

Métodos

FORD – FULKERSON

Propone buscar caminos con el fin de
ir aumentando el flujo hasta llegar al
máximo, busca saturar los arcos

EDMONDS KARP

a trayectoria de aumento encontrar es la más corta entre la fuente y el destino, es decir, la trayectoria que tenga menor número de arcos

CPM Y PERT

Preparan el plan mediante la representación gráfica de todas las operaciones que intervienen en el en una actividad.

Definición:

Consiste en determinar la máxima cantidad de flujo que puede ser enviada a lo largo de una red dirigida

con una capacidad por unidad de tiempo asociada a cada una de ellas.

Partiendo desde un nodo origen hasta un nodo destino.

Elementos que forman una red

Nodo:

Es una representación de un elemento del problema.

Arista:

Es un par de nodos, de la forma que representa un enlace entre ellos.

Existen dos tipos de arista:

Arista dirigida:

Es un par ordenado de nodos con un sentido definido.

Arista no dirigida:

Es un par no ordenado de nodos sin un sentido definido

Red:

Es un par (N, E) en un conjunto X, donde N es un conjunto no vacío de puntos de X y E es un subconjunto de aristas

Red no dirigida:

Es una red cuyo subconjunto E está formado por aristas no dirigidas.

Red dirigida:

Es una red cuyo subconjunto de aristas E está formado por aristas dirigidas.

Camino:

Es una sucesión de al menos dos nodos, tal que para cada uno de sus nodos existe una arista que contiene a dicho nodo y al nodo sucesor.

objetivo

Determinar la cantidad máxima de flujo

Para el flujo máximo la idea es encontrar una ruta de penetración con un flujo positivo neto que una los nodos de origen y destinos

El algoritmo del problema del agente viajero se utiliza más que todo para acortar las distancias que haya entre ciudades,por lugares a los cuales se debe llegar por medio de un transporte, pero que este mismo viaje dbe requerir la mínima cantidad de dinero gastado posible