Informe sobre maximos y minimos programacion geometrica, dinamica y separable

REPUBLICA BOLIVARIANA DE VENEZUELA MINISTERIO DE EDUCACION SUPERIOR INSTITUTO UNIVERSITARIO POLITECNICO “SANTIAGO MARINO”. AMPLIACION: MARACAIBO. ESCUELA: SISTEMAS CATEDRA: OPTIMIZACION DE SISTEMAS DE INFORMACION INFORME REALIZADO POR: BR. BARBARA GONZALEZ C. I. :18874087 SECCION 47 A NOCHE. MARACAIBO, NOVIEMBRE DEL 2009 Maximos y minimos en una funcion. Una funcion f(x) tiene en x = a un maximo cuando a su izquierda la funcion es creciente y a su derecha decreciente.

Y tiene un minimo, si a su izquierda la funcion es decreciente y a su derecha creciente. Minimo (fuerte): Un punto extremo X0 de una funcion f(X0) define un minimo de la funcion si f(X0+h) > f(X0), donde X0 es cualquier punto de la funcion y h en valor absoluto es suficientemente pequena. Maximo (fuerte): Un punto extremo X0 de una funcion f(X0) define un maximo de la funcion si f(X0+h) < f(X0), donde X0 es cualquier punto de la funcion y h en valor absoluto es suficientemente pequena.

Una funcion puede contener varios maximos y minimos, identificados por los puntos extremos de la funcion. En la figura 1 se puede observar esto, los puntos x1, x3 y x6 son maximos, de la figura notamos que f(x6) es el mayor que f(x1) y f(x3),

Lo sentimos, pero las muestras de ensayos completos están disponibles solo para usuarios registrados

Elija un plan de membresía
a este punto se le conoce como maximo global de la funcion y a los restantes como maximos locales. Lo mismo se puede ver para los minimos, en los que tambien existe un minimo global f(x2) y un minimo local f(x4). Como es de logico, solo puede existir un solo global y posiblemente varios locales.

Representacion de maximos y minimos en una funcion con una sola variable Una condicion necesaria pero no suficiente para que X0 sea un punto extremo, es que para una funcion con mas de una variable, el gradiente N f(X0) = 0. Si es cierto esto entonces X0 sera conocido como punto estacionario. Una condicion suficiente para que un punto estacionario sea extremo es que La matriz Hessiana H obtenida en X0 del sistema de ecuaciones sea positiva cuando X0 es un punto extremo de minimo. Y negativa cuando X0 es un punto extremo de Maximo.

Un maximo debil implica un numero finito de maximos alternativos (ver figura 1) y se define como X0 es un maximo debil, si f(X0 + h) 0, es un problema que no se puede resolver mediante Programacion Geometrica. Finalmente se resuelven los sistemas de ecuaciones simultaneas planteadas y se obtiene la solucion del problema. Ejemplo: 1. Encontrar la cantidad economica de pedido de un producto, es decir, se debe decidir que cantidad del articulo conviene almacenar periodicamente; los costos totales asociados al producto y su almacenamiento se pueden expresar CT = CCI + CHP + VC donde

Donde: La funcion objetivo tiene la siguiente formula general: De tal modo que al resolver el anterior sistema de ecuaciones simultaneas llegamos a que 1 = 2 y la variable Q* debe ser tal que haga que los dos terminos de la funcion objetivo sean iguales: Programacion Cuadratica. un problema de programacion no lineal cuya funcion objetivo es la suma de terminos de la forma el grado del termino Un problema de programacion no lineal, cuyas restricciones son lineales y cuya funcion objetivo es la suma de terminos de la forma es un problema de programacion cuadratica.

Vamos a ilustrar de manera general el metodo de WOLFE para resolver problemas de programacion cuadratica: Se define un problema de programacion cuadratica como: Con sus restricciones: Donde (Vector en con componentes continuas), C es un vector de precios con n componentes, Q es una matriz de nxn , simetrica y positiva definida, es decir , para toda , excepto X = 0, b es el vector de recursos con m componentes, A es una matriz de m*ncoeficientes tecnologicos y 0 es un vector con n ceros. El problema de optimizacion anterior tiene restricciones lineales, si Q es una matriz nula se convierte en un problema de programacion lineal.

Como Q es positiva definida , implica que W es una funcion estrictamente convexa y por lo tanto el minimo si existe es global; si Q es negativa definida, W es estrictamente concava y si el maximo existe es global. A continuacion se escribe el problema en notacion algebraica, se le aplican los multiplicadores de Lagrange, se verifican las condiciones necesarias y suficientes de Karush – Kuhn- Tucker que deben existir en un optimo global. El metodo de Wolfe sigue con la reescritura del problema original como un problema de programacion lineal con holguras complementarias; este ultimo problema es equivalente al problema original.

