Un modelo de Programación Lineal (PL) considera que las variables de decisión tienen un comportamiento lineal, tanto en la función objetivo como restricciones del problema. En este sentido, la Programación Lineal es una de las herramientas más utilizadas en la Investigación Operativa debido a que por su naturaleza se facilitan los cálculos y en general permite una buena aproximación de la realidad.
Los Modelos Matemáticos se dividen básicamente en Modelos Deterministas (MD) o Modelos Estocásticos (ME). En el primer caso (MD) se considera que los parámetros asociados al modelo son conocidos con certeza absoluta, a diferencia de los Modelos Estocásticos, donde la totalidad o un subconjunto de los parámetros tienen una distribución de probabilidad asociada. Los cursos introductorios a la Investigación Operativa generalmente se enfocan sólo en Modelos Deterministas.
Las aplicaciones de los modelos de Programación Lineal abarcan diversas áreas de la Ingeniería. A continuación un breve compendio de alguna de sus aplicaciones y referencias de interés para el lector:
El problema consiste en decidir cuántas unidades trasladar desde ciertos puntos de origen (platas, ciudades, etc) a ciertos puntos de destino (centros de distribución, ciudades, etc) de modo de minimizar los costos de transporte, dada la oferta y demanda en dichos puntos. Se suponen conocidos los costos unitarios de transporte, los requerimientos de demanda y la oferta disponible.
Por ejemplo, suponga que una empresa posee dos plantas que elaboran un determinado producto en cantidades de 250 y 400 unidades diarias, respectivamente. Dichas unidades deben ser trasladadas a tres centros de distribución con demandas diarias de 200, 200 y 250 unidades, respectivamente. Los costos de transporte (en $/unidad) son:
Se requiere formular un modelo de Programación Lineal que permita satisfacer los requerimientos de demanda al mínimo costo.
Variables de Decisión:
Xij: Unidades transportadas desde la planta i (i=1, 2) hasta el centro de distribución j (j=1, 2, 3)
Función Objetivo: Minimizar el costo de transporte entre las plantas y los centros de distribución dado por:
Minimizar 21X11 + 25X12 + 15X13 + 28X21 + 13X22 + 19X23
Restricciones:
Satisfacer los requerimientos de Demanda de los Centros de Distribución:
- X11+ X21 = 200
- X12 + X22 = 200
- X13 + X23 = 250
Sujeto a la Oferta o Capacidad de Producción de las Plantas::
- X11+ X12 + X13 = 250
- X21 + X22+ X23 = 400
No Negatividad:
El siguiente diagrama permite una visualización de la situación anterior:
A continuación una descripción de la implementación computacional y resolución del problema anterior utilizando el complemento Solver de Microsoft Excel:
1. Abrir una Planilla de Cálculo de Excel. Asegúrese de tener instalado el complemento Solver. Luego construya una planilla como la de la imagen de referencia. Se han marcado con amarillo las celdas cambiantes (variables de decisión) y con color azul la celda de la función objetivo.
Notar que algunas celdas en la imagen anterior consideran fórmulas:
- F7=SUMA(C7:E7)
- F8=SUMA(C7:E7)
- C9=SUMA(C7:C8)
- D9=SUMA(D7:D8)
- E9=SUMA(E7:E8)
2. Ingrese la función objetivo, celdas cambiantes y restricciones en la ventana de Parámetros de Solver. Seleccione también la opción Convertir variables sin restricciones en no negativas. Si utiliza la mismas celdas de la imagen anterior, usted debería obtener lo siguiente:
3. Seleccione Resolver. Obtendrá la solución al problema y podrá requerir los Informes de Solver. Finalmente presione Aceptar para obtener el o los informes de interés.
Finalmente, se obtienen los informes de confiabilidad (o sensibilidad) los cuales entregan información relevante en cuanto a los precios sombra asociados a las restricciones, intervalos de variación de garantizan la validez del precio sombra, intervalo de variación para los coeficientes de la función objetivo, etc.
APLICACIONES DE LA PROGRAMACIÓN LINEAL EN PRODUCCIÓN
COMBINACIÓN ÓPTIMA DE BIENES: A menudo las técnicas de PL permiten decidir sobre la cantidad más adecuada que una empresa debe producir de cada uno de sus productos a fin maximizar los beneficios sin dejar de cumplir con unos determinados requisitos (financieros, de demanda, contractuales, de disponibilidad de materias primas, etc.).
PLANIFICACIÓN DE LA PRODUCCIÓN: El establecer un plan de producción para un período de semanas o meses resulta ser una tarea difícil e importante en la mayoría de las plantas de producción. El director de operaciones debe considerar muchos factores: mano de obra, costes de inventario y almacenamiento, limitaciones de espacio, demanda, etc. Por lo general la mayoría de las plantas producen más de un bien, con lo que la tarea anterior se complica aún más. Como veremos en el siguiente ejemplo, el problema de la planificación se asemeja bastante al de la combinación óptima de bienes, pudiendo ser el objetivo maximizar beneficios o bien minimizar los costes de producción más almacenamiento.
APLICACIONES DE LA PROGRAMACIÓN LINEAL A LA DISTRIBUCIÓN DE ÁREAS
ASIGNACIÓN DE TRABAJOS: El objetivo aquí será asignar de la forma más eficiente posible un trabajo a cada empleado o máquina. Ejemplos de este tipo de asignación serían la distribución de coches patrulla por las calles de una ciudad o la destino de cada jefe de ventas a una determinada zona geográfica. El objetivo puede ser bien minimizar los tiempos o costes de desplazamiento, o bien maximizar la efectividad de las asignaciones.
Aparte de poder utilizar los algoritmos tradicionales (Simplex y Karmarkar), este tipo de problemas también puede resolverse usando técnicas especialmente diseñadas para sus características como el método húngaro, el cual necesita de menos iteraciones para dar con la solución.
Una propiedad particular de los problemas de asignación es que tanto los coeficientes tecnológicos cómo los términos independientes (right-hand-side) siempre toman el valor 1. Además, todas las variables serán binarias, tomando el valor 1 si la asignación propuesta se lleva a cabo y 0 en caso contrario.
PLANIFICACIÓN DE HORARIOS: La planificación de horarios intenta dar una respuesta efectiva a las necesidades de personal durante un período concreto de tiempo. La aplicación de la PL a este tipo de problemas resulta especialmente útil cuando los directivos disponen de cierta flexibilidad a la hora de asignar tareas a empleados polifuncionales. Un sector típico donde se hace uso de la PL para tomar decisiones sobre planificación de horarios son las entidades bancarias.
APLICACIONES DE LA PROGRAMACIÓN LINEAL A LAS FINANZAS
SELECCIÓN DE UNA CARTERA DE VALORES: Un problema al que se tienen que enfrentar de forma habitual los directivos de bancos, fondos de inversión, y compañías de seguros es la selección de una serie de inversiones concretas de entre la gran variedad de alternativas existentes en el mercado. Por norma general, el objetivo de estos directivos es maximizar los beneficios esperados de estas inversiones, las cuales se ven sometidas a un conjunto de restricciones, algunas legales y otras provenientes de la propia empresa (como puede ser el nivel de riesgo que se desea asumir o la cantidad máxima que se permite invertir).
APLICACIONES DE LA PROGRAMACIÓN LINEAL A LA LOGÍSTICA
El PROBLEMA DEL TRANSPORTE: El llamado problema del transporte se refiere al proceso de determinar el número de bienes o mercancías que se han de transportar desde cada uno de los orígenes a cada uno de los destinos posibles. El objetivo suele ser minimizar costes de transporte, y las restricciones vienen dadas por las capacidades productivas de cada origen y las necesidades de cada destino. Este tipo de problema es un caso específico de PL, por lo que existen métodos y algoritmos especiales que facilitan su resolución (Regla de la Esquina NorOeste, Método de Vogel, Método de Paso Secuencial, y Método de distribución modificada o MODI).
APLICACIONES DE LA PROGRAMACIÓN LINEAL A MEZCLAS
El PROBLEMA DE LA DIETA: Este problema representa una de las primeras aplicaciones de la PL, y comenzó a utilizarse en los hospitales para determinar la dieta más económica con la que alimentar a los pacientes a partir de unas especificaciones nutritivas mínimas. En la actualidad también se aplica con éxito en el ámbito agrícola con la misma idea de encontrar la combinación óptima de alimentos que, logrando un aporte nutritivo mínimo, suponga el menor coste posible.
