Universidad de Sonora

Departamento de Matemáticas

dIBLIOTECA
1 DE CIENCIAS EXACTA
Y NATURALES
Tesis

Algoritmos de Gráficas para el

Método de Ruta Crítica

ue para obtener el titulo de

Licenciado en Matemáticas

Presenta

Reynaldo Figueroa Galindo

Hermosillo, Sonora, 15 de Agosto de 1997

Contenido

Introducción 3

1 EL PROBLEMA DE LA SECUENCIA DE PROYECTOS 5

1.1 Problema de la Ruta Crítica (CPM) 6
1.2 Diagramas o modelos 6
1.3 Planteamiento de Problemas 9
1.3.1 Problema de construcción 9
1.3.2 Establecimiento de una fabrica 11
1.3.3 Fabricación de un nuevo Producto 13

2 LA TECNICA CPM EN LA SECUENCIA DE PROYECTOS 17

2.1 Determinación de la Ruta Crítica 18
2.1.1 Definición de Ruta Crítica 21
2.2 Determinación de las Holguras 22
2.3 Relación entre Duración y el Costo de una Actividad 23
2.4 Acortamiento de una actividad 25
2.5 Representación Lineal del CPM 44
2.6 Modelo Matemático del CPM 47
2.7 Como Determinar P(A) 58

3 Ejemplo con Aplicaciones del Algoritmo de Fulkerson 63

3.1 Ejemplo 63

1
 CONTENIDO

Conclusiones 119

A ALGORITMOS DE GRAFICAS PARA EL PROBLEMA CPM 121

A.1 Algoritmo de Dijkstra 121
A.2 Algoritmo de Ford Fulkerson 123

Bibliografía 125
CONTENI DO3

INTRODUCCION

En la actualidad existe un gran problema para poder planificar y programar proyectos de la

industria y de la construcción.
Hoy en dia existe una gran cantidad de libros de Investigación de operaciones en los cuales
hablan mucho de estos problemas pero ninguno nos dicen como llevarlos a la practica, el proposito
de nuestro trabajo es dar a conocer al lector un procedimiento para resolver este tipo de problemas.
Uno de los métodos usados para resolver este tipo de problemas es el Método de la ruta crítica
(CPM) en el que representa un proyecto mediante una red, la cual consiste en una serie de activi-
dades que tienen una determinada secuencia para realizarlas, es decir, existe una relación de tal
manera que una no se puede realizar hasta que otra halla terminado. Aqui presentamos un pro-
cedimiento para desarrollar un proyecto de tal manera que resulta muy sencillo utilizando gráficas
denominadas redes, cómo las actividades se pueden realizar más rapido a costo de un precio más
alto.
Nuestro objetivo es encontrar una solución al problema donde el costo sea mínimo bajo un
tiempo razonable.
El trabajo se divide en 4 capítulos, en los 3 primeros se desarrolla todo el material teótico y en
el cuarto capítulo desarrollamos un ejemplo completo.
En el primer capítulo se presentan el método del CPM y algunos ejemplos de problemas los
cuales se representan mediante una red que los modela y se quiere encontrar el costo mínimo bajo
un tiempo razonable para lo cual el CPM es un método muy práctico para resolver nuestro trabajo.
Aqui se resuelve un ejemplo intuitivamente.
En el capítulo 2 determinaremos como podemos encontrar y definir la ruta crítica, las holguras
las cuales nos indican el tiempo que debemos esperar para empezar una actividad, ademas veremos
la relación que existe entre la duración y el costo de una actividad, y resolveremos un ejemplo para
observar como se acortan dichas actividades. En este capítulo se incluye tambien los fundamentos
teoricos de nuestro trabajo
En el capítulo 3 desarrollaremos un ejemplo completo utilizando el algoritmo de Ford Fulkerson
para encontrar el mayor flujo posible para poder observar todos las posibles soluciones que existen
y poder ver cual es la mejor, es decir, la que nos da el mejor costo bajo un tiempo rasonable.

Por último, tenemos un anexo en donde mencionamos los algoritmos que utilizamos para la
solución de nuestros problemas entre ellos se encuentran el de Dijkstra y Ford Fulkerson.
CONTENIDO
Capítulo 1

EL PROBLEMA DE LA
SECUENCIA DE PROYECTOS

Un proyecto es una serie de actividades las cuales tienen una determinada secuencia para poder
realizarlas, es decir, existe una relación tal que una actividad no se realiza hasta que otras terminan.
Un proyecto es un trabajo que necesita tiempo y capital para realizarse.
En la actualidad existe una gran cantidad de libros de Investigación de Operaciones; en los que
hablan del método CPM (Critical Path Method) pero no nos explican su fundamentación ni nos
indican cómo poder llevarlo a la práctica. Esto es una gran deficiencia dado que este método es
muy usado en la planificación, control e información de los proyectos.
El proposito de nuestro es dar a conocer al lector uno de los métodos más utilizados en nuestros
tiempos cómo es el CPM, ya que en estos ultimos años se ha visto que es el método que más a
dado resultados en la planificación y programación de todo tipo de actividades a realizar, como por
ejemplo: en la industria de la construcción (barcos, edificios, puentes, carreteras etc.), también en
la instalación de los aparatos eléctricos de cualquier empresa, o las máquinas pasa la construcción
de cualquier producto. Por lo tanto, este trabajo está dedicado a la divulgación del método CPM
desde el punto de vista práctico para que pueda ser aplicado a los proyectos que se puedan presentas.
El CPM es un método que nos ayuda a encontrar cuál es la forma más eficiente de realizar un
proyecto consiguiendo que nos resulte lo mas barato posible en un tiempo razonable.
Daremos a conocer cómo saber el tiempo que se necesita para poder terminar una actividad
después de que ha terminado la anterior. Estudiaremos también el acortamiento de la duración del
proyecto, y las modificaciones del costo mínimo, empleando para esto una modificación al Algoritmo
de Dijkstra y de Ford Fulkerson con fin de que se puedan entender los fundamentos de esta técnica.

5
 Capítulo 1. EL PROBLEMA DE LA SECUENCIA DE PROYECTOS

1 1 Problema de la Ruta Crítica (CPM).

Por el año de 1957 la Casa E. I Du Pont desarrolló un método que nos sirve para planear y
program ar todo tipo de proyectos. Este método llamado Método de la Ruta Crítica ( Critical Path
Method ), y nos proporciona la forma de planear todas y cada una de las actividades que forman el
proyecto . El CPM nos proporciona la planeación más económica y con el menor tiempo en forma
tal que todas las actividades sean terminadas en las fechas deseadas.
Esta técnica es utilizada en muchas empresas, para planear la utilización de su presupuesto, es
decir, si se conocen todas las actividades que se tienen que realizar, y se conoce qué tanto dinero
se necesita y qué tiempo necesita cada actividad se puede racionalizar mejor el uso de los recursos.
La técnica CPM nos proporciona la información necesaria para poder resolver preguntas im-
portantes respecto a la programación de actividades como son: determinar cuál es el orden de
la actividad que se realizan primero y cuál después, cuántas serán las actividades que se pueden
realizar al mismo tiempo sin que intervengan unas con las otras, la duración de cada actividad y su,
costo cuál es la situación del proyecto que está en marcha con relación a la fecha programada para
su terminación, es decir, estamos en el tiempo esperado o es necesario forzar la marcha, cuáles son
las actividades en las que no se permite retraso ya que al retrasar cualquiera de ellas se alarga la
duración del proyecto, cuáles son las actividades que pueden, sí es necesario, durar un poco mas, y
qué tanto tiempo les es permitido, si el proyecto está atrasado, dónde se puede reforzar la marcha
para ahorrar tiempo y cuál es el costo en que aumentaría el proyecto.

1.2 Diagramas o modelos

En esta sección se dará la forma de cómo representar un proyecto por medio de un diagrama, el
cual nos será de utilidad al encontrar el camino mas adecuado para planificar la realización de un
proyecto.
Un diagrama de flechas es la forma de modelar un proyecto en forma de red para su rápida
solución, en este diagrama se muestra la relación correcta que debemos seguir al momento de
resolverlo.
En el diagrama de flechas o red, la flecha representa una actividad Cada una está relacionada
con otra y deben de representar relaciones que respondan a las preguntas siguientes:
¿Qué actividades deben de ser terminadas antes de que inicie la siguente?
¿Qué actividades son independientes y puedan realizarse al mismo tiempo ?
Existe otro tipo de red donde los nodos representan las actividades y donde las flechas repre-
sentan los eventos. Este tipo de red es similar a la red que aqui presentamos, pero la red de eventos
no la veremos en este trabajo. La mayor parte de las aplicaciones del CPM se resuelven utilizando
diagramas de flechas.
El CPM esta relacionado no sólo con el tiempo sino también con el costo de cada actividad. La
 2. Diagramas o modelos 7

red que se forma nos representa solamente la relación que existe entre una actividad y otra, estas
activida des están sujetas a ciertas restricciones de precedencia. El representar estas condiciones
gráficamente permite darnos cuenta de qué actividades son mas importantes, esta red no esta
terminad a hasta que a cada actividad se le asigne el tiempo que se necesita para terminar dicha
actividad, pues además, también se le debe de agregar el costo, el cual esta relacionado con el
tiempo. Una vez dada toda la información de las actividades del proyecto se dira que hemos
modelado el proyecto con una red.
Como hemos dicho anteriormente las actividades están sujetas a ciertas restricciones de prece-
dencia y una actividad puede comprender una tarea o una serie de ellas.
Nuestro modelo de red además de las actividades, cuenta con una serie de sucesos (nodos) que
nos representan el momento de comenzar o terminar una actividad representada por una flecha.
Ejemplo 1:
La siguiente red nos muestra un ploblema que está formado solamente por cuatro actividades
donde s es el inicio y t es el final.

fig. 1.1
Cada actividad debe de estar terminada para que la siguiente pueda comenzar. Sin embargo
los sucesos iniciales no tienen una actividad que le preceda y el suceso final no tiene una actividad
que le siga, por lo tanto el suceso final de la actividad precedente es igual que el suceso inicial de
la actividad subsiguiente, excepto en el primero y el último suceso.
Como podemos observar, los eventos estan enumerados, esto es para poder identificar con mayor
exactitud cada uno de ellos, las actividades que en estos momentos estamos definiendo con flechas,
donde la longitud no significa nada, sólo son para identificar cuales son los sucesos que están
conectados.
Un diagrama de flechas es la representación de un proyecto determinado en el que se muestra
la secuencia correcta para alcanzar los objetivos finales.
En algunas ocasiones existen en el diagrama de flechas una relación de precedencia entre dos
actividades, que no existe realmente, es decir no se requiere algún trabajo, ni recursos, ni tiempo si
no que por algunas circunstancias especiales una actividad debe de realizarse antes de otra, como
por ejemplo:
Supongamos que construimos un gran alternador eléctrico en el taller de caldería y no se puede
realizar el estator y el rotor al mismo tiempo por su tamaño, siendo estas dos actividades indepen-
dientes y para expresar el órden de ejecución unimos con una flecha ficticia, indicando que primero
 Capítulo 1. EL PROBLEMA DE LA SECUENCIA DE PROYECTOS

ace estator y luego el rotor.

Estator
o
fig. 1.2

En este caso para expresar la conexión de estas actividades, se crea una flecha ficticia represen-
ada con una linea punteada como en la figura 1.2
En muchas ocasiones, suele ocurrir que entre el mismo suceso inicial y el final aparezcan pa-
ralelamente varias actividades, para poder evitar esta confusión se puede crear la actividad ficticia
Ymentando el número de los sucesos.
Ejemplo

(a)

(b)
fig1.3 a, b
 3. Planteamiento de Problemas

El diagrama de flechas es el primer paso para lograr encontrar el tiempo mínimo para terminar
cada una de las actividades con el costo óptimo, para poder lograr esto se requiere de un proseso
especificando las fechas de inicio y terminación de cada actividad, para lograrlo se necesita encontrar
primero el tiempo más tardío el cual tiene el costo menor que existe entre el principio y el fin del
proyecto e ir acortando este tiempo paulatinamente hasta encontrar el menor tiempo posible pero
al ir acortando el tiempo, el costo se va incrementando hasta llegar al punto en el cual el tiempo y
el costo son los adecuados, es decir, el menor costo bajo un tiempo razonable.

1.3 Planteamiento de Problemas

En esta sección daremos a conocer algunos problemas que aparecen en la vida real, a los cuales
les daremos un planteamiento para poder resolverlos utilizando el método CPM. Entre estos men-
donamos algunos problemas de construcción en los cuales existe un factor muy importante: el
tiempo. Este es importante ya que si el proyecto no se termina en el tiempo establecido nos
ocasionaria un costo mayor.
El primero de ellos se refiere a la construción de una obra en el que se quiere saber si se puede
terminar a tiempo. El segundo a la instalación del equipo de una fábrica donde se quiere conocer
el tiempo para terminar la instalación lo más rápido posible.
A continuación presentaremos estos problemas que se pueden resolver con este método; aprovechán-
dolos para introducir el planteamiento en términos de gráficas, que detallaremos con mayor pro-
fundidad en el siguiente capítulo.

1.3.1 Problema de construcción

A un ingeniero se le ha encomendado la construcción de una cimentación de concreto. El ingeniero

realiza algunas investigaciones y se percata que son necesarias las siguientes actividades:
Excavación.
Obtención del concreto y acero de refuerso.
3.- Colocación del acero de refuerzo para castillos y dalas.
4.-Colocación de la cimbra.
5.-Corte y doble del acero de refuerzo para el colado.
6.- Colado.
Cada una de estas actividades tiene su tiempo de duración. Por la secuencia de las actividades.
Obsérvese que algunas actividades no se pueden realizar hasta que otras terminen. El ingeniero,
debe saber en qué momento termina una actividad y comienza otra, para poder conocer esto asigna
a cada una de las actividades la notación A(i,j) la cual significa que la actividad comienza en i y
termina en j, por lo tanto el ingeniero observa que el proyecto esta formado por varias actividades
 Capítulo 1. EL PROBLEMA DE LA SECUENCIA DE PROYECTOS

ales comienzan en un nodo que llamamos s y termina en otro llamado t, que representan el
io y el fin del proyecto, el ingeniero plantea su problema de tal manera que pueda saber
empie za y donde termina una actividad, para ello, une mediante una flecha lo que es el
'pie y el fin de cada actividad, representando asi mediante la flecha a la actividad A(i,j), se
ra que no todas las actividades se pueden realizar al mismo tiempo, es decir, se tiene que
erminar algunas antes de iniciar otras, entonces con los datos obtenidos en su investigación el
reareto forma la siguiente figura:

colocación
de castillos
y dalas

excavació
cimbra

obtención colado
del concreto
y varilla

para el colado
fig. 1.4
Usando los datos de la figura 1.1 el ingeniero forma la siguiente tabla.

A(i,j) Descripción tiempo

A(s,1) Excavación
A(s,2) Obtención del concreto 8
A(1,3) Colocación del acero de refuerzo 4
para los castillos y dalas 2
A(2,1) ficticia
A(2,4) Corte y doble del acero de refuerso 5
para el colado
A(3,4) colocación de la cimbra 10
A(4,t) Colado 3

tabla 1.1
En la figura 1.4 nos indica el seguimiento de cada una de las actividades, indicándonos cual
actividad se debe de realizar primero, cual después y el tiempo que se necesita en cada una de
ellas se muestra en la tabla. En la figura se puede observar 7 actividades, estas son A(s,1), A(5,2),
A(1,3), A(2,1), A(2,4) (3,4) y A(4,t) de las cuales una de ellas la A(2,1) es ficticia y por lo tanto
 lanteamien to de Problemas 11

e necesita tiempo para realizarla pero nos indica que no se puede realizar la actividad A(1,3)
ue halla terminado la actividad A(s,2) pero tambien tenemos que la actividad A(1,3) no puede
zar hasta que termine la actividad A(s,1) es decir no puede colocar el acero de refuerzo sin
hecho la escavación y no puede cortar la varilla sin haberla adquirido antes, tambien nos
tira con la figura que no puede colar si antes no se realizaron todas las demas actividades.
ui podemos observar que la máxima duración del proyecto es de 18 días ya que el camino
une a las actividades A(s,1) y A(1,t) es el más largo del proyecto.

S.2 Establecimiento de una fabrica

una fábrica, se pretende elaborar un producto para su comercialización, pero es necesario primero
quirir el equipo y proceder a su instalación, para ésto se contrata a un ingeniero que estudie la
anexa, de realizar la adquisición e instalación del equipo. El ingeniero ha hecho las averiguaciones
ertinentes y ha observado que son necesarias 7 actividades:
compra de equipo,
entrenamiento del personal,
búsqueda del mercado de capital,
instalación de equipo,
cálculo del presupuesto,
financiamiento para 5 años de producción,
prueba de equipo,
las cuales requieren ciertos tiempos para cada actividad (en dias).
Usando estos datos el ingeniero forma la siguiente red
 Capítulo 1. EL PROBLEMA DE LA SECUENCIA DE PROYECTOS

Financiamiento
para 5 años
Cálculo de
presupuesto

Prueba
de
equipo
Búsqueda
Instalación
de capital
del equipo
equipo

fig. 1.5
enero se ha percatado de que algunas actividades no se pueden comenzar hasta que otras
erminado como por ejemplo: para poder saber cuánto se gastará, es necesario comprar
y para saber el financiamiento primero es necesario conocer con cuánto capital se cuenta
o se debe saber cuáles actividades podemos realizar primero y cuáles después.
la figura anterior se puede notar que para poder comprar el equipo primero se debe calcular
upuesto y que para poder probarlo primero se debe de capacitar al personal, también se
blerrvar que para poderlo instalar primero se debe de comprar, por último se da cuenta que
der probar el equipo se debe tener todo ya listo, es decir, se debe de calcular el presupuesto,
,elequipo, capacitar al personal, instalarlo, buscar el capital, siendo este el final del proyecto
podemos observar que la duración del proyecto es de 20 días.
ernpos para cada actividad se especifican en la siguiente tabla.
 eamiento de Problemas 13

A(i,j) Descripción Tiempo

A(s,1) Cálculo del presupuesto 1

A(s,2) Búsqueda de capital 10
A( s ,4) Entrenamiento del personal 12
A(1,4) Financiamiento para 5
años de presupuesto 6
A(2,3) Compra de equipo 5

A(3,4) Instalación 4
A(4,t) Pruebas de equipo 8

tabla 1.2
stos dos problemas que hemos mencionado son problemas que utilizamos como ejemplo de
os otros más que existen en la vida real.
ontinuación se presentan las actividades necesarias para la fabricación de un nuevo producto.

Fabricación de un nuevo Producto

nuación se enlistan las actividades de un proyecto consistente en la fabricaciónde un nuevo

cto.
- Decisión preliminar
2.- Estudio de mercado
Reporte de estudio.
4.- Sugerencia del diseño.
Lista posible de proveedores.
6.- Estimación de la capacidad de poducción.
sta de posibles distribuidores.
Estudio de campaña de publicidad.
9.- Estudio del diseño.
0.- Cotización de precios.
 Capítulo 1. EL PROBLEMA DE LA SECUENCIA DE PROYECTOS

4- Pronósticos de Venta.
Cálculo de costos de publicidad.
Compra de material.
Pruebas de producción.
Presupuesto.
Estrategia de ventas.
Pruebas de control de calidad.
Resultados de publicidad.
Lanzamiento al público.
continuación presentamos la red que se forma con estas actividades

