ANALISIS DE REDES

2.1 FORMULACION DE MODELOS

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.

 

Terminología de Redes

* 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.

Rutas/Conexión entre nodos

*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 / Arboles /Arboles expandidos

* 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).

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 flujos de información. Las redes pueden tener muchos o pocos actores y una o más clases de relaciones entre pares de actores. Una res se  compone, por tanto, de tres elementos básicos los cuales son: nodos o actores, vínculos o relaciones y, flujos.

NODOS O ACTORES:

Son las personas o grupos de personas que se encuentran en torno a un objetivo en común. Usualmente los nodos o actores se representan por círculos. La suma de todos los nodos representa el tamaño de la red.

VÍNCULO O RELACIONES:

Son los lazos que existen entre dos o más nodos.  En una red de amistad, por ejemplo, un actor muestra un vínculo directo con otro actor. Los vínculos o relaciones se representan con líneas.

FLUJO:

Indica la dirección del vínculo. Los flujos se representan por una flecha que indica el sentido. Es posible que también existan flujos mutuos o bidireccionales. Cuando un actor no tiene ningún tipo de flujo, lo que a su vez implica ningún vínculo, se dice que este nodo esta suelto dentro de la red

GRAFOS NO DIRIGIDOS

Si los pares que forman las relaciones no son pares ordenados, entonces el lazo (n_a,n_b) entre dos nodos es exactamente la misma que (n_b,n_a), es decir, no hay un origen y un destino de la relación. Este tipo de relaciones son simétricas o no direccionales. Por ejemplo, la relación es hermano de es de este tipo.

 

GRAFOS DIRIGIDOS

Si los pares que forman las relaciones son pares ordenados, entonces el lazo (n_a,n_b) representa una información diferente al lazo (n_b,n_a), y puede que entre dos nodos haya un lazo en una dirección pero no en la otra. Por ejemplo, la relación «ama apasionadamente a» es dirigida, ya que puede darse el caso de que el amor sea de a hacia b pero que no esté correspondido de b hacia a.

2.2 PROBLEMA DE TRANSPORTE 

Un problema de transporte​ es, en matemáticas y economía, un caso particular de problema de programación lineal en el cual se debe minimizar el coste del abastecimiento a una serie de puntos de demanda a partir de un grupo puntos de oferta —posiblemente de distinto número—, teniendo en cuenta los distintos precios de envío de cada punto de oferta a cada punto de demanda.

l problema del transporte o distribución, es un problema de redes especial en programación lineal que se funda en la necesidad de llevar unidades de un punto específico llamado fuente u origen  hacia otro punto específico llamado destino. Los principales objetivos de un modelo de transporte son la satisfacción de todos los requerimientos establecidos por los destinos, y claro está, la minimización de los costos relacionados con el plan determinado por las rutas escogidas.

El contexto en el que se aplica el modelo de transporte es amplio y puede generar soluciones relacionadas con el área de operaciones, inventario y asignación de elementos.

El procedimiento de resolución de un modelo de transporte se puede llevar a cabo mediante programación lineal común, sin embargo su estructura permite la creación de múltiples alternativas de solución tales como los modelos de asignación, o los métodos de flujos de red. También es posible emplear los heurísticos más populares como Vogel, Esquina Noroeste o Mínimos Costos.

 Los problemas de transporte o distribución son uno de los más aplicados en la economía actual, dejando, como es de prever, múltiples casos de éxito a escala global que estimulan la aprehensión de los mismos.

EJEMPLO 

Una empresa energética colombiana dispone de cuatro plantas de generación para satisfacer la demanda diaria eléctrica en cuatro ciudades, Cali, Bogotá, Medellín y Barranquilla. Las plantas 1,2,3 y 4 pueden satisfacer 80, 30, 60 y 45 millones de KW al día respectivamente. Las necesidades de las ciudades de Cali, Bogotá, Medellín y Barranquilla son de 70, 40, 70 y 35 millones de Kw al día respectivamente. Los costos asociados al envío de suministro energético por cada millón de KW entre cada planta y cada ciudad son los registrados en la siguiente tabla.

             

Solución mediante programación lineal