El problema de programacion lineal a resolver sera de 2(m + n)n variables, m + n restricciones lineales y m + n restricciones de holgura complementaria. Ejemplo: Resolver el siguiente problema de programacion cuadratica por el metodo de Wolfe : Aplicando los multiplicadores de Lagrange tenemos: Las primeras derivadas parciales son: El problema de programacion lineal equivalente al original de acuerdo al metodo Wolfe es: Con las siguientes restricciones de holgura complementaria: Utilizando el metodo Simplex se tiene que la solucion basica inicial es:

En la primera iteracion entra y sale X1 ( es de aclarar que aunque el Simplex escoge 1 y 2 para entrar a la base antes que lo haga X2, 1 y 2 no son aceptables, ya que Y1 y Y2 son positivos). El punto extremo luego de recalcular es: En la tercera iteracion no pueden entrar a la base 1 y 2 y Y1 y Y2 son positivas; el Simplex toma como siguiente candidato a 1 y de salida Y1 ; el punto extremo despues de iterar es: En la ultima iteracion (V1 = 0 y V2 = 0) debe entrar X1 pero no puede porque 1 es positivo; el siguiente elemento a entrar a la base es 1 el cual reemplaza a V2 Luego De recalcular ( pivotear) el punto extremo es:

La solucion anterior corresponde al optimo: Programacion Separable. Una funcion es separable si se puede expresar como la suma de n funciones de una sola variable , es decir, Un caso especial de programacion separable ocurre cuando las funciones son convexas , resultando asi un espacio convexo de solucion; ademas la funcion es convexa en caso de minimizacion y concava en caso de maximizacion. No existe un algoritmo unico para solucionar problemas de programacion convexa; en general los algoritmos conocidos se pueden clasificar asi: . Algoritmos de gradiente, en estos casos se modifica de alguna manera el procedimiento de busqueda del gradiente para evitar que la trayectoria de busqueda penetre la frontera de restriccion. 2. Algoritmos secuenciales no restringidos, incluye los metodos de funcion de penalizacion y de funcion barrera; estos algoritmos convierten el problema de optimizacion restringida original en una sucesion de problemas de optimizacion no restringida, cuyas soluciones optimas convergen a la solucion optima del problema original. . Algoritmos de Aproximacion Secuencial, incluye metodos de aproximacion lineal y aproximacion cuadratica; estos algoritmos sustituyen la funcion objetivo no lineal por una sucesion de aproximaciones lineales o cuadraticas. Para problemas de optimizacion linealmente restringidos, estas aproximaciones permiten la aplicacion repetida de los algoritmos de programacion lineal o cuadratica. A continuacion resolvemos un problema de programacion separable aplicando el metodo de la base restringida.

El metodo de aproximacion nos sugiere que las variables separables son: 1 0 0 0 2 1 1 2 3 2 16 8 4 3 81 18 Luego: Entonces el problema original por aproximacion se convierte en: El tablero simplex inicial corresponde a: Donde S1 es una variable de holgura (relleno). La solucion optima por el Simplex a este problema equivalente es: Luego el optimo en terminos de es: Es una tecnica que parte del rincipio de no calcular dos veces la misma informacion, por lo tanto se utilizan estructuras de almacenamiento como vectores, tablas, arreglos, archivos, con el fin de almacenarlos resultados parciales, que contribuyan a la solucion final. Este algoritmo evita calcular dos veces la misma informacion, manteniendo una tabla de resultados conocidos, la cual se va llenando a medida que seresuelven los subcasos. Es una tecnica ascendente que normalmente, empieza por los subcasosmas pequenos y mas sencillos.

Combinando sus soluciones, obtenemoslas respuestas para los subcasos cada vez mayores, hasta que llegamosa la soluciondel caso original. La programacion dinamica se aplica no solo por razones de eficiencia, sino porque permite resolver de manera eficiente problemas que no se pueden resolver por otras metodologias. El mayor numero de aplicaciones se encuentra en problemas que requieren optimizacion, ya que se pueden hallar multiples soluciones y asi evaluarlas para hallar la optima. Porgramacion dinamica.

La forma general de las soluciones desarrolladas mediante programacion dinamica requiere de los siguientes pasos: planteamiento de la solucion, mediante una serie de decisiones que garanticen que la solucion sera optima. Encontrar una solucion recursiva de la definicion. Calcular la solucion teniendo en cuenta una tabla en la que se almacenen soluciones a problemas parciales para su reutilizacion y asi evitar el nuevo calculo. Encontrar la solucion optima utilizando la informacion previamente calculada y almacenada en las tablas.