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

Untitled Prezi

No description
by

kimberly soto

on 27 June 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Untitled Prezi

Integrantes:
Gandara, Mariannis C.I 19603875
Soto, Kimberly C.I 22719060
Zapata Delimarth C.I 19527964
Profesora: Ing. Greezzy Mendoza

Maturín, Julio del 2013
ALGORITMOS DE PROGRAMACIÓN NO LINEAL
OPTIMIZACIÓN DE SISTEMAS Y FUNCIÓN

REPÚBLICA BOLIVARIANA DE VENEZUELA
INSTITUTO UNIVERSITARIO POLITÉCNICO
“SANTIAGO MARIÑO”
ESCUELA DE INGENIERÍA DE SISTEMAS
MATURÍN, EDO-MONAGAS

PROGRAMACIÓN NO
LINEAL (PNL)
Es aquel donde las variables de decisión se expresan como funciones no lineales ya sea en la función objetivo y/o restricciones de un modelo de optimización. Esta característica particular de los modelos no lineales permite abordar problemas donde existen economías o deseconomías de escala o en general donde los supuestos asociados a la proporcionalidad no se cumplen.
TIPOS DE PROBLEMAS DE PROGRAMACIÓN NO LINEAL
De la manera general el problema de programación no lineal consiste en encontrar:
X=(X1, X2, X3, X4, XN) para
Maximizar f(X), sujeta a
Gi(X)<= b para i=1,2…..m,
Y X=>0,
Donde f(X) y gi(x) son funciones dadas de n variables de decisión.

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.
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.
Las condiciones de Karush-Kuhn-Tucker proporcionan las condiciones necesarias para que una solución sea óptima.
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.
DIFERENCIAS ENTRE PROGRAMACIÓN LINEAL Y NO LINEAL
Variables elevadas al exponente 1.
No Producto de Variables.
Proporcionalidad.
Solución óptima es factible.
Elevadas al exponente n.
Si hay producto de variables.
No siempre hay proporcionalidad.
No siempre es factible.
Programacion lineal
Programacion no lineal
PLANTEAMIENTO DE PROBLEMAS DE PROGRAMACIÓN NO LINEAL Y OPTIMIZACIÓN
Una suposición importante de programación lineal es que todas sus funciones (Función objetivo y funciones de restricción) son lineales. Aunque, en esencia, esta suposición se cumple para muchos problemas prácticos, es frecuente que no sea así. De hecho, muchos economistas han encontrado que cierto grado de no linealidad es la regla, y no la excepción, en los problemas de planeación económica, por lo cual, muchas veces es necesario manejar problemas de programación no lineal.
De una manera general, el problema de programación no lineal consiste en encontrar x=(x1,x2,…,xn) para
maximizar ƒ(x),
sujeta a
gi(x)≤b,para i=1,2,…m,
y
x≥ 0,

Extensión Del Método Langrangiano.
Supongamos que el problema esta dado por un
Maximice z = f(x)
Sujeta
g (x) < 0 , i = 1,2 , .. , m

Resuelve el problema no restringido:
Maximize z =f(x)
Si el ultimo resultante satisface todas las restricciones deténgase, porque todas las restricciones son redundantes. De otra forma, determine k = 1.