El modelo básico de transporte es el modelo en el cual la cantidad ofertada es igual a la cantidad demandada, como es el caso de este ejercicio, sin embargo trasladar esta suposición a la realidad es casi imposible por lo cual hace falta crear orígenes y/o destinos ficticios con el excedente de oferta y/o demanda (es sugerible que se haga con la demanda).

Como ya lo hemos planteado en módulos anteriores el primer paso corresponde a la definición de las variables, regularmente se le denomina a las variables de manera algebraica Xi,j donde i simboliza a la fuente y j simboliza al destino. En este caso i define el conjunto {Planta 1, Planta 2, Planta 3 y Planta 4}, y j define el conjunto {Cali, Bogotá, Medellín y Barranquilla}. Sin embargo es práctico renombrar cada fuente y destino por un número respectivo, por ende la variable X1,2 corresponde a la cantidad de millones de KW enviados diariamente de la Planta 1 a la ciudad de Bogotá.

 

El segundo paso corresponde a la formulación de las restricciones de oferta y demanda, cuya cantidad se encuentra determinada por el factor entre fuentes y destinos, en este caso 16 restricciones.

Restricciones de oferta o disponibilidad, las cuales son de signo ≤:

X1,1 + X1,2 + X1,3 + X1,4 ≤ 80

X2,1 + X2,2 + X2,3 + X2,4 ≤ 30

X3,1 + X3,2 + X3,3 + X3,4 ≤ 60

X4,1 + X4,2 + X4,3 + X4,4 ≤ 45

Restricciones de demanda, las cuales son de signo ≥:

X1,1 + X2,1 + X3,1 + X4,1 ≥ 70

X1,2 + X2,2 + X3,2 + X4,2 ≥ 40

X1,3 + X2,3 + X3,3 + X4,3 ≥ 70

X1,4 + X2,4 + X3,4 + X4,4 ≥ 35

Luego se procede a formular la función objetivo, en la cual se relaciona el costo correspondiente a cada ruta.

ZMIN = 5X1,1 + 2X1,2 + 7X1,3 + 3X1,4 + 3X2,1 + 6X2,2 + 6X2,3 + 1X2,4 + 6X3,1 + 1X3,2 + 2X3,3 + 4X3,4 + 4X4,1 + 3X4,2 + 6X4,3 + 6X4,4

Luego se puede proceder al uso de la herramienta WinQSB para resolver el modelo realizado, aquí están los resultados.

Este problema presenta una solución óptima alternativa, aquí los resultados.

 

Red solución:

Los análisis de dualidad y sensibilidad en los modelos de transporte resultan ser bastante interesantes, pues pueden llegar a determinar aumentos de capacidad en las fuentes si el precio sombra de las rutas en relación a ellas lo justifica.

2.3 PROBLEMA DE ASIGNACION 

En su forma más general, el problema es como sigue:

Hay un número de agentes y un número de tareas. Cualquier agente puede ser asignado para desarrollar cualquier tarea, contrayendo algún coste que puede variar dependiendo del agente y la tarea asignados. Es necesario, para desarrollar todas las tareas, asignar un solo agente a cada tarea de modo que el coste total de la asignación sea mínimo.

Este tipo de problemas son lineales, con una estructura de transporte, solo que la oferta en cada origen es de valor uno y la demanda en cada destino es también de valor uno. Sería muy ineficiente resolver este tipo de problemas por medio del método simplex o por medio del algoritmo de transporte. Debido a la estructura propia de los problemas de asignación, existen métodos de solución llamados "algoritmos de asignación" que son más eficientes que el simplex o que el método de transporte.

Los problemas de asignación presentan una estructura similar a los de transporte, pero con dos diferencias: asocian igual número de orígenes con igual número de demandas y las ofertas en cada origen es de valor uno, como lo es la demanda en cada destino.

La restricción importante para cada agente es que será asignado a una sola tarea.

Método Húngaro

El método húngaro es un método de optimización de problemas de asignación.

Este método utiliza la propiedad de reducción de matrices para reducir la matriz original de costo, hasta que los costos C i j asociados con la asignación óptima, sean cero y todos los otros costos sean no negativos.

En cada iteración del método húngaro, se reduce la matriz de tal manera que haya al menos un cero en cada renglón y columna, comprobando con el teorema de König si se ha alcanzado la solución óptima. Si el número mínimo de renglones y/o columnas necesarios para cubrir todos los ceros es n, entonces existe una asignación óptima (no necesariamente única).

