INGENIERÍA INDUSTRIAL

INVESTIGACION DE OPERACIONES II

SHIRLEY KAROLINNE SÁNCHEZ CASANOVA

MARTINEZ SALDAÑA PETE GARY
ESPINOSA CAMPOS MIGUEL ANGEL
SANCHEZ HERNANDEZ FROILAN

INVESTIGACION DE OPTIMIZACION DE
REDES

Catedratica Maria Elena Garcia Alvarado

19/Octubre/2020
TERMINOLOGÍA
Una red o grafo consiste de puntos, y líneas que conectan pares de puntos.
Los puntos se llaman nodos o vértices. Las líneas de llaman arcos. Los arcos
pueden tener una dirección asociada, en cuyo caso se denominan arcos
dirigidos. Si un arco no tiene dirección normalmente se le denomina rama. Si
todos los arcos en la red son dirigidos, la red se denomina una red dirigida. Si
todos los arcos son no-dirigidos, la red es una red no-dirigida.
Dos nodos pueden estar conectados por un conjunto de arcos. Una trayectoria
(path en inglés) es una secuencia de arcos distintos (con nodos no repetidos)
conectando a los nodos. Una trayectoria dirigida desde nodo i al nodo j es una
secuencia de arcos, cada uno de los cuales apunta al nodo j (si es que hay
dirección). Una trayectoria no dirigida puede incluir arcos dirigidos apuntando
en cualquiera de dirección.
Una trayectoria que comienza y que termina en el mismo nodo se denomina
ciclo y puede ser ya sea dirigida o no-dirigida.
Una red está conectada si existe una trayectoria no-dirigida entre cualquier par
de nodos. Una red conectada que no tiene ciclos se denomina árbol.
Optimización de redes es un tipo especial de modelo en programación lineal.
Los modelos de redes tienen tres ventajas importantes con respecto a la
programación lineal.
Pueden resolverse muy rápidamente. Problemas que con programación lineal
tendrían 1000 filas y 30.000 columnas pueden ser resueltos en segundos. Esto
permite que los modelos de redes sean usados en muchas aplicaciones (tal
como la toma de decisión en tiempo real) para lo cual la programación lineal no
es lo ideal.
Requieren en forma natural de soluciones enteras. Al reconocer que un
problema puede formularse como algún modelo de red nos permitirá resolver
tipos especiales de problemas de programación entera aumentando la
eficiencia y reduciendo el tiempo consumido por los algoritmos clásicos de
programación lineal.
Son intuitivos. Los modelos de redes proveen un lenguaje para tratar los
problemas, mucho más intuitivo que "variables, objetivo, restricciones".
Obviamente los modelos de redes no son capaces de cubrir la amplia gama de
problemas que puede resolver la programación lineal. Sin embargo, ellos
ocurren con suficiente frecuencia como para ser considerados como una
herramienta importante para una real toma de decisiones.
Los problemas de optimización de redes se pueden representar en términos
generales a través de uno de estos cuatro modelos:
 Modelo de minimización de redes (Problema del árbol de mínima
expansión).
  Modelo de la ruta más corta.
 Modelo del flujo máximo.
 Modelo del flujo del costo mínimo.
 Modelo de minimización de redes
El modelo de minimización de redes o problema del árbol de mínima expansión
tiene que ver con la determinación de los ramales que pueden unir todos los
nodos de una red, tal que minimice la suma de las longitudes de los ramales
escogidos. No se deben incluir ciclos en la solución del problema.
Para crear el árbol de expansión mínima tiene las siguientes características:
1. Se tienen los nodos de una red pero no las ligaduras. En su lugar se
proporcionan las ligaduras potenciales y la longitud positiva para cada una si se
inserta en la red. (Las medidas alternativas para la longitud de una ligadura
incluyen distancia, costo y tiempo.)
2. Se desea diseñar la red con suficientes ligaduras para satisfacer el requisito
de que haya un camino entre cada par de nodos.
3. El objetivo es satisfacer este requisito de manera que se minimice la longitud
total de las ligaduras insertadas en la red.
Una red con n nodos requiere sólo (n-1) ligaduras para proporcionar una
trayectoria entre cada par de nodos. Las (n-1) ligaduras deben elegirse de tal
manera que la red resultante formen un árbol de expansión. Por tanto el
problema es hallar el árbol de expansión con la longitud total mínima de sus
ligaduras.
PROBLEMA DE LA RUTA MAS CORTA
CONCEPTOS BÁSICOS
El problema de la ruta más corta es uno de los problemas más importantes de
optimización combinatoria con muchas aplicaciones, tanto directas como
subrutinas en otros algoritmos de optimización combinatoria. Los algoritmos
para este tipo de problemas han sido estudiados desde la década de los 50’s y
continúan siendo un área activa de investigación. De hecho, ha sido el objetivo
de una investigación extensiva durante muchos años y ha dado como resultado
la publicación de un gran número de documentos científicos.
Encontrar la ruta más corta entre dos nodos de una red, en la cual cada arco
tiene un costo (o longitud) no negativo es un problema que a menudo se
presenta en cierto tipo de actividades. El objetivo es minimizar el costo (tiempo
o longitud) total.
El ejemplo más sencillo para explicar el problema de la ruta más corta es tomar
el viaje de una persona que quisiera ir de la Ciudad de México a la ciudad de
Monterrey, Nuevo León, podría tener varias alternativas dependiendo de sus
intereses, es decir, si deseara llegar más rápido (minimizando el tiempo o la
distancia) o de una forma más económica (minimizando el costo), toda vez que
cada carretera tiene una longitud específica (kms.) y un precio por el derecho
de transitar en ella (costo). Entonces, el problema consiste en encontrar la ruta
más eficiente (la ruta mínima) con base en la longitud o el costo. Este problema
se representa por una red, donde las ciudades son identificadas por nodos y
las carreteras por arcos.
CARACTERISTICAS
 La amplia variedad de aplicaciones prácticas como es el envío de algún
