jueves, 7 de abril de 2011

Teoria de colas y lineas

Introducción

Concepto
El problema planteado es difícil de describir por la presencia de elementos aleatorios en el arribo y la atención de clientes. Para ello se ha desarrollado la Teoría de Cola o de la Línea de Espera que se basa en describir el arribo o la partida (o servicio) por distribuciones de probabilidad apropiadas. Usando teoría de probabilidad se derivan las características operativas del problema, como ser tiempo de espera hasta que el servicio del cliente sea completado, porcentaje de tiempo desocupado por servicio, etc., con tales elementos, el analista hace inferencias de la operación del sistema y puede ajustarlos para asegurar una efectiva utilización desde el punto de vista del cliente y del servidor. La teoría de cola también resulta útil para analizar muchos de los problemas relacionados al diseño del proceso.
A menudo es deseable tomar decisiones respecto de una situación de teoría de cola, basándose en algún tipo de análisis de costos. Por ejemplo, un incremento en el número de servidores en el sistema reduciría el tiempo de espera, pero incrementaría el costo del servicio e inversamente. Si se pudiera expresar el tiempo promedio de espera en valores monetarios, es posible seleccionar el óptimo número de servidores (o la velocidad de servicio) que minimiza la suma de los costos se servicio y el tiempo de espera. El problema de este enfoque radica que en la práctica es muy difícil de estimar el costo por unidad de espera.

 
Proceso Básico de las Colas
El proceso básico supuesto por la mayor parte de los modelos de colas es el siguiente. Los

 
Una característica de la fuente de entrada es su
Debe especificarse el patrón estadístico mediante el cual se generan los clientes a través del tiempo. La suposición normal es que se generan de acuerdo al proceso de Poisson. Este caso corresponde a aquel cuyas llegadas al sistema ocurren de manera aleatoria, pero con cierta taza media fija y sin importar cuantos clientes están ya allí (por lo que el tamaño de la fuente de entrada es ilimitada o limitada). infinito). Una suposición equivalente es que, la distribución de probabilidad del tiempo que transcurre entre dos llegadas consecutivas es exponencial. Se hace referencia al tiempo que transcurre entre dos llegadas consecutivas como tiempo entre llegadas.
Debe especificarse el patrón estadístico mediante el cual se generan los clientes a través del tiempo. La suposición normal es que se generan de acuerdo al proceso de Poisson. Este caso corresponde a aquel cuyas llegadas al sistema ocurren de manera aleatoria, pero con cierta taza media fija y sin importar cuantos clientes están ya allí (por lo que el tamaño de la fuente de entrada es

Población Finita
Es un grupo limitado de clientes que representa la fuente que usará un servicio y que en ocasiones forma una cola. En esta caso cuando un cliente deja su posición como miembro de la población de usuarios, se reduce en una unidad el tamaño del grupo de usuarios, lo cual reduce la probabilidad que un usuario requiera servicio. Por el contrario, si se brinda mantenimiento a un cliente y éste regresa al grupo de usuarios, aumenta la población y también la probabilidad de que un usuario requiera servicio. (ejemplos: reparación de cosechadoras, las PC de un gabinete, etc.).

Población Infinita
Es aquella población que tiene el tamaño suficiente en comparación con el sistema de servicio, para que los cambios en el tamaño de la población, ocasionados por disminuciones o incremento a la población, no afectan de manera sustancial las probabilidades del sistema. (ejemplos: en un supermercado los clientes que hacen fila; la cola en un banco; en una estación de gasolina, etc.).

2 – Llegadas
Proceso de Llegada
Es la forma en que los clientes de la fuente de entrada llegan a solicitar un servicio. La característica más importante del proceso de llegada es el tiempo entre llegadas, que es la cantidad de tiempo entre dos llegadas sucesivas de clientes a un sistema de colas.
Se supone que el proceso de llegada no es afectado por el número de clientes presentes en el sistema. Existen casos en los que el proceso de llegada puede depender del número de clientes presentes en el sistema, como en el caso de una población pequeña.
Ejemplo: hay cuatro barcos en un astillero, si los cuatro están en reparación, entonces ningún barco se puede descomponer en el futuro cercano. Por otro lado, si los barcos están en el mar, en el futuro cercano hay una probabilidad relativamente alta de que alguno sufra una avería.
Otro caso en el que el proceso de llegada depende del número de clientes presentes en cola, se tiene cuando la rapidez con la que llegan los clientes a la instalación disminuye si está demasiado concurrida. Por e

3 – Cola
colas en los que la cota superior es tan pequeña que se llegan a ella con cierta frecuencia, se suponen como cola finita.

Costos del Sistemas de Colas
jemplo: si un banco tiene mucha gente, cuando llega un cliente se puede ir. Una cola se caracteriza por el número de clientes que puede admitir. Las colas pueden ser finitas o infinitas; la suposición de una cola infinita es la estándar en la mayoría de los modelos, incluso las situaciones en las que de hecho existe una cota superior (relativamente grande) sobre el número permitido de clientes. Los sistemas de colas en los que la cota superior es tan pequeña que se llegan a ella con cierta frecuencia, se suponen como cola finita.
Las

Costo de Espera
llegadas son las unidades que entran en el sistema para recibir el servicio; estos elementos se unen primero a la cola; si no hay línea de espera se dice que la cola esta vacía.
Esperar significa desperdicio de algún recurso activo que bien se puede aprovechar en otra cosa y esta dado por:
Costo total de espera = Cw * L
Donde
Cw = costo de espera por llegada y por unidad de tiempo, y
L
Sistema de Costo Mínimo
= a longitud promedio de la cola.
Aquí hay que tomar en cuenta (ver Figura 2), que para tasas bajas de servicio se experimenta largas colas y costos de espera muy altos. Conforme aumenta el servicio disminuyen los costos de espera, pero aumenta el costo de servicio y el costo total disminuye, sin embargo, finalmente se llega a un punto de disminución en el rendimiento. Por lo tanto, se debe encontrar el balance adecuado para que el costo total sea el mínimo.

Figura 2: Costos de los Sistemas de Colas.  
4 – Selección a Partir de la Cola o Línea de Espera

Disciplina de Cola
La disciplina de la cola se refiere al orden en el que se seleccionan los clientes para recibir el servicio. Por ejemplo, el primero en entrar es el primero en salir; aleatoria; de acuerdo a algún procedimiento de prioridad o a algún otro orden. En general la disciplina de los modelos de cola es: primero en entrar, primero en salir. Las reglas de prioridades más comunes para determinar el orden de servicio a los clientes que esperan en la cola son:
PEPS: Primero Entrado, Primero Salido.
UEPS. Ultimo Entrado, Primero Salido.
SEOA: Servicio en Orden Aleatorio.
GD: Disciplina General de Servicio (representa las disciplinas PEPS, UEPS y SEOA).
5 – Instalación de Servicios o Estaciones
El mecanismo de servicio consiste en una o más
El tiempo que transcurre para un cliente desde el inicio del servicio hasta su terminación en una instalación se llama tiempo de servicio (
instalaciones de servicio, cada una de ellas con uno o más canales paralelos de servicio, llamados servidores. Si existe más de una instalación de servicio, puede ser que sirva al cliente a través de una secuencia de ellas (canales en serie de servicio). En una instalación dada, el cliente entra en uno de estos canales y el servidor le presta el servicio completo. Un modelo de colas debe especificar el arreglo de las instalaciones y el número de servidores (canales paralelos) en cada una. o duración del servicio). Un modelo de sistema de colas determinado debe especificar la distribución de probabilidad de los tiempos de servicio para cada servidor (y tal vez para los distintos clientes), aunque es común suponer la misma distribución para todos los servidores. El flujo de los elementos que recibirán servicios puede formar una cola única, una cola múltiple o una combinación de ambas y pueden ser brindadas por un servidor o múltiples servidores.

i) Un Servidor - Una Cola
Es el tipo más sencillo de estructura y existen fórmulas directas para resolver el problema con distribución normal de patrones de llegada y de servicio. Cuando las distribuciones no son normales se resuelve con simulaciones (ejemplo: lavadero automático de autos, muelle de descarga de un solo lugar, etc.).
Figura 3: Un Servidor – Una Cola.

 
1 – Fuente de Entrada
clientes que requieren servicios, a través del tiempo, provienen de una fuente de entrada. Estos clientes arriban al sistema de servicios y se unen a una cola. En un determinado tiempo se selecciona un miembro de la cola, mediante alguna regla conocida como disciplina de servicio. Luego, se brinda el servicio requerido por el cliente en un mecanismo de servicio, después de lo cual el cliente sale del sistema de servicio. (ver Figura 1). Figura 1: Esquema del Proceso de Cola.
ii) Múltiples Servidores (en paralelo) – Varias Colas
El problema con este formato es que las diferencias en el tiempo de servicio para cada cliente ocasionan un flujo o velocidad desigual en las colas. Como resultado de esto, algunos clientes son atendidos antes que otros que llegaron primero y además producen cambios de una cola a otra (por ejemplo: las ventanillas de los bancos y las cajas de pago de los supermercados).