El algoritmo tal como se detallará a continuación está diseñado para la resolución de problemas de minimización únicamente, ya que es más eficaz para resolver el problema del transporte por el alto grado de degeneración que pueden presentar los problemas de asignación.

Los problemas de asignación incluyen aplicaciones tales como asignar personas a tareas. Aunque sus aplicaciones parecen diferir de las del problema del transporte, constituye un caso particular. Los problemas de transporte y asignación son casos particulares de un grupo más grande de problemas, llamados problemas de flujo en redes.

Suposiciones de un problema de asignación:

1.    El número de asignados es igual al número de tareas (se denota por n). (esto puede variar).

2.    Cada asignado se asigna exactamente a una tarea.

3.    Cada tarea debe realizarla exactamente un asignado.

4.    Existe un costo cij asociado con el asignado i (i=1,2,…,n).

5.    El objetivo es determinar cómo deben hacerse las asignaciones para minimizar los costos totales

Procedimiento:

El Método Húngaro consta de los siguientes pasos:

Paso 1: En la matriz original de costo, identificar el mínimo de cada fila y restarlo de todos los elementos de la fila.

Paso 2: En la matriz que resulte del Paso 1, identificar el mínimo de cada columna, y restarlo de todos los elementos de la columna.

Paso 3: Identificar la solución óptima como la asignación factible asociada con los elementos cero de la matriz obtenida en el Paso 2.

A continuación presentaremos un ejemplo que muestra la aplicación del Método Húngaro que nos permite decidir la asignación de trabajadores a puestos de trabajo.

Ejemplo:

Un equipo de 3 ingenieros debe ser asignado para la realización de 3 tareas, donde cada ingeniero debe hacer una tarea. Se requiere encontrar la asignación de costo mínimo para lo cual se dispone de los costos asociados a que el ingeniero i realice la tarea j. Por ejemplo, representa el costo correspondiente a que el ingeniero 1 asuma la tarea 1.

Aplicar el Método Húngaro para encontrar una asignación óptima de los ingenieros a las tareas.

El Paso 1 del Método Húngaro requiere identificar el valor mínimo de cada fila. En el caso de la fila 1 dicho valor es $9 siendo el costo de que el ingeniero realice la tarea 3.

En particular si se dispone de un problema de mayor tamaño, hacer uso de Excel facilita los cálculos tal como se muestra en la siguiente imagen:

A continuación se resta el mínimo de cada fila a cada uno de los valores de la fila respectiva, para obtener la matriz reducida:

La aplicación del Paso 2 produce los mínimos de cada columna según se observa en la tabla anterior. Al restar esos valores de las columnas respectivas se obtiene la siguiente matriz reducida:

Las celdas con valor cero y color azul son la solución óptima. En consecuencia el ingeniero 1 realiza la tarea 2, el ingeniero 2 asuma la tarea 1 y el ingeniero 3 la tarea 3. Cada ingeniero realiza exactamente una tarea y el costo total de dicha asignación (valor óptimo) es de: 

$9 + $10 + $8 = $27

Los pasos presentados del Método Húngaro para el ejemplo anterior funcionaron bien debido a que los elementos cero de la matriz anterior permiten una asignación factible de ingenieros a las tareas (en el sentido que las tareas se asignan de forma única a los ingenieros). Aunque no siempre es posible lograr una solución factible en la aplicación, caso en el cual se requiere de pasos adicionales para la aplicación del método.

2.4 PROBLEMA DE LA RUTA MAS CORTA 

El Problema del Camino más Corto (o ruta más barata) consiste en encontrar una ruta o camino óptimo entre un nodo fuente y un nodo destino, los cuales están enlazados a través de una red con arcos que poseen un cierto atributo, el cual puede ser costo, distancia, tiempo, etc.

La Programación Entera permite abordar de forma eficiente este tipo de problemas, en especial cuando la cantidad de nodos y rutas posibles resulta ser un número significativo. Utilizar en estos casos un enfoque intuitivo de resolución es tedioso y de no ser exhaustivo no garantiza la identificación de la mejor alternativa o ruta.

Consideremos el siguiente diagrama donde los números asignados a cada uno de los arcos representan la distancia en kilómetros de un nodo a otro. Se desea encontrar la ruta con la distancia mínima para ir del nodo 1 al nodo 8.

