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, también existen otras opciones como el
WINQSB.
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
Figura 1.1 |
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
Figura 1.2 |
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.
Figura 1.3 |
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.
Figura 1.4 |
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.
Figura 1.5 |
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.
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.
No hay comentarios:
Publicar un comentario