iii) Múltiples Servidores (en paralelo) – Una Cola
Para modificar una estructura de manera que se asegure el servicio por orden de llegada, es necesario formar una sola cola, de la cual, al quedar disponible un servidor se le asigna el siguiente cliente.
El principal problema con esta estructura es que requiere un estricto control de la cola para mantener el orden y dirigir a los clientes hacia los servidores disponibles. (ejemplo: peluquería o una panadería en donde los clientes toman un número al entrar y se les sirve cuando llega el turno).


iv) Múltiples Servidores (en serie) – Una Cola
Un factor crítico del caso de un solo canal con servicio en serie es la cantidad de elementos que se acumulan al frente de cada servicio, lo cual genera colas de espera separada. Un ejemplo es el lavado de un automóvil, donde se realizan varios servicios (limpieza con aspiradora, remojo, lavado, enjuague, secado, estacionamiento) en una secuencia bastante uniforme.
Por la variación inherente de los tiempos de servicio, la situación óptima para maximizar el uso del servicio es permitir que se forme una cola de espera infinita frente a cada servidor. La peor situación es aquella donde no se permiten colas y sólo puede estar un cliente. Este problema es común en muchos sistemas orientados a productos (líneas de montaje), en los sistemas orientados a procesos (talleres de trabajo, procesamiento órdenes por lotes), permite la utilización máxima del servidor al dejar que el inventario de artículos disponibles absorba la variación en tiempo de desempeño.



v) Múltiples Servidores - Fases Múltiples
En este caso se sigue una secuencia de pasos específicos, como en el caso de admisión de pacientes en un hospital (contacto inicial en el mostrador de admisión, llenar formularios, elaborar tarjetas de identificación, obtener la asignación de una habitación, llevar al paciente a la habitación, etc.). Es posible procesar más de un paciente a la vez, ya que generalmente existen varios servidores disponibles para este procedimiento.



6 - Proceso de Salida
Es la forma en que los clientes abandonan un sistema de colas. Para describir el proceso de salida de un sistema de cola, se especifica una distribución de probabilidad. En la mayor parte de los casos suponemos que la distribución de tiempo de servicio es independiente del número de clientes presentes, es decir que el servidor no trabaja más rápido cuando hay más clientes.
Modelos de Teoría de Cola


El modelo 5 y 6, suelen llamarse de servicio cerrado. El servidor atiende a un número constante de máquinas o unidades. Cuando una máquina se rompe, no puede generarse nuevos llamados mientras permanezca en servicio. En el caso del modelo 6 el sistema tiene un total de K máquinas que son atendidas por R operarios.

