Optimización No Linea1

  • Published on
    10-Dec-2015

  • View
    7

  • Download
    2

Embed Size (px)

DESCRIPTION

optimizacion no lineal

Transcript

10. Programacin no linealEnmatemticas,Programacin no lineal(PNL) es el proceso de resolucin de un sistema de igualdades y desigualdades sujetas a un conjunto de restricciones sobre un conjunto de variables reales desconocidas, con un funcin objetivo a maximizar (o minimizar), cuando alguna de las restricciones o la funcin objetivo no son lineales.Formulacin matemtica del problema[editar]El problema de programacin no lineal puede enunciarse de una forma muy simple:maximizar una funcin objetivoominimizar una funcin objetivo (de coste)donde

Mtodos de resolucin del problemaSi la funcin objetivofes lineal y elespaciorestringido es unpolitopo, el problema es deProgramacin linealy puede resolverse utilizando alguno de los bien conocidos algoritmos de programacin lineal.Si la funcin objetivo escncava(problema de maximizacin), oconvexa(problema de minimizacin) y el conjunto de restricciones esconvexo, entonces se puede utilizar el mtodo general deOptimizacin convexaExiste una variedad de mtodos para resolver problemas no convexos. Uno de ellos consiste en utilizar formulaciones especiales de problemas de programacin lineal. Otro mtodo implica el uso de tcnicas deRamificacin y poda, cuando el problema se divide en subdivisiones a resolver mediante aproximaciones que forman un lmite inferior del coste total en cada subdivisin. Mediante subdivisiones sucesivas, se obtendr una solucin cuyo coste es igual o inferior que el mejor lmite inferior obtenido por alguna de las soluciones aproximadas. Esta solucin es ptima, aunque posiblemente no sea nica. El algoritmo puede ser parado antes, con la garanta de que la mejor solucin ser mejor que la solucin encontrada en un porcentaje acotado. Ello se utiliza en concreto en problemas importantes y especialmente difciles y cuando el problema cuenta con costes inciertos o valores donde la incertidumbre puede ser estimada en un grado de fiabilidad apropiado.Lascondiciones de Karush-Kuhn-Tuckerproporcionan las condiciones necesarias para que una solucin sea ptima.EjemplosEjemplo bidimensional

La interseccin de la lnea con el espacio de restricciones representa la solucin.Un problema sencillo Maximizar f(x) =x1+x2sujeto a las restricciones:x1 0x2 0x12+x22 1x12+x22 2dondex= (x1,x2)Ejemplo tridimensional

La interseccin de la superficie superior con el espacio de restricciones en el centro representa la solucin.Otro problema simple funcin objetivo a ser maximizadaf(x) =x1x2+x2x3

