Teoría de Colas – Colas Markovianas – de 1 solo canal

INTRODUCCIÓN

Todos alguna vez hemos hecho una cola, en un banco, supermercado, o un trámite donde muchas personas se congregan y existen definitivamente menos centros de atención que usuarios que desean realizar algún trámite. Las colas son un tópico de la investigación de operaciones que se aborda con la finalidad de optimizar el sistema, esto ocurre por lo siguiente pongámonos  en la situación que tenemos un banco en la cual tenemos un solo cajero en atención, estamos reduciendo costos pues al menos tenemos un cajero, pero no estamos pensando que podríamos perder clientes por los tiempos de espera prolongados, lo cual repercute en el rendimiento de las operaciones, ahora podemos ir al otro extremo en que colocamos muchos cajeros tal que cada cliente sea atendido inmediatamente por un cajero, esto ocasionaría un sobre costo aun cuando el cliente se sienta totalmente satisfecho, pero no resulta conveniente, es por ello que se busca la optimización en el equilibrio del sistema. Entonces tenemos un sistema de colas que puede ser de un solo canal (cajero) o multi-canal:

1canal
Un solo canal
multicanal
Multicanal

COMPONENTES

Tal como se puede observar en los gráficos, se pueden distinguir componentes que conforman el modelo de colas, estos son:

modelo

  • Fuente de Entrada:  Toma especial interés el tamaño de la población que puede requerir servicio en determinado momento, a esta población de clientes potenciales se le conoce como “población de entrada”, esta población puede ser de tamaño finito o infinito; sin embargo, y  por la facilidad de cálculo se suele tomar que es infinito, aun cuando se trate de un problema real que definitivamente tiene un tamaño finito se toma como supuesto que es infinito a menos que se establezca lo contrario. Así como el tamaño se debe de especificar  el patrón estadístico por el cual se generan los clientes, por lo general se asume que estos siguen una distribución de Poisson.
  • Cola: La cola es donde los clientes esperan antes de recibir servicio, se caracteriza por el número máximo de clientes que puede admitir, estas también pueden ser finitas o infinitas, el supuesto de infinito se aplica como un estándar de la mayoría de modelos, incluso cuando en la realidad existe una cota superior.
  • Disciplina de la Cola:  Se refiere al orden en el que sus miembros se seleccionan para recibir el servicio, puede ser: “primero en entrar, primero en salir -(FIFO)“, “último en entrar, primero en salir-(LIFO)” , aleatoria o algún otro procedimiento.
  • Mecanismo de Servicio: Consiste  en uno o más estaciones de servicio denominados servidores, en un modelo de colas siempre se debe especificar el arreglo de las estaciones y el número de los servidores. El tiempo que transcurre desde el inicio del servicio para un cliente hasta su terminación en una estación se llama tiempo de servicio.

NOTACIÓN  Y DISTRIBUCIÓN

En la notación se sigue la notación Kendall que se indica de la siguiente forma:

A/B/C

Donde:

  • A: Especifica el tipo de distribución en la llegada.
  • B: Especifica el proceso de servicio
  • C: Indica el número de servidores

Los códigos empleados son:

  • M: para Markoviano (las tasas de llegada siguen una distribución de Poisson), significando una distribución exponencial para los tiempos de llegada (un banco, cola de supermercado, etc.).
  • D: para unos tiempos deterministas, es decir, los tiempos de llegada no son probabilísticos  y son a intervalos constantes (una planta con un proceso automatizado en línea).
  • G: para una distribución general de los tiempos de llegada, es decir permite cualquier distribución arbitraria.

TERMINOLOGÍA

Se tiende a una terminología aunque cada autor podría diferir en la definición de los términos o símbolos que hace uso:

  • Estado del sistema: número de clientes en el sistema.
  • Longitud de la cola: número de clientes que esperan servicio o estado del sistema menos número de clientes a quiénes se les da el servicio.
  • N(t): número de clientes en el sistema de colas en el tiempo t (t≥0).
  • Pn(t): probabilidad de que exactamente n clientes estén en el sistema en el tiempo t dado el número en el tiempo 0.
  • s: número de servidores (canales de servicio en paralelo) en el sistema de colas.
  • λn: tasa media de llegadas (número esperado de llegadas por unidad de tiempo) de nuevos clientes cuando hay n clientes en el sistema.
  • μn: tasa media de servicio en todo el sistema (número esperado de clientes que completan su servicio por unidad de tiempo).

MEDIDAS DE RENDIMIENTO

Centradas en el cliente:

  • Wq: tiempo promedio de espera, en la cual un cliente llega y es atendido.
  • W: tiempo promedio total del sistema, que incluye el tiempo promedio de espera y el tiempo promedio del servicio.

Cuantitativas sobre el número de clientes:

  • P0: probabilidad de que no haya clientes en el sistema, puede ser empleado cuando se requiera la probabilidad de que haya n elementos en el sistema.

Relacionadas al costo:

  • Costo promedio por unidad de tiempo de operación del sistema
  • Cantidad de estaciones de trabajo necesarias para obtener la mayor efectividad en términos de costos.

RELACIONES ENTRE MEDIDAS DE RENDIMIENTO

El tiempo promedio del sistema, es el tiempo de espera y el tiempo de servicio, sí  “μ” es la cantidad de clientes atendidos por unidad de tiempo, la inversa será el tiempo que demore en atender a un cliente en una unidad de tiempo, entonces:

Tiempo total de un cliente en el sistema:form1

Sea que el tiempo que pasa el cliente en el sistema es W, y λ  por definición es la cantidad de clientes que llegan al sistema por unidad de tiempo, entonces podemos decir que la cantidad de clientes en el sistema  en cualquier tiempo dado será:

L=W*λ

Podemos hacer una analogía, para determinar la cantidad de clientes esperando en cualquier tiempo dado de la siguiente forma:

Cantidad de clientes en cola: Lq=Wq

ANÁLISIS DE COSTOS DEL SISTEMA DE COLAS

Para determinar el costo total debemos de hallar el costo total del personal:

Costo total de personal=(Costoxhoraxservidor) * (Cantidad de personal)

El costo total de los clientes en espera:

Costo total por la espera=(Costoxhoraxcliente_en_cola) * (Cantidad de clientes en cola)

Tal que el costo total es:

Costo total=Costo_total_personal + Costo_total_por_la_espera

ANÁLISIS DE UN SISTEMA DE COLAS DE TIPO (M/M/1)

Las fórmulas de rendimiento por lo general se han derivado a través del uso de las variables λ y μ tal que se llega a la expresión de la intensidad de tráfico o también denominado factor de uso (ρ)  que tiene la siguiente forma:

 Factor de uso: ρ=λ/μ

Si el factor de uso mientras más cerca a 1 significará que el sistema estará más cargado lo cual trae como resultados colas más largas y tiempos de espera más largos. Sí el factor de uso mide la intensidad de clientes en el sistema,  su complemento determina la probabilidad de que no exista clientes en el sistema:

Probabilidad de cero clientes en el sistema: P0=1-ρ

Esta probabilidad indica que un cliente que llega no tendrá que esperar a que se le proporcione servicio ya que la cola estará vacía.

Podemos de similar forma obtener la cantidad de clientes en espera o en la cola en función de ρ o de λ y μ.

Número de clientes en espera:col1

Este último resultado sirven de base para obtener el Wq y W acorde a las fórmulas planteadas líneas arriba.

Si deseamos determinar la probabilidad de que el sistema tenga exactamente “n” cantidad de clientes:

Cantidad n exacta de clientes en el sistema:col2

Esta última ecuación nos permite responder a las preguntas tales como: ¿Cuál es la probabilidad que no haya más de  n clientes en el sistema? , para ello debemos de tomar la suma desde 0 a n de las probabilidades:

col3

Y si en caso la pregunta fuera ¿Cuál es la probabilidad de encontrar hasta n clientes en el sistema?, se tomará el complemento, es decir:

1-Ptotal

EJEMPLOS DE APLICACIÓN

Ejercicio 1

Si la tasa de llegada a una estación de servicio es de 12 unidades por hora y el tiempo de atención por unidad es de 4 minutos siendo además que se pierde por unidad parada la cantidad de $80 por hora y que el costo por día del servicio es de $50, se pide:

  • La probabilidad de encontrar hasta 3 unidades en el sistema.
  • El costo total por día del sistema.
  • Determine si conviene contratar un ayudante por $20 diario si la tasa de atención mejora en 30%.

Resolución:

