Para empezar, es importante recordar que en un modelo de programación lineal, se busca encontrar la solución óptima que maximiza o minimiza una función objetivo, sujeta a un conjunto de restricciones. En el método gráfico, se representa gráficamente la función objetivo y las restricciones en un plano cartesiano, formando una región factible que contiene todas las soluciones posibles. Sin embargo, en algunos casos, la solución óptima no siempre se encuentra en uno de los vértices de la región factible. Estos son los denominados casos especiales de programación lineal.
En ocasiones, pueden existir múltiples soluciones que maximizan o minimizan la función objetivo de un modelo de programación lineal, es decir, múltiples soluciones óptimas. La elección de la solución en un contexto de aplicación práctico dependerá tanto de la sensibilidad de las restricciones activas como de los factores propios del sistema que no se consideran en un modelo matemático.
Por ejemplo, supongamos que tenemos el siguiente modelo de programación lineal:
La ebanistería «López S.A.S» ha recibido una gran cantidad de partes prefabricadas para la elaboración de mesas, pero no ha podido iniciar un plan de producción enfocado en ellas debido a la alta demanda de sus otros productos. Las mesas que se pueden elaborar con las partes prefabricadas son de dos modelos: A y B. Estas mesas solo requieren ser ensambladas y pintadas.
Esta semana se ha determinado dedicar 10 horas a ensamblar y 8 horas a pintar para elaborar la mayor cantidad de mesas posibles, teniendo en cuenta que cada mesa modelo A requiere 2 horas de ensamble y 1 hora de pintura, mientras que cada mesa modelo B requiere 1 hora de ensamble y 2 horas de pintura. Si el margen de utilidad es de $20000 por cada mesa modelo A y $10000 por cada mesa modelo B, determine el modelo de producción adecuado para esta semana.
Variables
x = Mesas modelo A a fabricar esta semana
y = Mesas modelo B a fabricar esta semana
Restricciones
2x + y <= 10 «Horas de ensamble»
x + 2y <= 8 «Horas de pintura»
x >= 0 «No negatividad»
y >= 0 «No negatividad»
Función objetivo
Zmax = 20000x + 10000y
Solución gráfica:
Como se puede observar, la región factible tiene dos vértices que maximizan la función Z: C(4,2) y D(6,0). Ambas soluciones son óptimas, ya que maximizan la función Z dentro de las restricciones del modelo. En este caso, la elección de la solución dependerá de factores propios del sistema que no se consideran en el modelo matemático, como por ejemplo la disponibilidad de recursos o el costo de producción; del mismo modo, sería conveniente evaluar la sensibilidad de las restricciones activas en cada vértice.
| Solución óptimas | 20000(x) | 10000(y) | Z |
| Vértice C | 20000(4) | 10000(2) | 100000 |
| Vértice D | 20000(5) | 10000(0) | 100000 |
En este caso se da una condición particular, ya que los vértices son consecutivos. Esto implica que cada punto en el tramo que une a C y a D son soluciones óptimas.
Con la ayuda de GeoGebra, se puede mover la barra de desplazamiento que representa la utilidad y evaluar que la función objetivo alcanza el máximo de 100000 tanto en C como en D, así como en cualquier punto del tramo CD. Esto demuestra que en este caso existen múltiples soluciones óptimas y que cualquier punto en el tramo CD es una solución válida.
Otra de las variantes que presentan los modelos de programación lineal es la solución óptima no acotada, es decir, problemas con infinitas soluciones óptimas. Dada la naturaleza finita de las restricciones en los contextos reales, estos problemas suelen deberse a un mal planteamiento de las restricciones, pero en el mundo académico es común evaluar este tipo de problemas.
Por ejemplo, supongamos que tenemos el siguiente modelo de programación lineal:
La compañía comercializadora de bebidas energéticas «WILD» está promocionando dos nuevas bebidas: la tipo A y la tipo B. Dado que se encuentran en promoción, se puede asegurar el cubrimiento de cualquier cantidad de demanda. Sin embargo, la empresa debe tener en cuenta dos políticas:
1. La cantidad de bebidas tipo A que se vendan no puede ser menor que la de tipo B.
2. Se deben vender por lo menos 1500 bebidas de cualquier tipo.
Estas políticas pueden ser representadas mediante restricciones en un modelo de programación lineal, que nos permitirá determinar la cantidad óptima de bebidas tipo A y B a vender en promoción.
El precio de venta de ambas bebidas es de $1800 por unidad
Es importante tener en cuenta estos supuestos y ajustar el modelo matemático en consecuencia, para obtener soluciones realistas y viables en un contexto de aplicación práctico.
Variables
x = Bebidas tipo A a vender en promoción
y = Bebidas tipo B a vender en promoción
Restricciones
x >= y «Políticas de ventas»
x + y >= 1500 «Horas de pintura»
x >= 0 «No negatividad»
y >= 0 «No negatividad»
Función objetivo
Zmax = 1800x + 1800y
Solución gráfica:
Como se puede observar, la región factible no está acotada, lo que significa que el conjunto de posibles soluciones factibles es infinito. En consecuencia, la solución óptima tiende a infinito, lo que hace que el modelo no tenga solución.
En este caso, el problema planteado tiene un mal planteamiento de las restricciones, lo que ha llevado a una solución no acotada. Para solucionar este problema, es necesario ajustar las restricciones del modelo para que la región factible sea acotada y tenga una solución óptima finita.
La solución infactible es un caso común en la programación lineal, y corresponde a aquellos casos en los que no existen soluciones que cumplan con todas las restricciones del modelo. Las restricciones acotan el sistema y establecen límites para alcanzar el objetivo del modelo. Cuando estas restricciones no se pueden cumplir en su totalidad, la solución es infactible.
En contexto de aplicación práctica, este caso es más común de lo que parece, y se da en escenarios en los que se plantean proporciones de oferta y demanda inviables en el modelo.
Por ejemplo, supongamos que tenemos el siguiente modelo de programación lineal:
La compañía de galletas «CAROLA» desea planificar la producción de galletas que deberá entregar a su cliente en dos semanas. Según el contrato, la empresa se compromete a entregar al menos 300 cajas de galletas, cualquiera sea su tipo (presentación D, presentación N o una combinación de ambas).
La producción de cada caja de galletas presentación D requiere 2 horas de elaboración y 3 horas de horneado, mientras que la producción de cada caja de presentación N requiere 3 horas de elaboración y 1 hora de horneado. La empresa cuenta con 550 horas para elaboración y 480 horas de horneado en las próximas dos semanas.
El margen de utilidad de cada caja de galletas presentación D es de $8500, y el margen de utilidad de cada caja de presentación N es de $8100. Para maximizar las utilidades, la empresa debe utilizar un modelo de programación lineal que le permita determinar el plan de producción adecuado.
Variables
x = Cajas de galletas de presentación D a producir en dos semanas
y = Cajas de galletas de presentación N a producir en dos semanas
Restricciones
2x + 3y <= 550 «Horas de elaboración»
3x + y <= 480 «Horas de horneado»
x + y >= 300 «Demanda según el contrato»
x >= 0 «No negatividad»
y >= 0 «No negatividad»
Función objetivo
Zmax = 8500x + 8100y
Solución gráfica:
La gráfica muestra el área sombreada que se delimita a partir de la representación de las restricciones que corresponden a los recursos de producción. Se puede apreciar cómo no existe una intersección entre las restricciones de capacidad y la restricción de demanda (sombreada de azul), lo que indica que no existen soluciones que cumplan con todas las restricciones del modelo. En este caso, se trata de una solución infactible.
Existen en los modelos de programación lineal un tipo de restricciones que no tienen ningún efecto en la determinación del conjunto solución (ni en la solución óptima). Estas restricciones se conocen como redundantes, ya que no afectan la solución del modelo.
En algunos casos, las restricciones redundantes pueden ser útiles para el análisis de sensibilidad, ya que nos permiten evaluar cómo cambia la solución óptima ante cambios en los valores de las restricciones. En lugar de eliminar estas restricciones, se pueden dejar en el modelo y marcar como inactivas. De esta manera, no afectan la solución óptima del modelo, pero se pueden utilizar para el análisis de sensibilidad.
En contextos de aplicación real, el profesional debe gestionar las restricciones del sistema, lo que implica que la restricción activa puede cambiar con el tiempo y las acciones tomadas (la restricción de un sistema se mueve, las restricciones se activan ante cambios en los parámetros). Por lo tanto, es importante considerar todas las restricciones del modelo y utilizarlas en el análisis de sensibilidad.
Por ejemplo, supongamos que tenemos el siguiente modelo de programación lineal:
La compañía «CONGELADORES MAJO» se encuentra en la necesidad de planificar su producción semanal de congeladores tipo A y B. Cada uno de ellos requiere pasar por tres operaciones: Ensamblaje, pintura y control de calidad. Los congeladores tipo A requieren 2 horas de ensamblaje, 3 kg de pintura y 4 horas de control de calidad; los congeladores tipo B requieren 3 horas de ensamblaje, 6 kg de pintura y 5 horas de control de calidad. La compañía cuenta con un margen contributivo de $102000 y $98000 por cada congelador tipo A y B respectivamente. La disponibilidad semanal de recursos se encuentra limitada a 300 horas de ensamblaje, 840 kg de pintura y 450 horas de control de calidad. A partir de esta información, se debe determinar la cantidad de unidades a producir semanalmente de cada referencia, con el fin de maximizar las utilidades.
Variables
x = Congeladores tipo A a producir semanalmente
y = Congeladores tipo B a producir semanalmente
Restricciones
2x + 3y <= 300 «Horas de ensamblaje»
3x + 5y <= 840 «Kg de pintura»
4x + 5y <= 450 «Horas de control de calidad»
x >= 0 «No negatividad»
y >= 0 «No negatividad»
Función objetivo
Zmax = 102000x + 98000y
Solución gráfica:
La gráfica muestra cómo las restricciones 1 y 2 (Horas de ensamblaje y Kg de pintura) no determinan el conjunto solución. La solución se encuentra en el vértice C(112.5, 0), con una utilidad de $11475000.
Sin embargo, denominar las restricciones que no determinan el área de factibilidad ni el punto óptimo, como redundantes o sobrantes (o excluirlas del modelo), quizá no sea la manera correcta; preferiblemente denominar estas restricciones como inactivas. Supongamos que nos encontramos en un escenario en el cual evaluamos la posibilidad de aumentar la capacidad de la restricción 3 (horas de control de calidad); es fundamental reconocer los límites en los cuales dicho incremento de capacidad activaría las restricciones 1 y 2.
En resumen, los casos especiales en programación lineal pueden darse por una mala formulación de las restricciones, la presencia de soluciones infactibles o infinitas. Es importante considerar siempre todas las restricciones del modelo y utilizar el análisis de sensibilidad para evaluar su efecto en la solución óptima.
¡Si te ha gustado este artículo sobre casos especiales en programación lineal, ¡compartelo con tus contactos!
Sábado por la mañana, Robert acaba de acompañar a su mujer a su clase de…
Reacciòn quìmica: Reuducción y oxdación Recientemente, por una de esas buenas suertes el algoritmo de…