APLICACIONES DIVERSAS DE LA PROGRAMACION LINEAL

Modelos y Aplicaciones de la Programación Lineal

By Investigación de Operaciones on 6 mayo, 2015 in Investigación Operativa

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:

1. Problema de Transporte: (Referencia: Hitchcock, 1941; Kantorovich, 1942; Koopmans 1947).

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:

• Xij>= 0   i=1,2 y j=1,2,3

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.

Programación Lineal

Cuando se habla de programación lineal (PL) se refiere a varias técnicas matemáticas empleadas para asignar, de forma óptima, los recursos limitados a distintas demandas, tareas, operaciones o productos que compiten entre ellos, es decir, la programación de actividades para obtener un resultado óptimo. La programación lineal utiliza un modelo matemático para describir y formular el problema; y el aspecto de lineal se refiere a que todas la funciones matemáticas del modelo deben ser funciones lineales (Ecuaciones o Inecuaciones).

Aplicaciones típicas:

• Planeación de operaciones y ventas para encontrar el programa de producción que tenga el costo mínimo.
• Análisis de la productividad en la producción o servicios, considerar el grado de eficiencia con el cual los establecimientos de servicios y de manufactura están utilizando sus recursos en comparación con la unidad que tiene mayor desempeño.
• Planeación de los productos, encontrar la mezcla óptima de productos, considerando que varios productos requieren diferentes recursos y tienen distintos costos.
• Rutas de los productos se refiere a encontrar el camino óptimo para fabricar un producto que debe ser procesado en secuencia.
• Programación de vehículos (método de transporte), encontrar la ruta óptima para utilizar los recursos de transporte que involucren el movimiento de productos o materiales de varios puntos llamados origen hacia otros puntos llamados destinos.
• Control de procesos, minimizar el volumen de desperdicio de material generado en los procesos de producción, tales como cortes de acero, pieles o telas.
• Control de inventario, encontrar la combinación óptima de productos a mantener en existencia dentro de una red de almacenes para garantizar el abastecimiento de las demandas de las líneas de producción.
• Otras aplicaciones que se pueden mencionar están la programación de la distribución de embarques, los estudios para ubicar una planta entre distintas alternativas y los programas de manejo de materiales con un costo mínimo.

Construcción de un modelo de programación lineal

Cualquier modelo de PL se compone de tres elementos básicos:

1. Variables de decisión, que se trata de determinar.
2. Función objetivo (meta), que se busca optimizar ya sea maximizar (beneficios) o minimizar (costos).
3. Restricciones que se deben satisfacer.

Para fines didácticos, se visualizan estos elementos básicos a través de un ejemplo de mezcla de productos. La empresa FICTICIA, S.A. elabora dos tipos de productos Alpha y Beta, los cuales requieren para su elaboración de dos materias primas (P y Q). Alpha utiliza 6 toneladas de P y requiere 1 tonelada de Q, mientras que Beta usa 4 toneladas de P y 2 toneladas de Q. La empresa disponone diariamente de 24 toneladas de P y de 6 toneladas de Q. El equipo de IO ha determinado que la contribución de Alpha es 5,000 y Beta aporta 4,000 dólares de beneficio y según una encuesta de mercado proporcionada por el equipo de marketing el producto Beta tiene una demanda máxima de 2 toneladas. Así mismo, se determinó que la demanda diaria de Beta no puede exceder a la demanda de Alpha por más de una (1) tonelada.

La variables de decisión de este problema están definidas por:
X1 = Producto Alpha
X2 = Producto Beta

La función objetivo se define de la siguiente manera:
Maximizar (Z) = 5 X1 + 4 X2   (en miles de dólares)

Sujeta a las siguientes restricciones:

(1) Materia prima P:   6 X1 + 4 X2 <= 24
(2) Materia prima Q:     X1 + 2 X2 <= 6
(3) Restricción 3:        - X1 +   X2 <= 1
(4) Restricción 4:                    X2 <= 2
(5) Condición:                  X1 , X2 >= 0 

Cualquier par de valores de X1, X2 que satisfaga todas las restricciones anteriormente expresadas, se considera una solución factible del modelo. Tal es el caso de la solución factible dada por X1=3 y X2=1 con un Z= 5x3 + 4x1 = 19 (miles de dólares). Posteriormente se mostrará como llegar a la solución óptima a través del método gráfico y del matemático.

Método Gráfico:

Este procedimiento plantea la construcción de una gráfica en un plano (2 ejes - 2 variables de decisión). Primeramente, se formulan las restricciones de manera matemática (paso ya cubierto). Segundo, se trazan todas las restricciones formuladas en el modelo de PL (se recomienda definir los interceptos de cada restricción a los ejes y luego trazar la recta que se define).  Nota: para el intercepto en el eje X1 se encuentra al llevar X2 a cero y para el intercepto en X2 hacemos que el valor de X1 sea cero. Por ejemplo, para la restricción (1) los interceptos son X1 = 24/6 = 4 y para X2 = 24/4 = 6.

Tercero, se define el espacio de solución factible, el cual está formado por la región de puntos que cumplen con todas las restricciones. Se deben marcar los puntos extremos del espacio de solución, es decir, los puntos de intersección de dos o más rectas y que pertenecen al espacio de solución delimitado.

Por último, se traza la recta definida por la ecuación objetivo (se recomienda utilizar la pendiente o se puede utilizar dos Z convenientes para simular el comportamiento de esta recta), luego se extiende esta recta hasta el punto más alejado en la región factible, este punto es el que determina la solución óptima del modelo. Para el ejemplo formulado de la empresa FICTICIA, S.A. se encuentra que la solución óptima se define por X1 = 3 producto Alpha y X2 = 1.5 producto Beta con un Z = 21 (miles). Ver gráfica a continuación:

En resumen, el enfoque gráfico consiste en la secuencia de pasos siguientes:

1. Plantear el problema de programación en términos matemáticos.  
2. Trazar las ecuaciones (inecuaciones) formuladas para las restricciones.
3. Determinar el área de factibilidad (espacio de solución).
4. Trazar la función objetivo. 
5. Encontrar el punto óptimo. 

Método Matemático:

Como se pudo observar, la solución optima de cualquier modelo de programación lineal se encuentra en uno de los puntos o vértices que conforman el polígono del espacio solución, los cuales se forman por las intersecciones de las restricciones del modelo. El enfoque matemático aprovecha esa situación, y emplea el álgebra para encontrar esos puntos de intersección a través de la solución de cada sistema de ecuaciones (inecuaciones) que se forma con cada par de restricciones y luego evaluando esos puntos en la función objetivo se determina la solución óptima, ya sea el mayor valor para los casos de maximización, como el menor valor para los casos de minimización.

La conjugación del método gráfico con el matemático es bastante utilizada. En el sentido, que el método gráfico permite simplificar la cantidad de pares de sistemas de ecuaciones que se deben resolver, reduciendo este número a un sólo sistema de ecuaciones, el cual se puede resolver por cualquier método matemático de su conveniencia. Se recomienda el enfoque de reducción o el de sustitución por su facilidad de encontrar la solución al sistema. En el ejemplo prototipo, el sistema de ecuaciones lo conforma las restricciones (1) y (2), cuya solución arroja el par ordenado que se constituye en la solución óptima. Intenta verificarlo!

Existen diversas aplicaciones y/o paquetes de software en el mercado que se pueden descargar de manera gratuita. Se les recomienda a los estudiantes para la solución de problemas de programación lineal buscar por alguno de estos:

• LINDO / LINGO
• MPL / CPLEX
• TORA
• Excel Solver