programación lineal Archivos - Página 11 de 17

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]

Aprueba tu Examen con el Libro de Apuntes de Programación Lineal

¿Te gustaría disponer de un Apunte con ejercicios resueltos explicados de modo sencillo que te permita aprobar tu Examen de Programación Lineal?

El Libro de Apuntes de Programación Lineal que necesitas esta aquí y ha sido diseñado especialmente para aquellos alumnos que se encuentran cursando una cátedra inicial de Investigación de Operaciones (o Investigación Operativa) que buscan resolver de forma sencilla aquellas preguntas frecuentes relacionadas a los modelos de optimización lineales.

El material contenido en este Apunte es original, es decir, no ha sido tomado de libros o apuntes de terceros. Para ello hemos desarrollado una labor creativa en el diseño de los ejercicios que estamos seguros sabrás apreciar.

El Libro de Apuntes contiene los siguientes capítulos:

UNIDAD 1: FORMULACIÓN Y RESOLUCIÓN GRÁFICA DE MODELOS DE PROGRAMACIÓN LINEAL EN 2 VARIABLES
UNIDAD 2: ANÁLISIS DE SENSIBILIDAD EN PROGRAMACIÓN LINEAL UTILIZANDO EL MÉTODO GRÁFICO
UNIDAD 3: RESOLVER UN MODELO DE PROGRAMACIÓN LINEAL CON SOLVER DE EXCEL
UNIDAD 4: INTERPRETACIÓN DE LOS INFORMES DE SENSIBILIDAD OBTENIDOS CON SOLVER DE EXCEL
UNIDAD 5: MÉTODO SIMPLEX
UNIDAD 6: MÉTODO SIMPLEX DE 2 FASES
UNIDAD 7: CASOS ESPECIALES DE LA PROGRAMACIÓN LINEAL DETECTADOS CON EL MÉTODO SIMPLEX

Beneficios

Eso no es todo!

~~Por la compra del Apunte recibirás GRATIS un archivo Excel con Ejercicios de Programación Lineal resueltos con Solver de Excel~~.

¿Quieres tener el archivo PDF con el Libro de Apuntes de Programación Lineal?

[sociallocker]MUCHAS GRACIAS!. DESCARGA AQUÍ EL APUNTE DE PROGRAMACIÓN LINEAL[/sociallocker]

Nuestros Usuarios nos Respaldan

Desde Febrero de 2012 el Libro de Apuntes de Programación Lineal ha sido descargado por más de ~~57.000~~ 100.000 usuarios de distintos países los cuales se han mostrados muy satisfechos por el material recibido. Esto ha permitido consolidar nuestro sitio web como una de las principales referencias sobre la Gestión de Operaciones e Investigación de Operaciones para estudiantes.

Cómo descargar e instalar Premium Solver en Excel 2010

Solver es sin duda junto a What’sBest! la herramienta más popular para resolver modelos de optimización utilizando Microsoft Excel como plataforma. En efecto la versión gratuita que utilizamos de Solver es desarrollada por Frontline Systems Inc, empresa que ofrece un importante número de herramientas y motores de resolución que son de gran utilidad para enfrentar problemas de naturaleza real aplicados en la industria.

En el siguiente artículo nos referiremos a cómo descargar e instalar la versión de prueba de Premium Solver que está disponible en forma gratuita por un período de 15 días y la cual nos permite enfrentar la resolución de modelos de Investigación Operativa significativamente mayores tanto en el número de variables de decisión como restricciones, que aquellos posibles de abordar con la versión tradicional de Solver.

Adicionalmente, al contar con algoritmos de resolución mejorados se favorece la confiabilidad de las soluciones encontradas y los tiempos de procesamiento.

A continuación presentamos el procedimiento detallado para descargar e instalar la versión de prueba de Premium Solver en un computador con Excel versión 2010.

Paso 1: Ingresar a Frontline Systems Inc, completando la información requerida en el formulario de suscripción.

Paso 2: Descargar la versión de prueba compatible con la versión de Excel que dispongamos. En este tutorial se muestra la instalación de la versión de 64 bits. Una vez que estamos seguros de nuestra elección seleccionamos “Download Now”.

Si tienes Excel 2010 y deseas saber de cuántos bits es la versión que utilizas ejecuta Excel y en el menú Archivo selecciona la opción Ayuda. En la esquina inferior derecha se mostrará la cantidad de bits de tu versión bajo el titulo “Acerca de Microsoft Excel”.

Paso 3: Revisa tu cuenta de correo electrónico (la que proporcionaste en el formulario de suscripción del Paso 1) y anota las 2 contraseñas que te han sido asignadas (en la imagen a continuación éstas han sido protegidas con color azul y rojo).

