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.

Con el fin de ilustrar de forma adecuada la estructura y composición de un problema de optimización, introduciremos a continuación un sencillo ejemplo.

Ejemplo 1 (Construcción de una caja con volumen máximo) Supongamos que queremos determinar las dimensiones de una caja rectangular de forma que contenga el mayor volumen posible, pero utilizando para ello una cantidad fija de material. El problema en forma abstracta se podría plantear en los siguientes términos Maximizar Volumen de la caja sujeto a Área lateral fija Con el fin de resolver este problema habrá que modelar matemáticamente, es decir tendremos que expresarlo en términos matemáticos.

El primer paso para modelar un problema de optimización es identificar y definir las variables que están implicadas en dicho problema, en este caso y puesto que estamos tratando de determinar el tamaño de una caja rectangular, la opción más clara es considerar como variables sus tres dimensiones rectangulares usuales (ancho, largo, alto) y que representamos con x, y, z. Con estas variables, la función para la que tenemos que encontrar el mejor valor será el volumen de la caja que puede expresarse como V (x, y, z) = x y z.

 A continuación debemos tener en cuenta las limitaciones existentes sobre el material. Como este material se utiliza para construir las paredes de la caja, necesitaremos considerar el área lateral de la misma, y si la caja tiene tapa, dicha área será A (x, y, z)= 2(xy + yz + zx).

Por último, teniendo en cuenta que las dimensiones de la caja no pueden ser negativas el problema puede expresarse matemáticamente como Maximizar xyz sujeto a 2 (xy + yz + zx) = A x, y, z ≥ 0.

Puntos de Inflexión

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.

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.

Máximos y Mínimos

Loas máximos y mínimos de una función son los valores más grandes o más pequeños de ésta, ya sea en una región o en todo el dominio.

Los máximos y mínimos en una función f son los valores más grandes (máximos) o más pequeños (mínimos) que toma la función, ya sea en una región (extremos relativos) o en todo su dominio (extremos absolutos).

A continuación tenemos un vídeo acerca de lo que es optimización clásica 

Ilustración de Problemas no lineales

 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

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.

 Programación no lineal

    ¿Qué es?

La programación no lineal forma parte de la investigación de operaciones y también, como la programación lineal, tiene como finalidad proporcionar los elementos para encontrar los puntos óptimos para una función objetivo.

 

En este planteamiento, tanto la función objetivo como las restricciones son no lineales. Se presenta un problema de programación no lineal cuando tanto la función objetivo que debe optimizarse, como las restricciones del problema, o ambas, tienen forma de ecuaciones diferenciales no lineales, es decir, corresponden a ecuaciones cuyas variables tienen un exponente mayor que 1. 

El campo de aplicación de la programación no lineal es muy amplio, sin embargo, hasta la fecha los investigadores de esta rama del conocimiento no han desarrollado un método sistemático que sea práctico para su estudio. 

La programación no lineal también es conocida con el nombre de programación cuadrática, en virtud de que la mayor parte de los problemas que resultan contienen ecuaciones cuadráticas o de segundo grado.

 Muchas veces se presentan casos en que se deben maximizar funciones no lineales que presentan restricciones lineales; esto es posible resolverlo, siempre y cuando se admita la hipótesis de que la utilidad marginal no es constante, en este caso, la función objetivo deja de ser lineal. 

    Características de la programación lineal

Los problemas no lineales se caracterizan por tener relaciones no lineales; es decir, no existe una relación directa y proporcional entre las variables que intervienen. 

Los problemas de programación no lineal, también son llamados curvilíneos, ya que el área que delimita las soluciones factibles en un gráfico se presenta en forma de curva.

 

La función objetivo en la programación no lineal, puede ser cóncavo o convexo. Es cóncavo cuando se trata de maximizar utilidades, contribuciones, etc. Es convexo cuando trata de minimizar recursos, costos, etc. Los problemas que contienen restricciones lineales, se resuelven de una forma más sencilla que los problemas con restricciones no lineales.