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.
Cualquier modelo de PL se compone de tres elementos básicos:
- Variables de decisión, que se trata de determinar.
- Función objetivo (meta), que se busca optimizar ya sea maximizar (beneficios) o minimizar (costos).
- 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:
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:
- Plantear el problema de programación en términos matemáticos.
- Trazar las ecuaciones (inecuaciones) formuladas para las restricciones.
- Determinar el área de factibilidad (espacio de solución).
- Trazar la función objetivo.
- Encontrar el punto óptimo.
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
