Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Programación no lineal

presentacion
by

Katherine Cafaro

on 23 January 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Programación no lineal

Modelos de Operaciones I
 OPTIMIZACIÓN RESTRINGIDA LINEALMENTE
Programación matemática
programación lineal
optimizar
cONVEXIDAD
CONCAVIDAD
RESTRICCIONES
FUNCIÓN OBJETIVO
FUNCIÓN CUADRÁTICA
INTRODUCCIÓN A LA PROGRAMACIÓN NO LINEAL


En los métodos indirectos, el problema original se sustituye por otro del cual se determina el óptimo. Como ejemplos de estos casos están la programación cuadrática, la programación separable y la programación estocástica.
TIPOS DE MODELOS DE PROGRAMACIÓN NO LINEAL

Los problemas de optimización no restringida no tienen restricciones, por lo que la función objetivo es, sencillamente,

Maximizar f (x)

Sobre todos los valores de x = (x1, x2, . . ., xn). La condición necesaria para que una solución específica x = x* sea óptima cuando f (x) es una función diferenciable es;

∂f/∂xj = 0 en x = x*, para j 1, 2, . . . , n.

- OPTIMIZACION NO RESTRINGIDA:
a) OPTIMIZACIÓN NO RESTRINGIDA DE UNA VARIABLE:
1. MÉTODO DE BISSECIÓN
Este procedimiento de búsqueda siempre se puede aplicar cuando f (x) es cóncava de forma que la segunda derivada sea negativa o cero para toda x.

Este método puede usarse también para algunas otras funciones. En particular, si x* denota la solución óptima, todo lo que se necesita es que:
2. MÉTODO DE NEWTON
La idea básica detrás del método de Newton es aproximar f (x) a la vecindad de la solución de prueba inicial mediante una función cuadrática y después maximizar (o minimizar) la función aproximada exactamente para obtener la nueva solución de prueba y así iniciar la siguiente iteración.
b) OPTIMIZACIÓN NO RESTRINGIDA DE VARIAS VARIABLES:
1. PROCEDIMIENTO DE BUSQUEDA DE GRADIENTE
Esta selección implica el uso del gradiente de la función objetivo. Como se supone que la función objetivo f (x) es diferenciable, posee un gradiente denotado por ∆f (x) en cada punto x. En particular, el gradiente en un punto específico x = x’ es el vector cuyos elementos son las derivadas parciales respectivas evaluadas en x = x’, por lo cual;
2. MÉTODO DE NEWTON
Se trabaja con una aproximación cuadrática de la función objetivo f (x), donde, en este caso, x = (x1, x2, . . ., xn). Después, esta función aproximada se maximiza (o minimiza) exactamente para obtener la nueva solución de prueba para iniciar la siguiente iteración.

Cuando la función objetivo es cóncava y tanto la solución de prueba actual x como su gradiente ∆f (x) se escriben como vectores columna, la solución x’ que maximiza la función cuadrática de aproximación tiene la forma:
Los problemas de programación cuadrática tienen restricciones lineales, pero ahora la función objetivo f (x) debe ser cuadrática.
a) PROGRAMACIÓN
CUADRÁTICA:


La programación convexa abarca una amplia clase de problemas, entre los cuales, como casos especiales, se puede mencionar todos los tipos anteriores cuando f (x) es una función cóncava que debe maximizarse.



b) PROGRAMACIÓN CONVEXA:
Los supuestos son:
1. f (x) es cóncava.
2. Cada una de las Gi(x) es convexa.

La programación separable es un caso especial de programación convexa, en donde el supuesto adicional es; Todas las funciones f (x) y Gi(x) son separables.

Una función separable es una función en la que cada término incluye una sola variable, por lo que la función se puede separar en una suma de funciones de variables individuales.

c) PROGRAMACIÓN SEPARABLE:

La programación no convexa incluye todos los problemas de programación no lineal que
no satisfacen los supuestos de programación convexa.
En este caso, aun cuando se tenga éxito en encontrar un máximo local, no hay garantía de que sea también un máximo global.

d) PROGRAMACIÓN NO CONVEXA:
ii. programación fraccional

Cuando se aplica programación no lineal a problemas de diseño de ingeniería, muchas veces la función objetivo y las funciones de restricción toman la forma;

I. PROGRAMACIOÓN GEOMÉTRICA:
En tales casos, ci y aij con frecuencia representan las constantes físicas, mientras que las xj son las variables de diseño.
Suponga que la función objetivo se encuentra en la forma de una fracción, esto es, la razón o cociente de dos funciones,
Estos problemas de programación fraccional surgen, por ejemplo, cuando se maximiza la razón de la producción entre las horas-hombre empleadas (productividad), o la ganancia entre el capital invertido (tasa de rendimiento), etc.
e) CONDICIONES DE KARUSH-KUHN-TUCKER (KKT) PARA OPTIMIZACIÓN RESTRINGIDA:
Su resultado básico se expresa en el siguiente teorema.

Suponga que f (x), g1(x), g2(x), . . ., gm(x) son funciones diferenciables que satisfacen ciertas condiciones de regularidad.13 Entonces,