material entre dos puntos específicos de la forma más eficiente,
económica o rápida.
 Existen métodos de solución eficientes, los cuales al ser aplicados a
una red con características específicas (acíclica y con costos no
negativos), proveen una solución exacta a un tiempo y costo razonables.
 Se puede utilizar como inicio en el estudio de modelos complejos de
redes, esto es, cuando no se conoce la estructura de la red se pueden
aplicar algoritmos para conocer algunas características de la red
(presencia de ciclos negativos).
 Se utiliza frecuentemente como subproblemas (subrutinas) en la
solución de problemas combinatorios y redes, así en el caso de
problemas para los cuales no existe un algoritmo de solución exacto (p.
e. problemas NPcompletos), la aplicación de algoritmos de ruta más
corta, resultan auxiliares para encontrar una buena solución.

APLICACIONES
El problema de ruta más corta tiene muchas aplicaciones prácticas, algunas
son: encontrar la ruta más corta o más rápida entre dos puntos en un mapa,
redes eléctricas, telecomunicaciones, transporte, planeación de tráfico urbano,
trasbordo, diseño de rutas de vehículos, planeación de inventarios,
administración de proyectos, planeación de producción, horarios de operadores
telefónicos, diseño de movimiento en robótica, redes de colaboración entre
científicos, reemplazo de equipo, etc.
Además, como se mencionó anteriormente los algoritmos de solución pueden
adaptarse en la búsqueda inicial de una solución aproximada de problemas
complejos, esto significa que la aplicación consiste precisamente en proveer
estructura para varios problemas de optimización combinatoria como: el
problema de la mochila, secuencia de alineación en biología molecular
(secuenciación del ADN), el problema del agente viajero, etc.
TERMINOLOGIA
NodosA, B, C, D , E
Arcos A—>B, A—>C, A—>D, B—>C, C—>E, D—>E, E—>D
Arco Dirigido AB, AC, AD, BC, CE, DE, ED
Trayectoria Entre A y D: A—>D A—>C—>E—>D A—>B—>C—>E—>D
Trayectoria Dirigida Entre A y E A—>B—>C—>E
Trayectoria No Dirigida Entre B y D B—>C—>—>A—>D
Ciclo DE-ED (ciclo dirigido) AB-BC-CA (ciclo no dirigido)
Red Conexa Si es red conexa
Capacidad de Arco 3, 2, 5, 3, 4, 2, 1
Nodo Fuente A
Nodo Demanda C, D
Nodo trasbordo B
Gráfica. G = (V, E), es una gráfica formada por el conjunto de nodos (vértices)
V y el conjunto de arcos (aristas) E.

Gráfica No Dirigida. En una gráfica no dirigida un arco es un par no ordenado

de nodos, las conexiones son bidireccionales, es decir, el orden no importa.
G = (V, E), donde:
V = {a, b, c, d, e, f}
E = {(a, b), (a, d), (b, c), (b, d), (b, e), (c, e), (c, f), (d, e), (e, f)}

Sin embargo, como el orden de los arcos no importa el arco (a, b) también
puede considerarse como (b, a), siendo lo mismo para todos los demás arcos.

Gráfica Dirigida o Digráfica.

En una gráfica dirigida un arco es un par ordenado. Esto es, si (a, b) es un
arco dirigido, entonces a es el nodo inicial (el arco sale del nodo) y b es el nodo
final (el arco entra al nodo). La conexión es únicamente del nodo inicial al nodo
final.
V = {a, b, c, d, e, f}
E = {(a, b), (a, d), (b, c), (b, d), (b, e), (c, e), (c, f), (d, e), (e, f)}

Gráfica Simple.
Esta gráfica considera un nodo fuente (únicamente salen arcos) y un nodo
sumidero (únicamente entran arcos). No existen arcos múltiples, es decir, dos
nodos están conectados por un arco o por ninguno, tampoco existen rizos, esto
es, ningún nodo está conectado a sí mismo por un arco.
Por lo general, cuando no se hace especificación se consideran gráficas
simples.

Gráfica Múltiple.
Existe la posibilidad de varios arcos entre el mismo par de nodos.
Gráfica Conectada.
Todos los nodos están conectados directa o indirectamente a todos los demás
nodos, esto es, existe una ruta desde cualquier nodo a cualquier otro nodo de
la red.

Gráfica Bipartita.
Los nodos de la gráfica se dividen en dos conjuntos, con la característica de
que todos los arcos conectan a los nodos desde un conjunto al otro.

Grado.
Es el número de arcos incidentes en un nodo.

Nodos Adyacentes.
Son los nodos conectados por un arco.

Arcos Incidentes.
Un arco e es incidente en un nodo v si v es el extremo de e.

Ruta.
Una ruta en una gráfica dirigida es una secuencia de nodos y arcos, además se
requiere que todos los nodos sean diferentes. En el caso de que algunos nodos
o arcos se repitan en la secuencia, se conoce como camino. Etc.

EJEMPLO
Para solucionar el problema de la ruta más corta existen varios algoritmos
eficientes, con los cuales dependiendo de las características de la red (p. e.
con costos no negativos), se puede obtener una solución exacta en un tiempo
razonable.

Líneas Fairway Van

 Determine la ruta mas corta entre Seattle y El Paso para la siguiente red
de carreteras.
 Solución- Analogía de un problema de programación lineal.

Variables de decisión
Solución-
Analogía de un problema de programación lineal.
– Variables de Decisión
 Problema de flujo de costo mínimo
El método del costo mínimo o método de los mínimos costos es un
algoritmo desarrollado con el objetivo de resolver problemas de transporte o
distribución, arrojando mejores resultados que métodos como el de la esquina
noroeste, dado que se enfoca en las rutas que presentan menores costos.
Este algoritmo es mucho más sencillo que los anteriores, dado que se trata
simplemente de la asignación de la mayor cantidad de unidades posibles
(sujeta a las restricciones de oferta y/o demanda) a la celda menos costosa de
toda la matriz hasta finalizar el método.

Algoritmo del Costo Mínimo

