¿Qué es la
Investigación Operativa ?
Actualmente
la
Investigación Operativa incluye gran cantidad de ramas como la Programación Lineal ,
Programación No Lineal, Programación Dinámica, Simulación, Teoría de Colas,
Teoría de Inventarios, Teoría de Grafos, etc.
Aunque su
nacimiento como ciencia se establece durante la Segunda Guerra
Mundial y debe su nombre a las operaciones militares, los verdaderos orígenes de la Investigación Operativa se remontan mucho más atrás en el tiempo, hasta el siglo
XVII. Sin embargo su auge es debido, en su mayor parte, al gran desarrollo de
la informática, gracias a la cual es posible resolver problemas en la práctica
y obtener soluciones que de otra forma conllevarían un enorme tiempo de
cálculo. Debido al gran éxito de la Investigación Operativa
en el campo militar, esta se extendió a otros campos tales como la industria,
física, informática, economía, estadística y probabilidad, ecología, educación,
servicio social, siendo hoy en día utilizada prácticamente en todas las áreas.
A lo largo de la historia es frecuente
encontrarse con la colaboración entre científicos y militares con el fin de
dictaminar la decisión óptima en la batalla. Es por esto que muchos expertos
consideran el inicio de la Investigación Operativa en el siglo III A.C.,
durante la II Guerra
Púnica, con el análisis y solución que Arquímedes propuso para la defensa de la
ciudad de Siracusa, sitiada por los romanos. Entre sus inventos se encontraban
la catapulta, y un sistema de espejos con el que incendiaba las embarcaciones
enemigas al enfocarlas con los rayos del sol.
El objetivo y finalidad de la investigación operacional (conocida también como teoría de la toma de decisiones o programación
matemática) es encontrar la solución óptima para un determinado problema
(militar, económico, de infraestructura, logístico, etc.)
Está constituida por un
acercamiento científico a la solución de problemas complejos, tiene
características intrínsecamente multidisciplinares y utiliza un conjunto
diversificado de instrumentos, prevalentemente matemáticos, para la
modelización, la optimización y el control de sistemas estructurales.
En el caso particular de
problemas de carácter económico, la función objetivo puede ser obtener el
máximo rendimiento o el menor costo.
La investigación operacional
tiene un rol importante en los problemas de toma de decisiones porque permite
tomar las mejores decisiones para alcanzar un determinado objetivo respetando
los vínculos externos, no controlables por quien debe tomar la decisión. 786
Tras la Segunda Guerra
Mundial, la organización de los recursos de Estados Unidos (EEUU) (energía,
armamentos, y todo tipo de suministros) se estimó oportuno realizarla mediante
modelos de optimización, resueltos mediante la programación lineal.
Anteriormente ya se habían planteado éstos
problemas en una disciplina conocida como Investigación de Empresas o Análisis
de Empresas, que no disponían de métodos tan efectivos como los desarrollados
durante la Segunda
Guerra Mundial (por ejemplo el Método Simplex). Las
aplicaciones no bélicas de la Investigación Operativa
se extienden tanto como se imagine, con problemas que van desde la
alimentación, ganadería, distribución de campos de cultivo en agricultura,
transporte de mercancías, localización, distribución de personal, problemas de
redes, colas, grafos, etc.
Casos reales de uso
de Investigación Operativa y los
beneficios reportados.
La siguiente tabla muestra algunos casos
reales de organizaciones que han hecho uso de la Investigación Operativa
y las ganancias y/o ahorros conseguidos a raíz de ello.
Organización
|
Aplicación
|
Año
|
Ahorros anuales
|
The
Netherlands Rijkswaterstaat
|
Desarrollo
de la política nacional de administración del agua, incluyendo mezcla de
nuevas instalaciones, procedimientos de operaciones y costeo
|
1985
|
$15
millones
|
Monsanto
Corp.
|
Optimización
de las operaciones de producción para cumplir metas con un costo mínimo
|
1985
|
$2
millones
|
Weyerhauser
Co.
|
Optimización
del corte de árboles en productos de madera para maximizar su producción
|
1986
|
$15
millones
|
Electrobas/CEPAL
Brasil
|
Asignación
óptima de recursos hidráulicos y térmicos en el sistema nacional de
generación de energía
|
1986
|
$43
millones
|
United
Airlines
|
Programación
de turnos de trabajo en oficinas de reservaciones y aeropuertos para cumplir
con las necesidades del cliente a un costo mínimo
|
1986
|
$6
millones
|
Citgo
Petroleum Corp.
|
Optimización
de las operaciones de refinación y de la oferta, distribución y
comercialización de productos
|
1987
|
$70
millones
|
SANTOS,
Ltd., Australia
|
Optimización
de inversiones de capital para producir gas natural durante 25 años
|
1987
|
$3
millones
|
Electric
Power Research Institute
|
Administración
de inventarios de petróleo y carbón para el servicio eléctrico con el fin de
equilibrar los costos de inventario y los riesgos de faltantes
|
1989
|
$59
millones
|
San
Francisco Police Department
|
Optimización
de la programación y asignación de oficiales de patrulla con un sistema
informatizado
|
1989
|
$11
millones
|
Texaco
Inc.
|
Optimización
de la mezcla de ingredientes disponibles para que los productos de gasolina
cumplieran con los requerimientos de ventas y calidad
|
1989
|
$30
millones
|
IBM
|
Integración
de una red nacional de inventario de refacciones para mejorar el apoyo al
servicio
|
1990
|
$20
millones + $250 millones en menor inventario
|
Rapidez
en la coordinación de aviones, tripulación, carga y pasajeros para manejar la
evacuación por aire en el proyecto "Tormenta del Desierto" en el
Medio Oriente
|
1992
|
Victoria
|
|
American
Airlines
|
Diseño
de un sistema de estructura de precios, sobreventas y coordinación de vuelos
para mejorar las utilidades
|
1992
|
$500
millones más de ingresos
|
Yellow
Freight System, Inc.
|
Optimización
del diseño de una red nacional de transporte y la programación de rutas de
envío
|
1992
|
$17.3
millones
|
New
Haven Health Dept.
|
Diseño
de un programa efectivo de cambio de agujas para combatir el contagio del
SIDA
|
1993
|
33%
menos contagios
|
AT&T
|
Desarrollo
de un sistema basado en PC para guiar a los clientes del negocio en el diseño
del centro de llamadas
|
1993
|
$750
millones
|
Delta
Airlines
|
Maximización
de ganancias a partir de la asignación de los tipos de aviones en 2.500 vuelos
nacionales
|
1994
|
$100
millones
|
Digital
Equipment Corp.
|
Reestructuración
de toda la cadena de proveedores entre proveedores, plantas, centros de
distribución, sitios potenciales y áreas de mercado
|
1995
|
$800
millones
|
China
|
Selección
y programación óptima de proyectos masivos para cumplir con las necesidades
futuras de energía del país
|
1995
|
$425
millones
|
Cuerpo
de defensa de Sudáfrica
|
Rediseño
óptimo del tamaño y forma del cuerpo de defensa y su sistema de armas
|
1997
|
$1.100
millones
|
Procter
and Gamble
|
Rediseño
del sistema de producción y distribución norteamericano para reducir costos y
mejorar la rapidez de llegada al mercado
|
1997
|
$200
millones
|
Taco
Bell
|
Programación
óptima de empleados para proporcionar el servicio a clientes deseado con un
costo mínimo
|
1998
|
$13
millones
|
Hewlett-Packard
|
Rediseño
de tamaño y localización de inventarios de seguridad en la línea de
producción de impresoras para cumplir metas de producción
|
1998
|
$280
millones de ingreso adicional
|
Teoría
sobre el modelado de problemas
Para poder solucionar un problema mediante
un algoritmo primero se debe extraer toda la información que nos aporta el
enunciado y preparar el problema para dicho algoritmo.
Los pasos para modelar un problema son los
siguientes:
- Paso 1: Se determinan las variables de
decisión y se expresan algebraicamente.
- X1,..., Xn
- Paso 2: Se determinan las restricciones y
se expresan como ecuaciones o inecuaciones de las variables de decisión:
- A11·X1 + A12·X2 + ... + A1n·Xn ≥, ≤, ó = b1
- A21·X1 + A22·X2 + ... + A 2n·Xn ≥, ≤, ó = b2
- ...
- Am1·X1 + Am2·X2 + ... + Amn·Xn ≥, ≤, ó = bm
- Paso 3: Se expresan todas las condiciones
implícitamente establecidas por la naturaleza de las variables: que no
puedan ser negativas, que sean enteras, que solo puedan tomar determinados
valores, ...
- X1,..., Xn ≥ 0
- X1,..., Xn son números enteros, o son booleanos,...
- Paso 4: Se determina la función objetivo.
- Maximizar o minimizar Z = C1·X1 + C2·X2 + ... + Cn·Xn
A modo de ejemplo vamos a ver como se modelan
algunos problemas típicos:
- Problema de la dieta
- Problema de transporte de tropas
- Problema de transporte de mercancías
- Problema de los árboles frutales
- Problema de asignación de personal
- Problema del camino mínimo
- Problema de localización
- Problema de inversión en bolsa
Problema
de la dieta
El problema de la dieta fue uno de los
primeros sobre optimización. Se trataba hallar la manera más económica de
alimentar al ejercito pero asegurando al mismo tiempo unos determinados niveles
nutricionales.
Este tipo de problema se puede plantear en
distintas formas tales como minimizar los gastos de la compra, dieta para el
ganado, una dieta adelgazante que cumpla unos determinados niveles de calorías,
proteínas, hidratos de carbono, ....
Ejemplo
Nos proponemos alimentar el ganado
de una granja con una dieta que sea la más económica posible. Dicha dieta debe
contener cuatro tipos de nutrientes que llamamos A, B, C, y D. Estos
componentes se encuentran en dos tipos de piensos(productos) M y N. La
cantidad, en gramos, de cada componente por kilo de estos piensos(productos)
viene dada en la tabla siguiente:
A
|
B
|
C
|
D
|
|
M
|
100
|
-
|
100
|
200
|
N
|
-
|
100
|
200
|
100
|
La dieta diaria de un animal debe
estar compuesta por al menos 0.4Kg del componente A, 0.6Kg del componente B,
2Kg del componente C, y 1.7Kg del componente D. El compuesto M cuesta 0.2€/Kg y
el compuesto N 0.08€/Kg. ¿Qué cantidades de piensos M y N deben adquirirse para
que el gasto de comida sea el menor posible?
Se determinan las variables de decisión y
se representan algebraicamente. En este caso:
- X1: cantidad de pienso M en Kg
- X2: cantidad de pienso N en Kg
Se determinan las restricciones y se
expresan como ecuaciones o inecuaciones de las variables de decisión. Dichas
restricciones se deducen de la composición requerida para la dieta diaria (en
Kg):
- En el componente A: 0.1·X1 + 0·X2 ≥ 0.4
- En el componente B: 0·X1 + 0.1·X2 ≥ 0.6
- En el componente C: 0.1·X1 + 0.2·X2 ≥ 2
- En el componente D: 0.2·X1 + 0.1·X2 ≥ 1.7
Se expresan todas las condiciones
implícitamente establecidas por la naturaleza de las variables: que no puedan
ser negativas, que sean enteras, que solo puedan tomar determinados valores,
... En este caso, la única restricción es que las cantidades de pienso que
forman la dieta no pueden ser negativas:
- X1 ≥ 0
- X2 ≥ 0
Se determina la función objetivo:
- Minimizar Z = 0.2·X1 + 0.08·X2
Transporte
de tropas
Un destacamento militar formado
por 50 soldados ingenieros, 36 zapadores, 22 de las fuerzas especiales, y 120
soldados de infantería como tropa de apoyo, ha de transportarse hasta una
posición estratégica importante. En el parque de la base se dispone de 4 tipos
de vehículos A, B, C, y D, acondicionados para transporte de tropas. El número
de personas que cada vehículo puede transportar es 10, 7, 6, y 9, de la forma
en que se detalla en la siguiente tabla:
Ingenieros
|
Zapadores
|
Fuerzas especiales
|
Infantería
|
|
A
|
3
|
2
|
1
|
4
|
B
|
1
|
1
|
2
|
3
|
C
|
2
|
1
|
2
|
1
|
D
|
3
|
2
|
3
|
1
|
El combustible necesario para que
cada vehículo llegue hasta el punto de destino se estima en 160, 80, 40, y 120
litros respectivamente. Si queremos ahorrar combustible, ¿cuántos vehículos de
cada tipo habrá que utilizar para que el consumo sea el mínimo posible?
Se determinan las variables de decisión y
se representan algebraicamente. En este caso:
- Xi: número de vehículos de cada tipo que se usen
- X1: número de vehículos de tipo A
- X2: número de vehículos de tipo B
- X3: número de vehículos de tipo C
- X4: número de vehículos de tipo D
Se determinan las restricciones y se
expresan como ecuaciones o inecuaciones de las variables de decisión. Dichas
restricciones se deducen de los soldados que deben ser transportados:
- Ingenieros: 3·X1 + X2 + 2·X3 + 3·X4 ≥ 50
- Zapadores: 2·X1 + X2 + X3 + 2·X4 ≥ 36
- Fuerzas especiales: X1 + 2·X2 + 2·X3 + 3·X4 ≥ 22
- Infantería: 4·X1 + 3·X2 + X3 + X4 ≥ 120
Se expresan todas las condiciones
implícitamente establecidas por la naturaleza de las variables: que no puedan
ser negativas, que sean enteras, que solo puedan tomar determinados valores,
... En este caso las restricciones son que la cantidad de vehículos no puede
ser negativa y debe ser además un número entero:
- Xi ≥ 0
- Xi son enteros
Se determina la función objetivo:
- Minimizar Z = 160·X1 + 80·X2 + 40·X3 + 120·X4
Transporte
de mercancías
Para este tipo de problemas, aunque pueden
ser resueltos por el método del Simplex, existe un método específico de más
fácil resolución: el método del transporte o método simplificado del Simplex
para problemas de transporte. Este método ahorra bastante tiempo y cálculos
frente al método del Simplex tradicional.
Sin embargo el problema se modela de la
misma forma.
Ejemplo
Un fabricante desea despachar
varias unidades de un artículo a tres tiendas T1, T2, y T3. Dispone de dos
almacenes desde donde realizar el envío, A y B. En el primero dispone de 5
unidades de este artículo y en el segundo 10. La demanda de cada tienda es de
8, 5, y 2 unidades respectivamente. Los gastos de transporte de un artículo
desde cada almacén a cada tienda están expresados en la tabla:
T1
|
T2
|
T3
|
|
A
|
1
|
2
|
4
|
B
|
3
|
2
|
1
|
¿Cómo ha de realizar el transporte
para que sea lo más económico posible?
Se determinan las variables de decisión,
en este caso:
- Xi: número de unidades transportadas desde cada
almacén a cada tienda
- X1: número de unidades transportadas desde el
almacén A hasta la tienda T1
- X2: número de unidades transportadas desde el
almacén A hasta la tienda T2
- X3: número de unidades transportadas desde el
almacén A hasta la tienda T3
- X4: número de unidades transportadas desde el
almacén B hasta la tienda T1
- X5: número de unidades transportadas desde el
almacén B hasta la tienda T2
- X6: número de unidades transportadas desde el
almacén B hasta la tienda T3
Se determinan las restricciones y se
expresan como ecuaciones o inecuaciones de las variables de decisión. Dichas
restricciones se deducen de la disponibilidad de unidades que hay en cada
almacén así como de la demanda de cada tienda:
- Disponibilidad en el almacén A: X1 + X2 + X3 = 5
- Disponibilidad en el almacén B: X4 + X5 + X6 = 10
- Demanda de la tienda T1: X1 + X4 = 8
- Demanda de la tienda T2: X2 + X5 = 5
- Demanda de la tienda T3: X3 + X6 = 2
Se expresan todas las condiciones
implícitamente establecidas por la naturaleza de las variables: que no puedan
ser negativas, que sean enteras, que solo puedan tomar determinados valores,
... En este caso las restricciones son que la cantidad de unidades no puede ser
negativa y debe ser además un número entero:
- Xi ≥ 0
- Xi son enteros
Se determina la función objetivo:
- Minimizar Z = X1 + 2·X2 + 4·X3 + 3·X4 + 2·X5 + X6
Árboles
frutales
Un agricultor tiene una parcela de
640m² para dedicarla al cultivo de árboles frutales: naranjos, perales,
manzanos y limoneros. Se pregunta de qué forma debería repartir la superficie
de la parcela entre las variedades para conseguir el máximo beneficio sabiendo
que:
- cada naranjo necesita un mínimo de 16m²,
cada peral 4m², cada manzano 8m² y cada limonero 12m².
- dispone de 900 horas de trabajo al año,
necesitando cada naranjo 30 horas al año, cada peral 5 horas, cada manzano
10 horas, y cada limonero 20 horas.
- a causa de la sequía, el agricultor tiene
restricciones para el riego: le han asignado 200m³ de agua anuales. Las
necesidades anuales son de 2m³ por cada naranjo, 1m³ por cada peral, 1m³
por cada manzano, y 2m³ por cada limonero.
- los beneficios unitarios son de 50, 25,
20, y 30 € por cada naranjo, peral, manzano y limonero respectivamente.
Se determinan las variables de decisión y
se representan algebraicamente. En este caso:
- X1: número de naranjos
- X2: número de perales
- X3: número de manzanos
- X4: número de limoneros
Se determinan las restricciones y se
expresan como ecuaciones o inecuaciones de las variables de decisión. Dichas
restricciones se deducen de las necesidades de cada árbol de terreno, horas de
trabajo anuales, y necesidades de riego:
- Necesidades de terreno: 16·X1 + 4·X2 + 8·X3 + 12·X4 ≤ 640
- Necesidades de horas anuales: 30·X1 + 5·X2 + 10·X3 + 20·X4 ≤ 900
- Necesidades de riego: 2·X1 + X2 + X3 + 2·X4 ≤ 200
Se expresan todas las condiciones
implícitamente establecidas por la naturaleza de las variables: que no puedan
ser negativas, que sean enteras, que solo puedan tomar determinados valores,
... En este caso las restricciones son que el número de árboles no puede ser
negativo y además debe ser un número entero:
- Xi ≥ 0
- Xi son enteros
Se determina la función objetivo:
- Maximizar Z = 50·X1 + 25·X2 + 20·X3 + 30·X4
Asignación
de personal
Una empresa ha preseleccionado 5
candidatos para ocupar 4 puestos de trabajo en dicha empresa. Los puestos de
trabajo consisten en manejar 4 máquinas diferentes (un trabajador para cada
máquina). La empresa puso a prueba a los 5 trabajadores en las 4 máquinas,
realizando el mismo trabajo todos ellos en cada una de las máquinas, obteniendo
los siguientes tiempos:
Máquina1
|
Máquina2
|
Máquina3
|
Máquina4
|
|
Candidato1
|
10
|
6
|
6
|
5
|
Candidato2
|
8
|
7
|
6
|
6
|
Candidato3
|
8
|
6
|
5
|
6
|
Candidato4
|
9
|
7
|
7
|
6
|
Candidato5
|
8
|
7
|
6
|
5
|
Determinar qué candidatos debe
seleccionar la empresa y a qué máquinas debe asignarlos.
Se determinan las variables de decisión,
en este caso:
- Xij: acción de que el trabajador i es asignado a la
máquina j (0 indica que el trabajador no ha sido asignado y 1 que sí ha
sido asignado)
Se determinan las restricciones y se
expresan como ecuaciones o inecuaciones de las variables de decisión. Dichas
restricciones son que cada trabajador debe ser asignado a una sola máquina y no
debe quedar ninguna máquina sin un trabajador asignado a ella:
- Cada trabajador debe estar asignado a una
sola máquina o a ninguna si no se selecciona:
- X11 + X12 + X13 + X14 ≤ 1
- X21 + X22 + X23 + X24 ≤ 1
- X31 + X32 + X33 + X34 ≤ 1
- X41 + X42 + X43 + X44 ≤ 1
- X51 + X52 + X53 + X54 ≤ 1
- En cada máquina debe haber un trabajador:
- X11 + X21 + X31 + X41 + X51 = 1
- X12 + X22 + X32 + X42 + X52 = 1
- X13 + X23 + X33 + X43 + X53 = 1
- X14 + X24 + X34 + X44 + X54 = 1
Se expresan todas las condiciones
implícitamente establecidas por la naturaleza de las variables: que no puedan
ser negativas, que sean enteras, que solo puedan tomar determinados valores,
... En este caso las restricciones son que las asignaciones de trabajadores a
máquinas no puede ser negativa y debe ser además una variable booleana (0 no se
asigna, 1 se asigna):
- Xij ≥ 0
- Xij es booleano
Se determina la función objetivo:
- Minimizar Z = 10·X11 + 8·X21 + 8·X31 + 9·X41 + 8·X51 + 6·X12 + 7·X22 + 6·X32 + 7·X42 + 7·X52 + 6·X13 + 6·X23 + 5·X33 + 7·X43 + 6·X53 + 5·X14 + 6·X24 + 6·X34 + 6·X44 + 5·X54
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Teoría de Grafos
Descargar apunte aquí
Método de la ruta crítica
El método
de la ruta crítica o del
camino crítico también conocido por sus siglas en inglés CPM (Critical Path
Method), fue desarrollado en 1957 en los Estados Unidos de América, por un
centro de investigación de operaciones para las firmas Dupont y Remington Rand,
buscando el control y la optimización de los costos mediante la planeación y
programación adecuadas de las actividades componentes del proyecto. Una ruta
crítica es la secuencia de las actividades con la mayor duración entre ellos,
determinando el tiempo más corto en el que es posible completar el proyecto. La
duración de la ruta crítica determina la duración del proyecto entero.
Cualquier retraso en una tarea que conforma el
camino critico, afectara la fecha de término o finalizacion planeada del proyecto.
Se dice que no hay holgura en la ruta crítica.
Ejemplo
Paso por paso,
la manera de crear un diagrama de flechas y de hallar el camino crítico, explicado tan detalladamente que hasta
el más perdido lo pueda entender (y de paso que se quede sin excusa).
Utilizamos un ejercicio sencillo:
Utilizamos un ejercicio sencillo:
Lo primero que tenemos que tener en cuenta es que las tareas son las aristas (flechas) del grafo, NO SON los nodos. Los nodos indican el inicio y el fin de una tarea, y siempre debe haber un nodo de inicio y uno de fin en el grafo.
Este es nuestro nodo de inicio. Todo nodo está dividido en 3 sectores:
* El inferior, donde va el número de nodo. Se utiliza para mantener un orden, más allá de eso no aporta ningún dato importante.
* Superior izquierdo, donde se encuentra el tiempo temprano.
* Superior derecho, donde se encuentra el tiempo tardío.
En este momento ambos tiempos se encuentran en cero, puesto que el inicio es cuando aún no se ha ejecutado ninguna tarea.
Ya que las tareas A y B no poseen ninguna dependencia, ambas pueden iniciar ni bien comience el proyecto. Se coloca un nodo de llegada para cada una de ellas (el cual indica el término de la tarea) ya que dos tareas no pueden tener el mismo nodo de inicio y el mismo de fin.
Ahora las que faltan: la tarea D depende únicamente de A, así que sólo debe esperar a que esta esté terminada para comenzar; eso significa que la arista "D" tiene como nodo de inicio aquel que sirve de llegada a la arista "A".
La tarea C, por otro lado, depende tanto de A como de B. Ya que es imposible dibujar una flecha que salga de dos puntos a la vez, unimos los nodos finales de A y B con lo que se conoce como "tarea ficticia" o "imaginaria". Esta clase de tareas no tiene tiempo de duración (es decir que su duración es cero), y en realidad no existen. Se indican con una línea de puntos para diferenciarlas de las tareas reales.
También existen los nodos imaginarios.
Como las tareas C y D son las tareas
"finales" del proyecto, y como todo diagrama solo puede tener UN nodo
de inicio y UN nodo de fin, entonces hacemos que ambas terminen en el nodo
final (aqui nodo 4). El número que aparece indicado junto al nombre de la tarea
es su tiempo de duración.
Así, por ejemplo en el nodo de llegada de A, ya que el tiempo temprano de su nodo de inicio es 0, entonces 0+3= 3.
El caso del nodo 3 es un poco más complicado. Mientras que al nodo dos sólo llega una tarea, a este llegan dos, contando la tarea ficticia. El camino que debemos elegir es aquél que nos dé como resultado el tiempo más grande, ya que así nos aseguramos de que las todas las tareas que lleguen a ese nodo hayan terminado. Siguiendo ese criterio:
0 (tiempo de inicio del nodo 1) + 5 (duracion de la tarea B) = 5
3 (tiempo de inicio del nodo 2) + 0 (duración de la tarea ficticia) = 3
El tiempo temprano del nodo 3 es 5. Pasa lo mismo con el nodo 4, así que aplicamos el mismo método y nos da como resultado que 10 + 5= 15. Esta es la duración total del proyecto.
Los tiempos temprano y tardío del nodo final del proyecto, al igual que pasa con su nodo de inicio, son siempre iguales.
Terminados los tiempos tempranos, pasamos a calcular los tiempos tardíos. Partiendo del nodo final del proyecto, damos "marcha átras", restando la duración de la tarea. Así, el nodo 3 tendría como tiempo tardía 15-10=5.
Hay que notar,
sin embargo, que del nodo 2 parten dos tareas, en este caso ya que estamos
yendo "marcha atrás", seleccionamos el menor de los tiempos, al
contrario de como hicimos antes. Así:
15 - 8= 7
5 - 0 = 5
Nos quedamos con la tarea ficticia, y colocamos ese 5 como tiempo tardío de nuestro nodo 2. Del nodo 1 también parten dos tareas, así que utilizando el mismo método:
5 - 3 = 2
5 - 5 = 0
Tiene que dar cero cuando se llega al nodo de inicio. Siempre, si no es así hay algun error.
Con los números algo chuecos, pero nuestro precioso gráfico está al fin
terminado. 15 - 8= 7
5 - 0 = 5
Nos quedamos con la tarea ficticia, y colocamos ese 5 como tiempo tardío de nuestro nodo 2. Del nodo 1 también parten dos tareas, así que utilizando el mismo método:
5 - 3 = 2
5 - 5 = 0
Tiene que dar cero cuando se llega al nodo de inicio. Siempre, si no es así hay algun error.
Ahora que tenemos representadas las tareas con sus respectivas duraciones, y tanto el tiempo temprano como el tardío en el que deriva cada una. Con estos datos ya estamos listos para calcular nuestro camino crítico.
Se calcula mediante una ecuación para nada complicada: tj1 - d - ti0. Y para que entiendan el idioma en el cual les hablo, paso a explicar:
"ti0" y "ti1" son los tiempos del nodo del cual parte la tarea, ti0 es el tiempo temprano y ti1 es el tiempo tardío. Así, por ejemplo para la tarea D, ti0=3 y ti1=5 respectivamente.
"tj0" y "tj1" son los tiempos del nodo de llegada de la tarea, el temprano y el tardio. En el caso de la tarea D serían 15 y 15 (el nodo 4).
"d" es la duración de la tarea.
La tabla es para organizar mejor nuestros datos. Ahora calculamos utilizando la ecuación antes mencionada: Tj1 - D - Ti0
A) 5 - 3 - 0 = 2
B) 5 - 5 - 0 = 0
C) 15 - 10 - 5 = 0
D) 15 - 8 - 3 = 4
Aquellas tareas cuyas ecuaciones nos den como resultado 0 son las que conforman el camino crítico. Las marcamos en el gráfico:
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi7Q7RaqMAyPTyD0JGKZUvQiNRHE1rapWr1QIJGymI8_AZrtglOVnVB7DgQpDnKRQTC7gg-bqSk2ckhOw1jUfPBbl6OzgTqht_VGRRVIMwh9rc1JwopYkh9UvbKBeDSXGzXAuNJ43do-MI/s400/8.png)
De esta manera ya tenemos resuelto nuestro ejercicio.
También es importante destacar, aunque este ejercicio en particular no es el caso, que las tareas ficticias también pueden formar parte del camino crítico, pero sólo como nexo que permite unir dos nodos del mismo. Ejemplo, siempre viene bien un ejemplo:
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Ordenación en Niveles del Grafo - Método de Demoucron
Descargar apunte aquí