Notación para Modelos de Cola

(A,B,C,):(D,E,F)
A
: distribución de arribos (M=Poisson – D=Determinista – E=Erlang).
B
: distribución de salidas (M=Poisson – D=Determinista – E=Erlang).
C
: Número de servidores en paralelo. (
D
: Disciplina del servicio.
E
F: Población


  
: Número máximo de clientes permitidos en el sistema (en cola + en servidores).
 

Una situación de cola se caracteriza por el flujo de clientes que arriban a una o más estaciones en las que se efectúa el servicio. Al arribo del cliente, éste puede ser atendido inmediatamente o puede tener que esperar hasta que el servicio esté disponible; el tiempo en la cual se atiende a cada cliente puede ser fijo o aleatorio, dependiendo del tipo de servicio. En la vida diaria hay muchos ejemplos que se adaptan a esta situación: autos arribando a una estación de servicio, o a un peaje; personas arribando al cajero automático; máquinas que fallan y que requieren ser reparadas; etc.

Modelo del tamaño del lote

MODELO DE TAMAÑO DEL LOTE ECONÓMICO BÁSICO (EOQ)

Esta técnica es relativamente fácil de usar pero hace una gran cantidad de suposiciones.
Las más importantes son:
1. la demanda es conocida y constante
2. el tiempo de entrega, esto es, el tiempo entre la colocación de la orden y la recepción del pedido, se conoce y es constante.
3. La recepción del inventario es instantánea. En otras palabras, el inventario de una orden llega en un lote el mismo momento.
4. Los descuentos por cantidad no son posibles.
5. Los únicos costos variables son el costo de preparación o de colocación de una orden (costos de preparación) y el costo del manejo o almacenamiento del inventario a través del tiempo (costo de manejo).
6. Las faltas de inventario (faltantes) se pueden evitar en forma completa, si las órdenes se colocan en el momento adecuado. La gráfica de utilización del inventario a través del tiempo tiene la forma de dientes de serrucho como en la figura 1.


En ésta, la letra Q representa la cantidad que se está ordenando. Si la cantidad es de 500 vestidos todos llegan en el mismo momento (cuando se recibe una orden). Por lo tanto, el nivel del inventario salta de 0 a 500 vestidos. En general, un inventario crece de 0 a Q unidades cuando llega la orden.Si la demanda es constante en un rango de tiempo, el inventario cae en una tasa uniforme a través del tiempo. (línea con pendiente de la figura). Cuando un nivel de inventario llega a 0, se coloca una nueva orden y se recibe y el nivel del inventario vuelve a saltar a unidades Q (representadas por las líneas verticales). Este proceso continúa a través del tiempo.



Nivel de inventario


Tasa de utilización

Cantidad ordenada = Q
(nivel máximo de inventario) Inventario promedio (Q/2)


Inventario mínimo 0

Tiempo

Figura 1. Utilización del inventario a través del tiempo.


VARIABLES

Q = número de piezas por orden.
Q* = número óptimo de piezas por orden (EOQ).
D = demanda anual en unidades para el producto del inventario.
S = costo de preparación para cada orden.
H = costo de manejo del inventario por unidad por año.
N = número esperado de órdenes.
T = tiempo esperado de órdenes.
CT = costo total.
FORMULAS.


Costo anual de preparación = (Número de órdenes colocadas/año)(Costo de preparación/orden)
Costo anual de manejo = (Nivel promedio de inventario)(Costo de manejo/unidad/año)



La cantidad óptima de cada orden se encuentra cuando el costo anual de preparación es igual al costo anual de manejo, es decir:


Para resolver Q*, sencillamente se multiplican los términos, el denominador por el numerador del miembro contrario y se despeja Q a la izquierda del signo de igual.
Número esperado de órdenes colocadas durante el año (N) y el tiempo transcurrido entre las órdenes (T).






Costo total anual = Costo de preparación + Costo de manejo


DESARROLLO DEL MÉTODO

EJEMPLO

Sharp, Inc., una empresa que comercializa las agujas hipodérmicas indoloras en los hospitales, desea reducir sus costos de inventario mediante la determinación del número de agujas hipodérmicas que debe obtener en cada orden. La demanda anual es de 1000 unidades; el costo de preparación o de ordenar es de 10 dólares por orden; y el costo de manejo por unidad de año es de 50 centavos de dólar. Utilizando estos datos, calcule el número óptimo de unidades por orden (Q*), el número de órdenes (N), el tiempo transcurrido (T), y el coso total anual del inventario. Utilizar un año laboral de 250 días.

Solución: utilizando las ecuaciones (1.1), (1.2), (1.3), y (1.4), tenemos:






El modelo EOQ tiene otra distinción importante; es un modelo robusto. El modelo robusto se refiere a que éste proporciona respuestas satisfactorias aun con variaciones substanciales a otros parámetros. Un modelo robusto es ventajoso. El costo total del EOQ cambia un poco en las cercanías del mínimo. Esto significa que los costos de preparación, los costos de manejo, la demanda y aun el EOQ representan pequeñas diferencias en el costo total.

EJEMPLO :
Utilizando los datos del ejemplo 3. Si la administración subestima la demanda total anual en un 50% (por decir, que en realidad sea de 1500 unidades en lugar de las 1000 unidades) mientras que se utiliza la misma Q, el costo anual del inventario se incrementa sólo en 25 dólares (1000 dólares contra 125 dólares) o 25 % como se muestra abajo. En forma similar, si la administración recorta el tamaño de la orden en un 50% de 200 a 100, el costo se incrementa en 25 dólares (100 dólares contra 125 dólares) o 25 por ciento:

a) Si la demanda del ejemplo 3 es en realidad de 1500 en lugar de 100, pero la administración utiliza una EOQ de Q = 200 (cuando debe ser Q = 244.9 basándose en D = 1500), el costo total se incrementa en 25%.


