Programación no Lineal

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.

Ventajas

En algunas ocasiones la distribución óptima del presupuesto excluye cualquiera de los bienes considerados en el presupuesto general; esta situación se refleja en cualquiera de las restricciones del modelo.
La programación no lineal aporta mayor información que la contenida en el análisis marginal. No sólo define el objetivo, sino que también señala la orientación específica para lograr el objetivo.

Características

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. Es convexo cuando trata de minimizar recursos, costos, entre otros. Los problemas que contienen restricciones lineales, se resuelven de una forma más sencilla que los problemas con restricciones no lineales.

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 necesaria 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 necuaciones 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 solución analítica simultánea. ¿Qué se puede hacer en ese caso? Las secciones 13.4 y 13.5 describen 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 algoritmos 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 necesaria (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 suficiente para que x= 0 sea óptima.

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

Optimizaciòn Linealmente Restringida

Los problemas de optimización literalmente restringida se caracterizan por restricciones que se ajustan por completo a la programación lineal, de manera que todas las funciones de restricció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 extensió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 especiales, están todos los tipos anteriores cuando /(x) es cóncava. Las suposiciones son

f(x) es cóncava.
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 suposició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 ejemplo, si f(x) es una función separable, se puede expresar como

son cada tina funciones de una sola variable 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 cualquier 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 satisfacen 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 locales, 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 presentará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 programación convexa no se pueden aplicar directamente a estos problemas de programació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 ¿ en cada función son estrictamente positivos, es decir, las funciones son polinomios 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 programación posinomial, al igual que para problemas de programación geométrica de otros tipos.

Programación Fracccional

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 razó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 estándar de alguna medida de desempeño para una cartera de inversiones (rendimiento/riesgo). 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 programación fraccional es transformarlo en un problema equivalente de algún tipo estándar que disponga 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 suponga 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 convexa.

Programación Cuadrática

La programación cuadrática (QP) es el nombre que se le da a un procedimiento que minimiza una función cuadrática de n variables sujeta a m restricciones lineales de igualdad o desigualdad. Un programa cuadrático es la forma más simple de problema no lineal con restricciones de desigualdad. La importancia de la programación cuadrática es debida a que un gran número de problemas aparecen de forma natural como cuadráticos (optimización por mínimos cuadrados, con restricciones lineales), pero además es importante porque aparece como un subproblema frecuentemente para resolver problemas no lineales más complicados. Las técnicas propuestas para solucionar los problemas cuadráticos tienen mucha similitud con la programación lineal. Específicamente cada desigualdad debe ser satisfecha como igualdad. El problema se reduce entonces a una búsqueda de vértices exactamente igual que se hacía en programación lineal.

Donde c es un vector de coeficientes constantes; A es una matriz (m x n) y se asume, en general que Q es una matriz simétrica. Dado que las restricciones son lineales y presumiblemente independientes la cualificación de las restricciones se satisface siempre, así pues, las condiciones de Karush-KuhnTucker son también condiciones suficientes para obtener un extremo, que será además un mínimo global si Q es definida positiva. Si Q no es definida positiva el problema podría no estar acotado o llevar a mínimos locales.

La Programación Cuadrática juega un papel muy relevante en la teoría de optimización lineal y no lineal pues guarda una relación muy estrecha con la Programación Lineal y es un paso intermedio esencial para resolver eﬁcazmente problemas generales de Programación No Lineal.

Para qué se usa

Existen diferentes tipos de problemas de programación cuadrática, los cuales se pueden clasificar en:

-Problemas cuadráticos de minimización sin restricciones, requieren minimizar la función cuadrática f (x) sobre el espacio completo.
-Problemas cuadráticos de minimización sujetos a restricciones de igualdad, requieren minimizar la función objetivo f (x) sujeta a restricciones lineales de igualdad Ax = b.
-Problemas cuadráticos de minimización sujetos a restricciones lineales de desigualdad. Requieren minimizar la función objetivo f (x) sujeta a restricciones lineales de desigualdad Ax = b, también puede contener restricciones de igualdad.
-Problemas de optimización de redes cuadráticas. Son problemas cuadráticos en los que las restricciones son restricciones de baja conservación sobre una red pura generalizada.
-Problemas cuadráticos convexos. Son cualquiera de los mencionados arriba, en el cual la función objetivo a ser minimizada, f (x) es convexa.
-Problemas cuadráticos no convexos. Son cualquiera de los mencionados arriba, en el cual la función objetivo a ser minimizada, f (x) es no convexa.
-Problemas de complementariedad lineal. Son problemas especiales con un sistema de ecuaciones en variables no negativas, en el cual las variables están formadas en varios pares llamados pares complementarios.

Históricamente, las funciones cuadráticas fueron prominentes porque proveían modelos locales simples para funciones no lineales generales. Una función cuadrática, es la función no lineal más simple, y cuando es usada como una aproximación para una función no lineal general, esta puede capturar la información importante de la curvatura, lo que una aproximación lineal no puede. El uso de aproximaciones cuadráticas para resolver problemas con funciones no lineales generales se remonta mucho tiempo atrás. Entre los métodos más destacados, tenemos al método de Newton y el método de gradiente conjugado. Para la programación cuadrática se pueden encontrar mínimos locales, mínimos globales, puntos estacionarios o de KKT, (son los que satisfacen las condiciones de KKT del problema).

Problemas Resueltos

Para desarrollar el problema hacemos:

(x ₁ - 2)² + (x ₂ - 2)² = a²

Y tenemos una circunferencia de radio a y centro en (2, 2). Por lo tanto, para obtener el mínimo de z necesitamos calcular el mínimo valor de a que cumple las restricciones. Gráficamente tenemos la situación de la figura y en ella vemos que el valor mínimo de a que verifica las restricciones es el de la perpendicular desde el punto (2, 2) a la recta dada por:

pues en dicho punto se tiene:

y de ese modo se cumplen todas las restricciones.

Para obtener la perpendicular hacemos:

y puesto que pasa por el punto (2, 2):

con lo que tendremos:

Ejemplo 2: Un joven ingeniero de una compañía ha sintetizado un nuevo fertilizante hecho a partir de dos materias primas. Al combinar cantidades de las materias primas básicas x1 y x2, la cantidad de fertilizante que se obtiene viene dada por Q = 4x1 + 2x2 − 0:5x21 − 0:25x22.

Se requieren 480 euros por unidad de materia prima 1 y 300 euros por cada unidad de materia prima 2 que se empleen en la fabricación del fertilizante (en estas cantidades se incluyen los costos de las materias primas y los costos de producción). Si la compañía dispone de 24000 euros para la producción de materias primas, plantear el problema para determinar la cantidad de materia prima de forma que se maximice la cantidad de fertilizante.

Las variables de decisión del problema son:

x1 : cantidad de materia prima 1

x2 : cantidad de materia prima 2

El objetivo es maximizar la cantidad de fertilizante, Q(x1; x2) = 4x1+2x2−0:5x21−0:25x22

Restricciones del problema:

- El coste no puede exceder el presupuesto que la empresa tiene asignado para el fertilizante, 480x1 + 300x2 ≤ 24000

- No negatividad de las cantidades: x1 ≥ 0; x2 ≥ 0 Por tanto

Max Q(x1; x2) = 4x1 + 2x2 − 0:5x21 − 0:25x2/2

480x1 + 300x2 ≤ 24000

X1 ≥ 0; x2 ≥ 0

Condiciones Karush Kuhn Tucker (KKT)

Las condiciones necesarias que deben satisfacer los óptimos de problemas de optimización no lineal con restricciones de desigualdad fueron publicadas por primera vez (1939) en la tesis de Maestría de William Karush (1917-1997) (en aquél entonces estudiante de matemáticas de la Universidad de Chicago) , aunque fueron renombradas tras un artículo en una conferencia de Harold W. Kuhn y Albert W. Tucker en 1951. Las condiciones de Karush-Kuhn-Tucker (KKT) son una generalización del método de los multiplicadores de Lagrange para restricciones de desigualdad.

Problema General de Optimizaciòn

Consideremos el siguiente problema general:

$\text{min }\; f(x)$

$\text{sujeto a }\$

$\ g_i(x) \le 0\$ , $\ i = 1,\ldots,m$

$\ h_j(x) = 0\$ , $\ j = 1,\ldots,l$

donde $f(x)$ es la función objetivo a minimizar, $g_{i}(x)$ son las restricciones de desigualdad y $h_{j}(x)$ son las restricciones de igualdad, con $m$ y $l$ el número de restricciones de desigualdad e igualdad, respectivamente.

Las condiciones necesarias para problemas con restricciones de desigualdad fueron publicadas por primera vez en la tesis de máster de W. Karush, aunque fueron renombradas tras un artículo en una conferencia de Harold W. Kuhn y Albert W. Tucker.

Condiciones Generales de Primer Orden

Supongamos que la función objetivo, por ejemplo, a minimizar, es $f : \mathbb{R}^n \rightarrow \mathbb{R}$ y las funciones de restricción son $g_i : \,\!\mathbb{R}^n \rightarrow \mathbb{R}$ y $h_j : \,\!\mathbb{R}^n \rightarrow \mathbb{R}$ . Además, supongamos que son continuamente diferenciales en el punto $x^*$ . Si $x^*$ es un mínimo local, entonces existe constantes $\lambda \ge 0$ , $\mu_i \ge 0\ (i = 1,\ldots,m)$ y $\nu_j\ (j = 1,...,l)$ tales que

$\lambda + \sum_{i=1}^m \mu_i + \sum_{j=1}^l |\nu_j| > 0,$

$\lambda\nabla f(x^*) + \sum_{i=1}^m \mu_i \nabla g_i(x^*) + \sum_{j=1}^l \nu_j \nabla h_j(x^*) = 0,$

$\mu_i g_i (x^*) = 0\; \mbox{para todo}\; i = 1,\ldots,m.$

Condiciones de Regularidad o Clasificación de las Restricciones

En la condición necesaria anterior, el multiplicador dual $\lambda$ puede ser igual a cero. Este caso se denomina degenerado o anormal. La condición necesaria no tiene en cuenta las propiedades de la función sino la geometría de las restricciones.Existen una serie de condiciones de regularidad que aseguran que la solución no es degenerada (es decir $\lambda \ne 0$ ).

Estas incluyen:Cualificación de la restricción de independencia lineal (CRIL): los gradientes de las restricciones activas de desigualdad y los gradientes de las restricciones de igualdad son linealmente independientes en $x^*$ .
Cualificación de la restricción de Mangasarian-Fromowitz (CRMF): los gradientes de las restricciones activas de desigualdad y los gradientes de las restricciones de igualdad son linealmente independientes positivos en $x^*$ .
Cualificación de la restricción de rango constante (CRRC): para cada subconjunto de las restricciones activas de desigualdad y los gradientes de las restricciones de igualdad, el rango en el entorno de $x^*$ es constante.
Cualificación de la restricción de dependencia lineal constante positiva (DLCP): para cada subconjunto de restricciones activas de desigualdad y de gradientes de las restricciones de igualdad, si es linealmente dependiente positivo en $x^*$ entonces es linealmente dependiente positivo en el entorno de $x^*$ . ( $\{v_1,\ldots,v_n\}$ es linealmente dependiente positivo si existe $a_1\geq 0,\ldots,a_n\geq 0$ distintos de cero tal que $a_1v_1+\cdots+a_nv_n=0$ )
Condición de Slater: para un problema únicamente con restricciones de desigualdad, existe un punto $x$ tal que $g_i(x) < 0$ para todo $i = 1,\ldots,m$

Condiciones Suficientes

Puede verse que CRIL=>CRMF=>DLCP, CRIL=>CRRC=>DLCP, aunque CRMF no es equivalente a CRRC. En la práctica, se prefiere cualificación de restricciones más débiles ya que proporcionan condiciones de optimalidad más fuertes.

Sea la función objetivo $f: \mathbb{R}^n \rightarrow \mathbb{R}$ y las funciones de restricción $g_i : \mathbb{R}^n \rightarrow \mathbb{R}$ sean funciones convexas y $h_j : \mathbb{R}^n \rightarrow \mathbb{R}$ sean las funciones de afinidad, y séa un punto $x^*$ . si existen constantes $\mu_i \ge 0\ (i = 1,\ldots,m)$ y $\nu_j\ (j = 1,\ldots,l)$ tales que

$\nabla f(x^*) + \sum_{i=1}^m \mu_i \nabla g_i(x^*) + \sum_{j=1}^l \nu_j \nabla h_j(x^*) = 0$ $\mu_i g_i (x^*) = 0\; \mbox{para todo}\; i = 1,\ldots,m,$

entonces el punto $x^*$ es un mínimo global.

Ejemplo Resuelto

El problema anterior se puede representar gráficamente a través del software Geogebra de modo de encontrar su solución óptima (x1=2 y x2=1) en la coordenada “C” con valor óptimo V(P)=2. El conjunto de factibilidad corresponde al área achurada y se puede observar que en la solución óptima se encuentran activas las restricciones 1 y 3 (el resto de las restricciones por cierto se cumple pero no en igualdad).

Por supuesto la resolución gráfica es sólo referencial y se ha utilizado en este caso para corroborar los resultados a obtener en la aplicación del teorema. En este contexto el problema en su forma estándar es simplemente:

Notar que sólo fue necesario cambiar la forma de las restricciones de no negatividad (esto se puede hacer multiplicando por -1 cada una de ellas). Cabe destacar que en este caso en particular el problema no considera restricciones de igualdad. Luego las condiciones necesarias de primer orden de Karush Kuhn Tucker (KKT) están dadas por:

si en las condiciones generales anteriores consideramos el problema no restringido (asumiendo que todas las restricciones son inactivas) la solución óptima por simple inspección es x1=3 y x2=2, que corresponde a la coordenada “E” de la gráfica anterior y que se puede observar no es a una solución factible para el problema. Luego la circunferencia de menor radio que intersecta el conjunto de factibilidad es precisamente aquella que pasa por la coordenada “C” donde las restricciones 1 y 3 se cumplen en igualdad, razón por la cual las cuales activaremos de forma simultanea:

Al calcular los gradientes respectivos se obtiene:

Lo cual da origen al siguiente sistema de ecuaciones:

Reemplazando x1=2 y x2=1 podemos despejar los valores de los multiplicadores los cuales cumplen con las condiciones de no negatividad:

Adicionalmente se puede verificar que x1=2 y x2=1 satisface las restricciones omitidas (2,4 y 5) por lo cual se puede afirmar que dicha solución cumple las condiciones necesarias de primer orden de Karush Kuhn Tucker (KKT).

martes, 21 de enero de 2014

Programación no Lineal

Ejemplo Resuelto