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.
3.2 ILUSTRACIÓN GRAFICA 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.
Se verán unos cuantos ejemplos, ya que una representación gráfica de ese
tipo proporciona una visión global de las propiedades de las soluciones óptimas
de programación lineal y no lineal.
La figura 13.5 muestra lo que ocurre con este problema si los únicos
cambios que se hacen al modelo.
La segunda y tercera restricciones funcionales se sustituyen por la
restricción no lineal 9x { + 5x2 <.
La solución óptima sigue siendo (a^ , x2)
= (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 = 3xx + x2).
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 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.
Se introducirán las clases más importantes y
después se describirá cómo se pueden resolver algunos de estos problemas.
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.
Los tipos de problemas de programación no lineal son:
1.
Optimización no restringida.
2.
Optimización linealmente restringida.
3.
Programación cuadrática
4.
Programación convexa.
5.
Programación separable.
6.
Programación no convexa.
7.
Programación geométrica.
8.
Programación fraccional.
9.
Problema de complementariedad.
3.4 OPTIMIZACIÓN CLÁSICA.
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.
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.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 modelizarlo
matemáticamente, es decir tendremos que expresarlo en términos matemáticos.
El primer paso para modelizar 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 , , .
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 ( ) =
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á ( ) = 2( + + )
Por último, teniendo en cuenta que las dimensiones de la caja no pueden
ser negativas el problema puede expresarse matemáticamente como Maximizar sujeto a 2 ( + + ) = ≥ 0
3.4.1 PUNTOS DE INFLEXIÓN.
Un punto de
inflexión es un punto donde
los valores de x de una función continua pasa de un tipo de concavidad a otra. La curva
"atraviesa" la tangente.
Matemáticamente la derivada segunda de la función f
en el punto de inflexión es cero, o no existe.
Cálculo
de los puntos de inflexión en funciones reales derivables de variable real
En las funciones derivables reales de una variable
real, para hallar estos puntos de inflexión, basta con igualar la segunda derivada de la función a cero y despejar.
Los puntos obtenidos deberán ser sustituidos en la derivada tercera o sucesiva
hasta que nos dé un valor diferente de cero. Cuando esto suceda, si la derivada
para la que es distinto de cero es impar, se trata de un punto de inflexión;
pero, si se trata de derivada par, no lo es.
Más concretamente:
1.
Se halla la primera derivada de
2.
Se halla la segunda derivada de
3.
Se halla la tercera derivada de
4.
Se iguala la segunda derivada a 0:
5.
Se despeja la variable independiente y se obtienen
todos los valores posibles de la misma:
.
6.
Se halla la imagen de cada
sustituyendo
la variable dependiente en la función.
7.
Ahora, en la tercera derivada, se sustituye cada
:
1.
Si
, se
tiene un punto de inflexión en
.
2.
Si
, debemos
sustituir
en las
sucesivas derivadas hasta sea distinto de cero. Cuando se halle la derivada
para la que
no sea
nulo, hay que ver qué derivada es:
1.
Si la derivada es impar, se trata de un punto de inflexión.
2.
Si la derivada es par, no se trata de un punto de
inflexión.
La ecuación
no tiene
puntos de inflexión, porque la derivada segunda es siempre mayor o igual a
cero, por tanto no hay cambio de
concavidad dado que es no negativa en todo su dominio. Sin embargo en
la
derivada segunda se anula y la primera derivada no nula en
es la
derivada cuarta, que es par. Obsérvese que
tampoco
presenta un extremo en
.
Ejemplo
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 más 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.
Así pues, si (x0, ë0) es un punto
minimax, x0 es una solución óptima del problema original.
No hay comentarios:
Publicar un comentario