CONCEPTOS BASICOS DE ANALISIS DE REDES

 El análisis de redes es el área encargada de analizar las redes mediante la teoría de redes (conocida más genéricamente como teoría de grafos).

Las redes pueden ser de diversos tipos:

•  Social
•  Transporte
•  Eléctrica
•  Biológica
•  Internet
•  Información
•  Epidemiología

Cuando se habla de una red,se entiende como un grupo de individuos que, en forma agrupada o individual, se relacionan con otros con un fin especifico, caracterizado por la existencia de flujo de informacion.Las redes pueden tener muchos o pocos actoresy una o mas clases de relaciones entre pares de actores.

 Flujo: Corresponde a la cantidad que debe transportarse desde un nodo i a un nodo j a través de un arco que los conecta.  La siguiente notación es usada: Xij= cantidad de flujo Uij= cota mínima de flujo que se debe transportar Lij= cota maxíma de flujo que se puede transportar.

 * Arcos dirigidos /no dirigidos:  Cuando el flujo puede transportarse en una sola dirección se tiene un arco dirigido (la flecha indica la dirección).  Si el flujo puede transportarse en ambas direcciones existe un arco no dirigido (sin flecha).

* Nodos adyacentes: Un nodo j es adyacente con un nodo i si existe un arco que une el nodo j con el nodo i.

*Ruta: Una colección de arcos formados por una serie de nodos adyacentes; los nodos están conectados si existe una ruta entre ellos.

 

* Ciclos : Un ciclo se produce cuando al partir de un nodo por un cierto camino se vuelve al mismo nodo por otra ruta.

 * Arbol : Una serie de nodos que no contienen ciclos.

 *Arbol expandido: Es un árbol que conecta todos lo nodos de la red (contiene n-1 arcos).

PROBLEMA DE TRANSPORTE 

El Problema de Transporte corresponde a un tipo particular de un problema de programación lineal. Si bien este tipo de problema puede ser resuelto por el método Simplex, existe un algoritmo simplicado especial para resolverlo.

Un problema particular que se resuelve con los procedimientos de la programación lineal es la situación conocida como problema del transporte o problema de la distribución de mercancías.

Se trata de encontrar los caminos para trasladar mercancía, desde varias plantas (orígenes) a diferentes centros de almacenamiento (destinos), de manera que se minimice el costo del transporte.

Ejemplo

Problema del transporte

Una empresa dedicada a la fabricación de componentes de ordenador tiene dos fábricas que producen, respectivamente, 800 y 1500 piezas mensuales. Estas piezas han de ser transportadas a tres tiendas que necesitan 1000, 700 y 600 piezas, respectivamente. Los costes de transporte, en pesetas por pieza son los que aparecen en la tabla adjunta. ¿Cómo debe organizarse el transporte para que el coste sea mínimo?

Tienda A Tienda B Tienda C Fábrica I 3 7 1 Fábrica II 2 2 6

En este tipo de problemas se exige que toda la producción sea distribuida a los centros de ventas en las cantidades que precisa cada uno; por tanto, no pueden generarse inventario del producto ni en las fábricas ni en los centros de ventas.

En consecuencia, los 800 artículos producidos en la fábrica I deben distribuirse en las cantidades x, y, z a A, B y C, de manera que x + y + z = 800. Pero, además, si desde I se envían x unidades a A, el resto, hasta las 1000 necesarias en A, deben ser enviadas desde la fábrica II; esto es, 1000 – x unidades serán enviadas desde II a A.
Del mismo modo, si desde I a B se envían y, el resto necesario, 700 – y, deben enviarse desde II. Y lo mismo para C, que recibirá z desde I y 600 – z desde II.

En la siguiente tabla de distribución se resume lo dicho:

Envíos	a la tienda A (1000)	a la tienda B (700)	a la tienda C (600)
Desde la fábrica I ( 800)	X	y	800 – x – y
Desde la fábrica II (1500)	1000 – x	700 – y	x + y – 200

La última columna la hemos obtenido de la siguiente forma:
Como x + y + z = 800 , se tiene que z = 800 – x – y, de donde, 600 – z = 600 – (800 – x – y) = x + y – 200.

Ahora bien, todas las cantidades anteriores deben ser mayores o iguales que cero. Por tanto, se obtienen las siguientes desigualdades:

x 0 ; 1000 – x 0 ; y 0; 700 – y 0 ; 800 – x – y 0 ; x + y – 200 0

