El método de multiplicadores de Lagrange (el cual es generalizado por las condiciones de optimalidad de Karush-Kuhn-Tucker) permite abordar la resolución de modelos de programación no lineal que consideran restricciones de igualdad. En este sentido y como resulta natural, el dominio de soluciones factibles considerará exclusivamente aquellas soluciones que permiten verificar el cumplimiento de la igualdad de dichas restricciones. Por el contrario, un problema de optimización que considera inecuaciones como restricciones, sólo requiere que éstas se cumplan y no necesariamente se deberá forzar el cumplimiento de ellas en igualdad (activas).
En general las condiciones de Lagrange se aplican a un problema que tiene la siguiente estructura:
Que da origen a la función Lagrangiana asociada a dicho problema:
Consideremos el siguiente problema de Programación No Lineal restringido que nos permitirá ilustrar la aplicación del método de Lagrange.
Notar que el problema adopta la estructura estándar previamente descrita y considera una única restricción de igualdad. No se incluye en particular condiciones de no negatividad, que en caso de estar presentes justificarían la aplicación del Teorema de Karush-Kuhn-Tucker.
En este contexto, un mínimo local para el problema propuesto debe satisfacer las condiciones necesarias de primer orden de Lagrange:
Que da origen al siguiente sistema de ecuaciones:
Donde la resolución es trivial y corresponde a x1=2, x2=2 y λ1=-4. Notar que el multiplicador de Lagrange asociado a una restricción de igualdad es libre de signo, en consecuencia la solución propuesta satisface las condiciones necesarias de primer orden.
Adicionalmente se cumplen las condiciones de segundo orden pues:
Es positiva definida (función objetivo estrictamente convexa y restricción lineal que define un conjunto convexo). Luego, el problema es convexo y en consecuencia x1=2 y x2=2 es mínimo global y solución óptima del problema. Este resultado por cierto es consistente con la representación gráfica del problema, donde la solución óptima corresponde al punto A, donde la restricción (color naranjo) es tangente a la curva de nivel que representa a la circunferencia de menor radio que intercepta el dominio de soluciones factibles.
Según hemos abordado en artículos previos, en la actualidad la formación profesional ya no esta limitada al aula de clases (enfoque tradicional), existiendo numerosas alternativas que permiten alcanzar grados académicos a través de modalidades de estudios semipresenciales o definitivamente en una opción online. En este contexto es importante tener especial atención en la correcta selección de la institución de educación superior que patrocina el programa y el plan de estudios correspondiente.
El curso de producción (con el apoyo metodológico de UOC) es una interesante alternativa que mediante un enfoque online ofrece las principales herramientas de la gestión de operaciones y calidad. El curso consta de una etapa previa que consiste en un taller virtual que permite a los alumnos familiarizarse con el enfoque de educación online para posteriormente pasar a los cursos propiamente tal, de modo de adquirir conocimientos que permitan tomar decisiones óptimas en el ámbito estratégico, táctico y operativo, en el contexto de la producción y Gestión de Calidad.
En la Gestión de Proyectos uno de los aspectos claves es determinar los costos asociados a terminar el proyecto en un tiempo determinado. Del mismo modo, resulta de particular interés poder enfrentar de forma eficiente el problema de cómo reducir la duración del mismo de la forma más económica posible, partiendo de la premisa que ciertas actividades eventualmente se podrían desarrollar en un tiempo menor al estimado inicialmente luego de asignar una mayor cantidad de recursos. En este contexto el siguiente artículo aborda la problemática anterior a través de la formulación y resolución computacional de un modelo de optimización lineal.
Consideremos el siguiente proyecto que consta de 12 tareas estrictamente necesarias, donde la relación de predecesores, tiempos (en semanas) y costos se resume en la tabla a continuación:
Por ejemplo la actividad I tiene puede comenzar una vez completadas las actividades F y H y su tiempo estimado es de 1,5 semanas con un costo normal de $75. Sin embargo la actividad I se puede apurar (lo que comúnmente se conoce como “crash” o “crashing”) de modo que su duración pueda ser de 0,5 semanas pero con un costo mayor de $135. En consecuencia la máxima reducción permisible para dicha tarea es de 1 semana (1,5 – 0,5 semanas) con un costo adicional de $60. Asumiremos adicionalmente que existe proporcionalidad entre el tiempo de reducción y el costo adicional, por ejemplo, si quisiéramos reducir la actividad I en 0,5 semanas (es decir, pasar de 1,5 a 1,0 semanas) el costo de la actividad sería $105 ($75+0,5*$60) y el costo adicional (sobre el costo normal) es de $30.
A continuación determinamos la duración del proyecto utilizando el Método de Ruta Crítica (CPM), considerando los tiempos normales estimados para cada actividad.
El proyecto tiene una duración estimada de 15,5 semanas y existe una única ruta crítica: A-B-D-G-H-I-K-L (notar que todas las actividades en esta ruta tienen holgura igual a cero). El costo del proyecto es de $2.620 y se obtiene simplemente sumando los costos normales de cada una de las actividades. La notación que hemos utilizado es:
Donde IC: Inicio más Cercano; TC: Término más Cercano; IL: Inicio más Lejano; TL: Término más Lejano; TN: Tiempo Normal, HOLG: Holgura. De esta forma, por ejemplo, la actividad I tiene un tiempo normal de 1,5 semanas y holgura igual a cero, es decir, si se retrasa esta actividad el proyecto también se retrasará.
En este contexto, el siguiente modelo de Programación Lineal permite abordar de forma óptima el problema de cómo reducir la duración del proyecto de la forma más económica posible, mediante la reducción del tiempo de las actividades (en particular de las actividades pertenecientes a la(s) ruta(s) crítica(s)). Cabe destacar que en la actualidad existen softwares que facilita este tipo de procedimientos (Crashing) como por ejemplo WINQSB.
Variables de Decisión:
Parámetros:
Función Objetivo: Se buscar minimizar el costo adicional asociado al proyecto luego de hacer el “crashing” necesario para completar el proyecto en un tiempo determinado. Notar que podríamos agregar en la función objetivo como constante el costo normal del proyecto ($2.620) en donde en dicho caso la interpretación del valor óptimo sería el costo total del proyecto que tiene duración de K semanas.
Restricciones:
Cada actividad se puede reducir (de ser posible) dentro del límite máximo de reducción permisible:
Relaciones de predecesores entre las actividades y el tiempo de inicio y reducción:
Por ejemplo en conjunto las inecuaciones (3) y (4) representan que la semana de inicio para la actividad D será mayor o igual a la semana de término (luego de una eventual reducción) de la que termine más tarde entre sus actividades predecesoras (B y C). Adicionalmente hemos definido una actividad “ficticia” o de término llamada “M” la cual tiene como predecesoras a aquellas actividades que terminan una ruta para el proyecto (no necesariamente crítica) y nos permitirá estimar la duración del proyecto.
Definición del tiempo objetivo para el proyecto:
En la resolución computacional con Solver de Excel se puede simular para distintos valores del parámetro K de modo de ver cómo cambian los resultados. La mínima duración del proyecto estará dada por el menor valor de K que permite generar una instancia factible para el modelo de optimización.
No negatividad de las variables de decisión:
Los resultados se muestran en la tabla a continuación donde la mínima duración del proyecto corresponde a 8,5 semanas con un costo total de $3.295 ($675 adicional al costo normal del proyecto). En las celdas color amarillo (variables de decisión) se puede apreciar la solución óptima donde queda explícito cuándo comienza la actividad y cuánto se reduce respecto a su tiempo normal. Por ejemplo la actividad G comienza al cabo de 2,5 semanas (a contar del inicio del proyecto) y su duración normal se reduce en 1,5 semanas (es decir pasamos de un tiempo normal de 3 a 1,5 semanas).
¿Quieres tener el archivo Excel con la resolución en Solver de este problema?
Una de las aplicaciones clásicas de los modelos de Programación Lineal son los problemas de mezcla de productos. Si la calidad de un producto que se procesa mediante la mezcla de determinados insumos se puede aproximar de forma razonable a través de una proporción, entonces un modelo de optimización lineal puede resultar de utilidad. El ejemplo a continuación muestra dicha situación para el caso de una refinería:
Problema de Mezcla de Productos en Programación Lineal
Una refinería de petróleos produce dos tipos de gasolina sin plomo: regular y extra, las cuales vende a los distribuidores en US$12 y US$14 por barril, respectivamente. Ambos tipos se preparan a partir del inventario de petróleo nacional refinado y de petróleo importado refinado que tiene la empresa (es decir mediante mezcla), las que deben cumplir las especificaciones que se presentan en la siguiente tabla:
Las características del inventario de petróleos refinados son las siguientes:
Se requiere formular y resolver un modelo de Programación Lineal que permita maximizar el ingreso semanal de la refinería, satisfaciendo los requerimientos previamente detallados.
Variables de Decisión:
Xnr: Barriles de petróleo nacional utilizados en la producción de gasolina regular
Xne: Barriles de petróleo nacional utilizados en la producción de gasolina extra
Xir: Barriles de petróleo importado utilizados en la producción de gasolina regular
Xie: Barriles de petróleo importado utilizados en la producción de gasolina extra
Función Objetivo: Se busca maximizar los ingresos semanales que percibe la refinería en la producción de gasolina regular y extra.
Max 12*(Xnr + Xir) + 14*(Xne + Xie)
Restricciones:
Presión de Vapor: El promedio ponderado de la presión de vapor de los distintos tipos de petróleos que participan de la mezcla no debe superar las 23 unidades (para cada tipo de gasolina).
(25Xnr + 15Xir ) / (Xnr + Xir) <= 23
(25Xne + 15Xie ) / (Xne + Xie) <= 23
Octanaje Mínimo: El promedio ponderado del octanaje de los distintos tipos de petróleos que participan de la mezcla debe ser al menos 88 y 93 unidades para la gasolina regular y extra, respectivamente.
(87Xnr + 98Xir ) / (Xnr + Xir) >= 88
(87Xne + 98Xie ) / (Xne + Xie) >= 93
Demanda Mínima y Máxima: Para cada gasolina se debe producir semanalmente una cantidad de barriles entre el mínimo y el máximo permitido.
50.000 <= Xnr + Xir <= 100.000
5.000 <= Xne + Xie <= 20.000
Inventario: Para la producción de gasolina regular y extra se debe respetar la disponibilidad de barriles de petróleo nacional e importado.
Xnr + Xne <= 40.000
Xir + Xie <= 60.000
No Negatividad: Las variables de decisión naturalmente deben adoptar valores mayores o iguales a cero.
Xnr, Xne, Xir, Xie >= 0
Al implementar el modelo de optimización anterior en Solver se alcanza la siguiente solución óptima y valor óptimo:
Se deben destinar 30.909,09 barriles de petróleo nacional para la producción de gasolina regular, 9.090,91 barriles de petróleo nacional para la producción de gasolina extra, 49.090,91 barriles de petróleo importado para la producción de gasolina regular y 10.909,09 barriles de petróleo importado para la producción de gasolina extra. La política de producción anterior permite generar un ingreso semanal de US$1.240.000.
Una recomendación en la carga computacional es rescribir las restricciones que incluyan proporciones de forma equivalente, de modo de evitar divisiones entre celdas cambiantes (variables de decisión) y adicionalmente denominadores que adopten inicialmente un valor igual a cero. Por ejemplo la restricción: (25Xnr + 15Xir ) / (Xnr + Xir) <= 23 se puede representar de forma análoga de la siguiente forma: (25Xnr + 15Xir ) -23 (Xnr + Xir) <= 0. De esta forma se puede corrobar, por ejemplo, que en la solución óptima la presión de vapor que alcanza la producción de barriles de gasolina regular es de: (25*30.909,09 + 15*49.090,91 ) / (30.909,09 + 49.090,91)=18,8636 (aprox) que es menor o igual al límite de 23 unidades.
¿Quieres tener el archivo Excel con la resolución en Solver de este problema?.
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:
