Investigación de operaciones

Casos especiales de programación lineal (Método Gráfico)

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.

Recordemos que en el área de solución se encuentran todas las posibles soluciones que satisfacen el conjunto de restricciones, lo que se denomina factibilidad. La optimalidad es diferente, ya que dentro de las soluciones factibles, una o algunas de ellas serán las que minimicen o maximicen la función objetivo. Esto es fundamental, tanto en la enseñanza de la programación lineal como en el aprendizaje.

Casos especiales

Soluciones óptimas múltiples

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.

En el caso en el que los vectores solución sean consecutivos, esta cantidad de soluciones óptimas puede tender a infinito.

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 óptimas20000(x)10000(y)Z
Vértice C20000(4)10000(2)100000
Vértice D20000(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.


Solución óptima no acotada

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

Antes de pasar al modelo matemático, es importante evaluar críticamente el problema planteado. El primer supuesto considera la capacidad de atender cualquier demanda, es decir, una demanda infinita. En la realidad, esto implicaría la existencia de recursos de producción infinitos, lo cual es un supuesto poco realista. De hecho, es una apelación al absurdo que se utiliza para definir la gestión de las restricciones en la programación lineal.

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.

En mi experiencia docente, este es uno de los casos más frecuentes que se dan en el modelamiento por parte de los estudiantes. Es importante que los estudiantes desarrollen habilidades para comprender si las restricciones presentes acotan suficientemente el modelo o no. Esto es fundamental para obtener soluciones realistas y viables en un contexto de aplicación práctico.

Solución inviable o infactible

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.

En mi experiencia, el síndrome del trabajador quemado es una de las principales consecuencias de una mala gestión de recursos en un plan de trabajo (un típico escenario de soluciones no acotadas en un contexto real). Cuando un trabajador se encuentra a cargo de cumplir con un plan que no cuenta con los recursos necesarios, se ve obligado a realizar un esfuerzo excesivo para lograr cumplir con las metas establecidas, lo que puede llevar a un agotamiento laboral y una disminución en su rendimiento y calidad de vida.

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.


Restricciones redundantes

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.

Es importante tener en cuenta que, aunque algunos autores recomiendan eliminar las restricciones redundantes para mejorar la precisión del modelo, esta práctica no siempre es recomendable, de hecho, definitivamente desaconsejo esta práctica.

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!

Recomendamos que lean: Método gráfico mediante Python

Bryan Salazar López

Ingeniero Industrial y Magíster en Logística Integral especializado en productividad y modelamiento de procesos bajo dimensiones de sostenibilidad, industria 4.0, transformación digital y modelos de optimización. Docente universitario de pregrado y posgrado con experiencia en la enseñanza de estos temas. Fundador de Ingenieriaindustrialonline.com, un sitio en donde se recogen las aportaciones de investigaciones, artículos y referencias relevantes para la industria.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.

Botón volver arriba