fig. 1.6
De acuerdo a la figura 1.6 se forma la siguiente tabla donde las actividades se encuentran
sumidas de la siguiente manera en la primera columna se muestran los A(i,j), en la segunda
umna se muestra la lista de actividades del proyecto y en la tercera columna se indica la duración
cada actividad (en días) Determínese la duración mínima del proyecto.
 Planteamiento de Problemas 15

A(i‘i) Actividad Duración

A(s,1) Decisión preliminar. 15
A(1,2) Estudio de mercado. 30
A(2,3) Reporte de estudio. 2
A(3,4) Sugerencia del diseño. 10
A(3,5) Lista posible de proveedores. 4
A(3,6) Estimación de la capacidad 10
de producción.
A(3,7) Lista de posibles distribuidores. 4
A(3,8) Estudio de campaña de publicidad. 20
A(4,9) Estudio del diseño. 40
A(5,10) Cotización de precios. 10
A(6,11) Pronósticos de Venta. 8
A(7,11) Cálculo de costos de publicidad. 6
A(8,14) Compra de material. 20
A(9,12) Pruebas de producción. 30
A(10,9) Presupuesto. 15
A(11,8) Estrategia de ventas. 3
A(12,13) Pruebas de control de calidad. 30
A(13,11) ficticia.
A(13,14) Resultados de publicidad. 12
A(14,t) Lanzamiento al público. 7

tabla 1.3
Este problema como podemos observar tiene ya un número mayor de actividades incluyendo
algunas actividades ficticias, estas actividades se utilizan cuando en algun proyecto existe una
alación que no requiere tiempo ni recursos pero se utiliza por alguna circunstancia especial, esta
ctividades ficticias se representa por una linea punteada, éstas son actividades que los problemas
Jmencionados anteriormente no las teman, por consiguiente este es ya un problema mas real y por
tanto para resolverlo es necesario estructurarlo más detalladamente mediante una red la cual
os representa paso a paso todas las actividades y la ruta que se tiene que seguir para poder llegar
la última actividad y así poder conocer la duración y el costo del proyecto, pero para esto es
ecomendable utilizar algún procedimiento de lo cual hablaremos mas adelante.
En el siguiente cápitulo veremos cómo dasificar las actividades en críticas o no críticas además
de encontrar el tiempo suficiente que necesita cada actividad para terminar el proyecto y observar
ué tiempo tiene cada actividad para comenzar y terminar, al cual se le llama tiempo de holgura,
veremos como representar nuestro problema, observaremos cómo relacionar el costo con la duración
de una actividad y como acotarla.
Capítulo 1. EL PROBLEMA DE LA SECUENCIA DE PROYECTOS
 TECNICA CPM EN LA
UENCIA DE PROYECTOS

