GEO Tutoriales, Autor en Gestión de Operaciones

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.

Ejemplo de una Cadena de Markov en Tiempo Discreto

En el siguiente artículo abordaremos la formulación de una Cadena de Markov en tiempo discreto, para la cual identificaremos la variable aleatoria que resulta de interés su análisis, los posibles estados que puede adoptar dicha variable en un periodo cualquiera y las probabilidades de transición en una etapa que se puede resumir en una matriz de transición de probabilidades conocida como matriz P. En dicho contexto consideremos el siguiente ejemplo:

Un individuo posee 2 paraguas los cuales emplea para ir de su casa al trabajo y viceversa (llevando uno a la vez). Si está en casa (oficina) al comienzo (final) del día y está lloviendo toma un paraguas, si lo hay para ir de su casa a la oficina y viceversa. Asuma que independiente del pasado llueve al comienzo (final) del día con probabilidad p (0<p<1). Se desea modelar el número de paraguas en su casa al inicio del día n, suponiendo que inicialmente ambos paraguas están en su casa.

El problema sugiere como variable aleatoria el modelamiento del número de paraguas que tiene el individuo en su casa al inicio del día n:

Los posibles estados o valores que puede adoptar la variable aleatoria en una etapa n cualquiera son 0, 1 o 2. Es decir, el individuo podrá tener en su casa al inicio de un día en particular 0, 1 o 2 paraguas.

A continuación corresponde identificar las probabilidades de transición en una etapa, lo cual depende de la dinámica de la situación planteada:

Por ejemplo P(0,0) representa la probabilidad de que un día el individuo no tenga paraguas en su casa (por tanto los 2 paraguas están en la oficina) y que al inicio del día siguiente siga en la misma situación (es decir, sin paraguas en la casa). Los escenarios que permiten esta situación son que llueva en la mañana (con probabilidad p) y que no llueva en la tarde (con probabilidad 1-p). Adicionalmente si no llueve en la mañana (con probabilidad 1-p) y no llueve en la tarde (con probabilidad 1-p) el individuo al inicio del día siguiente no tendrá paraguas en la casa. En consecuencia se puede notar que para este caso lo relevante es que no llueva en la tarde (sin importar si llueve o no en la mañana) para que de esta forma el individuo no se lleve un paragua desde la oficina a la casa.

Otra combinación interesante es P(2,2) que considera la probabilidad de tener los 2 paraguas en la casa al inicio de un día (y por tanto ninguno en la oficina) y al inicio del día siguiente también tener 2 paraguas en la casa. Para ello se debe cumplir alguno de los siguientes escenarios: que llueva en la mañana y en la tarde, que no llueva ni en la mañana ni en la tarde o que no llueva en la mañana pero si llueva en la tarde.

Una vez identificadas todas las probabilidades de transición en una etapa entre estados, éstas se pueden resumen en la matriz de probabilidades de transición (conocida también como matriz P). Notar que la suma de las probabilidades de cada una de las filas de la matriz es (y debe ser) un 100%.

Alternativamente la información anterior se puede representar a través de un grafo donde cada nodo representa un estado y las flechas muestran si es posible pasar de un estado a otro al cabo de una etapa (y cuál es la probabilidad asociada en dicho caso):

Adicionalmente se puede identificar (si se cuenta con dicha información) la distribución inicial de estados que permite identificar cuál es la probabilidad que al inicio de la planificación el proceso se encuentre en alguno de los n estados posibles. En este ejemplo sabemos que se comienza con 2 paraguas en la casa:

Con la información recabada en este problema estamos en condiciones de poder estimar cuál es la probabilidad que comenzando en un estado i pasemos a un estado j al cabo de n etapas (pasos). Este tipo de análisis y otros complementarios los abordaremos en un próximo artículo.

Actualización: Se recomienda consultar el artículo Cadenas de Markov (Ejercicios Resueltos) para encontrar material de estudio complementario al presentado en esta publicación.