Gestión de Operaciones

Problema de Asignación de Horas Académicas a Profesores aplicado a una Universidad Online

El desarrollo de las tecnologías de información ha favorecido un crecimiento sostenido en la oferta académica de las instituciones de educación superior, lo cual ha permitido sumar a la tradicional formación presencial la posibilidad de obtener grados académicos a través de una formación no presencial (online). En este contexto, en la actualidad existen numerosas “Universidades Online” las cuales deben programar horas de apoyo académico de sus distintos cursos por parte de los profesores o docentes hacia los alumnos, con el objetivo de favorecer la comprensión de los contenidos.

Problema de Asignación de Horas Académicas a Profesores

En el siguiente artículo consideraremos un problema de asignación para cubrir las necesidades de apoyo académico para un curso de Economía. Asumiremos que se desea tener exactamente un profesor de turno (para responder preguntas de los alumnos en tiempo real a través de un foro o chat) de Lunes a Viernes de 08:00 AM hasta las 23:00 PM. Los Sábados y Domingo también se desea ofrecer el servicio pero de 08:00 AM hasta las 20:00 PM. Actualmente se cuenta con 10 profesores que cuentan con los conocimientos necesarios para desarrollar los servicios de tutorias y su remuneración (en dólares por hora) depende básicamente de la experiencia en el curso y grado académico. Adicionalmente, debido a los compromisos que tienen dichos profesores con otros cursos de la Universidad, han manifestado su disponibilidad máxima (en horas) para atender los distintos requerimientos según se detalla en la siguiente tabla:

Por ejemplo el profesor 1 recibe un salario de 50 dólares la hora y puede trabajar como máximo 5 horas el Lunes, 6 horas el Miércoles y Viernes, 3 horas el Sábado y 2 horas el Domingo. Los días Martes y Jueves el profesor 1 no tiene disponibilidad de tiempo. En base a esta información la Universidad desea determinar una asignación de horas académicas a los profesores de modo de cubrir las necesidades de atención de alumnos al menor costo posible al mismo tiempo de garantizar un mínimo de 5 horas por profesor a la semana. Para enfrentar dicha situación formularemos el siguiente modelo de Programación Lineal:

Variables de Decisión:

Con i=1,…,10 representando a los profesores y j=1,…,7 los días de la semana don j=1 es el día Lunes y j=7 el día Domingo.

Parámetros:

Función Objetivo:

Se busca minimizar los costos totales de la asignación que considera la ponderación para cada profesor de la cantidad de horas que trabaja durante la semana por el salario por hora (en dólares).

Restricciones:

Se debe cumplir con la cantidad de horas para cada día de la semana (15 horas para cada día de Lunes a Viernes y 12 horas para el Sábado y Domingo).

Se desea asignar al menos 5 horas académicas semanales a cada profesor.

Se debe respetar la disponibilidad horaria de los profesores durante la semana.

Condiciones de no negatividad para las variables de decisión.

Luego de implementar computacionalmente el modelo de optimización con Solver de Excel se obtiene la siguiente solución óptima con valor óptimo V(P)=US$4.639.

El siguiente tutorial de nuestro canal de Youtube muestra la resolución del problema anterior:

Problema de Asignación de Capacidad de un Avión (Programación Lineal)

La industria de transporte de pasajeros enfrenta diariamente el problema de determinar cómo asignar de forma eficiente su capacidad de transporte al momento de ofrecer distintos tipos de tarifas a sus clientes para una ruta específica. Para ello se debe considerar de forma simultanea los ingresos por venta asociados a cada tipo de tarifa, una estimación de demanda de los clientes por dichas tarifas y la capacidad del medio de transporte en términos de la cantidad de asientos.

El siguiente problema considera la formulación y resolución computacional de un Problema de Asignación de capacidad de un avión para una empresa de transporte aéreo. La complejidad del problema y el nivel de detalle de la información se ha simplificado para fines académicos.

Problema de Asignación de Capacidad de un Avión

Consideremos una línea aérea que realiza la ruta Santiago (Chile) a Bogotá (Colombia) con escala en Lima (Perú). Para dicha ruta utiliza un avión con capacidad de 200 pasajeros. El departamento de ventas ha estimado los precios de mercado (en dólares) para las combinaciones de origen destino de 3 tipos de tarifas que actualmente ofrece la empresa: “Tarifa Y” (primera clase), “Tarifa B” (estándar) y “Tarifa C” (turista).