Activar cualesquiera restricciones (es decir, convertirlas en igualdades) y optimice con el método Langrangiano f(x) sujeta a las K restricciones activas.
Si K = M, deténgase; no existe ninguna solución factible. De otra forma determine K = K + 1.
Paso 1
Paso 2
Paso 3
Para identificar puntos estacionarios de un problema restringido no lineal sujeto a restricciones de desigualdad. Estas condiciones también son suficientes bajo ciertas reglas.
Una condición necesaria para la optimización es que sea no negativa (no positiva) para problemas de maximización (minimización). Esto se justifica como sigue. Considere el caso de maximización. Como mide la taza de variación de F con respecto a g.
Condiciones de Kuhn - Tucker.
TEORÍA DE OPTIMIZACIÓN
Proporciona la teoría clásica para localizar los puntos de máximos y mínimos de problemas no lineales restringidos y no restringidos. La teoría por lo general no es adecuada para propósitos de cálculo. Existen pocas excepciones donde la teoría de Kuhn - Tucker es la base para el desarrollo de algoritmos de cálculo eficientes. La programación cuadrática, es un ejemplo del uso de las condiciones necesarias de Kuhn - Tucker.
CONDICIONES DE CONCAVIDAD Y CONVEXIDAD
1.Función cóncava:
•Función cóncava: en ese punto si f"(x) <0.
•Función estrictamente cóncava: si f"(x) <0.
•Función cóncava: si f"(x) <= 0.
2.Función convexa:
•Función convexa: en ese punto si g"(x)>0.
•Función estrictamente convexa: en ese punto si g"(x) <0.
•Función convexa: si g´(x)>=0.

Ejercicios
Una compañía importa aceite de coco de su pueblo natal. Usa este aceite para poder producir 2 clases de crema; tostado y quemado. El precio por libra de lo que pueda vender depende de la cantidad que produzca. En concreto si la compañía produce x1 Libras de tostado y x2 Libras de quemado, podrá vender todo lo que produzca a los siguientes precios en dólares:
Precio/libra de tostado: = 80 -3 x1
Precio/libra de quemado:= 60-2x2
El costo de fabricación de x1 de pan tostado y x de quemado es: 12x1+ 8x2+ 4x1+ x2
Suponiendo que puede vender todo lo que produzca, la compañía desea determinar cuantas libras da cada crema debe programar en la producción que maximice su ganancia.

Procedimiento de búsqueda unidimensional (1 variable)
Seleccione el margen de error y encuentre una cota inferior ( x ) y una cota superior ( x ) iniciales por inspección. Seleccione una solución tentativa inicial donde el punto medio es igual a (x + x) / 2.
Evalúese la derivada x=x´
Si la derivada es >= 0 hagase la cota inferior = x´
Si la derivada es < 0 hagase la cota superior = x´
Seleccione una nueva x´ aplicando la formula de punto medio.
Regla de detención
Si y por lo tanto x´ debe estar dentro del margen de error de x* deténgase. De otra manera regrese al paso 1.
TÉCNICA DE LAGRANGE
Formar lagrangiano. Fórmese una nueva función llamada lagrangiana la cual abarca una nueva variable que se designa como la función para un modelo de maximizar quedaría de la siguiente forma:
L(x1,x2) = f (x1,x2) + λ (b - (x1,x2))
Obtener las derivadas parciales. Calculase las derivadas parciales con respecto a cada una de las variables e igualase a cero las tres derivadas parciales.
D* = - (gx2)2 Lx1x1 – (gx)2 Lx2x2 + 2gxgx2Lx1x2
Si D > 0 entonces (x1*,x2*) Es un máximo.
Si D < 0 entonces (x1*,x2*) Es un mínimo.
Si D = 0 No se obtiene conclusión.
Encontrar todas las soluciones que satisfacen las ecuaciones deducidas del paso 2.
Determinar si los puntos óptimos producen un máximo o un mínimo la comprobación se hace calculando para el punto optimo la siguiente expresión.

Una compañía planea gastar $10 000 dólares en publicidad, cuesta $3 000 dólares un minuto de publicidad en televisión y $100 dólares 1 minuto de publicidad en radio, Si la empresa compra "x" minutos de comerciales en televisión y "y" minutos de comerciales en radio su ingreso en miles de dólares .Esta dado por la función. f(x,y)= -2x2-y2+xy+8x+3y encontrar los valores de x, y que proporcionen el máximo ingreso .
x = cantidad de minutos en televisión.
y = cantidad de minutos en radio.

Gracias por su atencion...
Full transcript