3.3 TIPOS DE PROBLEMAS DE PROGRAMACION NO LINEAL

3.3 Tipos De Problemas De Programacion No Lineal 

Los problemas de programación no lineal se presentan de muchas formas distintas. Al con­trario del método símplex para programación lineal, no se dispone de un algoritmo que re­suelva 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 introduci­rán las clases más importantes y después se describirá cómo se pueden resolver algunos de es­tos 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. 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 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.
  

ALGORITMOS SIN RESTRICCIÓN

En esta sección se presentarán dos algoritmos para el problema no restringido: el algoritmo de búsqueda directa y el algoritmo de gradiente.  
   
 Método de búsqueda directa  
Los métodos de búsqueda directa se aplican principalmente a funciones estrictamente unimo- dales de una variable. Aunque puede parecer trivial el caso, la sección 21.1.2 muestra que la optimización de funciones de una variable juega un papel clave en el desarrollo de los algorit­mos de varias variables, más generales.  
La idea de los métodos de búsqueda directa es identificar el intervalo de incertidum- bre que comprenda al punto de solución óptima. El procedimiento localiza el óptimo estre­chando en forma progresiva el intervalo de incertidumbre hasta cualquier grado de exactitud que se desee.  
En esta sección se presentan dos algoritmos estrechamente relacionados: los métodos de búsqueda dicótomo y de sección dorada (o áurea). Ambos buscan la maximización de una fun­ción unimodal/(x) en el intervalo a ^ x < b, que se sabe que incluye el punto óptimo x*. Los dos métodos comienzan con /0 = (a, b) que representa el intervalo inicial de incertidumbre.  
Paso general i. Sea /, _ , = (xD xR) el intervalo actual de incertidumbre (en la iteración 0, xL = a y xR = b). A continuación se definen xx y x2 tales que  
xj^ ^ ^ x2 ^ xr  
El siguiente intervalo de incertidumbre, /z, se define como sigue:  
  1. Si f(xx) > /(x2), entonces xL < x* < x2. Se definen xR = x2 e /, = (xL, x2) (véase la figura 21.2[a]).
  2. Si f(xx) < f(x2\ entonces xx < x* < xR. Se definen xL = xx e I¡ = (xh xR) (véase la figura 21.1 [b]). .
  3. Si f{x\) = /(jc2), entonces xx < x* < x2. Se definen xL = x2 e /, = (xb x2).
  
La manera en que se determinan xx y x2 garantiza que /, < /,_ p como se demostrará en breve. El algoritmo termina en la iteración ksilk< A, donde A es un grado de exactitud defi­nido por el usuario.                                                                                                                                                                                        *  
La diferencia entre los métodos dicótomo y de sección dorada estriba en la forma en que se calculan xx y x2. La tabla siguiente presenta las fórmulas.  

En el método dicótomo los valores jc, y x2 se encuentran simétricos respecto del punto medio del actual intervalo de incertidumbre. Esto significa que 
La aplicación repetida del algoritmo garantiza que la longitud del intervalo de incertidumbre se acercará al nivel de exactitud deseado, A. 
En el método de la sección dorada la idea es de mayor involucramiento. Se puede apre­ciar que cada iteración del método dicótomo requiere calcular los dos valores/(jc,) y f(x2), Pe” ro termina por descartar alguno de ellos. Lo que propone el método de la sección dorada es ahorrar cálculos mediante el reuso del valor descartado en la iteración inmediata siguiente. Para definir 0 < a < 1 

Cuando el intervalo de incertidumbre /, en la iteración i es igual a (jc¿, x2) o a (xu xR). Conside­re el caso en que /, = (jcl, x2), lo cual significa que xx está incluido en /,. En la iteración /+1, seleccione x2 igual a jc, de la iteración /, lo cual lleva a la siguiente ecuación: 


VÍDEO (TIPOS DE PROBLEMAS DE PROGRAMACIÓN NO LINEAL)




Comentarios

Publicar un comentario

Entradas populares de este blog

3.4.1 PUNTOS DE INFLEXION

Imagen
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
Leer más

3.2 ILUSTRACION GRAFICA DE PROBLEMAS DE PROGRAMACION NO LINEAL

Imagen
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, 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 2  < 216. Compare las figuras 13.5 y 3.3. La solu­ción óptima sigue siendo ( a ^ ,  x 2 ) = (2,6). Todavía se encuentra sobre la frontera de la región factible, pero  no  es una solución facti
Leer más

3.4.2 MAXIMOS Y MINIMOS

Imagen
Costo Mínimo Es un algoritmo desarrollado con el objetivo de resolver problemas de transporte o distribución, arrojando mejores resultados que métodos como el de la esquina noroeste , dado que se enfoca en las rutas que presentan menores costos.   El diagrama de flujo de este algoritmo es mucho más sencillo que los anteriores dado que se trata simplemente de la asignación de la mayor cantidad de unidades posibles (sujeta a las restricciones de oferta y/o demanda) a la celda menos costosa de toda la matriz hasta finalizar el método. Procedimiento: 1.- Se busca la celda con menor costo y después se ajusta la oferta y la demanda afectada. 2.- Se revisa si la demanda fue satisfecha. De ser así se elimina esa columna. 3.- Si hay más de un renglón o columna se repite el paso 1. Ejemplo: Resuelve la tabla por el método de costo mínimo: EJEMPLO ( MÉTODO DE COSTO MÍNIMO )
Leer más