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:

...