Paso 1
De la matriz se elige la ruta (celda) menos costosa (en caso de un empate, este
se rompe arbitrariamente) y se le asigna la mayor cantidad de unidades
posible, cantidad que se ve restringida ya sea por las restricciones de oferta o
de demanda. En este mismo paso se procede a ajustar la oferta y demanda de
la fila y columna afectada, restándole la cantidad asignada a la celda.

Paso 2
En este paso se procede a eliminar la fila o destino cuya oferta o demanda sea
0 después del «Paso 1», si dado el caso ambas son cero arbitrariamente se
elige cual eliminar y la restante se deja con demanda u oferta cero (0) según
sea el caso.

Paso 3
Una vez en este paso existen dos posibilidades, la primera que quede un solo
renglón o columna, si este es el caso se ha llegado al final el método,
«detenerse».
La segunda es que quede más de un renglón o columna, si este es el caso
iniciar nuevamente el «Paso 1».

Ejemplo del Método del Costo Mínimo

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.
Formule un modelo de programación lineal que permita satisfacer las
necesidades de todas las ciudades al tiempo que minimice los costos
asociados al transporte.
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.
Algoritmo árbol de expansión mínima

Antes de abordar a profundidad el funcionamiento de este importante algoritmo,

descubramos un poco sobre su historia. Esté algoritmo diseñado para diseñar
un árbol de expansión mínima fue desarrollado por el científico checo Otakar
Boruvka en 1926. Este algoritmo nace en el intento de encontrar una red
eléctrica que fuese eficiente para Moravia (una de las tres regiones
históricas que conforman la República Checa)
Este algoritmo da nacimiento a lo que conocemos como árbol de expansión de
peso mínimo que comienza desde un vértice especificado
La modelación de redes permite la resolución de múltiples problemas de
programación matemática mediante la implementación de algoritmos
especiales creados para tal fin, conocidos como Algoritmos de optimización de
redes. Dentro de los problemas más comúnmente resueltos mediante la
modelación de redes se encuentran los ya vistos modelos de transporte,
transbordo además de los muy conocidos modelos de determinación de
cronograma de actividades para proyectos
El algoritmo del árbol de expansión mínima es un modelo de optimización de
redes que consiste en enlazar todos los nodos de la red de forma directa y/o
indirecta con el objetivo de que la longitud total de los arcos o ramales sea
mínima (entiéndase por longitud del arco una cantidad variable según el
contexto operacional de minimización, y que puede bien representar una
distancia o unidad de medida).
Sean:
N = {1,2, 3, n} el conjunto de nodos de la red.

Ck= Conjunto de nodos que se han enlazado de forma permanente en la

iteración k

Čk= Conjunto de nodos que hacen falta por enlazarse de forma permanente.

Paso cero (0): Conceptualización del algoritmo

Definir los conjuntos C0 = {ø} y Č0 = {N}, es decir que antes del paso 1 no se
han enlazado de forma permanente nodo alguno, y por ende el conjunto que
representa a los nodos que hacen falta por enlazarse de forma permanente es
igual a la cantidad de nodos que existen en la red.
Paso 1:
Se debe de escoger de manera arbitraria un nodo en el conjunto Č 0 llamado i el
cual será el primer nodo permanente, a continuación, se debe de actualizar el
conjunto C1 = {i}, que significa que al tiempo en que el conjunto C 1 gana el
elemento i el conjunto Č0pierde el elemento i por ende ahora será igual a Č1 =
N – {i}, además se debe actualizar el subíndice de los conjuntos k, el cual ahora
será igual a 2.

Paso 2: Paso general «K»

Se debe de seleccionar un nodo j del conjunto ČK-1 («k-1» es el subíndice que
indica que se está haciendo referencia al conjunto de la iteración
inmediatamente anterior) el cual tenga el arco o ramal con menor longitud con
uno de los nodos que se encuentran en el conjunto de nodos de enlace
permanente CK-1. Una vez seleccionado se debe de enlazar de forma
permanente lo cual representa que pasa a formar parte del conjunto de enlaces
permanentes y deja de formar parte del conjunto que todavía se debe conectar
para lograr la expansión. Al actualizar el algoritmo en este paso los conjuntos
deben de quedar de la siguiente forma.
CK = CK-1 + {j} mientras que ČK = ČK-1 – {j}

El paso general que define k que al mismo tiempo representa a las iteraciones
debe de ejecutarse toda vez que el conjunto ČK no sea vacío, cuando este
conjunto sea igual a vacío se tendrá el árbol de expansión mínima.

Solución de un problema de árbol de expansión mínima

El problema
La ciudad de Cali cuenta con un nuevo plan parcial de vivienda el cual
contará con la urbanización de más de 7 proyectos habitacionales que se
ubicarán a las afueras de la ciudad. Dado que el terreno en el que se construirá
no se encontraba hasta ahora dentro de las zonas urbanizables de la ciudad, el
acueducto municipal no cuenta con la infraestructura necesaria para satisfacer
las necesidades de servicios públicos en materia de suministro de agua. Cada
uno de los proyectos de vivienda inició la construcción de un nodo de
acueducto madre, el cual cuenta con las conexiones de las unidades de
vivienda propias de cada proyecto (es decir que cada nodo madre solo necesita
estar conectado con un ducto madre del acueducto municipal para contar con
su suministro). El acueducto municipal al ver la situación del plan parcial debe
de realizar las obras correspondientes a la instalación de ductos madres que
enlacen todos los nodos del plan con el nodo Meléndez (nodo que se
encuentra con suministro de agua y que no pertenece al plan parcial de
vivienda, además es el más cercano al mismo), la instalación de los ductos
implica obras de excavación, mano de obra y costos de los ductos mismos, por
lo cual optimizar la longitud total de los enlaces es fundamental. Las distancias
existentes (dadas en kilómetros) correspondientes a las rutas factibles capaces
de enlazar los nodos del plan parcial se presentan a continuación. Además, la
capacidad de bombeo del nodo Meléndez es más que suficiente para satisfacer
las necesidades de presión que necesita la red madre.

