Tema 1 Mod - Redes

Universidad
Nacional
Jos Faustino
Snchez Carrin
FACULTAD DE INGENIERA
INVESTIGACIN DE OPERACIONES II
Dr. Alcibiades Sosa

Palomino
TEMA 1: MODELO DE REDES

INVESTIGACIN DE OPERACIONES
Se han dado muchas definiciones. Segn Ackoff y Arnof en Prawda : La Investigacin
de operaciones es la aplicacin , por grupos interdisciplinarios, del mtodo cientfico a
problemas relacionados con el control de las organizaciones o sistemas a fin de que se
produzcan soluciones que mejor sirvan a los objetivos de toda la organizacin.
PROCESO EN LA TOMA DE DECISIONES
ESTRUCTURA DEL PROBLEMA
Problema
Modelo
Solucin
AHS
Analsis
Cuant.
Evaluac.
Toma de
decisiones
Anlisis
Cualit.
MODELO DE REDES
Modelo que permite tomar decisiones ptimas en un sistema, utilizando para ello el
modelo de programacin lineal y otros algoritmos para casos especiales.
Mediante el modelo de redes se han resuelto con xito diversos problemas industriales y
en otras reas tales como en sistemas de transporte, proyectos, etc.
Algunos casos de modelos de redes son:
M. Transporte.
M. Asignacin.
M. Transbordo.
M. Ruta ms corta.
M. rbol de extensin mnima.
M. Flujo mximo.
M. PERT/CPM
ELEMENTOS BASICOS DE UNA RED

1. NODO.- Lnea cerrada que representa: ciudad, almacn, interseccin de pistas; etc.
Pueden presentarse como:
FUENTE
i
Emisor
TRANSBORDO
DESTINO
j
Receptor
2. ARCOS .- Lnea o flecha que representa la trayectoria de un nodo a otro.
Pueden ser:
j
Dirigidos
xij
i
No dirigidos
3. FLUJO.- Representan los valores de xij
Estos valores pueden ser: n de vehculos que circulan por una pista,
volumen de agua que fluye por una caera, etc.
RED.- Diagrama formado por la inter relacin de nodos, arcos y flujos bsicamente.
Las redes pueden presentarse como cadenas, anillos, rbol abierto, combinacin
de todos ellos.
Cadena
Anillo
rbol
Red
CARACTERISTICA DEL MPL DE UNA RED
Los elementos de la matriz tecnolgica es 1 1 ( a ij )
Existe una restriccin para cada nodo.
Cada arco representa una variable de decisin.
Todo modelo matemtico que tiene estas caractersticas se puede representar
mediante una red y viceversa.
MODELO DE TRANSPORTE
El modelo general de programacin lineal de transporte con m orgenes y n destinos es:
m
c
i 1 j 1
ij
x ij
Min
Sujeta a:
n
x
j 1
ij
si
i = 1; 2 ; ; m
oferta
x
i 1
dj
ij
j=1;2;;n
demanda
xij 0 para toda i y para toda j.
Pueden aadirse restricciones adicionales de la forma xij < Lij si la ruta que va del origen
i al destino j , tiene la capacidad Lij . (Problema de transporte con capacidades)
MODELO DE ASIGNACIN
El problema general de asignacin implica n agentes y m tareas; en donde los valores
de xij es cero uno
m
c
i 1 j 1
ij
x ij
Min
Sujeta a
n
x
j 1
ij
x
i 1
xij
i = 1; 2 ; ; m
agentes
j=1;2;;n
tareas.
ij
0 para toda i y para toda j.
MODELO DE TRANSBORDO
Es una ampliacin del problema de transporte.
Existen nodos intermedios (nodos de transbordo)
Bsicamente se presentan las siguientes restricciones: restricciones de origen, de
transbordo de destino y de capacidad de flujo.
El modelo general de programacin lineal para el problema de transbordo es:
ij
X ij
Min
Todos los arcos
Sujeta a
ij
x ij s i
Arcos que salen
ij
x ij 0
Arcos que salen
Nodo origen i
arcos que entran
arcos que entran
Transferencia de nodos
ij
x ij d j
Nodos destino j
Arcos que salen
arcos que entran
xij 0
para toda i o j .
Adems pueden darse restricciones de capacidades de ruta ( Problemas de
transbordo con capacidades )
PROBLEMA DE LA RUTA MS CORTA.
Aplicacin de redes en la que el objetivo primordial consiste en determinar la ruta ms
corta el camino ms reducido a travs de la red.
ALGORITMO.
Distancia acumulada desde el nodo inicial Nodo precedente
1. Asignar al nodo 1 el rtulo permanente [ da, ni-1 ]
2. Determinar rtulos tentativos para los nodos a los que puede llegarse en forma
directa desde el nodo 1.
3. Identificar el nodo con la etiqueta tentativa que tenga el menor valor de distancia , y
considerarlo como rotulado en forma permanente.
4. Considrense todos los nodos que no tienen etiqueta permanente y a los que pueden
llegar en forma directa desde el nuevo nodo con etiqueta permanente que se
estableci en el paso 3.
En caso que el nodo tiene rtulo, si el acumulado es menor o igual rotular ambos
resultados.
En caso que el nodo no tiene rtulo, registrar los resultados.
5. Retornar al paso 3 hasta rotular en forma permanente todos los nodos. Los rtulos
permanentes identifican la distancia ms corta desde el nodo 1 hasta cada uno de los
nodos.
EL PROBLEMA DEL ARBOL DE EXTENSION MINIMA
Se refiere a utilizar las ramas (arcos), de la red para llegar a todos los nodos de la red de tal manera que
se minimice la longitud total de todas las ramas. Estas conexiones deben realizarse sin formar anillos.
ALGORITMO
1. Comenzar en forma arbitraria en cualquier nodo y conectarlo con el nodo ms prximo . A estos
nodos se les denomina nodos conexos y a los restantes nodos inconexos.
2. Identificar el nodo no conectado que est ms cerca de uno de los conectados. Deshacer los empates
en forma arbitraria. Agregar este nodo al conjunto de nodos conectados. Repetir esta iteracin hasta
que se hayan conectados todos los nodos.
EL PROBLEMA DEL FLUJO MAXIMO

