ILUSTRACION 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 re­presentar gráficamente de forma muy parecida al ejemplo de la Wyndor Glass Co. de progra­mació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 las propiedades de las soluciones ópti­mas 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 ha­cen al modelo de la sección 3.1 son que la segunda y tercera restricciones funcionales se susti­tuyen por la restricción no lineal 9x{ + 5x₂ < 216. Compare las figuras 13.5 y 3.3. La solu­ció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 solu­ciones 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 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 lu­gar geométrico de los puntos con Z más grande no toca la región factible en ningún punto.) Por otro lado, si

 

entonces la figura 13.7 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.

  

Otra complicación que surge en programación no lineal es que un máximo local no nece­sariamente es un máximogbbal (la solución óptima global). Por ejemplo, considere la fun­ción de una sola variable 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 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. Recuerde que en cálculo, cuando se maximiza una fun­ción ordinaria (doblemente diferenciable) de una sola variable f(x) sin restricciones, esta ga­rantía está dada cuando

 

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 13.9 se pueden ver ejemplos de esto. Note que la figura 13.8 ilustra una función que no es cóncava, ni convexa pues alterna sus curvaturas hacia arriba y hacia abajo.

Las funciones de variables múltiples también se pueden caracterizar como cóncavas o convexas si su curvatura es siempre hacia abajo o hacia arriba. Estas definiciones intuitivas se fundamentan en términos precisos que, junto con cierta profundización en los conceptos, se presentan en el apéndice 2. El apéndice 2 proporciona una prueba conveniente para verifi­car si una función de dos variables es cóncava, convexa o ninguna de las dos.

La siguiente es una forma conveniente de verificar esto para una función de más de dos variables cuando la función consiste en una suma de funciones más pequeñas cada una de sólo

una o dos variables. Si cada función más pequeña es cóncava, entonces la función completa es cóncava. De manera similar, la función completa es convexa si cada función más pequeña es convexa.

 

que es la suma de las dos funciones más pequeñas dadas en los paréntesis cuadrados. La pri­mera función más pequeña 4*! – x\ es una función de la variable x_x nada más, por lo que puede verse que es cóncava si se observa que su segunda derivada es negativa. La segunda función más pequeña -(x₂ – x¿ )² es una fimción de x₂ y por lo que se puede aplicar la prueba para funciones de dos variables dada en el apéndice 2. De hecho, este apéndice usa esta función en particular para ilustrar la prueba y encuentra que la función es cóncava. Como las dos funciones más pequeñas son cóncavas, la función completa f (jVj ,x₂,x₃) debe ser cóncava.

Si un problema de programación no lineal no tiene restricciones, el hecho de que la fun­ción objetivo sea cóncava garantiza que un máximo local es un máximoglobal. (De igual mane­ra, una función objetivo convexa asegura que un mínimo local es un mínimo global.) Si existen restricciones, entonces se necesita una condición más para dar esta garantía, a saber, que la re­gión factible sea un conjunto convexo. Como se analiza en el apéndice 2, un conjunto conve­xo es sencillamente un conjunto de puntos tales que, para cada par de puntos de la colección, el segmento de recta que los une está totalmente contenido en la colección. Así, la región fac­tible en el problema original de la Wyndor Glass Co. (vea la figura 13.6 o 13.7) es un conjun­to convexo. De hecho, la región factible para cualquier otro problema de programación lineal es un conjunto convexo. De igual manera, la región factible de la figura 13.5 también es un conjunto convexo.

En general la región factible para un problema de programación no lineal es un conjunto convexo siempre que todas las funciones g¡ (x) [para las restricciones g¿ (x) < b_{ ] sean conve­xas. Para el ejemplo de la figura 13.5, las dos g_t (x) son convexas, ya que g_x (x) = x_x (una fun­ción lineal es automáticamente cóncava y convexa) y g₂ (x) = 9x\ + 5x\ (tanto 9x\ como 5x₂ son funciones convexas, por lo que su suma es una función convexa). Estas dos funciones convexas g¡ (x) conducen a que la región factible de la figura 13.5 sea un conjunto convexo.

Ahora se analizará qué pasa cuando sólo una de estas funciones g¡ (x) es una función cón­cava. En particular, suponga que el único cambio que se hace al ejemplo de la figura 13.5 es

son funciones cóncavas. La nueva región factible mostrada en la figura 13.10 no es un conjun­to convexo. <Por qué? Porque contiene pares de puntos, como (0, 7) y (4, 3), tales que parte del segmento de recta que los une no está en la región factible. En consecuencia, no se puede garantizar que un máximo local sea un máximo global. De hecho, este ejemplo tiene dos má­ximos locales (0, 7) y (4, 3), pero sólo (0, 7) es un máximo global.

Entonces, para garantizar que un máximo local sea un máximo global para un problema de programación no lineal con restricciones (x) < b¡ (i = 1,2,…, m) y x > 0, la función obje­tivo /(x) debe ser cóncava y cada g_í (x) debe ser convexa. Un problema de este tipo se llama problema de programación convexa y es una de las clases más importantes de la programación no lineal que se estudiará en la siguiente sección.