ación de un proyecto por CPM consiste en planear, programar y controlar cada una de
Ldades del proyecto.
•
e de planeación significa descomponer el proyecto en actividades distintas. Los tiempos
actividad se dejan para después y se constrUye un diagrama de red donde cada uno de sus
emitan una actividad. La construcción de esta red nos ayuda a estudiar los diferentes
en detalle, sugiriendo mejoras antes de que este trabajo se ejecute.
ogramación nos ayuda a construir un diagrama de tiempos para conocer cuándo comienza
o termina una actividad y su relación con las demas, además el proyecto debe señalar las
es críticas que son las que requieren la mayor atención si se quiere terminar oportunamente.
`que una actividad es crítica si una demora en su comienzo causará una demora en la
terminación del proyecto. Una actividad no crítica es la que si se adelanta o atrasa no
ningún cambio en la duración del proyecto.
rólar un proyecto significa que se puede disminuir el tiempo de éste y por lo tanto se
a el costo, es decir, se puede optimizar el costo de un proyecto bajo un tiempo rasonable.
actividades no críticas el programa debe mostrar los tiempos de holgura que pueden
e cuando dichas actividades se demoran. •.
ontrol de un proyecto incluye el uso de la red de flechas y la gráfica de tiempos para hacer
s periódicos del progreso. La red por consiguiente puede actualizarse y analizarse y si es
io determinar un nuevo programa para la porción restante del proyecto.
aplicación del CPM deberá proporcionar un programa, especificando las fechas de inicio y
,
acion
. , de cada actividad. La red constituye el primer paso para poder lograrlo. Debido a la
clon de las diferentes actividades, la determinación de los tiempos de inicio y terminación,
e de cálculos especiales. Estos cálculos se realizan directamente en la red usando aritmética
y con lo cual las actividades se pueden clasificar en críticas y no críticas.

17
 Capítulo 2. LA TECNICA CPM EN LA SECUENCIA DE PROYECTOS

ante veremos que la actividad no crítica tiene un tiempo de holgura que nos indica el
puede atrasarse la actividad sin que otras actividades sufran algún cambio tanto en el
en el tiempo.

erminación de la Ruta Crítica

ítica define una cadena de actividades a las cuales no se les puede disminuir el tiempo
están con el mínimo tiempo posible, las cuales conectan los eventos iniciales y finales
en otras palabras la ruta crítica identifica todas las actividades críticas del proyecto.
os el método para determinar la ruta crítica con un ejemplo, pero antes diremos como
odelación del problema.
ciar, es conveniente representar a los nodos de la siguiente manera:
odo que representa los eventos para i = s, 1, 2, 3, 4, 5, 6.... t;
„representa la actividad que comienza en el evento i y termina en el evento j ademas t(i,j)
el tiempo y el costo de la actividad A(i,j), respectivamente.
conjunto de todos los eventos, es decir N lo podemos reprecentar como {s, 1,
una ruta que conduce del evento inicial s al evento final k.
(k)) la duración de la ruta, es decir

t(C(k)) = E t(i, j)
AmEc(k)

el siguiente ejemplo calculemos la duración de una ruta.

emos el proyecto representado por la siguiente gráfica.

 nación de la Ruta Crítica 19

fig. 2.1
oyecto esta formado por 5 eventos y 8 arcos, los eventos y los arcos forman una red que
s y termina en t, los cuales tienen sus tiempos determinados que son•
20 días
10 días
30 días
-'5 días
70 días
-,1 día
— 2 días
5 días
uta seria la formada por las actividades A(s,1), A(1,2), A(2,3), A(3,t) y su duración está

+ «1,2) + t(2,3) + t(3,t) 20 + 30 1 + 5 = 56 días.

u muchas rutas más pero solo una es la que nos interesa la cual encontramos acontinuación:
ando la ruta que nos indique la duración del proyecto.
culos para la ruta crítica la cual definiremas más adelante requiere dos faces, la primera
cálculo hacia adelante, la cual empieza en s y termina en t, donde en cada nodo se calcula
que representa el tiempo de inicio mas rápido del evento correspondiente. La segunda
 Capítulo 2. LA TECNICA CPM EN LA SECUENCIA DE PROYECTOS

culo hacia atrás, comienza en el nodo t y termina en el nodo s y el número calculado

epresenta el tiempo de inicio mas tardío del evento correspondiente.
de inicio más rápido es lo menos que debe esperar para comenzar la actividad, el
o más tardío es lo máximo que puede esperarse para comenzar la actividad

os -hacia adelante para la gráfica dada se representan a continuación:

de inicio más rápido de todas las actividades que comienzan en j, se representa como
empos de inicio más rápido se obtienen con la fórmula:
TIMRi = max[T/MRi +t(i,j)], i antecesor de j

TIMRs=0 si j=s

o ahora todos los tiempos de inicio más rápidos de cada uno de los eventos tenemos:
O días
[0+20] = 20 días
Max[0+10, 20+30] = Max[10, 50] = 50 días
Max[20+5, 50+1] = Max[25, 51] = 51 días
Max [20+70, 50+2, 51+5] = Max[90, 52, 56] = 90 días
operación terminamos los cálculos hacia adelante el cual determina la duración del

"rulos hacia atrás comienza desde t y terminan en s. lo que se quiere es encontrar los
inicio más tardío, TIMT, representa el tiempo de inicio más tardío del evento i para
icvidades que comienzan en el evento i. Para encontrar estos tiempos se usa la siguiente

TIMT, = min[TIMTi - t(i,j)] Vi t, j sucesor de i

TIMT, = TIMR, si i=t

do ahora todos los tiempos más tardíos de cada uno de los eventos tenemos
TIMRt = 90 días
TIMTt - t(3,t) = 90-5 = 85 días
min[TIMTt - t(2,t),TIMT3 - t(2,3)] = min[90- 2, 85-1] = min[88, 84] = 84 días
= inin[TIMTt - t(1,t),TIMT3 - t(1,3),TIMT2 - t(1,2)]=min[90 -70, 85 - 5, 84 - 30] =
 e la Ruta Crítica 21

días
n[TIMTi - t(s,l),TIMT2 - t(s,2)] = min [20 - 20, 84 - 10] = Min[0, 74] = 0 días
a los cálculos hacia atrás.
n veremos la utilidad de estos cálculos.

km de Ruta Crítica

de la ruta crítica se pueden identificar usando los resultados que encontramos

donde podemos observar que una actividades A(i,j) está en la ruta crítica si satisface
condiciones:
TIM T;
TIMT
TIMT; = TIMT3 - TIMRi t(i,j).
idades que nos definen la ruta crítica para nuestro ejemplo son A(s,l), A(1,t), que
d días es el tiempo máximo posible para terminar el proyecto.
a no es crítica cuando se tiene una actividad A(i,j) que no cumple las tres condiciones
anteriormente, por ejemplo, si se tiene la actividad A(2,3) del ejemplo anterior pode-
ar que los tiempos de inicio más rápido son diferentes a los tiempos más tardios.
probar esto hagamos los cálculos:
condición:
= max[0+10, 20+30] = max[10, 50] = 50 días
= min[T I MTt - t(2,t),T I MT3 - t(2,3)] = min[90- 2, 85-1] = min[88, 84] = 84 días
Condición:
= max[20+5, 50+1] = max[25, 51] = 51 días
3= TIMT - t(3,t) = 90-5 = 85 días
a condición :
R3 - TIMT2 = 51 - 84 = -33
T3 - TIMR2 = 85 - 50 = 35
omo las condiciones no se cumplieron podemos decir que esta actividad no se encuentra en la
rítica.
puede afirmar que el tiempo de 90 días es el más rápido para terminar el proyecto ya que si
os otra ruta veremos que es más corta en duración.
 Capítulo 2. LA TECNICA CPM EN LA SECUENCIA DE PROYECTOS

terminació n de las Holguras

Ia determinación de las rutas críticas, deben calcularse las holguras de las actividades no

ividades que se forman de la red de un proyecto podrían tener algún retraso en el tiempo
vez también se podrian adelantar algunas actividades, es decir, realizarlas en menor
"indicado, este adelanto o retrazo en el tiempo de realización de cada actividad se le
tira, dicha holgura se representa mediante una II y para conocer por ejemplo la holgura
vidad i lo hariamos de la siguiente manera:

= TIMT;—TIMRi para todo i E N.

ente una actividad crítica debe tener una holgura cero, de hecho, esto es una condición
ea crítica.
nocirniento de los tiempos de holgura en nuestro proyecto dá origen a que se realice un
cambio en el programa que se utiliza para encontrar el tiempo máximo por medio del
Dijkstra.
enemos la holgura de cada uno de los eventos del ejemplo anterior obtendremos lo si-

0 - 0 = O días
20 - 20 = O días
M - 50 = 34 días
85 - 51 = 34 días
90 - 90 = O días
holgura indica el tiempo que se puede esperar para empezar alguna actividad que parte
o evento i, quiere decir que las únicas actividades que no se deben de retrasar son las
s A(s,1) y A(1,t) por lo tanto las actividades que se pueden retrasar son las actividades
A(1,2), A(1,3), A(2,3), A(2,t) y A(3,t), pero si se retrasan más de lo indicado se retrasa
oyecto.
holgura importante es la holgura total
tipo de holgura nos señala el retraso que existe entre empezar A(i,j) lo más rápido posible
que su terminación se retrasa lo más posible, en otras palabras, lo que podemos tardar
do A(i,j), y la obtenemos de la siguiente manera:
HT(i,j) = TIMT2 —TIMR, - t(i,j)
culandola para el problema anterior seria:
(s,1) 20 - O - 20 = O días
 Relació n entre Duración y el Costo de una Actividad 23

T(s,2) -= 84 - O - 10 = 74 días
.RT(1,2) = 84 - 20 - 30 = 34 días
T(1,3) = 85 - 20 - 5 = 60 días
ILT(1,t) = 90 - 20 - 70 = O días
HT(2,3) = 85 - 50 - 2 = 33 días
T(2,t) = 90 - 50 - 2 = 38 días
T(3,t) = 90 - 51 - 5 = 34 días
Existen otros tipos de holgura los cuales para fines prácticos de nuestro problema no se utilizan.
La determinación de las holguras en las actividades es muy importante ya que son las que nos
dican que tanto podemos retrasarnos en la actividad para no retrasar el proyecto y nos indica
ambien cual es el tiempo máximo que podemos retrasarnos en iniciar una actividad antes de que
e convierta en crítica.

3 Relación entre Duración y el Costo de una Actividad

n el capítulo anterior vimos la manera de construir una red por medio de un ejemplo. Observamos
manera de encontrar la ruta más rápida, sin embargo no mencionamos el costo de la actividad ni
costo del proyecto, pero sabemos que si aumentamos la marcha de alguna actividad para reducir
duración, esto ocasionaría un aumento en el costo total ya que al apurar una actividad el costo
de la actividad aumenta y por lo tanto también el costo del proyecto.
E método CPM nos proporciona la técnica para optimizar la relación que existe entre costo y
lempo de un proyecto. Para esto observamos que para cada actividad de una red se requiere de
'-un rango de tiempo para su terminación, además el tiempo de realización se disminuye a costa de
aumentar el costo es decir con la duración más corta el costo es máximo.
Veamos un ejemplo sencillo para observar cómo va aumentando el costo cuando el tiempo
disminuye.
Ejemplo:
Se considera una excavación simple, como la de una zanja para una tuberia. Habrá varios
métodos de construcción que sean aplicables, incluyendo el trabajo manual por sí solo, así como
las diferentes formas mecánicas de excavación. Consideraremos que la tuberia es corta con muchos
cambios de dirección y que lo más práctico es el trabajo manual.
Lo primero que debe señalarse es la magnitud del trabajo, esto es, estimar los volumenes de
erra a remover, ademas de fijar el tamaño de la cuadrilla.
Suponiendo que el tiempo máximo del trabajo es de 8 horas al dia, 5 días a la semana, que
hl trabajo requiere 300 días hombres, que el numero de hombres en la cuadrilla es de 10, y que el
 Capítulo 2. LA TECNICA CPM EN LA SECUENCIA DE PROYECTOS

de 18 unidades por dia por cada hombre, entonces, considerando que trabaja una
os:
ranima = 30 días hábiles.
o 10x30x18 = 5400 unidades.
a cuadrilla trabajando dos turnos y el segundo turno tiene un salario obligado de
costo extra por dia, entonces serán necesario más recursos para la misma cantidad

n con dos turnos es de SI lo que nos da 15 días hábiles.

i dos turnos para el l er turno seria 10x15x18 = 2700
dos turnos para el 2 d ° turno seria 10x15x19 = 2850
tal es de 5550.
parecida para una cuadrilla trabajando 3 turnos con un salario obligado de dos
para el tercer turno se tiene.
ám tres turnos es de -11-3 lo que nos da 10 días habiles.
es turnos para el 1" turno seria 10x10x18 = 1800
tres turnos para el 2d° turno seria 10x10x19 = 1900
es turnos para el 3" turno seria 10x10x20 = 2000
es de 5700.
ación la podemos colocar en la figura siguiente relacionando el costo y el tiempo.

costo

5700 3 tur
5550 2 tur OS
5400 1 turno

10 15 30 duración

fig. 2.2
e ahora puede ser calculada en cualquier periodo intermedio de terminación. A
aumentan los turnos, se incrementará el costo de la operación, pero siempre hay un
ya no se puede disminuir de duración. A esta duración se le llama duración mínima
 cortamien to de una actividad 25

le denota como d(i,j) y el costo de esta duración sera la máxima a la cual se le llama C(i,j).
Por otro lado el costo mínimo designado como c(i,j) esta relacionado con la duración máxima a
uración con el costo mínimo se le denomina D(i,j).
Entre la duración máxima y la mínima existe una infinidad de duraciones, si nosotros encon-
amos todas las soluciones que existen entonces se formará una linea recta uniendo la duración
4,xima y la mínima como se ve en la figura.

fig. 2.3
Por lo tanto con los puntos que se forman en la recta los cuales son (D(i,j), c(i,j)) y (d(i,j),
C(i,j)) podemos ver que la pendiente que se forma es la siguiente:
Nizo — DC(i.j.)-C
-d«.,j
(14)(t) ,2)

Esta formula se usa para el acortamiento de una actividad como lo veremos a continuación.

2.4 Acortamiento de una actividad

Para acortar un proyecto lo que debe de buscarse primero son escoger aquellas actividades cuyos
ncrementos de costo por unidad de tiempo sean menor que las otras que se encuentran en la misma
ruta. El costo por unidad de tiempo se obtiene con la siguiente fórmula:
—
P (ij )_ g{2}---cdti,j4
para cada actividad A(i,j).
 Capítulo 2. LA TECNICA CPM EN LA SECUENCIA DE PROYECTOS
costo

C(i,j)

C(i,j)

c(i,j)

duración
fig. 2.4
onces tomando los puntos (d(i,j), C(i,j)) y (D(i,j), c(i,j)) podemos ver que la pendiente que
ma al obtener el costo por unidad de la siguiente forma:

-d
la ecuación dados dos puntos de una recta y tomando los puntos mencionados anteriormente
os;
c(i,i)—C /,ij
— t
- c (i ,j ) = -POLO[t (ii) - D(i,j)]
a: cabe aclarar que el signo de P(i,j) es debido a cómo se define P(i,j)
pejando C(i,j) queda:

j) = c(i,j) "ii)NOLD - D(i,j)]

arrollando:
= c(i,j) - P(i,j)t(i,j) t P(i,j)D(i,j)]
ero como c(i,j) P(i,j) D(i,j) es una constante a la cual la llamamos c(i,j) entonces nos queda
siguiente manera:

(11.1) = c(i,j) POLgt(1j)

n el ejemplo anterior la duración máxima D(i,j) es de 30 días y el costo mínimo c(i,j) = 5400
as que la duración mínima d(i,j) es de 10 días y el costo máximo es de 5700 entonces el
ento que existe por cada unidad de tiempo es de P(i,j) = 573oliso = 15 unidades, el cual
ca que al aumentar una unidad de tiempo, disminuye 15 unidades de costo.
ntonces para reducir el tiempo de todo el proyecto, lo primero es reducir la duración de las
idades críticas, y elegir la que tenga menor incremento de costo por unidad.
ara explicar más claramente el proceso de reducción del tiempo de los proyectos veamos un
lo. Observaremos cuantos cáminos existen desde el nodo origen s al nodo destino t y obten-
os la duración de cada uno de ellos; tomaremos el de mayor duración y trataremos de disminuir
ación del mismo, buscando la actividad que tiene el costo mínimo por unidad de tiempo en
 nto de una actividad 27

la siguiente red que representa un proyecto:

fig. 2.5
a red los valores de cada actividad tanto en costo como en duración se dan en la siguiente

linera columna tenemos las actividades, en la segunda el nodo inicial, en la tercera el

e siguen duración máxima, mínima, costo mínimo, costo máximo y costo por unidad
 Capítulo 2. LA TECNICA CPM EN LA SECUENCIA DE PROYECTOS

Duración Costo Costo por unidad de

Máxima Mínima Mínimo Máxima tiempo

D(i,j) d(i,j) C(i, C(j,i) P(ij)

5 2 100 199 33
2 1 50 80 30
2 1 150 180 30
7 5 200 250 25
5 2 20 41 7
4 2 20 40 10
3 1 60 80 10
10 6 30 62 8
5 2 10 19 3
9 5 70 90 5
4 1 100 130 10
3 1 140 160 10
3 1 900 990 10
tabla 2.1
tividades se encuentran en su máxima duración para que el cost o de cada una sea
entras que el costo de total del proyecto se calcula como la suma del costo de cada
,pr oyecto.
Corrida de escritorio
a red podemos encontrar todos los caminos que existen desde el n odo s al nodo t y
var que son los siguientes:

/vi ad se representa por letras mayúsculas y utilizamos la duración s máximas repre-

manas las cuales ponemos entre parentesis es decir A (5) represe ta la actividad A
n de 5 semanas:
(9) = 11 semanas
5) + M(3) = 10 semanas
+ M(3) = 12 semanas
+ K(4) + M(3) = 17 semanas
(5) + L(3) = 13 semanas
(7) + G(3) + J(9) = 24 semanas
(7) + G(3) + I(5) + M(3) = 23 semanas
 tinto de una actividad 29

D(7) + 11(10) + M(3) = 25 semanas

K(4) + M(3) = 9 semanas
+ L(3) = 5 semanas
ver que la duración máxima del proyecto es la del camino número 8, el cual tiene una
25 semanas y el costo total del proyecto es 1150.
s las actividades A, D, II y M son actividades críticas ya que si se les aumentara o
el tiempo, el tiempo total del proyecto cambiaría.
siguiente gráfica se muestra con flecha doble la ruta crítica

fig. 2.6
e t(i) = TIMR, (Tiempo de Inicio Más Rápido en i)
cede ver que la duración máxima del proyecto es de 25 semanas.
siguiente tabla podemos observar que en la columna de modificación de duración tenemos
que aumentó o disminuyó cierta actividad y lo mismo sucede en la última columna pero
costo.
 Capítulo 2. LA TECNICA CPM EN LA SECUENCIA DE PROYECTOS

Duración Modificación Costo mínimo Modificación de

de duración costos
No
Crítica crítica

100
50
150
200
20
20
60
30
10
70
100
140
200
25 os o recto mmuno 1150
tabla 2.2

Primera Programación
os reducir el tiempo del proyecto cuidando que nos salga lo más barato posible, por lo
sca la actividad crítica que tenga el costo por unidad de tiempo más bajo, podemos
e esta es la actividad H (ver la tabla 2.1) que se puede reducir hasta 4 semanas, pero si
4 semanas a la actividad II entonces la duración de la ruta seria de 21 pero no asi la del
e seria de 24 que es la duración de la ruta 6, así que bajar 4 semanas a la actividad II
os innecesarios pues la duración del proyecto no disminuye en la misma forma. Pero
arle 1 semamna con lo cual obtendremos 2 rutas crítica de 24 semanas de duración

*nos obtenidos entre s y t quedarían como sigue:

) + J(9) = 11 semanas
) + I(5) + M(3) = 10 semanas
) + F(4) + M(3) = 12 semanas
5) + E(5) + K(4) + M(3) = 17 semanas
5) + E(5) + L(3) = 13 semanas
(5) + D(7) + G(3) + J(9) = 24 semanas
(5) + D(7) + G(3) + I(5) + M(3) = 23 semanas
ortamien to de una actividad 31

5) + D(7) + 11(9) + M(3) = 24 semanas

(2) + K(4) + M(3) = 9 semanas
C(2) + L(3) = 5 semanas
de la red noa quedaria de la siguiente manera:

fig. 2.7
ervese que ahora existen dos rutas críticas en la red.
La tanto como la actividad II se reduce 1 semana entonces el costo del proyecto se aumentá
dades quedando en 1158 como se observa en la siguiente tabla donde se suman los costos
s agregandosele las 8 unidades de aumento:
 Capítulo 2. LA TECNICA CPM EN LA SECUENCIA DE PROYECTOS

{ Actividad Duración Modificación Costo mínimo Modificación

de duración de costos
Deno No
mina J Crítica crítica
,
C10111

A 1 5 100
3 2 50
C 4 2 150
1 2 7 200
E 1 4 5 20
F 1 5 4 20
G 2 3 3 60
2 5 9 1 30 8
3 5 5 10
3 t 70
K 4 5 4 100
4 t 3 140
5 t 3 200
Duración 24 CO sto mínimo 1158

tabla 2.3
1 costo de la actividad H se incrementa en 8 siendo ahora de 38 unidades.

Segunda Programación
ora debe analizarse los dos caminos que existen pues hay que reducir la duración simultane-
e hasta que aparesca otra ruta crítica o no puedan reducirse más estas. Hay 6 actividades
tibies de acortarce, son A, D, G, H, J y M.
nemos las siguientes opciones para disminuir la duración de ambos caminos:

A con costo = 33
con costo = 25
y II con costo = 10 + 8 = 18

y M con costo = 10 + 10 = 20
J y 11 con costo = 5 + 8 = 13

J y M con costo = 5 + 10 = 15
demos ver que reducir las actividades J y II nos cuesta menos. Por otro lado, la ruta 7 tiene
ración de 23 semanas por lo que sólo podemos bajar una semana de duración a la ruta
 cortamiento de una actividad 33

a, para lo cual bajaremos 1 a J y la 11.

epuede observar que ahora los caminos son:
B(2 ) J(8) = 10 semanas
B(2) + 1(5) + M(3) = 10 semanas
-3„ A(5) + F(4) + M(3) = 12 semanas
A(5) + E(5) + K(4) + M(3) = 17 semanas
A(5) + E(5) + L(3) = 13 semanas
6.- A(5) + D(7) + G(3) + J(8) = 23 semanas
7, A(5) + D(7) + G(3) + 1(5) + M(3) = 23 semanas
A(5) + D(7) + 11(8) + M(3) = 23 semanas
C(2) + K(4) + M(3) = 9 semanas
10.- C(2) + L(3) = 5 semanas
Nuestra red es ahora la siguiente:

B
t(3)=15
J

t(t)=23

L(3)

fig. 2.8
El costo del proyecto es de 1171 como se ve en la siguiente tabla:
 Capítulo 2. LA TECNICA CPM EN LA SECUENCIA DE PROYECTOS

tividad Duración Modificación Costo directo Modificación

de duración de costos
No
Crítica crítica

100
50
150
200
20
20
60
38
10
70
100
140
200
23 osto recto minimo 1171
tabla 2:4

Tercera Programación
Las opciones que tenemos para reducir las 3 rutas críticas simultaneas sera:
A, costo = 33
D, costo = 25
á) G y H, costo = 10 + 8 = 18
M y J, costo = 10 + 5 = 15
J, I y II, costo = 5 + 3 + 8 = 16
La opción más barata es la 4 con las actividadesM y J.
La duración de cada camino es:
B(2 ) J(6) = 8 semanas
B(2) + I(5) + M(1) = 8 semanas
A(5) + F(4) M(1) = 10 semanas
A(5) + E(5) + K(4) + M(1) = 15 semanas
5.- A(5) + E(5) + L(3) = 13 semanas
 ento de una actividad 35

D(7) + G(3) + J(6) = 21 semanas

+ D(7) + G(3) + 1(5) + M(1) = 21 semanas
D(7) + 11(8) + M(1) = 21 semanas
K(4) + M(1) = 7 semanas
) + L(3) = 5 semanas
ces el costo aumenta un total de 30 es decir el costo aumenta de 1171 a 1201 con una
dé 21 unidades quedando la red como sigue.

B(2)
t(3)=15
J

t(t)=21

L(3)

fig 2.9
o podemos ver los caminos siguen siendo los mismos pero disminuyo el tiempo y tambien
él costo y lo cual se puede observar en la siguiente tabla.
 Capítulo 2. LA TECNICA CPM EN LA SECUENCIA DE PROYECTOS

.1": Actividad Duración Modificación Costo directo Modificación

de duración de costos
Deno No
Mina Crítica crítica
Ción
1 5 100
3 2 50
4 2 150
D 1 2 7 200
1 4 5 20
F 1 5 4 20
2 3 3 60
H 2 5 8 46
I 3 5 5 10
J 3 t 2 75 10
K 4 5 4 100
4 t 3 140
20
M 5 t 1 200
Duración 21 Costo direct o 1111111M0 1201

tabla 2.5

Cuarta Programación
Las opciones ahora son:

A, costo = 33
D, costo = 25
G y H costo = 18
J, I y II costo = 16
Como podemos observar la mejor opción es la número 4 con un aumento de 16 por unidad
quiere decir que el costo del proyecto pasaria de 1201 a 1217 donde J y M han llegado a su duración
mínima y la duración del proyecto será de 20 unidades como podemos ver en los caminos:
B(2 ) J(5) = 7 semanas
B(2) + I(4) + M(1) = 7 semanas
A(5) + F(4) + M(1) = 10 semanas
A(5) + E(5) + K(4) + M(1) = 15 semanas
 Acortamiento de una actividad 37

.- A(5) + E(5) + L(3) = 13 semanas

A(5) + D(7) + G(3) + J(5) = 20 semanas
A(5) -I- D(7) + G(3) + 1(4) + M(1) = 20 semanas
A(5) D(7) + 11(7) + M(1) = 20 semanas
8.- C(2) + K(4) + M(1) = 7 semanas
0.- C(2) + L(3) = 5 semanas
por lo tanto la red nos quedaria de la siguiente manera:

B2
t(3)=15

t(t)=2o

(3)

fig. 2.10
El costo del proyecto esta representado en la siguiente tabla:
 Capítulo 2. LA TECNICA CPM EN LA SECUENCIA DE PROYECTOS

No
j Crítica crítica

1 5 100
3 2 50
4 2 150
2 7 200
14 5 20
5 4 20
3 3 60 8
25 6 1 46 3
35 3 1 10
3t 5 1 85
45 4 100
4t 3 140
ó.t
1 220
20 Costo direct o mínimo 1217

tabla 2.6

Quinta Programación
unes ahora son:

sto = 33
o = 25
costo = 18
ódemos observar la mejor opción es la número 3 con un aumento de 18 por unidad
que el costo del proyecto pasaría de 1217 a 1235 y la duración del proyect o será de 19
mo podemos ver en los caminos:
) .1(5) = 7 semanas
I(4) + M(1) = 7 semanas
F(4) + M(1) = 10 semanas
E(5) + K(4) + M(1) = 15 semanas
E(5) + L(3) = 13 semanas
 jato de una actividad 39

D(7) + G(2) + J(5) = 19 semanas

D(7) + G(2) + 1(4) + M(1) = 19 semanas
D(7) + 11(6) + M(1) = 19 semanas
K(4) + M(1) = 7 semanas
+ L(3) = 5 semanas
o la red nos quedaria de la siguiente manera:

B(2)
t(3)=14
J

t(t)=19

(3)

fig. 2.11
el costo representado por la siguiente tabla.
 Capítulo 2. LA TECNICA CPM EN LA SECUENCIA DE PROYECTOS

Duración Modificación Costo directo Modificación

de duración de costos
No
Crítica crítica

5 100
3 2 50
4 2 150
2 7 200
4 5 20
5 4 20
2 3 2 1 60 10
2 5 6 1 54
8
5 3 13
5 90
5 4 100
4 t 3 140
5 t 1 220
ron 19 o o 1111 111111. 0 1235
tabla 2;7

Sexta Programación
las siguientes opciones:
Oto = 33
da
esto de 25
oge la actividad D y se reduce 2 semanas.
podemos observar la mejor opción es la número 2 con un aumento de 25 por unidad
qt.; 'r que el costo del proyecto pasaria de 1235 a 1285 donde y la duración del proyecto será
dades como podemos ver en los caminos:
(2 ) + J(5) = 7 semanas
/(2) + I(4) + M(1) = 7 semanas
5) + F(4) + M(1) = 10 semanas

(5) + E(5) + K(4) + M(1) = 15 semanas

(5) + E(5) + L(3) = 13 semanas
(5) + D(5) + G(2) + J(5) = 17 semanas
(5) + D(5) + G(2) + I(4) + M(1) = 17 semanas
 ottamien to de una actividad 41

A(5) + D(5) + ii(6) + M(1) = 17 semanas

C(2) + K(4) + M(1) = 7 semanas
- C(2) + L(3) = 5 semanas
¿ir lo tanto la red nos queda de la siguiente manera.

B
t(3)=12

t(t)=17

L(3)

fig. 2.12
quedando representado el costo mediante la siguiente tabla:
 Capítulo 2. LA TECNICA CPM EN LA SECUENCIA DE PROYECTOS

Duración Modificación Costo directo Modificación

de duración de costos
No
Crítica crítica

100
50
150
2 200
4 20
5 20
3 70
5 62
5 13
90
45 100
4t 140
220
17 Costo directo mínimo

tabla 2.8

Séptima Programación
opción que tenemos es:
to de 33 por unidad y se puede reducir en 3 semanas por lo tanto el tiempo se reduce
anas y el costo aumenta 99 unidades es decir aumenta de 1285 a 1384 unidades.
to la red nos queda de la siguiente manera:
 ento de una actividad 43

t(3)=9
t(1)=-2 J5

t(5)=12 t(t)=14

L(3)

t(4)=7
11(6)

fig. 2.13
o esta representado en la siguiente tabla:
ividad Duración Modificación Costo mínimo Modificación
de duración de costos
No
Crítica crítica

1 2 100
3 50
4 150
2 5 250
4 20
5 20
3 2 70
5 62
5 13
t 5 90
5 100
t 140
t 1 220
14 Costo directo mínimo

tabla 2.9
 Capítulo 2. LA TECNICA CPM EN LA SECUENCIA DE PROYECTOS

algunas actividades no sean críticas es decir no tienen la mínima duración, podemos

e ya encontramos un camino en el cual todas las actividades estan con su mínima
or lo tanto ya hemos terminado y podemos decir que para realizar nuestro proyecto se
en el costo un total de 1384 con un tiempo de 14 semanas.
nces este procedimiento podemos observarlo en la siguiente tabla en la cual nos indica el
ue ha sucedido al disminuir los tiempos en algunas actividades y en el cual se puede elegir
endo del costo alguna programación de las anteriores y en este se calculan las olguras y
db inicio y terminación correspondiente a cada actividad.

costo
1384
1285
1235
1217
1201
1171
1158
1150

14 17 19 20 21 23 24 25 duración
fig. 2.14
lo tanto podemos decir que en un problema complejo existen miles de duraciones costo
cada duración determinada por eso decimos que seria muy tardado por este método. Sin
go con un modelo matemático se hallaría fácilmente la solución del costo total mínimo de
uracion.

Representación Lineal del CPM

e a existido una relación entre el costo y la duración de una actividad en un proyecto y por
to podremos aseguras que:
i) El máximo costo del proyecto se alcanza cuando todas las actividades han sido programadas
mínima duración.
I)) El mínimo costo se da si todas las actividades han sido programadas con duración máxima.
Entre estos 2 condiciones existe un número infinito de caminos que relacionan la duración y el
o del proyecto. Pero solo existen unas cuantas que lo llevan a un costo óptimo. El problema
fuste en encontrar las actividades del proyecto que influyan en la duración de éste y especificar
ellas combimaciones de duraciones de actividades que den lugar al costo óptimo para una
ación determinada del proyecto.
 Lineal del CPM 45

341 nos indica como determinar los caminos críticos a traves de la red eligiendose
activid ad de mínimo costo por unidad de tiempo, disminuyendo su tiempo mínimo
ta que aparezca un nuevo camino crítico que no contenga a tal actividad
vidad A(i,j) el costo se calcula por medio de la fórmula
C(i,j) = c(i,j) - P(i,j)t(i,j)
s la función de costo, c(i,j) es una constante fija y P(i,j) es el incremento que
actividad por cada unidad que disminuye en el tiempo.

PO,D=c4101
s la duración mínima y D(i,j) es la duración máxima,y t(i,j) es la duración de la

be cumplirs que:
0<d(i,j)<t(i,j)<D(i,j)

t(i,j) VA(i,j)
empo de inicio más rápido del evento Inicial N, y el evento final Nt se dan como
TIME, = O
T IM Rt =
una constante que nos representa la duración del proyecto, la cual es muy importante
acionado con el costo total del proyecto. Deseamos encontrar el costo mínimo cuando
equeña posible. Es decir la forma mas barata de hacer el proyecto lo más rápido

to diremos que el costo del proyecto viene dado de la siguiente manera:

> c(i,i)= E (c(i,j)- .0)

A(i,j) A(i,j)

lema consiste en:

Mitt E C(i, j)
A(i,j)

O< < j) < D(i,j) VA(i, j)

TIMRi > T I M Ri t(i,j)

 Capítulo 2. LA TECNICA CPM EN LA SECUENCIA DE PROYECTOS

TIMR, O

TIMRi = A

objetivo quedaria:

Min E c(id) . M in E (c(i,j)— P(i, j)t(i, j))

A (i ,j) A(i,j)

do un pequeño cambio nos queda de la siguiente manera.

• Min E c(i,;) , E C(i, - Max E ni,j)ki,...1)

A(i,j) A(i,j) A(i,j)

= constante — Max E P(i, j)t(i, j)

A(i,j)

arto este problema se convierte en un problema donde debemos:

Max E P(i,j)t(i,j)
A(i,j)
0<d),<A<DA

TIMR] > TIMRi +t(i,j) V A(i, j)

TIMR, O

TI M =

odelo Matemático del CPM

anterior observamos que para acortar un proyecto existen muchas duraciones, las cuales
114.1-fiaron en ocasiones haciendo algunas combinaciones de actividades y escogiendo la de
o hasta alcanzar la mínima duración que no se puedan reducir más.
 delo Matemático del CPM 47

ra analicemos la siguiente expresión:

c(i,j) P(i,j)t(i,j)
de sabemos que P(i,j) es el costo por unidad de tiempo encontrado de la siguiente manera:
P(ij) =
unción t(i,j) de una actividad cumple con la siguiente restricción:
O < d(i, j) t(i, j) D(i, j)
ecir no puede ser mayor que D(i,j) o menor que d(i,j).
nces el costo máximo del proyecto es la suma de todos los costos directos individuales con
definidos y se representa de la siguinte manera:

P( A) = E [c( - 13(i,i)t(i,./)]
'

e A(i,j) indica el conjunto de actividades que forma la red.

o tanto el problema consiste minimizar la ecuación:

P( A) = E [c(i,j) —
A(i,j)
nihnt(i/..7)1

O < d(i, j) < D(i, j)

t(i,j) t(j) — t(i)
t(s) = O
t(t) = A

e
TIMR,
TIMRi
uales son los tiempos lo mas pronto posible de terminar y comenzar la actividad A(i,j)
amente; t(s) es el tiempo del primer suceso y t(t) el tiempo del últimos suceso de la red el
nominamos A , con un proyecto de n 1 actividades.
oblema consiste en como encontrar un conjunto de A(i,j) en la red con el costo mínino
a valor de A.
 Capítulo 2. LA TECNICA CPM EN LA SECUENCIA DE PROYECTOS

er resolver este problema se puede plantear como un problema de Programación Lineal

ca de la siguiente manera.

f t(i, j) < D(i, j)

1 —t(i, j) < —d(i, j)
ones paramétricas
{ ti A
ER, ( d)-
ER, t(i,i) 
A

R, indica un camino entre s y t para determinado valor de A

P(A) se debe de minimizar entonces es lo mismo

minP(A) = > [c( im - p(i,i)t(i,j)]

A(i,j)

M az E ni, »t(i, j)
A(id)

t(i, j)+ t(i) — t(j) <

t(t) — t(s) A
t(i, j) < D(i, j)
—t(i, j) < — d(i, j)
Et(i, j) < A

E t(id) <
R2
A

11

,,

11

E j) < A
Rq
 Modelo Matemático del CPM 49

Estas son las restricciones del problema que esta en forma de Programación Lineal Paramétrica.
Veamos con un ejemplo como plantear el problema en forma de Programación Lineal Paramétrica:
Ejemplo 1
Tenemos una red sencilla:

fig 2.17
Los costos y la duración de cada actividad se detallan en la siguiente tabla:
Actividad Duración Costo unitario
Xj i,j Máxima(D) Mínima(d) Pi
Xs s,1 4 1 P3=5
X1 1,2 6 1 P1=4
X2 s,2 12 3 P2=3
Xt 2,t 3 1 Pt=2

tabla 2.11
Se minimiza la función de costos:

P(A) = E(c i — PiXj)

o lo que es lo mismo:

minP(A) = ci — tnax E PiXj

como E ci es constante entonces realizar lo siguiente:

rnaz(Z = Pin
50 Capítulo 2. LA TECNICA CPM EN LA SECUENCIA DE PROYECTOS

Según el ejemplo esta función será:

mazZ = 5X, + 4X13X2 2X

sujeta a:

X, <4
—1
X1 <6
-x1 < —1
X2< 12
—X2 < —3
Xt <3
—Xt < —1
X, + Xt < A
X2 + Xt < A

Entonces se pretende encontrar los valores de X,, X1, X2, yXt que satisfagan la función y que
cumplan con todas las restricciones.
Para resolver nuestro problema con mayor facilidad cambiemos el primal por el dual añadiendo
unas variables de holgura y este nos quedaria de la siguiente manera:

rn nZ = 4X, — + 6X 2 Xt + 12X5 — 3X63X7 — X8 + A (X9 + X1.0)

Restringida a:
— X1 + X3 — X11 = 5
X2 — Xt + X9 —X12 = 4
X5 — X6 +X 0 —X 13 = 3
X7 — X8 + X9 -E Xio — X14 — 2
donde X11 , X12, X13, yX14 son variables de holgura:
Fulkerson en lugar de resolver el problema de Programación lineal original, resuelve el problema
dual. El cual tiene caracteristicas de flujo en redes, el cual consiste en encontrar la manera de enviar
la cantidad máxima de flujo desde el suceso fuente al suceso destino de acuerdo a la capacidad de
cada uno de los sucesos.
 elo Matemático del CPM 51

ntinuación veamos con un ejemplo como se resuelve la ecuación obtenida anteriormente la

la siguiente:

max E P(i, j)t(i , j)

t(i, j) t(i) — t(j) < O

—t(s) + t(t) < A

t(i,j) < D(i, j)

—t(i, j) < j)

ene la siguiente red

fig 2.18
valores de cada actividad tanto en costo como en duración se dan en la siguiente tabla:
 Capítulo 2. LA TECNICA CPM EN LA SECUENCIA DE PROYECTOS

Actividad Duración Costo Directo Costo por

unidad de
máxima tiempo Observaciones
mínima máxi:nanínima
Deno PO,j)
j D(i,j) d(i,j) c(i,j) CO,])
mina
ción
tiempo de
TP s 1 0 0 0 0 0 Preparación
G s 4 22 2 0 50000 No continua
A 1 2 8 4 420000 700000 70000
B 1 3 14 12 800000 960000 80000
C 2 3 12 6 1000000 1300000 50000
D 2 4 18 14 1080000 1200000 30000
E 3 4 10 8 300000 480000 90000
F 3 5 8 2 1000000 2200000 200000
II 4 5 14 12 1200000 1500000 150000
5 t 6 6 300000 300000 No reducible

tabla 2.12
Planteemos este problema.
Como se quiere minimizar la función costo total directo:

P( A) = i) — »t(i, i)1

o lo que es lo mismo-

P(A) -= E c ( i, E ni, Bt(i,

j) - j)

entonces como E c(i, j) es constante entonces maximicemos:

max Z = E P(i, j)t(i, j)
Para nuestro ejemplo la función objetivo es:
max Z = Ot(s,1) Ot(s,4) + 70000t(1,2) 80000t(1,3) 50000t(2,3) 30000t(2,4) 90000t(3,4)
200000t(3,5) 150000t(4,5) Ot(5,6)
2.6. Modelo Matemático del CPM 53

t(s,1) t(8) - 1(1) < 0

t(s,4) «e) - t(4) <

t(1,2) 1(1) 1(2) < O
1(1,3) t(1) t(3) <o

1(2,3) 1(2) - t(3) < 0

1(2,4) t(2) t(4) <o

1(3,4) 8(3) - 4(4) < 0

1(3,5) t(3) t(5) <o

1(4,5) 1(4) - 8(5) <o

1(5,1) t(5) - t(t) <
sujeta a:
- 1(8) t(t) <
t(4,1) <
t(s,4) 22
1(1,2) 8
t(1,3) 14

1(2,3) 12
t(1,4) 18

1(3,4) 10
1(3,5) 8
1(4,5) < 14
1(5,0 < 6

-t(s,1) <
-t(s,4) -2
-1(1,2) -4

4(1,3) -12
-1(2,3) -6
-1(2,4) -14

-1(3,4) -8
-8(3,5) -2
4(4,5) -12
-1(54) -6

Estas condisiones son del primal, pero si a cada grupo del primal se le asigna una variable del
dual; por ejemplo f(i,j), v, g(i,j) y h(i,j) respectivamente. Con estas variables duales se colocan en
cada columna de la matriz y así podemos poner el problema de la siguiente manera:
Entonces si encontramos la transpuesta la funcion objetivo sera:
MM W =00,1) + 22g(5,4) + 8g(1,2) + 14g(1,3) + 12g(2,3) + 18g(2,4) + 10g(3,4) + 8g(3,5)
+ 14g(4,5) + 6g(5,6) - Oh(0,1) - 2h(0,4) - 4h(1,2) - 12h(1,3) - 6h(2,3) + 14h(2,4) - 8h(3,4) -2h(3,5)
- 12h(4,5) - 6h(5,6)
restringidas a:
54 Capítulo 2. LA TECNICA CPM EN LA SECUENCIA DE PROYECTOS

f(s,1) + g(s,1) - h(s,1) = P(s,1)

f(s,4) + g(s,4) - h(s,4) P(s,4)
f(1,2) + g(1,2) - h(1,2) = P(1,2)
f(1,3) + g(1,3) - h(1,3) = P(1,3)
12,3) + g(2,3) - h(2,3) = P(2,3)
f(2,4) + g(2,4) - h(2,4) = P(2,4)
f(3,4) + g(3,4) - h(3,4) = P(3,4)
f(3,5) + g(3,5) - h(3,5) = P(3,5)
f(4,5) + g(4,5) - h(4,5) = P(4,5)
f(5,t) + g(5,t) - h(5,t) = P(5,t)
la cual podemos poner de la siguiente manera:
f(i,j) g(i,j) - h(i,j) = PO,j)
También tenemos las restricciones
f(s,1) f(s,4) - A = O
f(s,1),+ 11,2) + f(1,3) =
- 11,2) + f(2,3) + f(2,4) = O
f(1,3) - f(2,3) + f(3,4) + 13,5) = O
- f(s,4) - 12,4) + f(3,4) + 14,5) = O
- f(3,5) - f(4,5) + f(5,t) = O
- f(5,t) + y = O
las cuales se pueden reacomodar de la siguinte manera:
f(s,1) + f(s,4) = A
f(s,1) + f(1,2) + f(1,3) = O
- f(1,2) + f(2,3) + f(2,4) = O
f(1,3) - f(2,3) + f(3,4) + 13,5) =
f(s,4) - f(2,4) + f(3,4) + f(4,5) = O
- f(3,5) - 14,5) + f(5,t) = O
- f(5,t) = -
 Modelo Matemático del CPM 55

De este grupo de ecuaciones se puede observar lo siguiente red:

fig 2.19
podemos observar que todo lo que entra al 2 tiene que salir es decir,
f(1,2) + f(1,t) - f(s,1) O
por lo tanto el grupo de ecuaciones vistas anteriormente se pueden poner de la siguiente manera:

y i=s
E f( i)- E A l( I i) = O i$s i$t
3E6 + (s) KE6— (i) —v i = t

Donde 5+ (i) es el antecesor de i, 8 + (i) es el sucesor de i la v es el flujo y debe de ser lo que sale
el suceso origen igual que el que llega al suceso destino lo mismo se cumple en cada uno de los
icesos, por lo tanto la diferencia entre lo que sale y lo que entra siempre es cero.
Entonces tenemos que la función objetivo del dual nos queda de la siguiente manera:

Av + [E D(i,j)g(i,j) — E d(i, j)h(i, j)

entonces como el máximo del primal es igual al mínimo del dual, nos quedaria:

max E P(i, j)t(i, = rnin(Av + E D(i,j)g(i,j) — E d(i, j)h(i, i))

Entonces resolviendo:

ruin[Av E D(i, DO, j) — d(i, j)h(i, j)]

 Capítulo 2. LA TECNICA CPM EN LA SECUENCIA DE PROYECTOS

quedarla resuelta la ecuación:

max P(i, j)t(i, j)

Para encontrar la solución que nos proporcione el valor óptimo. Entonces en la ecuación:

max E P(i, j)t(i, j) = min(Av + E mimo,» — E d(i, j)h(i, j))

debe de ser por lo menos cero ya sea g(i,j) o h(i,j) entonces por dualidad
si:
t(i,j) =D(i,j); t(i,j) > d(i,j):
como:
h(i,j)[t(i,j)-d(i,j) = O entonces h(i,j) =
Si:
t(i,j) = d(i,j); entonces t(i,j) < D(i,j):
como:
g(i,j)[t(i,j)-D(i,j) = O entonces g(i,j) = O
Por lo tanto de la ecuación:
f(i,j) g(i,j) - h(i,j) = P(i,j)
se optiene:
g(i,j) = max[0, P(i,j) - f(i,j)]
h(i,j) = max[0, f(i,j) - P(i,j)]
de lo anterior se puede decir que si el costo por unidad es mayor que el flujo entonces au-
tomáticamente h(i,j), O pero si el flujo es mayor que la capacidad entonces g(i,j) = O entonces por
estas dos conclusiones tendremos nuestro problema se puede representar de la manera siguiente

min[Av E D(i, j)(13(i, j) — f(i,j))]

min[Av — E d(i, j)(f (i, j) — P(i,j))]

Fulkerson hizo un cambio de variables, remplazando a f(i,j) por dos variables no negativas.
f(i,j) f(i,j; 1) + f(i,j;2)
donde las nuevas variables tienen las siguientes restricciones.
lija) < c(i,j)
 Modelo Matemático del CPM 57

f(i.j;2) _< oo
cuando el flujo es mayor que la capacidad se toma la ecuación siguiente:

min[Av + E D(i, j)P(i, j) — > D(i, j)f (i, j; 1)]

si el flujo es igual o menor que infinito, se toma la ecuación:

min[Av — E d(i, j)f (á, j; 2)]

ya que cuando f(i,j) es mayor que P la ecuación

f(i,j) = f(i,j;1) f(i,j;2)
se combierte en

= P (i ,j ) f(i:1;2)
y sustituyendo en

Av — rain[E d(i, j)[f (i, j) — P(i,j)]

se obtiene

Av — E d(i,j)f(i,j; 2)

Por lo tanto podemos poner la ecuación

Av + min[ED(i,j)g(i, j) — E d(i, j)h(i, j)]

sin tomar en cuenta la constante y definiendo:

P(i, j) cuando k = 1
c(i, j; k)
oo cuando k=2

D(i, j) cuando k = 1
= j) cuando k = 2

se puede poner de la siguiente manera:

Av — rain[E E d(i,j;k)f(z, j; k)
 Capítulo 2. LA TECNICA CPM EN LA SECUENCIA DE PROYECTOS

Con las siguientes restricciones:

f d; c(i,j;k)

v,i= s
E j; k) — E f(1,i;k)= 0,i s, t
ea+ (.0 le5+ (1) —v,i-= t

como Fulkerson divide la variable f(i,j) en dos variables no negativas las cuales son 1(i11) y
,12), entonces en cada actividad de la red existen dos conductos para pasar el flujo y cada uno
ne su capacidad asignada c(i,j;k) y esta se representa en siguiente figura:

f(i11).< c(i,j)
f(i12)< 00

fig. 2.17
Por lo tanto podemos decir que en el instante en que la duración máxima el flujo es cero; pero
iniciar la aceleración, el flujo pasa según la capacidad de 1.(i11). Al llegar a la duración mínima,
costo sera f(i12), y el flujo pasará por el segundo conducto.

.7 Como Determinar P(A)

ltecordemas que para encontrar el costo óbtimo de nuestro problema se tenia la siguiente función:

TrainP(A) = E c(im_ mar E P(i, j)t(i, j)

A(i,j) A(i,j)

P(A) = E c(i, j) — nzin[Av + E D(i , j)P(i , j) — E ck i d k)f( i , j ; k)]

A (i ,j ) A(i,j) A(i,j)

P(A) = E c( im_ E D(i, j).13 (i, j) — raintAv — EE j; f (i, j; k)]

A(i,j) A(i,j) 1 A(i,j)

Entonces si a
 59
2.7. Como Determinar P(A)

c(i, j) — E D(i, j)P(i, j)

Ai,i)

se le llama I< entonces nos quedaría:

2
P(A) = K — min[Av — E E d( i , j ; k) f (i, j; k)]
A(i,j)

El problema consiste en encontrar un flujo máximo f(i,j;k) que pase desde t(s) hasta t(t) por la
red para asi poder mínimizar la ecuación:

Av — E E d(i, j;k)f (i, j; k)]

Este flujo puede pasar por dos conductos o caminos, se puede ir desde t(i) a t(j) o de t(j) a t(i);
es decir el flujo puede trasladarse de la siguiente manera:

Para poder lograr el objetivo de encontrar el flujo máximo que va desde el nodo origen al nodo
destino es necesario utilizar una serie de marcajes.
Pero para poder comenzar el marcaje se debe de cumplir:

t(s)=0
d(i,j;k) t(i)-t(j) < O entonces fli,j;k)=0
Lo que nos indica esta condición es que cuando la actividad no sea crítica entonces no pasa
ningun flujo.
3.- d(i,j;k) t(i)-t(j) > O entonces gi,j;k)=P(i,j;k)
Aqui nos indica que al reducir las actividades críticas, el flujo pasa según su capacidad P(i,j:k)
Estas 3 condiciones deben de cumplirse para poder optimizar la ecuación:

Av — E E d( i , j ; f j;
60 Capítulo 2. LA TECNICA CPM EN LA SECUENCIA DE PROYECTOS

restringida a:

O < f j : k) < j; k)

Para lograr el objetivo, primero se trata de encontrar la A mas larga, la cual nos reprecenta el
camino crítico y la cual determina la A = t(t), por lo tanto si se logra encontrar el t(t) entonces se
puede decir que se ha encontrado un camino abierto y por lo tanto si no se logra encontrar al t(t)
entonces sera un camino cerrado.
Si se logra encontrar un camino abierto entonces se podra decir que se a logrado marcar todos
los nodos desde t(s) hasta t(t).
Cuando d(i,j;k)=d(i.j;k)-H(j)-t(i)=0 el flujo se mueve hacia adelante con un f(i,j;k)<c(i,j;k) y
se movera hacia atrás cuando d(i,j;k)=0 y f(i,j;k)>0.
Cuando se conoce el flujo máximo al cual se le denota E (n) el cual es la suma de todos los t(s),
t(1), t(2).... t(t), Entonces podemos añadir el valor de E (u) a los flujos positivos y se les resta a los
negativos. Ya terminado este procedimiento se busca una nueva cantidad de flujo que pase por los
conductos; que siga cumpliendo con las condiciones anteriores mencionadas e intentandose pasar
un nuevo flujo para comprobar si es posible encontrar otro camino abierto. Cuando no se puede
encontrar el t(t) entonces se puede decir que existe un camino cerrado y por lo tanto no fue psible
marcar el último nodo y también se dice que no se 'pudo encontrar algún flujo, si no se encontro
flujo se resta una cantidad 6 positiva a todos los t(i) que no se han marcado y se busca una nueva
A' la cual esta formada por los nuevos ti (i, j).
Estos ti (i, j) y A' son calculados utilizando la fórmula:

(i, j) min[D(i, j),t(j) — t(i)1

El costo del proyecto P(A) es lineal entre los valores de A originados por el camino cerrado.
El primer A debe de cumplir la condicion de tener un flujo cero, y el costo directo sera P(A)=K,
donde K es la suma de todos los costos del programa donde se han manejado con los valores
correspondientes a todo normal. Al encontrar un nuevo valor de A' donde este nuevo valor será
menor que el anterior el cual se óptiene de la siguiente manera:

P(A') = K — [Aiti — j; f(ij; k)]

donde:
—[A v - EE j; k) f(ij; k)]

nos indica el incremento que sufrio A' y se terminará el procedimiento cuando se encuentre un
camino crítico en el cual todas las duraciones esten a su máxima capacidad y por lo tanto será el
tiempo mínimo en terminar el proyecto.
2.7. Como Determinar P(A) 61

El proyecto será terminado cuando se encuentre un camino crítico el cual todas las las actividades
esten a su mínima duración es decir cuando el flujo pase por el segundo conducto.

Detalle del proceso de marcaje

Calcular el valor de A1 el cual es el t(t) más largo el se obtiene de la siguiente manera:
t(s) = O
t(j) max[t(i) D(i,j)]
t(t) O A1
f(i,j;k) = O
P(A1) = K
Proceso de marcaje:
Al iniciar el marcaje se pasa un flujo f(i,j:k) en los t(i) y estos satisfacen las ecuaciones:
t(s) = O
d(i,j;k) t(j) - t(i) < O para f(i,j;k) = O
d(i,j;k) t(j) - t(i) > O para f(i,j;k) = c(i,j;k)
El proceso de marcaje se divide en dos partes:
Primer marcaje:
Se le asigna la marca[-,-,-s(s) = ce] al nodo t(s) y se le llama marcado pero no esplorado y
tosos los demas son no marcados, buscamos todos los nodos t(j) no marcados que tengan d(i,j;2)
= O para observar si forman un camino desde t(s) hasta t(t) y lo marcamos con [s,2,+ e(s) = oo]
y observamos si existe un camino crítico.
Podemos observar que dentro de cada marca existen 4 indicaciones:
la primera señala el nodo sucesor inicial
la segunda señala el conducto k = 1 o k = 2
la tercera señala la dirección del flujo
la cuarta señala la cantidad de flujo que pasa por A(i,j)
Se repite la operación de marcaje hasta que t(t) pueda ser marcado o no, en el caso primero, se
señala que la eceleración del proyecto esta concluida y no se puede reducir más la A, ya que todas
las actividades estan en su mínima duración y en el caso segundo se pasa al segundo marcaje.
Segundo marcaje:
62 Capítulo 2. LA TECNICA CPM EN LA SECUENCIA DE PROYECTOS

Si existen algunos nodos que han sido marcados con [i,2,-E,e = oo] deben de ser conserbados
y el proceso de marcaje continua con los 7/(i,1k) = O y seleccionar cualquier nodo t(i) marcado
y no explorado, se buscan todoa los nodos t(j) para ser marcados, los cuales se encuentran de la
siguiente manera:
si -c-/(i,j;k) = O y f(i,j;k) < O asignamos a t(j) la marca [i,k,-F,E(j)] donde e(j) = min[e(j),
c(i,j;k) - f(i,j;k)]
si a(i,j;k) = O y f(i,j;k) > O asignamos a t(j) la marca [i,k,-,e(j)] donde e(j) = min[s(j), f(i,j;k)]
Si llegamos al nodo t(t) sera un camino abierto si no sera un camino cerrado, en el primer caso
se cambia el flujo y en el segundo se cambia el tiempodel asuceso t(i) no marcado.
Cambio de flujo
Se suma s(t) a los flujos exiastentes desde (t) hasta t(s), si el suceso t(t) ha sido marcado con
[j,k,+,6(j)] se suma e(t) al flujo f(i,j;k) pero si a sido marcado con [i,k,-,e(j)] se resta al flujo f(i,j;k)
y se repite el proceso hasta llegar a t(s) al terminar se borran los marcajes menos los [i,k,-F,E(j) O
co] y se marca de nuevo con este nuevo f(i,j;k).
Cambio de tiempo en los sucesos
Se busca:
Al [A(i,j) donde i es marcado y j no, con c/(i,j;k) < O
A2 [A(i,j) donde i es no marcado y j si, con a(i,j;k) >O
se calculan y se comparan llamandoseles:

ól = j; k)]

62 = rninA2 [1-714 j ; k)]

donde:

6= 62]

y cambiamos los sucesos restando 6 a todos los t(i) no marcados.

Al terminar la operación se borran las marcajes y se vuelve a comenzar el proceso de maecaje
buscando otro camino abierto o cerrado para calcular otro P(A).
 Capítulo 3

Ejemplo con Aplicaciones del

Algoritmo de Fulkerson

El principio del programa de flujo es considerar una red de flechas conectando dos nodos donde
uno es el nodo fuente y el otro nodo destino y, entre ellos, existe una serie de nodos intermedios.
A cada flecha de la red se le asigna una capacidad limitada para transportar el flujo y éste
puede moverse en ambas direcciones.
El algoritmo de flujo consiste en encontrar la forma de enviar la cantidad máxima de flujo desde
el nodo fuente al nodo destino, de acuerdo a la capacidad limitada.

3.1 Ejemplo
Veamos un ejemplo paso a paso para observar cómo se utiliza la función a maximizar.
También la explicación más clara sobre el Algoritmo de fulkerson sobre el proceso de progra-
mación con respecto al costo directo total mínimo Y para resolver este tipo de problemas usaremos
la tabla 4.1 En la cual podemos observar que, los datos que nos estan dando son, las actividades,
la duración mínima y la duración máxima, el costo mínimo y el costo máximo, el costo por unidad
el cual se obtiene restando el costo máximo al costo mínimo y dividiendolo entre la duración que
se obtiene al restar la duración máximo y la duración mínimo, y tambien nos indican cuales son
las actividades criticas donde se usan semanas para el tiempo y pesos para el costo.

63
 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

Actividad Duración Costo Directo Costo por uni-

Observaciones
Máxima Mínima Mínimo Máxima dad de tiempo
Deno
mina i j D(i,j) d(i,j) c(i,j) C(i,j) P(i, j)
ción
A s 1 5 2 100 199 33
B s 3 2 1 50 80 30
C s 4 2 1 150 180 30
D 1 2 7 5 200 250 25
E 1 4 5 2 20 41 7
F 1 5 4 2 20 40 10
G 2 3 3 1 60 80 10
11 2 5 10 6 30 62 8
I 3 5 5 2 10 19 3
J 3 t 9 5 70 90 5
K 4 5 4 1 100 130 10
N 4 t 3 1 140 160 10
M 5 t 3 1 200 220 10

tabla 3.1
Este problema quedaria expresado en la siguiente red.
B

fig. 3.1
En la cual nos indica cómo deben de ir relacionadas las actividades, y cuál debe de comenzar
ero y cuál despues, y lo que se pide es determinar el flujo máximo entre s y t. Para resolver este
o de problemas tomaremos en cuenta solo las actividades, la duración mínima, duración máxima
3.1. Ejemplo 65

y el costo por unidad de tiempo y estos datos los podemos poner en una tabla de la siguiente
manera:
Actividad Duración Duración Costo por unidad
Máxima Mínima de tiempo
t(i,j) D(i,j) d(i,j) P(i,j)

«5,1) 5 2 33
t(s,3) 2 1 30
t(s,4) 2 1 30
t(1,2) 7 5 25
t(1,4) 5 2 7
t(1,5) 4 2 10
t(2,3) 3 1 10
t(2,5) 10 6 8
t(3,5) 5 2 3
t(3,t) 9 5 5
t(4,5) 4 1 10
t(4,t) 3 1 10
t(5,t) 3 1 10

tabla 3.2
De la tabla 3.2 podemos formar dos tipos de redes, una estara formada por duración y otra por
el costo por unidad. En la primera se tomaran en cuenta la duración mínima y la duración máxima
y en la segunda se tomára en cuenta el costo el cual se le denominará flujo.
La primera red nos quedaria de la siguiente manera:
(1,2)
(Duración mínimo, Duración máximo)
 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

y la segunda red, en la cual simplificamos el costo por unidad para facilitar nuestro trabajo nos
darla de la siguiente manera:
(0,30) (flujo, capacidad máxima (P(i,j)))

fig. 3.3
Nuestro problema consiste en encontrar el valor óptimo de P(A) el cual nos representa el costo
el proyecto, tambien nos maximiza el flujo en el menor tiempo posible y el valor de A nos representa
tiempo para terminar el proyecto. Este valor se puede encontrar con la siguiente formula:
P(A)=K-[Av-E j; k) f (i, j; k)]
donde A significa el tiempo máximo de la red, y significa el flujo de la red, K es el costo, d(i,j;k)
es el tiempo de la actividad, si K=1 es el tiempo máximo, si K=2 sera el mínimo y f(i,j;k) es el
flujo actual en el conducto K.
Y para resolver este problema debemos de maximizar
Av- E d(i, j; k) f (á, j; k)
para esto, inicializamos todas las etiquetas en la segunda red ya que la primera solo sera para,
el cambio de tiempo, en esta red utilizaremos cuatro indicaciones, la primera indica el antecesor
en la cadena aumentante de flujo, la segunda señala el conducto, la tercera indica la dirección del
flujo, el signo positivo significa marcha adelante y el negativo marcha atrás y la ultima enumera la
cantidad de flujo (E) que puede pasar por la flecha(i,j).
 67

(0,30)
(flujo,Capacidad máxima)

Corrida de Escritorio

Pimero se calcula el primera con todas las actividades normales de duración del proyecto
omanda la primer red que es la de los tiempos en la cual, el costo total es mínimo y la duración
el proyecto es máxima, y lo podemos obtener de la siguiente red:
(1,2)

fig. 3.5
 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

de la siguiente manera:
t(s)=0
t(j)=máx [i( D(i,j)]
t(s)=0
(1)=max[5]=5
(2)=max[5 +1=12
(3)=max[0 + 2,12 + 3],máx[2,15]=15
t(4)=max[0 + 2, 5 + 5]=máx[2, 101=10
(5)=max[5 + 4,12 + 10, 15 + 5,10 + 4]=máx[9, 22, 20,14]=22
t(t)=max[15 + 9,10 + 3, 22 + 3]=max[24, 13, 25]=25
Entonces la duración normal del proyecto sera de 25 unidades por lo tanto el costo sera la suma
odos los costos máximos, es decir K = C(i,j).
Por lo tanto, la red nos quedaria de la siguiente manera:
(1,2)

fig. 3.6
Donde podemos observar que: A =25 y el flujo f(i,j;k)=0 y V el cual significa la totalidad del
flujo sobre la red y por lo tanto hasta este momento su volor es cero y el valor de K es la suma de
odos los costos de las actividades en su duración máxima, por lo tanto K = 1150.

P(A)= K-[AV - j; k)f (á, j; k)]

 Ejemplo 69

Entonces encontrando los valores de los d(i,j;k) de f(i,j;k) como todos pasan por el primer el
i nter conducto entonces:
K 1150
d(s,1;1) = 5
d(1,2;1) = 7
d(2,5;1) = 10
d(5,t;1) = 3
y los flujos todos son ceros por lo tanto:
P(25)=1150-[25(0)-(5(0)+7(0)+10(0)+3(0))]
P(25)=1150-[0-(0+0+0+0)]
P(25)=1150-[(0)-(0)]
P(25)=1150-O
P(25)=1150
Pasamos a la primera iteración:

Primera Iteración
Antes de iniciar el primer proceso de marcaje; es preciso calcular los valores:

7((i,j;1)=D(i,j)l-t(j)-t(i)

d(i,j;2)=d(i,j)-Et(j)-t(i)

con los cuales podemos formar la tabla siguiente:

 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

a(i,j;1)= 7/(i,j;2).=
t(i,j) t(i)-t(j) D(i,j)+t(i)-t(j) d(i,j)+t(j)-t(i)

t(5,1) 0-5=-5 5-5=0 2-5=-3

t(5,3) 0-15=-15 2-15=-13 1-15=-14
t(s,4) 0-10=-10 2-10=-8 1-10=-9
t(1,2) 5-12=-7 7-7=0 5-7=-2
t(1,4) 5-10=-5 5-5=0 2-5=-3
t(1,5) 5-22=-17 4-17=-13 2-17=-15
t(2,3) 12-15=-3 3-3=0 1-3=-2
t(2,5) 12-22=-10 10-10=0 6-10=-4
t(3,5) 15-22=-7 5-7=-2 2-7=-5
t(3,t) 15-25=-10 9-10=-1 5-10=5
t(4,5) 10-22=-12 4-12=-8 1-12=-11
t(4,t) 10-25=-15 3-15=-12 1-15=-14
t(5,t) 22-25=-3 3-3=0 1-3=-2

tabla 3.3

Primer Marcaje de la primera iteración

Asignamos la marca [-,-,-,s oo] al nodo t(s) al cual se le llama marcado, pero no explorado;
todos los demás nodos de la red son todavía no marcados. apartir de este nodo marcado buscamos
todos los nodos j no marcados que tengan un d(i,j:2) = O para observar si forman un camino crítico
desde t(s) hasta t(t), podemos observar que, en la tabla 3.3 los datos de d(i,j;2) no existen ceros
por lo tanto no se forma un camino crítico y por eso el proyecto se puede reducir en su tiempo de
duración .
La red nos quedaria de la siguiente manera:
3.1. Ejemplo 71

(0,30)
(flujo,Capacidad máxima)

fig. 3.7

Segundo Marcaje de la primera iteración

Apartir del nodo marcado buscamos todos los t(j) no marcados siguiendo el camino donde los
a(i,j;k)=0 para encontrar una cadena aumentante y los marcamos donde estos nodos quedaran
marcados pero no explorados.
Observamos que existe un cero en la actividad A(s,1), A(1,2), A(1,4) A(2,3), A(2,5) y A(5,t) todos
en d(i,j;1) por lo tanto marcamos a los nodos t(1), t(2), t(3), t(4), t(5) y t(t) de la siguiente manera:

a t(1) lo marcamos de la siguiente manera [s,1,+,33].

a t(2) lo marcamos de la siguiente manera [1,1,+,25].
a t(3) lo marcamos de la siguiente manera [2,1,+,10].
a t(4) lo marcamos de la siguiente manera [1,1,+,7].
a t(5) lo marcamos de la siguiente manera [2,1,+,8].
a t(t) lo marcamos de la siguiente manera [5,1,+,8].
la red nos quedaria de la siguiente manera:
 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

(0,30)
[s,1,+,33] +,10] (flujo,Capacidad máxima)
(0,5)

(0,33) (0,10) (0,3)

e >,°C)] (0,25)

(0,10) (0,10)
5 (0,10)
[2,1,+,8]
5,1,+,8]

(0,10)
(0,30)

[1,1,+,25]
(0,8)
fig. 3.8
or lo tanto, como hemos podido marcar, a t(t) tenemos una cadena aumentante, y por lo tanto
mos aumentar el flujo de la siguiente manera:

e toma el nodo t y su antecesor en la cadena aumentante (+5), como es positivo se busca en

ta de antecesores y se le suma el flujo de ese arco, que es la capacidad de ese arco (8), se busca
do t en la lista de sucesores del nodo 5 y se le suma 8 unidades al flujo de ese arco. y se realiza
smo procedimiento con los nodos 5, 2 y 1.Cuando ya llegemos al nodo s, hemos actualizado el
de la red quedandonos está de la siguiente manera.
3.1. Ejemplo 73

(0,30)
(flujo,Capacidad máxima)

fig. 3.9
Volvemos a marcar(segundo marcaje)
Utilizando la red anterior encontrar una cadena 'aumentante y la capacidad incremental de la
cadena con el flujo ya actualizado tomando encuenta los d(i,j;k)=0. podemos ver que existen los
mismos ceros que en la ocación anterior por lo tanto marcamos
a t(1) lo marcamos de la siguiente manera [s,1,+,25].
a t(2) lo marcamos de la siguiente manera [1,1,+,17].
a t(3) lo marcamos de la siguiente manera [2,1,+,10].
a t(4) lo marcamos de la siguiente manera [1,1,+,7].
como por la actividad A(2,5) ya se encuentra a su máxima capacidad entonces ya no se puede
pasar ningún flujo por lo tanto no pudimos marcar a t(t) y la red nos quedaria de la siguiente
manera:
74 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

(0,30)
[s,1,+,25] (flujo,Capacidad máxima)
12,1,+,10]
3 (0,5)

(8,33) (0,3)

(8,25)

(0,10) (0,10)
(0,30)
1,1,+,7]
[1,1,+,17]
(8,8)
fig. 3.10
Como el último suceso no esta marcado entonces no existe cadena aumentante por lo tanto
pasamos al cambio de los tiempos de los sucesos, el cual se hace de la siguiente manera: Se buscan
los : A1 =[A(i,j) donde i es marcado y j es no marcado, 7/(i,1k) < 0]
A2 =[A(i,j) donde j es marcado e i es no marcado, 2(i,j;k) > 0]

se calculan y se comparan llamandoseles:

81 = minÁi[-41(ii;k)]
82 = minA2[4ii;k)]
los cuales son:
-7(1,5;1)=13 -7(1,5;2)=15
-2(2,5;2)=4
-0,5;1)=2 -2(3,5;2)=5
-2(3,t;1)=1 -7(3,5;2)=5
-7(4,5;1)=8 -7(4,5;2)=11
-d(4,t;1)=12 -2(4,t;2)=14
tomandose:
6 rnin[61, 82]

donde el mínimo es 6 = 1
3.1. Ejemplo 75

Por lo tanto, el valor 1 se lo restamos a los tiempos de los nodos t(i) no marcados de la red que
nos representa los tiempos, por lo tanto se le restara al nodo t(5) y t(t) una unidad:
(1,2)

fig. 3.11
Donde podemos ver que el tiempo que era de 25 semanas se redujo a 24.
Para conocer cuánto fue el incremento que sufrió el costo primero encontremos los d(i,j;k) y los
f(i,j;k) que son los que sufrieron aumento en el flujo los cuales son:
d(s,1;1)=5 f(s,1;1)=8
d(1,2;1)=7 f(1,2;1)=8
d(2,5;1)=10 f(2,5;1)=8
d(5,t;1)=3 f(5,t;1)=8
donde podemos decir que el costo directo total en el tiempo de 24 es:
P(24)=1150-{(24)8-[5(8)+7(8)+10(8)+3(8)1}
=1150-{192-[40+ 56+80+241 }
=1150-{(192-200)}
=1150+8)
=1150+8
=1158
de donde P(24)=1158 es decir 8 pesos de incremento.
 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

Pasamsos a la siguiente iteración:

Segunda Iteración
Para poder comenzar con el marcaje se borran todas las etiquetas anteriores que ya teniamos
y calculamos los nuevos valores de d(i,j;1) y d(i,j;2) de la siguiente manera:
La red nos quedaria de la siguiente manera:
(0,30)
(flujo,Capacidad máxima)

fig. 3.12
y los valores de 2(i11) y 75/(i,j;2) de la siguiente manera:
3.1. Ejemplo 77

71(i,11)= a(i,j;2)=
t(i,j) t(i)-t(j) D(i,j)+t(j)-t(i) d(i,j)+t(j)-t(i)

t(s,1) 0-5=-5 5-5=0 2-5=-3

t(s,3) 0-15=-15 2-15=-13 1-15=-14
t(s,4) 0-10=-10 2-10=-8 1-10=-9
t(1,2) 5-12=-7 7-7=0 5-7=-2
t(1,4) 5-10=-5 5-5=0 2-5=-3
t(1,5) 5-21=-16 4-16=-12 2-16=-14
t(2,3) 12-15=-3 3-3=0 1-3=-2
t(2,5) 12-21=-9 10-9=1 6-9=-3
t(3,5) 15-21=-6 5-6=-1 2-6=-4
t(3,t) 15-24=-9 9-9=0 5-9=-4
t(4,5) 10-21=-11 4-11=-7 1-11=-10
t(4,t) 10-24=-14 3-14=-11 1-14=-13
t(5,t) 21-24=-3 3-3=0 1-3=-2

tabla 3.4

Primer Marcaje de la segunda Iteración

como t(s) ya estaba marcado entonces todos los demás nodos de la red son todavía no marcados,
apartir de este nodo marcado buscamos todos los nodos j no marcados que tengan un 7/(ij;2) = O
para observar si forman un camino crítico desde t(s) hasta t(t), podemos observar que, en la tabla
3.4 los datos de 2(i,j;2) no existen ceros por lo tanto no se forma un camino crítico y por eso el
proyecto se puede reducir en su tiempo de duración .
La red nos quedaría de la siguiente manera:
78 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

(flujo,Capacidad máxima)

fig. 3.13
pasamos al siguiente marcaje :

Segundo Marcaje de la segunda Iteración

Partiendo del nodo marcado buscamos todos los t(j) no marcados siguiendo el camino donde
los 71(i,j;k)=0 para encontrar una cadena aumentante y los marcamos donde estos nodos quedaran
marcados pero no explorados.
Observamos que existe un cero en la actividad A(s,1), A(1,2), A(1,4) A(2,3), y A(3,t) todos en
d(i,j;1) por lo tanto marcamos a los nodos t(1), t(2), t(3), t(4) y t(t) de la siguiente manera:

a t(1) lo marcamos de la siguiente manera [s,1,+,25].

a t(2) lo marcamos de la siguiente manera [1,1,+,17].
a t(3) lo marcamos de la siguiente manera [2,1,+,10].
a t(4) lo marcamos de la siguiente manera [1,1,+,7].
a t(t) lo marcamos de la siguiente manera [3,1,+,5].
la red nos quedaría de la siguiente manera:
 1 Ejemplo 79

(0,30)
[s,1,-F,25} (flujo,Capacidad máxima)
2,4+,101
(0,5)

(0,30)

fig. 3.14
Por lo tanto, como hemos podido marcar, a t(t) tenemos una cadena aumentante, y por lo tanto
podemos aumentar el flujo de la siguiente manera:
Se toma el nodo t y su antecesor en la cadena aumentante (3), como es positivo se le suma
el flujo al arco (3,t) 5 unidades y se realiza el mismo procedimiento con los nodos 2, y 1.Cuando
ya llegamos al nodo s, hemos actualizado el flujo de la red quedandonos está de la siguiente manera.

(0,30)
(flujo,Capacidad máxima)

fig. 3.15
Marcamos de nuevo el segundo marcaje.
 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

dizando la red anterior encontrar una cadena aumentante y la capacidad incremental de la

a con el flujo ya actualizado tomando encuenta los 7/(i,j;k)=0. podemos ver que existen los
s ceros que en la ocación anterior por lo tanto marcamos
(1) lo marcamos de la siguiente manera [s,1,+,20].

a t(2) lo marcamos de la siguiente manera [1,1,+,12].

lo marcamos de la siguiente manera [2,4+,10].
lo marcamos de la siguiente manera [1,1,+,7].
Como por la actividad A(3,t) ya se encuentra a su máxima capacidad entonces ya no se puede
ar ningún flujo por lo tanto no pudimos marcar a t(t) y la red nos quedaría de la siguiente
anera:
(0,30)
(flujo,Capacidad máxima)

fig. 3.16
Como el último suceso no esta marcado entonces no existe cadena aumentante por lo tanto
pasamos al cambio de tiempos de los sucesos, el cual se hace de la siguiente manera:
Se buscan los : A I =[A(i,j) donde i es marcado y j es no marcado, a(i,j;k)<0]
A2 =[(i,j) donde j es marcado e i es no marcado, Ci(i,j;k)>01

se calculan:
61 = minA, [-d(i,j;k)]

= Tninm [71(1xi;k)]
los cuales son:
 Ejemplo 81

4(1,5;1) = 12 -1(1,5;2)=14
=1(2,5;1) = 1 -7/(2,5;2)=5
-1(3,5;1) = 1 -1(3,5;2)=4
-7/1(3,5;2)=4
-1(4,5;1)=7 -714,5;2)=10
-14,t;1)=11 -d(4,t;2)=13
tomandose:
6 = min[81,82]
donde el mínimo es 5 = 1
Por lo tanto, el valor 1 se lo restamos a los tiempos de los nodos t(i) no marcados de la red que
os representa los tiempos, por lo tanto se le restara al nodo t(5) y t(t) una unidad y al mismo
lempo encontrando la nueva ruta quedandonos de la siguiente manera:
(1,2)

fig. 3.17
Donde podemos ver que el tiempo que era de 24 semanas se redujo a 23.
Para encontrar el costo busquemos los d(i,j:k) y los f(i,j;k):
d(s,1;1) = 5 l(s,1;1) = 13.
d(1,2;1) = 7 f(1,2;1) = 13.
d(2,3;1) = 3 12,3;1) = 5.
 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

cl,(2,5;1) = 10 f(2,5;1) = 8.

d(3,t;1) 9 f(3,t;1) = 5.
d(5,t;1) = 3 15,41) = 8.
donde podemos decir que el costo directo total en el tiempo de 23 es: P(23)=1150-{(23)13-
3)+7(13)+3(5)+9(5)+10(8)+3(8)]}
=1150-{299-[65+91+15+45+80+24] }
=1150-{(299-320)}
=1150+21]
=1150+21
=1171
de donde P(23)=1171 es decir 21 pesos de incremento.
pasamos a la siguiente iteración

Tercera Iteración
Para poder comenzar con el siguiente marcaje se borran todas las etiquetas anteriores que ya
teníamos en la red y es preciso calcular los nuevos valores de ii(i,j;1) y d(i,j;2):
La red nos queda de la siguiente manera:
(0,30)
(flujo,Capacidad máxima)

fig. 3.18
 Ejemplo 83

los d(i,j;1) y 1(i,j;2) nos quedarían de la siguiente manera:

7/(i,j;1)= 7/(i,j;2)=-
t(i,j) t(i)-t(j) D(i,j)-Ft(j)-t(i) d(i,j)A-t(j)-t(i)

t(s,l) 0-5=-5 5-5=0 2-5=-3

t(s,3) 0-15=-15 2-15=-13 1-15=-14
t(s,4) 0-10=-10 2-10=-8 1-10=-9
t(1,2) 5-12=-7 7-7=0 5-7=-2
t(1,4) 5-10=-5 5-5=0 2-5=-3
t(1,5) 5-20=-15 4-15=-11 2-15=-13
t(2,3) 12-15=-3 3-3=0 1-3=-2
t(2,5) 12-20=-8 10-8=2 6-8=-2
t(3,5) 15-20=-5 5-5=0 2-5=-3
t(3,t) 15-23=-8 9-8=1 5-8=-3
t(4,5) 10-20=-10 4-10=-6 1-10=-9
t(4,t) 10-23=-13 3-13=-10 1-13=-12
t(5,t) 20-23=-3 3-3=0 1-3=-2

tabla 3.5

Primer Marcaje de la tercera Iteración

como t(s) ya estaba marcado entonces todos los demás nodos de la red son todavía no marcados.
apartir de este nodo marcado buscamos todos los nodos j no marcados que tengan un d(ij:2) = O
para observar si forman un camino crítico desde t(s) hasta t(t), podemos observar que, en la tabla
3.5 los datos de 7/(i,j;2) no existen ceros por lo tanto no se forma un camino crítico y por eso el
proyecto se puede reducir en su tiempo de duración .
La red nos quedaria de la siguiente manera:
 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

(0,30)
(flujo,Capacidad máxima)

fig. 3.19

Segundo Marcaje de la tercera Iteración

Apartir del nodo marcado buscamos todos los t(j) no marcados siguiendo el camino donde los
(1,3;11)=0 para encontrar una cadena aumentante y los marcamos donde estos nodos quedarán
míarcados pero no explorados.
Observamos que existe un cero en la actividad A(s,1), A(1,2), A(1,4) A(2,3), A(3,5) y A(5,t)
od s en .1(i,j;1) por lo tanto marcamos a los nodos t(1), t(2), t(3), t(4), t(5) y t(t) de la siguiente
anera:
a t(1) lo marcamos de la siguiente manera [s,1,+,20].
a t(2) lo marcamos de la siguiente manera [1,4+,12].
lo marcamos de la siguiente manera [2,4+,5].
lo marcamos de la siguiente manera [1,4+,7].
t(5) lo marcamos de la siguiente manera [3,4+,3].
t(t) lo marcamos de la siguiente manera [5,4+,2].
a red nos quedaria de la siguiente manera:
 Ejemplo 85

(0,30)
(flujo,Capacidad máxima)

fig. 3.20
Por lo tanto, como hemos podido marcar a t(t) tenemos una cadena aumentante, y por lo tanto
podemos aumentar el flujo de la siguiente manera:

Se toma el nodo t y su antecesor en la cadena aumentante (5), como es positivo se le suma al

flujo del arco (5,t) 2 unidades y se realiza el mismo procedimiento con los nodos 3, 2, y 1. Cuando
ya llegemos al nodo s, hemos actualizado el flujo de la red quedandonos ésta de la siguiente manera.

(0,30)
(flujo,Capacidad máxima)

fig. 3.21
 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

vemos a marcar el segundo marcaje:

utilizando la red anterior y borrando las marcas buscamos una cadena aumentante y la capaci-
d incrementad de la cadena con el flujo ya actualizado tomando encuenta los d(i,j;k)=0. podemos
r que existen los mismos ceros que en la ocación anterior por lo tanto marcamos
a t(1) lo marcamos de la siguiente manera [s,1,-1-,181.
a t(2) lo marcamos de la siguiente manera [1,1,1-44
a t(3) lo marcamos de la siguiente manera [2,1,+,3].
a t(4) lo marcamos de la siguiente manera [1,4+,1.
a t(5) lo marcamos de la siguiente manera [3,1,-1-4].
como por la actividad A(5,t) ya se encuentra a su máxima capacidad entonces ya no se puede
pasar ningun flujo por lo tanto no pudimos marcas a t(t) y la red nos quedaría de la siguiente
manera:
(0,30)
(flujo,Capacidad máxima)

fig. 3.22
Como el último suceso no esta marcado entonces no existe cadena aumentante por lo tanto
pasamos al cambio en los tiempos de los sucesos, el cual se hace de la siguiente manera:
Se buscan los :
A1 =[A(i,j) donde i es marcado y j es no marcado, 2(i,j;k)<01
A2 --4A(i,j) donde j es marcado e i es no marcado, a(ij;k)>01
se calculan y se comparan llamandoseles:
E = rnink [-a(i,j;k)]
3,1. Ejemplo 87

62 = minA2[cki4)]
los cuales son:
2(3,t;2)=3
-d(4,t;1)=10 -7(4,t;2)=12
c/(5,t;2)=2

tomandose:

= rnin[81 , 62]
donde el mínimo es (5 = 2
Por lo tanto, el valor 2 se lo restamos a los tiempos de los nodos t(i) no marcados de la red que
os representa los tiempos, por lo tanto se le restara al nodo t(t) dos unidades.
(1,2)

fig. 3.23
Donde podemos ver que el tiempo que era de 23 semanas se redujo a 21.
Para encontrar el costo busquemos los d0,110 y los d(i,j;K) pordonde pasa el fiujoe los cuales
son:
d(s,1;1) = 5 1s,1;1) = 15
d(1,24) = 7 f(1,2;1) = 15

d(2,3;1) = 3 f(2,3;1) = 7
88 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

d(2,5;1) = 10 f(2,5;1) = 8
d(3,5;1) = 5 f(3,5;1) = 2
d(3,t;1) = 9 f(3,t;1) = 5
d(5,t;1) = 3 15,t;1) = 10
donde podemos decir que el costo directo total en el tiempo de 21 es: P(21)=1150-{(21)15-
[5(15)+7(15)+3(7)+10(8)+5(2)+ 9(5)+3(10)1}
=1150-{315-[75+105+21+80+10+45+30] }
=1150-{(315-366)}

= 11 50+51]

=1150+51

=1201

de donde P(21)=1201 es decir 51 pesos de incremento.

pasamos a la siguiente iteración:

Cuarta Iteración
Antes de iniciar el siguiente marcaje borramos las etiquetas anteriores y calcular los nuevos
valores de 7011) y 10,14
La red nos quedarían de la siguiente manera:
3.1. Ejemplo 89

(0,30)
(flujo,Capacidad máxima)

fig. 3.24
y los d(i,j;1) y los 1(i,j;2) nos quedan de la siguiente manera:

a(i,j;1)= d(i,j;2)=
t(i,j) t(i)-t(j) D(i,j)-Ft(j)-t(i) d(i,j)-takt(i)

t(s,1) 0-5=-5 5-5=0 2-5=-3

t(s,3) 0-15=-15 2-15=-13 1-15=-14
t(s,4) 0-10=-10 2-10=-8 1-10=-9
t(1,2) 5-12=-7 7-7=0 5-7=-2
«1,4) 5-10=-5 5-5=0 2-5=-3
t(1,5) 5-20=-15 4-15=-11 2-15=-13
t(2,3) 12-15=-3 3-3=0 1-3=-2
t(2,5) 12-20=-8 10-8=2 6-8=-2
t(3,5) 15-20=-5 5-5=0 2-5=-3
t(3,t) 15-21=-6 9-6=3 5-6=-1
t(4,5) 10-20=-10 4-10=-6 1-10=-9
t(4,t) 10-21=-11 3-11=-8 1-11=-10
t(5,t) 20-21=-1 3-1=2 1-1=0

tabla 3.6
pasamos al siguiente marcaje:
90 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

Primer Marcaje de la Cuarta Iteración

Como t(s) ya estaba marcado entonces todos los demás nodos de la red son todavía no marca-
dos. apartir de este nodo marcado buscamos todos los nodos j no marcados que tengan un d(i,j:2)
O para observar si forman un camino crítico desde t(s) hasta t(t), podemos observar que, en la
tabla 3.6 los datos de d(i,j;2) existe un cero en la actividad A(5,t) por lo tanto marcamos a t(t)
como [5,2,1-,oc] pero no se forma un camino crítico y por eso el proyecto se puede reducir en su
tiempo de duración .

La red nos quedaría de la siguiente manera:

(0,30)
(flujo,Capacidad máxima)

fig. 3.25

Segundo Marcaje de la Cuarta Iteración

Apartir del nodo marcado buscamos todos los t(j) no marcados siguiendo el camino donde los
-d- (i,j;k)=0
para encontrar una cadena aumentarte y los marcamos donde estos nodos quedarán
marcados pero no explorados.
Observamos que existe un cero por el primer conducto en las actividades A(8,1), A(1,2), A(1,4)
A(2,3), A(3,5) y por el segundo conducto en A(5,t) por lo tanto marcamos a los nodos t(1), t(2),
t(3), t(4), y t(5) y t(t) de la siguiente manera:

a t(1) lo marcamos de la siguiente manera [s,1,-F,18].

a t(2) lo marcamos de la siguiente manera [1,1,+,10].
a t(3) lo marcamos de la siguiente manera [2,1,+,3].
 Ejemplo 91

a t(4) lo marcamos de la siguiente manera [1,4+,1.

a t(5) lo marcamos de la siguiente manera [3,4+,11.
a t(t) lo marcamos de la siguiente manera [5,2,-F,1].
como marcamos a t(t) entonces la red nos queda de la siguiente manera:
(0,30)
(flujo,Capacidad máxima)

fig. 3.26
Por lo tanto tenemos una cadena aumentante, y por lo tanto podemos aumentar el flujo de la
siguiente manera:
Se toma el nodo t y su antecesor en la cadena aumentante (5), como es positivo se pasa ese
flujo por el segundo conducto y se pasa al siguiente que es el (3) se le suma 1 unidad al flujo del
arco (3,5) y se realiza el mismo procedimiento con los nodos 2, y 1.Cuando ya llegemos al nodo s,
hemos actualizado el flujo de la red quedandonos ésta de la siguiente manera.
92 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

(0,30)
(flujo,Capacidad máxima)

fig. 3.27
volvemos a marcar el segundo marcaje:
Utilizando la red anterior y borrando las marcas átenos las del primer marcaje buscamos una
cadena aumentante y la capacidad incremental de la cadena con el flujo ya actualizado tomando
encuenta los a( i,j;k)=0. podemos ver que existen los mismos ceros que en la ocación anterior por
lo tanto marcamos
a t(1) lo marcamos de la siguiente manera [s,1,+,15].
a t(2) lo marcamos de la siguiente manera [1,1,+,10].
a t(3) lo marcamos de la siguiente manera [2,1,+,3].
a t(4) lo marcamos de la siguiente manera [1,1,+,7].
como por la actividad A(3,5) ya se encuentra a su máxima capacidad entonces ya no se puede
pasar ningun flujo por lo tanto no pudimos marcar a t(t) y la red nos quedaría de la siguiente
manera:
92 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

(0,30)
(flujo,Capacidad máxima)

fig. 3.27
volvemos a marcar el segundo marcaje:
Utilizando la red anterior y borrando las marcas Menos las del primer marcaje buscamos una
cadena aumentante y la capacidad incremental de la cadena con el flujo ya actualizado tomando
encuenta los 71(i,j;k)=0. podemos ver que existen los mismos ceros que en la ocación anterior por
lo tanto marcamos
a t(1) lo marcamos de la siguiente manera [s,1,+,18].
a t(2) lo marcamos de la siguiente manera [1,1,+,10].
a t(3) lo marcamos de la siguiente manera [2,1,+,3].
a t(4) lo marcamos de la siguiente manera [1,1,+,7].
como por la actividad A(3,5) ya se encuentra a su máxima capacidad entonces ya no se puede
pasar ningun flujo por lo tanto no pudimos marcar a t(t) y la red nos quedaría de la siguiente
manera:
 93
plo

(0,30) (flujo,Capacidad máxima)

2, 1 ,+,2]
55

[5,2,-F, cc]
(0,10)

fig. 3.28
Como el último suceso no esta marcado entonces no existe cadena aumentante por lo tanto
asamos al cambio los tiempos de los sucesos, el cual se hace de la siguiente manera:

Se buscan los :
=[A.0,0 donde i es marcado y j es no marcado, 2(i,j;k)<01
A1
=[A(i,j) donde j es marcado e i es no marcado, W(i,j;k)>01
Ay

se calculan y se comparan llamandoseles:

¡
TriinAili,j;k)1

62 = minA,[7/ki,j;k)]
los cuales son:
7/(3,5;2)=3
31(3,t;2)=1

-7/(4,5;1)=-6 -2(4,5;2)=9

-2(4,1;1)=8 -71(4,t;2)=10

tornándose:
5 rnin[51, 62]
donde el mínimo es 5 = 1
Por lo tanto, el valor 1 se lo restamos a los tiempos de los
 93
plo

(0,30) (flujo,Capacidad máxima)

2,1,+,2]
55

[5,2,4-, Gol
(0,10)

fig. 3.28
Como el último suceso no esta marcado entonces no existe cadena aumentante por lo tanto
asamos al cambio los tiempos de los sucesos, el cual se hace de la siguiente manera:

Se buscan los :
Ar =[A(i,j) donde i es marcado y j es no marcado, cd(i,j;k)<01
donde j es marcado e i es no marcado, 7/(i,j;k)>I3]
A 2 r-{A(i,j)
se calculan y se comparan llamandoseles:
= TriinAJ-71(i,j;k)]
62 = minm[dki,j;k)]
los cuales son:
-7(3,5;2)=3
-d(3,t;2)=1

-7(4,5;1)=6 -d(4,5;2)=-9

-71(4,t;1)--.8 -7k4,t;2)=10

tomandose:
5= min[di,52]
donde el mínimo es 5 = 1
Por lo tanto, el valor 1 se lo restamos a los tiempos de los no&
 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

representa los tiempos, por lo tanto se le restara al nodo t(5) y a t(t) una unidad.
(1,2)

fig. 3.29
Donde podemos ver que el tiempo que era de 21 semanas se redujo a 20.
Para encontrar el costo busquemos los d(i,j;k) y los f(i,j;k).
0,1;1) = 5 f(s,1;1) = 16.
d(1,2;1) 7 f(s,1;1) = 16.
d(2,3;1) = 3 f(s,1;1) = 8.
d(2,5;1) = 10 f(s,1;1) = 8.
d(3,5;1) = 5 f(3,5;1) = 3.
d(3,t;1) = 9 f(34;1) = 5.
d(5,t;1) = 3 f(5,t;1) = 10.
d(5,t;2) = 1 f(s,1;1) = 1.
donde podemos decir que el costo directo total en el tiempo de 20 es:
P(20)=1150-1(20)1645(16)+7(16)+3(8)+10(8)+5(3)+9(5)+3(10)+1(1)1}
=1150-{320480+112+24+80+15+45+30+1] }
=1150-1(320-387)}
=1150+67]
 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

representa los tiempos, por lo tanto se le restara al nodo t(5) y a t(t) una unidad.
(1,2)
t(3)=15

t(t)=20

(1,3)

fig. 3.29
Donde podemos ver que el tiempo que era de 21 semanas se redujo a 20.
Para encontrar el costo busquemos los d(i,j;k) y los f(i,j;k).
d(s,1;1) = 5 f(s,1;1) = 16.
d(1,2;1) = 7 f(s,1;1) = 16.
d(2,3;1) = 3 f(s,1;1) = 8.
d(2,5;1) = 10 f(s,1;1) = 8.
d(3,5;1) = 5 f(3,5;1) = 3.
d(3,t;1) = 9 f(3,t;1) = 5.
d(5,t;1) = 3 f(5,t;1) = 10.
d(5,t;2) = 1 f(s,1;1) = 1.
donde podemos decir que el costo directo total en el tiempo de 20 es:
P(20)=11501(20)1645(16)+7(16)+3(8)+10(8)+5(3)+9(5)+3(10)+1(1)1}
=11501320480+112+24+80+15+45+30+1] }
=1150-{(320-387)}
=11504-671
 .1. Ejemplo 95

=1150+67
=1217
de donde P(20)=1217 es decir 67 pesos de incremento.
pasamos a la siguiente iteración:

Quinta Iteración
Antes de iniciar el siguiente marcaje borramos las etiquetas anteriores y calcular los nuevos
valores de i,j;1)
a( y d(i,j;2).
La red nos quedaría de la siguiente manera:

(0,30)
(flujo,Capacidad máxima)

fig. 3.30
y los a(i,j;1 ) y los ct(i,j;2) nos quedan de la siguiente manera:
 1. Ejemplo 95

=1150+67
=1217
de donde P(20)=1217 es decir 67 pesos de incremento.
pasamos a la siguiente iteración:

Quinta Iteración
Antes de iniciar el siguiente marcaje borramos las etiquetas anteriores y calcular los nuevos
valores de 7/(i,11) y d(i,j;2).
La red nos quedaría de la siguiente manera:

(0,30)
(flujo,Capacidad máxima)

fig. 3.30
y los a(i,j;i) y los d(i,j;2) nos quedan de la siguiente manera:
 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

cki,j;1)--.= 71(i,j;2)=
t(i,j) t(i)-t(j) D(i,j)-Ft(j)-t(i) d(i,j)-Ft(j)-t(i)

«5,1) 0-5=-5 5-5=0 2-5=-3

t(s,3) 0-15=-15 2-15=-13 1-15=-14
t(s,4) 0-10=-10 2-10=-8 1-10=-9
t(1,2) 5-12=-7 7-7=0 5-7=-2
t(1,4) 5-10=-5 5-5=0 2-5=-3
t(1,5) 5-19=-14 4-14=-10 2-14=-12
t(2,3) 12-15=-3 3-3=0 1-3=-2
t(2,5) 12-19=-7 10-7=3 6-7=-1
t(3,5) 15-19=-4 5-4=1 2-4=-2
t(3,t) 15-20=-5 9-5=4 5-5=0
t(4,5) 10-19=-9 4-9=-5 1-9=-8
t(4,t) 10-20=-10 3-10=-7 1-10=-9
t(5,t) 19-20=-1 3-1=2 1-1=0

tabla 3.7
pasamos al siguiente marcaje:

Primer Marcaje de la Quinta Iteración

como t(s) ya estaba marcado entonces todos los demás nodos de la red son todavía no marcados.
apartir de este nodo marcado buscamos todos los nodos j no marcados que tengan un -d-(i,j:2) = O
para observar si forman un camino crítico desde t(s) hasta t(t), podemos observar que, en la tabla
3.7 los datos de ii(i,j;2) existen dos ceros uno en la actividad A(3,t) y otro en la actividad A(5,t)
por lo tanto marcamos a t(t) como [3,2,-Foo] y [5,2+,00] pero no se forma un camino crítico y por
eso el proyecto se puede reducir en su tiempo de duración .
La red nos quedaria de la siguiente manera:
 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

71(i,j;1)=- 20,j;2)=
t(i,j) t(i)-t(j) D(i,j)-Et(j)-t(i) d(i,j)-Ft(j)-t(i)

t(s,1) 0-5=-5 5-5=0 2-5=-3

t(s,3) 0-15=-15 2-15=-13 1-15=-14
t(s,4) 0-10=-10 2-10=-8 1-10= 9
t(1,2) 5-12=-7 7-7=0 5-7=-2
t(1,4) 5-10=-5 5-5=0 2-5=-3
t(1,5) 5-19=-14 4-14=-10 2-14=-12
t(2,3) 12-15=-3 3-3=0 1-3=-2
t(2,5) 12-19=-7 10-7=3 6-7=-1
t(3,5) 15-19=-4 5-4=1 2-4=-2
t(3,t) 15-20=-5 9-5=4 5-5=0
t(4,5) 10-19=-9 4-9=-5 1-9=-8
t(4,t) 10-20=-10 3-10=-7 1-10=-9
t(5,t) 19-20=-1 3-1=2 1-1=0

tabla 3.7
pasamos al siguiente marcaje: is

Primer Marcaje de la Quinta Iteración

como t(s) ya estaba marcado entonces todos los demás nodos de la red son todavía no marcados.
apartir de este nodo marcado buscamos todos los nodos j no marcados que tengan un a(i,j:2) =
para observar si forman un camino crítico desde t(s) hasta t(t), podemos observar que, en la tabla
3.7 los datos de c/(i,12) existen dos ceros uno en la actividad A(3,t) y otro en la actividad A(5,t)
por lo tanto marcamos a t(t) como [3,2,-I-0o] y [5,21-,00] pero no se forma un camino crítico y por
eso el proyecto se puede reducir en su tiempo de duración .
La red nos quedaria de la siguiente manera:
 97

(0,30)
(flujo,Capacidad máxima)

[3,2,+, co]

fig. 3.31

Segundo Marcaje de la Quinta Iteración

Apartir del nodo marcado buscamos todos los t(j) no marcados siguiendo el camino donde los
(i,j;k)=0 para encontrar una cadena aumentante y los marcamos donde estos nodos quedaran
marcados pero no explorados.
Observamos que existe un cero por el primer conducto en las actividades A(s,1), A(1,2), A(1,4),
A(2,3) y por el segundo conducto en A(3,t) y A(5,t) por lo tanto marcamos a los nodos t(1), t(2),
t(3), t(4), y t(t) de la siguiente manera:

a t(1) lo marcamos de la siguiente manera [6,1,+,17].

a t(2) lo marcamos de la siguiente manera [1,1,+,9].
a t(3) lo marcamos de la siguiente manera [2,4+,2].
a t(4) lo marcamos de la siguiente manera [1,1,+,7].
a t(t) lo marcamos de la siguiente manera [3,2,+,2].
como marcamos a t(t) entonces la red nos queda:
 97

(0,30)
(flujo, Capacidad máxima)

fig. 3.31

Segundo Marcaje de la'Quinta Iteración

Apartir del nodo marcado buscamos todos los t(j) no marcados siguiendo el camino donde los
(i,j;k)=0 para encontrar una cadena aumentante y los marcamos donde estos nodos quedaran
marcados pero no explorados.
Observamos que existe un cero por el primer conducto en las actividades A(s,1), A(1,2), A(1,4),
A(2,3) y por el segundo conducto en A(3,t) y A(5,t) por lo tanto marcamos a los nodos t(1), t(2),
t(3), t(4), y t(t) de la siguiente manera:

a t(1) lo marcamos de la siguiente manera [8,1,+,17].

a t(2) lo marcamos de la siguiente manera [1,1,+,9].
a t(3) lo marcamos de la siguiente manera [2,1,+,2].
a t(4) lo marcamos de la siguiente manera [1,1,+,7].
a t(t) lo marcamos de la siguiente manera [3,2,+,2].
como marcamos a t(t) entonces la red nos queda:
 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

(flujo,Capacidad máxima)

fig. 3.32
tenemos una cadena aumentante, y por lo tanto podemos aumentar el flujo de la siguiente
manera:
Se toma el nodo t y su antecesor en la cadena aumentante (3), como es positivo se pasa el flujo
por el segundo conducto y se pasa al siguiente que es el (2) y se le suma 2 unidades al flujo del
arco (2,3) y se realiza el mismo procedimiento con los nodos 1 y s. Cuando ya llegemos al nodo s,
hemos actualizado el flujo de la red quedandonos ésta de la siguiente manera.

(flujo,Capacidad máxima)

fig. 3.33
 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

(flujo,Capacidad máxima)

[3,2,+, 2]

fig. 3.32
tenemos una cadena aumentante, y por lo tanto podemos aumentar el flujo de la siguiente

Se toma el nodo t y su antecesor en la cadena aumentante (3), como es positivo se pasa el flujo
por el segundo conducto y se pasa al siguiente que es el (2) y se le suma 2 unidades al flujo del
arco (2,3) y se realiza el mismo procedimiento con los nodos 1 y s. Cuando ya llegemos al nodo s,
hemos actualizado el flujo de la red quedandonos ésta de la siguiente manera.

(flujo,Capacidad máxima)

fig. 3.33
 jemplo 99

olvem os a marcar:

Utilizando la red anterior y borrando las marcas buscamos una cadena aumentante y la capaci-
d incrementa]. de la cadena con el flujo ya actualizado tomando encuenta los Tki,j;k)=0, podemos
que existen los mismos ceros que en la ocación anterior por lo tanto marcamos
a t(1) lo marcamos de la siguiente manera [s,1,+,18].
a t(2) lo marcamos de la siguiente manera [1,1,+,10].
a t(3) lo marcamos de la siguiente manera [2,1,+,3[.
a t(4) lo marcamos de la siguiente manera [1,1,+,7].
como por la actividad A(2,3) ya se encuentra a su máxima capacidad entonces ya no se puede
pasar ningún flujo, por lo tanto no pudimos marcar a t(t) y la red nos quedaría de la siguiente
manera:
(0,30)
(flujo,Capacidad máxima)

[3,1,+,00]

fig. 3.34
Como el último suceso no esta marcado entonces no existe cadena aumentante por lo tanto
pasamos al cambio de flujo en los tiempos de los sucesos, el cual se hace de la siguiente manera:
Se buscan los:
A1 =[A(i,j) donde i es marcado y j es no marcado, d(i.j;k)<01
A 2 =[A(i,j) donde j es marcado e i es no marcado,j(i,j;k)>01
se calculan y se comparan llamandoseles:
dl = rninA i [-dkijik)]
 99

vemos a marcar:

Utilizando la red anterior y borrando las marcas buscamos una cadena aumentante y la capad-
incremental de la cadena con el flujo ya actualizado tomando encuenta los a(i,j;k)=0, podemos
que existen los mismos ceros que en la ocación anterior por lo tanto marcamos
a t(1) lo marcamos de la siguiente manera [s,1,+,18].
a t(2) lo marcamos de la siguiente manera [1,1,+,10].
a t(3) lo marcamos de la siguiente manera [2,1,+,3].
a t(4) lo marcamos de la siguiente manera [1,1,+,7].
como por la actividad A(2,3) ya se encuentra a su máxima capacidad entonces ya no se puede
pasar ningún flujo, por lo tanto no pudimos marcar a t(t) y la red nos quedaría de la siguiente
manera:
(0,30)
(flujo,Capacidad máxima)

[3,1,+,00]

fig. 3.34
Como el último suceso no esta marcado entonces no existe cadena aumentante por lo tanto
pasamos al cambio de flujo en los tiempos de los sucesos, el cual se hace de la siguiente manera:
Se buscan los:
A1 =[A(i,j) donde i es marcado y j es no marcado, 1(i,j;k)<0]
A2 =[A(i,j) donde j es marcado e i es no marcado,1(i,1k)>0]

se calculan y se comparan llamandoseles:

= raro 41 [-d(ij;k)]
 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

2 minA,[d(i,j;k)]
los cuales son:

-70,3;1)=13 As,3;2).14

a( 1,54) =10 ;41,5;2)=12

d(2,3;2)=2

d(2,5;2)=1

14,5;1)=5 ic(4,5;2)=8

7/(4,t,1)=7 -d(4,t;2)=9

tomandose:

= min[61,52]
donde el mínimo es á = 1
Por lo tanto, el valor 1 se lo restamos a los tiempos de los nodos t(i) no marcados de la red que
os representa los tiempos, por lo tanto se le restara al nodo t(3), t(5) y a t(t) una unidad.
 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

52 = minA2 [d(i,j;k)]
los cuales son:

--d(s,3;1)=13 -d(s,3;2)=14

-d(1,54)=10 -2(1,5;2)=12

-0,3;2)=2

-0,5;2)=1

-d(4,5;1)=5 -d(4,5;2)=8

-2(4,t;1)=7 -d(4,t;2)=9

tomandose:

5 = min[82 , 82]
donde el mínimo es 8 = 1
Por lo tanto, el valor 1 se lo restamos a los tiempos de los nodos t(i) no marcados de la red que
os representa los tiempos, por lo tanto se le restara al nodo t(3), t(5) y a t(t) una unidad.

190
 101

fig. 3.35
Donde podemos ver que el tiempo que era de 20 semanas se redujo a 19.
Para encontrar el costo busquemos los d(i,j;k) y los f(i,j;k).
d(s,1;1) = 5 f(s,1;1) = 18.
d(1,2;1) = 7 f(1,2;1) = 18.
d(2,3;1) = 3 f(2,3;1) = 10.
d(2,5;1) = 10 f(2,5;1) = 8.
d(3,5;1) = 5 f(3,5;1) = 3.
d(3,t;1) = 9 f(3,t;1) = 5.
d(5,t;1) = 3 f(5,t;1) = 10.
d(3,t;2) = 5 f(3,t;1) = 2.
d(5,t;2) = 1 f(5,t;1) = 1.
donde podemos decir que el costo directo total en el tiempo de 19 es:
P(19)=1150-{(19)1845(18)+7(18)+3(10)+10(8)+5(3)-1-9(5)+3(10)+5(2)+1M}
=1150-{342490-1-126+30+80+15+45+30+10+1] }
=1150-{(342-427)}
=1150-[-85]
 101

fig. 3.35
Donde podemos ver que el tiempo que era de 20 semanas se redujo a 19.
Para encontrar el costo busquemos los d(i,j;k) y los f(i,j;k).
d(s,1;1) = 5 f(s,1;1) = 18.
d(1,2;1) = 7 11,2;1) = 18.
d(2,3;1) = 3 f(2,3;1) = 10.
d(2,5;1) = 10 f(2,5;1) = 8.
d(3,5;1) = 5 f(3,5;1) = 3.
d(3,t;1) = 9 f(3,t;1) = 5.
d(5,t;1) = 3 15,t;1) = 10.
d(3,t;2) = 5 f(3,t;1) = 2.
d(5,t;2) = 1 15,t;1) 1.
donde podemos decir que el costo directo total en el tiempo de 19 es:
P(19)=1150-{(19)18-[5(18)+7(18)+3(10)+10(8)+5(3)+9(5)+3(10)-1-5(2)+1(1)1}
=1150-{342-[90+126+30+80+15+45+30+10+1] }
=1150-{(342-427)}
=1150-[-85]
 Capítulo 3, Pulkerson

=1150+85
=1235
de donde P(19)=1235 es decir 85 pesos de inc
Pasamos a la siguiente iteración:

Sexta Ite
Antes de iniciar el siguiente marcaje borram
atores de d(i,j;1) y d(i,j;2).
La red nos quedaría de la siguiente manera:
(0,30)

fig. 3'
y los d(i,j;1) y los d(i,j;2) nos quedan de la sig
 Capítulo 3. -e Fulkerson

=1150+85
=1235
de donde P(19)=1235 es decir 85 pesos de inc

Pasamos a la siguiente iteración:

Sexta Ite
Antes de iniciar el siguiente marcaje borramosl
atores de a (il i ) y ii(i,12).
La red nos quedaría de la siguiente manera:
(0,30)

fig.
y los 2(i,11) y los d(i,12) nos quedan de la si
3.1. Ejemplo 103

2(i,j;1)= 7/(i12)=
t(i,j) t(i)-t(j) D(i,j)+t(j)-t(i) d(i,j)-Ft(j)-t(i)

t(s,1) 0-5=-5 5-5=0 2-5=-3

t(s,3) 0-14=-14 2-14=-12 1-14=-13
t(s,4) 0-10=-10 2-10=-8 1-10=-9
t(1,2) 5-12=-7 7-7=0 5-7=-2
t(1,4) 5-10=-5 5-5=0 2-5=-3
t(1,5) 5-18=-13 4-13=-9 2-13=-11
t(2,3) 12-14=-2 3-2=1 1-2=-1
t(2,5) 12-18=-6 10-6=4 6-6=0
t(3,5) 14-18=-4 5-4=1 2-4=-2
t(3,t) 14-19=-5 9-5=4 5-5=0
t(4,5) 10-18=-8 4-8=-4 1-8=-7
t(4,t) 10-19=-9 3-9=-6 1-9=-8
t(5,t) 18-19=-1 3-1=2 1-1=0
1
tabla 3.8
pasamos al siguiente marcaje:

Primer Marcaje de la Sexta Iteración

como t(s) ya estaba marcado entonces todos los demás nodos de la red son todavía no marcados.
apartir de este nodo marcado buscamos todos los nodos j no marcados que tengan un U(i,j:2) = O
para observar si forman un camino crítico desde t(s) hasta t(t), podemos observar que, en la tabla
3.8 los datos de d(i,j;2) existen ceros en las actividades A(2,5),A(3,t) y otro en la actividad A(5,t)
por lo tanto marcamos a t(5) cómo [2,2,-E0o] y a t(t) con dos marcas cómo [3,2+,00] y [5,2,+ oo]
pero no se forma un camino crítico y por eso el proyecto se puede reducir en su tiempo de duración.
La red nos quedaria de la siguiente manera:
 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

(0,30)
(finjo,Capacidad máxima)

[3,2,+, oo]

fig. 3.37

Segundo Marcaje de la Sexta Iteración

Desde el nodo marcado buscamos todos los t(j) no marcados siguiendo el camino donde los
c-/(i,j;k)=0 para encontrar una cadena aumentante y los marcamos donde estos nodos quedarán
marcados pero no explorados.
Observamos que existe un cero por el primer conducto en las actividades A(8,1), A(1,2), A(1,4)
y por el segundo conducto en A(2,5), A(3,t) y A(5,t) por lo tanto marcamos a los nodos t(1), t(2),
t(4), t(5) y t(t) de la siguiente manera:
a t(1) lo marcamos de la siguiente manera [s,1,+,15].
a t(2) lo marcamos de la siguiente manera [1,1,+,7].
a t(4) lo marcamos de la siguiente manera [1,1,+,7].
a t(5) lo marcamos de la siguiente manera [2,2,+,7].
a t(t) lo marcamos de la siguiente manera [5,2,4-,7].
como marcamos a t(t) entonces la red nos queda de la siguiente manera:
 105

(0,30)
(flujo,Capacidad máxima)

[3,2,+, 00]

fig. 3.38
tenemos una cadena aumentante, y por lo tanto podemos aumentar el flujo de la siguiente

Se toma el nodo t y su antecesor en la cadena aumentante (5), como es positivo se pasa el flujo
por el segundo conducto y se pasa al siguiente que es el (2) y se le suma 7 unidades al flujo de
ese arco. y se realiza el mismo procedimiento con los nodos 1 y s. Cuando ya llegemos al nodo s,
hemos actualizado el flujo de la red quedandonos está de la siguiente manera.
(0,30)
(flujo,Capacidad máxima)

[3,2,+, oo]

fig. 3.39
 O6 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

volvemos a marcar el segundo marcaje:

Utilizando la red anterior y borrando las marcas buscamos una cadena aumentante y la capaci-
dad incrementa) de la cadena con el flujo ya actualizado tomando encuenta los 1(i,j;k)=0. podemos
ver que existen los mismos ceros que en la ocación anterior por lo tanto marcamos
a t(1) lo marcamos de la siguiente manera [s,1,+,8].
como por la actividad A(1,2) ya se encuentra a su máxima capacidad entonces ya no se puede
pasar ningún flujo, por lo tanto no pudimos marcar a t(t) y la red nos quedaría de la siguiente
manera:
(0,30)
(flujo,Capacidad máxima)

[3,1,-E,00]

fig. 3.40
Como el último suceso no esta marcado entonces no existe cadena aumentante por lo tanto
pasamos al cambio de flujo en los tiempos de los sucesos, el cual se hace de la siguiente manera:
Se buscan los :
A1 ..[A(i,j) donde i es marcado y j es no marcado, a(i,j;k)<O]
A2 =[A(i,j) donde j es marcado e i es no marcado, d(i,j;k)>O]

se calculan y se comparan llamandoseles:

ól = minAi [-dkij;k)]
62 = min242[71(ii;k)]
los cuales son:
-d(s,34)=12 -d(s,3;2)=13
-d(1,2;2)=2
 Ejemplo 107

-2(1,5;1)=9 -2(1,5;2)=11
-2(4,5;1)=4 -2(4,5;2)=7
-2(4,1;1)=6 -d(4,t;2)=8
tomandose:

6= min [ 61; 62]

donde el mínimo es E = 2
Por lo tanto, el valor 2 se lo restamos a los tiempos de los nodos t(i) no marcados de la red que
nos representa los tiempos, por lo tanto se le restara al nodo t(2), t(3) t(5) y a t(t) 2 unidades y al
mismo tiempo encontrando la nueva ruta quedandonos de la siguiente manera:

fig. 3.41
Donde podemos ver que el tiempo que era de 19 semanas se redujo a 17.
Para encontrar el costo busquemos los d(i,j;k) y los f(i,j;k).
d(s,1;1) = 5 1s,14) = 25.
d(1,2;1) = 7 f(1,2;1) = 25.
d(2,3;1) = 3 f(2,3;1) = 10.
d(2,5;1) = 10 í(2,5;1) = 8.
d(3,5;1) = 5 f(3,5;1) = 3.
d(3,t;1) = 9 13,t;1) = 5.
 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

d(5,t;1) = 3 f(5,t;1) = 10.

d(2,5;2) = 6 f(2,5;1) =
d(3,t;2) = 5 13,t;1) = 2.
d(5,t;2) = 1 f(5,t;1) =
donde podemos decir que el costo directo total en el tiempo de 17 es:
P(17)=1150-{(17)25-[5(25)+7(25)+3(10)+10(8)+5(3)+9(5)+3(10)++6(7)+5(2)+1(8)1
=1150-{425-[125+175+30+80+15+45+30+42+10+8] }
=1150-{(425-560)}
=-1150+135]
=1150+135
=1285
de donde P(17)=1285 es decir 135 pesos de incremento.
Pasamos a la siguiente iteración:

Séptima Iteración
Antes de iniciar el siguiente marcaje borramos las etiquetas anteriores y calcular los nuevos
valores de d(i,j;1) y 1(i,j;2).
La red nos quedaría de la siguiente manera:
 109

(0,30)
(flujo,Capacidad máxima)

fig. 3.42
y los a(i,j;1) y los d(i,j;2) nos quedan de la siguiente manera:

2(i,j;1), 74412).
t(i,j) t(i)-t(j) D(i,j)-I-t(j)-t(i) d(i,j)+t(j)-t(i)

t(s,1) 0-5=-5 5-5=0 2-5=-3

t(s,3) 0-12=-12 2-12=-10 1-12=-11
t(s,4) 0-10=-10 2-10=-8 1-10=-9
«1,2) 5-10=-5 7-5=2 5-5=0
t(1,4) 5-10=-5 5-5=0 2-5=-3
«1,5) 5-16=-11 4-11=-7 2-11=-9
«2,3) 10-12=-2 3-2=1 1-2=-1
«2,5) 10-16=-6 10-6=4 6-6=0
t(3,5) 12-16=-4 5-4=1 2-4=-2
t(3,t) 12-17=-5 9-5=4 5-5=0
t(4,5) 10-16=-6 4-6=-2 1-6=-5
t(4,t) 10-17=-7 3-7=-4 1-7=-6
t(5,t) 16-17=-1 3-1=2 1-1=0

tabla 3.9
pasamos al siguiente marcaje:
 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

Primer Marcaje de la Séptima Iteración

como t(s) ya estaba marcado entonces todos los demás nodos de la red son todavía no marcados.
apartir de este nodo marcado buscamos todos los nodos j no marcados que tengan un a(i,j:2) =
para observar si forman un camino crítico desde t(s) hasta t(t), podemos observar que, en la tabla
3.9 los datos de c/(i,j;2) existen ceros en las actividades A(1,2), A(2,5),A(3,t) y otro en la actividad
A(5,t) por lo tanto marcamos a t(2) cómo [1,2,1-,o0], a t(5) cómo [2,2,1-0o] y a t(t) con dos marcas
cómo [3,2+,00] y [5,2,+ oo] pero no se forma un camino crítico y por eso el proyecto se puede
reducir en su tiempo de duración .

La red nos quedaría de la siguiente manera:

(0,30)
(flujo,Capacidad máxima)

[3,2,+, cc]

fig. 3.43

Segundo Marcaje de la Séptima Iteración

Desde el nodo marcado buscamos todos los t(j) no marcados siguiendo el camino donde los
ri(i,j;k)=0 para encontrar una cadena aumentante y los marcamos donde estos nodos quedarán
marcados pero no explorados.
Observamos que existe un cero por el primer conducto en las actividades A(s,1), A(1,4) y por el
segundo conducto en A(1,2), A(2,5), A(3,t) y A(5,t) por lo tanto marcamos a los nodos t(1), t(2),
t(4), t(5) y t(t) de la siguiente manera:
a t(1) lo marcamos de la siguiente manera [s,1,+,8].
a t(2) lo marcamos de la siguiente manera [1,2,+,8].
a t(4) lo marcamos de la siguiente manera [1,4+,1.
 Ej emplo 111

a t(5) lo marcamos de la siguiente manera [2,2,+,8].

t(t) lo marcamos de la siguiente manera [5,2,+,8].
como marcamos a t(t) tenemos la siguiente red:
!II
(0,30) !!.„
(flujo,Capacidad máxima)
s,1,+,81
55

(25,33) (0,10) (3,3)

[3,2,+, co]

o [-,-,->col
(25,25)

(0,7)
10 10

[2,2,4-,8] [5,2,+,8]
(10,10) (0,10). (0,10)
(0,30)
[1 rE,8]

v~la

fig. 3.44
tenemos una cadena aumentante, y por lo tanto podemos aumentar el flujo de la siguiente
manera:
Se toma el nodo t y su antecesor en la cadena aumentante (5), como es positivo se pasa el flujo
por el segundo conducto y se realiza el mismo procedimiento con los nodos 2,1 y s. Cuando ya
llegemos al nodo s, hemos actualizado el flujo de la red quedandonos ésta de la siguiente manera.
 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

(0,30)
(flujo,Capacidad máxima)
55
2
(33,33) (0,10) (3,3)
[3,2,+, oo]

(25,25) 10,10

(0,7) [5,2,-E,0o]
(10,10) (0,10) (0,10)
(0,30)

fig. 3.45
volvemos a marcar el segundo marcaje:

Utilizando la red anterior y borrando las marcas buscamos una cadena aumentante y la capaci-
dad incremental de la cadena con el flujo ya actualizado tomando encuenta, los a(i,j;k)=0. podemos
ver que existen los mismos ceros que en la ocación anterior pero como la actividad A(5,1) ya se
encuentra a su máxima capacidad entonces ya no se puede pasar ningun flujo, por lo tanto no
pudimos marcar a t(t) y la red nos quedaria de la siguiente manera:
(0,30)
(flujo,Capacidad máxima)
,5

(33,33) (0,10) (3,3)

[3,2,-k,00]

[5,2,+,00]
(10,10) (0,10) (0,10)
(0,30)

[1,2,-k,00

fig. 3.46
 Ejemplo 113

Como el último suceso no esta marcado entonces no existe cadena aumentante por lo tanto
pasamos al cambio en los tiempos de los sucesos, el cual se hace de la siguiente manera-
Se buscan los :
A1 =[A(i,j) donde i es marcado y j es no marcado, Tki,j;k)<O]
A2 =[A(i,j) donde j es marcado e i es no marcado, a(i,j;k)>O]

se calculan y se comparan llamandoseles:

= minA,[-d(i,j;k)]

6. 2 = minA2[71(i,j;k)]
los cuales son:
-d(s,1;2)=3
-d(s,3;1)=10 -a(s,3;2)=11
-a(s,4;1)=8 -d(s,4;2)=9
tomandose:
8= 82]
donde el mínimo es 6 = 3
Por lo tanto, el valor 3 se lo restamos a los tiempos de los nodos t(i) no marcados de la red que
nos representa los tiempos, por lo tanto se le restara al nodo t(1), t(2), t(3), t(4), t(5) y a t(t) 3
unidades quedandonos de la siguiente manera:
(1,2)
 14 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

Donde podemos ver que el tiempo que era de 17 semanas se redujo a 14.
Para encontrar el costo busquemos los d(i,j;k) y los f(ij;k).
d(s,1;1) = 5 f(s,1;1) = 33.
d(1,2;1) = 7 f(1,2;1) = 25.
d(2,3;1) = 3 f(2,3;1) = 10.
d(2,5;1) = 10 f(2,5;1) = 8.
d(3,5;1) = 5 f(3,5;1) = 3.
d(3,t;1) = 9 f(3,t;1) = 5.
d(5,t;1) = 3 f(5,t;1) = 10.
d(1,2;2) = 5 f(1,2;1) = 8.
d(2,5;2) -= 6 f(2,5;1) =
d(3,t;2) = 5 f(3,t;1) = 2.
d(5,t;2) = 1 f(5,t;1) =
donde podemos decir que el costo directo total en el tiempo de 14 es:
P(14)=1150-{(14)33-[5(33)+7(25)+3(10)+10(8)+5(3)+9(5)+3(10)+5(8)+6(15)+5(2)+1(16)11
=1150-{462-[165+175+30+80+15+45+30+40+90+10+16] }
=1150-{(462-696)}
=1150+234]
=1150+234
=1384
de donde P(14)=1384 es decir 234 pesos de incremento.
pasamos a la siguiente iteración:

Octava Iteración
Antes de iniciar el siguiente marcaje borramos las etiquetas anteriores y calcular los nuevos
valores de d(i,j;1) y 2/(i,12).
La red nos quedaría de la siguiente manera:
 Ejemplo 115

(0,30)
(flujo,Capacidad máxima)

(0,10)

fig. 3.48
y los a(i,j;1 ) y los d(i.j;2) nos quedan de la siguiente manera:

d(i,j;1)= ‘1(ii;2)=
t(i,j) t(i)-t(j) D(i,j)+t(j)-t(i) d(i,j)i-t(j)-t(i)

«s,1) 0-2=-2 5-2=3 2-2=0

t(s,3) 0-9=-9 2-9=-7 1-9=-8
t(5,4) 0-7=-7 2-7=-5 1-7=-6.
«1,2) 2-7=-5 7-5=2 5-5=0
«1,4) 2-7=-5 5-5=0 2-5=-3
«1,5) 2-13=-11 4-11=-7 2-11=-9
«2,3) 7-9=-2 3-2=1 1-2=-1
«2,5) 7-13=-6 10-6=4 6-6=0
t(3,5) 9-13=-4 5-4=1 2-4=-2
t(3,t) 9-14=-5 9-5=4 5-5=0
t(4,5) 7-13=-6 4-6=-2 1-6=-5
t(4,t) 7-14=-7 3-7=-4 1-7=-6
t(5,t) 13-14=-1 3-1=2 1-1=0

tabla 3.10
pasamos al siguiente marcaje:
116 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

Primer Marcaje de la Octava Iteración

como t(s) ya estaba marcado entonces todos los demás nodos de la red son todavía no marcados.
apartir de este nodo marcado buscamos todos los nodos j no marcados que tengan un 2/(i,12) =
para observar si forman un camino crítico desde t(s) hasta t(t), podemos observar que, en la tabla
3.10 los datos de 7/(i,12) existen ceros en las actividades A(s,1),A(1,2), A(2,5), A(3,t) y otro en la
actividad A(5,t) por lo tanto marcamos a t(1) como [8,2,-Hoo], t(2) cómo [1,2,+,00l, a t(5) cómo
[2,2,1-o0] y a t(t) con dos marcas cómo [3,2-1-,00] y oo] podemos ver que ya se forma un
camino crítico quedando la red de la siguiente manera:

(0,30)
(flujo,Capacidad máxima)

fig. 3.49
y por lo tanto ya terminamos ya que no se puede reducir más la duración del proyecto quedan-
donos una duración de 14 unidades y un costo de 1384 unidades quedando un camino de s a t.
por lo tanto la red de los tiempos nos queda de la siguiente manera:
 Ejemplo 117

(1,2)
t(3)=9

t(t)=14

(1,3)

fig. 3.50
y la figura de costos nos queda de la siguiente manera:
 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson

1235

1217

1201

1171

1158
1150
17 19 20 21 23 24 25 t
tab. 3.11

Por lo tanto al tener todos es tiempos entonces al escoger alguna opción se pueden
calcular las holguras.
 Ejemplo

Conclusiones
La idea de este trabajo es dar aconocer al lector una forma muy sencilla de como se puede
utilizar el método CPM en cualquier proyecto ya que este método es el más usado en la vida real
para minimizando el costo bajo un tiempo rasonable.
La experiencia obtenida al realizar este material es que se necesita conocer muy bien el desarrollo
de los algoritmos de Dijkstra y Ford Fulkerson para poder realizar el proyecto y esperando tambien
que en un futuro se desarrolle un software para el CPM por los estudiantes que se interesen en
continuar con este trabajo.
 Capítulo 3. Ejemplo con Aplicaciones del Algoritmo de Fulkerson
120
Appendix A

ALGORITMOS DE GRAFICAS
PARA EL PROBLEMA CPM

En este capítulo veremos algunos algoritmos por medio de los cuales solucionaremos el problema
duración - costo de algunos proyectos.

Los proyectos que utilizamos son aplicables en la vida real y pueden modelarse por medio de
una red formada por nodos y arcos
Como se explico en el primer capítulo. En el capitulo 2 vimos un ejemplo completo aplicando
el algoritmo de Dijkstra y en el 3 un problema aplicando el Ford Fulkerson, los cuales descrivimos
a continuación.

A.1 Algoritmo de Dijkstra

Tenemos una red la cual tiene unas marcas que indican la duración de cada actividad.
Se pretende encontrar el la duración máximo entre s y t de la red:

121
 Appendix A. ALGORITMOS DE GRÁFICAS PARA EL PROBLEMA CPM

A continuación precentaremos el algoritmo utilizando la red anterior:

Comenzamos con el primer paso el cual es:
Inicializacion de etiqueten.
Duración máxima (s) = 0 V s E N
Anterior a la ruta máxima de s=sVs E N
Todas los nodos tienen una etiqueta de revisión del algoritmo
Sea C el conjunto de nodos que están marcados de manera temporal junto con la distancia
máxima que hay desde la raíz hasta el los cuales estan ordenados de mayor a menor. Inicialmente
en C solo está la raiz.
Se saca un elemento de C y se guarda en P.
Se marca el nodo p como definitivo, despues se concidera cada nodo i E I' + (p) y se revisa.

Si no lo a tocado el algoritmo

- Marcar i temporalmente

- Hacer duración máxima i = duración máximo (p) duración(i,j)

- Anterior ruta máxima (i) = p

- Meter i en C.

Si está marcado como temporal y si Duración máxima (i) > Duración máxima p Du-
ración(i,j).
A.2. Algoritmo de Ford Fulkerson 123

- Hacer Duración máxima (i) = Duración máxima (p) Duración(p,j)

- Anterior ruta máxima (i) = p

- Actualizar en C la duración Máxima de i.

5. Ir a 3, mientras Cy

A.2 Algoritmo de Ford Fulkerson

Se tiene la siguiente red donde precentamos los arcos con los costos máximo y mínimos

05

Donde:
f(i,j) = fu = el flujo a trabes del arco A(i,j)
f(i = flujo que llega al nodo i
q(i,j) = Capacidad máxima del flujo de A(i,j)
P+ conjunto de todos los nodos sucesores de i

= conjunto de todos los nodos antecesores de i

Se desea encontrar el flujo máximo entre un nodo fuente y un nodo destinode una red lt=[X,
A, q] donde X reprecenta el conjunto de nodos, A reprecenta el conjunto de caminos (arcos) por
donde es posible transportar el flujo
Descripcion
1.- Iniciamos con cualquier flujo factible f.
124 Appendix A. ALGORITMOS DE GRÁFICAS PARA EL PROBLEMA CPM

2.- Se busca una cadena aumentante, para ésto se hace lo siguiente.

Etiquetamos el nodo s con [s,00].

Elegir un nodo etiquetado para examinarlo; suponiendo que j es el nodo elegido y que sus
etiquetas son [+(k), f(j)].
A todo nodo i E r ± (i,j) que no tenga etiqueta y tal que fu < qu se le asigna las etiquetas
[+j,f(i)] donde = min[f(i), - fu]

A todo i E l - (j) que no tenga etiqueta y tal que fu > O se le asigna las etiquetas [-j,f(i)]
donde f(i) =min{i), fu}
luego el nodo j ha sido examinado.
c) Repetir el paso 2 hasta que :
El nodo destino t recibe etiqueta. Ir a paso 3.
Todos los nodos etiquetados han sido examinados, si el nodo destino t no tiene etiqueta el
flujo factible f es el máximo y termina el algoritmo.
3.- Actualizar el flujo.

sea x=t

Revisar la etiqueta de x

i. Si es de la forma [+z,f(z)] hacer:

fzx = f - f(x)•

c) Si x = s borrar todas las etiquetas y regresar al paso 2 si z s hacer x=z y regresar al paso
3.b)

o 'TE 11
t 191 -
CIENCI1 AS
/ 1 IIETURALU

NABA
Bibliografía
Gestion Deusto. Aplicaciones Practicas del PERT y CPM. Quinta edición
Taha. Investigacion de Operaciones. Edit. Alfaomega
James M. Ántill. Ronald W. Woodheand. Método de la Ruta Crítica. Edit. Limusa
Helbert Moskowitz y Gordon P. Wright. Investigacion de Operaciones y sus Aplicaciones a la
Construccin.
Graciela Bueno de Araujo. Introducción a la Programación Lineal yal Analisas de Sensibilidad
Edit. Trillas
Edelmira Rordiguez Alcantar. Los problemas de: Arbol de mínima expansiií en gráficas y ruta
mínima en digráficas
[7] Irene Rodriguez Castillo. Una Implementación Computacional del Algoritmo de Ford-Fulkerson
y sus Generalizaciónes