b) Si el tamaño de la orden se reduce de 200 a 100, pero todos los demás parámetros permanecen constantes, el costo también se incrementa el 25%:
El Economic Order Quantity, o EOQ, constituye actualmente uno de los sistemas de administración de inventarios. Creado a principios del sigloXX, el EOQ es un método que, tomando en cuenta la demanda, el costo por mantener (en inventario), y por ordenar, así como el costo del artículo, produce como salida la cantidad óptima a ordenar, para minimizar costos por mantenimiento de los artículos.
El principio del EOQ es simple, y se basa en encontrar el punto en el que los costos por ordenar artículos y los costos por mantenerlos en inventario son iguales.
Se trata de un método que no da una solución óptima, pero sí se aproxima a ésta. Otro de sus defectos, es que considera una demanda determinística.
Método de inventario cíclico del inventario
El inventario cíclico es un método de inventario en el que el inventario se cuenta a intervalos regulares durante el ejercicio. Dichos intervalos (o ciclos) dependen del indicador de inventario cíclico establecido en los materiales.
El inventario cíclico permite contar con más frecuencia los artículos de alta rotación que los artículos obsoletos, por ejemplo.
Procedimiento general
En el registro maestro de materiales (datos de almacén), se marcan todos los materiales que deben incluirse en el inventario cíclico, mediante un indicador de inventario cíclico. El indicador de inventario cíclico se utiliza para agrupar los materiales en diversas categorías de inventario cíclico (por ejemplo, A,B,C y D). En cada categoría se definen los intervalos de tiempo del recuento de materiales.
Se pueden marcar los materiales del siguiente modo:
  • Manualmente en el registro maestro de materiales (datos de almacén)
  • Automáticamente con el análisis ABC
Para realizar un análisis ABC, utilice el programa RMCBIN00. En dicho análisis, el sistema asigna los materiales a las categorías individuales, según el consumo o las necesidades. También se puede especificar si en el análisis sólo deben considerarse los materiales con indicador de inventario cíclico, o bien deben considerarse todos los materiales. El indicador de inventario cíclico puede actualizarse automáticamente mientras se ejecuta el análisis ABC.
Para planificar el inventario cíclico, se ejecuta el programa RM07ICN1 a intervalos regulares. Dicho programa verifica todos los materiales de inventario cíclico para determinar si debe hacerse un inventario.
Si es necesario hacer inventario de un material, se utiliza el programa que genera juegos de datos batch input para crear documentos para inventario. Sólo se crean documentos para inventario del tipo de stocks 1 (stock de libre utilización). La fecha de recuento prevista se calcula del siguiente modo:
  • Fecha de último inventario + intervalo predefinido.
El intervalo de inventario de cada indicador de intervalo cíclico se define en el Customizing.
Para crear documentos para inventario, es necesario procesar los juegos de datos batch input.
Realice el inventario. Cuando se contabilizan las diferencias de inventario, la fecha de recuento real queda registrada en los datos de inventario del material como la fecha del último inventario.
Para obtener más información sobre los programas utilizados en el inventario cíclico, consúltese la documentación de report relevante.
Etapas generales del inventario cíclico
El inventario cíclico de materiales está formado por las siguientes etapas:
Marca de materiales del inventario cíclico
Esta etapa sólo es necesaria si se realiza un inventario cíclico por primera vez o si se desea actualizar los indicadores de inventario cíclico.
En el registro maestro de materiales (datos de almacén), se actualiza el indicador de inventario cíclico de todos los materiales a incluir en el inventario cíclico.
Se puede activar el indicador de uno de los siguientes modos:
  • Actualización manual del indicador en el registro maestro de materiales (datos de almacén). Para actualizarlo, seleccione Material  Modificar en el menú Maestro de materiales.
  • Actualización automática del indicador durante la ejecución del análisis ABC. En tal caso, seleccione Procedimientos especiales  Intervalo cíclico  Fijar indicador IC.
Creación de documentos para inventario cíclico
Para crear documentos para inventario, realice lo siguiente:
  1. En el menú de inventario, marque Procedimiento especial  Inventario cíclico  Crear documento para inventario. Aparecerá la pantalla inicial de la función.
  2. Actualice los datos en la pantalla inicial.
  3. Realice la valoración.
  4. Para generar el juego de datos batch input, seleccione Tratar  Generar juego de datos en el menú.
  5. Para procesar el juego de datos, seleccione Sistema  Servicios  Batch input  Tratar en el menú.
  6. Haga inventario de los documentos para inventario creados.
Inventario Cíclico: Son inventarios que se requieren para apoyar la decisión de operar según tamaños de lotes. Esto se presenta cuando en lugar de comprar, producir o transportar inventarios de una unidad a la vez, se puede decidir trabajar por lotes, de esta manera, los inventarios tienden a acumularse en diferentes lugares dentro del sistema.

Metodos CPM y PERT

MÉTODOS CPM Y PERT
Los métodos CPM (método de la ruta crítica o del camino crítico, criticaI path method) y PERT (técnica de evaluación y revisión de programa, program evaluation and review techni- que) se basan en redes, y tienen por objeto auxiliar en la planeación, programación y control de proyectos. Se define un proyecto como conjunto de actividades interrelacionadas, en la que cada actividad consume tiempo y recursos. El objetivo del CPM y del PERT es contar con un método analítico para programar las actividades. En la figura 6.50 se resumen los pasos de estas técnicas. Primero se definen las actividades del proyecto, sus relaciones de precedencia.

Figura 6.50

