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 contrario del método símplex para programación lineal,
no se dispone de un algoritmo que resuelva 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 introducirán las clases más importantes y después se describirá cómo
se pueden resolver algunos de estos problemas.
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.
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 algoritmos 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 funció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 definido por el
usuario.
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 restricció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 extensió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.