Programacion no lineal
Páginas: 16 (3764 palabras)
Publicado: 2 de noviembre de 2011
3.2 Ilustración Gráfica de Problemas de Programacion No Lineal
Cuando un problema de programación no lineal tiene sólo una o dos variables, se puede representar gráficamente de forma muy parecida al ejemplo de la Wyndor Glass Co. de programación lineal, de la sección 3.1. Se verán unos cuantos ejemplos, ya que una representación gráfica de este tipo proporciona una visión global de laspropiedades de las soluciones óptimas de programación lineal y no lineal. Con el fin de hacer hincapié en las diferencias entre programación lineal y no lineal, se usarán algunas variaciones no lineales del problema de la Wyndor Glass Co.
La figura 13.5 muestra lo que ocurre con este problema si los únicos cambios que se hacen al modelo de la sección 3.1 son que la segunda y tercera restriccionesfuncionales se sustituyen por la restricción no lineal 9x{ + 5x2 < 216. Compare las figuras 13.5 y 3.3. La solución óptima sigue siendo (a^ , x2) = (2,6). Todavía se encuentra sobre la frontera de la región factible, pero no es una solución factible en un vértice (FEV). La solución óptima pudo haber sido una solución FEV con una función objetivo diferente (verifique Z = 3xx + x2), pero que nonecesite serlo significa que ya no se puede aprovechar la gran simplificación utilizada en programación lineal que permite limitar la búsqueda de una solución óptima para las soluciones FEV
Ahora suponga que las restricciones lineales de la sección 3.1 se conservan sin cambio, pero que la función objetivo se hace no lineal. Por ejemplo, si
entonces la representación gráfica en la figura13.6 indica que la solución óptima es xx – x2 = 5, que de nuevo se encuentra en la frontera de la región factible. (El valor óptimo de Z es Z = 857; así, la figura 13.6 muestra el hecho de que el lugar geométrico de todos los puntos para los que Z = 857 tiene en común con la región factible sólo este punto, mientras que el lugar geométrico de los puntos con Z más grande no toca la región factibleen ningún punto.) Por otro lado, si
entonces la figura 13.7 ilustra que la solución óptima es (*l5 x2 ) = (3,3), que se encuentra dentro de la frontera de la región factible. (Se puede comprobar que esta solución es óptima si se usa cálculo para derivarla como un máximo global no restringido; como también satisface las restricciones, debe ser óptima para el problema restringido.) Por lotanto, es necesario que
un algoritmo general para resolver problemas de este tipo tome en cuenta todas las soluciones en la región factible, y no sólo aquellas que están sobre la frontera.
Otra complicación que surge en programación no lineal es que un máximo local no necesariamente es un máximogbbal (la solución óptima global). Por ejemplo, considere la función de una solavariable graficada en la figura 13.8. En el intervalo 0 < x < 5, esta función tiene tres máximos locales — x=0,x=2,x=4—pero sólo uno de éstos—x – 4—es un máximo global. (De igual manera, existen mínimos locales en x = 1,3 y 5, pero sólo x = 5 es un mínimo global.)
En general, los algoritmos de programación no lineal no pueden distinguir entre un máximo local y un máximo global (excepto siencuentran otro máximo local mejor), por lo que es determinante conocer las condiciones bajo las que se garantiza que un máximo local es un máximo global en la región factible. Recuerde que en cálculo, cuando se maximiza una función ordinaria (doblemente diferenciable) de una sola variable f(x) sin restricciones, esta garantía está dada cuando
Una función de este tipo cuya curvaturasiempre es “hacia abajo” (o que no tiene curvatura) se llama función cóncava.1 De igual manera, si se sustituye < por >, de manera que la función tiene siempre una curvatura “hacia arriba” (o no tiene curvatura), se llama función convexa.2 (Así, una función lineal es tanto cóncava como convexa.) En la figura 13.9 se pueden ver ejemplos de esto. Note que la figura 13.8 ilustra una función que no...
Cuando un problema de programación no lineal tiene sólo una o dos variables, se puede representar gráficamente de forma muy parecida al ejemplo de la Wyndor Glass Co. de programación lineal, de la sección 3.1. Se verán unos cuantos ejemplos, ya que una representación gráfica de este tipo proporciona una visión global de laspropiedades de las soluciones óptimas de programación lineal y no lineal. Con el fin de hacer hincapié en las diferencias entre programación lineal y no lineal, se usarán algunas variaciones no lineales del problema de la Wyndor Glass Co.
La figura 13.5 muestra lo que ocurre con este problema si los únicos cambios que se hacen al modelo de la sección 3.1 son que la segunda y tercera restriccionesfuncionales se sustituyen por la restricción no lineal 9x{ + 5x2 < 216. Compare las figuras 13.5 y 3.3. La solución óptima sigue siendo (a^ , x2) = (2,6). Todavía se encuentra sobre la frontera de la región factible, pero no es una solución factible en un vértice (FEV). La solución óptima pudo haber sido una solución FEV con una función objetivo diferente (verifique Z = 3xx + x2), pero que nonecesite serlo significa que ya no se puede aprovechar la gran simplificación utilizada en programación lineal que permite limitar la búsqueda de una solución óptima para las soluciones FEV
Ahora suponga que las restricciones lineales de la sección 3.1 se conservan sin cambio, pero que la función objetivo se hace no lineal. Por ejemplo, si
entonces la representación gráfica en la figura13.6 indica que la solución óptima es xx – x2 = 5, que de nuevo se encuentra en la frontera de la región factible. (El valor óptimo de Z es Z = 857; así, la figura 13.6 muestra el hecho de que el lugar geométrico de todos los puntos para los que Z = 857 tiene en común con la región factible sólo este punto, mientras que el lugar geométrico de los puntos con Z más grande no toca la región factibleen ningún punto.) Por otro lado, si
entonces la figura 13.7 ilustra que la solución óptima es (*l5 x2 ) = (3,3), que se encuentra dentro de la frontera de la región factible. (Se puede comprobar que esta solución es óptima si se usa cálculo para derivarla como un máximo global no restringido; como también satisface las restricciones, debe ser óptima para el problema restringido.) Por lotanto, es necesario que
un algoritmo general para resolver problemas de este tipo tome en cuenta todas las soluciones en la región factible, y no sólo aquellas que están sobre la frontera.
Otra complicación que surge en programación no lineal es que un máximo local no necesariamente es un máximogbbal (la solución óptima global). Por ejemplo, considere la función de una solavariable graficada en la figura 13.8. En el intervalo 0 < x < 5, esta función tiene tres máximos locales — x=0,x=2,x=4—pero sólo uno de éstos—x – 4—es un máximo global. (De igual manera, existen mínimos locales en x = 1,3 y 5, pero sólo x = 5 es un mínimo global.)
En general, los algoritmos de programación no lineal no pueden distinguir entre un máximo local y un máximo global (excepto siencuentran otro máximo local mejor), por lo que es determinante conocer las condiciones bajo las que se garantiza que un máximo local es un máximo global en la región factible. Recuerde que en cálculo, cuando se maximiza una función ordinaria (doblemente diferenciable) de una sola variable f(x) sin restricciones, esta garantía está dada cuando
Una función de este tipo cuya curvaturasiempre es “hacia abajo” (o que no tiene curvatura) se llama función cóncava.1 De igual manera, si se sustituye < por >, de manera que la función tiene siempre una curvatura “hacia arriba” (o no tiene curvatura), se llama función convexa.2 (Así, una función lineal es tanto cóncava como convexa.) En la figura 13.9 se pueden ver ejemplos de esto. Note que la figura 13.8 ilustra una función que no...
Leer documento completo
Regístrate para leer el documento completo.