Dicotoma

ING. SOFTWARE





SIMULACION E INVESTIGACION DE OPERACIONES


SANCHEZ GONZALEZ LIBIA


INVESTIGACION
ALGORITMOS DE PROGRAMACION NO LINEAL

GRUPO:
6°K

ALUMNO
Leopoldo Aguayo Pereyda


A 17 de Mayo de 2011

ALGORITMOS DE PROGRAMACION NO LINEAL

Programación no lineal (PNL) es el proceso de resolución de un sistema de igualdades ydesigualdades sujetas a un conjunto de restricciones sobre un conjunto de variables reales desconocidas, con un función objetivo a maximizar (o minimizar), cuando alguna de las restricciones o la función objetivo no son lineales.

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 paraprogramació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.

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 conocidosalgoritmos 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   

Las condiciones de Karush-Kuhn-Tucker proporcionan las condiciones necesarias para que una solución sea óptima.   
 
Los tipos de  problemas deprogramació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

Método de búsqueda directa 
Se aplican principalmente a funciones estrictamente unimodales de una variable. Aunque puede parecer trivial el caso

La idea de los métodos de búsqueda directa es identificar el intervalo de incertidumbre que comprenda al punto de solución óptima.

Dos algoritmos estrechamente relacionados son: los métodos de búsqueda dicótomo y de seccióndorada (o áurea). Ambos buscan la maximización de una funció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.  

La diferencia entre los métodos dicótomos y de sección dorada estriba en la forma en que se calculan xx y x2. La tabla siguiente presenta lasfó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 apreciar que cadaiteració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 reusó del valor descartado en la iteración inmediata siguiente. Para definir 0 < a < 1 

 
Comparado con el método dicótomo, el método de la sección dorada converge más rápidamente haciael nivel deseado de exactitud. Adicionalmente, cada iteración en el método de la sección dorada requiere la mitad de los cálculos, en virtud de que recicla siempre un conjunto de los cálculos correspondientes a la iteración inmediata anterior. 

EJEMPLO

El máximo valor de f(x) ocurre en x = 2. La siguiente tabla muestra los cálculos para las iteraciones 1 y 2, usando el método dicótomo y...