El acueducto municipal le contacta a usted para que mediante sus

conocimientos en teoría de redes construya una red de expansión que
minimice la longitud total de ductos y que enlace todos los nodos del plan
parcial de vivienda.
PASO 0:
Se definen los conjuntos iniciales C0 = {ø} que corresponde al conjunto
de nodos enlazados de forma permanente en la iteración indicada en el
subíndice y Č0 = {N = 1,2,3,4,5,6,7,8} que corresponde al conjunto de nodos
pendientes por enlazar de manera permanente en la iteración indicada en el
subíndice.

PASO 1:
Se debe definir de manera arbitraria el primer nodo permanente del
conjunto Č0, en este caso escogeremos el nodo 1 (puede ser cualquier otro),
que algebraicamente se representa con la letra i, se procede a actualizar los
conjuntos iniciales, por ende, C1 = {i} = {1} y Č0 = {N – i} = {2,3,4,5,6,7,8},
actualizamos k por ende ahora será igual a 2.

PASO 2:
Ahora se debe seleccionar el nodo j del conjunto ČK-1 (es decir del
conjunto del paso 1) el cual presente el arco con la menor longitud y que se
encuentre enlazado con uno de los nodos de enlace permanente del conjunto
Ck-1 en el cual ahora solo se encuentra el nodo 1 (es decir que se debe de
encontrar un nodo que tenga el arco de menor longitud enlazado al nodo 1).

Los arcos o ramales de color naranja representan los arcos que enlazan el
conjunto ČK-1 (es decir del conjunto del paso 1, recordemos que K en este
paso es igual a 2, por ende, ČK-1= Č1) con los nodos de enlace permanente
del conjunto Ck-1 en el cual ahora solo se encuentra el nodo 1, por ende, ahora
solo falta escoger el de menor longitud, que en este caso es el arco cuya
longitud es 2, que enlaza de forma permanente ahora el nodo 2.
Al actualizar los conjuntos quedan así:
C2 = {1,2} y Č2 = {3,4,5,6,7,8}
Ahora se procede a actualizar k ya que se procede a efectuar la siguiente
iteración. Ahora se seleccionará un nuevo nodo j del conjunto Č2que presente
el enlace (ramal o arco) de menor longitud con los nodos que se encuentran en
el conjunto C2.
Los arcos de color naranja representan los enlaces posibles y dado que existe
empate entre las menores longitudes se elige de manera arbitraria, en este
caso se representa nuestra elección con un arco de color verde, enlazando de
forma permanente ahora el nodo 4.
Al actualizar los conjuntos quedan así:
C3 = {1,2,4} y Č3 = {3,5,6,7,8}

Ahora se procede a actualizar k ya que se procede a efectuar la siguiente

iteración.

Lo que representan los arcos naranja y verde es ya conocido, ahora la línea

azul interrumpida irá trazando nuestro árbol de expansión final. Dado a que el
arco menor es el de longitud 3, ahora se enlazará de manera permanente el
nodo 5.
Al actualizar los conjuntos quedan así:
C4 = {1,2,4,5} y Č4 = {3,6,7,8}
Ahora se procede a actualizar k ya que se procede a efectuar la siguiente
iteración.

Ahora se enlazará de manera permanente el nodo 7.

Al actualizar los conjuntos quedan así:
C5 = {1,2,4,5,7} y Č5 = {3,6,8}
Ahora se procede a actualizar k ya que se procede a efectuar la siguiente
iteración.

Ahora se enlazará de manera permanente el nodo 6.

Al actualizar los conjuntos quedan así:

C6 = {1,2,4,5,7,6} y Č6 = {3,8}
 Ahora se procede a actualizar k ya que se procede a efectuar la
siguiente iteración.

Se rompen los empates de forma arbitraria, ahora se enlazará de

manera permanente el nodo 3.

Al actualizar los conjuntos quedan así:

C7 = {1,2,4,5,7,6,3} y Č7 = {8}
 Ahora se procede a actualizar k ya que se procede a efectuar la última
iteración.

Ahora se enlazará de manera permanente el nodo 8.

Al actualizar los conjuntos quedan así:

C8 = {1,2,4,5,7,6,3,8} = {N} y Č8 = {ø}

Por ende, se ha llegado al árbol de expansión mínima

APLICACIÓN DEL MODELO PERT CPM”
1. 1. Tema: “APLICACIÓN DEL MODELO PERT CPM” INTRODUCCIÓN
La problemática de la planeación de proyectos no ha sido una problemática
reciente, si no que desde tiempos pasados nuestros antepasados han
enfrentado emprendimientos de gran envergadura que significaron una
problemática desde el punto de la planificación. Actualmente se han logrado
perfeccionar herramientas que permiten a los administradores de dichos
proyectos, realizar una labor más eficiente permitiendo una óptima aplicación
de los recursos en las mismas y logrando una maximización de los mismos.
Admitiendo que la ejecución de un proyecto o elaboración se puede subdividir
en planear, programar y controlar, y hablando de manera clásica, podemos
considerar las técnicas PERT (Program Evaluación and review Technique) y el
CPM (Critical Path Method,) que son los más usuales para un primer cometido.
En general estas técnicas resultan útiles para una gran variedad de proyectos
que contemplen: Investigación y desarrollo de nuevos productos y procesos.
Construcción de plantas, edificios, y carreteras. Diseño de equipo grande y
complejo. Diseño e instalación de sistemas nuevos. Diseño y control de
epidemias, y otras múltiples aplicaciones en las cuales se requiera una
planificación adecuada. En los proyectos como estos, los administradores
deben programas, coordinar las diversas tareas o actividades a desarrollar un
proyecto, las cuales no necesariamente son secuenciales, y aun en este caso
estas actividades son interdependientes. Si bien es cierto que, algunas
actividades en paralelo que originan una tercera. Las preguntas esenciales de
la elaboración de un proyecto comprenden:
2.
3. 2. Cuál es el tiempo que se requiere para terminar el proyecto. Cuáles
son las fechas programadas de inicio y finalización del proyecto. Que
actividades son críticas y deben terminarse exactamente según lo programado
para poder mantener el proyecto según el cronograma. Cuales actividades
pueden ser demoradas sin afectar el tiempo de terminación del proyecto.
OBJETIVOS OBJETIVO GENERAL Comprender la aplicación del método
PERT- CPM OBJETIVOS ESPECÍFICOS Determinar la importancia que tiene
el modelo PERT – CPM Explicar detalladamente la metodología que utiliza el
modelo PERT- CPM Realizar una investigación minuciosa sobre el modelo
PERT- CPM ya que esto nos ayudara a despejar todas las dudas existentes en
esta investigación.

