Formulación de Programación Lineal

Los problemas de programación lineal tienen la particularidad (casi que obvia) en que su función objetivo y las restricciones son funciones lineales, es decir el máximo exponente en ellas es uno.  Con esta herramienta matemática se puede describir una gigantesca cantidad de problemas en el mundo real, con una sencillez muy grande.  Tal vez el problema más común en Programación Lineal es el de la combinación óptima de recursos, en el cual para lograr el valor máximo de un objetivo, es necesario encontrar en que cantidad mezclar o usar, una cantidad determinada y limitada de recursos.

 

Poder formular correctamente un problema matemático, es en mi opinión lo más importante en matemáticas aplicadas, en este caso, Investigación de Operaciones.  Pues, una vez se tiene el problema formulado, llamado el Programa Lineal, sólo se necesita un software para resolverlo, de los incontables que se encuentran en Internet, muchos de ellos, gratis. Incluso, en esta página se muestra como resolver los programas lineales en Excel.

 

 

Combinación Optima de Producción

 

Este es uno de los ejemplos típicos. No sé en cuantos libros de texto lo he leído, y aunque es increíblemente sencillo sirve como buena introducción para aprender a formular problemas de Programación Lineal.

 

Una pequeña fabrica de muebles (el ejemplo también funciona para una fabrica gigante, jajaja), produce camas económicas y camas línea dorada.  Las camas económicas, son mucho más fáciles de fabricar, consumen menos madera y se producen mucho más rápido que las camas de línea dorada. Las camas de línea dorada son más exclusivas y tienen un precio y un margen de ganancia mucho mayor.

 

Las camas económicas consumen 1 metro cúbico de madera por unidad, mientras que las camas de línea dorada consumen dos metros cúbicos de madera por unidad. En el mes, se tiene un disponible máximo de 100 metros cúbicos de madera. Cada cama económica toma 5 horas hombre de fabricación, mientras que las camas de línea dorada, debido a su complejidad, toman 15 horas hombre fabricarlas. Cada mes en la fabrica, se tienen 1000 horas hombre disponibles, para producir.

 

Cada cama económica deja una utilidad por unidad de 100 dólares, mientras que las camas de línea dorada producen una utilidad por unidad de 400 dólares.

 

Qué cantidad de camas económicas y de línea dorada se deben producir para obtener la máxima utilidad posible, respetando las disponibilidades máximas de madera y mano de obra?

 

Solución:

 

Dentro de la formulación, este es el formato que siguen la mayoría de los problemas de programación lineal. Un objetivo: una meta a la cual llegar. Pero todo tiene un precio. Para llegar a ese objetivo se tienen recursos limitados: las restricciones. Cómo usar esos recursos limitados, de la manera más inteligente para llegar al valor más alto del objetivo, es el propósito para el que fue creada la programación lineal.

 

Es realmente inmensa la cantidad de problemas en la vida real que siguen este tipo de formato, y es por eso, y por supuesto, por la creciente disponibilidad de herramienta de computo, su inseparable aliada, que la programación lineal se hizo tan popular y útil en los últimos años.

 

La Metodología:

 

La gran mayoría de libros de texto que conozco, cuando explican este capitulo, lo hacen siguiendo unos pasos como si se tratara de una receta de cocina. Bueno, no tengo nada en contra de seguir pasos como receta de cocina en muchas cosas de investigación de operaciones, incluso, yo mismo doy algoritmos tipo receta de cocina en esta web. Pero eso es cuando estos pasos, son rutinarios, los puede hacer una máquina (como realizar iteraciones sobre una tabla), pero en cambio, tener un problema y traducirlo a lenguaje matemático, se me antoja que no es como una receta de cocina que seguir, por que se coarta el ingrediente más importante a mi parecer: Pensar.

 

Un pequeño consejo: empezar en pequeño. Si. Empezar en pequeño e ir mejorando la formulación para que se acerque cada vez más al problema real. No hay una receta de cocina para formular, por que si existiera, las maquinas podrían hacerlo. Y no pueden (aún, tal vez en unos años los blogs los escriban androides jajaja). Así querido lector, que si está empezando en esta ciencia, sólo le aconsejo no tener miedo, empezar en pequeño y... pensar.

 

Función Objetivo:

 

Por convención general, a la meta que se busca se le llama función objetivo. se denota con la variable Z.  Cómo a todo objetivo tiene una dirección deseada. O se desea que sea un máximo o se desea que sea un mínimo. Las cosas buenas en la vida se desean que crezcan al máximo, por ejemplo los ingresos, las utilidades, el conocimiento. Las malas que vayan al mínimo: los costos, los gastos, los impuestos...

 

En este ejemplo, las utilidades.

 

Z= Utilidades. Pero no se desean unas utilidades cualquiera... se desean las más altas utilidades de la historia.  El máximo de las utilidades. Es decir:

 

Maximizar Z.

 

Las utilidades totales son iguales a las utilidades que se obtengan de vender camas económicas y camas línea dorada. 

 

Llamemos X1 a la cantidad de camas de línea económica producidas. Así que si se produce una se obtiene una utilidad de 100 dólares, si se producen dos se obtienen 200 dólares, 3... 300 dólares. En resumen, se obtiene 100 por la cantidad de camas económicas producidas: 100 x X1 o sea: 100X1.   De manera similar, si representamos a la cantidad de camas producidas en línea dorada por X2, y se obtiene 400 dólares por cada cama línea dorada producida, se puede representar por 400T2.

 

O sea:

 

Función objetivo:

 

Max Z = 100X1 + 400X2.

 

Restricciones:

 

La cantidad de madera usada no puede ser superior a 100 metros cúbicos. La cantidad de madera usada por las camas económicas se puede representar por 1 metro cúbico multiplicada por la cantidad de camas, o sea 1 x X1. De manera similar, si las camas de línea dorada consumen dos metros cúbicos, se puede representar por: 2X2.

 

En ese orden de ideas, la cantidad de madera usada será la madera usada por las camas económicas más la madera usada en las camas en línea dorada. Es decir:

 

 Cantidad total de madera = X1 + 2X2.

 

Pero la cantidad de madera no puede sobre pasar a los 100 metros cúbicos. O sea que la cantidad de madera usada debe ser menor o igual a 100. Lo que podríamos escribir usando la siguiente desigualdad:

 

             X1 + 2X2 <= 100

 

De manera  similar podemos escribir para la restricción de horas hombre disponibles:

 

5 horas para cada cama económica y 15 horas para cada cama de línea dorada, es decir:

 

             5X1 + 15X2 es el total de horas hombre usadas en ambos tipos de cama. Pero el tiempo disponible en total no puede superar las 1000 horas hombre, por lo que podemos escribir:

 

             5X1 + 15X2 <= 1000.

 

Y por último, dado que en la mayoría de problemas de programación lineal, no tiene sentido los valores negativos, como en este caso, no tendría sentido decir: menos tres camas, se introduce una restricción como condición general, que las variables deben ser no negativas. Se suele escribir el acrónimo CNN: condición de no negatividad.

 

Por lo que el modelo completo formulado es el siguiente:

 

Max Z = 100X1 + 400X2.

Sujeto a:

                 X1 + 2X2 <= 100

               5X1 + 15X2 <= 1000

c.n.n.

Contenido :

Social