Paso 4: Una vez completada la descarga ejecuta el archivo “SolverSetup64.exe” (o el nombre que corresponda según la versión de Excel que estés utilizando).

A continuación se desplegará el asistente para la instalación del programa. (Seleccionar “Next”).

Ahora debemos ingresar los password que hemos recibido por correo electrónico (Paso 3) para continuar con la activación del programa:

Luego debemos aceptar los acuerdos de la licencia del programa y seleccionar “Next”.

En estos momentos la licencia del programa ya ha sido activada y continuamos el proceso de la instalación seleccionando “OK”.

Se debe seleccionar la carpeta donde se instalará el programa y podemos en este punto seleccionar simplemente aquella ubicación que el programa selecciona por defecto.

Es el momento de seleccionar el producto que deseamos activar. En este caso hemos seleccionado “Premium Solver Pro” que corresponde a la versión mejorada de la versión de Solver que se utiliza generalmente para fines académicos.

El asistente de instalación nos solicitará confirmar la instalación que hemos seleccionado (“Install”).

Finalmente hemos completado la instalación del programa Premium Solver Pro y ya estamos en condiciones de poder utilizarlo para resolver modelos de optimización utilizando Microsoft Excel como plataforma.

Cambio de Variables en un Modelo de Programación Lineal

Cuando se desea resolver un modelo de Programación Lineal es importante tener en cuenta que generalmente se dispone de varias alternativas las cuales difieren en dificultad y por tanto es necesario evaluar cada una en su mérito para luego decidir qué estrategia algorítmica utilizar.

Este concepto es válido tanto para la resolución de pequeños modelos de optimización lineales como los que usualmente se consideran para fines académicos, como también para modelos de mayor tamaño, donde seleccionar una estrategia adecuada favorece los tiempos y confiabilidad de la resolución computacional.

A continuación presentaremos un problema de Programación Lineal en 2 variables que resulta de interés su resolución:

Notar que existen distintas estrategias que nos permiten abordar el problema anterior. Por ejemplo, lo podríamos resolver gráficamente (Método Gráfico en Programación Lineal) o utilizar el Método Simplex de 2 Fases, agregando variables de holgura para las restricciones 1, 2 y 3 y variables de exceso y auxiliares para las restricciones 4 y 5. También por cierto se podría definir el Problema Dual del ejemplo anterior y luego intentar su resolución, lo que a primera vista no sería de mayor ayuda.

Ahora bien, si una variable de decisión x debe cumplir la restricción x≥a, para una constante a positiva, se puede imponer un cambio de variables y=x-a, que define una nueva variable y que tiene solo una restricción de no negatividad y simplifica imponer la primera como una restricción general en la aplicación del Método Simplex.

El concepto anterior nos permite hacer lo siguiente: Y1=X1-20>=0; Y2=X2-20>=0. Es decir X1=Y1+20 y X2=Y2+20. En consecuencia podemos reescribir el modelo original de la siguiente forma:

Reduciendo términos semejantes se obtiene:

Notar que este nuevo modelo de optimización se puede resolver de forma directa a través del Método Simplex, incorporando las variables no negativas Y3, Y4 e Y5 como holguras de las restricciones 1, 2 y 3, respectivamente. De esta forma el problema en su forma estándar proporciona la siguiente tabla inicial: (Notar que el valor de la función objetivo inicialmente es 1.100 debido a que dicha constante se obtiene luego de realizar el cambio de variables)

La variable Y1 entra a la base al ser la variable no básica con el costo reducido más negativo. Luego para determinar la variable básica que deja la base calculamos el mínimo cuociente: Min {420/6; 140/1; 160/2} = 70 ==>Y3 sale de la base. Se realiza una iteración del Método Simplex:

Ahora Y2 entra a la base al ser la única variable no básica con costo reducido negativo. A continuación la variable que deja la base se determina a través del criterio del mínimo cuociente: Min {70/1/2; 70/3/2; 20/1} = 20 ==>Y5 sale de la base. Se realiza una nueva iteración:

Se ha alcanzado la tabla óptima donde Y1=60 e Y2=20 con valor óptimo V(P)=3.400. Reemplazando en las variables originales se obtiene la solución óptima del problema original: X1=60+20=80 y X2=20+20=40. Se puede corroborar que esta solución óptima al ser evaluada en la función objetivo del problema inicial proporciona el valor óptimo del modelo de programación lineal: Max 30*(80)+25*(40)=3.400, lo que permite garantizar la equivalencia del procedimiento utilizado.