Adicionalmente y según información histórica de esta ruta, la línea aérea ha estimado el número máximo de pasajes que los clientes demandarán por cada combinación de tarifa en un tramo del vuelo. Por ejemplo la demanda máxima esperada para el tramo Santiago (SCL) a Bogota (BOG) en la Tarifa B es de 35 tickets.

Con esta información la línea aérea desea determinar cómo asignar la capacidad del avión de modo de ofrecer un determinado número de pasajes para cada tipo de tarifa en un tramo del vuelo. Para ello definiremos el siguiente modelo de Programación Lineal:

Variables de Decisión:

Donde i=1,2,3 representa los distintos tipos de tarifa (Y, B y C, respectivamente) y j=1,2,3 las combinaciones de origen destino (SCL-LIM, LIM-BOG y SCL-BOG, respectivamente).

Parámetros:

Al utilizar una notación con parámetros podemos representar el modelo de optimización de forma compacta.

Función Objetivo:

Restricciones:

Se ofrece para cada tarifa en las combinaciones origen destino un número de tickets que no supere la demanda máxima del mercado.

Para cada tramo del vuelo se debe respetar la capacidad total del avión de 200 pasajeros.

Cuando el avión despega desde Santiago con destino Lima lleva pasajeros con destino tanto a Lima como Bogotá. Por tanto independiente de la tarifa que cada uno de estos pasajeros haya pagado (por ello la sumatoria en las tarifas) no pueden superar la capacidad total del avión. Lo anterior esta garantizado por la primera restricción de capacidad.

La segunda restricción de capacidad es para el tramo desde Lima a Bogotá, donde se consideran adicionalmente los pasajeros que vienen desde Santiago.

Finalmente se definen las condiciones de no negatividad.

Al resolver con Solver el problema anterior se alcanza la siguiente solución óptima que determina cuántos pasajes debería ofertar la línea aérea para cada combinación de tarifa y origen destino.

El valor óptimo del problema que representa los ingresos totales (en dólares) asociados a la solución óptima propuesta es de US$158.340.

¿Quieres tener el archivo Excel con la resolución en Solver de este problema?.

[sociallocker]Descarga Aquí el Archivo[/sociallocker]

Distribución Límite de una Cadena de Markov en Tiempo Discreto

Una Distribución Límite (estacionaria) de una Cadena de Markov en tiempo discreto consiste en una distribución de estado estable para los estados de una cadena que es independiente de la distribución inicial.

En distintas aplicaciones de esta categoría de procesos estocásticos resulta de interés identificar la probabilidad de que la variable aleatoria “Xn” adopte un valor “j” (entre M estados posibles) al cabo de un número de etapas o transiciones “n” que tiende a infinito. Lo anterior equivale a:

En este contexto existen ecuaciones que permiten encontrar estas probabilidades de largo plazo en la medida que el proceso markoviano en tiempo discreto sea una cadena irreducible con estados recurrentes positivos aperiódicos.

Para ello se requiere en primera instancia Clasificar los Estados de la Cadena de Markov de modo de corroborar las condiciones anteriores.

En forma compacta las ecuaciones que permiten encontrar las probabilidades estacionarias son:

Consideremos el siguiente ejemplo que satisface las condiciones enunciadas previamente. ¿Cuál es la probabilidad de que en el largo plazo el proceso se encuentre en el estado 0, 1 o 2?.

La matriz de probabilidades de transición en una etapa (y su respectiva matriz transpuesta) son las siguientes:

El sistema de ecuaciones que permite encontrar las probabilidades de estado estable queda especificado por:

La resolución del sistema anterior permite obtener:

Es decir, la probabilidad de que en el largo plazo el proceso se encuentre en el estado 0, 1 y 2 es de un 28,57%, 35,71% y 35,71%, respectivamente (las probabilidades han sido aproximadas a dos decimales). Esto es independiente de la distribución inicial, es decir, en qué estado actualmente se encuentre la variable aleatoria.

Conclusión: Se puede corroborar los resultados anteriores utilizando las fórmulas matriciales para encontrar la distribución de estado para una etapa “n”. Para ello seleccionamos un valor de “n” relativamente “grande” y una distribución inicial cualquiera (se deben seleccionar valores de a, b y c mayores o iguales a cero tal que a+b+c=1). Con esto se puede verificar que independiente de la distribución inicial las probabilidades de largo plazo convergerán asintóticamente a los valores obtenidos anteriormente.