y sus necesidades de tiempo. A continuación, el proyecto se traduce en una red que muestre las relaciones de precedencia entre las actividades. El tercer paso implica cálculos específicos de redes, que forman la base del desarrollo del programa del proyecto en función del tiempo.
Durante la ejecución del proyecto, podría no cumplirse el programa que estaba planeado, causando que algunas de las actividades se adelanten o se atrasen. En este caso será necesario actualizar el programa para que refleje la realidad. Ésta es la razón de incluir un bucle, lazo o ci­clo de retroalimentación entre la fase de programa y la fase de red, como se ve en la figura 6.50.
Las dos técnicas, CPM y PERT, que se desarrollaron en forma independiente, difieren en que en el CPM se supone duraciones determinísticas de actividad, mientras que en PERT se suponen duraciones probabilísticas. Esta presentación comenzará con el CPM y después se pre­sentarán los detalles del PERT.


Representación en red
Cada actividad del proyecto se representa con un arco que apunta en la dirección de avance del proyecto. Los nodos de la red establecen las relaciones de precedencia entre las diferentes actividades del proyecto.
Para configurar la red se dispone de dos reglas:
Regla 1. Cada actividad se representa con un arco, y uno sólo.
Regla 2. Cada actividad se debe identificar con dos nodos distintos.

La figura 6.51 muestra cómo se puede usar una actividad ficticia para representar dos actividades concurrentes, A y B. Por definición, la actividad ficticia, que normalmente se re­presenta con un arco de línea interrumpida, no consume tiempo o recursos. La inserción de una actividad ficticia en una de las cuatro formas que se ven en la figura 6.51, mantiene la concurrencia de A y B, y también proporciona nodos finales únicos para las dos actividades (para satisfacer la regla 2).

Regla 3. Para mantener las relaciones de precedencia correctas, se deben contestar las si­guientes preguntas cuando se agrega a la red cada actividad:
a)         ¿Qué actividades deben anteceder inmediatamente a la actividad actual?
b)         ¿Qué actividades deben seguir inmediatamente a la actividad actual?
c)         ¿Qué actividades deben efectuarse en forma concurrente o simultánea con la actividad actual?

Figura 6.51 


Uso de una actividad ficticia para tener representación única de las actividades concurrentes A y B
Para contestar estas preguntas se podrá necesitar el uso de actividades ficticias, para asegurar las precedencias correctas entre las actividades. Por ejemplo, considere al siguiente segmento de un proyecto:
  1. La actividad C comienza de inmediato después de haber terminado A y B.
  2. La actividad E se inicia después de que sólo terminó la actividad B.
La parte (a) de la figura 6.52 muestra la representación incorrecta de esta relación de prece­dencia, porque pide que A y B terminen antes de poder iniciar E. En la parte B se corrige la si­tuación con el uso de la actividad ficticia.


Figura 6.52: Uso de una actividad ficticia para asegurar una relación de precedencia correcta


Ejemplo
Un editor tiene un contrato con un autor, para publicar su libro de texto. Las actividades (sim­plificadas) relacionadas con la producción del libro se ven a continuación. Formular la red asociada al proyecto.



La figura 6.53 muestra la red que describe las relaciones de precedencia entre las diver­sas actividades. Con la actividad ficticia (2, 3) se obtienen nodos finales únicos para las ac­tividades concurrentes A y B. La numeración de los nodos se hace en forma que indique el avance en el proyecto.

Figura 6.53



Cálculos para la ruta crítica (CPM)
El resultado final de CPM es la formulación o construcción del programa del proyecto (véase la figura 6.50). Para lograr este objetivo en una forma adecuada, se hacen cálculos especiales con los que se obtiene la siguiente información:
a)    Duración total necesaria para terminar el proyecto.
b)    Clasificación de las actividades del proyecto en críticas y no críticas.

Se dice que una actividad es crítica si no hay margen en la determinación de sus tiem­pos de inicio y de término. Una actividad no crítica permite alguna holgura en su programa­ción, de modo que el tiempo de inicio de la actividad se puede adelantar o retrasar dentro de ciertos límites, sin afectar la fecha de terminación de todo el proyecto.

Para efectuar los cálculos necesarios, se define un evento como un momento en el tiem­po en el que se terminan actividades y otras se inician. En términos de redes, un evento co­rresponde a un nodo. Se define lo siguiente:
= Tiempo más temprano de ocurrencia del evento j
Aj = Tiempo más tardío de ocurrencia del evento j
D¡j = Duración de la actividad (i, j)

Las definiciones de los tiempos más temprano y más tardío del evento j se especifican en re­lación con las fechas de inicio y terminación de todo el proyecto.
Los cálculos de ruta crítica implican dos pasos: el paso hacia adelante determina los tiempos más tempranos o de ocurrencia de los eventos, y el paso hacia atrás calcula sus tiem­pos más tardíos de ocurrencia.

Paso hacia adelante (tiempos más tempranos de ocurrencia o tiempos más próximos, de ocurrencia, □). Los cálculos se inician en el nodo 1 y avanzan en forma recursiva hasta el nodo final n.

Paso inicial. Poner = 0, para indicar que el proyecto se inicia cuando el tiempo es 0. Paso general j. Dado que los nodos p, q, …, y v están enlazados directamente con el nodo j por las actividades de entrada (p,j), (q,j),…, y (v,j) y que los tiempos más tempra­nos de ocurrencia de los eventos (nodos) p, q,…, y v ya se han calculado, entonces se calcula el tiempo más temprano de ocurrencia del evento j como sigue:
máx {□„ + üpp + Dqr …, a + DVI}
El paso hacia adelante se termina cuando se calcula □„ en el nodo n. Por defini­ción, □• representa la ruta (duración) más larga al nodo j.

Paso hacia atrás (tiempos más tardíos de ocurrencia o tiempos más lejanos de ocurren­cia, A). Después de terminar el paso hacia adelante, los cálculos del paso hacia atrás co­mienzan en el nodo n y terminan en el nodo 1.

