PROGRAMACION NO LINEAL

PROGRAMACION NO LINEAL

1. En matemáticas, Programación no lineal (PNL) es el proceso de resolución de un sistema de igualdades y desigualdades sujetas a un conjunto de restricciones sobre un conjunto de variables reales desconocidas, con un función objetivo a maximizar (o minimizar), cuando alguna de las restricciones o la función objetivo no son lineales.

   • En matemáticas, Programación no lineal (PNL) es el proceso de resolución de un sistema de igualdades y desigualdades sujetas a un conjunto de restricciones sobre un conjunto de variables reales desconocidas, con una función objetivo a maximizar (o minimizar), cuando algunas de las restricciones o la función objetivo no son lineales. Los problemas de programación no lineal se presentan de muchas formas distintas. Al con­trario del método símplex para programación lineal, no se dispone de un algoritmo que re­suelva todos estos tipos especiales de problemas. En su lugar, se han desarrollado algoritmos para algunas clases (tipos especiales) de problemas de programación no lineal. Se introduci­rán las clases más importantes y después se describirá cómo se pueden resolver algunos de es­tos problemas.

2. Existe una variedad de métodos para resolver problemas no convexos. Uno de ellos consiste en utilizar formulaciones especiales de problemas de programación lineal. Otro método implica el uso de técnicas de Ramificación y poda, cuando el problema se divide en subdivisiones a resolver mediante aproximaciones que forman un límite inferior del coste total en cada subdivisión.

   • Los tipos de problemas de programación no lineal son: • Optimización no restringida. • Optimización linealmente restringida. • Programación cuadrática • Programación convexa. • Programación separable. • Programación no convexa. • Programación geométrica. • Programación fraccional. • Problema de complementariedad.

3. Método de búsqueda directa Los métodos de búsqueda directa se aplican principalmente a funciones estrictamente unimo- dales de una variable. Aunque puede parecer trivial el caso, la sección 21.1.2 muestra que la optimización de funciones de una variable juega un papel clave en el desarrollo de los algorit­mos de varias variables, más generales.

   • En esta sección se presentan dos algoritmos estrechamente relacionados: los métodos de búsqueda dicótomo y de sección dorada (o áurea). Ambos buscan la maximización de una fun­ción unimodal/(x) en el intervalo a ^ x < b, que se sabe que incluye el punto óptimo x*. Los dos métodos comienzan con /0 = (a, b) que representa el intervalo inicial de incertidumbre.
     • Paso general i. Sea /, _ , = (xD xR) el intervalo actual de incertidumbre (en la iteración 0, xL = a y xR = b). A continuación se definen xx y x2 tales que xj^ ^ ^ x2 ^ xr El siguiente intervalo de incertidumbre, /z, se define como sigue: Si f(xx) > /(x2), entonces xL < x* < x2. Se definen xR = x2 e /, = (xL, x2) (véase la figura 21.2[a]). Si f(xx) < f(x2\ entonces xx < x* < xR. Se definen xL = xx e I¡ = (xh xR) (véase la figura 21.1 [b]). . Si f{x\) = /(jc2), entonces xx < x* < x2. Se definen xL = x2 e /, = (xb x2). La manera en que se determinan xx y x2 garantiza que /, < /,_ p como se demostrará en breve. El algoritmo termina en la iteración ksilk< A, donde A es un grado de exactitud defi­nido por el usuario.

4. OPTIMIZACIÓN LINEALMENTE RESTRINGIDA Los problemas de optimización linealmente restringida se caracterizan por restricciones que se ajustan por completo a la programación lineal, de manera que todas las funciones de restric­ción g¡ (x) son lineales, pero la función objetivo es no lineal. El problema se simplifica mucho si sólo se tiene que tomar en cuenta una función no lineal junto con una región factible de programación lineal. Se han desarrollado varios algoritmos especiales basados en una exten­sión del método símplex para analizar la función objetivo no lineal. Un caso especial importante descrito a continuación es la programación cuadrática.