3.1 Conceptos básicos de problemas de programación no lineal

Programación no lineal (PNL) es el proceso de resolución de un sistema de igualdades y desigualdades sujetas a un conjunto de restricciones sobre un conjunto de variables reales desconocidas, con una función objetivo a maximizar, cuando alguna de las restricciones o la función objetivo no son lineales.

Una suposición importante de programación lineal es que todas sus funciones (función objetivo y funciones de restricción) son lineales. Aunque, en esencia, esta suposición se cumple para muchos problemas prácticos, con frecuencia no es así.
De hecho muchos economistas han encontrado que cierto grado de no linealidad es la regla, y no la excepción, en los problemas de planeación económica, por lo cual, muchas veces es necesario manejar problemas de programación no lineal, lo cual vamos a analizar enseguida.

De la manera general el problema de programación no lineal consiste en encontrar:
X=(X1, X2, X3, X4, XN)
para Maximizar f(X), sujeta a Gi(X)<= bi para i=1,2…..m, Y X=>0, Donde f(X) y gi(x) son funciones dadas de n variables de decisión.

La programación lineal da respuesta a situaciones en las que se exige maximizar o minimizar funciones que se encuentran sujetas a determinadas limitaciones, que llamaremos restricciones.

Su empleo es frecuente en aplicaciones de la industria, la economía, la estrategia militar, etc.

Función objetivo

En esencia la programación lineal consiste en optimizar (maximizar o minimizar) una función objetivo, que es una función lineal de varias variables:

f(x,y) = ax + by.

Restricciones

La función objetivo está sujeta a una serie de restricciones, expresadas por inecuaciones lineales:

	a1x + b1y ≤ c1
	a2x + b2y ≤c2
	…    …    …
	anx + bny ≤cn

Cada desigualdad del sistema de restricciones determina un semiplano.

Solución factible

El conjunto intersección, de todos los semiplanos formados por las restricciones, determina un recinto, acotado o no, que recibe el nombre de región de validez o zona de soluciones factibles.

Solución óptima

El conjunto de los vértices del recinto se denomina conjunto de soluciones factibles básicas y el vértice donde se presenta la solución óptima se llama solución máxima (o mínima según el caso).

Valor del programa lineal

El valor que toma la función objetivo en el vértice de solución óptima se llama valor del programa lineal.

PASOS PARA RESOLVER UN PROBLEMA DE PROGRAMACION LINEAL

1. Elegir las incógnitas.

2. Escribir la función objetivo en función de los datos del problema.

3. Escribir las restricciones en forma de sistema de inecuaciones.

4. Averiguar el conjunto de soluciones factibles representando gráficamente las restricciones.

5. Calcular las coordenadas de los vértices del recinto de soluciones factibles (si son pocos).

6. Calcular el valor de la función objetivo en cada uno de los vértices para ver en cuál de ellos presenta el valor máximo o mínimo según nos pida el problema (hay que tener en cuenta aquí la posible no existencia de solución si el recinto no está acotado).

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.

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 no lineal. Se introducirán las clases más importantes y después se describirá cómo se pueden resolver algunos de estos problemas.
Los tipos de problemas de programación no lineal son:
 Optimización no restringida.
 Optimización lineal-mente restringida.
 Programación cuadrática
 Programación convexa.
 Programación separable.
 Programación no convexa.
 Programación geométrica.
 Programación fraccional.
 Problema de complementariedad.

OPTIMIZACIÓN NO RESTRINGIDA

Los problemas de optimización no restringida no tienen restricciones, por lo que la función objetivo es sencillamente

Maximizar f(x)

sobre todos los valores x= (x1, x₂,…,x_n). Según el repaso del apéndice 3, la condición necesa­ria para que una solución específica x = x* sea óptima cuando f(x) es una función diferenciable es

  