Paso inicial. Igualar A„ = para indicar que las ocurrencias más temprano y más tardío
del último nodo en el proyecto son iguales. Paso general j. Dado que los nodos p, q, …, y v están enlazados en forma directa con el nodo j por actividades de salida (j, p), (j, q),…, y (/’, v), y que ya se calcularon los tiempos más tardíos de los nodos p, q, …, y v, el tiempo tardío del nodo j se calcula como sigue:
A, = mín {Ap - Djp, \ – Djq,…, Av. – Djv} El paso hacia atrás se termina cuando se calcula A, en el nodo 1.
Con base en los cálculos anteriores, una actividad (i, j) será crítica si satisface tres con­diciones:
a)      a,- = q¡
b)         Aj = D;
c)         A, – A,- = – = D,,

Las tres condiciones indican que los tiempos más tempranos y más tardíos de ocurrencia de los nodos i y j son iguales, y que la duración D;j se ajusta exactamente al intervalo especifica­do de tiempo. Una actividad que no satisface las tres condiciones es no crítica.
Las actividades críticas de una red deben formar una trayectoria no interrumpida que abarque toda la red, desde el inicio hasta el final.


Ejemplo
Determinar la ruta crítica para la red del proyecto de la figura 6.54. Todas las duraciones están en días.

Paso hacia adelante
Nodo 1. Hacer o definir □, = 0 Nodo 2. IHj = □, + Dn = 0 + 5 = 5
Nodo 3. CI3 = máx{D, + D13, C^ + D23} = máx {0 + 6, 5 + 3} = 8 Nodo 4. Q, = Ct + D24 = 5 + 8 = 13
Nodo 5. CI5 = máx {□, + D35, O, + £>45} = máx {8 + 2, 13 + 0} = 13 Nodo 6. q, = máx {O, + D36, + D^, Ds + D56} = máx {8 + 11, 13 + 1, 13 + 12} = 25
Los cálculos indican que el proyecto se puede terminar en 25 días.


Paso hacia atrás
Nodo 6.          Hacer A6 = = 25
Nodo 5.          A5 = A6 D56 = 25 – 12 = 13
Nodo 4.          A4 = mín {A6 – D46, A5 – D45} = mín {25 – 1, 13 – 0} = 13
Nodo 3.          A3 = mín {A6 – D36, A5 – D35} = mín {25 – 11, 13 – 2} = 11
Nodo 2.          A2 = mín {A4 – D24, A3 – £>23} = mín {13 – 8, 11 – 3} = 5
Nodo 1.          A, = mín {A3 – D,3, A2 – D,2} = mín {11 – 6, 5 – 5} = 0
Si los cálculos fueron correctos, siempre terminarán con A! = 0.
Los cálculos en los pasos hacia adelante y hacia atrás se resumen en la figura 6.54. Las re­glas para determinar las actividades críticas indican que la ruta crítica esl—>2—>4—>5—>6, que abarca la red desde el inicio (nodo 1) hasta el fin (nodo 6). La suma de las duraciones de las actividades críticas [(1,2), (2,4), (4, 5) y (5,6)] es igual a la duración del proyecto (= 25 días), Observe que la actividad (4, 6) satisface las dos primeras condiciones para que la actividad sea crítica (A4 = m4 = 13yA5 = II]5 = 25), pero la tercera no (C^ – D4 ^ D^). Por consi­guiente, esa actividad no es crítica.

Figura 6.54 


Redes de PERT
El PERT difiere del CPM en que basa la duración de una actividad en tres estimaciones:
1.        Tiempo optimista a, donde se supone que la ejecución va extremadamente bien.
2.        Tiempo más probable m, donde se supone que la ejecución se hace bajo condiciones normales.
3.        Tiempo pesimista b, donde se supone que la ejecución va extremadamente mal.

Se supone que el intervalo (a, b) abarca todas las estimaciones posibles de la duración de una actividad. Por consiguiente, el estimado m debe estar en algún lugar dentro del intervalo (a, b). Con base en los estimados (o estimaciones), el tiempo promedio de duración D, y la va- rianza v, se calculan como sigue:
_ a + 4m + b

Los cálculos de ruta crítica (CPM) que se describieron en las secciones 6.6.2 y 6.6.3 se pue­den aplicar en forma directa, sustituyendo la estimación única D por D.
Ahora es posible estimar la probabilidad de que un nodo j en la red suceda en un tiempo programado especificado con anterioridad, Sj. Sea el tiempo más temprano de ocurrencia del nodo j. Como las duraciones de las actividades que van del nodo de inicio al nodo j son variables aleatorias, también debe ser una variable aleatoria. Suponiendo que todas las acti­vidades en la red sean estadísticamente independientes, se puede determinar la media, E{e¿) y la varianza, var{^} como sigue. Si sólo hay una ruta desde el nodo de inicio hasta el nodo j, la media es la suma de las duraciones esperadas D, para todas las actividades a lo largo de esa ruta, y la varianza es la suma de las varianzas v de las mismas actividades. Por otra parte, si

hay más de una ruta que llegue al nodo j, será necesario calcular primero la distribución esta­dística de la duración de la ruta más larga, antes de calcular la media y la varianza correctas. Este problema es bastante difícil, porque equivale a determinar la distribución del máximo de varias variables aleatorias. Por consiguiente, una hipótesis simplificadora es calcular la media y la varianza, y var{e¡}, como el de la ruta al nodo j que tenga la suma mayor de dura­ciones esperadas de las actividades. Si hay dos o más rutas que tienen la misma media (o pro­medio), se selecciona la que tenga la varianza mayor, porque refleja la máxima incertidumbre y en consecuencia conduce a un estimado más conservador de las probabilidades.
Una vez calculados la media y la varianza E{ej] y var{^} de la ruta al nodo j, la probabili­dad que se realice el nodo j en un tiempo S¿ preestablecido, se calcula con la siguiente fórmula:
f e. – E{e.} S¡ -
en donde
z = Variable aleatoria normal estándar k = Sj – E{e,} Vvar{<?;}

