Catedrático:
José María Kury
Catedrática:
María Emilia Recinos Menjivar
Alumno:
Jallyl Alberto Sabat Martinez 20152000312
Asignatura:
Investigación de Operaciones I
Tema:
Modelo de redes
Fecha de entrega:
08 de abril, 2021
Introducción
En la siguiente investigación se abordarán temas como el flujo máximo, red
PERT y CPM, además de terminologías y definición de redes. Mostraremos
ejemplos y elaboración de los mismos paso a paso. Aprenderemos que la
representación de redes se utiliza de manera amplia en áreas tan diversas
como: producción, distribución, planeación de proyectos, localización de
instalaciones, administración de recursos y planeación financiera.
Objetivos
• Definir el concepto de redes al igual que la terminología empleada.
• Explicar la red PERT y CPM además de cómo realizar su elaboración.
• Determinar el procedimiento de solución del algoritmo de la ruta más
corta y flujo máximo.
¿Qué es una red?
Una red consiste en un conjunto de puntos y un conjunto de líneas que unen
ciertos pares de puntos. Los puntos se llaman nodos (o vértices) las líneas se
llaman arco (o ligaduras, aristas o ramas).
Terminologías usadas:
Arcos dirigidos Un arco es dirigido cuando tiene flujo en una sola
dirección y ésta se indica con una cabeza de
flecha al final del arco o línea en la dirección del
flujo.
Arcos no dirigidos Un arco donde se permite el flujo en ambas
direcciones.
Trayectoria Sucesión de arcos distintos que conectan dos nodos.
Trayectoria Una trayectoria dirigida del nodo i al nodo j, es una
dirigida sucesión de arcos cuya dirección (si la tienen) es
hacia el nodo j, de manera que el flujo del nodo i
al nodo j, a través de esta trayectoria, es factible.
Trayectoria no Una trayectoria no dirigida del nodo i al nodo j es una
dirigida sucesión de arcos cuya dirección (si la tienen) puede
ser hacia o desde el nodo j.
Red dirigida Es una red que tiene sólo arcos dirigidos.
Red no dirigida Es una red donde todos sus arcos son no dirigidos.
Red conexa Es una red en la que cada par de nodos está
conectado. Se dice que dos nodos están conectados si
la red contiene al menos una trayectoria no dirigida
entre ellos aparte.
Capacidad de arco Es la cantidad máxima de flujo (quizás infinito)
que puede circular en un arco dirigido.
Nodo fuente (o Tiene la propiedad de que el flujo que sale del
nodo de origen) nodo excede al flujo que entra a él.
Nodo demanda (o Es el caso contrario al nodo fuente, donde el flujo
nodo destino) que llega excede al que sale de él.
Nodo de Satisface la conservación del flujo, es decir, el
trasbordo (o flujo que entra es igual al que sale.
nodo intermedio)
El algoritmo de la ruta más corta consiste 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.
Objetivo de la n-ésima iteración. Encontrar el n-ésimo nodo más cercano al
origen (este paso se repetirá para n=1,2,… hasta que el n-ésimo nodo más
cercano sea el nodo destino).
Datos para la n-ésima iteración. Son los n-1 nodos más cercanos al origen
(encontrados en las iteraciones previas), incluida su ruta más corta y la
distancia desde el origen (estos nodos y el origen se llaman nodos resueltos, el
resto son nodos no resueltos).
Candidatos para el n-ésimo nodo más cercano. Cada nodo resuelto que
tiene conexión directa por una ligadura con uno o más nodos no resueltos,
proporciona un candidato y éste es el nodo no resuelto que tiene la ligadura
más corta (los empates proporcionan candidatos adicionales).
Cálculo del n-ésimo nodo más cercano. Para cada nodo resuelto y sus
candidatos, se suma la distancia entre ellos y la distancia de la ruta más corta
desde el origen a este nodo resuelto. El candidato con la distancia total más
pequeña es el n-ésimo nodo más cercano (los empates proporcionan nodos
resueltos adicionales) y su ruta más corta es la que genera esta distancia.
El algoritmo es muy sencillo y su aplicación se facilita aún más si se utiliza una
tabla que registra el resultado de las iteraciones y permite la
identificación de las conexiones que forman la ruta más corta de la red.
Ejemplo:
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.
Variables de decisión
El nombre de las variables en este caso poco importa, dado que de ser
escogida para la solución básica eso significa simplemente que será empleada
como ruta para ir a rescatar al minero, sin embargo, nada tiene de malo el que
se le pueda asociar con el envío de unidades desde la entrada de la mina hacia
el minero, por ende puede sugerirse este como nombre de las variables.
«Cantidad de unidades enviadas desde el nodo i hacia el nodo j».
X12 = Cantidad de unidades enviadas desde el nodo 1, hacia el nodo 2
X13 = Cantidad de unidades enviadas desde el nodo 1, hacia el nodo 3
X23 = Cantidad de unidades enviadas desde el nodo 2, hacia el nodo 3
X24 = Cantidad de unidades enviadas desde el nodo 2, hacia el nodo 4
X32 = Cantidad de unidades enviadas desde el nodo 3, hacia el nodo 2
X34 = Cantidad de unidades enviadas desde el nodo 3, hacia el nodo 4
X35 = Cantidad de unidades enviadas desde el nodo 3, hacia el nodo 5
X46 = Cantidad de unidades enviadas desde el nodo 4, hacia el nodo 6
X47 = Cantidad de unidades enviadas desde el nodo 4, hacia el nodo 7
X54 = Cantidad de unidades enviadas desde el nodo 5, hacia el nodo 4
X56 = Cantidad de unidades enviadas desde el nodo 5, hacia el nodo 6
X57 = Cantidad de unidades enviadas desde el nodo 5, hacia el nodo 7
X58 = Cantidad de unidades enviadas desde el nodo 5, hacia el nodo 8
X67 = Cantidad de unidades enviadas desde el nodo 6, hacia el nodo 7
X69 = Cantidad de unidades enviadas desde el nodo 6, hacia el nodo 9
X76 = Cantidad de unidades enviadas desde el nodo 7, hacia el nodo 6
X78 = Cantidad de unidades enviadas desde el nodo 7, hacia el nodo 8
X79 = Cantidad de unidades enviadas desde el nodo 7, hacia el nodo 9
X87 = Cantidad de unidades enviadas desde el nodo 8, hacia el nodo 7
X89 = Cantidad de unidades enviadas desde el nodo 8, hacia el nodo 9
Restricciones
Restricciones de Oferta y Demanda
Hay que recordar que el objetivo de este modelo es la consecución de un plan
de ruta que nos permita encontrar al minero lo más pronto posible al recorrer la
distancia mínima posible, por ende la clave para plantear el modelo como si
fuese de transbordo es establecer una demanda y oferta igual a la unidad (1).
X12 + X13 = 1
X69 + X79 + X89 = 1
Restricciones de Balance
X12 + X32 – X23 – X24 = 0
X13 + X23 – X32 – X34 – X35 = 0
X24 + X34 + X54 – X46 – X47 = 0
X35 – X54 – X56 – X57 – X58 = 0
X46 + X56 + X57 – X67 – X69 = 0
X67 + X47 + X57 + X87 – X76 – X78 – X79 = 0
X78 + X58 – X89 = 0
En palabras sencillas: «Todo lo que entra a cada nodo es igual a lo que sale de
él»
Función objetivo
ZMIN = 4X12 + 2X13 + 2X23 + 7X24 + 4X32 + 9X34 + 6X35 + 1X46 + 5X47 +
2X54 + 4X56 + 3X57+ 2X58 + 1X67 + 5X69 + 4X76 + 3X78 + 5X79 + 2X87 +
7X89
Ingresando los datos en WinQSB
Solución:
La ruta más corta para rescatar al minero tiene como distancia total 1600
metros (dado que las distancias estaban dadas en cientos de metros) y es tal
como se muestra en la siguiente gráfica:
Flujo máximo
Cuando se pretende maximizar el flujo a través de una red,
considerando como inicio de la red un nodo llamado fuente y como nodo
final un nodo llamado destino y tomando en cuenta que el flujo en los
arcos es sólo en la dirección que en el diagrama de la red se indica, se
tiene un problema de flujo máximo, en el cual el objetivo es maximizar la
cantidad total de flujo de la fuente al destino.
Este tipo de problema tiene una amplia gama de aplicaciones dentro de las
cuales se pueden mencionar:
1. Maximizar el flujo de cualquier fluido a través de una tubería.
2. Maximizar el flujo de vehículos por un sistema carretero.
3. Maximizar el flujo de insumos o productos desde los proveedores
hacia los clientes de cualquier tipo de empresa.
Para resolver este problema, se requiere una red conexa dirigida,
identificar los nodos fuente y destino, así como conocer, por lo general, los
límites máximos permisibles de flujo en cada uno de los arcos dirigidos
de la red. Con el diagrama de la red y los datos mencionados se utiliza un
algoritmo para obtener la solución.
Ejemplo Flujo Máximo
Desde el punto de vista de la Programación Entera podemos plantear la
situación de la siguiente forma:
Variables de Decisión:
Función Objetivo: Maximizar las unidades que salen del nodo de origen (1) a
los que éste conecta (2, 4 y 5) o alternativamente maximizar las unidades que
llegan al nodo de destino (8) desde los que conectan a él (3, 6 y 7).
Restricciones:
Restricciones de Flujo Máximo: La cantidad de unidades que sale de cada
nodo de origen a un nodo de destino no puede superar la capacidad detallada
en el arco, por ejemplo, del nodo 1 al nodo 2 sólo se pueden enviar 7 unidades.
Restricciones de Balance de Flujo en los Nodos: Debe existir un equilibrio
entre la cantidad de unidades que llega a un nodo y las que de éste salen, por
ejemplo, el número de unidades que se envía desde el nodo 1 al 4 (si es que
así fuese el caso) debe ser igual a lo que desde el nodo 4 se envían al nodo 3 y
6.
No Negatividad e Integralidad: Las variables de decisión de decisión deben
cumplir las condiciones de no negatividad. Adicionalmente exigiremos que
éstas adopten valores enteros aun cuando se podría flexibilizar dicha situación
lo que daría origen a un problema de Programación Lineal.
Luego de implementar el modelo de optimización anterior con Solver se
alcanza la siguiente solución óptima y valor óptimo:
Notar que el flujo máximo de unidades que puede llegar al nodo de destino
son 32 unidades (valor óptimo) donde cualquiera de las funciones objetivos
propuestas proporciona el mismo resultado (en particular hemos utilizado la
primera de ellas). Los valores de las celdas en color amarillo representan la
solución óptima, es decir, la cantidad de unidades que fluyen en cada
combinación de un nodo origen destino.
El PERT/CPM fue diseñado para proporcionar diversos elementos útiles de
información para los administradores del proyecto. Primero, el PERT/CPM
expone la «ruta crítica» de un proyecto. Estas son las actividades que limitan la
duración del proyecto.
En otras palabras, para lograr que el proyecto se realice pronto, las actividades
de la ruta crítica deben realizarse pronto. Por otra parte, si una actividad de la
ruta crítica se retarda, el proyecto como un todo se retarda en la misma
cantidad. Las actividades que no están en la ruta crítica tienen una cierta
cantidad de holgura; esto es, pueden empezarse más tarde, y permitir que el
proyecto como un todo se mantenga en programa. El PERT/CPM identifica
estas actividades y la cantidad de tiempo disponible para retardos.
El PERT/CPM también considera los recursos necesarios para completar las
actividades. En muchos proyectos, las limitaciones en mano de obra y equipos
hacen que la programación sea difícil. El PERT/CPM identifica los instantes del
proyecto en que estas restricciones causarán problemas y de acuerdo a la
flexibilidad permitida por los tiempos de holgura de las actividades no críticas,
permite que el gerente manipule ciertas actividades para aliviar estos
problemas.
El método del camino crítico es un proceso administrativo de planeación,
programación, ejecución y control de todas y cada una de las actividades
componentes de un proyecto que debe desarrollarse dentro de un tiempo
crítico y al costo óptimo.
Dos son los orígenes del método del camino crítico: el método PERT (Program
Evaluation and Review Technique) desarrollo por la Armada de los Estados
Unidos de América, en 1957, para controlar los tiempos de ejecución de las
diversas actividades integrantes de los proyectos espaciales, por la necesidad
de terminar cada una de ellas dentro de los intervalos de tiempo disponibles.
Fue utilizado originalmente por el control de tiempos del proyecto Polaris y
actualmente se utiliza en todo el programa espacial.
Fases para la planificación de un proyecto con PERT
Paso 1: Actividades del proyecto
Paso 2: Calcular el tiempo estimado (Duración promedio) y la varianza
Paso 3: Diagrama de red
Paso 4: Calcular la red
Paso 5: Cálculo de la varianza, desviación estándar y probabilidades
Paso 6: Establecer el cronograma
Ejemplo de diagrama de PERT:
El método CPM (Crítical Path Method), el segundo origen del método actual,
fue desarrollado también en 1957 en los Estados Unidos de América, por un
centro de investigación de operaciones para la firma Dupont y Remington
Rand, buscando el control y la optimización de los costos de operación
mediante la planeación adecuada de las actividades componentes del
proyecto.
Pasos clave en el método de la Ruta Crítica
Existen seis pasos en el método de la ruta crítica:
• Paso1: Especificar cada actividad
• Paso 2: Definir las dependencias (secuencia de la actividad)
• Paso 3: Dibujar el diagrama de red
• Paso 4: Calcular el tiempo de finalización de la actividad
• Paso 5: Identificar la ruta crítica
• Paso 6: Actualice el diagrama de la ruta crítica para mostrar el progreso
Ejemplo de diagrama CPM:
Veamos un ejemplo sencillo, que es similar al de un diagrama PERT.
Imaginemos una empresa que tiene cuatro actividades: A,B, C y D. La última
(D) recibe de B y C, por tanto, creamos una ficticia (Fb) que no consume
tiempos ni recursos. Esta solo sirve para cumplir los requisitos básicos del
diagrama.
Ahora rellenamos los tiempos más tempranos (T1) partiendo de cero en A y
sumando el del nódulo anterior a la siguiente tarea. Cuando lleguen dos tareas
al mismo nódulo se escoge la de mayor T1. La última será la suma de las
tareas anteriores. Ahora calculamos T2 partiendo del nódulo 4 y restando los
tiempos en vez de sumar. Si llegan dos cogemos el menor de ellos.
Como último paso del diagrama CPM calculamos las holguras (H) como la
diferencia entre T1 y T2. Como vemos, al inicio los tiempos quedarán a cero y
en el último nódulo se refleja el tiempo máximo y mínimo de ejecución (que son
iguales). La ruta crítica (azul oscuro) será aquella en que los nódulos no tengan
holgura (H=0).
Conclusiones
• La técnica de la ruta más corta nos sirve para determinar la ruta más
corta desde nuestro nodo de origen y nuestra ruta de transporte.
• Podemos decir que los arcos son los conectores de nodos dentro de
cada red, estos modelos pueden tener una dirección directa o indirecta.
• La técnica de flujo máximo determina cuanto es lo más que puede fluir
dentro de una red.
Bibliografía
• [Link]
investigacion-de-operaciones#:~:text=Una%20red%20consiste%20en
%20un,ligaduras%2C%20aristas%20o%20ramas
• [Link]
operaciones/algoritmo-de-la-ruta-mas-corta/
• [Link]
problema-del-flujo-maximo-en-programacion-entera-resuelto-con-solver/
• [Link]
de-decisiones/apuntes/mate-negocios-unidad-6-apuntes-
123/11062234/view
• [Link]
