Investigación de análisis 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

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

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 paso a paso

Seleccionamos la celda con menor valor, es decir la menos costosa, para asignarle la mayor cantidad posible.

Luego esa cantidad asignada se resta a la demanda de Bogotá y a la oferta de la «Planta 3», en un proceso muy lógico. Dado que Bogotá se queda sin demanda esta columna desaparece, y se repite el primer proceso.

Nuevo proceso de asignación

Nuevo proceso de asignación

Nuevo proceso de asignación

Una vez finalizado el cuadro anterior nos daremos cuenta que solo quedará una fila, por ende asignamos las unidades y se ha terminado el método.

El cuadro de las asignaciones (que debemos desarrollarlo paralelamente) queda así:

Los costos asociados a la distribución son:

En este caso el método del costo mínimo presenta un costo total superior al obtenido mediante Programación Lineal y el Método de Aproximación Vogel, sin embargo comúnmente no es así, además es simple de desarrollar y tiene un mejor rendimiento en cuanto a resultados respecto al Método de la Esquina Noroeste.

• Problemas de asignación

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.

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.

• Problema de 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.

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 esta dada por la secuencia 1-3-6-8 con una distancia total de 29[km].

A continuación 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).

• Programación de proyecto(PERT-CPM)

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:

Figura 7. 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 determinísticas 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?