JUSTIFICACIÓN
Se realizara esta investigación ya que es importante conocer ampliamente de
que se trata el método PERT CPM para poder desarrollar de forma correcta la
investigación teniendo así que 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. 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

5. 4. Según MONTAÑO, Agustín. Iniciación al Método del Camino Crítico.

1972. Editorial Trillas, S.A. México. D.F. México (Internet). Los métodos y
avances científicos han permitido demostrar cuales son las posibles soluciones
más viables a estas diatribas, así como el crecimiento acelerado de la ciencia
se han logrado discrepar en cierta proporción lo que tiene que tiene que ver
con los eventos y las actividades, aplicando estas herramientas, se combina en
forma integral para producir una técnica más depurada y flexible en las
actividades gerenciales. Según Frederick S. Hillier, Gerald J. Lieberman;
Introducción a la Investigación de Operaciones, Quinta edición, Edit. McGraw
Hill, México 1993 (Internet) El método PERT y CPM tiene muchas aplicaciones
que oscilan desde le planeación y control de proyectos, construcción de
puentes edificios, desarrollos industriales, instalación de equipos electrónicos,
grandes operaciones comerciales etc.; sin embargo lo diversificado de la
aplicación del PERT y CPM ha mostrado la calidad en todos estos campos,
dándoles información inmediata al ámbito correspondiente para la toma de
decisión de la forma de acción más conveniente. Esta técnica nos permite la
cimentación y visualización de un diagrama de red representando cada
actividad (etapa) mediante una flecha llamada arco. Así miso las redes tienen
un papel importante en el manejo de los proyectos permitiendo demostrar las
relaciones entre las actividades, además el nodo en el diagrama de red es un
aspecto de mucha importancia en un problema como la fuente y destinación de
bienes, sin dudas el PERT y CPM es una herramienta de estudios múltiples
con una serie de elementos Inter conectados por lo que se requiere desde
interpretaciones reales y objetivas al momento de ser empleadas, pero con la
convicción de que sus resultados serán beneficiosos al cumplimiento de las
metas de las metas planeadas en los diversos campos. 1.1. USOS Según
MOSKOWITZ, Herbert y Gordon P. Wrigth. Investigación de Operaciones.
1982. Prentice Hall Hispanoamericana, S.A. Naucalpan de Juárez. México
(Internet). El campo de acción de este método es muy amplio, dada su gran
flexibilidad y adaptabilidad a cualquier
6.
7. 5. proyecto grande o pequeño. Para obtener los mejores resultados debe
aplicarse a los proyectos que posean las siguientes características: Que el
proyecto sea único, no repetitivo, en algunas partes o en su totalidad. Que se
deba ejecutar todo el proyecto o parte de él, en un tiempo mínimo, sin
variaciones, es decir, en tiempo crítico. Que se desee el costo de operación
más bajo posible dentro de un tiempo disponible. Dentro del ámbito aplicación,
el método se ha estado usando para la planeación y control de diversas
actividades, tales como construcción de presas, apertura de caminos,
pavimentación, construcción de casas y edificios, reparación de barcos,
investigación de mercados, movimientos de colonización, estudios económicos
regionales, auditorías, planeación de carreras universitarias, distribución de
tiempos de salas de operaciones, ampliaciones de fábrica, planeación de
itinerarios para cobranzas, planes de venta, censos de población, etc.
1.2.DIFERENCIAS ENTRE PERT Y CPM TAHA,
Hamdy A. Investigación de Operaciones, Una Introducción. 1989. Ediciones
Alfaomega, S.A. México. D.F. México (Internet). Como se indicó antes, la
principal diferencia entre PERT y CPM es la manera en que se realizan los
estimados de tiempo. E1 PERT supone que el tiempo para realizar cada una de
las actividades es una variable aleatoria descrita por una distribución de
probabilidad. E1 CPM por otra parte, infiere que los tiempos de las actividades
se conocen en forma determinísticas y se pueden variar cambiando el nivel de
recursos utilizados. La distribución de tiempo que supone el PERT para una
actividad es una distribución beta. La distribución para cualquier actividad se
define por tres estimados: El estimado de tiempo más probable, m; El estimado
de tiempo más optimista,

8. 6. El estimado de tiempo más pesimista, b. La forma de la distribución se