Cuando f (x) es cóncava, esta condición también es suficiente, con lo que la obtención de x* se reduce a resolver el sistema de las n ecuaciones obtenidas al establecer las n derivadas parciales iguales a cero. Por desgracia, cuando se trata de funciones no lineales f (x), estas ecuaciones suelen ser no lineales también, en cuyo caso es poco probable que se pueda obtener una solu­ción analítica simultánea. ¿Qué se puede hacer en ese caso? Las secciones 13.4 y 13.5 descri­ben procedimientos algorítmicos de búsqueda para encontrar x* primero para n = 1 y luego para n > 1. Estos procedimientos también tienen un papel importante en la solución de varios tipos de problemas con restricciones, que se describirán en seguida. La razón es que muchos algo­ritmos para problemas restringidos están construidos de forma que se adaptan a versiones no restringidas del problema en una parte de cada iteración.

Cuando una variable Xj tiene una restricción de no negatividad, x- > 0, la condición ne­cesaria (y tal vez) suficiente anterior cambia ligeramente a

 

para cada j de este tipo. Esta condición se ilustra en la figura 13.11, donde la solución óptima de un problema con una sola variable es x = 0 aun cuando la derivada ahí es negativa y no cero. Como este ejemplo tiene una función cóncava para maximizar sujeta a una restricción de no negatividad, el que su derivada sea menor o igual a 0 en # = 0, es una condición necesaria y su­ficiente para que x= 0 sea óptima.

Un problema que tiene algunas restricciones de no negatividad y que no tiene restriccio­nes funcionales es un caso especial (m = 0) de la siguiente clase de problemas.

OPTIMIZACIÓN LINEALMENTE RESTRINGIDA

Los problemas de optimización linealmente restringida se caracterizan por restricciones que se ajustan por completo a la programación lineal, de manera que todas las funciones de restric­ción g¡ (x) son lineales, pero la función objetivo es no lineal. El problema se simplifica mucho si sólo se tiene que tomar en cuenta una función no lineal junto con una región factible de programación lineal. Se han desarrollado varios algoritmos especiales basados en una exten­sión del método símplex para analizar la función objetivo no lineal.

Un caso especial importante descrito a continuación es la programación cuadrática.

 

PROGRAMACIÓN CUADRÁTICA

 

De nuevo los problemas de programación cuadrática tienen restricciones lineales, pero ahora la función objetivo /(x) debe ser cuadrática. Entonces, la única diferencia entre éstos y un

 

problema de programación lineal es que algunos términos de la función objetivo incluyen el cuadrado de una variable o el producto de dos variables.

  

PROGRAMACIÓN CONVEXA

La programación convexa abarca una amplia clase de problemas, entre ellos como casos espe­ciales, están todos los tipos anteriores cuando /(x) es cóncava. Las suposiciones son

1. f(x) es cóncava.
2. Cada una de las g(x) es convexa.

PROGRAMACIÓN SEPARABLE

La programación separable es un caso especial de programación convexa, en donde la suposi­ción adicional es

Todas las funciones f(x) y g(x) son funciones separables.

Una función separable es una función en la que cada término incluye una sola variable, por lo que la función se puede separar en una suma de funciones de variables individuales. Por ejem­plo, si  f(x) es una función separable, se puede expresar como

son cada tina funciones de una sola va­riable x1 y x₂, respectivamente. Usando el mismo razonamiento, se puede verificar que la función considerada en la figura 13.7 también es una función separable.

Es importante distinguir estos problemas de otros de programación convexa, pues cual­quier problema de programación separable se puede aproximar muy de cerca mediante uno de programación lineal y, entonces, se puede aplicar el eficiente método símplex.

son cada tina funciones de una sola va­riable x1 y x₂, respectivamente. Usando el mismo razonamiento, se puede verificar que la función considerada en la figura 13.7 también es una función separable.

Es importante distinguir estos problemas de otros de programación convexa, pues cual­quier problema de programación separable se puede aproximar muy de cerca mediante uno de programación lineal y, entonces, se puede aplicar el eficiente método símplex.

PROGRAMACIÓN NO CONVEXA