La variable aleatoria normal estándar z tiene media 0 y desviación estándar 1 (véase el apéndice C). La justificación para usar la distribución normal es que es la suma de variables aleatorias independientes. De acuerdo con el teorema del límite central (o ley de la distribución de los errores; véase la sección 12.5.4), e] está distribuida normalmente, en forma aproximada.


Ejemplo
Se tiene el proyecto del ejemplo anterior. Para evitar repetir los cálculos tk ruta crítica, se selec­cionaron los valores de a, m y b en la tabla siguiente, de tal modo que D¡¡ = D¡¡ para toda i y j en el ejemplo anterior.



La media D¡¡ y la varianza VtJ de las distintas actividades se ve en la tabla de abajo. Ob­serve que para una actividad ficticia (a, b, m) = (0, 0, 0), y en consecuencia su media y va­rianza también son iguales a cero



La tabla siguiente muestra la trayectoria más larga del nodo 1 a los distintos nodos, junto con su media y varianza asociados.



Por último, en la tabla siguiente se calcula la probabilidad de que cada nodo se realice en un tiempo S. preestablecido, especificado por el analista.


Metodo Simplex

El Método Simplex publicado por George Dantzig en 1947 consiste en un algoritmo iterativo que secuencialmente a través de iteraciones se va aproximando al óptimo del problema de Programación Lineal en caso de existir esta última.
La primera implementación computacional del Método Simplex es el ano 1952 para un problema de 71 variables y 48 ecuaciones. Su resolución tarda 18 horas. Luego, en 1956, un código llamado RSLP1, implementado en un IBM con 4Kb en RAM, admite la resolución de modelos con 255 restricciones.
El Método Simplex hace uso de la propiedad de que la solución óptima de un problema de Programación Lineal se encuentra en un vértice o frontera del dominio de puntos factibles (esto último en casos muy especiales), por lo cual, la búsqueda secuencial del algoritmo se basa en la evaluación progresiva de estos vértices hasta encontrar el óptimo. Cabe destacar que para aplicar el Método Simplex a un modelo lineal, este debe estar en un formato especial conocido como formato estándar el cual definiremos a continuación.
FORMA ESTÁNDAR DE UN MODELO DE PROGRAMACIÓN LINEAL
Consideremos un modelo de Programación Lineal en su forma estandar, que denotaremos en lo que sigue por:
  • Min          c1x1  + c2x2  + ... + cnxn
  • sa            a11x1 + a12x2 + ... + a1nxn = b1
  •                 a21x1 + a22x2 + ... + a2nxn = b2
  •                 ...          ...                  ...
  •                 am1x1 + am2x2 + ... + amnxn = bm
  •                 xi >=  0,   i = 1, 2, ..., n    y    m <= n
  • Matricialmente escrito como: Min    cTx s.a      Ax = b            x >=  0 No existe pérdida de generalidad en asumir que un modelo de PL viene dado en su forma estándar:
  • EJEMPLO
  • P)            Max        9u + 2v + 5z
  •                 sa            4u + 3v + 6z <=  50
  •                                 u + 2v - 3z >=  8
  •                                2u - 4v + z = 5
  •                                u,v >=  0
  •                                z e IR
  1. Siempre es posible llevar un problema de maximización a uno de minimización. Si f(x) es la función objetivo a maximizar y x* es la solución óptima f(x*) >= f(x), para todo x factible. -f(x*) <= - f(x), para todo x factible. En consecuencia:  x* es también mínimo de  -f(x)
  2. Cada restricción del tipo <= puede ser llevada a una ecuación de igualdad usando una (nueva) variable de holgura no negativa, con coeficiente nulo en la función objetivo.
  3. Cada restricción del tipo >= puede ser llevada a una ecuación de igualdad usando una (nueva) variable de exceso no negativa, con coeficiente nulo en la función objetivo.
  4. Siempre es posible escribir una variable libre de signo como la diferencia de dos variables no negativas.
Considerando la siguiente notación: u = x1, v = x2, z = x3 - x4, s1 = x5 (holgura), s2 = x6 (exceso), el problema P) puede ser escrito en forma equivalente como:
  • Min         - 9x1 - 2x2 - 5x3 + 5x4 + 0x5 + 0x6
  • sa:              4x1 + 3x2 + 6x3 - 6x4 +    x5          = 50
  •                      x1 + 2x2 - 3x3 + 3x4             - x6  =  8
  •                    2x1 - 4x2 +  x3   -   x4                     =  5
  •                    xi >=  0,    i=1,2,3,4,5,6.  
EJEMPLO:
Resolver el siguiente problema de Programación Lineal utilizando el Método Simplex:

  • Max     40*X1 + 60*X2
  • s.a.     2*X1 + 1*X2 <= 70
  •             1*X1 + 1*X2 <= 40
  •             1*X1 + 3*X2 <= 90
  •              X1 >= 0  X2 >= 0
  • Para poder aplicar el Método Simplex, es necesario llevar el modelo a su formato estándar, para lo cual definimos X3, X4, X5 >= 0 como las respectivas variables de holgura para la restricción 1, 2 y 3. De esta forma queda definida la tabla inicial del método de la siguiente forma:
    X1
    X2
    X3
    X4
    X5
    2
    1
    1
    0
    0
    70
    1
    1
    0
    1
    0
    40
    1
    3
    0
    0
    1
    90
    -40
    -60
    0
    0
    0
    0
    En esta situación, las variables de holgura definen una solución básica factible inicial, condición necesaria para la aplicación del método. Luego, se verifican los costos reducidos de las variables no básicas (X1 y X2 en la tabla inicial) y se escoge como variable que entra a la base aquella con el costo reducido "más negativo". En este caso, X2. Luego, para escoger que variable básica deja la base debemos buscar el mínimo cuociente entre el lado derecho y los coeficientes asociados a la variable entrante en cada fila (para aquellos coeficientes > 0 marcados en rojo en la tabla anterior). El mínimo se alcanza en Min {70/1, 40/1, 90/3} = 30 asociado a la tercera fila, el cual corresponde a la variable básica actual X5, en consecuencia, X5 deja la base. En la posición que se alcanza el mínimo cuociente lo llamaremos "Pivote" (marcado con rojo) el cual nos servirá para realizar las respectivas operaciones filas, logrando la siguiente tabla al cabo de una iteración:
