Objetivo

Métodos cuantitativos para la toma de decisiones
Métodos Cuantitativos para la
Toma de Decisiones
Integradora 4.
Maximizando Recursos
con Programación Lineal
Objetivo
M A E S T R Í A
Al finalizar la actividad integradora, serás capaz de:
•
•
•
Determinar un plan de transporte de mercancías de
varias fuentes a varios destinos.
Usar el modelo de asignación para seleccionar la
distribución óptima.
Construir un criterio general de la teoría de líneas
de espera.
Derechos reservados © TecMilenio, A.C.
1
Métodos cuantitativos para la toma de decisiones
Introducción
M A E S T R Í A
La programación lineal puede ser
vista como una parte del gran
desarrollo revolucionario que ha
dado al hombre la habilidad de
optimizar o maximizar recursos
hoy en día. Algo que le ha
ayudado a trazar un camino de
toma de decisiones con el fin de
mejorar objetivos trazados por las empresas. Esto dentro de
un ámbito práctico en situaciones de gran complejidad
complejidad.
Uno de los objetivos de este módulo es mostrar el vasto
número de problemas de la vida real que pueden ser
abordados mediante las técnicas de programación lineal.
Introducción
M A E S T R Í A
Las herramientas que plantea la programación lineal son
los modelos que formulan problemas del mundo real en
términos matemáticos detallados
detallados, los algoritmos que
resuelven los modelos, y el software para ejecutar los
algoritmos por medio de computadoras, basados en teoría
matemática.
Estudiaremos aplicaciones de los métodos más famosos
de la programación lineal:
• El modelo de transporte.
• El modelo de asignación.
• Teoría de filas de espera.
Derechos reservados © TecMilenio, A.C.
2
Métodos cuantitativos para la toma de decisiones
M A E S T R Í A
Introducción
Veremos las aplicaciones en
áreas diversas como dirección de
la producción, investigación de
mercados, mercadotecnia,
logística, finanzas, etc. En todos
estos ámbitos, la programación
lineal se revela como una
herramienta insustituible en la
o a de dec
decisiones.
s o es
toma
Modelo de Transporte
•
En temas anteriores, hablamos
sobre problemas de programación
lineal en este tema se presenta
lineal,
otro tipo de problema de
programación lineal al cual le
llamamos problema de
transporte.
•
Patines “Niño feliz” se dedica a la
fabricación de patinetas en
diferentes plantas de la ciudad
(orígenes) y las distribuye a
diferentes jugueterías de la misma
ciudad (destinos), las cuales tienen
una capacidad finita.
M A E S T R Í A
Derechos reservados © TecMilenio, A.C.
3
Métodos cuantitativos para la toma de decisiones
Modelo de Transporte
M A E S T R Í A
Formulación
• Supongamos que se tienen tres plantas para producir
patinetas A1, A2 y A3, las cuales son distribuidas a
cuatro diferentes jugueterías B1, B2, B3 y B4.
•
Supongamos que el número de unidades producidas en
las plantas A1, A2 y A3 son a1, a2 y a3 respectivamente,
la demanda de las jugueterías son b1, b2, b3 y b4.
•
Por lo que se asume la siguiente condición:
a 1 + a 2 + a 3 = b1 + b2 + b3 + b4
Modelo de Transporte
M A E S T R Í A
•
Supongamos que el costo de transportar una patineta
de A1 a B1 es c11, el de transportar de A1 a B2 es c12 y
así respectivamente para todos destinos y orígenes
orígenes.
•
Las unidades a1 que se distribuyen de A1 a B1 se les
llamará x12, las que se envíen de A3 a B1 x31 y así
respectivamente.
•
Los supuestos anteriormente planteados se representan
de manera completa en la siguiente figura:
Derechos reservados © TecMilenio, A.C.
4
Métodos cuantitativos para la toma de decisiones
Modelo de Transporte
M A E S T R Í A
De esta figura podemos observar que el número total de
unidades a distribuir de la planta A1 a todas las
jugueterías B1, B2, B3 y B4 debe ser igual a a1, es decir:
x11+x12+x13+x14 = a1
Modelo de Transporte
M A E S T R Í A
De igual manera para A2 y A3, la suma total de unidades
distribuidas debe ser a2 y a3 respectivamente:
• x21 + x22 + x23 + x24 = a2
• x31 + x32 + x33 + x34 = a3
Por otro lado, también se debe considerar que el total de
unidades entregadas a cada una de las jugueterías debe
ser igual a b1, b2 y b3, es decir:
• x11 + x21 + x31 = b1
• x12 + x22 + x32 = b2
• x13 + x23 + x33 = b3
• x14 + x24 + x34 = b4
Derechos reservados © TecMilenio, A.C.
5
Métodos cuantitativos para la toma de decisiones
M A E S T R Í A
Modelo de Transporte
Usando la información anterior, se puede construir la
siguiente tabla:
Por lo que el costo de transportación de Ai = (i = 1, 2, 3) a
Bj = (j = 1, 2, 3, 4) es igual a
Costo de transporta ción = ∑ c ij x ij
i, j
Modelo de Transporte
M A E S T R Í A
Para poder determinar este costo, se presenta la siguiente
tabla:
Nota: todos los costos están en cientos.
Derechos reservados © TecMilenio, A.C.
6
Métodos cuantitativos para la toma de decisiones
Modelo de Transporte
M A E S T R Í A
Para obtener la solución factible inicial se pueden usar los
siguientes métodos:
Regla de la esquina noreste.
Método de menor costo.
Método de aproximación Vogel.
Modelo de Asignación
•
•
•
M A E S T R Í A
El problema de asignación es una forma especial de
otro problema de optimización conocido como el
problema de transporte,
transporte el cual vimos en el tema
anterior.
El problema de asignación es uno de los problemas
fundamentales de optimización combinatoria en la rama
de la Programación Lineal o investigación de
operaciones en las matemáticas.
En su forma más general, el problema implica lo
siguiente:
i i t h
hay un número
ú
d
de personas y un número
ú
d
de
tareas. Cualquier persona puede ser asignada a hacer
cualquier tarea, para lo cual hay algunos costos que
pueden variar dependiendo de la asignación.
Derechos reservados © TecMilenio, A.C.
7
Métodos cuantitativos para la toma de decisiones
Modelo de Asignación
M A E S T R Í A
•
El objetivo más frecuente es minimizar los costos totales
o tiempo total de realizar las tareas en cuestión. Una
importante característica de los problemas de
asignación es que sólo se asigna un trabajo o trabajador
a una máquina o proyecto.
•
Este método o modelo es muy útil debido a que los
gerentes de empresas normalmente se topan con este
tipo de problemas, hay que minimizar los costos
mediante
di t lla asignación
i
ió d
de personall para realizar
li
un
determinado número de tareas.
Modelo de Asignación
M A E S T R Í A
El problema de asignación es un tipo especial del
problema de transporte, en el cual:
•
•
•
•
El número de productos o suministros y nodos de
demanda son iguales.
El suministro de cada nodo de suministro es 1.
Cada nodo de demanda tiene una demanda de 1.
La solución requerida
q
es q
que todos sean enteros.
Derechos reservados © TecMilenio, A.C.
8
Métodos cuantitativos para la toma de decisiones
Modelo de Asignación
M A E S T R Í A
El objetivo general es encontrar la asignación óptima de
máquinas (o trabajadores) para realizar tareas asignando
un agente sólo una vez y asegurándonos que todas las
tareas son completadas. El objetivo podría ser minimizar el
tiempo total para completar el conjunto de tareas, o
maximizar la satisfacción total del grupo, o minimizar el
costo de la asignación.
Esto está sujeto a los siguientes requerimientos:
• Cada máquina es asignada sólo a una tarea.
• Cada tarea es asignada únicamente a una
máquina.
Modelo de Asignación
M A E S T R Í A
Para entender más claramente este concepto
analizaremos el siguiente ejemplo.
Supongamos que un sitio de taxis tiene
tres vehículos disponibles (agentes), y
tiene tres clientes (tareas) que desean
ser recogidos lo más pronto posible.
El sitio se anuncia en el radio como el
más rápido de la ciudad
ciudad, así que por
cada taxi el “costo” de recoger a algún
cliente en particular dependerá del
tiempo tomado por el taxi en llegar por
el cliente.
Derechos reservados © TecMilenio, A.C.
9
Métodos cuantitativos para la toma de decisiones
Modelo de Asignación
M A E S T R Í A
La solución al problema de asignación será cualquier
combinación de taxis y clientes que resulte en el costo
menor.
menor
Sin embargo, el problema de asignación puede ser
planteado un poco más fácil de lo que parece. En este
ejemplo, supongamos que tenemos cuatro vehículos
disponibles, pero los mismos tres clientes.
Modelo de Asignación
M A E S T R Í A
Entonces podríamos inventar una cuarta tarea, que
podemos llamarla “sentado sin hacer nada”, con un costo
de 0 por el taxi asignado a hacer esa tarea
tarea.
El problema puede ser entonces ser resuelto en la forma
tradicional y dar también la mejor solución al problema.
Pueden hacer más combinaciones con este tipo de
problemas, por ejemplo que en lugar de un cliente sea un
grupo de personas en un taxi
taxi, o podemos cambiar el
problema a que la mejor solución sea maximizar las
ganancias en lugar de minimizar los costos.
Derechos reservados © TecMilenio, A.C.
10
Métodos cuantitativos para la toma de decisiones
Teoría de Líneas de Espera
M A E S T R Í A
¿Recuerdas la última vez en que tuviste que esperar en la
fila del súper para ser atendido? ¿La última vez que
estuviste formado en el banco para hacer algún depósito?
¿O para ser atendido en tu restaurant favorito de comida
rápida? En estos y otros tipos casos el tiempo que pasas
en espera, mientras sea menos mejor.
Para este tipo de situaciones existe una rama de la
Investigación de Operaciones, llamada ‘Modelo de filas
d espera’,’ lla cuall sirve
de
i
d
de ayuda
d a llos ttomadores
d
d
de
decisiones a entender y mejorar los modelos de filas de
espera.
Teoría de Líneas de Espera
M A E S T R Í A
Es importante destacar que los modelos de filas de espera
se basan en la Teoría de Colas, la cual tuvo su inicio a
principios del siglo pasado por el ingeniero danés llamado
A. K. Erlang, debido a la necesidad de entender el
comportamiento de las personas al hacer una llamada
telefónica y esperar a que fuera contestada por una
operadora.
Al principio sólo fue usada en el ramo de la telefonía pero
con ell ti
tiempo se encontró
t ó que ttambién
bié podía
dí aplicarse
li
en
otras ramas en donde se involucra a una entidad o
persona esperando a ser atendida.
Derechos reservados © TecMilenio, A.C.
11
Métodos cuantitativos para la toma de decisiones
Características de los modelos de líneas
M A E de
S T R Í A
espera
Antes de entrar de lleno al estudio de los modelos de filas
de espera, es importante que entendamos las
características principales de los mismos
mismos, por lo que a
continuación te las presentamos:
•
Características de llegada
Todos los sistemas de líneas de espera cuentan con
llegadas las cuales tienen un tamaño, patrón de llegadas y
p
comportamiento.
Características de los modelos de líneas
M A E de
S T R Í A
espera
•
Tamaño: se refiere a la fuente de llegadas al sistema, la
cual pueden ser infinitas o finitas, es decir, ilimitadas y
limitadas.
limitadas
Por ejemplo, se dice que las llegadas son ilimitadas
cuando la población de estudio es muy grande, tales
como compradores en un supermercado, clientes que
esperan en la fila del banco o automóviles que llegan a
una caseta de cobro.
Se dice que una fuente es limitada cuando se conoce el
número de unidades potenciales a entrar al sistema.
Derechos reservados © TecMilenio, A.C.
12
Métodos cuantitativos para la toma de decisiones
Características de los modelos de líneas
M A E de
S T R Í A
espera
•
Patrón de llegadas: frecuencia con la que las unidades
llegan al sistema, las cuales se les considera aleatorias
debido a que son independientes una de otra y se
representan a manera de distribución de probabilidad.
•
Las llegadas que se presentan en este tema siempre
serán descritas por la distribución de probabilidad
Poisson. La cual se representa de la siguiente manera:
Características de la línea de espera
M A E S T R Í A
Todos los sistemas de líneas de espera cuentan con línea
o líneas de espera, las cuales tienen una longitud y
comportamiento en la cola
cola.
• Longitud:
•
•
•
Puede ser limitada o ilimitada.
Se dice que la longitud de la línea de espera es limitada
cuando por restricciones de espacio o legales no puede
aumentar a un tamaño infinito.
infinito
Se dice que la longitud de la línea de espera es ilimitada
cuando no existe ninguna restricción para tener un
tamaño infinito.
Derechos reservados © TecMilenio, A.C.
13
Métodos cuantitativos para la toma de decisiones
Características de la línea de espera
M A E S T R Í A
•
Comportamiento en la cola: se refiere a la manera en
que las entidades o unidades en la línea de espera
serán atendidas
atendidas, las cuales pueden ser de modo PEPS
(primeras entradas, primeras salidas) o por prioridades.
•
Se dice que un sistema de líneas de espera tiene
comportamiento de prioridades cuando dependiendo el
criterio que haya establecido la empresa se decida
quien deberá ser atendido primero sin importar el orden
d llllegada.
de
d
A E S T R Í A
Características de las instalaciones deM servicio
Todos los sistemas de líneas de espera cuentan con
instalaciones de servicio o servidores, los cuales
atenderán a las entidades o unidades en la línea o líneas
de espera. Cada instalación de servicio o servidor tienen
una configuración y distribución de tiempo de servicio.
• Configuración: consiste en identificar la cantidad de
servidores y el número de etapas o fases de servicio por
las que tiene que pasar una entidad.
Derechos reservados © TecMilenio, A.C.
14
Métodos cuantitativos para la toma de decisiones
A E S T R Í A
Características de las instalaciones deM servicio
Como ya se mencionó previamente, en este tema se
analizarán las configuraciones de un sólo canal y
multicanal (ambos con una sola fase)
fase). La configuración de
los mismos se representa gráficamente de la siguiente
manera:
Sistema de un sólo canal con una sola fase
Servidor
Llegadas
línea de espera
Salida
después del servicio
M A E S T R Í A
Teoría de Líneas de Espera
Sistema multicanal con una sola fase
Servidor
Salida
después del servicio
Llegadas
línea de espera
Servidor
Derechos reservados © TecMilenio, A.C.
15
Métodos cuantitativos para la toma de decisiones
Teoría de Líneas de Espera
•
M A E S T R Í A
Distribución de tiempos de servicio: al igual que las
llegadas al sistema, los tiempos en que las entidades
son atendidas dentro del sistema tienden a ser
independientes una de la otra y aleatorias, por lo que es
común que se representen con una distribución de
probabilidad.
Importante: en la teoría de colas también puede
encontrarse que los tiempos de servicio son constantes,
los cuales se pueden encontrar en procesos
automatizados. Dicha variante la veremos como último
modelo de análisis en este tema.
Teoría de Líneas de Espera
M A E S T R Í A
Notación Kendall
Todos
T
d llos sistemas
i t
d
de lílíneas d
de espera pueden
d ser
representados de manera más sencilla mediante el uso
de la notación desarrollada por A. G. Kendall, la cual
tiene el propósito de representar mediante tres
caracteres el tipo de sistema a analizar.
La notación Kendall se representa de la siguiente manera:
Distribución de Llegadas / Distribución de tiempos de
Servicio / Número de servidores
Derechos reservados © TecMilenio, A.C.
16
Métodos cuantitativos para la toma de decisiones
Teoría de Líneas de Espera
M A E S T R Í A
Donde
• La Distribución de Llegadas puede ser:
M = distribución de llegadas de tipo Poisson
D = distribución de llegadas es constante
G = distribución de llegadas general con varianza y
media conocidas
• La Distribución de tiempos de Servicio puede ser:
M = distribución de tiempos de servicio de tipo
Exponencial
D = distribución de tiempos de servicio es constante
G = distribución de tiempos de servicio general con
varianza y media conocidas
• El Número de servidores puede tomar valores de 1, 2,
3,…m
Teoría de Líneas de Espera
M A E S T R Í A
Para los modelos de líneas de espera a analizar en este
tema la notación Kendall será de la siguiente manera:
1 Modelo de un sólo canal (M / M / 1).
1.
1)
2. Modelo de canales múltiples (M / M / m).
3. Modelo de tiempo de servicio constante (M / D / 1).
1. Modelo de un solo canal (M / M / 1)
A continuación se p
presenta el enfoque
q de análisis q
que se
debe dar al sistema de línea de espera típico con llegadas
de tipo Poisson, tiempos de servicio de tipo Exponencial
con un sólo servidor.
Derechos reservados © TecMilenio, A.C.
17
Métodos cuantitativos para la toma de decisiones
Modelo de un solo canal (M / M / 1)
M A E S T R Í A
Importante: se supone que en este sistema, la
entidad está dispuesta a esperar el tiempo que sea
para ser atendido
atendido, es decir no hay rechazo
rechazo.
Donde:
λ = número promedio de llegadas al sistema
μ = número promedio de entidades que se atienden
en el sistema
Nota: ambas variables deberán representarse con el
mismo periodo, es decir por ejemplo para λ llegadas/hora y
para μ unidades/hora.
Modelo de un solo canal (M / M / 1)
M A E S T R Í A
Y las ecuaciones
serán de la
siguiente
i i t manera:
Derechos reservados © TecMilenio, A.C.
18
Métodos cuantitativos para la toma de decisiones
M A E S T R Í A
Modelo de canales múltiples (M / M / m)
2. Modelo de canales múltiples (M / M / m)
A continuación
ti
ió se presenta
t ell enfoque
f
d
de análisis
áli i que
se debe dar al sistema de línea de espera con dos o
más servidores con llegadas de tipo Poisson y tiempos
de servicio de tipo Exponencial.
Importante: se supone que en este sistema, la entidad
está dispuesta a esperar el tiempo que sea para ser
atendido, es decir no hay rechazo; y que los m
servidores tardan lo mismo en atender (μ) a las
unidades.
M A E S T R Í A
Modelo de canales múltiples (M / M / m)
Donde
•
•
•
λ = número
ú
promedio
di d
de llllegadas
d all sistema
i t
μ = número promedio de entidades que se atienden en
el sistema
m = número de servidores o instalaciones
Derechos reservados © TecMilenio, A.C.
19
Métodos cuantitativos para la toma de decisiones
M A E S T R Í A
Modelo de canales múltiples (M / M / m)
Y las ecuaciones serán de la siguiente manera:
E S T R Í A
Modelo de tiempo de servicio constanteM A(M
/ D / 1)
3. Modelo de tiempo de servicio constante (M / D / 1)
A continuación se presenta el enfoque de análisis que
se debe dar al sistema de línea de espera con llegadas
de tipo Poisson, tiempo de servicio constante y un
servidor.
Este tipo de modelos los valores de Lq, Wq, L y W
siempre son menores a los que se obtienen en los
modelos anteriormente presentados.
p
Donde
• λ = número promedio de llegadas al sistema
• μ = número de entidades que se atienden en el sistema
de manera constante
Derechos reservados © TecMilenio, A.C.
20
Métodos cuantitativos para la toma de decisiones
E S T R Í A
Modelo de tiempo de servicio constanteM A(M
/ D / 1)
Y las ecuaciones serán de la siguiente manera:
Cierre
M A E S T R Í A
Con estos temas principales de la programación lineal,
terminamos de cubrir los métodos cuantitativos para la
toma de decisiones
decisiones.
Para el aprendizaje de este módulo se aplicaron algunos
casos de la vida real, esperando que esto te ayudará a
aterrizar las ideas de una manera más práctica.
Los métodos de transporte, asignación y teoría de filas de
espera complementan por mucho la introducción de la
programación lineal que iniciamos al final del módulo 3.
Esperamos que puedas aplicar estos conocimientos en tu
vida profesional.
Derechos reservados © TecMilenio, A.C.
21
Métodos cuantitativos para la toma de decisiones
Referencias Bibliográficas
M A E S T R Í A
Render, B., Stair, R. M., & Hanna, M. E. (2006). Métodos
Cuantitativos para los Negocios. México: Pearson
Prentice Hall.
Hall
M A E S T R Í A
Créditos
Diseño de contenido:
Lic. Iván Alarcón Múgica, MET
Coordinador académico del área:
L.I. Oscar Andrés Rodríguez Múgica, MATI
Edición de contenido:
Lic. Miriam Gómez Moore, MED
Edición de texto:
Lic. Alejandra Zaragoza Scherman
Diseño gráfico:
Lic. Alejandro Calderas González, MATI
Derechos reservados © TecMilenio, A.C.
22