Programación no Lineal
La programación lineal ha demostrado ser una herramienta sumamente poderosa, tanto en la modelización de problemas de la vida real como en la teoría matemática de amplia aplicación. Sin embargo, muchos problemas interesantes de optimización son no lineales. El estudio de estos problemas implica una mezcla diversa de álgebra lineal, cálculo multivariado, análisis numérico y técnicas de computación. Entre las áreas especiales importantes se encuentra el diseño de algoritmos de computación (incluidas las técnicas de puntos interiores para programación lineal), la geometría y el análisis de conjuntos convexos y funciones, y el estudio de problemas especialmente estructurados, tales como la programación cuadrática. La optimización no lineal proporciona información fundamental para el análisis matemático, y se usa extensamente en las ciencias aplicadas (en campos tales como el diseño de ingeniería, el análisis de regresión, el control de inventario y en la exploración geofísica).
Conceptos básicos de problemas de programación no lineal.
· Programación no lineal: 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.
· Qué es una función: una función es una cosa que hace algo. Por ejemplo, una máquina de moler café es una función que transforma los granos de café en polvo. La función (objetivo) traza, traduce el dominio de entrada (denominado región factible) en un rango de salida con dos valores finales denominados valores máximo y mínimo.
· El método Simplex es un algoritmo de solución muy utilizado para resolver programas lineales. Es la solución algorítmica inicial para resolver problemas de Programación Lineal (PL). Este es una implementación eficiente para resolver una serie de sistemas de ecuaciones lineales. Mediante el uso de una estrategia ambiciosa mientras se salta desde un vértice factible hacia el próximo vértice adyacente, el algoritmo termina en una solución óptima.
· Un algoritmo es una serie de pasos para cumplir con una tarea determinada.
· Región de Factibilidad Ilimitada: Tal y como se mencionó anteriormente, aprenda que una solución ilimitada requiere una región de factibilidad cerrada ilimitada. La situación inversa de este enunciado podría no ocurrir. Por ejemplo, el siguiente problema de PL tiene una región de factibilidad cerrada ilimitada, sin embargo, la solución es limitada.
· Redundancia Entre las Restricciones: Redundancia significa que algunas de las restricciones no son necesarias dado que existen otras más severas.
3.2 ILUSTRACION GRAFICA DE PROBLEMAS DE PROGRAMACION NO LINEAL
Ilustración grafica de problemas de programación no lineal.
Cuando un problema de programación no lineal tiene solo una o dos variables, se puede representar gráficamente de forma muy parecida a algún ejemplo anterior de programación lineal. 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 optimas de programación lineal y no lineal. Con el fin de hacer hincapié en las diferencias entre programación lineal y no lineal, se usaran algunas variaciones no lineales del problema anterior.
3.3 Tipos de problemas de programación no lineal.
Si la función objetivo f es lineal y el espacio restringido es un politopo, el problema es de Programación lineal y puede resolverse utilizando alguno de los bien conocidos algoritmos de programación lineal.
Si la función objetivo es cóncava (problema de maximización), o convexa (problema de minimización) y el conjunto de restricciones es convexo, entonces se puede utilizar el método general de Optimización convexa.
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.
Las condiciones de Karush-Kuhn-Tucker proporcionan las condiciones necesarias para que una solución sea óptima.
Los problemas de programación no lineal se presentan de muchas formas distintas. Al contrario del método simplex 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.
· Optimización no restringida.
· Optimización linealmente restringida.
· Programacion separable.
· Entre otras
3.4 OPTIMIZACION CLÁSICA
1 Optimización restringida
1.1 Una receta de cocina para resolver problemas de optimizaci´on restringida
Esta receta tiene 7 pasos.
Paso 0 : Escribir el problema en la forma can´onica.
Esto es convertir el problema en uno que se vea as´ı:
max
x2IRk
f(x)
s:a (1)
hi(x) = ci i = 1; : : : ; n
gj(x) · cj j = 1; : : : ;m
Paso 1 : Formar el Lagrangeano agregando ¸i i = 1; : : : ; n y ¸j j = 1; : : : ;m para tener una
funci´on de k + n + m variables:
L = f(x) ¡
Xn
i=1
¸i(hi(x) ¡ ci) ¡
mX
j=1
¸j(gj(x) ¡ cj)
Paso 2 : Expresar las condiciones de primer orden para cada xh h = 1; : : : ; k.
@L
@xh
= @f
@xh
¡
Xn
i=1
¸i
@hi(x)
@xh
¡
mX
j=1
¸j
@gj(x)
@xh
= 0
Paso 3 : Agregar las n + m restricciones.
hi(x) = ci i = 1; : : : ; n
gj(x) · cj j = 1; : : : ;m
Paso 4: Para los m ¸j , agregar las restricciones de no negatividad.
¸j ¸ 0 j = 1; : : : ;m
Paso 5: Agregar las condiciones de holgura complementaria.
¸j(gj ¡ cj) = 0 i = 1; : : : ;m
¸i(hi ¡ ci) = 0 i = 1; : : : ; n (Estas no aportan mucho)
Paso 6: Mezcle todos los ingredientes y resuelva por ensayo y error. Si encuentra una soluci´on, es
una posible soluci´on del problema.
1.2 ¿Por qu´e funciona la receta?
Teorema 1 (Lagrange) En el problema:
max
x2IRn
f(x)
s:a
gi(x) = ci i = 1; : : : ;m
Si:
1. f y gi i = 1; : : : ; n son diferenciables.
2. ¯x 2 C es una soluci´on.
3. La matriz de n £ m
M =
2
6664
@g1(¯x)
@x1
¢ ¢ ¢ @g1(¯x)
@xn ...
. . .
...
@gm(¯x)
@x1
¢ ¢ ¢ @gm(¯x)
@xn
3
7775
tiene rango m (condici´on de calificaci´on de restricciones).
Entonces, existen m escalares ¸i 2 IR, llamados multiplicadores de Lagrange, tales que:
@f(¯x)
@xj
=
mX
i=1
¸i
@gi(¯x)
@xj
8j = 1; : : : ; n
Dem.
La condici´on de calificaci´on de restricciones, garantiza que ¯x tambi´en es soluci´on del siguiente
problema (que no es sino una linearizaci´on, en torno a ¯x del problema original)
max
x2IRn
f(¯x) + rf(¯x)¢(x ¡ ¯x)
s:a
rgi(x)¢(x ¡ ¯x) = ci i = 1; : : : ;m
Intuitivamente, si ¯x es una soluci´on del problema, entonces cualquier direcci´on de desplazamiento
z 2 IRn tal que no tiene efectos de primer orden en las restricciones, tampoco puede tenerlos en
la funci´on objetivo. Es decir si ¯x es soluci´on, no debe ser posible aumentar el valor de la funci´on
objetivo sin violar alguna restricci´on.
Por lo tanto, cualquier direcci´on z tal que:
rgi(¯x)¢z = 0 8i = 1; : : : ;m
implica que:
rf(¯x)¢z = 0
Por lo tanto la matriz de (m + 1) £ n:
E =
2
6666664
@f(¯x)
@x1
¢ ¢ ¢ @f(¯x)
@xn
@g1(¯x)
@x1
¢ ¢ ¢ @g1(¯x)
@xn ...
. . .
...
@gm(¯x)
@x1
¢ ¢ ¢ @gm(¯x)
@xn
3
7777775
satisface que:
z=E¢z = 0 , rgj ¢z = 0
luego:
M¢z = 0
Como esto s´olo es posible si E y M tienen el mismo rango, entonces agregar la fila rf(¯x)0 no tuvo
efectos en el rango de la matriz. En conclusion rf(¯x) es una combinaci´on lineal de los rgi(¯x) y,
por lo tanto, existen m escalares tales que:
@f(¯x)
@xj
=
mX
i=1
¸i
@gi(¯x)
@xj
8j = 1; : : : ; n
2
N´otese que esta es una condici´on necesaria pero no suficiente, es decir, que existan los multiplicadores
de Lagrange no implica que el punto sea soluci´on del problema, sino, solamente, que es una
posible soluci´on del mismo.
Definici´on 1 (Hiperplano) Sean z 2 IRn y ¯ 2 IR, se define el hiperplano Hz;¯ como el conjunto
de los x 2 IRn tales que:
z¢x = ¯
Este hiperplano divide al espacio en dos mitades, la mitad superior Hs
z;¯ , compuesta por todos los
puntos xs tales que
z¢xs > ¯
y la mitad inferior Hi
z ;¯ , compuesta por todos los puntos xi tales que:
z¢xi < ¯
Teorema 2 (Hiperplano separador) Sea el conjunto convexo y cerrado B ½ IRn y un punto
x 2 IRn 2= B, entonces, existe un hiperplano Hz;beta tal que, si B ½ Hs
z;¯ entonces x 2 Hi
z;beta y
viceversa.
Dem.
Sea y el punto de B que es m´as cercano, en el sentido de la norma euclidiana, a x. Definamos
z = x ¡ y y ¯0 = z¢y, entonces, es f´acil ver que z¢x > ¯0. En efecto:
z¢x ¡ ¯ = (x ¡ y)¢x ¡ (x ¡ y)¢y = (x ¡ y)¢(x ¡ y) = k(x ¡ y)k2 > 0
Adem´as para cualquier w 2 B el ´angulo entre (w ¡ y) y (x ¡ y) no puede ser agudo (si lo fuera,
entonces y no ser´ıa el punto de B m´as cercano a x). Luego,
(x ¡ y)¢(w ¡ y) < 0
es decir:
(x ¡ y)¢w ¡ (x ¡ y)¢y < 0
o, lo que es lo mismo,
z¢w < ¯0
Sea ahora ¯ = ¯0 +" con " > 0 suficientemente peque˜no para que z¢x > ¯. Entonces, el hiperplano
Hz;¯ es tal que B 2 Hi
z;¯ y x 2 Hs
z;¯ . 2
Teorema 3 (Kuhn–Tucker) Supongamos que ¯x 2 C es una soluci´on del problema:
max
x2IRn
f(x)
s:a
gi(x) · ci i = 1; : : : ;m
si se satisface la condici´on de calificaci´on de restricciones, entonces existen m multiplicadores de
Lagrange ¸i 2 IR+ tales que:
1. Para todo j = 1; : : : ; n:
@f(¯x)
@xj
=
mX
i=1
¸i
@gi(¯x)
@xj
2. Para todo i = 1; : : : ;m:
¸i(gi(¯x) ¡ ci) = 0
Dem.
Intuitivamente, demostraremos que, para toda direcci´on de desplazamiento z 2 IRn tal que rgi(¯x)¢z ·
0 i = 1; : : : ;m (es decir, que satisface las restricciones) entonces rf(¯x)¢z · 0, es decir, no es una
direcci´on de crecimiento de f(x). Es decir, si hay una direcci´on en la cual la funci´on objetivo puede
aumentar, entonces en dicha direcci´on debe violarse, al menos, una restricci´on.
El teorema establece que, para que ¯x sea una soluci´on del problema, rf(¯x) debe estar en el cono
definido por las restricciones activas:
¡ =
8<
:y 2 IRn=y =
X
j
¸jrgj(¯x) 8¸j ¸ 0
9=
;
Supongamos que esto no es as´ı, es decir, rf(x) 2= ¡, entonces, por el teorema del hiperplano
separador, existen un vector z 2 IRn y un n´umero ¯ 2 IR tal que rf(x)¢z ¸ ¯ y y¢z < ¯ 8y 2 ¡.
Como 0 2 ¡, esto implica ¯ > 0, por lo tanto, rf(¯x)¢z ¸ 0.
Adem´as, 8y 2 ¡; µ 2 IR+, µy 2 ¡, por la definici´on de cono. De donde se obtiene que:
µy¢z < ¯ 8µ 2 IR+
En particular, sea µ =
³
1 + ¯
y¢z
´
entonces:
µ
1 + ¯
y¢z
¶
y¢z = y¢z + ¯ < ¯
es decir, y¢z < 0 y, por lo tanto, rgi(¯x)¢z · 0 para todo i y rf(¯x)¢z ¸ 0 (es decir, existe
una direcci´on de crecimiento factible que permite incrementar la funci´on) lo que contradice a la
linearizaci´on del problema que se desprende de la condici´on de calificaci´on de restricciones
3.4.1 Puntos de inflexión
Si f y f' son derivables en a, a es un:
Punto de inflexión
Si f'' = 0
y f''' ≠ 0
Cálculo de los puntos de inflexión
Para hallar los puntos de inflexión, seguiremos los siguientes pasos:
1. Hallamos la derivada segunda y calculamos sus raíces.
2. Realizamos la derivada tercera, y calculamos el signo que toman en ella los ceros de derivada segunda y si:
f'''(x) ≠ 0 Tenemos un punto de inflexión.
3. Calculamos la imagen (en la función) del punto de inflexión.
Ejemplo
Hallar los puntos de inflexión de:
f(x) = x3 − 3x + 2
f''(x) = 6x 6x = 0 x = 0.
f'''(x) = 6 Será un punto de inflexión.
f(0) = (0)3 − 3(0) + 2 = 2
Punto de inflexión: (0, 2)
Si ya hemos estudiado la concavidad y convexidad de una función habrá:
Puntos de inflexión en los puntos en que ésta pasa de cóncava a convexa o vicecersa.
Ejemplo
Calcular los puntos de inflexión de la función:
Tenemos un punto de inflexión en x = 0, ya que la función pasa de convexa a concava.
En este vídeo se estudia la concavidad y convexidad, y los puntos de inflexión de una función.
No hay comentarios:
Publicar un comentario