x* = (x1*, x2*, . . ., x*n)

puede ser una solución óptima para el problema de programación no lineal, sólo si existen m números u1, u2, . . ., um, que satisfagan todas las siguientes condiciones KKT:

APLICACIONES DE MUESTRA
PROBLEMA DE MEZCLA DE PRODUCTOS CON ELASTICIDAD DE PRECIOS

En problemas de mezcla de productos, la meta es determinar la mezcla óptima de los niveles de elaboración de los productos de una empresa, dadas las limitaciones sobre los recursos que se necesitan para manufacturarlos, con el objeto de maximizar la ganancia total de la empresa.
PROBLEMA DE TRANSPORTE CON DESCUENTO DE PRECIOS POR VOLUMEN DE EMBARQUE
Una aplicación común del problema de transporte es determinar un plan óptimo para enviar bienes desde varios orígenes hasta varios destinos, dadas las restricciones de recursos y demanda, con el fin de minimizar el costo total de transporte. El costo por unidad enviada de un origen a un destino dados es fijo, independientemente de la cantidad que se envíe
SELECCIÓN DE UNA CARTERA DE INVERSIONES RIESGOSAS
Una práctica común entre los administradores de grandes carteras de inversión es usar, como guía, modelos de computadora basados en parte en programación no lineal.

Se emplea para determinar una cartera que, bajo ciertos supuestos, proporcione un trueque óptimo entre estos dos factores.
Los métodos de solución de la programación no lineal se pueden clasificar, de manera general, en algoritmos directos o indirectos.

Como ejemplo de los métodos directos están los algoritmos de gradiente, donde se busca el máximo (el mínimo) de un problema siguiendo la mayor tasa de aumento (disminución) de la función objetivo.

Un conjunto convexo es simplemente un conjunto de puntos tales que, para cada par de puntos de la colección, el segmento de recta que los une está totalmente contenido en ella.
la región factible de cualquier otro problema de programación lineal es un conjunto convexo.
CONVEXIDAD
La región factible de un problema de programación no lineal es un conjunto convexo siempre que todas las funciones para las restricciones sean convexas. Las funciones de variables múltiples también se pueden caracterizar como cóncavas o convexas si su curvatura es siempre hacia abajo o hacia arriba.
Una forma práctica de verificar esta característica en el caso de una función de más de dos variables cuando la función consiste en una suma de funciones más pequeñas cada una de sólo una o dos variables. Si cada función más pequeña es cóncava, entonces la función completa es cóncava. De manera similar, la función completa es convexa si cada función más pequeña es convexa.
Máximos y Mínimos Locales y Globales
El localizar valores extremos es el objetivo básico de la optimización matemática.
Los máximos y mínimos de un conjunto son los elementos mayor y menor en el conjunto, cuando existen.
En la teoría clásica de la optimización se usa el cálculo diferencial para determinar puntos extremos, o de máximo o de mínimo, para funciones sin restricciones y restringidas.
Si un problema de programación no lineal no tiene restricciones, el hecho de que la función objetivo sea cóncava garantiza que un máximo local es un máximo global. De igual manera, una función objetivo convexa asegura que un mínimo local es un mínimo global.

Si existen restricciones, se necesita una condición más para dar esta garantía, a saber, que la región factible sea un conjunto convexo.
Un punto extremo f(X) define un máximo o un minimo de ella. Matematicamente un punto X0=(X1, X2,…Xn) es máximo sí;

F(x0 + h) ≤ F(x0)
Para toda h= (h1, h2, …. hn)

En otras palabras, x0 es un valor máximo sui el valor de f en cada punto de la proximidad de x0 no es mayor que f(x0) .

En forma parecida, x0 es un mínimo sí;

F(x0 + h) ≥ f(x0)

Un máximo local no necesariamente es un máximo global (la solución óptima global). Por ejemplo, considere la función de una sola variable en el intervalo 0 < x < 5;
En general, los algoritmos de programación no lineal no pueden distinguir entre un máximo local y un máximo global; excepto si encuentran otro máximo local mejor, por lo que es determinante conocer las condiciones bajo las que se garantiza que un máximo local es un máximo global en la región factible.
Puede ser expresado de la forma:

x = (x1, x2, . . ., xn) para maximizar f (x)

sujeta a gi(x) ≤ bi, para i = 1, 2, . . ., m, y x ≥ 0,

Donde f (x) y gi(x) son funciones dadas de n variables de decisión.

Uno de los mayores desafíos en la programación no lineal es que algunos problemas exponen "grados óptimos locales"; es decir las soluciones falsas que simplemente satisfacen las exigencias sobre las derivadas de las funciones.
Es un modelo matemático de solución de problemas que contiene restricciones diferenciales no lineales.


Cuando el conjunto de restricciones, la función objetivo, o ambos, son no lineales, se dice que se trata de un problema de programación no lineal.
programación no lineal
Los algoritmos que proponen vencer esta dificultad son llamados "Optimización Global".
Definición de términos
GRACIAS POR SU ATENCIÓN
¿PREGUNTAS?
¿PREGUNTAS?
Full transcript