Por ejemplo, estableciendo (arbitrariamente) a=1, b=0, c=0 se logran las siguientes probabilidades de estado al cabo de 10 transiciones (con color verde se muestra las probabilidades estacionarias).

Clasificación de Estados de una Cadena de Markov en Tiempo Discreto

En esta sección se presentan algunos resultados teóricos que tienen relación con la existencia y cálculo de una distribución para la Cadena de Markov en el largo plazo (conocida también como Distribución Estacionaria).

Previamente, se enumeran algunas definiciones que clasifican los estados de una cadena. Para ello consideraremos el ejemplo que utilizamos para introducir una Cadena de Markov en Tiempo Discreto, asumiendo la probabilidad de lluvia al inicio (y final del día) en un 20% (p=0,2).

El grafo que resume las probabilidades de transición es el siguiente:

Clasificación de Estados de una Cadena de Markov

Un estado j se dice accesible desde el estado i si y sólo si para algún n:

Lo anterior implica que existe una probabilidad no nula que comenzando en el estado i se puede llegar al estado j al cabo de n etapas. En nuestro ejemplo el estado 2 es accesible desde el estado 0 (dado que desde 0 se puede acceder a 1 y desde 1 se puede acceder a 2). Es trivial demostrar en este contexto que el estado 2 es accesible desde 1 (como también 1 lo es desde 2).

Adicionalmente si tanto el estado i es accesible desde j como viceversa decimos que los estados i y j se comunican. Notar que 1 es accesible desde 0 (como 0 también es accesible desde 1) por tanto 0 y 1 se comunican. También es posible demostrar que 1 y 2 se comunican. Luego por transitividad el estado 0 y 2 se comunican. Lo anterior deja en evidencia que en el ejemplo todos los estados se comunican entre sí, por lo cual pertenecen a la misma clase de estados.

Una cadena es irreducible si tiene una única clase de estados, es decir, los estados que la componen se comunican entre sí (son accesibles viceversa).

Un estado se dice que tiene periodo d, para el mayor valor del entero d que cumple:

sólo para valores de n pertenecientes al conjunto {d, 2d, 3d, ….}. Si d=1 decimos que el estado es aperiódico.

En otras palabras, un estado es periódico si, partiendo de ese estado, sólo es posible volver a él en un número de etapas que sea múltiplo de un cierto número entero mayor que uno.

En el ejemplo se puede volver a cada estado con probabilidad no nula al cabo de una etapa, condición suficiente (pero no necesaria) para afirmar que los estados son aperiódicos.

Se denota por Fk(i,i) la probabilidad de que el proceso retorne al estado i por primera vez al cabo de exactamente k etapas. De modo que:

es la probabilidad que partiendo en i, el proceso regrese al estado i alguna vez.

Si F(i,i)=1 se dice que el estado es recurrente (en caso contrario, es decir, F(i,i)<1, el estado es transciente).

La demostración matemática de que un estado es recurrente no resulta siempre trivial, no obstante en el ejemplo estamos frente a una cadena irreducible con un número finito de estados, por tanto dichos estados son recurrentes positivos.

El concepto de recurrente positivo se refiere a que el valor esperado del número de etapas que le toma al proceso volver al estado i por primera vez, partiendo del estado i es un número finito.

En resumen, se concluye que para el ejemplo propuesto, la cadena es irreducible con estados recurrentes positivos aperiódicos.

Aplicaciones de Investigación de Operaciones en la Agroindustria

El 27 de Septiembre del año 2013 el Instituto Chileno de Investigación Operativa (ICHIO) en conjunto con la Facultad de Ingeniería de la Universidad de Talca desarrolló el 2° Coloquio sobre las “Aplicaciones de Investigación de Operaciones en la Agroindustria”. En dicha oportunidad se dictaron 3 interesantes charlas a cargo de destacados profesionales que dejan de manifiesto la utilidad práctica de esta disciplina.

Cabe destacar que es una actividad habitual para ICHIO en el contexto de su misión institucional la difusión de la Investigación de Operaciones a nivel nacional (Chile) a través de la organización de congresos bianuales (Óptima) y coloquios que abordan aspectos tanto teóricos como prácticos relacionados a esta disciplina.

A continuación un enlace con el detalle de la Programación 2° Coloquio ICHIO 2013.