Elementos de Diseño Óptimo Programación Lineal

Elementos de Diseño Óptimo

Programación Lineal

Ing. C.N. Paniagua – Ing. O.A. Iglesias

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.

Sea la función objetivo lineal de la forma:

máx Z = X1 + X2

En la figura 1.1 están representadas algunas de sus rectas de nivel. Ellas son rectas paralelas y en el sentido perpendicular a cualquiera de ellas se encuentra la dirección de máxima variación de Z, que corresponde a la del vector gradiente.

Puede notarse que, como no existe otra restricción sobre las variables, excepto la no negatividad, el máximo de Z se encuentra en el infinito.

Si se agrega otra restricción, por ejemplo, X2  3, la situación es la que se presenta en la figura 1.2. En este caso, al buscar el óptimo, el valor de X2 queda fijo en 3 y la función objetivo se desplaza sobre la frontera de la restricción y su máximo se sigue encontrando en el infinito.

Si la restricción fuese, en cambio, X1  2, se puede ver, como lo muestra la figura 1.3, que el máximo se encuentra para un valor infinito de X2, y es X1 la variable que tiene un valor finito.

Si se consideran a la vez ambas restricciones, la zona de soluciones admisibles está limitada por una polígonal cerrada y la función objetivo, en este caso, no puede crecer más allá del punto A de la figura 1.4. En ese punto, al igual que en cualquiera de los vértices de la poligonal, se agotan los grados de libertad.

En todo problema de Programación Lineal, siempre que se tenga una zona de soluciones posibles cerrada, habrá un mínimo y un máximo de la función objetivo para valores finitos de las variables. Si la zona está abierta un extremo se encuentra en el infinito, el máximo o el mínimo, dependiendo del sentido de crecimiento de la función objetivo. Si se observan las figuras 1.2 y 1.3 hay un mínimo en el origen de coordenadas pero si se busca máximo se lo hallará en el infinito.

Si al problema se le agrega la restricción 4X1 + 3X2  12, el máximo, como puede observarse en la figura 1.5, se encuentra en B y nuevamente está en la intersección de dos fronteras.

Se puede inducir, entonces, que, para dos variables, de existir un óptimo finito en un problema de programación lineal, éste debe encontrarse en la intersección de dos restricciones. En general, para n variables, se encontrará en la intersección de n restricciones. En cualquiera de estas situaciones, el sistema carece de grados de libertad.

Si se admitiera que las soluciones capaces de ser óptimas poseyeran algún grado de libertad, aplicando el método de sustitución y dada la naturaleza lineal de la función objetivo, se encontraría tal óptimo en el infinito. La solución óptima se obtiene, entonces, por la resolución de un sistema de ecuaciones lineales.

El concepto expuesto es sumamente importante, puesto que si bien el conjunto de soluciones posibles o permitidas tiene infinitos puntos, sólo se deberían analizar las intersecciones de n restricciones. O sea que la búsqueda se efectuaría sobre un número finito de posibilidades. Este número puede, todavía, ser demasiado grande. Para un caso genérico de m restricciones y n variables, siendo m  n, el número de vértices estará dado por:

lo que arroja para 10 variables y 20 restricciones, 184756 vértices. Obviamente, no todos estos vértices pertenecen a la zona de soluciones admisibles, por lo que se hace imprescindible la utilización de una metodología que minimice el número de casos a ser analizados.En los problemas de Programación Lineal las zonas que delimitan las restricciones son siempre convexas. En una zona de este tipo dos puntos que se encuentran dentro de la misma, definen un segmento que está totalmente incluido en la zona.

Cuando ese segmento es un lado de la poligonal que define la zona de soluciones admisibles, la totalidad de la misma ha de quedar dentro de uno de los subespacios que define la recta a la que pertenece dicho segmento. Esto garantiza que, una vez encontrado un óptimo local este será el óptimo global en el problema.

2. Formulación del problema de programación lineal

La formulación adoptada como canónica o estándar es:

Encontrar el máximo de una función objetivo lineal en n variables de decisión no negativas.

dentro de una zona de soluciones posibles definida por las desigualdades lineales

La no negatividad de las variables agrega, al conjunto anterior, las restricciones

Muchas variables químicas y físicas son por definición cantidades positivas, por ejemplo, presión absoluta, concentración, temperatura absoluta. Si por alguna razón se deben permitir valores negativos para ciertas variables,

...