Optimizacion De Redes (ensayo)

OPTIMIZACIÓN EN REDES

• EN ALGUNOS PROBLEMAS DE OPTIMIZACIÓN PUEDE SER ÚTIL REPRESENTAR EL PROBLEMA A TRAVÉS DE UNA GRÁFICA: ruteo de vehículos, distribución de producto, programa de actividades en un proyecto, redes de comunicación, etc.

• MODELOS DE REDES: algoritmos especiales

GRÁFICA

• ES UN CONJUNTO DE NODOS (N) Y ARCOS (A) QUE CONECTAN LOS NODOS. NOTAMOS G=(N,A)

• LOS NODOS SE NUMERAN : 1,2,...,n

• LOS ARCOS SE DENOTAN (i,j) indicando que une el nodo i al nodo j

CONCEPTOS BÁSICOS

• Un arco (i,j) es dirigido si conecta i con j pero no j con i.

• Una gráfica G=(N,A) es dirigida si sus arcos están dirigidos. En una gráfica no dirigida (i,j) y (j,i) representan el mismo arco ( no dirigido).

CONCEPTOS BÁSICOS

Gráfica no dirigida

CONCEPTOS BÁSICOS

• Un Camino o Ruta del nodo i al nodo j es una secuencia de arcos que unen el nodo i con el nodo j: (i,i1), (i1,i2), (i2,i3),...,(ik,j). Ruta de k arcos.

• Un Ciclo es un camino que une un nodo consigo mismo:(i,i1), (i1,i2), (i2,i3),...,(ik,i)

CONCEPTOS BÁSICOS

CONCEPTOS BÁSICOS

• UNA SUBGRÁFICA G’=(N’,A’) DE UNA GRÁFICA G=(N,A) es un conjunto de nodos y arcos de G: N’Î N y G’ Î G.

• UNA GRÁFICA G=(N,A) ES CONEXA si para cada par de nodos i,j Î N existe un camino que conecte el nodo i con el nodo j.

• CONCEPTOS BÁSICOS

• Una RED es una gráfica con uno o mas valores asignados a los nodos y/o a los arcos:

Nodos: (ai)demanda, oferta, eficiencia, confiabilidad.

Arcos: (cij) costo, distancia, capacidad

Ejemplos: representar a través de una red : red de agua potable, red de comunicación, red logística.

• PROBLEMAS Y MODELOS DE REDES

• PROBLEMAS: encontrar la ruta más corta de la planta al centro de distribución pasando por ciudades intermedias. Problemas de transbordo. Política de reemplazo de equipo.

• MODELO de la RUTA MÁS CORTA: dada una red dirigida G=(N,A) con distancias asociadas a los arcos (cij), encontrar la ruta más corta del nodo i al nodo j, donde i,jÎN

PROBLEMAS Y MODELOS DE REDES

• PROBLEMAS: transportar la mayor cantidad de producto posible a través de una red de distribución: ductos, tráfico vehicular.

• MODELO de FLUJO MÁXIMO: dada una red dirigida G=(N,A) con capacidades en los arcos (cij) encontrar la mayor cantidad de flujo total de un nodo fuente a un nodo destino.

PROBLEMAS Y MODELOS DE REDES

• PROBLEMAS: programar las actividades de un proyecto y determinar el tiempo requerido para terminar el proyecto así como las actividades “críticas”

• MODELO: CPM, PERT (RUTA MAS LARGA)

• PROBLEMAS: redes de comunicaciones. Conectar todos los nodos con el mínimo costo.

• MODELO DEL ÁRBOL GENERADOR MINIMAL: dada una red conexa no dirigida G=(N,A) con costos cij en cada arco (i,j) Î A, encontrar el Árbol Generador de costo mínimo

• Problema del Agente Viajero: encontrar el camino más corto saliendo de un nodo y regresando al mismo.

• MODELO DEL AGENTE VIAJERO: encontrar un ciclo en una red (dirigida o no dirigida ). Un (camino) ciclo que no repite nodos es un (camino) o ciclo Hamiltoniano.

• NO SIEMPRE EXISTE

OTROS CASOS ESPECIALES

• RED PLANA: que puede representarse en el plano sin cruzar arcos. Útil en ruteo

CICLO DE EULER: UN CICLO QUE INCLUYE CADA ARCO SOLO UNA VEZ. (Solo existe en una gráfica si esta tiene un número par de arcos incidentes en cada vértice (Euler). Útil en ruteo.

OTRAS APLICACIONES A II

• LAYOUT: distribución física de instalaciones

...