La programación no convexa incluye todos los problemas de programación no lineal que no sa­tisfacen las suposiciones de programación convexa. En este caso, aun cuando se tenga éxito en encontrar un máximo local, no hay garantía de que sea también un máximo global. Por lo tanto, no se tiene un algoritmo que garantice encontrar una solución óptima para todos estos problemas; pero sí existen algunos algoritmos bastante adecuados para encontrar máximos lo­cales, en especial cuando las formas de las funciones no lineales no se desvían demasiado de aquellas que se supusieron para programación convexa. En la sección 13.10 se presenta uno de estos algoritmos.

Ciertos tipos específicos de problemas de programación no convexa se pueden resolver sin mucha dificultad mediante métodos especiales. Dos de ellos, de gran importancia, se pre­sentarán más adelante.

PROGRAMACIÓN GEOMÉTRICA

Cuando se aplica programación no lineal a problemas de diseño de ingeniería, muchas veces la función objetivo y las funciones de restricción toman la forma

 

En tales casos, las c_i y a _ty representan las constantes físicas y las x_} son las variables de diseño. Estas funciones por lo general no son ni cóncavas ni convexas, por lo que las técnicas de pro­gramación convexa no se pueden aplicar directamente a estos problemas deprogramacióngeo- métrica. Sin embargo, existe un caso importante en el que el problema se puede transformar en un problema de programación convexa equivalente. Este caso es aquel en el que todos los coeficientes c¿ en cada función son estrictamente positivos, es decir, las funciones son polino­mios positivos generalizados (ahora llamados posinomiales), y la función objetivo se tiene que minimizar. El problema equivalente de programación convexa con variables de decisión y_x, y₂,…, y_n se obtiene entonces al establecer

en todo el modelo original. Ahora se puede aplicar un algoritmo de programación convexa. Se ha desarrollado otro procedimiento de solución para resolver estos problemas de progra­mación posinomial, al igual que para problemas de programación geométrica de otros tipos.¹

PROGRAMACIÓN FRACCIONAL

Suponga que la función objetivo se encuentra en la forma de una fracción, esto es, la razón o cociente de dos funciones,

Estos problemas de programación fraccional surgen, por ejemplo, cuando se maximiza la ra­zón de la producción entre las horas-hombre empleadas (productividad), o la ganancia entre el capital invertido (tasa de rendimiento), o el valor esperado dividido entre la desviación es­tándar de alguna medida de desempeño para una cartera de inversiones (rendimiento/ries­go). Se han formulado algunos procedimientos de solución especiales¹ para ciertas formas de f1(x) y f2 (x)

 Cuando se puede hacer, el enfoque más directo para resolver un problema de programa­ción fraccional es transformarlo en un problema equivalente de algún tipo estándar que dis­ponga de un procedimiento eficiente. Para ilustrar esto, suponga que f(x) es de la forma de programación fraccional lineal

 

donde c y d son vectores renglón, x es un vector columna y c₀ y d_Q son escalares. También su­ponga que las funciones de restricción g¡ (x) son lineales, es decir, las restricciones en forma matricial son Ax < b y x > 0.

Con algunas suposiciones débiles adicionales, el problema se puede transformar en un problema equivalente de programación lineal si se establece

 

que se puede resolver con el método símplex. En términos generales, se puede usar el mismo tipo de transformación para convertir un problema de programación fraccional con /¡(x) cóncava, f₂ (x) convexa y g¡ (x) convexas, en un problema equivalente de programación con­vexa.

3.4 Optimización clásica

La teoría de optimización clásica o programación matemática está constituida por un conjunto de resultados y métodos analíticos y numéricos enfocados a encontrar e identificar al mejor candidato de entre una colección de alternativas, sin tener que enumerar y evaluar explícitamente todas esas alternativas. Un problema de optimización es, en general, un problema de decisión.

Si la restricción no existe, o es una restricción de igualdad, con menor o igual número de variables que la función objetivo entonces, el cálculo diferencial, da la respuesta, ya que solo se trata de buscar los valores extremos de una función.