muestra en la siguiente Figura. E1 tiempo más probable es el tiempo requerido
para completar la actividad bajo condiciones normales. Los tiempos optimistas
y pesimistas proporcionan una medida de la incertidumbre inherente en la
actividad, incluyendo desperfectos en el equipo, disponibilidad de mano de
obra, retardo en los materiales y otros factores. Con la distribución definida, la
media (esperada) y la desviación estándar, respectivamente, del tiempo de la
actividad para la actividad Z puede calcularse por medio de las fórmulas de
aproximación. El tiempo esperado de finalización de un proyecto es la suma de
todos los tiempos esperados de las actividades sobre la ruta crítica. De modo
similar, suponiendo que las distribuciones de los tiempos de las actividades son
independientes (realísticamente, una suposición fuertemente cuestionable), la
varianza del proyecto es la suma de las varianzas de las actividades en la ruta
crítica. Estas propiedades se demostrarán posteriormente. En CPM solamente
se requiere un estimado de tiempo. Todos los cálculos se hacen con la
suposición de que los tiempos de actividad se conocen. A medida que el
proyecto avanza, estos estimados se utilizan para controlar y monitorear el
progreso. Si ocurre algún retardo en el proyecto, se hacen esfuerzos por lograr
que el proyecto quede de nuevo en programa cambiando la asignación de
recursos. 1.3.Metodología. El Método del Camino Critico consta de dos ciclos:
1. Planeación y Programación. 1.1.- Definición del proyecto 1.2.- Lista de
Actividades 1.3.- Matriz de Secuencias 1.4.- Matriz de Tiempos 1.5.- Red de
Actividades 1.6.- Costos y pendientes 1.7.- Compresión de la red
9. 7. 1.8.- Limitaciones de tiempo, de recursos y económicos 1.9.- Matriz de
elasticidad 1.10.- Probabilidad de retraso 2. Ejecución y Control. 2.1.-
Aprobación del proyecto 2.2.- Ordenes de trabajo 2.3.- Gráficas de control 2.4.-
Reportes y análisis de los avances 2.5.- Toma de decisiones y ajustes 1.4.
Definición del Proyecto En toda actividad a realizar se requieren conocimientos
precisos y claros de lo que se va a ejecutar, de su finalidad, viabilidad,
elementos disponibles, capacidad financiera, etc. Esta etapa, aunque esencial
para la ejecución del proyecto no forma parte del método. Es una etapa previa
que se debe desarrollar separadamente y para la cual también puede utilizarse
el Método del Camino Critico. Es una investigación de objetivos, métodos y
elementos viables y disponibles. 1.5. Lista de Actividades Es la relación de
actividades físicas o mentales que forman procesos interrelacionados en un
proyecto total. En general esta información es obtenida de las personas que
intervendrán en la ejecución del proyecto, de acuerdo con la asignación de
responsabilidades y nombramientos realizados en la Definición del Proyecto.
Las actividades pueden ser físicas o mentales, como construcciones, tramites,
estudios, inspecciones, dibujos, etc. En términos generales, se considera
Actividad a la serie de operaciones realizadas por una persona o grupo de
personas en forma continua, sin interrupciones, con tiempos determinables de
iniciación y terminación. Esta lista de actividades sirve de base a las personas
responsables de cada proceso para que elaboren sus presupuestos de
ejecución.

EJEMPLOS

