Teoria de redes

METODOS CUANTITATIVOS APLICADOS A LA ADMINISTRACION
Material de Apoyo – Modelos de REDES - 2005
28
/05/2005
(1-25)
Prof. Hugo Roche
Análisis de Modelos de Redes
(Ver Capitulo 9 de Hillier&Lieberman 7º Edicion, 2002)
Los Modelos de Optimización de redes se aplican a numerosos casos en la Ciencia de la
Administración, en particular relacionados con la operación de redes detransporte,
logística,
redes eléctricas o de
comunicación, pero también en programación y
seguimiento de Proyectos, en Marketing, Recursos Humanos y en Finanzas.
La mayor parte de los modelos de redes son casos particulares de modelos de
Programación Lineal, y pueden ser formalizados a partir de un modelo general que los
engloba : el Modelo de Flujo de Costo Mínimo. En Anexo I se seleccionadoun Glosario de
la terminología propia de estos modelos
En el Curso se verán 5 tipos de modelos de Redes : la Ruta mas corta (RMC), el árbol de
expansión mínima (AEM) , la red de flujo máximo (RFM), el modelo de Transporte y el
Modelo de Asignación. En Anexo II se resume en una Tabla las principales características
de los principales modelos de Redes.
Ejemplo Prototipo : el Parque Seervada(Hillier&Lieberman, 2002 Cap. 9)
El Parque Seervada está organizado de tal manera que se dispone de una Entrada y una
serie de senderos que pasan por 5 Estaciones intermedias que conducen al Mirador, el
cual representa la estación terminal.
El Administrador del Parque debe resolver tres tipos de problemas propios de la gestión
del Parque:
(1)
Determinar la ruta más corta desde la Entrada alMirador. (RMC)
(2) Determinar el tendido del cableado telefónico de todas las estaciones desde la
entrada hasta el Mirador que minimice el total de cable a instalar. (AEM)
(3) Determinar el número máximo de viajes que se pueden organizar desde la
Entrada hasta el Mirador tomando en cuenta el factor de carga que ha
establecido el guardaparque en términos de total de viajes permitidos por día ypor sendero (RFM).
En la figura siguiente se identifican las 7 estaciones del Parque como Nodos, con la
Entrada como Nodo (O) y el Mirador como Nodo (T). La información disponible en cada
Arco representa la distancia entre nodos medidos en millas.
2
7
5
2
5
4
7
4
1
3
1
4
O
A
B
C
D
E
T

METODOS CUANTITATIVOS APLICADOS A LA ADMINISTRACION
Materialde Apoyo – Modelos de REDES - 2005
28
/05/2005
(2-25)
Prof. Hugo Roche
Modelo de la Ruta más corta (RMC)
En el marco de los problemas de RMC se considera una red conexa y no dirigida con dos
nodos especiales, llamados origen y destino. A cada una de las ligaduras (arcos no
dirigidos) se asocia una distancia no negativa. El objetivo del análisis es encontrar la ruta
más corta, es decir, latrayectoria con la mínima distancia total, que va del origen al
destino.
Para su resolución se utiliza el Algoritmo de la Ruta más corta o también se puede utilizar
el SIMPLEX utilizando las propiedades de este Problema, que es un caso específico del
Modelo de Programación Lineal.
Algoritmo de Ruta más corta.
Este algoritmo analiza la red a partir del origen, identificando sucesivamente laruta más
corta a cada uno de los nodos en orden ascendente de sus distancias desde el origen,
quedando resuelto el problema en el momento de llegar al nodo destino. A continuación
se muestra la tabla de aplicación del algoritmo de la ruta más corta para encontrar la ruta
más corta desde la entrada al parque hasta el mirador (ejemplo prototipo).
Tabla: Aplicación del Algoritmo Ruta Mas CortaResolución del Ejemplo “Parque Seervada”.
N
Nodos
resueltos
conectados
directamente a
nodos no
resueltos
Nodo no
resuelto más
cercano
conectado
Distancia total
involucrada
n-ésimo nodo
más cercano
Distancia
mínima
Ultima
conexión
1
O A 2 A 2 OA
2,3
O
A
C
B
4
2+
2
=4
C
B
4
4
OC
AB
4
A
B
C
D
E
E
2+
7
=9
4+
3
=7
4+...