3.2 Ilustración gráfica de problemas de programación 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.
una representación gráfica de este tipo proporciona una visión global de las propiedades 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.
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. 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.





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 restricciones funcionales se sustituyen por la restricción no lineal 9x{ + 5x₂ < 216. La solución óptima sigue siendo (a^ , x₂) = (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 = 3x_x + x₂), pero que no necesite 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
entonces la representación gráfica en la figura 13.6 indica que la solución óptima es x_x – x₂ = 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 factible en ningún punto.) 

Por otro lado, si



 ilustra que la solución óptima es (*_l5 x₂ ) = (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 lo tanto, 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.

DATO: En general, los algoritmos de programación no lineal no pueden distinguir entre un máximo local y un máximo global (excepto si encuentran 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.

ahora pues una función de este tipo cuya curvatura siempre es “hacia abajo” (o que no tiene curvatura) se llama función cóncava.¹ 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.² (Así, una función lineal es tanto cóncava como convexa.)

 En la figura  Note que ilustra una función que no es cóncava, ni convexa pues alterna sus curvaturas hacia arriba y hacia abajo.