Tenemos que el tiempo de llegada es de λ: 12 unidades por hora, y la cantidad de unidades por unidad de tiempo es de  μ: 15 unidades por hora ya que cada unidad tarda 4 minutos en un servidor. Nos piden hallar la probabilidad de encontrar hasta 3 unidades en el sistema, para ello usaremos  1-Ptotal,entonces hallamos el total desde i=0 hasta i=n=3 en:

col2

Tenemos que λ/μ=0.8, entonces en P0=(0.8)0(0.2)=0.2, P1=(0.8)1(0.2)=0.16, P2=(0.8)2(0.2)=0.128 y P3=(0.8)3(0.2)=0.1024; la suma total es 0.5904, entonces la probabilidad de encontrar hasta 3 unidades es 1-0.5904=0.4096.

El costo total del sistema, tenemos como datos el costo del día del servicio que es de $50, tomaremos que el día está compuesto de  8 horas laborales, entonces debemos de hallar cuántos clientes se encuentran en cola cada hora; debemos de hallar la cantidad de elementos en cola, sabemos que Lq:

col1

tenemos que la cola cada hora está compuesta por 3.2 unidades, y el costo por unidad por hora es de $80, entonces el costo total de espera por hora es de $256 por hora, pero como son 8 horas laborales tenemos que el costo diario es de $2048, el costo del servicio es de $50 y la cantidad de servidores es de 1, finalmente el costo total será:

Costo total=$50+$2,048=$2098

Ahora debemos de evaluar que sucede si se incluye un ayudante que mejora la tasa de atención es un 30%, esto se traduce en 1.3μ, entonces el nuevo μ será de 19.5 unidades por hora con lo cual debemos de revisar el costo, para ello el nuevo Lq es 0.985 unidades en cola en cada hora, entonces el nuevo costo será:

Costo total=$50+$20+8*80*0.985=$700.154 teniendo como conclusión que sí resulta conveniente.

Ejercicio 2

El departamento de sistemas trata de determinar si alquila una copiadora lenta o rápida. El tiempo de un empleado vale 15 soles la hora, el alquiler de la copiadora lenta cuesta 4 soles la hora y un empleado tarda en promedio 10 minutos en terminar un trabajo, la copiadora rápida cuesta 15 soles la hora en arrendamiento y un empleado tarda un promedio de 6 minutos en terminar un trabajo, al departamento llegan en promedio 4 trabajos de copiado por  hora y el costo de la espera por cada uno de estos trabajos es de 7 soles por  hora. Se pide:

  • La probabilidad de que no haya trabajos en el sistema con copiadora lenta.
  • La probabilidad de que haya al menos dos trabajos en el sistema con copiadora rápida.
  • ¿Cuál es el costo total si se alquila la máquina lenta?
  • ¿Cuál es el costo total si se alquila la máquina rápida?
  • Si el promedio de llegadas de trabajos es de 7 por hora, ¿Cuál es la máquina que deberá utilizar?

Resolución:

Por los datos del problema sabemos que λ=4 trabajos por hora y μ0= 6 trabajos por hora y μ1= 10 trabajos por hora, siendo los sub-índices 0 y 1 para la copiadora lenta y rápida respectivamente, entonces para hallar el primer punto (con la copiadora lenta), debemos de usar:

Probabilidad de cero clientes en el sistema: P0=1-ρ

Entonces ρ=4/6 y P0=1-4/6=1/3=0.333.

Para el segundo punto, nos piden la probabilidad de al menos 2 trabajos para la copiadora rápida, con lo cual debemos de hallar las probabilidades desde 0 a 2, hacer su suma y luego obtener su complemento a 1. Tenemos que λ/μ=0.4 (copiadora rápida), entonces en P0=(0.4)0(0.6)=0.6, P1=(0.4)1(0.6)=0.24 y P2=(0.4)2(0.6)=0.096; la suma total es 0.936, entonces la probabilidad de encontrar hasta 3 unidades es 1-0.936=0.064.

El tercer punto sobre el costo con la copiadora rápida, tomaremos como unidad de tiempo la hora, sabemos que el costo del personal es de S/.15 por hora y el costo por alquiler de copiadora por hora es de S/. 4, con lo cual debemos de hallar cuántos clientes hay en promedio en la cola en la unidad de tiempo, entonces Lq=4/3 y el costo por trabajo por hora es de S/.7, con lo que obtenemos:

Costo total=4+15+(4/3)*7=S/.28.333 

El cuarto punto de forma similar solo que se usará los datos de la copiadora rápida, Lq=4/15, entonces:

Costo total=15+15+(4/15)*7=S/.31.867 

En el quinto punto, si tomamos que λ=7 al resolver Lq con la copiadora lenta nos saldrá un valor negativo, por lo cual queda descartado siendo finalmente la conclusión hacer uso de la copiadora rápida.

Anuncios

Programación Dinámica Determinística – Investigación de Operaciones

Anteriormente:

Programación Dinámica

Ya hemos revisado las bases de la programación dinámica, una técnica empleada dentro de la ingeniería industrial para la optimización de procesos. Ahora vamos revisar la programación dinámica determinística, que se centra en los problemas que el estado de la siguiente etapa está determinado por completo por el estado y la política de la etapa actual. La programación determinística se puede describir por el siguiente gráfica:

pd_13

Siendo esto el único factor diferencial, todo el proceso y características posteriores se cumplen, entonces veamos algunos ejemplos de su aplicación para entender  bien su entendimiento.

AGENCIA DE PUBLICIDAD

Una agencia de publicidad está llevando a cabo una campaña de publicidad de una semana para una tienda local. La agencia ha determinado que es posible que la campaña más efectiva pudiera incluir la colocación de anuncios en cuatro medios. Un periódico diario, un periódico dominical, radio y televisión. Se tiene disponible $ 8,000 para esta campaña y la agencia le gustaría distribuir esa cantidad en incrementos de $1,000 en todos los medios, de manera que se maximice el índice de exposición a la publicidad. Investigaciones llevadas a cabo por la agencia permiten obtener las siguientes estimaciones de la exposición por cada $1,000 de gasto en cada uno de los medios.

pd_14

Determine cuánto debe invertir la agencia en cada uno de los medios para maximizar la exposición de los anuncios.

Resolución

Vemos que no se menciona de forma explícita las etapas, para ello debemos de ponernos a meditar sobre la toma decisión que ha de ocurrir, podemos decir que si empezamos de arriba hacia abajo en la tabla que se ha presentado, podríamos decir que nuestro estado inicial es S1=$8000 y tomaremos una decisión X1 que sería el valor de la inversión en uno de los medios informativos tal que nos lleve al  siguiente estado (el siguiente medio informativo) y en el siguiente estado tendremos S2=8000-X1, y así sucesivamente S3=S2-X2 tal que al final quedemos con 0, observemos la situación determinística que dicta que el estado n+1 está determinado enteramente por el estado anterior y su contribución , ahora bien bajo esto podríamos decir que los medios informativos son las etapas, ya que en ellos se concentran las tomas de decisiones, podemos entonces realizar la siguiente tabla:

pd_15.png

Sí cada etapa es cada medio informativo, observemos lo que sucede en la etapa 1; en la etapa 1 podemos elegir, invertir 0 a 8, no sabemos cuánto pero sabemos que esas son los valores posibles:

pd_16

Si encontramos una razón a ello podemos decir, sea:

  • Sea n el número de estados que es 4.
  • Sn: La cantidad actual para invertir en la etapa n
  • xn: La cantidad actual que se invertirá en la etapa n tal que xn ={0,1,2,3,4,5,6,7,8}
  • Sn+1: La cantidad restante de inversión en la etapa n+1.
  • Csn,sn+1: la contribución inmediata de ir de n a n+1.

Entonces:

Sn+1=Sn-Xn

Con estos datos podemos buscar la relación recursiva; nuestro objetivo es obtener la maximización de exposición en los medios, entonces en cada etapa se ha evaluado y obtenido un gn+1(Sn+1), entonces podemos decir que la maximización de exposición (Gmax) es:

Gmax=C(Sn,Sn+1)+gn+1(Sn+1) equivalente a C(Sn,Sn+1)+gn+1(Sn-Xn)

Entonces en la etapa 1, sea S1=8, si invertimos los 8 el cual es nuestro X1  en la etapa 1 nos quedamos con 0 el cual es nuestro Sn+1.Y la contribución de invertir esos 8 en la etapa 1 es  C(Sn,Sn+1)=82, según dato en tabla.Esto ocurre de forma similar con los otros posibles estados. Bajo esa misma lógica creamos los demás estados y etapas.

pd_17.png

Obtenemos una red de la forma en que se muestra, expliquemos un poco que es lo que está sucediendo:

pd_18