Simplificando las desigualdades anteriores, se obtienen las siguientes inecuaciones:

1000 x 0 ; 700 y 0 ; 800 x + y 0

Recordemos que nuestro objetivo es abaratar al máximo los costes de transporte.

Estos costes se hallan multiplicando las cantidades enviadas a desde cada fábrica a cada tienda por los respectivos costes de transporte unitario.
Se obtiene:

Z = f(x,y) = 3x + 2(1000 – x) + 7y + 2(700 – y) + (800 – x – y) + 6(x + y – 200) = 6x + 10y + 3000

En definitiva, el programa lineal a resolver es :

Minimizar:	Z = 6x + 10y + 3000
sujeto a:	1000 x 0
	700 y 0
	800 x + y 0

La región factible se da en la imagen del margen.

Sus vértices son A(200,0) ; B(800,0) ; C(100,700) ; D(0,700) y E(0,200).

El coste, el valor de Z en cada uno de esos puntos, es:

conjunto de actividades u operaciones de naturaleza

concreta o abstracta, por ejemplo, colocación de hormigón o presentación a una propuesta;

debidamente planeadas y coordinadas. Con límites y alcances definidos en un área o campo

determinado y cuyo objetivo es satisfacer necesidades humanas, dentro de un marco de

referencia previamente establecido.

PROBLEMA DE ASIGNACIÓN

consiste en encontrar la forma de asignar ciertos recursos disponibles (máquinas o personas) para la realización de determinadas tareas al menor coste, suponiendo que cada recurso se destina a una sola tarea, y que cada tarea es ejecutada por uno solo de los recursos. Es uno de los problemas fundamentales de optimización combinatoria de la rama de optimización o investigación operativa en matemática. El modelo se puede aplicar a la asignación de empleados a tareas, de fábricas a productos, de vendedores a territorios, de postores a contratos, etc. Con una sencilla manipulación, el método también se puede aplicar al caso en el que se pretende maximizar cierta cantidad.

Formalmente, el problema de la asignación consiste en encontrar un emparejamiento de peso óptimo en un grafo bipartito ponderado. El problema de asignación es un caso particular del problema de transporte, en el que la oferta en cada origen y la demanda en cada destino son ambas de valor 1.

a compañía de manufactura «Jiménez y Asociados» desea realizar una jornada de mantenimiento preventivo a sus tres máquinas principales A, B y C. El tiempo que demanda realizar el mantenimiento de cada máquina es de 1 día, sin embargo la jornada de mantenimiento no puede durar más de un día, teniendo en cuenta que la compañía cuenta con tres proveedores de servicios de mantenimiento debe de asignarse un equipo de mantenimiento a cada máquina para poder cumplir con la realización del mantenimiento preventivo. Teniendo en cuenta que según el grado de especialización de cada equipo prestador de servicios de mantenimiento el costo de la tarea varía para cada máquina en particular, debe de asignarse el equipo correcto a la máquina indicada con el objetivo de minimizar el costo total de la jornada. Los costos asociados se pueden observar en la siguiente tabla:

PROBLEMA DE LA RUTA MAS CORTA

consiste, si es necesario decirlo, en una modalidad de problemas de redes, en la cual se debe determinar el plan de rutas que genere la trayectoria con la mínima distancia total, que una un nodo fuente con un nodo destino, sin importar el número de nodos que existan entre estos.

Un minero ha quedado atrapado en una mina, la entrada a la mina se encuentra ubicada en el nodo 1, se conoce de antemano que el minero permanece atrapado en el nodo 9, para llegar a dicho nodo hay que atravesar una red de túneles que van conectados entre sí. El tiempo de vida que le queda al minero sin recibir auxilio es cada vez menor y se hace indispensable hallar la ruta de acceso al nodo 9 más corta. Las distancias entre nodos de la mina se encuentran en la siguiente gráfica dadas en cientos de metros. Formule un modelo de transbordo y resuelva mediante cualquier paquete de herramientas de investigación operativa que permita establecer la ruta más corta para poder así auxiliar al minero.

PROGRAMACIÓN DE PROYECTOS

.

indica qué se debe hacer, qué recursos se deben utilizar y cuándo vence el proyecto. Es decir, es un plan que expone las fechas de inicio y finalización y los hitos que deben cumplirse para que el proyecto se complete a tiempo.