Programación Nolineal (Non Linear Programming NLP)
NLP: Conjunto de técnicas para optimizar funciones no-lineales sujetas a restricciones de igualdad o desigualdad. Tanto las funciones como las restricciones pueden ser de una o más variables
Formulación general de un problema de optimización
Encontrar x tal que
se minimice una función objetivo f(x)
sujeto a restricciones: gi(x) = bi (i=1,…, m) gj(x) ? bj (j=m,…, k)
Donde
x es un vector de n variables independientes
Características de los problemas que trataremos mayormente en el curso
Funciones objetivo y restricciones continuas con sus primeras derivadas parciales también continuas (suaves)
Esto garantiza que pequeños cambios en x conlleve a pequeños cambios en valores asociados
Inecuaciones estrictas no son permitidas (< ó >) solo se permiten restricciones de ? , ? e ?
El problema debe ser determinístico
Todas las variables deben ser reales, ninguna puede tomar únicamente valores enteros. (Continuous Programming)
S dominio de f y gi sea una región conectada
Tipos de Problemas No-lineales
Sin restricciones
Con restricciones
Tamaño de los Problemas
Una forma de medir la complejidad de los problemas es en función del número de variables o del número de restricciones
Pequeña Escala: hasta 5 variables y restricciones ? puede ser resuelto a mano
Escala intermedia: de 5 a 100 variables y restricciones ? Computador Personal o Servidor de Propósito General
Gran Escala: más de 100 y quizás 1000 variables y restricciones ? Mainframe para cálculo científico (cray), explotando la estructura del problema con algoritmos paralelos
Tipos de Problemas No-lineales
En el curso se estudiarán la teoría y los métodos que permiten efectivamente la solución de la más amplia variedad de problemas (pequeña y mediana escala principalmente)
A pesar de que un gran número de algoritmos han sido propuestos para la solución del problema general de optimización no lineal, sólo unos pocos han demostrado ser efectivos cuando se aplican a problemas de “gran – escala”
No existe un método general de optimización no lineal en el sentido como es SIMPLEX para problemas lineales
Ninguno es tan superior para ser clasificado como la “panacea” universal de la NLP
Criterios de Comparación de Algoritmos
Número de evaluaciones de la función objetivo
Confiabilidad (Éxito en alcanzar la solución)
Rapidez
Tiempo de Preparación del usuario (sobre parametrización)
Precisión de la solución
Grado de satisfacción de las restricciones
Dificultad
Algoritmos Iterativos y Convergencia
La mayoría de los algoritmos de NLP son iterativos
En programación lineal existe una secuencia de longitud finita para alcanzar la solución
En NLP la secuencia generalmente no alcanza la solución óptima sino que converge hacia ella
En problemas no lineales se determina una solución lo suficientemente cercana a la óptima
Solución Óptima
Algoritmos Iterativos y Convergencia
La teoría de algoritmos iterativos se divide en:
Diseño del Algoritmo
Convergencia Global: Análisis de convergencia global (si eventualmente converge)
Convergencia Local: Análisis de convergencia local (la razón a la cual el algoritmo converge en la Solución óptima)
“Una buena teoría es mejor que miles de corridas”
Esto da una idea de la manejabilidad de los problemas mediante un análisis simple lo cual es muy importante
Funciones de una variable
Continuidad de una función en un número
Se dice que f es continua en el número a si y solo si las siguientes 3 condiciones se satisfacen:
existe
existe
Discontinuidad removible
Discontinuidad Esencial
Página siguiente  |