inv operativa 2

Universidad Arturo Prat – Ingeniería Industrial

Investigación Operativa II
Vivian Segovia Barros
vivian.segovia@Gmail.com
Diciembre 2014

Unidad 2

Optimización de Redes

Investigación Operativa II
Universidad Arturo Prat – Ingeniería Industrial

Unidad 2

Introducción
Conceptos relacionados


Todo sistema se compone de una red que interconecta procesos,
entidades, etc.

La optimización en redes corresponde, en algunos casos, a un tipo
especial de programación lineal.



Caracterización típica de los problemas de redes:
Donde:

A

C
E

D
B

F

A
B
C

Nodos
Arcos o ramas (dirigido para
unidireccional y no dirigido
para bidireccional)

Introducción
Conceptos relacionados


Ejemplos:


Nodos  Aeropuertos, estaciones deservicio, centros de trabajo.



Arcos  Caminos, líneas aéreas, tuberías, canales, cables.



Flujo  Vehículos, fluidos, trabajos, aviones.

Unidad 2

Aplicaciones
Tipos de problemas de redes
1.

Flujo máximo  maximización de flujo desde origen a destino

2.

Ruta más corta  Encontrar la distancia más pequeña a
recorrer desde origen a destino (entre nodos).

3.

Árbolde expansión mínima  Diseño de red para unir nodos
y minimizar longitud de arcos que los conecten.

4.

Flujo del costo mínimo (Simplex en redes)

5.

Método CPM

Unidad 2

Flujo Máximo


Todo flujo a través de una red conexa dirigida se origina en
un nodo (origen) y termina en otro nodo (destino).



Los nodos restantes son nodos de trasbordo



El flujo a través deun arco se permite sólo en la dirección
indicada por la flecha y la cantidad máxima de flujo está
dada por la capacidad del arco.



Objetivo  Maximizar la cantidad total de flujo del origen al
destino. Se puede medir como la cantidad que sale del origen
o la cantidad que entra al destino.

Unidad 2

Unidad 2

Ruta más corta


Ejemplo
Problema de reemplazo de flota vehicularutilizando la ruta más corta. Se
quiere encontrar el menor costo asociado.

Costo menor según = 0-2-5 = $12.500
9800
5400

0

4000

1

7100

4300

2

4800

6200
8700

3

4900

4

Árbol de expansión mínima


Procedimiento:
•

Se selecciona un nodo de inicio y se conecta al nodo distinto
más cercano y así sucesivamente según cual sea el objetivo.

•

Losempates del nodo más cercano distinto o del nodo no
conectado más cercano se pueden romper en forma
arbitraria, pero el algoritmo debe llegar a una solución
óptima. También esto puede significar que existan múltiples
soluciones óptimas

•

De manera gráfica es más rápido resolverlo

Unidad 2

Unidad 2

Árbol de expansión mínima


Ejemplo

Se requiere encontrar la mínimalongitud requerida de
tuberías para ser instaladas en un parque, estas tuberías
deben llegar a todas las estaciones.

Longitud mínima = 14 un.

Flujo de Costo Mínimo
Qué es ?


Es una de las técnicas más usadas por su versatilidad (se
puede ocupar en una variada gama de problemas de redes).



Genera los mismos resultados que todas las técnicas
anteriores (aquellas son tipos especialesde este).



Se resuelve de manera eficiente dado que se formula como
problema de Programación Lineal y se resuelve con una
versión simplificada del método simplex (Simplex en redes)

Objetivo
Minimizar costo total de envío de suministro disponible a
través de la red para satisfacer una demanda dada. También
puede tomarse como maximizar utilidades totales de envío.

Unidad 2Unidad 2

Flujo de Costo Mínimo
Aplicaciones

Hillier, 2010

Flujo de Costo Mínimo
Condiciones


La red es una red dirigida y conexa.



Al menos uno de los nodos es un nodo fuente.



Al menos uno de los nodos es un nodo demanda.



El resto de los nodos son nodos de trasbordo.



Se permite flujo a través de un arco sólo en la dirección que indica la
flecha,...