IOinformacion
Páginas: 7 (1595 palabras)
Publicado: 8 de noviembre de 2015
3.3 Tipos De Problemas De Programación No Lineal
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 nolineal. Se introducirán las clases más importantes y después se describirá cómo se pueden resolver algunos de estos problemas.
Si la función objetivo f es lineal y el espacio restringido es un politopo, el problema es de Programación lineal y puede resolverse utilizando alguno de los bien conocidos algoritmos de programación lineal.
Si la función objetivo es cóncava (problema demaximización), o convexa (problema de minimización) y el conjunto de restricciones es convexo, entonces se puede utilizar el método general de Optimización convexa
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 elproblema se divide en subdivisiones a resolver mediante aproximaciones que forman un límite inferior del coste total en cada subdivisión. Mediante subdivisiones sucesivas, se obtendrá una solución cuyo coste es igual o inferior que el mejor límite inferior obtenido por alguna de las soluciones aproximadas. Esta solución es óptima, aunque posiblemente no sea única. El algoritmo puede ser parado antes,con la garantía de que la mejor solución será mejor que la solución encontrada en un porcentaje acotado. Ello se utiliza en concreto en problemas importantes y especialmente difíciles y cuando el problema cuenta con costes inciertos o valores donde la incertidumbre puede ser estimada en un grado de fiabilidad apropiado.
Las condiciones de Karush-Kuhn-Tucker proporcionan las condicionesnecesarias para que una solución sea óptima.
Los tipos de problemas de programación no lineal son:
1. Optimización no restringida.
2. Optimización linealmente restringida.
3. Programación cuadrática
4. Programación convexa.
5. Programación separable.
6. Programación no convexa.
7. Programación geométrica.
8. Programación fraccional.
9. Problemade complementariedad.
ALGORITMOS SIN RESTRICCIÓN
En esta sección se presentarán dos algoritmos para el problema no restringido: el algoritmo de búsqueda directa y el algoritmo degradiente.
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.2muestra 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.
La idea de los métodos de búsqueda directa es identificar el intervalo de incertidum- bre que comprenda al punto de solución óptima. El procedimiento localiza el óptimo estrechando en forma progresiva el intervalo de incertidumbre hasta cualquiergrado de exactitud que se desee.
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 x2tales que
xj^ ^ ^ x2 ^ xr
El siguiente intervalo de incertidumbre, /z, se define como sigue:
1. Si f(xx) > /(x2), entonces xL < x* < x2. Se definen xR = x2 e /, = (xL, x2) (véase la figura 21.2[a]).
2. Si f(xx) < f(x2\ entonces xx < x* < xR. Se...
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 nolineal. Se introducirán las clases más importantes y después se describirá cómo se pueden resolver algunos de estos problemas.
Si la función objetivo f es lineal y el espacio restringido es un politopo, el problema es de Programación lineal y puede resolverse utilizando alguno de los bien conocidos algoritmos de programación lineal.
Si la función objetivo es cóncava (problema demaximización), o convexa (problema de minimización) y el conjunto de restricciones es convexo, entonces se puede utilizar el método general de Optimización convexa
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 elproblema se divide en subdivisiones a resolver mediante aproximaciones que forman un límite inferior del coste total en cada subdivisión. Mediante subdivisiones sucesivas, se obtendrá una solución cuyo coste es igual o inferior que el mejor límite inferior obtenido por alguna de las soluciones aproximadas. Esta solución es óptima, aunque posiblemente no sea única. El algoritmo puede ser parado antes,con la garantía de que la mejor solución será mejor que la solución encontrada en un porcentaje acotado. Ello se utiliza en concreto en problemas importantes y especialmente difíciles y cuando el problema cuenta con costes inciertos o valores donde la incertidumbre puede ser estimada en un grado de fiabilidad apropiado.
Las condiciones de Karush-Kuhn-Tucker proporcionan las condicionesnecesarias para que una solución sea óptima.
Los tipos de problemas de programación no lineal son:
1. Optimización no restringida.
2. Optimización linealmente restringida.
3. Programación cuadrática
4. Programación convexa.
5. Programación separable.
6. Programación no convexa.
7. Programación geométrica.
8. Programación fraccional.
9. Problemade complementariedad.
ALGORITMOS SIN RESTRICCIÓN
En esta sección se presentarán dos algoritmos para el problema no restringido: el algoritmo de búsqueda directa y el algoritmo degradiente.
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.2muestra 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.
La idea de los métodos de búsqueda directa es identificar el intervalo de incertidum- bre que comprenda al punto de solución óptima. El procedimiento localiza el óptimo estrechando en forma progresiva el intervalo de incertidumbre hasta cualquiergrado de exactitud que se desee.
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 x2tales que
xj^ ^ ^ x2 ^ xr
El siguiente intervalo de incertidumbre, /z, se define como sigue:
1. Si f(xx) > /(x2), entonces xL < x* < x2. Se definen xR = x2 e /, = (xL, x2) (véase la figura 21.2[a]).
2. Si f(xx) < f(x2\ entonces xx < x* < xR. Se...
Leer documento completo
Regístrate para leer el documento completo.