El tamaño reducido de la red anterior permite encontrar el camino más corto simplemente enumerando las distintas alternativas que comenzando en el nodo 1 permita llegar al nodo 8. De esta forma las rutas posibles son:

• Ruta 1-2-5-7-8: 4+8+17+9=38[km]
• Ruta 1-3-4-7-8: 3+12+20+9=44[km]
• Ruta 1-3-4-6-8: 3+12+2+22=39[km]
• Ruta 1-3-4-8: 3+12+15=30[km]
• Ruta 1-3-6-8: 3+4+22=29[km]

La ruta o camino más corto e

 se formula un modelo de Programación Entera que permite extender este tipo de resultados a un problema de estas características:

Variables de Decisión:

Función Objetivo: Minimizar la distancia total en [km] dada por la siguiente expresión:

Restricciones:

1. La primera restricción (1) garantiza que sólo un nodo (entre el 2 y el 3) pueda ser el que se visita a continuación de comenzar en el nodo 1.
2. La restricción (2) determina que si se visito el nodo 2 después del nodo 1, entonces necesariamente el nodo 5 será visitado después del nodo 2.
3. La restricción (3) permite verificar que si el nodo 3 fue visitado luego del nodo 1, entonces a continuación se visita el nodo 4 o el nodo 6 (sólo uno de ellos).
4. La restricción (4) establece que si el nodo 5 fue visitado luego del nodo 2, entonces el nodo 7 debe ser visitado luego del nodo 5.
5. La restricción (5) garantiza que si el nodo 4 fue visitado luego del nodo 3, entonces a continuación se visita uno de los siguientes nodo: 7, 8 o 6.
6. La restricción (6) indica que si el nodo 6 fue visitado inmediatamente luego de estar en el nodo 3 o 4, a continuación se visita el nodo 8.
7. La restricción (7) determina que si el nodo 7 fue visitado inmediatamente luego de estar en el nodo 4 o 5, a continuación se visita el nodo 8.
8. Finalmente la restricción (8) asegura que ya sea el nodo 7, 4 o 6 sea el último en visitar previo a terminar la ruta en el nodo 8.

Al implementar en Solver el problema del Camino más Corto o Ruta Mínima anterior se alcanzan los siguientes resultados:

Donde se corrobora que la ruta más corta (solución óptima) corresponde al camino 1-3-6-8 con una distancia total de 29[km] (valor óptimo). 

2.5 PROGRAMACION DE PROYECTOS

Los métodos CPM (método de la ruta critica o del camino critico, critical path method) y PERT (técnica de evaluación y revisión de programa, program evaluation and riview technique), se basan en redes y tiene por objeto auxiliar en la planeación, programación y control de proyectos. Se define un proyecto como un conjunto de actividades interrelacionadas, en la que cada actividad consume tiempo y recursos. El objetivo del CPM y PERT es contar con un método analítico para programar las actividades.

En la siguiente imagen se resumen los pasos de estas técnicas:

 Fases de planeación de un proyecto con CPM o PERT.

Pasos:

1.- Definición  de las actividades del proyecto, relaciones de precedencia y de tiempo.

2.-  Traducción del proyecto a una red que muestre las relaciones de las actividades.

3.- Cálculos específicos de redes, que forman la base del desarrollo del programa del proyecto en función del tiempo.

Es conveniente colocar un bucle entre la fase de programa y la fase de red, para que se hagan actualizaciones y no haya problemas.

Las dos técnicas, CPM y PERT, que se desarrollaron en forma independiente, difieren en que en el CPM se supone duraciones deterministicas de actividad, mientras que en PERT se suponen duraciones probabilísticas.

 Representación en Red de CPM

Cada actividad del proyecto se representa con un arco que apunta en la dirección de avance del proyecto. Los nodos de la red establecen las relaciones de procedencia entre las diferentes actividades del proyecto. Los nodos de la red establecen las relaciones de procedencia entre las diferentes actividades del proyecto.

Para configurar la red se disponen de dos reglas:

Regla 1: cada actividad se representa con un arco, y uno solo.

Regla 2: cada actividad se debe identificar con dos nodos distintos.