Bibliografía

http://www.sangakoo.com/es/temas/concavidad-y-convexidad-puntos-de-inflexion-de-una-funcion

http://nuyoo.utm.mx/~jjf/rna/guia_foe.pdf

http://www.universoformulas.com/matematicas/analisis/maximos-minimos-funcion/

3.4.1 Puntos de inflexión

Ya antes visto el video hablar sofre puntos de inflexión ahora podemos decir como repaso que:
Se define un punto de inflexión como el punto en que la función pasa de ser convexa a cóncava o de cóncava a convexa.
Un punto de inflexión es un punto donde cambia la curvatura de la función. 

En la siguiente gráfica podemos ver que cuando x = 0, la gráfica pasa de ser cóncava a ser convexa, por lo que podemos decir que el punto de inflexión esta en X = 0.

Una característica de los puntos de inflexión es que son los puntos donde la función derivada tiene máximos y mínimos. Si nos fijamos, cuando nos acercamos a un punto de inflexión la función cada vez crece más (o decrece menos), pero al sobrepasar el punto de inflexión la función empieza a crecer menos (o decrecer menos). Esto significa que justamente donde haya un punto de inflexión la derivada tendrá un máximo o un mínimo. Consecuentemente encontraremos los puntos de inflexión buscando ceros de la segunda derivada.

Vamos a ilustrar el proceso con un ejemplo para así dar una explicación simple y clara:

Consideraremos la función F(x) = x³ - 3x  (es la función representada en la anterior gráfica).

Sabemos ya calcular los máximos y los mínimos de la función f(x)  usando la primera derivada. La expresión de ésta es 3x² - 3  y justamente encontramos máximos y mínimos respectivamente en x = -14  y x = 1 .  Si representamos la gráfica de la derivada queda:

Observamos que justamente donde la derivada tiene un mínimo es donde la función tiene el punto de inflexión.

Para saber qué punto es vamos a derivar la función derivada e igualarla a cero: F´´(x) = 6x=0 = x = 0/6 = 0, y por tanto la función original en x = 0  tiene un punto de inflexión.

3.4.2 Máximos y mínimos

Mínimo (fuerte): Un punto extremo X0 de una función f(X0) define un mínimo de la función si f(X0+h) > f(X0), donde X0 es cualquier punto de la función y h en valor absoluto es suficientemente pequeña.

Máximo (fuerte): Un punto extremo X0 de una función f(X0) define un máximo de la función si f(X0+h) < f(X0), donde X0 es cualquier punto de la función y h en valor absoluto es suficientemente pequeña.

Una función puede contener varios máximos y mínimos, identificados por los puntos extremos de la función.

Puntos minimax.

El punto minimax de la función lagrangiana es otro concepto relacionado con la solución de un problema de optimización. Si bien su definición no le hace útil a la hora de la resolución directa del problema, sí constituye un paso intermedio muy importante en la obtención del problema dual, que estudiaremos más adelante. En esta sección definimos dicho punto y estudiamos su relación con otro concepto, el punto de silla de la lagrangiana. La relación del punto minimax con la solución del problema de programación no lineal se obtiene de forma inmediata sin mas que tener en cuenta que: Min L (x, ë ) = f (x) − Max ët [g(x) − b]R m+R m+ Si gi (x) – bi ≤ 0, entonces ëi [gi(x) - bi] ≤ 0, luego Max ëi ( gi (x) − bi ) = 0R m+ (se alcanza en ë = 0). Por tanto, si x ∈ X, Min L (x, ë ) = f (x) .R m+ Si gi (x) – bi > 0, entonces Sup ëi [gi(x) - bi] = ∞, por lo que en este caso no se alcanza el R m+ mínimo de la Lagrangiana. Por tanto, Max Min L (x, ë ) = Max f (x) D R m+ X Así pues, si (x0, ë0) es un punto minimax, x0 es una solución óptima del problema original.