EJEMPLO DE APLICACIÓN
23. 20. Primeramente se prepara la gráfica de actividades siguiendo la
secuencia lógica ya explicada, respetando las actividades antecedentes. Como
segundo paso se procede a determinar el tiempo esperado Te mediante la
fórmula: El tercer paso consiste en calcular el costo de acelerar la actividad un
día, esto se determina mediante la fórmula: Como tercer paso para de la ruta
crítica se calcula los tiempos más tempranos para cada actividad se comienza
dejando el tiempo como cero en el nodo inicial. Luego, se calcula el intervalo de
tiempo que transcurre entre el inicio y las actividades inmediatas al comienzo
del proyecto. Debido a que la actividad artificial no tiene duración, el tiempo
acumulado al
24. 21. nodo 3 para que sean terminadas todas las actividades
predecesoras a dicho nodo corresponde a 9 días. En otras palabras, el tiempo
más temprano para el nodo 3 es 9 días. Luego, las actividades que comienzan
en el nodo 3 no pueden comenzar antes de 9. A continuación, es posible
completar el intervalo de tiempo de desarrollo para la actividad Finalmente, el
tiempo más temprano para el nodo 5 es de 26 días, por lo que la actividad F
solo puede comenzar en dicho instante. Los intervalos de tiempo más
temprano para todas las actividades del proyecto. A partir de esta figura, se
puede concluir que la duración mínima del proyecto es de 38 días, cantidad
que corresponde al camino más largo para llegar del nodo inicial 1 al nodo al 6.
Como segunda etapa se procede a calcular los tiempos más tarde para cada
nodo. La idea consiste en determinar cuánto es posible retardar el inicio de
cada actividad sin afectar la duración total del proyecto. Para ello se comienza
desde el nodo final. En este caso, dado que existe una única actividad que
llega a dicho nodo no es posible retardarla sin afectar la duración del proyecto.
La figura muestra el intervalo de tiempo más tarde para la última actividad en
paréntesis cuadrado. Las actividades que llegan al nodo 5 terminan a más
tardar en el día 26, por lo tanto, es posible retardar la actividad C en 26 -17 = 9
días. Se incorpora los intervalos de duración de tiempo más tarde a la malla en
la figura. El nodo 4 tiene como tiempo más tarde 26, por lo que no es factible
retardar la actividad D. De esta forma, el nodo 3 tiene como tiempo más tarde 9
días, por lo tanto las actividades deben llegar a más tardar el día 9. Como la
actividad artificial no tiene duración, La actividad B no puede ser retardada. La
actividad A puede ser retardada en 9-6= 3 días. Una actividad crítica es una
actividad que no puede ser retardada sin afectar la duración total del proyecto.
En otras palabras, en el tiempo más temprano y el tiempo más tarde de inicio
de la actividad son idénticos. Un camino desde el nodo inicial al final constituido
solo por actividades críticas se denomina ruta crítica. Es decir, constituye el
camino que no puede ser retrasado sin afectar la duración del proyecto, o bien,
la ruta más larga entre los nodos inicial y final. De acuerdo a las definiciones
anteriores, la ruta crítica del proyecto corresponde a las actividades B- dummy-
D-E-F, las cuales han sido marcadas con una línea más oscura
25. 24. METODOLOGÍA 2.1.Método de Investigación 2.1.1. Investigación
Bibliográfica-Documental La información presentada en este proyecto es de
tipo bibliográfica y documental debido a que fue obtenida de libros y páginas de
internet la información extraída de las diferentes fuentes nos ayudara a
despejar todas las dudas existentes en la elaboración y ejecución del proyecto,
este método nos permitirá concretar el marco conceptual que detalla las bases
de nuestro proyecto objetivo. 2.2.Tipo de investigación 2.2.1. Investigación
Descriptiva Este proyecto es de tipo descriptivo debido a que mediante la
utilización de esta metodología podremos describir las situaciones y eventos
que generan la problemática de estudio la misma que es la aplicación
26. TIPOS DE MODELO PERT- CPM.
27. 2.3. Técnicas de la Investigación
28. 25. 2.3.1. Bibliográfica La técnica que se ha utilizado es la de investigar
en páginas web, en folletos, libros e información extraída de libros básicos de
investigación operativa. CONCLUSIONES Y RECOMENDACIONES 3.1.
CONCLUSIÓN El PERT y CPM han sido aplicados a numerosos proyectos.
Empezando con su aplicación inicial al proyecto Polaris y al mantenimiento de
plantas químicas, hoy ellos (y sus variantes) se aplican a la construcción de
carreteras y de edificios, y al desarrollo y producción de artículos de alta
tecnología tales como aviones, vehículos espaciales, barcos y computadores.
El PERT se desarrolló para proyectos en donde hubiera incertidumbre en el
tiempo de las actividades (usualmente debido a que el proyecto nunca se había
intentado antes y por tanto no había bases de datos, para los tiempos de las
actividades). Esto condujo al enfoque probabilístico que se tomó. Mientras que
en PERT los estimados de tiempo y sus distribuciones han sido de
controversia, el PER'I' ha constituido una herramienta útil para la administración
de proyectos. La principal desventaja es que no es funcional para grandes
proyectos, debido a los tres estimados de tiempo que se requieren en cada
actividad y a la capacidad limitada de los computadores actuales, para
almacenar esta vasta cantidad de datos. Además, el costo de actualizar y
mantener la información del proyecto con el tiempo en ambientes tan
dinámicos, puede ser excesivamente prohibitivo.
29. 26. Por otra parte, el CPM se desarrolló para manejar proyectos
repetitivos o similares (ej., mantenimiento de plantas químicas). Obviamente,
se gana gran cantidad de experiencia con el tiempo en tales circunstancias,
aun cuando dos proyectos puede que no sean iguales. Esta experiencia llevó al
análisis de técnicas de colisión utilizadas en las redes CPM. Mientras que el
CPM y PER'I' son esencialmente lo mismo, sus matices hacen cada uno
aplicable más que el otro en situaciones diferentes. En ambos métodos la
información esencial deseada es la ruta crítica y las holguras. Estas, le
permiten al director del proyecto hacer decisiones con base a información,
basado en el principio de administración por excepción, sobre los planes y
proyectos del trabajo actual y monitorear el progreso del proyecto. 3.2.
RECOMENDACIONES Recomendamos analizar a fondo la información
presentada en la siguiente investigación ya que esto nos ayudara a
comprender de manera fácil la aplicación del modelo PERT-CPM. Se
recomienda poner en práctica la presente investigación debido a que ayudará a
desarrollar correctamente la aplicación de la ruta crítica en un proyecto de
investigación ya que el modelo PERT-CPM se basa fundamentalmente en el
desarrollo de la ruta crítica. Recomendamos la aplicación de método PERT-
CPM ya que este tiene muchas aplicaciones que oscilan desde le planeación y
control de proyectos, construcción de puentes edificios, desarrollos industriales,
instalación de equipos electrónicos, grandes operaciones comerciales. Se
recomienda ampliar la información ya existente ya que pueden existir algunas
dudas que la investigación presente no haya satisfecho aun cuando esta esté
abarcando los temas principales a tratarse dentro del estudio del método PERT
CPM. Recomendamos a los estudiantes tratar a fondo este tema para una fácil
asimilación debido a que existen partes complejas en el proceso de aplicación
del modelo PERT CPM que se entenderán únicamente desarrollando un
ejemplo práctico el mismo que ayudara a despejar todas las incógnitas
existentes en la aplicación del modelo PERT CPM.

ETAPAS, Inicio y el final de la tarea.

Cada tarea tiene una etapa de inicio y una de finalización. Con excepción de
las etapas iniciales y finales, cada etapa final es una etapa de inicio de la
siguiente tarea. Las etapas generalmente están numeradas y representadas
por un círculo, pero en algunos otros casos pueden estar representadas por
otras formas (cuadrados, rectángulos, óvalos, etc.).
TAREAS FICTICIAS
Representadas por una flecha punteada que indica las limitaciones de las
cadenas de tareas entre ciertas etapas.
TAREAS Actividades
Etapas, representadas por una flecha. Se le asigna a cada una de las tareas un
código y una duración. Sin embargo, la longitud de la flecha es independiente
de la duración de la tarea.
ELEMENTOS
Técnicas de revisión Evaluación de Programas (PERT)
RUTA CRITICA
La ruta más larga a través de red
Técnicas de revisión Evaluación de Programas (PERT) PASOS BÁSICOS: 
Definir el proyecto y preparar la estructura desglosada del trabajo.
 Desarrollar las relaciones entre actividades para decidir qué actividad
debe preceder y cual debe seguir a otras.
 Dibujar la red que conecta todas las actividades.
 Asignar estimaciones de costo y/o tiempo de cada actividad.
 Calcular el tiempo de la ruta más larga a través de red: RUTA CRITICA
 Usar la red como ayuda para planear, programar, supervisar y controlar
el proyecto.
Ventajas
 Útil para el control y programación de grandes proyectos.
 Concepto directo y sin complejidad matemática.
 Ayudan al panorama global de las relaciones entre las actividades.
  El análisis de la ruta crítica y el tiempo de holgura ayuda a detectar las
actividades que requieren vigilancia estrecha.
 Los documentos y las gráficas de proyecto señalan quien es el
responsable de varias actividades.
 Se aplica a una amplia variedad de proyectos.
 Útil para supervisar los programas y los costos.

Limitantes
 •Las actividades del proyecto deben definirse con claridad, de
manera independiente y estable en sus relaciones.
 •Las relaciones de precedencia deben ser específicas y seguirse