En la primera etapa el esfuerzo de invertir 6 trae como resultado 80 y me quedo con 2 que es el estado inicial para la etapa 2, luego yo puedo decidir invertir esos 2 en la etapa 2 y me quedaría con 0, el resultado de invertir 2 en la segunda etapa es 55, o podría solo invertir 1 y el resultado de invertir 1 es 15 en la segunda etapa o no podría invertir nada, quedándome con 2 y el resultado de no invertir nada es 0, no puedo invertir 3 ya que no poseo dicha cantidad, siguiendo esa misma lógica es que se ha desplegado toda la red. En la última etapa sea lo que quede se va a distribuir, entonces el último estado será de valor 0, con todo esto descrito pasamos a las tablas:

Etapa 4 (Televisión):

pd_19

Etapa 3 (Radio):

pd_20

 

Etapa 2 (Periódico dominical:

pd_21

Etapa 1 (Periódico diario):

Aquí se observa lo sucedido con el nodo de 8 a 2, existe una inversión 6, invertir 6 en la etapa 1 trae una exposición de 80, dejando esos 2 para la siguiente etapa, es ahí donde revisamos cual es la forma más óptima de distribuir 2, que en la siguiente etapa es de 40

pd_22

Finalmente la mayor exposición es de 167 y se logra a través de la distribución de inversión de:

2->3->1->2 o 2->2->1->3

Aquí nos detenemos por el momento, esperando que les haya sido de su agrado.

Programación Dinámica – Investigación de Operaciones

TEORÍA

La programación dinámica es un técnica muy útil para la toma de decisiones de problemas complejos que pueden ser discretizados y secuencializados, proporciona un procedimiento sistemático para determinar la combinación óptima de decisiones; este método no tiene una formulación estándar ya que las ecuaciones que se planteen responden al problema específico.

Esta técnica es muy útil para la reducción el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas y subestructuras óptimas, todo ello haciendo uso del principio de optimalidad:

“Dada una secuencia óptima de decisiones, toda subsecuencia de ella es, a su vez, óptima”

Para la introducción de las características y terminologías de la programación dinámica se creo el problema de la diligencia por parte del profesor Harvey M Wagner:

Un cazafortunas mítico de Missouri que decide ir al oeste a sumergirse en la fiebre del oro que surgió en California a mediados del siglo XIX. Tiene que hacer ek viaje en diligencia a través de territorios sin ley, donde existen serios peligros de ser atacado por merodeadores. A pesar de que su punto de partida y su destino son fijos, tiene muchas opciones en cuanto a qué estados – o territorios – debe elegir como puntos intermedios (tomar en cuenta que el viaje es siempre de izquierda a derecha).

planos1

Para lograr el viaje se requieren de 4 etapas para ir desde el estado A a su destino en el estado J, este cazafortunas es un hombre prudente preocupado por su seguridad. Después de reflexionar un poco ideó una manera bastante ingeniosa para determinar la ruta más segura. Se ofrecen pólizas de seguros de vida a los pasajeros. Como el costo de la póliza de cualquier jornada en la diligencia está basado en una evaluación cuidadosa de la seguridad del recorrida, la ruta más segura debe ser aquella cuya póliza represente el menor costo total“.

El costo de la póliza estándar del viaje en diligencia, del estado i al estado j se denota como:

costo

Creamos las tablas asociadas a cada uno de estos costos tenemos:

pd_1

FORMULACIÓN

Vamos a dividir el problema en etapas, las etapas serán evaluadas en la solución más óptima y se agregarán en el análisis de la siguiente etapa hasta encontrar la solución más óptima general, entonces:

Sean Xn=El destino inmediato de la etapa n (el n-ésimo viaje que se hará en diligencia), tal que la ruta seleccionada final para este problema será:

A->X1->X2->X3->X4, donde X4=J

Sea fn(s,xn) el costo total de la mejor política global para enfrentar las etapas restantes, mientras el cazafortunas se encuentra en el estado “s“, listo para iniciar la etapa n y elige xn como destino inmediato. Dados s y n, sea yn el valor de xn – no necesariamente único – que minimiza fn(s,xn) y gn(s) el valor mínimo correspondiente de fn(s,xn). Entonces:

gn(s)=mínf(s,xn)=f(s,yn)

Donde:

 fn(s,xn)=costo inmediato (etapa n) + costo futuro mínimo (etapas n+1 en adelante)

Representado de la siguiente forma:

pd_3

Entonces nuestro objetivo es encontrar g1(A) y su ruta correspondiente, pero para encontrarlo debemos de resolver de forma sucesiva g4(s), g3(s), g2(s) para cada uno de los estados posibles de s y usar g2(s) para encontrar g1(A).  Entonces es una suerte de ir del fin hacia el inicio obteniendo el costo mínimo (para este caso) en cada una de las etapas.

PROCEDIMIENTO

Recordemos que hemos de ir de adelante hacia atrás, entonces partimos de la última etapa, en nuestro ejemplo esta es la etapa 4, la cual es la última etapa por recorrer, cuando esto sucede su ruta está perfectamente definida, sea por H o por I la ruta se dirige hacia J:

pd_1

Podemos entonces hacer lo siguiente:

pd_2

para el caso de la etapa 4 no existe un g(S) ya que es la última, podemos considerar entonces que este es cero, así que está solo calculado directamente con el costo que representa ir por cada una de las rutas H o I hacia J.

En la etapa 3 se nos representa que ahora se deben de recorrer 2 etapas, aquí debemos de tomar especial atención a lo siguiente; tomemos como base que desde F podemos ir sea hacia H o I:

pd_4

Sabemos por la resolución anterior que el g4(H)=3 y g4(I)=4, entonces si decidimos ir de F->H tendríamos un costo total 6+3=9, ya que estamos haciendo la ruta F->H->J; si hacemos F-I tendríamos un costo total de 3+4=7 siendo menor el costo  y haciendo que g3(F)=7, lo mismo ocurre con E y G, en consecuencia realizando la tabla:

pd_5

En cada una de las celdas hemos hecho la operación descrita para F.

Al resolver la segunda etapa, realizamos los mismos cálculos donde obtenemos la siguiente tabla:

pd_6

Solo podemos observar que el destino inmediato de B y D pueden ser E o F ya que minimizan el valor de “g“, ahora debemos de ocuparnos de la primera etapa:

pd_7

Resuelta la última etapa ya nos es  posible obtener la ruta o rutas óptimas para nuestro problema, tenemos entonces que:

A->C->E->H->J  o  A->D->E->H->J o A->D->F->I->J

Tenemos estas 3 rutas disponibles donde todas tienen el costo mínimo de 11.

CARACTERÍSTICAS

  • El problema se puede dividir por etapas, y cada una de las etapas requiere de una política de decisión.
  • Cada etapa tiene cierto número de estados, los estados son las distintas condiciones posibles en las que se puede encontrar el sistema en cada etapa.
  • El efecto de la política de decisión en cada etapa es transformar el estado actual en un estado asociado con el inicio de la siguiente etapa, entonces podemos decir que un estado es una columna de nodos, cada nodo representa un estado y cada rama una política de decisión.
  • El procedimiento de resolución de la programación dinámica está diseñado para encontrar una política óptima para cada etapa logrando así la política óptima general.
  • Dado el estado actual, una política óptima para las etapas restantes es independiente de la política adoptada en etapas anteriores, por ende la decisión inmediata óptima solo depende del estado actual y no de cómo se llegó ahí, esto es el principio de optimalidad de la programación dinámica.
  • Se dispone de una relación recursiva que identifica la política óptima para la etapa n, dada la política óptima para la etapa n+1. La relación recursiva en su forma difiere de un problema a otro, pero se puede emplear las notaciones que ya se han usado en el problema de la diligencia, tal que finalmente siempre será cuestión de hallar un máximo o un mínimo.
  • Cuando se hace uso de la relación recursiva, el procedimiento de solución comienza al final se mueve hacia atrás etapa por etapa hasta encontrar la política óptima en cada etapa hasta la etapa inicial.

APLICACIONES

La Ruta Crítica

Hallar la ruta crítica con programación dinámica:

pd_8

Resolución

Recordemos que debemos de dividir por etapas nuestra red, sabemos que una etapa es un conjunto nodos o estados y los arcos con su valor con las contribuciones directas; podemos notar que existe la particularidad que el estado 3 está conectado tanto al estado final como a un estado intermedio, este estado 3 en consecuencia estará presente en al menos 2 etapas, si hiciéramos un corte podríamos observar que nuestro problema puede segmentarse en 4 etapas, entonces:

La etapa 4 es la última etapa por recorrer, y el único estado siguiente es 7 y no existe un g5 por lo cual el esfuerzo o tiempo será solo la contribución directa del arco:

 

pd_9

La etapa 3, ahora son dos etapas que debemos de considerar, en este caso en particular, recuerda tomar en cuenta todos los estados previos que te permiten llegar a los estados futuros, para ello observemos el estado 4 que si bien se encuentra en un estado final para la etapa también es parte del estado actual ya que conecta con otros estados finales, se puede observar que por ejemplo en el estado 2 que va hacia el estado 6 y 4 la contribución inmediata de ir de 2 a 6 más el g4(6)  máximo que hasta el momento es 1, igualmente ocurre de 2 a 4, de entre ellos dos elegimos el máximo, ¿Por qué el máximo?, pues porqué estamos buscando la ruta crítica, la ruta crítica está representada por la ruta más larga que me permita ir de 1 a 7.

pd_10

La etapa 2, correspondería ubicar en los estados finales a 1, 2, 4 y 5, pero no tiene sentido colocar a 1 ya que no existe un estado previo para él, entonces solo colocaremos a 2, 4 y 5, hacemos la misma lógica que ya está sustentada en la relación recursiva que aplica para este caso:

pd_11

La etapa 1 y última etapa se consideran las 3 etapas anteriores, entonces tenemos:

pd_12

Hecho todo ello, ¿Cómo hallamos la ruta crítica?, debemos de seleccionar todos los valores máximos, si existe un estado (nodo) que se encuentre en más de una etapa debemos de seleccionar en cual de ellos es el mayor por ejemplo, revisemos la ruta de 1 a 2 y 1 a 3 aparentemente sea de 1 a 3 la ruta más larga; sin embargo, la ruta de 1 a 2 en la etapa 2  es mayor que la ruta de 1 a 3, es por ello que tomamos dicha ruta, luego, en la etapa 2 se obtuvo ese valor del estado 2 ya que provenía del estado 6 y de 6 a 7, entonces nuestra ruta crítica será:

1->2->6->7 longitud de 13

 

Técnica de Evaluación de Proyectos PERT

PERT (Project Evaluation and Review Techniques) es un algoritmo basado en la teoría de redes diseñado para facilitar la planificación de proyectos. El resultado final de este algoritmo será un cronograma para el proyecto, en el cual se podrá conocer la duración total del mismo y la ruta crítica.

ALGORITMO

Reconocer las actividades: Se debe reconocer las actividades y actividades predecesoras y sucesoras, creando una tabla de relaciones, en la tabla de relaciones debe indicarse 3 tipos de tiempos:

  • Tiempo Optimista (a): el cual ocurre cuando la ejecución del proyecto transcurre extremadamente bien.
  • Tiempo más probable (m): el cual ocurre cuando la ejecución del proyecto se realiza en condiciones normales.
  • Tiempo pesimista (b):  el cual ocurre cuando la ejecución del proyecto transcurre extremadamente deficiente.
1426636882
Tabla Ejemplo

Estimación de tiempos y varianza:

Se calcula el tiempo estimado a través de la siguiente fórmula:

1426637180

Además del tiempo estimado debemos de calcular la varianza en cada una de las actividades:

1426637642

Diagramación de la Red y Cálculo de la Red

Ampliamente estudiado en este tópico.

Cálculo de la varianza, desviación estándar y probabilidades de un Proyecto

Información que nos resulta útil es la información respecto a que tan probable es que terminemos el proyecto en una fecha estimada, esto se logra con la siguiente ecuación:

1426640962

  • Sea Z los valores dentro de una tabla de distribución estándar:

tabla_de_distribucic3b3n_normal_estandar

  • X: El tiempo deseado o propuesto.
  • µ: El tiempo de la ruta crítica.
  • σ: Desviación estándar total de la ruta crítica

Obtener la desviación estándar total de la ruta crítica se realiza sumando los valores de la varianza de la ruta crítica y del resultado obtener su raíz cuadrada.

EJEMPLO

Se tiene el siguiente programa:

r11

Se pide:

  • Ruta Crítica
  • Tiempo para un 90% de probabilidad
  • Probabilidad para un cumplimiento entre R+3 y R+1 (R=tiempo de la ruta crítica)

La duración será ya el tiempo estimado, entonces debemos de diseñar la red, quedando de la siguiente forma:

r12

Calculamos la ruta crítica:

r13

Como podemos observar existen 3 rutas críticas, de las cuáles debemos elegir una principal, la ruta crítica principal está dada por la mayor varianza, entonces:

  • Ruta Crítica 1 (C-I-K):0.8+1.7+2.1=4.6
  • Ruta Crítica 2 (A-E-H-K):1.7+0.4+2.1+2.1=6.3
  • Ruta Crítica 3 (A-E-H-J): 1.7+0.4+2.1+0.1=4.3

Entonces la ruta crítica es: A-E-H-K

Luego nos piden el tiempo para un 90% de probabilidad, para ello debemos de revisar la tabla de distribución normal  donde Z seria 1.289 (aquí como se usa).

Debemos de obtener la desviación estándar total de la ruta crítica haciendo la raíz cuadrada de la varianza, entonces la desviación estándar total es: 2.51.

Reemplazando en la fórmula tenemos que la fecha al 90% de probabilidad de termino sería al 31.23 entonces 32.

Finalmente si la fecha propuesta sea R+3 o R+1 debemos ahora obtener la probabilidad, dado que R es ruta crítica en el numerador queda: R+3-R=3 y en el denominador sigue siendo el mismo valor por lo cual obtenemos un Z= 1.1953, buscando el valor en la tabla de distribución normal tenemos que la probabilidad seria del 88.3% aproximadamente. Ahora R+1 lo dejo para ustedes.

 

 

 

La Ruta Crítica (CPM) – Gestión de Proyectos

Según muchas por no decir todas las definiciones de un proyecto, un proyecto es un esfuerzo temporal que tiene como fin generar un producto y/o servicio, para la obtención de este resultado se establece un conjunto de actividades que están relacionadas entre sí a través de precedencia (es decir hacer esto antes que inicie esto), estas actividades tienen como parámetro principal un tiempo requerido para la finalización de esta actividad, cuando se ha realizado la asignación de tiempos, existen actividades que son preponderantes dentro del proyecto, tal que una demora o un adelanto de ellas repercute en la misma medida en la duración total del proyecto e incluso definen la duración del mismo, al conjunto de actividades que determinan la duración del proyecto (incluso más adelante sus costos) se les denomina ruta crítica o CPM de sus siglas en ingles Critical Path Method, la ruta crítica asume actividades determinísticas (lo cual por lo general no sucede en la realidad al menos muy a menudo) es por ello que va acompañado de la técnica PERT (que hablaremos más adelante) que es probabilística.

Representación de una Red

  • Regla 1: Cada actividad está representada por uno, y solo un arco.
  • Regla 2: Cada actividad debe estar identificada por dos nodos terminales distintos
  • Regla 3: Para mantener las relaciones de precedencia  correctas, hay que contestar las siguientes preguntas: ¿Qué actividades preceden inmediatamente a la actividad actual?, ¿ Qué actividades siguen inmediatamente a la actividad actual?, ¿Qué actividades son concurrentes con la actividad actual?

La correcta representación de una red a través de estas reglas puede requerir del uso de actividades ficticias (la cual se representa en línea de rayas y no consume ni tiempo ni recursos) para garantizar la precedencia correcta entre las actividades. Por ejemplo sea:

  • La actividad C se inicia inmediatamente después de que las actividades A y B se han completado.
  • La actividad E puede iniciarse después de que se complete la actividad B.

r2

El gráfico izquierdo muestra la representación incorrecta, que en donde se entiende que la actividad E requiere que A y B estén terminadas, y eso es falso de acuerdo al enunciado ya que E puede continuar solo si B ha sido finalizado, el lado derecho es correcto, pero ha utilizado una actividad ficticia.

Ejemplo de Representación

Un editor firmó un contrato con un autor para publicar un libre de texto. El autor somete a consideración una copia impresa de un archivo de computadora del manuscrito. Las actividades (simplificadas) asociadas con la producción del libro  de texto se resume en la siguiente tabla:

ruta 1.png

Se representa de la siguiente forma:

R1

La regla 2 se cumple, existe un único nodo terminal por actividad, esto se logra añadiendo una activad ficticia a través del nodo 2 a 3.

También nos podemos encontrar respecto a la representación de la red en que el nodo es la actividad en sí misma y la red solo visualiza la precedencia, en la cual de no existir un inicio único se debe crear de forma ficticia, es decir:

r6

Cálculo de los Métodos de la  Ruta Crítica

Recordemos que el resultado final es un cronograma del proyecto, para ello se deben realizar cálculos que nos permitan obtener la siguiente información:

  • Duración total necesaria para completar el proyecto
  • Clasificación de las actividades del proyecto como críticas o no críticas

¿Cuándo una actividad es crítica y cuando no?

Una actividad es crítica si sus tiempos de inicio y terminación están predeterminados (fijos). Una actividad es no crítica si puede ser programada en un espacio de tiempo mayor que su duración, lo que permite tiempos de inicio y terminación flexibles dentro de los límites.

¿Cuál es el impacto de las actividades críticas en un proyecto?

Una demora en el tiempo de inicio de una actividad crítica definitivamente retrasa la terminación  del proyecto, en tanto que una demora en una actividad no crítica puede que no llegue a afectarlo.

Metodología de Cálculo

Para realizar los cálculos necesarios definimos un evento como un punto en el tiempo en el cual se completan las actividades y se inician las subsiguientes. En función de la red, un evento corresponde a un nodo, entonces:

αj=Tiempo de ocurrencia más temprana del evento j.

θj=Tiempo de ocurrencia más tardío del evento j.

Dij=Tiempo de ocurrencia más temprana del evento j.

Todos los tiempos de ocurrencia se miden a partir del inicio del proyecto. el lapso (αj,θj) define el periodo de tiempo durante el cual se programa la actividad (i,j) de duración Dij. Si la actividad (i,j) es crítica entonces:

Dij=θjαj

Sino:

Dij<θjαj

Los cálculos de la ruta crítica implican dos pasos. El paso adelantado, determina los tiempos de ocurrencia más tempranos de los eventos y el paso retrasado que calcula sus tiempos de ocurrencia más tardíos.

Paso Adelantado:

  • Los cálculos inician en el nodo 1 y avanzan recursivamente hacia el nodo n.
  • Establecemos αj=0 para indicar que el proyecto se inicia en el tiempo 0.
  • Dado que los nodos p, q, … y v están vinculados directamente al nodo j por las actividades entrantes (p,j),(q,j) … y (v,j) y que los tiempos de ocurrencia más temprano de los eventos (nodos) p,1,… y v ya se calcularon, entonces el tiempo más temprano de ocurrencia del evento j se calcula como:

αj=máx{αp+Dpj,αq+Dqj,…,αv+Dvj}

El paso adelantado se completa cuando se ha calculado αj  en el nodo n. Por definición, αj es la ruta de más larga duración al nodo j.

Paso Retrasado:

  • Los cálculos se inician en el nodo n y terminan en el nodo 1 y se da luego de haber culminado el paso adelantado.
  • Establecemos θj=αj para indicar que las ocurrencias más tardías del último nodo son iguales a la duración del proyecto.
  • Dado que los nodos p, q, … y v están vinculados directamente al nodo j por las actividades entrantes (j,p),(j,q) … y (j,v) y que los tiempos de ocurrencia más temprano de los eventos (nodos) p,1,… y v ya se calcularon, entonces el tiempo más temprano de ocurrencia del evento j se calcula como:

θj=min{θj-Djp,θj-Djq,…,θjDjv}

El paso retrasado termina con θ1=0 en el nodo 1

Condición para ser Actividad Crítica

Con base en los cálculos anteriores una actividad (i,j) será crítica si satisface 3 condiciones:

θij

θjj

Dijjj

Las 3 condiciones establecen que los tiempos de ocurrencia más tempranos y más tardíos de los nodos finales i y j son iguales y que la duración Dij encaja “perfectamente” en el espacio de tiempo especificado. Una actividad que no satisfaces las 3 condiciones no es crítica.

Por definición: “Las actividades críticas de una red constituyen la ruta más larga que abarca el proyecto desde el inicio hasta la terminación“.

Ejemplo de Cálculo 1

Determine la ruta crítica para la siguiente red de proyecto:

r3

Recordemos que el método se realiza nodo por nodo, entonces:

Paso adelantado :

  • Nodo 1: Tal como menciona el método en el paso 1, establecemos que α1=0 siempre en el nodo 1.
  • Nodo 2: Del nodo 1 al nodo 2 solo existe una forma de llegar, no tenemos de porque hallar un máximo sino solo realizar la acumulación, entonces: α21+D12==0+5=5
  • Nodo 3:Para llegar al nodo 3 se puede llegar desde el nodo 1 y el nodo 2, por lo cual debemos de hallar el máximo  α3=máx{α1+D132+D23}=máx{0+6,5+3}=8
  • Nodo 4: Para llegar al nodo 4 solo podemos hacerlo a través del nodo 2, entonces: α42+D24=5+8=13
  • Nodo 5: Para llegar al nodo 5 lo podemos hacer a través del nodo 4 y 3, recordemos que una actividad ficticia no consume ni tiempo ni recursos por lo que D45=0, de igual forma debemos hacer: α5=máx{α3+D354+D45}=máx{8+2,13+0}=13
  • Nodo 6:Para llegar al nodo 6 podemos hacerlo a través del nodo 3, 4 y 5, entonces debemos de hallar el máximo:

α6=máx{α3+D364+D465+D56}=máx{8+11,13+1,13+12}=25

El 25 hace referencia a que el proyecto puede completarse en 25 días.

Paso retrasado:

Recuerda que el paso retrasado se realiza luego del paso adelantado, esto es debido al paso del método.

  • Nodo 6: Establecemos que θ66=25
  • Nodo 5: En cada nodo debemos de elegir el mínimo recorrido, debes de imaginar que es en el nodo 6 que inicia del proyecto, desde esta perspectiva verás que para llegar al nodo 5 solo se puede hacer desde el nodo 6, por lo tanto el nodo θ56-D56=25-12=13.
  • Nodo 4: Para llegar al nodo 4 podemos hacerlo a través del nodo 5 y 6, por lo tanto debemos de elegir el mínimo, entonces: θ4=min{θ6-D465-D45}=min{25-1,13-0}=13.
  • Nodo 3: Para llegar al nodo 3 podemos hacerlo a través del nodo 5 y 6, por lo tanto debemos de elegir el mínimo, entonces θ3=min{θ6-D365-D35}=min{25-11,13-2}=11
  • Nodo 2: Para llegar al nodo 2 podemos hacerlo a través del nodo 3 y 4, por lo tanto debemos de elegir el mínimo, entonces θ4=min{θ3-D234-D24}=min{11-3,13-8}=5.
  • Nodo 1: Para llegar al nodo 1 podemos hacerlo a través del nodo 3 y 2, por lo tanto debemos de elegir el mínimo, entonces θ1=min{θ3-D132-D12}=min{11-6,5-5}=0.

Hacemos una tabla comparativa para revisar cuales cumplen las 3 condiciones:

Aunque es independiente el orden de la comprobación se puede sugerir que se empiece corroborando la tercera condición:

r4

De las que han cumplido pasamos a verificar si cumplen las demás condiciones:

r5

Vemos que todos los que hemos seleccionado cumplen la condición, entonces podemos decir que la ruta crítica se encuentra en:

(1;2)->(2;4)->(4;5)->(5;6)

Ejemplo de Cálculo 2

Para ello tenemos que hacer algunas precisiones sobre la definición, respecto a los eventos de inicio temprano, podemos decir que una actividad tiene un inicio y un fin, pero este inicio y fin se encuentran pueden ser tempranos o tardíos, es así que tenemos:

Sobre los eventos de inicio temprano:

  • Tiempo de Inicio Temprano (ES por las siglas en inglés de Early Start) que se expresa como:  ES=αj=máx{αp,αq,…,αv}
  • Tiempo de Terminación más temprano (EF por las siglas en inglés de Early Finish) que se expresa como α(máximo obtenido en ES) más la duración de la actividad Dij, entonces: EF=αjmax+Dactividad.

Sobre los eventos de inicio tardío:

  • Tiempo de Terminación más tardío (LF por las siglas en inglés de Late Finish) que se expresa como LF=θj=min{θpq,…,θv}.
  • Tiempo de Inicio más tardío (LS por las siglas en inglés de Late Start) se expresa como θ(mínimo obtenido en LF) menos la duración de la actividad Dij, entonces: LS=θjmin-Dactividad

Entonces podemos reconstruir la red de la siguiente forma:

r7

En cada uno de los nodos vamos hallar y colocar de la siguiente forma:

r8

Para obtener los valores en secuencia en la red, se sigue el método de paso adelantado y paso retrasado, entonces queda de la siguiente forma:

r9.png

Paso Adelantado

  • Lo primero a resolver es el paso adelantado, el paso adelantado está conformado por ES y EF, entonces tenemos el nodo inicio el cual su ES=0 y tiene una duración de 0, por lo cual EF=0.
  • En el nodo B, ingresa el EF de inicio como el ES de B, como la actividad de B dura 6, entonces EF=0+6=6.
  • En el nodo A, de similar forma que en el nodo B.
  • En el nodo C ingresa el EF de A como inicio ES de C, como la actividad C dura 3, entonces EF=8.
  • En el nodo E, se tiene que dos actividades C y B se requieren para iniciar E, entonces debemos de elegir el mayor EF entre C y B el cual es 8 (de la actividad C) y la duración de la actividad E es 2, entonces EF=8+2=10.
  • En el nodo F, ingresa el EF de B como el ES de F, como la actividad de F dura 11, entonces EF=14+11=25.
  • El nodo H debe elegirse el máximo entre E y D, siendo D el máximo, entonces el EF de D ingresa como ES de H y el EF de H es 25 ya que la actividad de H dura 12.
  • En G su ES es el EF de D y el EF de G es 14 ya que la duración de la actividad es 1.

Paso Atrasado

  • El paso atrasado sucede cuando se ha finalizado el paso adelantado, lo primero que se resuelve es el LF, en el nodo fin LF=EF, haciendo ello entonces LF=25, como la actividad dura 0 entonces el LS=LF-0=25-0=25.
  • El nodo H recibe como LF el EF del nodo FIN que es 25, entonces el LS de H es igual a LS=LF-D=25-12=13.
  • El nodo F y G de similar forma que el nodo H.
  • En el nodo D tenemos una doble concurrencia, para ello debemos de elegir el menor EF entre los nodos H y G, siendo H el menor con 13, entonces el LF=13 y el LS=13-8=5.
  • Podemos repetir los mismos pasos con los demás nodos.

La obtención de la ruta crítica se obtiene reconociendo las holguras, una holgura es el tiempo extra en el cual una actividad puede iniciar o finalizar, si esta holgura es cero significa que la actividad en cuestión es crítica, la holgura se divide en Holgura Libre (Hl) y Holgura Total (Ht) y se representan como:

Ht=LF-EF

Hl=LS-ES

Entonces revisando la red tenemos que la ruta crítica está compuesta de las actividades:

A-D-H

 

 

 

 

Método del Flujo máximo

INTRODUCCIÓN

El flujo máximo es un método aplicable para la optimización de rutas entre dos puntos de importancia, esto es aplicable a oleoductos, redes eléctricas o de transmisión de datos, ya que en dichas situaciones se debe determinar el flujo máximo que pasa a través de una red, aspectos más cercanos es la repartición de recursos con el fin de maximizar la eficacia en su uso, por ejemplo si tenemos ingenieros y su repartición en las tareas durante un mes, el flujo máximo es uno de los métodos que se emplea dentro de la ingeniería industrial haciendo uso de los digrafos (grafos dirigidos).

ALGORITMO

Revisemos la metodología del algoritmo obtenido del libro: “Investigación de Operaciones” Novena Edición – Hamdy A.Taha, página – 237.

Este algoritmo  se basa en el hallazgo de rutas de avance con flujo positivo entre los nodos fuente y sumidero. Cada ruta destina una parte de o todas las capacidades de sus arcos al flujo total en la red. Consideramos el arco (i,j) con las capacidades bidireccionales ( de diseño):

1
Capacidad de diseño

Como algunas partes de estas capacidades se destinan al flujo en el arco, los residuos (capacidades no utilizadas, o flujo remanente) del arco se actualizan. Se usa para los residuos la notación:

2
Capacidad Residual

Para un nodo J que recibe flujo del nodo I, anexamos la etiqueta [Aj,i] donde Aj es el flujo del nodo I al nodo J.

  • Paso 1: Para todos los arcos, iguale la capacidad residual a la capacidad de diseño, entonces:

3

Sea:

4

Etiquetando entonces al nodo fuente con:

5

  • Paso 2: Determinar Si, el conjunto de nodos no etiquetados J al que se puede llegar directamente desde I por medio de arcos con residuos positivos ( es decir Cij>0 para todas las J que pertenecen a Si). Si  Si  es diferente al vacío, se continua con el paso 3. De lo contrario, una ruta parcial termina en el nodo i. Continúe con el paso 4.
  • Paso 3: Determine k que pertenece a Si de modo que:

6

Donde j pertenece a Si.

  • Paso 4: (Retroceso) – Si i=1, no es posible avanzar; continúe con el paso 6. De lo contrario, sea r el nodo (en la ruta parcial) que se etiquetó inmediatamente antes del nodo actual i, y elimine i del conjunto de nodos adyacentes a r. Designe i=r, y regrese al paso 2.
  • Paso 5: (Determinación de los residuos) – Defina los nodos de la ruta de avance p-ésima del nodo 1 al nodo n como Np=(1,k1,k2, …,n). Entonces el flujo máximo a lo largo de la ruta se calcula como:

fp=min{a1,ak1,ak2,..,an}

La capacidad residual de cada arco a lo largo de la ruta de avance se reduce en fp en la dirección del flujo, y se incrementa en fp en la dirección inversa; es decir, para los nodos i y j en la ruta, el flujo residual cambia del actual (cij,cji) a:

(a) (cij-fp,cji+fp) si el flujo es de i a j

(b) (cij+fp,cn+fp) si el flujo es de j a i

Restaure los nodos que se eliminaron en el paso 4. Designe i=1, y regrese al paso 2.

Paso 6: (Solución) – dado que se determinaron m rutas de avance, el flujo máximo en la red es:

F=f1+f2+ … + fm

EJEMPLO

Determinemos el flujo máximo de:

flujo_maximo

Iteración 1

Iguale los residuos iniciales  a las capacidades iniciales

Paso 1: Establezca a1 igual a infinito y etiquete el nodo 1 con [∞,-]. Establezca  i=1

 

fm1

Paso 2: Hallamos el conjunto Sde nodos que no están etiquetados y que se pueden unir directamente con i=1, desde el nodo 1 nos podemos conectar a 2, 4 y 3, entonces:

S1={2,3,4} (≠∅)

Paso 3: Determina k ∈ Sde modo que cik=max{cij} tal que  j ∈ S1 . Es decir del conjunto debemos hallar el valor máximo de [ c12,c13,c14]=[10,30,20], entonces  30 es el máximo y en consecuencia k=3 quedando c13=max[c12,c13,c14], etiquetamos el nodo 3 con la etiqueta [30,1] y hacemos i=3 y repetimos el paso 2.

fmi1p3

Paso 2: Ya que nuestro nuevo i=3, entonces debemos de hallar todos los nodos no etiquetados y que se pueden unir al nodo 3 directamente, entonces:

S3={4,5} (≠∅)

Paso 3: Debemos hallar el k en S3 de modo que Cjk sea máximo, y tal como vemos el máximo flujo es 20, entonces k=5.

fmi1p3_2

Paso 5: La ruta de avance se determina a partir de las etiquetas iniciando en el nodo 5 y regresando al nodo 1; es decir (5)->[20,3]->(3)->[30,1]->(1). De este modo N1=[1,3,5] y f1=min{a1,a3,a5}={∞,30,20}=20. Si sabemos que:

(a) (cij-fp,cji+fp) si el flujo es de i a j.

(b) (cij+fp,cn+fp) si el flujo es de j a i.

Las capacidades residuales a lo largo de la ruta N1 son:

(c13,c31)=(30-20,0+20)=(10,20)

(c35,c53)=(20-20,0+20)=(0,20)

Quedando de la siguiente forma:

fmi1p5

Iteración 2

Paso 1: Establezca a1 =∞ y etiquete el nodo 1 con [∞,-]. Establezca  i=1. Idéntico al paso 1 de la iteración 1.

Paso 2: Aún desde el nodo 1 se puede conectar a los demás nodos, entonces el conjunto S1={2,3,4}.

Paso 3: Determina k ∈ Sde modo que cik=max{cij} tal que  j ∈ S1 . Entonces el máximo es c12=20.

fmi2p32

Paso 2: El nuevo i=2 y los que se conectan directamente son: S2={3,5}

Paso 3: El cik máximo es a3=c23=40, entonces k=3 y etiquetamos el nodo 3 con [40,2], y repetimos el Paso 2.

fmi2p33

Paso 2: El nuevo i=3 y los que se conectan directamente son: S3={4,5}.

Paso 3: El cik máximo es a4=c34=10, entonces k=4 y etiquetamos el nodo 4 con [10,3], y repetimos el Paso 2.

fmi2p35

Paso 2: El nuevo i=4 y los que se conectan directamente son: S4={5}.

Paso 3:El cik máximo es a5=c45=20, entonces k=5 y etiquetamos el nodo 5 con [20,4] y se completó una ruta de avance.

fmi2p37.png

Paso 5: La ruta de avance se determina a partir de las etiquetas iniciando en el nodo 5 y regresando al nodo 1; es decir (5)->[20,4]->(4)->[10,3]->(3)->[40,2]->(2)->[20,1]->1. De este modo N1=[1,2,3,4,5] y f2=min{a1,a2,a3,a4,a5}={∞,20,40,10,20}=10. Si sabemos que:

(a) (cij-fp,cji+fp) si el flujo es de i a j.

(b) (cij+fp,cn+fp) si el flujo es de j a i.

Las capacidades residuales a lo largo de la ruta N1 son:

(c12,c21)=(20-10,0+10)=(10,10)

(c23,c32)=(40-10,0+10)=(30,10)

(c34,c43)=(10-10,5+10)=(0,15)

(c45,c54)=(20-10,0+10)=(10,10)

Quedando de la siguiente forma:

fmi2p38.png

Hemos realizado 2 iteraciones al detalle, para entender como procede el algoritmo, ahora seguiremos con las demás iteraciones de forma descriptiva y dejaremos la red resultante al final de cada una de las iteraciones.

Iteración 3

Paso 1: Establezca a1 =∞ y etiquete el nodo 1 con [∞,-]. Establezca  i=1. Idéntico al paso 1 de la iteración 1.

Paso 2: Aún desde el nodo 1 se puede conectar a los demás nodos, entonces el conjunto S1={2,3,4}.

Paso 3: Determina k ∈ Sde modo que cik=max{cij} tal que  j ∈ S1 , vemos que tenemos un empate, entonces los empates se pueden romper de forma arbitraria; sin embargo, se estila elegir el de menor índice, por lo cual elegimos el nodo 2. El máximo es c12=10 y etiquetamos al nodo 2 con [10,1]. Ahora hacemos i=2 y repetimos el paso 2.

Paso 2: Con i=2, entonces S2={3,5},

Paso 3: También existe un empate, tomamos el menor índice en este caso k=3 u a23=30. Etiquetamos el nodo con [30,2]. Se establece i=3, y se repite el paso 2.

Paso 2: Para S3={∅} ya que c34=0 y c35=0, esto nos obliga ir al paso 4 para retroceder.

Paso 4: La etiqueta [30,2] que está en el nodo 3 se elimina y r=2 es decir nos dirigimos hacia el nodo anterior y se repite el paso 2 sin considerar ya el nodo 3.

Paso 2: S2={5} (se ve que se eliminó al nodo 3).

Paso 3: Como S2 solo tiene un elemento, entonces k=5, c25=30, se etiqueta el nodo 5 con [30,2]. Se logra una ruta de avance y se pasa al paso 5.

Paso 5: N3=[1,2,5] y  f3=min{∞,10,30)=10. Los residuos de la ruta son:

(c12,c21)=(10-10,10+10)=(0,20)

(c25,c52)=(30-10,0+10)=(20,10)

Quedando de la siguiente forma:

fmi3p1.png

Iteración 4

Paso 1: Establezca a1 =∞ y etiquete el nodo 1 con [∞,-]. Establezca  i=1. Idéntico al paso 1 de la iteración 1.

Paso 2: Aún desde el nodo 1 se puede conectar a los demás nodos, entonces el conjunto S1={3,4}.

Paso 3: Determina k ∈ Sde modo que cik=max{cij} tal que  j ∈ S1 , vemos que tenemos un empate, entonces los empates se pueden romper de forma arbitraria; sin embargo, se estila elegir el de menor índice, por lo cual elegimos el nodo 3. El máximo es c13=10 y etiquetamos al nodo 3 con [10,1]. Ahora hacemos i=3 y repetimos el paso 2.

Paso 2: Con i=3, entonces S3={2}.

Paso 3: Como S3 solo tiene un elemento, entonces k=2, c32=10, se etiqueta el nodo 2 con [10,3]. Se logra una ruta de avance y se pasa al paso 2.

Paso 2: Con i=2, entonces S2={5}.

Paso 3: Como S2 solo tiene un elemento, entonces k=5, c25=20, se etiqueta el nodo 5 con [20,2]. Se obtiene una ruta de avance y se pasa al paso 5.

Paso 5: N3=[1,3,2,5] y  f4=min{∞,10,20)=10. Los residuos de la ruta son:

(c13,c31)=(10-10,20+10)=(0,30)

(c32,c23)=(10-10,30+10)=(0,40)

(c25,c52)=(20-10,10+10)=(10,20)

Quedando de la siguiente forma:

fmi4p1

Iteración 5

Paso 1: Establezca a1 =∞ y etiquete el nodo 1 con [∞,-]. Establezca  i=1. Idéntico al paso 1 de la iteración 1.

Paso 2: Aún  nos queda una ruta de avance desde el nodo 1 al nodo 4, entonces el conjunto S1={4}.

Paso 3: Determina k ∈ Sde modo que cik=max{cij} tal que  j ∈ S1 , al ser un único nodo entonces k=4, c14=10, etiquetamos el nodo 4 con [10,1] y pasamos al paso 2.

Paso 2: Desde el nodo 4 tenemos S4={3,5}

Paso 3: el cik máximo es k=3 y etiquetamos el nodo 3 con [15,4], establecemos i=3 y pasamos al nodo 2.

Paso 2: Para S3={∅} ya que c35=0 y c32=0, esto nos obliga ir al paso 4 para retroceder.

Paso 4: La etiqueta [15,4] que está en el nodo 3 se elimina y r=4 es decir nos dirigimos hacia el nodo anterior y se repite el paso 2 sin considerar ya el nodo 3.

Paso 2: Desde el nodo 4 tenemos S4={5} (ya no contamos con el nodo 3), entonces i=5.

Paso 3: El máximo es C45=10, y agregamos la etiqueta en le nodo 5 de [10,4], hemos obtenido una ruta de avance y pasamos al paso 5.

Paso 5: N4=[1,4,5] y  f5=min{∞,15,10)=10. Los residuos de la ruta son:

(c14,c41)=(10-10,0+10)=(0,10)

(c45,c54)=(10-10,10+10)=(0,20)

Quedando de la siguiente forma:

fmi5p1.png

Iteración 6

Todos los arcos que parten del nodo 1 tienen residuos cero. Por lo tanto, no son posibles más rutas de avance. Se procede al paso 6 para la resolución:

Paso 6: El flujo máximo (F) será: F=f1+f2+ … + f5=20+10+10+10+10=60 unidades.

 

Desarrollo de una Aplicación en Python para resolución de Problemas de Programación Lineal – caso Transportes parte 2

Anteriormente:

Hola, en esta ocasión volvemos a la resolución de problemas bajo la programación lineal a través de python, pero en este post trataremos de un caso específico que son los problemas de transportes. El problema del transporte es un problema de redes especial que se  basa en el esquema  de que existe la necesidad de llevar unidades de un punto específico llamados fuente u origen hacia otro punto específico llamado destino tal que existe un costo de envío de la fuente hacia el destino , el objetivo principal de un modelo de transporte es la satisfacción de todos los requerimientos establecidos por los destinos con el menor costo posible. Un problema de transporte tiene un contexto de aplicación muy amplio como inventarios o asignación de elementos; este tipo de problemas (su estructura) permite la creación de múltiples alternativas de solución como estructuras de asignación o métodos heurísticos como Vogel, Esquina Noroeste o Mínimos Costos. Un problema de transporte se puede representar de la siguiente forma:

transporte1

Supuestos

  • Haz leído al menos la parte 1.
  • No te es necesario leer la parte 1 ya que tienes conocimientos en python y la resolución de problemas de programación lineal.
  • Nuestro caso abordará la situación más básica, es decir: la sumatoria de cantidades disponibles del origen es igual a la sumatoria de requerimientos de los destinos.

Empecemos

Enunciado

Tenemos que enviar cajas de cervezas de dos cervecerías a cinco bares de acuerdo al siguiente gráfico:

Trans_problem

Así también el área de finanzas nos informa que el costo de transporte por caja de cada origen hacia cada destino es:

t1

Se nos pide hallar el costo mínimo que satisfaga todas las necesidades de los bares.

Modelado

Sabemos que un problema de programación lineal tiene:

  • Variables de decisión
  • Una función objetivo
  • Un conjunto de restricciones de no negatividad de las variables de decisión

Nuestras variables de decisión podemos hacerlas de la siguiente forma:

Xij=la cantidad enviada desde el origen i al destino j

Sea Cij el costo de envío desde el origen i al destino j y sea Xij lo representamos de la siguiente forma:

transporte

Podemos decir entonces que la función objetivo se puede representar de la siguiente forma:

t3

Entonces de forma general si tuviéramos “n” orígenes y “m” destinos:

t2

Las restricciones del problema se basan en lo siguiente, la suma total de cantidades enviadas del origen “i” a los destinos “j” no pueden exceder la cantidad máxima del mismo origen “i“, entonces sea ai la cantidad máxima que puede despachar una cervecería:

t4

Así también las cantidades recibidas desde los orígenes “i” no pueden exceder la cantidad máxima requerida del destino “j“, entonces sea bj la cantidad requerida por un bar:

t5

Modelado lo llevamos a Python

Recuerda que el detalle de cada uno de los métodos e instancias de clase se encuentra en la parte 1

Creamos un fichero, abrimos la consola (en mi caso la consola que viene en Visual Studio Code) e instalamos pulp:

pip install pulp

En el fichero debemos de importar la librería (se estila la importación en la parte superior del fichero):

from pulp import *

Creamos una instancia de la clase LpProblem :

problema=pulp.LpProblem("Problema de Distribución de Cervezas",pulp.LpMinimize)

Ahora debemos de generar las estructuras necesarias para solucionar nuestro problema, para ello vamos a crear una lista con las etiquetas de los orígenes y un diccionario, primero vamos con la oferta máxima de cada una de los orígenes:

cervecerías=["Cervecería A","Cervecería B"]
oferta={"Cervecería A":1000,"Cervecería B":4000}

Recuerda que tanto los elementos de la lista y la clave del diccionario que estamos creando deben ser idénticos, ya que cuando se realicen las iteraciones y hubiese algún valor diferente podríamos sufrir de datos perdidos y todo se echaría perder. El procedimiento anterior lo realizamos con la demanda de cada uno de los bares:

bares=["Bar 1","Bar 2","Bar 3","Bar 4","Bar 5"]
demanda={"Bar 1":500,"Bar 2":900,"Bar 3":1800,"Bar 4":200,"Bar 5":700}

Por último creamos una lista de los costos, esta lista será una lista de listas, donde cada lista que es elemento será los costos asociados de llevar del origen i al destino j:

costos=[[2,4,5,2,1],[3,1,3,2,3]]

Ahora debemos de crear un diccionario en que se asocien origen destino y tenga como elementos los costos correspondientes tal como la matriz del enunciado:

t1

Entonces hablamos de que cada valor está asociado a un destino y un destino a un origen y que se exprese a través de un diccionario que en nuestro caso es de 2 dimensiones (ver más ejemplos), operativamente el resultado que esperamos es el siguiente:

costos={
         "Cervecería A":{"Bar 1":2,"Bar 2":4,"Bar 3":5,"Bar 4":2,"Bar 5":1},
         "Cervecería B":{"Bar 1":3,"Bar 2":1,"Bar 3":3,"Bar 4":2,"Bar 5":3}
        }

Para ello pulp tiene una función que es makeDict():

makeDict(headers,array,default=None)

Los headers son una lista que contiene como elementos las listas de las etiquetas, array es la lista de valores expresado en las dimensiones que tendrá la matriz resultante (2×5 en nuestro caso), entonces generamos el diccionario bidimensional costos:

costos=pulp.makeDict([cervecerias,bares],costos,0)

Ahora necesitamos crear una lista con todas las rutas posibles y que se expresen como pares ordenados, esto lo podemos hacer con las tuplas, el resultado esperado es:

[("Cervecería A","Bar 1"),("Cervecería A","Bar 2")... ("Cervecería B",Bar 5")]

Para ello vamos a crear una lista por comprensión, y que asignaremos a una variable rutas:

rutas=[(c,b) for c in cervecerias for b in bares]

Al igual que tenemos una matriz de costos entre el origen y el destino debemos de crear las variables de las cantidades:

t6

Como se tratan de variables debemos de usar la clase LpVariable y su método dicts,

dicts(nombre_diccionario,indexs_tuplas,límite_inferior=None,Límite_superior=None,cat=categoria_Integer_Continuous

Aquí debemos de hacer una observación, el constructor del método admite una lista o una tupla de listas dentro del parámetro indexs, la cantidad de elementos en la tupla determina las dimensiones de la matriz, así también el límite inferior es cero por la restricción de no negatividad; sin embargo, el límite superior no está acotado y por ello usaremos None, finalmente tratamos con elementos enteros por lo que su categoría es pulp.LpInteger, entonces:

cantidad_variable=pulp.LpVariable.dicts("cantidadxruta",(cervecerias,bares),0,None,pulp.LpInteger

El resultado esperado debe ser:

cantidad_variables={
              'Cervecería A': {'Bar 1': cantidadxruta_Cervecería_A_Bar_1, 'Bar 2': cantidadxruta_Cervecería_A_Bar_2, 'Bar 3': cantidadxruta_Cervecería_A_Bar_3, 'Bar 4': cantidadxruta_Cervecería_A_Bar_4, 'Bar 5': cantidadxruta_Cervecería_A_Bar_5}, 
              'Cervecería B': {'Bar 1': cantidadxruta_B_Bar_1, 'Bar 2': cantidadxruta_Cervecería_B_Bar_2, 'Bar 3': cantidadxruta_Cervecería_B_Bar_3, 'Bar 4': cantidadxruta_Cervecería_B_Bar_4, 'Bar 5': cantidadxruta_Cervecería_B_Bar_5}
                   }

Con todo esto ya tenemos listo todas las estructuras necesarias para la resolución del problema, entonces lo primero es introducir la función objetivo, tal como observamos la función objetivo se expresa como:

t2

Y debemos de expresarlo de la siguiente forma:

problema+=lpSum(costos[c][b]*[cantidad_variables[c][b] for (c,b) in rutas),"Función Objetivo"

recordemos que problema es una instancia de LpProblem, el cual es el encargado de almacenar la función objetivo y las restricciones, esto lo logramos a través de lpSum, ahora vamos a entender que es lo que hemos hecho, supongamos que estamos buscando la siguiente expresión:

t7

Que significa: “el costo de la cervecería A hacia el Bar 1 multiplicado por la cantidad enviada desde la cervecería A hacia el Bar 1“, esta expresión la tenemos configurada en los diccionarios de costos y cantidad_variables respectivamente y como necesitamos discriminar por ruta, esta se encuentra almacenada en el par ordenado (tupla) de la lista rutas.

Explicado a ello ahora procedemos de forma similar con las restricciones y que también tenemos que agregar a nuestra instancia problema:

Primero abordaremos las restricciones de la oferta, para la oferta tenemos lo siguiente:

t4

Y lo expresamos de la siguiente forma:

for c in cervecerias:
  problema+=lpSum([cantidad_variables[c][b] for b in bares])<=oferta[c],"Restricciones de oferta"

La cantidad de ecuaciones  para la restricción de la oferta es la cantidad de elementos que existen en la lista de cervecerías, así que:

c=Ai tal que i=1,2,3 … n

Queremos obtener:

t8_oferta

  • X11=cantidad enviada de la cervecería A hacia el bar 1
  • X21=cantidad enviada de la cervecería B hacia el bar 1

El que se encuentra en constante iteración son los bares y que dicha suma no puede exceder al valor de la cervecería origen.

De similar forma ocurre con la demanda:

t5

for b in bares:
  problema+=lpSum([cantidad_variables[c][b] for c in cervecerias])<=demanda[b],"Restricciones de demanda

En la demanda la suma de envíos desde las cervecerías no puede exceder a la demanda solicitada por cada bar.

 

Hecho todo esto ahora podemos resolver el problema, para ello ya de casi forma automática (se encuentra explicado de forma detallada en la parte 1), debemos de escribir el archivo Lp:

problema.writeLp("ProblemaTransporte.lp")

Lo resolvemos:

problema.solve()

Imprimimos el estado del problema, para saber si pudo ser resuelto o no:

print("Status: {}".format(pulp.LpStatus[problema.status]))

Luego imprimimos los resultados por variable para conocer el detalle del estado:

for v in problema.variables():
  print("{0:}={1:}".format(v.name,v.varValue))

Finalmente imprimimos el resultado del costo optimizado:

print("Costo optimizado = {}".format(problema.objective.value()))

t9_resultado

No te preocupes si el nombre de la variable es distinto:

ruta_Cervecería_A_Bar_1==cantidadxruta_Cervecería_A_Bar_1

En un siguiente post vamos a crear una interfaz que nos permite colocar n orígenes y m destinos, así nuestra aplicación estará apta para cualquier tipo de problema donde existe un origen y un destino, saludos.