Una Cadena de Markov en tiempo discreto consiste en una clase particular de un proceso estocástico donde se verifica el cumplimiento de la propiedad markoviana (en términos simples establece que el futuro es independiente del pasado dado el presente) y la propiedad estacionaria (la probabilidad de transición de un estado i a un estado j al cabo de una etapa no depende de la etapa n). En este contexto a continuación presentamos 3 preguntas de selección múltiple que permite reforzar algunos conceptos básicos sobre las Cadenas de Markov.
Pregunta N°1: En la matriz de probabilidades de transición:
a) La suma de cada columna debe ser igual a 1
b) La suma de cada columna y cada fila debe ser igual a 1
c) Por lo menos debe haber un 0 en cada fila d) La suma de cada fila debe ser igual a 1
e) Por lo menos debe haber un 0 en cada columna
Respuesta:Alternativa d). La matriz de probabilidades de transición o matriz P resume las probabilidad de transición en una etapa de un estado i a un estado j. La matriz P tiene la misma cantidad de filas y columnas. Por ejemplo a continuación de presenta la matriz de transición que corresponde a uno de los casos discutidos en el artículo Cadenas de Markov (Ejercicios Resueltos) donde se corrobora que la sumatoria de los valores de cada fila corresponde a un 100%.
Pregunta N°2: Si la distribución de probabilidad de la variable no cambia de una etapa a otra:
a) Cada probabilidad debe ser igual a 1
b) Debe haber al menos una probabilidad igual a 0
c) La probabilidad debe ser la misma para cada estado d) Dicha distribución coincide con la distribución estacionaria
e) Debe haber al menos una probabilidad igual a 1
Respuesta:Alternativa d). En este caso estamos frente a la distribución estacionaria o de largo plazo la cual como hemos discutido previamente es independiente de la distribución inicial para la variable aleatoria. Antecedentes adicionales y un ejemplo con el detalle del cálculo se puede consultar en Distribución Límite de una Cadena de Markov en Tiempo Discreto.
Pregunta N°3: Cuál de las siguientes alternativas no es un supuesto de las cadenas de Markov:
a) Existe un número finito de estados
b) Existe un número finito de etapas
c) Las probabilidades de la variable de estado se pueden calcular usando únicamente la matriz de probabilidades de transición
d) La distribución de probabilidades de una etapa no cambia de una etapa a la otra e) Todas la anteriores no son supuestos del análisis
Respuesta:Alternativa e). Se descarta a) y b) debido a que puede existir un número infinito de estados y etapas. En cuanto a las probabilidades de la variable de estado , se requiere conocer una distribución de estado actual o inicial para que luego, haciendo uso de las ecuaciones matriciales se pueda estimar las probabilidades de estado.
La Función de Pérdida de Taguchi propuesta por el experto en calidad japones Genichi Taguchi establece que cualquier desviación con respecto al valor meta o especificación deseada produce una pérdida monetaria para la sociedad. En este contexto el método de Taguchi se basa en la hipótesis de que mientras menor sea la variación con respecto a dicho valor objetivo (meta) mejor será la calidad del producto. Notar que el valor meta o especificación deseada es equidistante del Límite de Especificación Inferior (LEI) y el Límite de Especificación Superior (LES).
El aporte de Taguchi radica en incorporar en el análisis la perspectiva del cliente, dado que en general no existe prácticamente mayor diferencia entre un producto que esta justo dentro de los límites de especificación y un producto que está justo fuera de éstas. Por el contrario, la diferencia resulta ser mucho mayor en términos de la calidad, al comparar un producto que tiene la especificación meta (objetivo) en relación a un producto que se encuentra cerca de uno de los límites de especificación (pero en el intervalo [LEI,LES]).
Para comprender de mejor forma la propuesta de Taguchi es conveniente contrastar su visión en relación a la Perspectiva Tradicional. Según el concepto tradicional, las pérdidas ocurren sólo cuando un producto excede los límites de especificación tal como se muestra en la gráfica. De esta forma se asume que cualquier producto que se encuentre contenido entre los límites de especificación no genera una pérdida en términos de la calidad para el cliente y para la sociedad.
Si bien dicho enfoque es simplificador y en algunos casos se podría encontrar razonable, en la actualidad existe un consenso es considerar que es obsoleto, al no representar de forma adecuada la valoración del cliente.
Por el contrario, la Función de Pérdida de Taguchi establece que existe una degradación de la calidad desde la perspectiva del cliente cuando el producto se aleja de la especificación deseada aun cuando se encuentre entre los límites de especificación. Más aún como se puede observar en la representación gráfica el costo incremental de la variabilidad para la sociedad crece (de forma no lineal) en la medida que el producto se aleja de la especificación deseada.
De esta forma Taguchi postula que esta visión (su propuesta) es más cercana a cómo los clientes ven la función de pérdida en comparación a la perspectiva tradicional.
En relación a lo anterior, por lo general la Función de Pérdida de Taguchi se representa en su expresión cuadrática de modo que las mayores desviaciones respecto al valor objetivo (especificación deseada o meta) provoquen pérdidas cada vez mayores para la sociedad. La fórmula es:
Donde:
: Valor de la característica de calidad
: Valor meta u objetivo
: Pérdida por una unidad producida en el límite de especificación
: Límite de Especificación Superior (LES) –
Ejemplo Función de Pérdida de Taguchi
Suponga que tenemos una característica de calidad que tiene una especificación de 0.500 +- 0.020, y que si el valor de la característica de calidad difiere 0.02 del valor deseado de 0.500, es probable que el producto falle durante el período de garantía, y su reparación cuesta 50 dólares. Estos valores se pueden calcular analizando los registros de la compañía. Entonces:
Luego, si la desviación resultará ser sólo 0.010, la pérdida estimada al utilizar la Función de Pérdida de Taguchi sería:
El Método de Johnson permite determinar una secuencia u orden para realizar trabajos en un taller que considera 2 máquinas, donde todos los trabajos siguen un orden común (por ejemplo, primero se ejecutan labores en una máquina 1 y luego en una máquina 2), asumiendo que todos los trabajos se encuentran disponibles para su programación al inicio del horizonte de evaluación y que los tiempos requeridos para pasar por cada máquina son conocidos (es decir, se asume que no existe incertidumbre). De esta forma se busca determinar el tiempo mínimo para completar los trabajos en el taller lo cual se conoce como makespan. En este contexto a continuación se presenta un ejemplo resuelto del Método o Algoritmo de Johnson.
Ejercicio Resuelto del Método de Johnson
Una imprenta se dedica a la copia y encuadernación de documentos. Esta mañana recibió los trabajos que se muestran a continuación, todos los cuales requieren ambas operaciones en ese orden:
La imprenta comienza a trabajar puntualmente a las 09:00 y no se detiene hasta que termina de procesar todos los trabajos. La hora de entrega para todos los trabajos corresponde a las 13:00. Determine una secuencia de manera que el tiempo que tardan en ser procesados los trabajos sea el menor posible, esto es minimizando el makespan. Construya una Carta Gantt para complementar su respuesta.
Este problema trata de máquinas en paralelo sin interrupción con trabajos cuyo tiempo de proceso es determinista y la llegada al comienzo (estática), de modo que se puede aplicar el Algoritmo de Johnson.
El tiempo más breve corresponde al trabajo A en encuadernación, por tanto se asigna en primer lugar y se ejecuta al final de la secuencia. Luego el tiempo más breve es para el trabajo B en encuadernación, siendo este trabajo asignado en segundo lugar y ejecutado penúltimo. De los trabajos remanentes el tiempo más breve es 40[min] existiendo un empate en encuadernación (trabajo C) y copia (trabajo E). En caso de empate el Método de Johnson establece que se prioriza la máquina 1 (en este caso copia) y por tanto E se asigna en tercer lugar y se ejecuta primero. A continuación naturalmente se asigna el trabajo C en cuarto lugar y se ejecuta antepenúltimo. El quinto trabajo en asignar será el D el cual se realiza inmediatamente antes del trabajo C (al tener su menor tiempo en encuadernación). Finalmente se asignan los trabajos F y G (en ese orden) ejecutándolos en segundo y tercer lugar, respectivamente. De esta forma la secuencia es:
E-G-F-D-C-B-A
El makespan para este problema de Programación de Trabajos es de 440 minutos, terminando de atender el último trabajo a las 16:20.
En relación a los resultados obtenidos anteriormente determine: ¿A qué hora se termina de atender el último trabajo?, ¿Cuántos trabajos atrasados tiene la imprenta?, ¿Cuál es el tiempo de flujo promedio?, ¿Cuál es el atraso promedio?, ¿Cuál es el atraso máximo?.
Para responder a esta pregunta confeccionamos una tabla resumen la cual se basa en los resultados obtenidos a través de la Carta Gantt y los horarios de entrega de los trabajos.
Total Atrasos: 5 (Trabajos A, B, C, D y F)
El último trabajo se termina de atender a las 16:20 (Trabajo A)
Tiempo de Flujo Promedio: 06:01
Atraso Promedio: 1:48
Atraso Máximo: 3:20
Cabe recordar que el Tiempo de Flujo (TF) corresponde al tiempo total que cada trabajo se encuentra en el taller, es decir, esto es la suma del tiempo de espera más el tiempo de atención o procesamiento en las distintas máquinas. Por ejemplo si bien el trabajo A requiere en total un tiempo de 30[min] éste comienza a ser atendido recién a las 15:20 en copia, terminando a las 16:20 en encuadernación (total 60[min] o 1[hora]). Adicionalmente el trabajo A debe esperar 7 horas con 5 minutos (es decir, de las 08:15 a las 15:20) para comenzar su atención en copia. Luego el Tiempo de Flujo es 1:00+7:05=8:05 (8 horas y 5 minutos).
El Método Simplex desarrollado por George B. Dantzig en 1947 es sin duda el algoritmo más popular a la hora de enfrentar la resolución de un modelo de Programación Lineal y ocupa un lugar destacado en los cursos introductorios a la Investigación de Operaciones.
En esta oportunidad hemos buscado resumir 10 conceptos principales sobre el uso y la aplicación del Método Simplex con el objetivo de que nuestros usuarios puedan tener una primera aproximación al método observando algunos aspectos característicos. Esta recopilación se basa sobre nuestra experiencia docente dictando cursos de Investigación Operativa y las preguntas que frecuentemente recibimos por parte de los alumnos de pregrado.
10 Cosas que Necesitas Saber sobre el Método Simplex
Te invitamos a revisar y compartir esta infografía en las redes sociales. Adicionalmente si consideras si un elemento importante quedo fuera de la lista anterior utiliza la herramienta de comentarios al pie de la página para hacernos saber tu opinión. De esta forma podremos ir actualizando periódicamente el artículo con las características principales del Método Simplex.
El siguiente problema consiste en la formulación de un modelo de Programación Entera y posterior resolución computacional haciendo uso del complemento OpenSolver de Excel, específicamente en lo que se refiere a un modelo que permita encontrar la estrategia óptima para la Planificación de la Producción Multiproducto (es decir, 2 o más productos) y multiperiodo (2 o más períodos en el horizonte de evaluación). Referencias adicionales sobre esta clase de problemáticas pueden ser consultadas en la categoría Plan Maestro de la Producción (PMP) donde se presentan un importante volumen de ejercicios resueltos de planificación agregada. Dicho lo anterior a continuación presentamos el ejemplo objeto de nuestro análisis:
Una empresa desea optimizar la planificación de la producción de sus cinco productos principales para los primeros 6 meses del año 2016. Para el desarrollo de la tarea encomendada la empresa recolecta los siguientes antecedentes:
El proceso de fabricación es intensivo en mano de obra donde cada trabajador percibe un salario bruto de US$1.200 por una jornada de 160 horas de trabajo al mes.
El costo unitario de materiales y gastos generales, excluyendo el trabajo es de US$12 para A, US$14 para B, US$9 para C, US$13 para D y US$8 para E.
El costo de mano de obra de producción en tiempo extra se paga con un recargo de un 50% respecto a la hora trabajada en horario normal. No obstante por política de la empresa se establece un máximo de 200 horas hombre en tiempo extraordinario para cada mes, exceptuando Enero y Febrero donde el límite corresponde a 100 horas (por acuerdos con el sindicato).
El costo mensual de almacenar una unidad de cualquier producto en inventario es de US$4 por unidad. La bodega tiene una capacidad de almacenamiento de 250 unidades.
El tiempo de producción por unidad es de 5 horas para A, 6 horas para B, 8 horas para C, 4 horas para D y 3 horas para E.
La contratación de personal de producción considera un costo único de US$1.500 (adicional al sueldo) por concepto de capacitación y entrenamiento.
Para la reducción de horas de trabajo o despido considere en promedio: un sueldo de US$1.200 y una antigüedad de 2 años. Por política de estabilidad laboral se establece un máximo de despido de 6 trabajadores durante el primer semestre.
El inventario inicial corresponde a 120 y 80 unidades para los productos B y C respectivamente. No se dispone de inventario inicial para el producto A, D y E.
La planilla de trabajadores al 31 de Diciembre de 2015 es de 55 trabajadores.
Es posible dejar demanda pendiente del producto A y D asumiendo un costo unitario de US$25 en cada caso, la cual no expira y sólo se posterga para un próximo mes. No obstante la empresa requiere que como máximo queden 500 unidades de demanda pendiente (en total para la suma de ambos productos) a fines de Junio de 2016.
En cuanto al producto B, éste se puede comprar adicionalmente a un proveedor a un costo unitario de US$75. Adicionalmente el costo fijo de gestionar un pedido al proveedor del producto B (independiente del tamaño del pedido) es de US$200.
En cuanto al producto E, éste se puede comprar adicionalmente a un proveedor a un costo unitario de US$35. Adicionalmente el costo fijo de gestionar un pedido al proveedor del producto E (independiente del tamaño del pedido) es de US$150.
Formule y resuelva un modelo de optimización matemática que permita determinar la política operacional que minimice los costos totales en el horizonte de planificación y cumpla con las condiciones expuestas.
Planificación de la Producción Multiproducto
Variables de Decisión:
Notar que se dispone de 5 productos y 6 períodos. En este contexto y con el objetivo de lograr una notación más compacta se utilizan los índices i y t para representar los productos y períodos (meses), respectivamente.
Parámetros:
La definición de parámetros no es estrictamente necesaria y se realiza de modo de establecer un caso más general para el problema que facilita (compacta) la notación requerida para definir el modelo. Se puede apreciar que no todos los datos factibles de poder representar con parámetros ha sido llevado a cabo, lo cual corresponde a una decisión arbitraria la que sin embargo no afecta los resultados.
Función Objetivo:
Se busca minimizar los costos totales de la planificación multiproducto y multiperiodo. Los costos involucrados son (en orden): producción, inventario, mano de obra en tiempo normal, mano de obra en sobretiempo, contratación, despido, demanda pendiente, compra del producto B y compra del producto E.
Restricciones:
Balance de Inventario: Para el caso del producto A y D se puede utilizar demanda pendiente y para los productos B y E se pueden realizar compras. En este caso sólo los requerimientos del producto C deben ser satisfechos de forma exclusiva a través de la producción e inventario.
Balance de Trabajadores: La cantidad de trabajadores disponibles en un mes para funciones de producción será igual a los disponibles en el mes anterior, más los contratados en el mes y menos los despedidos en dicho mes.
Capacidad de Producción: El lado izquierdo de la restricción representa la cantidad de horas requeridas en un mes para la producción de los 5 productos, lo cual no podrá superar las horas disponibles (siendo éstas las horas en tiempo normal más las horas que eventualmente se utilicen en sobretiempo).
Capacidad de la Bodega: Para cada mes del horizonte de planificación la cantidad de productos almacenados en inventario (suma de todos los productos) no podrá superar la capacidad de almacenamiento de la bodega de 250 unidades.
Máximo de Compras B y E: La cantidad máxima de compra para el producto B y E dependerá si se adopta la decisión de realizar una compra en el mes respectivo. En dicho caso la cantidad máxima a comprar corresponderá a los parámetros o constantes grandes y , respectivamente. Por ejemplo un valor para podría ser 3.152 que corresponde a la suma de la demanda del producto B del mes 1 al mes 6.
Máxima Cantidad de Despidos: Durante el horizonte de planificación no se pueden despedir más de 6 trabajadores.
Máximo Demanda Pendiente Mes 6: Al final del mes 6 no debe quedar más de 500 unidades de demanda pendiente para el producto A y D (en conjunto).
No Negatividad y Enteros: Las variables de decisión deben adoptar no negativos y enteros (exceptuando las variables binarias).
La implementación computacional con OpenSolver del modelo de optimización anterior entrega los siguientes resultados. Las celdas en color amarillo corresponden a las variables de decisión del problema definidas inicialmente que satisfacen las restricciones impuestas (solución factible).
El valor óptimo corresponde a US$599.770 que corresponde al costo mínimo asociado al plan de producción. A continuación se desglosa dicho costo total en los distintos ítems de costos según lo detallado anteriormente.
¿Quieres tener la planilla Excel con la resolución en OpenSolver de este problema?.
no cambia de una etapa a otra:
: Valor de la característica de calidad
: Valor meta u objetivo
: Pérdida por una unidad producida en el límite de especificación
: Límite de Especificación Superior (LES) – 
y 
, respectivamente. Por ejemplo un valor para 
