OPTIMIZACIÓN
Los métodos de optimización es una rama de las matemáticas que consiste en el uso de
modelos matemáticos, estadísticos y algoritmos con objeto de realizar un proceso de toma de
decisiones. Frecuentemente trata del estudio de complejos sistemas reales, con la finalidad de
mejorar (u optimizar) su funcionamiento. La investigación de operaciones permite el análisis de la
toma de decisiones teniendo en cuenta la escasez de recursos, para determinar cómo se puede
optimizar un objetivo definido, como la maximización de los beneficios o la minimización de
costos.
En ocasiones es necesario optimizar un proceso. Esto es, determinar las condiciones que
resultarán en la “mejor” operación del sistema o proceso. En otras palabras, optimizar es
seleccionar a partir de un conjunto de alternativas posibles, aquella que mejor satisfaga los
objetivos propuestos. Pero el concepto de “mejor opción” es relativo. Si consideramos el caso de
un reactor en el que ocurra una reacción principal y reacciones secundarias que dan productos
indeseables, la mejor opción puede ser:
aumentar la producción de productos valiosos.
reducir los productos contaminantes.
incrementar las ganancias.
prolongar los periodos entre paradas.
Reducir los costos de mantenimiento o la utilización de determinados equipos.
El ingeniero químico debe tratar problemas de optimización en distintas etapas de su actividad.
1. Desarrollo de procesos
2. Diseño de plantas.
3. Operación de la planta.
Algunos ejemplos son:
Determinación de los mejores lugares para la ubicación de la planta.
Dimensionamiento de tuberías
Diseño de equipos y plantas enteras.
Organigrama de mantenimiento y reemplazo de equipos.
Planificación y análisis de operaciones existentes.
Evaluación de datos de planta para construir un modelo del proceso.
Modelo matemático: Es una representación matemática de los aspectos esenciales de un
sistema y que presenta conocimiento del mismo en una manera útil (Eykhoff, 1974).
Aspectos a considerar en el modelado:
a) Ecuaciones de balances de materia y de energía.
b) Relaciones de diseño.
c) Ecuaciones que describen el fenómeno físico.
d) Inecuaciones que definen los rangos de operación permitidos.
ETAPAS NECESARIAS PARA LA RESOLUCION DEL PROBLEMA
- La “formulación del modelo de optimización”: no es un procedimiento formal estructurado
sino más bien un proceso que requiere de experiencia y creatividad.
- Resolver y validar dicho modelo: para esta etapa se han desarrollado innumerables
métodos y estrategias para resolverlos por lo que puede considerarse formalizada.
ESTRUCTURA DE UN PROBLEMA DE OPTIMIZACIÓN
En los problemas de optimización existen dos objetivos en conflicto:
1. Construir un modelo suficientemente preciso que describa apropiadamente el
problema.
2. Construir un modelo tratable, que se pueda resolver mediante alguna técnica de
resolución.
Se buscará maximizar o minimizar una función llamada objetivo cuyas variables deben estar
regidas, además, por un cierto número de restricciones que pueden ser de igualdad o desigualdad.
Tiene la siguiente estructura:
Max o min f(x) Función objetivo
Sujeto a: Hk(x) = 0 k= 1,2,....k restricciones de igualdad
Gj(x) >=0 j= 1,2,...j restricciones de desigualdad
Procedimiento para resolver problemas de optimización
1. Analizar el proceso y definir las variables y características específicas de interés.
preparar una lista de las variables.: Hay que definir los límites del sistema. Elegir un criterio
cuantitativo para medir la performance del sistema, índice que permita identificar el mejor diseño
(Factor económico: capital total, costo anual, retorno sobre la inversión, etc. Y Factor tecnológico:
tiempo de producción, velocidad de producción, utilización de energía).
2. Determinar el criterio de optimización y especificar la función objetivo en términos
de las variables listadas en 1.: Los objetivos son fijados arbitrariamente por quien debe decidir y
están relacionados con la rentabilidad del proceso (maximizar beneficios, minimizar el consumo de
energía, etc), la calidad del producto ( maximizar pureza, minimizar la producción de productos
secundarios), con el impacto ambiental (reducir la producción de contaminantes).
3. Desarrollar, vía expresiones matemáticas, un modelo de proceso o equipo que
relacione las variables de entrada-salida de un proceso con los coeficientes asociados.
4. Aplicar una técnica de optimización adecuada respecto de la formulación
matemática del problema.
5. Verificar las respuestas y examinar la sensibilidad de los resultados o cambios en
los coeficientes e hipótesis del problema.
Algoritmos de resolución
De acuerdo a la forma de f (x) y las restricciones:
Cuando la función objetivo y todas las restricciones son lineales esta estructura matemática
se denomina Modelo de Programación Lineal ( LP )
Si alguna de las funciones descriptas es no lineal se denomina “Modelo de Programación no
lineal” (NLP).
De acuerdo a la presencia o no de restricciones:
_ Optimización no restringida: El problema de optimización no tiene restricciones.
_ Optimización restringida: El problema de optimización tiene restricciones.
Según su dimensionalidad:
_ Optimización unidimensional: función objetivo de una variable.
_ Optimización multidimensional: función objetivo de varias variables.
Según el número de funciones objetivo:
_ Optimización con un objetivo: Una sola función objetivo.
_ Optimización con múltiples objetivos: Varias funciones objetivo
Algoritmos de optimización Solución grafica
de LP Simplex
Algoritmos para NLP
NLP no condicionados (univariables)
1. Métodos de reducción de intervalos: método de la sección dorada : Se basa en la
colocación de puntos simétricos, de tal manera que en cada iteración, el punto que se
conserva sirve como base para la selección del nuevo punto, el cual a su vez, debe
conservar la simetría original, pero acotando la solución óptima dentro de un intervalo de
búsqueda menor.
2. Métodos que utilizan derivadas: Método de Newton
NLP no condicionados (multivariables):
1. búsqueda Simplex
2. búsqueda directa
3. Mét. Coordenado cíclico
4. Mét de la direcció empinada o de Cauchy
5. Mét. De Newton (multivariables)
NLP con restricciones:
1. método de direcciones factibles y de mejora
2. método del gradiente reducido de Wolfe (GR)
3. método del gradiente reducido generalizado (GRG)
PROGRAMACIÓN LINEAL:
Para casos de 2 variables se emplea un método gráfico. Para modelos de 2 o más variables
se emplea el método SIMPLEX.
La formulación de un modelo LP:
Ejemplo de aplicación: La empresa Blue Ridge Hot Tubs, fabrica y vende dos modelos de baños
calientes: Aqua-Spa y la Hydro-Lux. Su propietario y gerente, Howie Jones, necesita decidir cuanto
de cada tipo producir durante el ciclo siguiente de producción. El baño en sí y las bombas, la
compra prefabricadas, a las cuales le adiciona la tubería, para confeccionar dichos baños. Howie
instala el mismo tipo de bombas a ambos baños. Su disposición de las mismas es de 200 en cada
ciclo. Ambos baños tienen diferentes requerimientos de material y mano de obra. Así, cada Aqua-
Spa requieren 9 horas de mano de obra y 12 pies de tubería mientras que cada Hydro-Lux requiere
6 horas de mano de obra y 16 pies de tubería. Howie, espera disponer de 1566 horas de mano de
obra y 2880 pies de tubería en cada ciclo de producción. Cada AquaSpa provee de una ganancia de
350$ mientras que cada Hydro-Lux vendido reporta 300$. Su propietario confía en vender toda su
producción. La pregunta es, ¿Cuántos Aqua-Spa y cuántos Hydro-Lux producir para maximizar las
ganancias en cada ciclo?
Si bien el proceso de modelado es esencialmente cualitativo y requiere de la habilidad y
experiencia de quien desarrolle el modelo, en términos generales se pueden definir los siguientes
pasos:
1. Comprender el problema:
A pesar de la obviedad del mismo, este paso debe ser previo al de formulación de la función
objetivo, para que esta enfoque realmente a la resolución de dicho problema.
En nuestro caso implica, determinar el número a producir de cada tipo de baño para
obtener la máxima ganancia, disponiendo de 200 bombas, 1566 h de mano de obra y 2880
pies de tubería.
2. Identificar las variables de decisión: pertenecen a la propia naturaleza del problema y no
pueden ser establecidas arbitrariamente.
Así, en nuestro ejemplo x1 será la cantidad de A-S y x2 los de H-L a producir.
3. Formular la función objetivo como combinación lineal de las variables de decisión z:
Esta función expresa la relación matemática entre las variables que debe ser maximizada o
minimizada. Generalmente es la ecuación que expresa la utilidad económica obtenida al
operar el proceso con un conjunto específico de variables de control (independientes).
Recibe diferentes denominaciones según la bibliografía. Los nombres usuales son función de
costo o función de ganancia aunque en programación lineal se utiliza el término “función
objetivo”.
La ganancia total será:
350x1 + 300x2 MAX.
4. Formular las restricciones como combinación lineal de las variables de decisión: Éstas
definen el conjunto de valores que pueden tomar las variables de decisión. Las restricciones
pueden pertenecer a la naturaleza del problema (Ej. Restricciones físicas: Límites de presión
y temperatura, etc) o ser fijadas arbitrariamente.
Nosotros tenemos 3 restricciones:
El nº de bombas: 1* X1 + 1 *X2 <= 200
El nº de horas disponibles: 9 x1 + 6 x2 <= 1566
Pies de tubería disponibles. : 12 x1 + 16 x2 <= 2880
5. Identificar los límites superiores e inferiores de las variables.
En nuestro ejemplo se asume que ni x1 ni x2 deben ser negativos o ceros, lo que se expresa en
forma matemática como: x1 > 0
x2 > 0
En resumen, el modelo planteado para el problema será:
RESUMEN PARA LA RESOLUCION GRÁFICA DE PROBLEMAS DE PROGRAMACIÓN LINEAL.
En primer lugar, dibujar un sistema de coordenadas cartesianas en las dos variables del problema.
Cada restricción representada por una desigualdad, divide al espacio en dos zonas: una factible y
la otra, no. Las igualdades, solo se cumplen en una recta. Una vez introducidas todas las
restricciones quedará una zona en la que las variables asumen todas las restricciones.
1. Dibujar las rectas correspondientes a cada restricción.
2. Identificar la zona factible, esto es, los puntos del gráfico que satisfacen simultáneamente a
todas las restricciones.
3. Localizar la solución óptima por uno de los siguientes métodos:
a. dibujar una o más curvas de nivel para la función objetivo y determinar la dirección en
la cual la función objetivo logra su resultado deseado (máximo o mínimo). Trasladar en forma
paralela una recta a dichas curvas de nivel en la dirección determinada hasta que la misma
intercepte al punto más lejano. Determinar las coordenadas de dicho punto, el cual será el óptimo.
b. Identificar todos los puntos extremos de la región factible (vértices) y determinar el
valor de la función objetivo en cada uno de ellos. Si la zona factible es limitada, el punto con el
mejor resultado será el óptimo.
Modelado y resolución con Hojas de Cálculo.
La resolución de problemas de LP se ha vuelto tan importante que existen numerosos
softwares de cálculos que permiten encontrar objetivos que pueden ser maximizados,
minimizados o simplemente encontrar un número determinado.
Las ventajas que presentan los sistemas informáticos es que son más flexibles que los
métodos gráficos. Además permiten resolver problemas con más de 2 variables.
El Excell tiene incorporado una herramienta llamada Solver. Éste programa evalúa
resultados, límites y sensibilidad de las soluciones.
Los pasos son:
1. Organizar los datos del modelo en la hoja. El reporte final debe ser claro: los
objetivos, las restricciones y las variables deben ser identificados.
2. Reservar celdas separadas para representar cada variable de decisión.
3. Crear una fórmula, en una celda, para representar la función objetivo.
4. Para cada restricción: crear en una celda una fórmula que represente el miembro
izquierdo de la restricción. En celdas contiguas se colocan los valores que puede
tomar la restricción, para compararlas con el valor que finalmente tomarán.
Método Simplex
El método Simplex, transforma el sistema de inecuaciones en un sistema de igualdades
mediante el uso de variables auxiliares llamadas Slacks (débiles). Por ejemplo, la siguiente
desigualdad se transforma en igualdad por el empleo de una variable slack S.
Si el número de variables supera al de restricciones, se deben tomar cierto número de ellas
y ser consideradas como variables básicas, mientras que las restantes (variable no-básicas) se fijan
en el límite inferior. Con el sistema obtenido, se resuelven sus incógnitas las cuales dan una
solución básica factible que corresponde a uno de los vértices de intersección de las restricciones.
Al haber 3 restricciones y 5 variables, debemos tomar 3 variables básicas y 2 no-básicas, lo
que da diez formas distintas de posibles soluciones básicas factibles, que son:
Los puntos marcados por * son infactibles debido a que no cumplen la condición de no
negatividad. Los puntos 1 a 5 son los que delimitan la zona factible, como se ilustra en la figura.
El método Simplex identifica una de las soluciones básicas factibles y compara el valor de la
función objetivo con la correspondiente con los puntos adyacentes. Si ningún punto adyacente al
de estudio es mejor, dicho punto es el óptimo.
PROGRAMACIÓN NO LINEAL (NLP)
La diferencia con la programación lineal es que en este último caso las restricciones y la
función objetivo son todas lineales. En NLP la función objetivo y/o una o todas las restricciones son
no lineales.
Fig. a: función objetivo lineal. Una de las restricciones es no lineal. El borde de la zona
factible no es lineal.
Fig. b: el borde de la zona factible es lineal (restricciones), pero las curvas de la función
objetivo no.
Fig. c: la función objetivo y una de las restricciones son curvas (no lineales).
Fig. d: caso en que la zona factible está limitada por líneas rectas y las curvas de nivel se
concentran sobre la solución óptima “dentro” de la zona factible a diferencia del 2º caso donde la
solución óptima está en el borde.
En NLP la solución óptima puede estar sobre un borde curvo, recto o dentro de la zona
factible.