X1
X2
X3
X4
X5
5/3
0
1
0
-1/3
40
2/3
0
0
1
-1/3
10
1/3
1
0
0
1/3
30
-20
0
0
0
20
1800
El valor de la función objetivo luego de una iteración ha pasado de 0 a 1.800. Se recomienda al lector hacer una representación gráfica del problema y notar como las soluciones factibles del método corresponden a vértices del dominio de puntos factibles.

La actual tabla no corresponde a la solución óptima del problema P) debido a que existe una variable no básica con costo reducido negativo, por tanto X1 entra a la base. Posteriormente, mediante el criterio del mínimo cuociente calculamos la variable que debe dejar la base: Min {40/(5/3), 10/(2/3), 30/(1/3)} = 15, asociado a la fila 2 (variable básica actual X4), por tanto X4 deja la base. Obtenido lo anterior se aplica una iteración del método:
X1
X2
X3
X4
X5
0
0
1
-5/2
1/2
15
1
0
0
3/2
-1/2
15
0
1
0
-1/2
1/2
25
0
0
0
30
10
2100
Finalmente se alcanza la solución óptima del problema P) y se verifica que los costos reducidos asociados a las variables no básicas (X4 y X5 son mayores o iguals que cero). Notése que la existencia de un costo reducido igual a cero para una variable no básica en esta etapa define un problema con "infinitas soluciones".

La solución alcanzada es X1* = 15, X2* = 25 con V(P*) = 2.100. Adicionalmente, los costos reducidos asociados a las variables no básicas definen el precio sombra asociado a las restricciones 1, 2 y 3, respectivamente, lo cual es equivalente a la obtención del precio sombra mediante el método gráfico. Dejaremos para una posterior presentación, la forma de calcular el intervalo de variación para el lado derecho que permite la validez del precio sombra, utilizando la tabla final del Método Simplex.
MÉTODO SIMPLEX DE 2 FASES
Esta estrategia se utiliza cuando no es inmediata una solución básica factible inicial en las variables originales del modelo.
FASE 1: Se considera un problema auxiliar que resulta de agregar tantas variables auxiliares a las restricciones del problema, de modo de obtener una solución básica factible. Resolver por Simplex un problema que considera como función objetivo la suma de las variables auxiliares. Si el valor óptimo es cero, seguir a la Fase II, en caso contrario, no existe solución factible.
FASE 2: Resolver por Simplex el problema original a partir de la solución básica factible inicial hallada en la Fase I.
  • P)            Max        2X1 + X2
  •                 sa           10X1 + 10X2 <=  9
  •                                10X1 + 5X2  >=  1
  •                                X1, X2 >=  0
Se debe agregar X3 como variable de holgura de la restricción 1, X4 como variable de exceso de la restricción 2 y X5 variable auxiliar para poder comenzar la Fase 1. (Nótese que solo agregando X3 como variable de holgura a la restricción 1 y X4 como variable de exceso a las segunda restricción no se obtiene una solución básica factible inicial, en particular X4<0).
  • F1)            Min        X5
    sa             ...............10X1 + 10X2 + X3              =  9
  •                                 10X1 + 5X2         - X4 + X5 =  1
  •                                 X1, X2, X3, X4, X5 >=  0
La tabla inicial asociada a la Fase I queda en consecuencia definida de la siguiente forma:
X1
X2
X3
X4
X5
10
10
1
0
0
9
10
5
0
-1
1
1
0
0
0
0
1
0
Luego, se debe hacer 0 el costo reducido de X5, obteniendo la siguiente tabla inicial para hacer el uso de Simplex:
X1
X2
X3
X4
X5
10
10
1
0
0
9
10
5
0
-1
1
1
-10
-5
0
1
0
-1
Se escoge X1 como variable que entra a la base al tener el costo reducido más negativo. Posteriormente, mediante el criterio del mínimo cuociente se selecciona la variable que sale de la base: Min {9/10; 1/10} = 1/10, X5 sale de la base:
X1
X2
X3
X4
X5
0
5
1
1
-1
8
1
1/2
0
-1/10
1/10
1/10
0
0
0
0
1
0
Se obtiene la solución óptima de la Fase I, con valor óptimo cero. Luego iniciamos la Fase II del método tomando X1 y X3 como variables básicas iniciales.
FASE 2: Resolver por Simplex el problema original a partir de la solución básica factible inicial hallada en la Fase I.
X1
X2
X3
X4
0
5
1
1
8
1
1/2
0
-1/10
1/10
-2
-1
0
0
0
Hacemos cero los costos reducidos de las variables básicas:
X1
X2
X3
X4
0
5
1
1
8
1
1/2
0
-1/10
1/10
0
0
0
-1/5
1/5
X4 entra a la base. Por el criterio del mínimo cuociente, el pivote se encuentra en la fila 1, por tanto X3 sale de la base:
X1
X2
X3
X4
0
5
1
1
8
1
1
1/10
0
9/10
0
1
1/5
0
9/5
Donde la solución óptima es: X1=9/10    X2=0    Con valor óptimo V(P) = 9/5.