se define por la restricciones: x12x22+x32 2x12+x22+x32 10dondex= (x1,x2,x3)Los problemas de programacin no lineal se presentan de muchas formas distintas. Al contrario del mtodo smplex para programacin lineal, no se dispone de un algoritmo que resuelva todos estos tipos especiales de problemas. En su lugar, se han desarrollado algoritmos para algunasclases(tipos especiales) de problemas de programacin no lineal. Se introducirn las clases ms importantes y despus se describir cmo se pueden resolver algunos de estos problemas.Si la funcin objetivofes lineal y el espacio restringido es un politopo, el problema es de Programacin lineal y puede resolverse utilizando alguno de los bien conocidos algoritmos de programacin lineal.Si la funcin objetivo es cncava (problema de maximizacin), o convexa (problema de minimizacin) y el conjunto de restricciones es convexo, entonces se puede utilizar el mtodo general de Optimizacin convexaExiste una variedad de mtodos para resolver problemas no convexos. Uno de ellos consiste en utilizar formulaciones especiales de problemas de programacin lineal. Otro mtodo implica el uso de tcnicas de Ramificacin y poda, cuando el problema se divide en subdivisiones a resolver mediante aproximaciones que forman un lmite inferior del coste total en cada subdivisin. Mediante subdivisiones sucesivas, se obtendr una solucin cuyo coste es igual o inferior que el mejor lmite inferior obtenido por alguna de las soluciones aproximadas. Esta solucin es ptima, aunque posiblemente no sea nica. El algoritmo puede ser parado antes, con la garanta de que la mejor solucin ser mejor que la solucin encontrada en un porcentaje acotado. Ello se utiliza en concreto en problemas importantes y especialmente difciles 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 condiciones necesarias para que una solucin sea ptima.Los tipos de problemas de optimizaacin no lineal son:1. Optimizacin no restringida.2. Optimizacin linealmente restringida.3. Programacin cuadrtica4. Programacin convexa.5. Programacin separable.6. Programacin no convexa.7. Programacin geomtrica.8. Programacin fraccional.9. Problema de complementariedad.ALGORITMOS SIN RESTRICCINEn esta seccin se presentarn dos algoritmos para el problema no restringido: el algoritmo debsqueda directay el algoritmo degradiente.Mtodo de bsqueda directaLos mtodos de bsqueda directa se aplican principalmente a funciones estrictamente unimo- dales de una variable. Aunque puede parecer trivial el caso, la seccin 21.1.2 muestra que la optimizacin de funciones de una variable juega un papel clave en el desarrollo de los algoritmos de varias variables, ms generales.La idea de los mtodos de bsqueda directa es identificar elintervalo de incertidum- breque comprenda al punto de solucin ptima. El procedimiento localiza el ptimo estrechando en forma progresiva el intervalo de incertidumbre hasta cualquier grado de exactitud que se desee.En estaseccinsepresentan dos algoritmos estrechamente relacionados: los mtodos debsqueda dictomo y de seccin dorada (o urea). Ambos buscan la maximizacin de una funcin unimodal/(x) en el intervaloa ^ x < b,que se sabe que incluye el punto ptimox*.Los dos mtodos comienzan con /0=(a, b)que representa el intervalo inicial de incertidumbre.Paso generali. Sea /, _ , =(xDxR) el intervalo actual de incertidumbre (en la iteracin 0,xL= ayxR= b).A continuacin se definenxxyx2tales quexj^ ^ ^ x2^ xrEl siguiente intervalo de incertidumbre, /z, se define como sigue:1. Sif(xx) >/(x2), entoncesxL< x* < x2.Se definenxR= x2e /, =(xL, x2)(vase la figura 21.2[a]).2. Sif(xx) < f(x2\entoncesxx< x* < xR.Se definenxL= xxeI = (xhxR)(vase la figura 21.1 [b]). .3. Sif{x\)= /(jc2), entoncesxx< x* < x2.Se definenxL= x2e /, = (xbx2).La manera en que se determinanxxy x2garantiza que /, < /,_pcomo se demostrar en breve. El algoritmo termina en la iteracinksilk1. Estos procedimientos tambin tienen un papel importante en la solucin de varios tipos de problemas con restricciones, que se describirn en seguida. La razn es que muchos algoritmos para problemasrestringidosestn construidos de forma que se adaptan a versionesno restringidasdel problema en una parte de cada iteracin.Cuando una variable Xj tiene una restriccin de no negatividad, x- > 0, la condicin necesaria (y tal vez) suficiente anterior cambia ligeramente apara cadajde este tipo. Esta condicin se ilustra en la figura 13.11, donde la solucin ptima de un problema con una sola variable esx= 0 aun cuando la derivada ah es negativa y no cero. Como este ejemplo tiene una funcin cncava para maximizar sujeta a una restriccin de no negatividad, el que su derivada sea menor o igual a 0 en # = 0, es una condicin necesaria y suficiente para quex=0 sea ptima.Un problema que tiene algunas restricciones de no negatividad y que no tiene restricciones funcionales es un caso especial(m= 0) de la siguiente clase de problemas.OPTIMIZACIN LINEALMENTE RESTRINGIDALos problemas de optimizacin linealmente restringida se caracterizan por restricciones que se ajustan por completo a la programacin lineal, de manera quetodaslas funciones de restriccing(x) son lineales, pero la funcin objetivo es no lineal. El problema se simplifica mucho si slo se tiene que tomar en cuenta una funcin no lineal junto con una regin factible de programacin lineal. Se han desarrollado varios algoritmos especiales basados en unaextensindel mtodo smplex para analizar la funcin objetivo no lineal.Un caso especial importante descrito a continuacin es la programacin cuadrtica.PROGRAMACIN CUADRTICADe nuevo los problemas deprogramacin cuadrticatienen restricciones lineales, pero ahora la funcin objetivo /(x) debe sercuadrtica.Entonces, la nica diferencia entre stos y unproblema de programacin lineal es que algunos trminos de la funcin objetivo incluyen elcuadradode una variable o elproductode dos variables.PROGRAMACIN CONVEXALaprogramacin convexaabarca una amplia clase de problemas, entre ellos como casos especiales, estn todos los tipos anteriores cuando /(x) es cncava. Las suposiciones son1. f(x) es cncava.2. Cada una de las g(x) es convexa.PROGRAMACIN SEPARABLELaprogramacin separablees un caso especial de programacin convexa, en donde la suposicin adicional esTodas las funciones f(x) yg(x)son funciones separables.Una funcin separable es una funcin en la quecada trminoincluyeuna sola variable, por lo que la funcin se puedesepararen una suma de funciones de variables individuales. Por ejemplo, si f(x) es una funcin separable, se puede expresar como

son cada tina funciones de una sola variable x1 y x2, respectivamente. Usando el mismo razonamiento, se puede verificar que la funcin considerada en la figura 13.7 tambin es una funcin separable.Es importante distinguir estos problemas de otros de programacin convexa, pues cualquier problema de programacin separable se puede aproximar muy de cerca mediante uno de programacin lineal y, entonces, se puede aplicar el eficiente mtodo smplex.

son cada tina funciones de una sola variable x1 y x2, respectivamente. Usando el mismo razonamiento, se puede verificar que la funcin considerada en la figura 13.7 tambin es una funcin separable.Es importante distinguir estos problemas de otros de programacin convexa, pues cualquier problema de programacin separable se puede aproximar muy de cerca mediante uno de programaci