Cuencas Petrolifera

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 lascondiciones 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úmerode 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” delExcel. 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 ( 0Cada 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 seadmite 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áximavariació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ónobjetivo 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 paravalores 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...