programacion no lineal
Páginas: 8 (1756 palabras)
Publicado: 13 de mayo de 2013
PROGRAMACION NO LINEAL
INTRODUCCION
La programación lineal ha demostrado ser una herramienta sumamente poderosa, tanto en la modelización de problemas de la vida real como en la teoría matemática de amplia aplicación. Sin embargo, muchos problemas interesantes de optimización son no lineales.
El estudio de estos problemas implica una mezcla diversa de álgebralineal, cálculo multivariado, análisis numérico y técnicas de computación. Entre las áreas especiales importantes se encuentra el diseño de algoritmos de computación (incluidas las técnicas de puntos interiores para programación lineal), la geometría y el análisis de conjuntos convexos y funciones, y el estudio de problemas especialmente estructurados, tales como la programación cuadrática.La optimización no lineal proporciona información fundamental para el análisis matemático, y se usa extensamente en las ciencias aplicadas (en campos tales como el diseño de ingeniería, el análisis de regresión, el control de inventario y en la exploración geofísica).
ALGORITMOS NO LINEALES RESTRINGIDOS
METODO DE PROGRAMACION SEPARABLE
La programación separable es un casoespecial de programación convexa, en donde las suposiciones adicionales es:
3.- todas las funciones f(X) y gj(X) son funciones separables.
Una función separable es una función en la que cada término incluye una sola variable, por lo que la función se puede separar en una suma de funcioneEl problema general de programación no lineal con restricciones se define como sigue:
Maximizar (o minimizar) z =f(X) sujeta a g(X) _ 0
Las condiciones X _ 0 de no negatividad forman parte de las restricciones. También, al menos una de las funciones f(X) y g(X) es no lineal, y todas las funciones son continuamente diferenciables.
No existe algoritmo general para manejar modelos no lineales, por el comportamiento complicado de las funciones no lineales. Quizá el resultado más general aplicable al problema esel de las condiciones KKT. La tabla 2 de la sección correspondiente, muestra que a menos que f(X) y g(X) tengan buen comportamiento (condiciones de convexidad y concavidad), las condiciones KKT solo son necesarias (pero no suficientes) para alcanzar la optimalizacion de variables individuales. Por ejemplo, si f(X) es una función separable, se puede expresar como
F(X)= Σ fj (Xj),
En donde cadafj(Xj) incluye solo los términos con Xj. en la terminología de programación lineal , los problemas de programación separable satisfacen las suposiciones de auditividad pero no las de proporcionalidad (para funciones no lineales). Para ilustrar, la función objetivo considerada en la siguiente figura:
F(X1, X2)=126X1 – 9x21 + 182X2 – 13X22
Es una función separable porque puede ser expresada comoF(X1, X2)= F(X1) + F(X2)
Donde F1(X1)= 126X1 – 9x21 y F(X2)= 182X2 – 13X22 son cada una funciones de una sola variable x1 y x2, respectivamente. Usando el mismo razonamiento, se puede verificar que la función considerada en la figura siguiente, también es una función separable.
Es importante distinguir estos problemas de otros de programación convexa, pues cualquier problema de programaciónseparable se puede aproximar muy de cerca mediante uno de programación lineal y, entonces, se puede aplicar el eficiente método simplex.
A continuación resolvemos un problema de programación separable aplicando el método de la base restringida.
El método de aproximación nos sugiere que las variables separables son:
1 0 0 0
2 1 1 2
3 2 16 8
4 3 81 18
Luego:
Entonces elproblema original por aproximación se convierte en:
El tablero simplex inicial corresponde a:
Donde S1 es una variable de holgura (relleno).
La solución óptima por el Simplex a este problema equivalente es: Luego el óptimo en términos de es:
METODO DE PROGRAMACION CUADRATICA
De nuevo los problemas de programación cuadrática tienen restricciones lineales, pero ahora la...
INTRODUCCION
La programación lineal ha demostrado ser una herramienta sumamente poderosa, tanto en la modelización de problemas de la vida real como en la teoría matemática de amplia aplicación. Sin embargo, muchos problemas interesantes de optimización son no lineales.
El estudio de estos problemas implica una mezcla diversa de álgebralineal, cálculo multivariado, análisis numérico y técnicas de computación. Entre las áreas especiales importantes se encuentra el diseño de algoritmos de computación (incluidas las técnicas de puntos interiores para programación lineal), la geometría y el análisis de conjuntos convexos y funciones, y el estudio de problemas especialmente estructurados, tales como la programación cuadrática.La optimización no lineal proporciona información fundamental para el análisis matemático, y se usa extensamente en las ciencias aplicadas (en campos tales como el diseño de ingeniería, el análisis de regresión, el control de inventario y en la exploración geofísica).
ALGORITMOS NO LINEALES RESTRINGIDOS
METODO DE PROGRAMACION SEPARABLE
La programación separable es un casoespecial de programación convexa, en donde las suposiciones adicionales es:
3.- todas las funciones f(X) y gj(X) son funciones separables.
Una función separable es una función en la que cada término incluye una sola variable, por lo que la función se puede separar en una suma de funcioneEl problema general de programación no lineal con restricciones se define como sigue:
Maximizar (o minimizar) z =f(X) sujeta a g(X) _ 0
Las condiciones X _ 0 de no negatividad forman parte de las restricciones. También, al menos una de las funciones f(X) y g(X) es no lineal, y todas las funciones son continuamente diferenciables.
No existe algoritmo general para manejar modelos no lineales, por el comportamiento complicado de las funciones no lineales. Quizá el resultado más general aplicable al problema esel de las condiciones KKT. La tabla 2 de la sección correspondiente, muestra que a menos que f(X) y g(X) tengan buen comportamiento (condiciones de convexidad y concavidad), las condiciones KKT solo son necesarias (pero no suficientes) para alcanzar la optimalizacion de variables individuales. Por ejemplo, si f(X) es una función separable, se puede expresar como
F(X)= Σ fj (Xj),
En donde cadafj(Xj) incluye solo los términos con Xj. en la terminología de programación lineal , los problemas de programación separable satisfacen las suposiciones de auditividad pero no las de proporcionalidad (para funciones no lineales). Para ilustrar, la función objetivo considerada en la siguiente figura:
F(X1, X2)=126X1 – 9x21 + 182X2 – 13X22
Es una función separable porque puede ser expresada comoF(X1, X2)= F(X1) + F(X2)
Donde F1(X1)= 126X1 – 9x21 y F(X2)= 182X2 – 13X22 son cada una funciones de una sola variable x1 y x2, respectivamente. Usando el mismo razonamiento, se puede verificar que la función considerada en la figura siguiente, también es una función separable.
Es importante distinguir estos problemas de otros de programación convexa, pues cualquier problema de programaciónseparable se puede aproximar muy de cerca mediante uno de programación lineal y, entonces, se puede aplicar el eficiente método simplex.
A continuación resolvemos un problema de programación separable aplicando el método de la base restringida.
El método de aproximación nos sugiere que las variables separables son:
1 0 0 0
2 1 1 2
3 2 16 8
4 3 81 18
Luego:
Entonces elproblema original por aproximación se convierte en:
El tablero simplex inicial corresponde a:
Donde S1 es una variable de holgura (relleno).
La solución óptima por el Simplex a este problema equivalente es: Luego el óptimo en términos de es:
METODO DE PROGRAMACION CUADRATICA
De nuevo los problemas de programación cuadrática tienen restricciones lineales, pero ahora la...
Leer documento completo
Regístrate para leer el documento completo.