al elaborar la red.
 •Las extensiones de tiempo tendrán que ser subjetivas y estar
sujetas a márgenes de los administradores que tienen que ser
demasiado optimistas o no suficientemente pesimistas
, •Existe el peligro inherente

PROGRAMACION LINEAL EN TEORÍA DE REDES

La programación lineal es actualmente la técnica matemática utilizada más
actualmente gracias a que el algoritmo simplex es muy eficiente y al desarrollo
de la computación. Lo que se busca con la aplicación de la programación lineal
es resolver problemas comunes y a la vez muy variados de la empresa en
donde en general se tienen necesidades por satisfacer con cierto número de
recursos limitados o escasos y con el objetivo de lograrlo en forma óptima.

Ejemplo
Una empresa ha dejado de fabricar ciertos productos, liberando de esta forma
las cargas de producción que tenían sus equipos en los departamentos de
maquinado. Ahora se tienen horas máquina que se pueden utilizar en los
productos denominados 1,2,3 de la siguiente manera:
Máquina Horas por pieza de producto Horas Maq. Disponibles
1 2 3 por semana
Fresadora 9 3 5 500
Torno 5 4 - 350
Rectificadora 3 - 2 150
Utilidad
$/ pieza 50 20 25
Recomendación del Mínimo Mínimo Mínimo
Depto. Vtas a Prod. 30 15 20

Formular un modelo de Programación Lineal para este problema

 Definición de variables a utilizar en el método de programación lineal
Sea: Xj = número de piezas de producto j(j=1,2,3) a fabricar para maximizar la
utilidad.
 Función económica y objetivo:
MAX Z= 50X1 + 20X2 + 25X3 [ (Dls/Unidad) (Unidad/Sem)] = [Dls/Sem.]
Sujeta a restricciones de horas máquina disponibles por semana
Fresadora: 9X1 + 3X2 + 5X3 * 500 horas máquina fresadora
Torno: 5X1 + 4X2 * 350 horas máquina torno
Rectificadora: 3X1 + 2X3 * 150 horas maquina rectificadora

Condiciones de signos pare las variables:

X1 * 30 piezas
X2 * 15 piezas
X3 * 20 piezas

Problema de flujo máximo

Conceptos generales
Las técnicas de flujo de redes están orientadas a optimizar situaciones
vinculadas a las redes de transporte, redes de comunicación, sistema de
vuelos de los aeropuertos, ruta de navegación de los cruceros, estaciones de
bombeo que transportan fluidos a través de tuberías, rutas entre ciudades,
redes de conductos y toda aquella situaciones que puedan representarse
mediante una red donde los nodos representan las estaciones o las ciudades,
los arcos los camiones, mensajes y fluidos que pasan por la red. Con el
objetivo de encontrar la ruta mas corta si es una red de caminos o enviar el
máximo fluido si es una red de tubería.
Cuando se trata de encontrar el camino mas corto entre un origen y un destino,
la técnica, algoritmo o el modelo adecuado es el de la ruta mas corta; flujo
máximo y flujo de costo mínimo cada uno abarca un problema en particular. En
este trabajo se mencionan los modelos de redes existentes y los problemas
que abarca cada uno de ellos, además se describen los algoritmos que aplican
estos modelos para encontrar la solución optima al problema. Utilizando la
terminología utilizada para representarlo como una red.

Características principales

 El flujo va a ser siempre positivo y con unidades enteras.

 El flujo que entra en un nodo es igual al que sale.
 El flujo que atraviesa un arco nunca será mayor que la capacidad,
solo puede ser menor o igual que ella.

VISTA GENERAL DE ALGUNAS APLICACIONES PRÁCTICAS

DE LA OPTIMIZACIÓN DE REDES
 Diseño de redes de telecomunicación (redes de fibra óptica, de
computadores, telefónicas, de televisión por cable, etc.)
 Diseño de redes de transporte para minimizar el costo total de
proporcionar las ligaduras (vías ferroviarias, carreteras, etc.)
 Diseño de una red de líneas de transmisión de energía eléctrica de
alto voltaje.
 Diseño de una red de cableado en equipo eléctrico (como sistemas
de cómputo) para minimizar la longitud total del cable.
 Diseño de una red de tuberías para conectar varias localidades.
 Diseño de una red de tuberías de gas natural mar adentro que
conecta fuentes del golfo de México con un punto de entrega en
tierra con el objetivo de minimizar el costo de construcción.
 Determinación de la ruta más corta que une dos ciudades en una
red de caminos existentes.
 Determinar la capacidad anual de máxima en toneladas de una red
de conductos de pasta aguada de carbón que enlaza las minas
carboneras de Wyoming con las plantas generadoras de
electricidad Houston. (Los conductos de pasta aguada de carbón
transportan éste bombeando agua a través de tubos
adecuadamente diseñados que operan entre las minas de carbón y
el destino deseado.)
 Determinación del programa de costo mínimo de los campos
petrolíferos a refinerías y finalmente a los campos de distribución.
Se pueden enviar petróleo crudo y productos derivados de la
gasolina en buques tanque, oleoductos y/o camiones. Además de
la disponibilidad de la oferta máxima en los campos petrolíferos y
los requisitos de demanda mínima en los centros de distribución,
deben tomarse en cuenta restricciones sobre la capacidad de las
refinerías y los modos de transporte.

EJEMPLO
DETERMINE EL NÚMERO MÁXIMO DE PERSONAS QUE PUEDEN CIRCULAR
A LO LARGO DE LA RED DEL EJEMPLO ANTERIOR MEDIANTE EL
ALGORITMO DE LA TRAYECTORIA AUMENTANTE.
TRAYECTORIA:

CAPACIDAD:
Bibliografía
 Bryan Salazar López

https://www.ingenieriaindustrialonline.com/investigacion-de-
operaciones/metodo-del-costo-minimo/

Bibliografía
BIBIANA OBREGÓN QUINTANA (2005) TEORÍA DE REDES: EL PROBLEMA DE LA RUTA MÁS
CORTA