La solución de problemas de programación lineal

1.Introducción

Es una de las técnicas de optimización más ampliamente usadas y una de las más efectivas. El término Programación Lineal fue inventado por Dantzig en 1947 para referirse al procedimiento de optimización de problemas en los cuales tanto la función objetivo como las condiciones son lineales y todas las variables no negativas.

Algunos casos donde puede usarse esta técnica son:

• Problemas de mezclado

• Programas de fabricación

• Problemas de transporte

• Problemas de almacenamiento

• Formulación de dietas

• Restricciones de presupuesto

Cuando se enuncia matemáticamente cada uno de esos problemas el modelo matemático involucra un gran número de variables y de ecuaciones o inecuaciones. Una solución no sólo debe satisfacer todas las ecuaciones y restricciones, sino también alcanzar un extremo de la función objetivo, por ejemplo máximo beneficio o mínimo costo.

Con la ayuda de la computadora se pueden resolver problemas lineales con cientos de variables y condiciones. Una herramienta muy eficiente es el optimizador “Solver” del Excel. Productos similares se disponen en otras planillas de cálculo.

A fin de visualizar gráficamente las características básicas de los problemas a los que se aplica la técnica de Programación Lineal propongamos uno, hipotético, en dos variables, X1 y X2.

En los problemas de Programación Lineal es normal establecer la no negatividad de las variables involucradas:

X1  0 ; X2  0

Cada una de estas relaciones divide el espacio total en dos subespacios (uno con los puntos que cumplen la restricción y otro con los que no la cumplen). Las restricciónes permiten hablar así de soluciones permitidas (admisibles o posibles) y no permitidas. En este caso, el problema queda restringido a valores de X1 y X2 que se ubican en el primer cuadrante.

Esta consideración se admite en forma implícita, por lo cual, salvo expresa indicación en contrario se supondrá que las variables deben ser no negativas.

...