La figura siguiente muestra como se puede usar una actividad ficticia para representar dos actividades concurrentes, A y B. por definición, la actividad ficticia, que normalmente se representa con un arco de línea interrumpida, no consume tiempo ni recursos. La inserción de una actividad ficticia en una de las cuatro formas que se ven en la figura, mantiene la concurrencia de A y B, y también proporciona nodos finales únicos para las dos actividades.

Regla 3: Para mantener las relaciones de precedencia correctas, se deben contestar las siguientes preguntas cuando se agrega a la red cada actividad:

a)      ¿Qué actividades deben anteceder inmediatamente a la actividad actual?

b)      ¿Qué actividades deben seguir inmediatamente a la actividad actual?

c)       ¿Qué actividades deben efectuarse en forma concurrente o simultanea con la actividad actual? 

 

 Uso de la actividad ficticia parta tener representación única de las actividades concurrentes A y B.

 Uso de una actividad ficticia para tener representación única de las actividades concurrentes A y B.

Para contestar estas preguntas se podrá necesitar el uso de actividades ficticias, para asegurar las procedencias correctas entre las actividades. Por ejemplo, considere al siguiente segmento de un proyecto:

        1.       La actividad C comienza de inmediato después de haber terminado A y B. 

       2.       La actividad E se inicia después de que solo termino la actividad B.

La parte (a) de la figura 9 muestra la representación incorrecta de esta relación de precedencia, porque pide que A y B terminen antes de poder iniciar E. En la parte B se corrige la situación con el uso de la actividad ficticia.

 Uso de una actividad ficticia para asegurar una relacion de precedencia correcta.

Redes de PERT

El PERT difiere del CPM en que basa la duracion de una actividad en tres estimaciuones:

        1.      Tiempo optimista a,donde se supone que la ejecucion va extremadamente bien.

        2.     Tiempo mas probable m, dond se supone que la ejecucion se hace bajo condiciones normales.

       3.     Tiempo pesimista b, donde se supone que la ejecucion va extremadamente mal.

Se supone que el intervalo (a,b) abarca todas las situaciones posibles de la duracion de una actividad. Por consiguiente, el estimado m debe estar en algun lugar dentro del intervalo (a, b). con base en los estimados (o estimaciones), el tiempo promedio de duracion D, y la varianza v, se calculan como sigue

Los calculos de ruta critica (CPM) se pueden aplicar en forma directa, sustituyendo la estimacion unica D por .

Ahora es posible estimar la probabilidad de que un nodo j en la red suceda en un tiempo programado especificado con anterioridad. . Sea  el tiempo más temprano de ocurrencia del nodo j. como  las duraciones de las actividades que van del nodo de inicio al nodo j son variables aleatorias,  tambien debe de ser una variable aleatoria. Suponiendo que todas las actividades en la red sean estadisticamente independientes, se puede determinar la medida,  y la varianza, var  como sigue. Si solo hay una ruta desde el nodo de inicio hasta el nodo j, la medida es la suma de las duraciones esperadas , para todas las actividades , para todas las actividades a lo largo de esa  ruta, y la varianza es la suma de las varianzas v de las mismas actividades. Por otra parte si hay mas de una ruta que llegue al nodo j, será necesario calcular primero la distribucion estadistica de la duracion de la ruta mas larga, antes de calcular la medida y la varianza correctas.

Este problema es bastante dificil, porque equivalea determinar la distribucion del maximo de varias variables aleatorias. Por consiguiente, una hipotesis simplificadora es calcular la medida y la varianza,    y var , como el de la ruta del nodo j que tenga la suma mayor de duraciones esperadas de las actividades. Si hay dos o más rutas que tienen la misma medida (o promedio), se selecciona la que tenga la varianza mayor, porque refleja la máxima incertidumbre y en consecuencia conduce a un estimado más conservador de las probabilidades.

Una vez calculados la media y la varianza      y var , de la ruta al nodo j , la probabilidad que se realice el nodo j en un tiempo  preestablecido, se calcula con la siguiente formula:

La variable aleatoria estandar z tiene media 0 y desviacion estandar 1. La justificacion para usar la distribucion normal es que  es la suma de variables aleatorias independientes. De acuerdo con el teorema del limite central (o ley de la distribucion de los errores),  esta distribuida normalmente, en forma aproximada.