Investigacion Operativa


¿Qué es la Investigación Operativa?

  
La Investigación Operativa o Investigación de Operaciones es una disciplina moderna que mediante el uso de modelos matemáticos, estadística y algoritmos modela y resuelve problemas complejos determinando la solución óptima y permitiendo, de esta forma, la toma de decisiones.

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
U.S. Military Airlift Command
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: 

 

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. 


Ahora que el diagrama está hecho, hay que calcular los tiempos. Simplemente hay que realizar una suma entre el tiempo temprano del nodo de inicio (el nodo del cual parte la tarea) y la duración misma.

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. 

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: 

                                            

 


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í