El objetivo es terminar el flujo mximo que puede entrar y salir del sistema de una red
en un periodo determinado de tiempo y adems la distribucin del flujo en la red.
ALGORITMO
1. Encontrar cualquier camino del nodo de entrada (fuente) al nodo de salida (anti
fuente) que tenga capacidades de flujo.
2. Encontrar la menor capacidad de la rama ( pf), sobre el camino elegido en 1.
3. Para el camino elegido en 1 aumentar en p f a las capacidades de flujo en sentido
contrario y reducir en pf las capacidades en el sentido del flujo. Volver al paso 1
hasta saturar todo los caminos posibles, encontrndose de esta manera la solucin
ptima.
FLUJO MAXIMO A COSTO MINIMO
Se puede utilizar este modelo cuando existe la posibilidad de utilizar ms de una
mquina de caractersticas diferentes por capacidad (unidades /hora mquina) y costo
($/unidad); en la secuencia operativa del proceso de elaboracin de un artculo de gran

demanda.
En este modelo es posible maximizar el flujo de produccin (unidades/hora), logrando
que se obtenga al mnimo costo posible.
El algoritmo que se utiliza es de BUSACKER que consiste en :
1. Se construye una red donde los nodos representan las mquinas ( grupos similares)
disponibles para el proceso y cada arco una posible ruta.
2. En cada arco debe figurar el costo unitario y el flujo mximo (cu,fm).
3. Se procede a etiquetar las mquinas en la red eligiendo las de menor costo,
empezando por el nodo S (start-inicio) hasta llegar al nodo final.
La secuencia de mquinas etiquetadas representa la ruta ptima.
La etiqueta consta de (c acumulado, mq. de donde proviene, f que pasa por la
mq.)
4. Para determinar cunto es lo que an puede procesar cada mquina se recorre la ruta
elegida de modo inverso, colocando bajo los arcos la cantidad que fue procesada y
lo que an se puede procesar.
5. Se calcula el flujo y el costo de esta primera iteracin de la etiqueta final.
6. Se repite el proceso hasta saturar todas las rutas.
7. Se obtiene la sumatoria de los costos y flujos parciales

Tema 1 Mod - Redes

Cargado por

Copyright:

Formatos disponibles

Tema 1 Mod - Redes

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Tema 1 Mod - Redes

Cargado por

Copyright:

Formatos disponibles

Universidad

Dr. Alcibiades Sosa

TEMA 1: MODELO DE REDES

ELEMENTOS BASICOS DE UNA RED

0 para toda i y para toda j.

Arcos que salen

Arcos que salen

arcos que entran

arcos que entran

EL PROBLEMA DEL FLUJO MAXIMO

($/unidad); en la secuencia operativa del proceso de elaboracin de un artculo de gran

También podría gustarte